1 /*
2 * Copyright (c) 2007-2009 Erik Tews, Andrei Pychkine and Ralf-Philipp
3 * Weinmann.
4 * 2013 Ramiro Polla
5 *
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
19 *
20 *
21 * In addition, as a special exception, the copyright holders give
22 * permission to link the code of portions of this program with the
23 * OpenSSL library under certain conditions as described in each
24 * individual source file, and distribute linked combinations
25 * including the two.
26 * You must obey the GNU General Public License in all respects
27 * for all of the code used other than OpenSSL. * If you modify
28 * file(s) with this exception, you may extend this exception to your
29 * version of the file(s), but you are not obligated to do so. * If you
30 * do not wish to do so, delete this exception statement from your
31 * version. * If you delete this exception statement from all source
32 * files in the program, then also delete it here.
33 */
34
35 #include <string.h>
36 #include <stdio.h>
37 #include <stdlib.h>
38 #include <pthread.h>
39 #ifdef HAVE_SYS_TYPES_H
40 #include <sys/types.h>
41 #endif
42 #if defined(__sun__)
43 #include <alloca.h>
44 #endif
45 #include "pcap.h"
46 #include "aircrack-ptw-lib.h"
47 #include "aircrack-ng.h"
48
49 #define n PTW_n
50 #define CONTROLSESSIONS PTW_CONTROLSESSIONS
51 #define KSBYTES PTW_KSBYTES
52 #define IVBYTES PTW_IVBYTES
53 #define TESTBYTES 6
54
55 static struct options opt;
56
57 // Internal state of rc4
58 typedef struct
59 {
60 uint32_t s[n];
61 uint8_t i;
62 uint8_t j;
63 } rc4state;
64
65 // Helper structures for sorting
66 typedef struct
67 {
68 int keybyte;
69 uint8_t value;
70 int distance;
71 } sorthelper;
72
73 typedef struct
74 {
75 int keybyte;
76 double difference;
77 } doublesorthelper;
78
79 // The rc4 initial state, the idendity permutation
80 static const uint32_t rc4initial[] = {
81 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
82 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
83 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44,
84 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59,
85 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74,
86 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89,
87 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104,
88 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119,
89 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134,
90 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149,
91 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164,
92 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179,
93 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194,
94 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209,
95 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, 224,
96 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239,
97 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254,
98 255};
99
100 // Values for p_correct_i
101 static const double eval[] = {0.00534392069257663,
102 0.00531787585068872,
103 0.00531345769225911,
104 0.00528812219217898,
105 0.00525997750378221,
106 0.00522647312237696,
107 0.00519132541143668,
108 0.0051477139367225,
109 0.00510438884847959,
110 0.00505484662057323,
111 0.00500502783556246,
112 0.00495094196451801,
113 0.0048983441590402};
114
115 int tried, max_tries;
116 int depth[KEYHSBYTES];
117 PTW_tableentry keytable[KEYHSBYTES][n];
118
119 // Check if optmizied RC4 for AMD64 has to be compiled
120 #if defined(__amd64) && defined(__SSE2__) \
121 && (!defined(__clang__) \
122 || (defined(__clang__) \
123 && (__clang_major__ >= 4 \
124 || (__clang_major__ == 3 && __clang_minor__ >= 9))))
125 #define USE_AMD64_RC4_OPTIMIZED
126 #endif
127
128 // For sorting
compare(const void * ina,const void * inb)129 static int compare(const void * ina, const void * inb)
130 {
131 PTW_tableentry * a = (PTW_tableentry *) ina;
132 PTW_tableentry * b = (PTW_tableentry *) inb;
133 return b->votes - a->votes;
134 }
135
136 // For sorting
comparedoublesorthelper(const void * ina,const void * inb)137 static int comparedoublesorthelper(const void * ina, const void * inb)
138 {
139 doublesorthelper * a = (doublesorthelper *) ina;
140 doublesorthelper * b = (doublesorthelper *) inb;
141 if (a->difference > b->difference)
142 {
143 return 1;
144 }
145 else if (a->difference == b->difference)
146 {
147 return 0;
148 }
149 else
150 {
151 return -1;
152 }
153 }
154
155 #ifdef USE_AMD64_RC4_OPTIMIZED
156 static const uint32_t __attribute__((used)) __attribute__((aligned(16)))
157 x0123[4]
158 = {0, 1, 2, 3};
159 static const uint32_t __attribute__((used)) __attribute__((aligned(16)))
160 x4444[4]
161 = {4, 4, 4, 4};
162 static int
rc4test_amd64_sse2(uint8_t * key,int keylen,uint8_t * iv,uint8_t * keystream)163 rc4test_amd64_sse2(uint8_t * key, int keylen, uint8_t * iv, uint8_t * keystream)
164 {
165 int idx, i, j;
166 int scratch1, scratch2;
167
168 __asm__ volatile(
169 #define state "%%rsp"
170 #define keybuf "0x400(%%rsp)"
171 #define keystream_ "0x428(%%rsp)"
172 // setup stack
173 "movq %%rsp, %q0 \n\t"
174 "subq $0x430, %%rsp \n\t"
175 "andq $-16, %%rsp \n\t"
176 "movq %q0, -8(%%rsp) \n\t"
177
178 // save keystream variable
179 "movq %q6, " keystream_ " \n\t"
180
181 // keylen += IVBYTES
182 "addl $3, %k4 \n\t"
183
184 // memcpy(keybuf, iv, IVBYTES);
185 "movl (%q5), %k1 \n\t"
186 "movl %k1 , " keybuf " \n\t"
187 // memcpy(&keybuf[IVBYTES], key, keylen);
188 "movdqa (%q3), %%xmm0 \n\t"
189 "cmpl $16, %k4 \n\t"
190 "movdqu %%xmm0, 3+" keybuf " \n\t"
191 "jng .Lsmall_key1 \n\t"
192 "movdqa 16(%q3), %%xmm1 \n\t"
193 "movdqu %%xmm1,19+" keybuf " \n\t"
194 ".Lsmall_key1: \n\t"
195
196 // key = keybuf
197 "lea " keybuf ", %q3 \n\t"
198 // load xmm registers
199 "movdqa %q9, %%xmm0 \n\t"
200 "movdqa %q10, %%xmm1 \n\t"
201 // clear some registers
202 "xorq %q0, %q0 \n\t" // idx
203 "xorq %q1, %q1 \n\t" // i
204 "xorq %q2, %q2 \n\t" // j
205
206 // build identity array
207 ".p2align 4 \n\t"
208 ".Lidentity_loop: \n\t"
209 "movdqa %%xmm0, (" state ",%q1,4)\n\t"
210 "addb $4, %b1 \n\t"
211 "paddd %%xmm1, %%xmm0 \n\t"
212 "jnc .Lidentity_loop \n\t"
213
214 // load state into register
215 "movq " state ", %q1 \n\t"
216
217 // %q4 = and mask for idx
218 "movq %q4, %q8 \n\t"
219 "cmpq $16, %q8 \n\t"
220 "movq $15, %q4 \n\t"
221 "je .Lsmall_key2 \n\t"
222 "shrq $1, %q4 \n\t"
223 ".Lsmall_key2: \n\t"
224
225 // init array with key
226 ".p2align 4 \n\t"
227 ".init_loop: \n\t"
228 "movl %k0, %k8 \n\t" /* scratch2 = idx */
229 "movl (%q1), %k5 \n\t" /* s1 = state[i] */
230 "leal 1(%q0,1), %k0 \n\t" /* idx++ */
231 "movzbl (%q3,%q8,1), %k6 \n\t" /* key_n = key[scratch2]
232 */
233 "leal (%q5,%q6,1), %k8 \n\t" /* scratch2 = s1 + key_n */
234 "addl %k8, %k2 \n\t" /* j += scratch2 */
235 "andl %k4, %k0 \n\t" /* idx &= mask */
236 "movzbl %b2, %k8 \n\t" /* scratch2 = j */
237 "movl (" state
238 ",%q8,4), %k7 \n\t" /* s2 = state[scratch2] */
239 "movl %k7, (%q1) \n\t" /* state[i] = s2 */
240 "addq $4, %q1 \n\t" /* i++ */
241 "movl %k5, (" state ",%q8,4) \n\t" /* state[scratch2] = s1 */
242 "cmpq %q1, %q3 \n\t" /* state == &state[0x100]
243 */
244 "jne .init_loop \n\t"
245
246 // restore keystream variable
247 "movq " keystream_ ", %q6 \n\t"
248
249 // clear some registers
250 "xorq %q2, %q2 \n\t" // j = 0
251 "xorq %q0, %q0 \n\t" // result
252
253 #define RC4TEST_LOOP(offset) \
254 "movl 4*" offset "(" state "), %k5\n\t" /* s1 = state[i] */ \
255 "leal (%q5,%q2,1), %k4 \n\t" /* */ \
256 "movzbl %b4, %k2 \n\t" /* j += s1 */ \
257 "movl (" state ",%q2,4), %k1 \n\t" /* s2 = state[j] */ \
258 "movl %k1, 4*" offset "(" state ")\n\t" /* state[i] = s2 */ \
259 "movl %k5, (" state ",%q2,4) \n\t" /* state[j] = s1 */ \
260 "addb %b1, %b5 \n\t" /* s1 += s2; */ \
261 "movb (" state ",%q5,4), %b3 \n\t" /* ret = state[s1] */ \
262 "cmpb %b3, " offset "-1(%q6) \n\t" /* ret == keystream[i-1] */ \
263 "jne .ret \n\t"
264
265 RC4TEST_LOOP("1") RC4TEST_LOOP("2") RC4TEST_LOOP("3") RC4TEST_LOOP("4")
266 RC4TEST_LOOP("5") RC4TEST_LOOP("6")
267
268 #undef RC4TEST_LOOP
269
270 "addb $1, %b0 \n\t"
271 ".ret: \n\t"
272
273 // restore stack
274 "movq -8(%%rsp), %%rsp \n\t"
275
276 : "=&r"(idx),
277 "=&r"(i),
278 "=&r"(j),
279 "+r"(key),
280 "+r"(keylen),
281 "+r"(iv),
282 "+r"(keystream),
283 "=&r"(scratch1),
284 "=&r"(scratch2)
285 : "m"(x0123[0]), "m"(x4444[0])
286 : "xmm0", "xmm1");
287 #undef state
288 #undef keybuf
289 #undef keystream_
290
291 return idx;
292 }
293 #endif
294
295 // RC4 key setup
rc4init(uint8_t * key,int keylen,rc4state * state)296 static void rc4init(uint8_t * key, int keylen, rc4state * state)
297 {
298 int i;
299 unsigned char j;
300 uint8_t tmp;
301 int idx = 0;
302 memcpy(state->s, &rc4initial, sizeof(rc4initial));
303 j = 0;
304 for (i = 0; i < n; i++)
305 {
306 /* this should be:
307 j = (j + state->s[i] + key[i % keylen]) % n;
308 but as "j" is declared as unsigned char and n equals 256,
309 we can "optimize" it
310 */
311 j = (j + state->s[i] + key[idx]);
312 if (++idx == keylen) idx = 0;
313 tmp = state->s[i];
314 state->s[i] = state->s[j];
315 state->s[j] = tmp;
316 }
317 state->i = 0;
318 state->j = 0;
319 }
320
321 // RC4 key stream generation
rc4update(rc4state * state)322 static uint8_t rc4update(rc4state * state)
323 {
324 uint8_t tmp;
325 uint8_t k;
326 state->i++;
327 state->j += state->s[state->i];
328 tmp = state->s[state->i];
329 state->s[state->i] = state->s[state->j];
330 state->s[state->j] = tmp;
331 k = state->s[state->i] + state->s[state->j];
332
333 return state->s[k];
334 }
335
rc4test(uint8_t * key,int keylen,uint8_t * iv,uint8_t * keystream)336 static int rc4test(uint8_t * key, int keylen, uint8_t * iv, uint8_t * keystream)
337 {
338 uint8_t keybuf[PTW_KSBYTES];
339 rc4state rc4state;
340 int j;
341 memcpy(&keybuf[IVBYTES], key, keylen);
342 memcpy(keybuf, iv, IVBYTES);
343 rc4init(keybuf, keylen + IVBYTES, &rc4state);
344 for (j = 0; j < TESTBYTES; j++)
345 {
346 if ((rc4update(&rc4state) ^ keystream[j]) != 0)
347 {
348 return 0;
349 }
350 }
351 return 1;
352 }
353
354 // For sorting
comparesorthelper(const void * ina,const void * inb)355 static int comparesorthelper(const void * ina, const void * inb)
356 {
357 sorthelper * a = (sorthelper *) ina;
358 sorthelper * b = (sorthelper *) inb;
359 return a->distance - b->distance;
360 }
361
362 /*
363 * Guess the values for sigma_i
364 * ivlen - how long was the iv (is used differently in original klein attack)
365 * iv - IV which was used for this packet
366 * keystream - keystream recovered
367 * result - buffer for the values of sigma_i
368 * kb - how many keybytes should be guessed
369 */
guesskeybytes(int ivlen,uint8_t * iv,uint8_t * keystream,uint8_t * result,int kb)370 static void guesskeybytes(
371 int ivlen, uint8_t * iv, uint8_t * keystream, uint8_t * result, int kb)
372 {
373 uint32_t state[n];
374 uint8_t j = 0;
375 uint8_t tmp;
376 int i;
377 int jj = ivlen;
378 uint8_t ii;
379 uint8_t s = 0;
380 memcpy(state, &rc4initial, sizeof(rc4initial));
381 for (i = 0; i < ivlen; i++)
382 {
383 j += state[i] + iv[i];
384 tmp = state[i];
385 state[i] = state[j];
386 state[j] = tmp;
387 }
388 for (i = 0; i < kb; i++)
389 {
390 tmp = jj - keystream[jj - 1];
391 ii = 0;
392 while (tmp != state[ii])
393 {
394 ii++;
395 }
396 s += state[jj];
397 ii -= (j + s);
398 result[i] = ii;
399 jj++;
400 }
401 return;
402 }
403
404 /*
405 * Is a guessed key correct?
406 */
correct(PTW_attackstate * state,uint8_t * key,int keylen)407 static int correct(PTW_attackstate * state, uint8_t * key, int keylen)
408 {
409 int i;
410 int k;
411
412 // We need at least 3 sessions to be somehow certain
413 if (state->sessions_collected < 3)
414 {
415 return 0;
416 }
417
418 tried++;
419
420 k = rand() % (state->sessions_collected - 10);
421 for (i = k; i < k + 10; i++)
422 {
423 if (!state->rc4test(key,
424 keylen,
425 state->sessions[i].iv,
426 state->sessions[i].keystream))
427 return 0;
428 }
429 return 1;
430 }
431
432 /*
433 * Calculate the squaresum of the errors for both distributions
434 */
getdrv(PTW_tableentry orgtable[][n],int keylen,double * normal,double * ausreiser)435 static void getdrv(PTW_tableentry orgtable[][n],
436 int keylen,
437 double * normal,
438 double * ausreiser)
439 {
440 int i, j;
441 int numvotes = 0;
442 double e;
443 double e2;
444 double emax;
445 double help = 0.0;
446 double maxhelp = 0;
447 double maxi = 0;
448 for (i = 0; i < n; i++)
449 {
450 numvotes += orgtable[0][i].votes;
451 }
452 e = numvotes / n;
453 for (i = 0; i < keylen; i++)
454 {
455 emax = eval[i] * numvotes;
456 e2 = ((1.0 - eval[i]) / 255.0) * numvotes;
457 normal[i] = 0;
458 ausreiser[i] = 0;
459 maxhelp = 0;
460 maxi = 0;
461 for (j = 0; j < n; j++)
462 {
463 if (orgtable[i][j].votes > maxhelp)
464 {
465 maxhelp = orgtable[i][j].votes;
466 maxi = j;
467 }
468 }
469 for (j = 0; j < n; j++)
470 {
471 if (j == maxi)
472 {
473 help = (1.0 - orgtable[i][j].votes / emax);
474 }
475 else
476 {
477 help = (1.0 - orgtable[i][j].votes / e2);
478 }
479 help = help * help;
480 ausreiser[i] += help;
481 help = (1.0 - orgtable[i][j].votes / e);
482 help = help * help;
483 normal[i] += help;
484 }
485 }
486 }
487
488 /*
489 * Guess a single keybyte
490 */
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,int * bf,int validchars[][n])491 static int doRound(PTW_tableentry sortedtable[][n],
492 int keybyte,
493 int fixat,
494 uint8_t fixvalue,
495 int * searchborders,
496 uint8_t * key,
497 int keylen,
498 PTW_attackstate * state,
499 uint8_t sum,
500 int * strongbytes,
501 int * bf,
502 int validchars[][n])
503 {
504 int i;
505 uint8_t tmp;
506
507 if (!opt.is_quiet && keybyte < 4)
508 show_wep_stats(keylen - 1, 0, keytable, searchborders, depth, tried);
509 if (keybyte > 0)
510 {
511 if (!validchars[keybyte - 1][key[keybyte - 1]])
512 {
513 return 0;
514 }
515 }
516 if (keybyte == keylen)
517 {
518 return correct(state, key, keylen);
519 }
520 else if (bf[keybyte] == 1)
521 {
522 for (i = 0; i < n; i++)
523 {
524 key[keybyte] = i;
525 if (doRound(sortedtable,
526 keybyte + 1,
527 fixat,
528 fixvalue,
529 searchborders,
530 key,
531 keylen,
532 state,
533 sum + i % n,
534 strongbytes,
535 bf,
536 validchars))
537 {
538 return 1;
539 }
540 }
541 return 0;
542 }
543 else if (keybyte == fixat)
544 {
545 key[keybyte] = fixvalue - sum;
546 return doRound(sortedtable,
547 keybyte + 1,
548 fixat,
549 fixvalue,
550 searchborders,
551 key,
552 keylen,
553 state,
554 fixvalue,
555 strongbytes,
556 bf,
557 validchars);
558 }
559 else if (strongbytes[keybyte] == 1)
560 {
561 // printf("assuming byte %d to be strong\n", keybyte);
562 tmp = 3 + keybyte;
563 for (i = keybyte - 1; i >= 1; i--)
564 {
565 tmp += 3 + key[i] + i;
566 key[keybyte] = n - tmp;
567 if (doRound(sortedtable,
568 keybyte + 1,
569 fixat,
570 fixvalue,
571 searchborders,
572 key,
573 keylen,
574 state,
575 (n - tmp + sum) % n,
576 strongbytes,
577 bf,
578 validchars)
579 == 1)
580 {
581 printf("hit with strongbyte for keybyte %d\n", keybyte);
582 return 1;
583 }
584 }
585 return 0;
586 }
587 else
588 {
589 for (i = 0; i < searchborders[keybyte]; i++)
590 {
591 key[keybyte] = sortedtable[keybyte][i].b - sum;
592 if (!opt.is_quiet)
593 {
594 depth[keybyte] = i;
595 keytable[keybyte][i].b = key[keybyte];
596 }
597 if (doRound(sortedtable,
598 keybyte + 1,
599 fixat,
600 fixvalue,
601 searchborders,
602 key,
603 keylen,
604 state,
605 sortedtable[keybyte][i].b,
606 strongbytes,
607 bf,
608 validchars))
609 {
610 return 1;
611 }
612 }
613 return 0;
614 }
615 }
616
617 /*
618 * Do the actual computation of the key
619 */
doComputation(PTW_attackstate * state,uint8_t * key,int keylen,PTW_tableentry table[][n],sorthelper * sh2,int * strongbytes,int keylimit,int * bf,int validchars[][n])620 static int doComputation(PTW_attackstate * state,
621 uint8_t * key,
622 int keylen,
623 PTW_tableentry table[][n],
624 sorthelper * sh2,
625 int * strongbytes,
626 int keylimit,
627 int * bf,
628 int validchars[][n])
629 {
630 int i, j;
631 int choices[KEYHSBYTES];
632 int prod;
633 int fixat;
634 int fixvalue;
635
636 if (!opt.is_quiet)
637 memcpy(keytable, table, sizeof(PTW_tableentry) * n * keylen);
638
639 for (i = 0; i < keylen; i++)
640 {
641 if (strongbytes[i] == 1)
642 {
643 choices[i] = i;
644 }
645 else
646 {
647 choices[i] = 1;
648 }
649 }
650 i = 0;
651 prod = 0;
652 fixat = -1;
653 fixvalue = 0;
654 max_tries = keylimit;
655
656 while (prod < keylimit)
657 {
658 if (doRound(table,
659 0,
660 fixat,
661 fixvalue,
662 choices,
663 key,
664 keylen,
665 state,
666 0,
667 strongbytes,
668 bf,
669 validchars)
670 == 1)
671 {
672 // printf("hit with %d choices\n", prod);
673 if (!opt.is_quiet)
674 show_wep_stats(keylen - 1, 1, keytable, choices, depth, tried);
675 return 1;
676 }
677 while ((i < keylen * (n - 1)) && ((strongbytes[sh2[i].keybyte] == 1)
678 || (bf[sh2[i].keybyte] == 1)))
679 {
680 i++;
681 }
682 if (i >= (keylen * (n - 1)))
683 {
684 break;
685 }
686 choices[sh2[i].keybyte]++;
687 fixat = sh2[i].keybyte;
688 // printf("choices[%d] is now %d\n", sh2[i].keybyte,
689 // choices[sh2[i].keybyte]);
690 fixvalue = sh2[i].value;
691 prod = 1;
692 for (j = 0; j < keylen; j++)
693 {
694 prod *= choices[j];
695 if (bf[j] == 1)
696 {
697 prod *= n;
698 }
699 }
700
701 /*
702 do {
703 i++;
704 } while (strongbytes[sh2[i].keybyte] == 1);
705 */
706 i++;
707
708 if (!opt.is_quiet)
709 show_wep_stats(keylen - 1, 0, keytable, choices, depth, tried);
710 }
711 if (!opt.is_quiet)
712 show_wep_stats(keylen - 1, 1, keytable, choices, depth, tried);
713 return 0;
714 }
715
716 /*
717 * Guess which key bytes could be strong and start actual computation of the key
718 */
PTW_computeKey(PTW_attackstate * state,uint8_t * keybuf,int keylen,int testlimit,int * bf,int validchars[][n],int attacks)719 int PTW_computeKey(PTW_attackstate * state,
720 uint8_t * keybuf,
721 int keylen,
722 int testlimit,
723 int * bf,
724 int validchars[][n],
725 int attacks)
726 {
727 int strongbytes[KEYHSBYTES];
728 double normal[KEYHSBYTES];
729 double ausreisser[KEYHSBYTES];
730 doublesorthelper helper[KEYHSBYTES];
731 int simple, onestrong, twostrong;
732 int i, j;
733 #ifdef USE_AMD64_RC4_OPTIMIZED
734 /*
735 * The 64-bit SSE2-optimized rc4test() requires this buffer to be
736 * aligned at 3 bytes.
737 */
738 uint8_t fullkeybuf_unaligned[PTW_KSBYTES + 13] __attribute__((aligned(16)));
739 uint8_t * fullkeybuf = &fullkeybuf_unaligned[13];
740 #else
741 uint8_t fullkeybuf[PTW_KSBYTES];
742 #endif
743 uint8_t guessbuf[PTW_KSBYTES];
744 sorthelper(*sh)[n - 1];
745 PTW_tableentry(*table)[n] = alloca(sizeof(PTW_tableentry) * n * keylen);
746
747 #ifdef USE_AMD64_RC4_OPTIMIZED
748 /*
749 * sse2-optimized rc4test() function for amd64 only works
750 * for keylen == 5 or keylen == 13
751 */
752 if (keylen == 5 || keylen == 13)
753 state->rc4test = rc4test_amd64_sse2;
754 else
755 #endif
756 state->rc4test = rc4test;
757
758 tried = 0;
759 sh = NULL;
760
761 if (table == NULL)
762 {
763 printf("could not allocate memory\n");
764 exit(-1);
765 }
766
767 if (!(attacks & NO_KLEIN))
768 {
769 // Try the original klein attack first
770 for (i = 0; i < keylen; i++)
771 {
772 memset(&table[i][0], 0, sizeof(PTW_tableentry) * n);
773 for (j = 0; j < n; j++)
774 {
775 table[i][j].b = j;
776 }
777 for (j = 0; j < state->packets_collected; j++)
778 {
779 // fullkeybuf[0] = state->allsessions[j].iv[0];
780 memcpy(
781 fullkeybuf, state->allsessions[j].iv, 3 * sizeof(uint8_t));
782 guesskeybytes(i + 3,
783 fullkeybuf,
784 state->allsessions[j].keystream,
785 guessbuf,
786 1);
787 table[i][guessbuf[0]].votes += state->allsessions[j].weight;
788 }
789 qsort(&table[i][0], n, sizeof(PTW_tableentry), &compare);
790 j = 0;
791 while (!validchars[i][table[i][j].b])
792 {
793 j++;
794 }
795 // printf("guessing i = %d, b = %d\n", i, table[0][0].b);
796 fullkeybuf[i + 3] = table[i][j].b;
797 }
798 if (correct(state, &fullkeybuf[3], keylen))
799 {
800 memcpy(keybuf, &fullkeybuf[3], keylen * sizeof(uint8_t));
801 // printf("hit without correction\n");
802 return 1;
803 }
804 }
805
806 if (!(attacks & NO_PTW))
807 {
808 memcpy(table, state->table, sizeof(PTW_tableentry) * n * keylen);
809
810 onestrong = (testlimit / 10) * 2;
811 twostrong = (testlimit / 10) * 1;
812 simple = testlimit - onestrong - twostrong;
813
814 // now, sort the table
815 for (i = 0; i < keylen; i++)
816 {
817 qsort(&table[i][0], n, sizeof(PTW_tableentry), &compare);
818 strongbytes[i] = 0;
819 }
820
821 sh = alloca(sizeof(sorthelper) * (n - 1) * keylen);
822 if (sh == NULL)
823 {
824 printf("could not allocate memory\n");
825 exit(-1);
826 }
827
828 for (i = 0; i < keylen; i++)
829 {
830 for (j = 1; j < n; j++)
831 {
832 sh[i][j - 1].distance = table[i][0].votes - table[i][j].votes;
833 sh[i][j - 1].value = table[i][j].b;
834 sh[i][j - 1].keybyte = i;
835 }
836 }
837 qsort(sh, (n - 1) * keylen, sizeof(sorthelper), &comparesorthelper);
838
839 if (doComputation(state,
840 keybuf,
841 keylen,
842 table,
843 (sorthelper *) sh,
844 strongbytes,
845 simple,
846 bf,
847 validchars))
848 {
849 return 1;
850 }
851
852 // Now one strong byte
853 getdrv(state->table, keylen, normal, ausreisser);
854 for (i = 0; i < keylen - 1; i++)
855 {
856 helper[i].keybyte = i + 1;
857 helper[i].difference = normal[i + 1] - ausreisser[i + 1];
858 }
859 qsort(helper,
860 keylen - 1,
861 sizeof(doublesorthelper),
862 &comparedoublesorthelper);
863 // do not use bf-bytes as strongbytes
864 i = 0;
865 while (bf[helper[i].keybyte] == 1)
866 {
867 i++;
868 }
869 strongbytes[helper[i].keybyte] = 1;
870 if (doComputation(state,
871 keybuf,
872 keylen,
873 table,
874 (sorthelper *) sh,
875 strongbytes,
876 onestrong,
877 bf,
878 validchars))
879 {
880 return 1;
881 }
882
883 // two strong bytes
884 i++;
885 while (bf[helper[i].keybyte] == 1)
886 {
887 i++;
888 }
889 strongbytes[helper[i].keybyte] = 1;
890 if (doComputation(state,
891 keybuf,
892 keylen,
893 table,
894 (sorthelper *) sh,
895 strongbytes,
896 twostrong,
897 bf,
898 validchars))
899 {
900 return 1;
901 }
902 }
903 return 0;
904 }
905
906 /*
907 * Add a new session to the attack
908 * state - state of attack
909 * iv - IV used in the session
910 * keystream - recovered keystream from the session
911 */
PTW_addsession(PTW_attackstate * state,uint8_t * iv,uint8_t * keystream,int * weight,int total)912 int PTW_addsession(PTW_attackstate * state,
913 uint8_t * iv,
914 uint8_t * keystream,
915 int * weight,
916 int total)
917 {
918 int i, j;
919 int il;
920 int ir;
921 uint8_t buf[PTW_KEYHSBYTES];
922
923 i = (iv[0] << 16) | (iv[1] << 8) | (iv[2]);
924 il = i / 8;
925 ir = 1 << (i % 8);
926 if ((state->seen_iv[il] & ir) == 0)
927 {
928 state->seen_iv[il] |= ir;
929 for (j = 0; j < total; j++)
930 {
931 state->packets_collected++;
932 guesskeybytes(
933 IVBYTES, iv, &keystream[KSBYTES * j], buf, PTW_KEYHSBYTES);
934 for (i = 0; i < KEYHSBYTES; i++)
935 {
936 state->table[i][buf[i]].votes += weight[j];
937 }
938 if (state->allsessions_size < state->packets_collected)
939 {
940 state->allsessions_size = state->allsessions_size << 1;
941 state->allsessions
942 = realloc(state->allsessions,
943 state->allsessions_size * sizeof(PTW_session));
944 if (state->allsessions == NULL)
945 {
946 printf("could not allocate memory\n");
947 exit(-1);
948 }
949 }
950 memcpy(state->allsessions[state->packets_collected - 1].iv,
951 iv,
952 IVBYTES);
953 memcpy(state->allsessions[state->packets_collected - 1].keystream,
954 &keystream[KSBYTES * j],
955 KSBYTES);
956 state->allsessions[state->packets_collected - 1].weight = weight[j];
957 }
958 if ((state->sessions_collected < CONTROLSESSIONS))
959 {
960 memcpy(state->sessions[state->sessions_collected].iv, iv, IVBYTES);
961 memcpy(state->sessions[state->sessions_collected].keystream,
962 keystream,
963 KSBYTES);
964 state->sessions_collected++;
965 }
966
967 return 1;
968 }
969 else
970 {
971 return 0;
972 }
973 }
974
975 /*
976 * Allocate a new attackstate
977 */
PTW_newattackstate()978 PTW_attackstate * PTW_newattackstate()
979 {
980 int i, k;
981 PTW_attackstate * state = NULL;
982 state = malloc(sizeof(PTW_attackstate));
983 if (state == NULL)
984 {
985 return NULL;
986 }
987 memset(state, 0, sizeof(PTW_attackstate));
988 for (i = 0; i < PTW_KEYHSBYTES; i++)
989 {
990 for (k = 0; k < n; k++)
991 {
992 state->table[i][k].b = k;
993 }
994 }
995 state->allsessions = malloc(4096 * sizeof(PTW_session));
996 state->allsessions_size = 4096;
997 if (state->allsessions == NULL)
998 {
999 printf("could not allocate memory\n");
1000 exit(-1);
1001 }
1002
1003 return state;
1004 }
1005
1006 /*
1007 * Free an allocated attackstate
1008 */
PTW_freeattackstate(PTW_attackstate * state)1009 void PTW_freeattackstate(PTW_attackstate * state)
1010 {
1011 free(state->allsessions);
1012 free(state);
1013 return;
1014 }
1015