1/*-
2 * Copyright (c) 2007, Erik Tews, Andrei Pychkine and Ralf-Philipp Weinmann
3 *		       <aircrack-ptw@cdc.informatik.tu-darmstadt.de>
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 * 1. Redistributions of source code must retain the above copyright
10 *    notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 *    notice, this list of conditions and the following disclaimer in the
13 *    documentation and/or other materials provided with the distribution.
14 *
15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
16 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
18 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
19 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
20 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
21 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
22 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
23 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
24 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
25 * SUCH DAMAGE.
26 */
27#include <string.h>
28#include <stdio.h>
29#include <stdlib.h>
30#include "aircrack-ptw-lib.h"
31
32
33#define n PTW_n
34#define CONTROLSESSIONS PTW_CONTROLSESSIONS
35#define KEYHSBYTES PTW_KEYHSBYTES
36#define KSBYTES PTW_KSBYTES
37#define IVBYTES PTW_IVBYTES
38#define TESTBYTES 6
39
40
41// Internal state of rc4
42typedef struct {
43	uint8_t i;
44	uint8_t j;
45	uint8_t s[n];
46} rc4state;
47
48
49// Helper structures for sorting
50typedef struct {
51	int keybyte;
52	uint8_t value;
53	int distance;
54} sorthelper;
55
56typedef struct {
57	int keybyte;
58	double difference;
59} doublesorthelper;
60
61// The rc4 initial state, the idendity permutation
62static const uint8_t rc4initial[] =
63{0,1,2,3,4,5,6,7,8,9,10,
6411,12,13,14,15,16,17,18,19,20,
6521,22,23,24,25,26,27,28,29,30,
6631,32,33,34,35,36,37,38,39,40,
6741,42,43,44,45,46,47,48,49,50,
6851,52,53,54,55,56,57,58,59,60,
6961,62,63,64,65,66,67,68,69,70,
7071,72,73,74,75,76,77,78,79,80,
7181,82,83,84,85,86,87,88,89,90,
7291,92,93,94,95,96,97,98,99,100,
73101,102,103,104,105,106,107,108,109,110,
74111,112,113,114,115,116,117,118,119,120,
75121,122,123,124,125,126,127,128,129,130,
76131,132,133,134,135,136,137,138,139,140,
77141,142,143,144,145,146,147,148,149,150,
78151,152,153,154,155,156,157,158,159,160,
79161,162,163,164,165,166,167,168,169,170,
80171,172,173,174,175,176,177,178,179,180,
81181,182,183,184,185,186,187,188,189,190,
82191,192,193,194,195,196,197,198,199,200,
83201,202,203,204,205,206,207,208,209,210,
84211,212,213,214,215,216,217,218,219,220,
85221,222,223,224,225,226,227,228,229,230,
86231,232,233,234,235,236,237,238,239,240,
87241,242,243,244,245,246,247,248,249,250,
88251,252,253,254,255};
89
90
91// Values for p_correct_i
92static const double eval[] = {
930.00534392069257663,
940.00531787585068872,
950.00531345769225911,
960.00528812219217898,
970.00525997750378221,
980.00522647312237696,
990.00519132541143668,
1000.0051477139367225,
1010.00510438884847959,
1020.00505484662057323,
1030.00500502783556246,
1040.00495094196451801,
1050.0048983441590402};
106
107// For sorting
108static int compare(const void * ina, const void * inb) {
109        PTW_tableentry * a = (PTW_tableentry * )ina;
110        PTW_tableentry * b = (PTW_tableentry * )inb;
111        if (a->votes > b->votes) {
112                return -1;
113        } else if (a->votes == b->votes) {
114                return 0;
115        } else {
116                return 1;
117        }
118}
119
120// For sorting
121static int comparedoublesorthelper(const void * ina, const void * inb) {
122        doublesorthelper * a = (doublesorthelper * )ina;
123        doublesorthelper * b = (doublesorthelper * )inb;
124        if (a->difference > b->difference) {
125                return 1;
126        } else if (a->difference == b->difference) {
127                return 0;
128        } else {
129                return -1;
130        }
131}
132
133
134// RC4 key setup
135static void rc4init ( uint8_t * key, int keylen, rc4state * state) {
136	int i;
137	int j;
138	uint8_t tmp;
139	memcpy(state->s, &rc4initial, n);
140	j = 0;
141	for (i = 0; i < n; i++) {
142		j = (j + state->s[i] + key[i % keylen]) % n;
143		tmp = state->s[i];
144		state->s[i] = state->s[j];
145		state->s[j] = tmp;
146	}
147	state->i = 0;
148	state->j = 0;
149}
150
151// RC4 key stream generation
152static uint8_t rc4update(rc4state * state) {
153	uint8_t tmp;
154	uint8_t k;
155	state->i++;
156	state->j += state->s[state->i];
157	tmp = state->s[state->i];
158	state->s[state->i] = state->s[state->j];
159	state->s[state->j] = tmp;
160	k = state->s[state->i] + state->s[state->j];
161
162	return state->s[k];
163}
164
165// For sorting
166static int comparesorthelper(const void * ina, const void * inb) {
167	sorthelper * a = (sorthelper * ) ina;
168	sorthelper * b = (sorthelper * ) inb;
169	if (a->distance > b->distance) {
170		return 1;
171	} else if (a->distance == b->distance) {
172		return 0;
173	} else {
174		return -1;
175	}
176}
177
178/*
179 * Guess the values for sigma_i
180 * iv - IV which was used for this packet
181 * keystream - keystream recovered
182 * result - buffer for the values of sigma_i
183 * kb - how many keybytes should be guessed
184 */
185static void guesskeybytes(uint8_t * iv, uint8_t * keystream, uint8_t * result, int kb) {
186        uint8_t state[n];
187        uint8_t j = 0;
188        uint8_t tmp;
189        int i;
190        int jj = IVBYTES;
191        uint8_t ii;
192        uint8_t s = 0;
193        memcpy(state, rc4initial, n);
194        for (i = 0; i < IVBYTES; i++) {
195                j += state[i] + iv[i];
196                tmp = state[i];
197                state[i] = state[j];
198                state[j] = tmp;
199        }
200        for (i = 0; i < kb; i++) {
201                tmp = jj - keystream[jj-1];
202                ii = 0;
203                while(tmp != state[ii]) {
204                        ii++;
205                }
206                s += state[jj];
207                ii -= (j+s);
208                result[i] = ii;
209                jj++;
210        }
211        return;
212}
213
214/*
215 * Is a guessed key correct?
216 */
217static int correct(PTW_attackstate * state, uint8_t * key, int keylen) {
218	int i;
219        int j;
220        uint8_t keybuf[PTW_KSBYTES];
221        rc4state rc4state;
222
223        for (i = 0; i < state->sessions_collected; i++) {
224                memcpy(&keybuf[IVBYTES], key, keylen);
225                memcpy(keybuf, state->sessions[i].iv, IVBYTES);
226                rc4init(keybuf, keylen+IVBYTES, &rc4state);
227                for (j = 0; j < TESTBYTES; j++) {
228                        if  ((rc4update(&rc4state) ^ state->sessions[i].keystream[j]) != 0) {
229                                return 0;
230                        }
231                }
232        }
233        return 1;
234}
235
236/*
237 * Calculate the squaresum of the errors for both distributions
238 */
239static void getdrv(PTW_tableentry orgtable[][n], int keylen, double * normal, double * ausreiser) {
240        int i,j;
241	int numvotes = 0;
242        double e;
243	double e2;
244	double emax;
245        double help = 0.0;
246	double maxhelp = 0;
247	double maxi = 0;
248        for (i = 0; i < n; i++) {
249                numvotes += orgtable[0][i].votes;
250        }
251        e = numvotes/n;
252        for (i = 0; i < keylen; i++) {
253		emax = eval[i] * numvotes;
254		e2 = ((1.0 - eval[i])/255.0) * numvotes;
255		normal[i] = 0;
256		ausreiser[i] = 0;
257		maxhelp = 0;
258		maxi = 0;
259		for (j = 0; j < n; j++) {
260			if (orgtable[i][j].votes > maxhelp) {
261				maxhelp = orgtable[i][j].votes;
262				maxi = j;
263			}
264		}
265                for (j = 0; j < n; j++) {
266			if (j == maxi) {
267				help = (1.0-orgtable[i][j].votes/emax);
268			} else {
269				help = (1.0-orgtable[i][j].votes/e2);
270			}
271			help = help*help;
272			ausreiser[i] += help;
273			help = (1.0-orgtable[i][j].votes/e);
274			help = help*help;
275			normal[i] += help;
276                }
277        }
278}
279
280/*
281 * Guess a single keybyte
282 */
283static int doRound(PTW_tableentry sortedtable[][n], int keybyte, int fixat, uint8_t fixvalue, int * searchborders, uint8_t * key, int keylen, PTW_attackstate * state, uint8_t sum, int * strongbytes) {
284	int i;
285	uint8_t tmp;
286	if (keybyte == keylen) {
287		return correct(state, key, keylen);
288	} else if (strongbytes[keybyte] == 1) {
289		// printf("assuming byte %d to be strong\n", keybyte);
290		tmp = 3 + keybyte;
291		for (i = keybyte-1; i >= 1; i--) {
292			tmp += 3 + key[i] + i;
293			key[keybyte] = 256-tmp;
294			if(doRound(sortedtable, keybyte+1, fixat, fixvalue, searchborders, key, keylen, state, (256-tmp+sum)%256, strongbytes) == 1) {
295				printf("hit with strongbyte for keybyte %d\n", keybyte);
296				return 1;
297			}
298		}
299		return 0;
300	} else if (keybyte == fixat) {
301		key[keybyte] = fixvalue-sum;
302		return doRound(sortedtable, keybyte+1, fixat, fixvalue, searchborders, key, keylen, state, fixvalue, strongbytes);
303	} else {
304		for (i = 0; i < searchborders[keybyte]; i++) {
305			key[keybyte] = sortedtable[keybyte][i].b - sum;
306			if (doRound(sortedtable, keybyte+1, fixat, fixvalue, searchborders, key, keylen, state, sortedtable[keybyte][i].b, strongbytes) == 1) {
307				return 1;
308			}
309		}
310		return 0;
311	}
312}
313
314/*
315 * Do the actual computation of the key
316 */
317static int doComputation(PTW_attackstate * state, uint8_t * key, int keylen, PTW_tableentry table[][n], sorthelper * sh2, int * strongbytes, int keylimit) {
318	int i,j;
319	int choices[KEYHSBYTES];
320	int prod;
321	int fixat;
322	int fixvalue;
323
324	for (i = 0; i < keylen; i++) {
325		if (strongbytes[i] == 1) {
326			choices[i] = i;
327		} else {
328			choices[i] = 1;
329		}
330	}
331	i = 0;
332	prod = 0;
333	fixat = -1;
334	fixvalue = 0;
335
336	while(prod < keylimit) {
337		if (doRound(table, 0, fixat, fixvalue, choices, key, keylen, state, 0, strongbytes) == 1) {
338			// printf("hit with %d choices\n", prod);
339			return 1;
340		}
341		choices[sh2[i].keybyte]++;
342		fixat = sh2[i].keybyte;
343		// printf("choices[%d] is now %d\n", sh2[i].keybyte, choices[sh2[i].keybyte]);
344		fixvalue = sh2[i].value;
345		prod = 1;
346		for (j = 0; j < keylen; j++) {
347			prod *= choices[j];
348		}
349		do {
350			i++;
351		} while (strongbytes[sh2[i].keybyte] == 1);
352
353	}
354	return 0;
355}
356
357
358/*
359 * Guess which key bytes could be strong and start actual computation of the key
360 */
361int PTW_computeKey(PTW_attackstate * state, uint8_t * keybuf, int keylen, int testlimit) {
362	int strongbytes[KEYHSBYTES];
363	double normal[KEYHSBYTES];
364	double ausreisser[KEYHSBYTES];
365	doublesorthelper helper[KEYHSBYTES];
366	int simple, onestrong, twostrong;
367	int i,j;
368
369	onestrong = (testlimit/10)*2;
370	twostrong = (testlimit/10)*1;
371	simple = testlimit - onestrong - twostrong;
372
373	PTW_tableentry (*table)[n] = alloca(sizeof(PTW_tableentry) * n * keylen);
374	if (table == NULL) {
375		printf("could not allocate memory\n");
376		exit(-1);
377	}
378	memcpy(table, state->table, sizeof(PTW_tableentry) * n * keylen);
379
380	// now, sort the table
381	for (i = 0; i < keylen; i++) {
382                qsort(&table[i][0], n, sizeof(PTW_tableentry), &compare);
383		strongbytes[i] = 0;
384        }
385
386	sorthelper (* sh)[n-1] = alloca(sizeof(sorthelper) * (n-1) * keylen);
387	if (sh == NULL) {
388		printf("could not allocate memory\n");
389		exit(-1);
390	}
391
392
393	for (i = 0; i < keylen; i++) {
394		for (j = 1; j < n; j++) {
395			sh[i][j-1].distance = table[i][0].votes - table[i][j].votes;
396			sh[i][j-1].value = table[i][j].b;
397			sh[i][j-1].keybyte = i;
398		}
399	}
400	qsort(sh, (n-1)*keylen, sizeof(sorthelper), &comparesorthelper);
401
402
403	if (doComputation(state, keybuf, keylen, table, (sorthelper *) sh, strongbytes, simple)) {
404		return 1;
405	}
406
407	// Now one strong byte
408	getdrv(state->table, keylen, normal, ausreisser);
409	for (i = 0; i < keylen-1; i++) {
410		helper[i].keybyte = i+1;
411		helper[i].difference = normal[i+1] - ausreisser[i+1];
412	}
413	qsort(helper, keylen-1, sizeof(doublesorthelper), &comparedoublesorthelper);
414	strongbytes[helper[0].keybyte] = 1;
415	if (doComputation(state, keybuf, keylen, table, (sorthelper *) sh, strongbytes, onestrong)) {
416		return 1;
417	}
418
419	// two strong bytes
420	strongbytes[helper[1].keybyte] = 1;
421	if (doComputation(state, keybuf, keylen, table, (sorthelper *) sh, strongbytes, twostrong)) {
422		return 1;
423	}
424
425	return 0;
426}
427
428/*
429 * Add a new session to the attack
430 * state - state of attack
431 * iv - IV used in the session
432 * keystream - recovered keystream from the session
433 */
434int PTW_addsession(PTW_attackstate * state, uint8_t * iv, uint8_t * keystream) {
435	int i;
436	int il;
437	int ir;
438	uint8_t buf[PTW_KEYHSBYTES];
439
440	i = (iv[0] << 16) | (iv[1] << 8) | (iv[2]);
441	il = i/8;
442	ir = 1 << (i%8);
443	if ((state->seen_iv[il] & ir) == 0) {
444		state->packets_collected++;
445		state->seen_iv[il] |= ir;
446		guesskeybytes(iv, keystream, buf, PTW_KEYHSBYTES);
447                for (i = 0; i < KEYHSBYTES; i++) {
448                	state->table[i][buf[i]].votes++;
449                }
450		if (state->sessions_collected < CONTROLSESSIONS) {
451			memcpy(state->sessions[state->sessions_collected].iv, iv, IVBYTES);
452			memcpy(state->sessions[state->sessions_collected].keystream, keystream, KSBYTES);
453			state->sessions_collected++;
454		}
455		return 1;
456	} else {
457		return 0;
458	}
459}
460
461/*
462 * Allocate a new attackstate
463 */
464PTW_attackstate * PTW_newattackstate() {
465	int i,k;
466	PTW_attackstate * state = NULL;
467	state = malloc(sizeof(PTW_attackstate));
468	if (state == NULL) {
469		return NULL;
470	}
471	bzero(state, sizeof(PTW_attackstate));
472	for (i = 0; i < PTW_KEYHSBYTES; i++) {
473                for (k = 0; k < n; k++) {
474                        state->table[i][k].b = k;
475                }
476        }
477        return state;
478}
479
480/*
481 * Free an allocated attackstate
482 */
483void PTW_freeattackstate(PTW_attackstate * state) {
484	free(state);
485	return;
486}
487
488