git.zerfleddert.de Git - proxmark3-svn/blob - tools/nonce2key/crapto1.c

   1 /*  crapto1.c
   2
   3     This program is free software; you can redistribute it and/or
   4     modify it under the terms of the GNU General Public License
   5     as published by the Free Software Foundation; either version 2
   6     of the License, or (at your option) any later version.
   7
   8     This program is distributed in the hope that it will be useful,
   9     but WITHOUT ANY WARRANTY; without even the implied warranty of
  10     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11     GNU General Public License for more details.
  12
  13     You should have received a copy of the GNU General Public License
  14     along with this program; if not, write to the Free Software
  15     Foundation, Inc., 51 Franklin Street, Fifth Floor,
  16     Boston, MA  02110-1301, US$
  17
  18     Copyright (C) 2008-2008 bla <blapost@gmail.com>
  19 */
  20 #include "crapto1.h"
  21 #include <stdlib.h>
  22
  23 #if !defined LOWMEM && defined __GNUC__
  24 static uint8_t filterlut[1 << 20];
  25 static void __attribute__((constructor)) fill_lut()
  26 {
  27         uint32_t i;
  28         for(i = 0; i < 1 << 20; ++i)
  29                 filterlut[i] = filter(i);
  30 }
  31 #define filter(x) (filterlut[(x) & 0xfffff])
  32 #endif
  33
  34 static void quicksort(uint32_t* const start, uint32_t* const stop)
  35 {
  36         uint32_t *it = start + 1, *rit = stop;
  37
  38         if(it > rit)
  39                 return;
  40
  41         while(it < rit)
  42                 if(*it <= *start)
  43                         ++it;
  44                 else if(*rit > *start)
  45                         --rit;
  46                 else
  47                         *it ^= (*it ^= *rit, *rit ^= *it);
  48
  49         if(*rit >= *start)
  50                 --rit;
  51         if(rit != start)
  52                 *rit ^= (*rit ^= *start, *start ^= *rit);
  53
  54         quicksort(start, rit - 1);
  55         quicksort(rit + 1, stop);
  56 }
  57 /** binsearch
  58  * Binary search for the first occurence of *stop's MSB in sorted [start,stop]
  59  */
  60 static inline uint32_t*
  61 binsearch(uint32_t *start, uint32_t *stop)
  62 {
  63         uint32_t mid, val = *stop & 0xff000000;
  64         while(start != stop)
  65                 if(start[mid = (stop - start) >> 1] > val)
  66                         stop = &start[mid];
  67                 else
  68                         start += mid + 1;
  69
  70         return start;
  71 }
  72
  73 /** update_contribution
  74  * helper, calculates the partial linear feedback contributions and puts in MSB
  75  */
  76 static inline void
  77 update_contribution(uint32_t *item, const uint32_t mask1, const uint32_t mask2)
  78 {
  79         uint32_t p = *item >> 25;
  80
  81         p = p << 1 | parity(*item & mask1);
  82         p = p << 1 | parity(*item & mask2);
  83         *item = p << 24 | (*item & 0xffffff);
  84 }
  85
  86 /** extend_table
  87  * using a bit of the keystream extend the table of possible lfsr states
  88  */
  89 static inline void
  90 extend_table(uint32_t *tbl, uint32_t **end, int bit, int m1, int m2, uint32_t in)
  91 {
  92         in <<= 24;
  93         for(*tbl <<= 1; tbl <= *end; *++tbl <<= 1)
  94                 if(filter(*tbl) ^ filter(*tbl | 1)) {
  95                         *tbl |= filter(*tbl) ^ bit;
  96                         update_contribution(tbl, m1, m2);
  97                         *tbl ^= in;
  98                 } else if(filter(*tbl) == bit) {
  99                         *++*end = tbl[1];
 100                         tbl[1] = tbl[0] | 1;
 101                         update_contribution(tbl, m1, m2);
 102                         *tbl++ ^= in;
 103                         update_contribution(tbl, m1, m2);
 104                         *tbl ^= in;
 105                 } else
 106                         *tbl-- = *(*end)--;
 107 }
 108 /** extend_table_simple
 109  * using a bit of the keystream extend the table of possible lfsr states
 110  */
 111 static inline void
 112 extend_table_simple(uint32_t *tbl, uint32_t **end, int bit)
 113 {
 114         for(*tbl <<= 1; tbl <= *end; *++tbl <<= 1)
 115                 if(filter(*tbl) ^ filter(*tbl | 1)) {
 116                         *tbl |= filter(*tbl) ^ bit;
 117                 } else if(filter(*tbl) == bit) {
 118                         *++*end = *++tbl;
 119                         *tbl = tbl[-1] | 1;
 120                 } else
 121                         *tbl-- = *(*end)--;
 122 }
 123 /** recover
 124  * recursively narrow down the search space, 4 bits of keystream at a time
 125  */
 126 static struct Crypto1State*
 127 recover(uint32_t *o_head, uint32_t *o_tail, uint32_t oks,
 128         uint32_t *e_head, uint32_t *e_tail, uint32_t eks, int rem,
 129         struct Crypto1State *sl, uint32_t in)
 130 {
 131         uint32_t *o, *e, i;
 132
 133         if(rem == -1) {
 134                 for(e = e_head; e <= e_tail; ++e) {
 135                         *e = *e << 1 ^ parity(*e & LF_POLY_EVEN) ^ !!(in & 4);
 136                         for(o = o_head; o <= o_tail; ++o, ++sl) {
 137                                 sl->even = *o;
 138                                 sl->odd = *e ^ parity(*o & LF_POLY_ODD);
 139                                 sl[1].odd = sl[1].even = 0;
 140                         }
 141                 }
 142                 return sl;
 143         }
 144
 145         for(i = 0; i < 4 && rem--; i++) {
 146                 extend_table(o_head, &o_tail, (oks >>= 1) & 1,
 147                         LF_POLY_EVEN << 1 | 1, LF_POLY_ODD << 1, 0);
 148                 if(o_head > o_tail)
 149                         return sl;
 150
 151                 extend_table(e_head, &e_tail, (eks >>= 1) & 1,
 152                         LF_POLY_ODD, LF_POLY_EVEN << 1 | 1, (in >>= 2) & 3);
 153                 if(e_head > e_tail)
 154                         return sl;
 155         }
 156
 157         quicksort(o_head, o_tail);
 158         quicksort(e_head, e_tail);
 159
 160         while(o_tail >= o_head && e_tail >= e_head)
 161                 if(((*o_tail ^ *e_tail) >> 24) == 0) {
 162                         o_tail = binsearch(o_head, o = o_tail);
 163                         e_tail = binsearch(e_head, e = e_tail);
 164                         sl = recover(o_tail--, o, oks,
 165                                      e_tail--, e, eks, rem, sl, in);
 166                 }
 167                 else if(*o_tail > *e_tail)
 168                         o_tail = binsearch(o_head, o_tail) - 1;
 169                 else
 170                         e_tail = binsearch(e_head, e_tail) - 1;
 171
 172         return sl;
 173 }
 174 /** lfsr_recovery
 175  * recover the state of the lfsr given 32 bits of the keystream
 176  * additionally you can use the in parameter to specify the value
 177  * that was fed into the lfsr at the time the keystream was generated
 178  */
 179 struct Crypto1State* lfsr_recovery32(uint32_t ks2, uint32_t in)
 180 {
 181         struct Crypto1State *statelist;
 182         uint32_t *odd_head = 0, *odd_tail = 0, oks = 0;
 183         uint32_t *even_head = 0, *even_tail = 0, eks = 0;
 184         int i;
 185
 186         for(i = 31; i >= 0; i -= 2)
 187                 oks = oks << 1 | BEBIT(ks2, i);
 188         for(i = 30; i >= 0; i -= 2)
 189                 eks = eks << 1 | BEBIT(ks2, i);
 190
 191         odd_head = odd_tail = malloc(sizeof(uint32_t) << 21);
 192         even_head = even_tail = malloc(sizeof(uint32_t) << 21);
 193         statelist =  malloc(sizeof(struct Crypto1State) << 18);
 194         if(!odd_tail-- || !even_tail-- || !statelist)
 195                 goto out;
 196
 197         statelist->odd = statelist->even = 0;
 198
 199         for(i = 1 << 20; i >= 0; --i) {
 200                 if(filter(i) == (oks & 1))
 201                         *++odd_tail = i;
 202                 if(filter(i) == (eks & 1))
 203                         *++even_tail = i;
 204         }
 205
 206         for(i = 0; i < 4; i++) {
 207                 extend_table_simple(odd_head,  &odd_tail, (oks >>= 1) & 1);
 208                 extend_table_simple(even_head, &even_tail, (eks >>= 1) & 1);
 209         }
 210
 211         in = (in >> 16 & 0xff) | (in << 16) | (in & 0xff00);
 212         recover(odd_head, odd_tail, oks,
 213                 even_head, even_tail, eks, 11, statelist, in << 1);
 214
 215 out:
 216         free(odd_head);
 217         free(even_head);
 218         return statelist;
 219 }
 220
 221 static const uint32_t S1[] = {     0x62141, 0x310A0, 0x18850, 0x0C428, 0x06214,
 222         0x0310A, 0x85E30, 0xC69AD, 0x634D6, 0xB5CDE, 0xDE8DA, 0x6F46D, 0xB3C83,
 223         0x59E41, 0xA8995, 0xD027F, 0x6813F, 0x3409F, 0x9E6FA};
 224 static const uint32_t S2[] = {  0x3A557B00, 0x5D2ABD80, 0x2E955EC0, 0x174AAF60,
 225         0x0BA557B0, 0x05D2ABD8, 0x0449DE68, 0x048464B0, 0x42423258, 0x278192A8,
 226         0x156042D0, 0x0AB02168, 0x43F89B30, 0x61FC4D98, 0x765EAD48, 0x7D8FDD20,
 227         0x7EC7EE90, 0x7F63F748, 0x79117020};
 228 static const uint32_t T1[] = {
 229         0x4F37D, 0x279BE, 0x97A6A, 0x4BD35, 0x25E9A, 0x12F4D, 0x097A6, 0x80D66,
 230         0xC4006, 0x62003, 0xB56B4, 0x5AB5A, 0xA9318, 0xD0F39, 0x6879C, 0xB057B,
 231         0x582BD, 0x2C15E, 0x160AF, 0x8F6E2, 0xC3DC4, 0xE5857, 0x72C2B, 0x39615,
 232         0x98DBF, 0xC806A, 0xE0680, 0x70340, 0x381A0, 0x98665, 0x4C332, 0xA272C};
 233 static const uint32_t T2[] = {  0x3C88B810, 0x5E445C08, 0x2982A580, 0x14C152C0,
 234         0x4A60A960, 0x253054B0, 0x52982A58, 0x2FEC9EA8, 0x1156C4D0, 0x08AB6268,
 235         0x42F53AB0, 0x217A9D58, 0x161DC528, 0x0DAE6910, 0x46D73488, 0x25CB11C0,
 236         0x52E588E0, 0x6972C470, 0x34B96238, 0x5CFC3A98, 0x28DE96C8, 0x12CFC0E0,
 237         0x4967E070, 0x64B3F038, 0x74F97398, 0x7CDC3248, 0x38CE92A0, 0x1C674950,
 238         0x0E33A4A8, 0x01B959D0, 0x40DCACE8, 0x26CEDDF0};
 239 static const uint32_t C1[] = { 0x846B5, 0x4235A, 0x211AD};
 240 static const uint32_t C2[] = { 0x1A822E0, 0x21A822E0, 0x21A822E0};
 241 /** Reverse 64 bits of keystream into possible cipher states
 242  * Variation mentioned in the paper. Somewhat optimized version
 243  */
 244 struct Crypto1State* lfsr_recovery64(uint32_t ks2, uint32_t ks3)
 245 {
 246         struct Crypto1State *statelist, *sl;
 247         uint8_t oks[32], eks[32], hi[32];
 248         uint32_t low = 0,  win = 0;
 249         uint32_t *tail, table[1 << 16];
 250         int i, j;
 251
 252         sl = statelist = malloc(sizeof(struct Crypto1State) << 4);
 253         if(!sl)
 254                 return 0;
 255         sl->odd = sl->even = 0;
 256
 257         for(i = 30; i >= 0; i -= 2) {
 258                 oks[i >> 1] = BIT(ks2, i ^ 24);
 259                 oks[16 + (i >> 1)] = BIT(ks3, i ^ 24);
 260         }
 261         for(i = 31; i >= 0; i -= 2) {
 262                 eks[i >> 1] = BIT(ks2, i ^ 24);
 263                 eks[16 + (i >> 1)] = BIT(ks3, i ^ 24);
 264         }
 265
 266         for(i = 0xfffff; i >= 0; --i) {
 267                 if (filter(i) != oks[0])
 268                         continue;
 269
 270                 *(tail = table) = i;
 271                 for(j = 1; tail >= table && j < 29; ++j)
 272                         extend_table_simple(table, &tail, oks[j]);
 273
 274                 if(tail < table)
 275                         continue;
 276
 277                 for(j = 0; j < 19; ++j)
 278                         low = low << 1 | parity(i & S1[j]);
 279                 for(j = 0; j < 32; ++j)
 280                         hi[j] = parity(i & T1[j]);
 281
 282                 for(; tail >= table; --tail) {
 283                         for(j = 0; j < 3; ++j) {
 284                                 *tail = *tail << 1;
 285                                 *tail |= parity((i & C1[j]) ^ (*tail & C2[j]));
 286                                 if(filter(*tail) != oks[29 + j])
 287                                         goto continue2;
 288                         }
 289
 290                         for(j = 0; j < 19; ++j)
 291                                 win = win << 1 | parity(*tail & S2[j]);
 292
 293                         win ^= low;
 294                         for(j = 0; j < 32; ++j) {
 295                                 win = win << 1 ^ hi[j] ^ parity(*tail & T2[j]);
 296                                 if(filter(win) != eks[j])
 297                                         goto continue2;
 298                         }
 299
 300                         *tail = *tail << 1 | parity(LF_POLY_EVEN & *tail);
 301                         sl->odd = *tail ^ parity(LF_POLY_ODD & win);
 302                         sl->even = win;
 303                         ++sl;
 304                         sl->odd = sl->even = 0;
 305                         continue2:;
 306                 }
 307         }
 308         return statelist;
 309 }
 310
 311 /** lfsr_rollback_bit
 312  * Rollback the shift register in order to get previous states
 313  */
 314 void lfsr_rollback_bit(struct Crypto1State *s, uint32_t in, int fb)
 315 {
 316         int out;
 317
 318         s->odd &= 0xffffff;
 319         s->odd ^= (s->odd ^= s->even, s->even ^= s->odd);
 320
 321         out = s->even & 1;
 322         out ^= LF_POLY_EVEN & (s->even >>= 1);
 323         out ^= LF_POLY_ODD & s->odd;
 324         out ^= !!in;
 325         out ^= filter(s->odd) & !!fb;
 326
 327         s->even |= parity(out) << 23;
 328 }
 329 /** lfsr_rollback_byte
 330  * Rollback the shift register in order to get previous states
 331  */
 332 void lfsr_rollback_byte(struct Crypto1State *s, uint32_t in, int fb)
 333 {
 334         int i;
 335         for (i = 7; i >= 0; --i)
 336                 lfsr_rollback_bit(s, BEBIT(in, i), fb);
 337 }
 338 /** lfsr_rollback_word
 339  * Rollback the shift register in order to get previous states
 340  */
 341 void lfsr_rollback_word(struct Crypto1State *s, uint32_t in, int fb)
 342 {
 343         int i;
 344         for (i = 31; i >= 0; --i)
 345                 lfsr_rollback_bit(s, BEBIT(in, i), fb);
 346 }
 347
 348 /** nonce_distance
 349  * x,y valid tag nonces, then prng_successor(x, nonce_distance(x, y)) = y
 350  */
 351 static uint16_t *dist = 0;
 352 int nonce_distance(uint32_t from, uint32_t to)
 353 {
 354         uint16_t x, i;
 355         if(!dist) {
 356                 dist = malloc(2 << 16);
 357                 if(!dist)
 358                         return -1;
 359                 for (x = i = 1; i; ++i) {
 360                         dist[(x & 0xff) << 8 | x >> 8] = i;
 361                         x = x >> 1 | (x ^ x >> 2 ^ x >> 3 ^ x >> 5) << 15;
 362                 }
 363         }
 364         return (65535 + dist[to >> 16] - dist[from >> 16]) % 65535;
 365 }
 366
 367
 368 static uint32_t fastfwd[2][8] = {
 369         { 0, 0x4BC53, 0xECB1, 0x450E2, 0x25E29, 0x6E27A, 0x2B298, 0x60ECB},
 370         { 0, 0x1D962, 0x4BC53, 0x56531, 0xECB1, 0x135D3, 0x450E2, 0x58980}};
 371
 372
 373 /** lfsr_prefix_ks
 374  *
 375  * Is an exported helper function from the common prefix attack
 376  * Described in the "dark side" paper. It returns an -1 terminated array
 377  * of possible partial(21 bit) secret state.
 378  * The required keystream(ks) needs to contain the keystream that was used to
 379  * encrypt the NACK which is observed when varying only the 4 last bits of Nr
 380  * only correct iff [NR_3] ^ NR_3 does not depend on Nr_3
 381  */
 382 uint32_t *lfsr_prefix_ks(uint8_t ks[8], int isodd)
 383 {
 384         uint32_t *candidates = malloc(4 << 21);
 385         uint32_t c,  entry;
 386         int size, i;
 387
 388         if(!candidates)
 389                 return 0;
 390
 391         size = (1 << 21) - 1;
 392         for(i = 0; i <= size; ++i)
 393                 candidates[i] = i;
 394
 395         for(c = 0;  c < 8; ++c)
 396                 for(i = 0;i <= size; ++i) {
 397                         entry = candidates[i] ^ fastfwd[isodd][c];
 398
 399                         if(filter(entry >> 1) == BIT(ks[c], isodd))
 400                                 if(filter(entry) == BIT(ks[c], isodd + 2))
 401                                         continue;
 402
 403                         candidates[i--] = candidates[size--];
 404                 }
 405
 406         candidates[size + 1] = -1;
 407
 408         return candidates;
 409 }
 410
 411 /** brute_top
 412  * helper function which eliminates possible secret states using parity bits
 413  */
 414 static struct Crypto1State*
 415 brute_top(uint32_t prefix, uint32_t rresp, unsigned char parities[8][8],
 416           uint32_t odd, uint32_t even, struct Crypto1State* sl)
 417 {
 418         struct Crypto1State s;
 419         uint32_t ks1, nr, ks2, rr, ks3, good, c;
 420
 421         for(c = 0; c < 8; ++c) {
 422                 s.odd = odd ^ fastfwd[1][c];
 423                 s.even = even ^ fastfwd[0][c];
 424
 425                 lfsr_rollback_bit(&s, 0, 0);
 426                 lfsr_rollback_bit(&s, 0, 0);
 427                 lfsr_rollback_bit(&s, 0, 0);
 428
 429                 lfsr_rollback_word(&s, 0, 0);
 430                 lfsr_rollback_word(&s, prefix | c << 5, 1);
 431
 432                 sl->odd = s.odd;
 433                 sl->even = s.even;
 434
 435                 ks1 = crypto1_word(&s, prefix | c << 5, 1);
 436                 ks2 = crypto1_word(&s,0,0);
 437                 ks3 = crypto1_word(&s, 0,0);
 438                 nr = ks1 ^ (prefix | c << 5);
 439                 rr = ks2 ^ rresp;
 440
 441                 good = 1;
 442                 good &= parity(nr & 0x000000ff) ^ parities[c][3] ^ BIT(ks2, 24);
 443                 good &= parity(rr & 0xff000000) ^ parities[c][4] ^ BIT(ks2, 16);
 444                 good &= parity(rr & 0x00ff0000) ^ parities[c][5] ^ BIT(ks2,  8);
 445                 good &= parity(rr & 0x0000ff00) ^ parities[c][6] ^ BIT(ks2,  0);
 446                 good &= parity(rr & 0x000000ff) ^ parities[c][7] ^ BIT(ks3, 24);
 447
 448                 if(!good)
 449                         return sl;
 450         }
 451
 452         return ++sl;
 453 }
 454
 455
 456 /** lfsr_common_prefix
 457  * Implentation of the common prefix attack.
 458  * Requires the 28 bit constant prefix used as reader nonce (pfx)
 459  * The reader response used (rr)
 460  * The keystream used to encrypt the observed NACK's (ks)
 461  * The parity bits (par)
 462  * It returns a zero terminated list of possible cipher states after the
 463  * tag nonce was fed in
 464  */
 465 struct Crypto1State*
 466 lfsr_common_prefix(uint32_t pfx, uint32_t rr, uint8_t ks[8], uint8_t par[8][8])
 467 {
 468         struct Crypto1State *statelist, *s;
 469         uint32_t *odd, *even, *o, *e, top;
 470
 471         odd = lfsr_prefix_ks(ks, 1);
 472         even = lfsr_prefix_ks(ks, 0);
 473
 474         statelist = malloc((sizeof *statelist) << 20);
 475         if(!statelist || !odd || !even)
 476                 return 0;
 477
 478
 479         s = statelist;
 480         for(o = odd; *o != 0xffffffff; ++o)
 481                 for(e = even; *e != 0xffffffff; ++e)
 482                         for(top = 0; top < 64; ++top) {
 483                                 *o = (*o & 0x1fffff) | (top << 21);
 484                                 *e = (*e & 0x1fffff) | (top >> 3) << 21;
 485                                 s = brute_top(pfx, rr, par, *o, *e, s);
 486                         }
 487
 488         s->odd = s->even = 0;
 489
 490         free(odd);
 491         free(even);
 492
 493         return statelist;
 494 }