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