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 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 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 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 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 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 485 void PTW_freeattackstate(PTW_attackstate * state) { 486 free(state); 487 return; 488 } 489