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