tools/tools/net80211/wesside/wesside/aircrack-ptw-lib.c

   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$
  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