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: src/tools/tools/net80211/wesside/wesside/aircrack-ptw-lib.c,v 1.2 2007/04/09 15:43:43 sam Exp $
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
44 typedef struct {
45 uint8_t i;
46 uint8_t j;
47 uint8_t s[n];
48 } rc4state;
49
50
51 // Helper structures for sorting
52 typedef struct {
53 int keybyte;
54 uint8_t value;
55 int distance;
56 } sorthelper;
57
58 typedef struct {
59 int keybyte;
60 double difference;
61 } doublesorthelper;
62
63 // The rc4 initial state, the idendity permutation
64 static const uint8_t rc4initial[] =
65 {0,1,2,3,4,5,6,7,8,9,10,
66 11,12,13,14,15,16,17,18,19,20,
67 21,22,23,24,25,26,27,28,29,30,
68 31,32,33,34,35,36,37,38,39,40,
69 41,42,43,44,45,46,47,48,49,50,
70 51,52,53,54,55,56,57,58,59,60,
71 61,62,63,64,65,66,67,68,69,70,
72 71,72,73,74,75,76,77,78,79,80,
73 81,82,83,84,85,86,87,88,89,90,
74 91,92,93,94,95,96,97,98,99,100,
75 101,102,103,104,105,106,107,108,109,110,
76 111,112,113,114,115,116,117,118,119,120,
77 121,122,123,124,125,126,127,128,129,130,
78 131,132,133,134,135,136,137,138,139,140,
79 141,142,143,144,145,146,147,148,149,150,
80 151,152,153,154,155,156,157,158,159,160,
81 161,162,163,164,165,166,167,168,169,170,
82 171,172,173,174,175,176,177,178,179,180,
83 181,182,183,184,185,186,187,188,189,190,
84 191,192,193,194,195,196,197,198,199,200,
85 201,202,203,204,205,206,207,208,209,210,
86 211,212,213,214,215,216,217,218,219,220,
87 221,222,223,224,225,226,227,228,229,230,
88 231,232,233,234,235,236,237,238,239,240,
89 241,242,243,244,245,246,247,248,249,250,
90 251,252,253,254,255};
91
92
93 // Values for p_correct_i
94 static const double eval[] = {
95 0.00534392069257663,
96 0.00531787585068872,
97 0.00531345769225911,
98 0.00528812219217898,
99 0.00525997750378221,
100 0.00522647312237696,
101 0.00519132541143668,
102 0.0051477139367225,
103 0.00510438884847959,
104 0.00505484662057323,
105 0.00500502783556246,
106 0.00495094196451801,
107 0.0048983441590402};
108
109 // For sorting
compare(const void * ina,const void * inb)110 static 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
comparedoublesorthelper(const void * ina,const void * inb)123 static 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
rc4init(uint8_t * key,int keylen,rc4state * state)137 static 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
rc4update(rc4state * state)154 static 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
comparesorthelper(const void * ina,const void * inb)168 static 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 */
guesskeybytes(uint8_t * iv,uint8_t * keystream,uint8_t * result,int kb)187 static 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 */
correct(PTW_attackstate * state,uint8_t * key,int keylen)219 static 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 */
getdrv(PTW_tableentry orgtable[][n],int keylen,double * normal,double * ausreiser)241 static 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 */
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)285 static 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 */
doComputation(PTW_attackstate * state,uint8_t * key,int keylen,PTW_tableentry table[][n],sorthelper * sh2,int * strongbytes,int keylimit)319 static 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 */
PTW_computeKey(PTW_attackstate * state,uint8_t * keybuf,int keylen,int testlimit)363 int 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 */
PTW_addsession(PTW_attackstate * state,uint8_t * iv,uint8_t * keystream)436 int 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 */
PTW_newattackstate()466 PTW_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 */
PTW_freeattackstate(PTW_attackstate * state)485 void PTW_freeattackstate(PTW_attackstate * state) {
486 free(state);
487 return;
488 }
489