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