1168502Ssam/*- 2168538Ssam * Copyright (c) 2007, Erik Tews, Andrei Pychkine and Ralf-Philipp Weinmann 3168538Ssam * <aircrack-ptw@cdc.informatik.tu-darmstadt.de> 4168502Ssam * All rights reserved. 5168502Ssam * 6168502Ssam * Redistribution and use in source and binary forms, with or without 7168502Ssam * modification, are permitted provided that the following conditions 8168502Ssam * are met: 9168502Ssam * 1. Redistributions of source code must retain the above copyright 10168502Ssam * notice, this list of conditions and the following disclaimer. 11168502Ssam * 2. Redistributions in binary form must reproduce the above copyright 12168502Ssam * notice, this list of conditions and the following disclaimer in the 13168502Ssam * documentation and/or other materials provided with the distribution. 14168502Ssam * 15168502Ssam * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 16168502Ssam * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 17168502Ssam * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 18168502Ssam * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 19168502Ssam * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 20168502Ssam * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 21168502Ssam * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 22168502Ssam * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 23168502Ssam * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 24168502Ssam * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 25168502Ssam * SUCH DAMAGE. 26168502Ssam * 27168502Ssam * $FreeBSD$ 28168502Ssam */ 29168502Ssam#include <string.h> 30168502Ssam#include <stdio.h> 31168502Ssam#include <stdlib.h> 32168502Ssam#include "aircrack-ptw-lib.h" 33168502Ssam 34168502Ssam 35168502Ssam#define n PTW_n 36168502Ssam#define CONTROLSESSIONS PTW_CONTROLSESSIONS 37168502Ssam#define KEYHSBYTES PTW_KEYHSBYTES 38168502Ssam#define KSBYTES PTW_KSBYTES 39168502Ssam#define IVBYTES PTW_IVBYTES 40168502Ssam#define TESTBYTES 6 41168502Ssam 42168502Ssam 43168502Ssam// Internal state of rc4 44168502Ssamtypedef struct { 45168502Ssam uint8_t i; 46168502Ssam uint8_t j; 47168502Ssam uint8_t s[n]; 48168502Ssam} rc4state; 49168502Ssam 50168502Ssam 51168502Ssam// Helper structures for sorting 52168502Ssamtypedef struct { 53168502Ssam int keybyte; 54168502Ssam uint8_t value; 55168502Ssam int distance; 56168502Ssam} sorthelper; 57168502Ssam 58168502Ssamtypedef struct { 59168502Ssam int keybyte; 60168502Ssam double difference; 61168502Ssam} doublesorthelper; 62168502Ssam 63168502Ssam// The rc4 initial state, the idendity permutation 64168502Ssamstatic const uint8_t rc4initial[] = 65168502Ssam{0,1,2,3,4,5,6,7,8,9,10, 66168502Ssam11,12,13,14,15,16,17,18,19,20, 67168502Ssam21,22,23,24,25,26,27,28,29,30, 68168502Ssam31,32,33,34,35,36,37,38,39,40, 69168502Ssam41,42,43,44,45,46,47,48,49,50, 70168502Ssam51,52,53,54,55,56,57,58,59,60, 71168502Ssam61,62,63,64,65,66,67,68,69,70, 72168502Ssam71,72,73,74,75,76,77,78,79,80, 73168502Ssam81,82,83,84,85,86,87,88,89,90, 74168502Ssam91,92,93,94,95,96,97,98,99,100, 75168502Ssam101,102,103,104,105,106,107,108,109,110, 76168502Ssam111,112,113,114,115,116,117,118,119,120, 77168502Ssam121,122,123,124,125,126,127,128,129,130, 78168502Ssam131,132,133,134,135,136,137,138,139,140, 79168502Ssam141,142,143,144,145,146,147,148,149,150, 80168502Ssam151,152,153,154,155,156,157,158,159,160, 81168502Ssam161,162,163,164,165,166,167,168,169,170, 82168502Ssam171,172,173,174,175,176,177,178,179,180, 83168502Ssam181,182,183,184,185,186,187,188,189,190, 84168502Ssam191,192,193,194,195,196,197,198,199,200, 85168502Ssam201,202,203,204,205,206,207,208,209,210, 86168502Ssam211,212,213,214,215,216,217,218,219,220, 87168502Ssam221,222,223,224,225,226,227,228,229,230, 88168502Ssam231,232,233,234,235,236,237,238,239,240, 89168502Ssam241,242,243,244,245,246,247,248,249,250, 90168502Ssam251,252,253,254,255}; 91168502Ssam 92168502Ssam 93168502Ssam// Values for p_correct_i 94168502Ssamstatic const double eval[] = { 95168502Ssam0.00534392069257663, 96168502Ssam0.00531787585068872, 97168502Ssam0.00531345769225911, 98168502Ssam0.00528812219217898, 99168502Ssam0.00525997750378221, 100168502Ssam0.00522647312237696, 101168502Ssam0.00519132541143668, 102168502Ssam0.0051477139367225, 103168502Ssam0.00510438884847959, 104168502Ssam0.00505484662057323, 105168502Ssam0.00500502783556246, 106168502Ssam0.00495094196451801, 107168502Ssam0.0048983441590402}; 108168502Ssam 109168502Ssam// For sorting 110168502Ssamstatic int compare(const void * ina, const void * inb) { 111168502Ssam PTW_tableentry * a = (PTW_tableentry * )ina; 112168502Ssam PTW_tableentry * b = (PTW_tableentry * )inb; 113168502Ssam if (a->votes > b->votes) { 114168502Ssam return -1; 115168502Ssam } else if (a->votes == b->votes) { 116168502Ssam return 0; 117168502Ssam } else { 118168502Ssam return 1; 119168502Ssam } 120168502Ssam} 121168502Ssam 122168502Ssam// For sorting 123168502Ssamstatic int comparedoublesorthelper(const void * ina, const void * inb) { 124168502Ssam doublesorthelper * a = (doublesorthelper * )ina; 125168502Ssam doublesorthelper * b = (doublesorthelper * )inb; 126168502Ssam if (a->difference > b->difference) { 127168502Ssam return 1; 128168502Ssam } else if (a->difference == b->difference) { 129168502Ssam return 0; 130168502Ssam } else { 131168502Ssam return -1; 132168502Ssam } 133168502Ssam} 134168502Ssam 135168502Ssam 136168502Ssam// RC4 key setup 137168502Ssamstatic void rc4init ( uint8_t * key, int keylen, rc4state * state) { 138168502Ssam int i; 139168502Ssam int j; 140168502Ssam uint8_t tmp; 141168502Ssam memcpy(state->s, &rc4initial, n); 142168502Ssam j = 0; 143168502Ssam for (i = 0; i < n; i++) { 144168502Ssam j = (j + state->s[i] + key[i % keylen]) % n; 145168502Ssam tmp = state->s[i]; 146168502Ssam state->s[i] = state->s[j]; 147168502Ssam state->s[j] = tmp; 148168502Ssam } 149168502Ssam state->i = 0; 150168502Ssam state->j = 0; 151168502Ssam} 152168502Ssam 153168502Ssam// RC4 key stream generation 154168502Ssamstatic uint8_t rc4update(rc4state * state) { 155168502Ssam uint8_t tmp; 156168502Ssam uint8_t k; 157168502Ssam state->i++; 158168502Ssam state->j += state->s[state->i]; 159168502Ssam tmp = state->s[state->i]; 160168502Ssam state->s[state->i] = state->s[state->j]; 161168502Ssam state->s[state->j] = tmp; 162168502Ssam k = state->s[state->i] + state->s[state->j]; 163168502Ssam 164168502Ssam return state->s[k]; 165168502Ssam} 166168502Ssam 167168502Ssam// For sorting 168168502Ssamstatic int comparesorthelper(const void * ina, const void * inb) { 169168502Ssam sorthelper * a = (sorthelper * ) ina; 170168502Ssam sorthelper * b = (sorthelper * ) inb; 171168502Ssam if (a->distance > b->distance) { 172168502Ssam return 1; 173168502Ssam } else if (a->distance == b->distance) { 174168502Ssam return 0; 175168502Ssam } else { 176168502Ssam return -1; 177168502Ssam } 178168502Ssam} 179168502Ssam 180168502Ssam/* 181168502Ssam * Guess the values for sigma_i 182168502Ssam * iv - IV which was used for this packet 183168502Ssam * keystream - keystream recovered 184168502Ssam * result - buffer for the values of sigma_i 185168502Ssam * kb - how many keybytes should be guessed 186168502Ssam */ 187168502Ssamstatic void guesskeybytes(uint8_t * iv, uint8_t * keystream, uint8_t * result, int kb) { 188168502Ssam uint8_t state[n]; 189168502Ssam uint8_t j = 0; 190168502Ssam uint8_t tmp; 191168502Ssam int i; 192168502Ssam int jj = IVBYTES; 193168502Ssam uint8_t ii; 194168502Ssam uint8_t s = 0; 195168502Ssam memcpy(state, rc4initial, n); 196168502Ssam for (i = 0; i < IVBYTES; i++) { 197168502Ssam j += state[i] + iv[i]; 198168502Ssam tmp = state[i]; 199168502Ssam state[i] = state[j]; 200168502Ssam state[j] = tmp; 201168502Ssam } 202168502Ssam for (i = 0; i < kb; i++) { 203168502Ssam tmp = jj - keystream[jj-1]; 204168502Ssam ii = 0; 205168502Ssam while(tmp != state[ii]) { 206168502Ssam ii++; 207168502Ssam } 208168502Ssam s += state[jj]; 209168502Ssam ii -= (j+s); 210168502Ssam result[i] = ii; 211168502Ssam jj++; 212168502Ssam } 213168502Ssam return; 214168502Ssam} 215168502Ssam 216168502Ssam/* 217168502Ssam * Is a guessed key correct? 218168502Ssam */ 219168502Ssamstatic int correct(PTW_attackstate * state, uint8_t * key, int keylen) { 220168502Ssam int i; 221168502Ssam int j; 222168502Ssam uint8_t keybuf[PTW_KSBYTES]; 223168502Ssam rc4state rc4state; 224168502Ssam 225168502Ssam for (i = 0; i < state->sessions_collected; i++) { 226168502Ssam memcpy(&keybuf[IVBYTES], key, keylen); 227168502Ssam memcpy(keybuf, state->sessions[i].iv, IVBYTES); 228168502Ssam rc4init(keybuf, keylen+IVBYTES, &rc4state); 229168502Ssam for (j = 0; j < TESTBYTES; j++) { 230168502Ssam if ((rc4update(&rc4state) ^ state->sessions[i].keystream[j]) != 0) { 231168502Ssam return 0; 232168502Ssam } 233168502Ssam } 234168502Ssam } 235168502Ssam return 1; 236168502Ssam} 237168502Ssam 238168502Ssam/* 239168502Ssam * Calculate the squaresum of the errors for both distributions 240168502Ssam */ 241168502Ssamstatic void getdrv(PTW_tableentry orgtable[][n], int keylen, double * normal, double * ausreiser) { 242168502Ssam int i,j; 243168502Ssam int numvotes = 0; 244168502Ssam double e; 245168502Ssam double e2; 246168502Ssam double emax; 247168502Ssam double help = 0.0; 248168502Ssam double maxhelp = 0; 249168502Ssam double maxi = 0; 250168502Ssam for (i = 0; i < n; i++) { 251168502Ssam numvotes += orgtable[0][i].votes; 252168502Ssam } 253168502Ssam e = numvotes/n; 254168502Ssam for (i = 0; i < keylen; i++) { 255168502Ssam emax = eval[i] * numvotes; 256168502Ssam e2 = ((1.0 - eval[i])/255.0) * numvotes; 257168502Ssam normal[i] = 0; 258168502Ssam ausreiser[i] = 0; 259168502Ssam maxhelp = 0; 260168502Ssam maxi = 0; 261168502Ssam for (j = 0; j < n; j++) { 262168502Ssam if (orgtable[i][j].votes > maxhelp) { 263168502Ssam maxhelp = orgtable[i][j].votes; 264168502Ssam maxi = j; 265168502Ssam } 266168502Ssam } 267168502Ssam for (j = 0; j < n; j++) { 268168502Ssam if (j == maxi) { 269168502Ssam help = (1.0-orgtable[i][j].votes/emax); 270168502Ssam } else { 271168502Ssam help = (1.0-orgtable[i][j].votes/e2); 272168502Ssam } 273168502Ssam help = help*help; 274168502Ssam ausreiser[i] += help; 275168502Ssam help = (1.0-orgtable[i][j].votes/e); 276168502Ssam help = help*help; 277168502Ssam normal[i] += help; 278168502Ssam } 279168502Ssam } 280168502Ssam} 281168502Ssam 282168502Ssam/* 283168502Ssam * Guess a single keybyte 284168502Ssam */ 285168502Ssamstatic 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) { 286168502Ssam int i; 287168502Ssam uint8_t tmp; 288168502Ssam if (keybyte == keylen) { 289168502Ssam return correct(state, key, keylen); 290168502Ssam } else if (strongbytes[keybyte] == 1) { 291168502Ssam // printf("assuming byte %d to be strong\n", keybyte); 292168502Ssam tmp = 3 + keybyte; 293168502Ssam for (i = keybyte-1; i >= 1; i--) { 294168502Ssam tmp += 3 + key[i] + i; 295168502Ssam key[keybyte] = 256-tmp; 296168502Ssam if(doRound(sortedtable, keybyte+1, fixat, fixvalue, searchborders, key, keylen, state, (256-tmp+sum)%256, strongbytes) == 1) { 297168502Ssam printf("hit with strongbyte for keybyte %d\n", keybyte); 298168502Ssam return 1; 299168502Ssam } 300168502Ssam } 301168502Ssam return 0; 302168502Ssam } else if (keybyte == fixat) { 303168502Ssam key[keybyte] = fixvalue-sum; 304168502Ssam return doRound(sortedtable, keybyte+1, fixat, fixvalue, searchborders, key, keylen, state, fixvalue, strongbytes); 305168502Ssam } else { 306168502Ssam for (i = 0; i < searchborders[keybyte]; i++) { 307168502Ssam key[keybyte] = sortedtable[keybyte][i].b - sum; 308168502Ssam if (doRound(sortedtable, keybyte+1, fixat, fixvalue, searchborders, key, keylen, state, sortedtable[keybyte][i].b, strongbytes) == 1) { 309168502Ssam return 1; 310168502Ssam } 311168502Ssam } 312168502Ssam return 0; 313168502Ssam } 314168502Ssam} 315168502Ssam 316168502Ssam/* 317168502Ssam * Do the actual computation of the key 318168502Ssam */ 319168502Ssamstatic int doComputation(PTW_attackstate * state, uint8_t * key, int keylen, PTW_tableentry table[][n], sorthelper * sh2, int * strongbytes, int keylimit) { 320168502Ssam int i,j; 321168502Ssam int choices[KEYHSBYTES]; 322168502Ssam int prod; 323168502Ssam int fixat; 324168502Ssam int fixvalue; 325168502Ssam 326168502Ssam for (i = 0; i < keylen; i++) { 327168502Ssam if (strongbytes[i] == 1) { 328168502Ssam choices[i] = i; 329168502Ssam } else { 330168502Ssam choices[i] = 1; 331168502Ssam } 332168502Ssam } 333168502Ssam i = 0; 334168502Ssam prod = 0; 335168502Ssam fixat = -1; 336168502Ssam fixvalue = 0; 337168502Ssam 338168502Ssam while(prod < keylimit) { 339168502Ssam if (doRound(table, 0, fixat, fixvalue, choices, key, keylen, state, 0, strongbytes) == 1) { 340168502Ssam // printf("hit with %d choices\n", prod); 341168502Ssam return 1; 342168502Ssam } 343168502Ssam choices[sh2[i].keybyte]++; 344168502Ssam fixat = sh2[i].keybyte; 345168502Ssam // printf("choices[%d] is now %d\n", sh2[i].keybyte, choices[sh2[i].keybyte]); 346168502Ssam fixvalue = sh2[i].value; 347168502Ssam prod = 1; 348168502Ssam for (j = 0; j < keylen; j++) { 349168502Ssam prod *= choices[j]; 350168502Ssam } 351168502Ssam do { 352168502Ssam i++; 353168502Ssam } while (strongbytes[sh2[i].keybyte] == 1); 354168502Ssam 355168502Ssam } 356168502Ssam return 0; 357168502Ssam} 358168502Ssam 359168502Ssam 360168502Ssam/* 361168502Ssam * Guess which key bytes could be strong and start actual computation of the key 362168502Ssam */ 363168502Ssamint PTW_computeKey(PTW_attackstate * state, uint8_t * keybuf, int keylen, int testlimit) { 364168502Ssam int strongbytes[KEYHSBYTES]; 365168502Ssam double normal[KEYHSBYTES]; 366168502Ssam double ausreisser[KEYHSBYTES]; 367168502Ssam doublesorthelper helper[KEYHSBYTES]; 368168502Ssam int simple, onestrong, twostrong; 369168502Ssam int i,j; 370168502Ssam 371168502Ssam onestrong = (testlimit/10)*2; 372168502Ssam twostrong = (testlimit/10)*1; 373168502Ssam simple = testlimit - onestrong - twostrong; 374168502Ssam 375168502Ssam PTW_tableentry (*table)[n] = alloca(sizeof(PTW_tableentry) * n * keylen); 376168502Ssam if (table == NULL) { 377168502Ssam printf("could not allocate memory\n"); 378168502Ssam exit(-1); 379168502Ssam } 380168502Ssam memcpy(table, state->table, sizeof(PTW_tableentry) * n * keylen); 381168502Ssam 382168502Ssam // now, sort the table 383168502Ssam for (i = 0; i < keylen; i++) { 384168502Ssam qsort(&table[i][0], n, sizeof(PTW_tableentry), &compare); 385168502Ssam strongbytes[i] = 0; 386168502Ssam } 387168502Ssam 388168502Ssam sorthelper (* sh)[n-1] = alloca(sizeof(sorthelper) * (n-1) * keylen); 389168502Ssam if (sh == NULL) { 390168502Ssam printf("could not allocate memory\n"); 391168502Ssam exit(-1); 392168502Ssam } 393168502Ssam 394168502Ssam 395168502Ssam for (i = 0; i < keylen; i++) { 396168502Ssam for (j = 1; j < n; j++) { 397168502Ssam sh[i][j-1].distance = table[i][0].votes - table[i][j].votes; 398168502Ssam sh[i][j-1].value = table[i][j].b; 399168502Ssam sh[i][j-1].keybyte = i; 400168502Ssam } 401168502Ssam } 402168502Ssam qsort(sh, (n-1)*keylen, sizeof(sorthelper), &comparesorthelper); 403168502Ssam 404168502Ssam 405168502Ssam if (doComputation(state, keybuf, keylen, table, (sorthelper *) sh, strongbytes, simple)) { 406168502Ssam return 1; 407168502Ssam } 408168502Ssam 409168502Ssam // Now one strong byte 410168502Ssam getdrv(state->table, keylen, normal, ausreisser); 411168502Ssam for (i = 0; i < keylen-1; i++) { 412168502Ssam helper[i].keybyte = i+1; 413168502Ssam helper[i].difference = normal[i+1] - ausreisser[i+1]; 414168502Ssam } 415168502Ssam qsort(helper, keylen-1, sizeof(doublesorthelper), &comparedoublesorthelper); 416168502Ssam strongbytes[helper[0].keybyte] = 1; 417168502Ssam if (doComputation(state, keybuf, keylen, table, (sorthelper *) sh, strongbytes, onestrong)) { 418168502Ssam return 1; 419168502Ssam } 420168502Ssam 421168502Ssam // two strong bytes 422168502Ssam strongbytes[helper[1].keybyte] = 1; 423168502Ssam if (doComputation(state, keybuf, keylen, table, (sorthelper *) sh, strongbytes, twostrong)) { 424168502Ssam return 1; 425168502Ssam } 426168502Ssam 427168502Ssam return 0; 428168502Ssam} 429168502Ssam 430168502Ssam/* 431168502Ssam * Add a new session to the attack 432168502Ssam * state - state of attack 433168502Ssam * iv - IV used in the session 434168502Ssam * keystream - recovered keystream from the session 435168502Ssam */ 436168502Ssamint PTW_addsession(PTW_attackstate * state, uint8_t * iv, uint8_t * keystream) { 437168502Ssam int i; 438168502Ssam int il; 439168502Ssam int ir; 440168502Ssam uint8_t buf[PTW_KEYHSBYTES]; 441168502Ssam 442168502Ssam i = (iv[0] << 16) | (iv[1] << 8) | (iv[2]); 443168502Ssam il = i/8; 444168502Ssam ir = 1 << (i%8); 445168502Ssam if ((state->seen_iv[il] & ir) == 0) { 446168502Ssam state->packets_collected++; 447168502Ssam state->seen_iv[il] |= ir; 448168502Ssam guesskeybytes(iv, keystream, buf, PTW_KEYHSBYTES); 449168502Ssam for (i = 0; i < KEYHSBYTES; i++) { 450168502Ssam state->table[i][buf[i]].votes++; 451168502Ssam } 452168502Ssam if (state->sessions_collected < CONTROLSESSIONS) { 453168502Ssam memcpy(state->sessions[state->sessions_collected].iv, iv, IVBYTES); 454168502Ssam memcpy(state->sessions[state->sessions_collected].keystream, keystream, KSBYTES); 455168502Ssam state->sessions_collected++; 456168502Ssam } 457168502Ssam return 1; 458168502Ssam } else { 459168502Ssam return 0; 460168502Ssam } 461168502Ssam} 462168502Ssam 463168502Ssam/* 464168502Ssam * Allocate a new attackstate 465168502Ssam */ 466168502SsamPTW_attackstate * PTW_newattackstate() { 467168502Ssam int i,k; 468168502Ssam PTW_attackstate * state = NULL; 469168502Ssam state = malloc(sizeof(PTW_attackstate)); 470168502Ssam if (state == NULL) { 471168502Ssam return NULL; 472168502Ssam } 473168502Ssam bzero(state, sizeof(PTW_attackstate)); 474168502Ssam for (i = 0; i < PTW_KEYHSBYTES; i++) { 475168502Ssam for (k = 0; k < n; k++) { 476168502Ssam state->table[i][k].b = k; 477168502Ssam } 478168502Ssam } 479168502Ssam return state; 480168502Ssam} 481168502Ssam 482168502Ssam/* 483168502Ssam * Free an allocated attackstate 484168502Ssam */ 485168502Ssamvoid PTW_freeattackstate(PTW_attackstate * state) { 486168502Ssam free(state); 487168502Ssam return; 488168502Ssam} 489168502Ssam 490