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         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                         tmp = *it;
  48                         *it = *rit;
  49                         *rit = tmp;
  50                 }
  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         s->odd &= 0xffffff;
 331         tmp = s->odd;
 332         s->odd = s->even;
 333         s->even = tmp;
 334
 335         out = s->even & 1;
 336         out ^= LF_POLY_EVEN & (s->even >>= 1);
 337         out ^= LF_POLY_ODD & s->odd;
 338         out ^= !!in;
 339         out ^= (ret = filter(s->odd)) & !!fb;
 340
 341         s->even |= parity(out) << 23;
 342         return ret;
 343 }
 344 /** lfsr_rollback_byte
 345  * Rollback the shift register in order to get previous states
 346  */
 347 uint8_t lfsr_rollback_byte(struct Crypto1State *s, uint32_t in, int fb)
 348 {
 349         int i, ret = 0;
 350         for (i = 7; i >= 0; --i)
 351                 ret |= lfsr_rollback_bit(s, BIT(in, i), fb) << i;
 352         return ret;
 353 }
 354 /** lfsr_rollback_word
 355  * Rollback the shift register in order to get previous states
 356  */
 357 uint32_t lfsr_rollback_word(struct Crypto1State *s, uint32_t in, int fb)
 358 {
 359         int i;
 360         uint32_t ret = 0;
 361         for (i = 31; i >= 0; --i)
 362                 ret |= lfsr_rollback_bit(s, BEBIT(in, i), fb) << (i ^ 24);
 363         return ret;
 364 }
 365
 366 /** nonce_distance
 367  * x,y valid tag nonces, then prng_successor(x, nonce_distance(x, y)) = y
 368  */
 369 static uint16_t *dist = 0;
 370 int nonce_distance(uint32_t from, uint32_t to)
 371 {
 372         uint16_t x, i;
 373         if(!dist) {
 374                 dist = malloc(2 << 16);
 375                 if(!dist)
 376                         return -1;
 377                 for (x = i = 1; i; ++i) {
 378                         dist[(x & 0xff) << 8 | x >> 8] = i;
 379                         x = x >> 1 | (x ^ x >> 2 ^ x >> 3 ^ x >> 5) << 15;
 380                 }
 381         }
 382         return (65535 + dist[to >> 16] - dist[from >> 16]) % 65535;
 383 }
 384
 385
 386 static uint32_t fastfwd[2][8] = {
 387         { 0, 0x4BC53, 0xECB1, 0x450E2, 0x25E29, 0x6E27A, 0x2B298, 0x60ECB},
 388         { 0, 0x1D962, 0x4BC53, 0x56531, 0xECB1, 0x135D3, 0x450E2, 0x58980}};
 389 /** lfsr_prefix_ks
 390  *
 391  * Is an exported helper function from the common prefix attack
 392  * Described in the "dark side" paper. It returns an -1 terminated array
 393  * of possible partial(21 bit) secret state.
 394  * The required keystream(ks) needs to contain the keystream that was used to
 395  * encrypt the NACK which is observed when varying only the 3 last bits of Nr
 396  * only correct iff [NR_3] ^ NR_3 does not depend on Nr_3
 397  */
 398 uint32_t *lfsr_prefix_ks(uint8_t ks[8], int isodd)
 399 {
 400         uint32_t c, entry, *candidates = malloc(4 << 10);
 401         int i, size = 0, good;
 402
 403         if(!candidates)
 404                 return 0;
 405
 406         for(i = 0; i < 1 << 21; ++i) {
 407                 for(c = 0, good = 1; good && c < 8; ++c) {
 408                         entry = i ^ fastfwd[isodd][c];
 409                         good &= (BIT(ks[c], isodd) == filter(entry >> 1));
 410                         good &= (BIT(ks[c], isodd + 2) == filter(entry));
 411                 }
 412                 if(good)
 413                         candidates[size++] = i;
 414         }
 415
 416         candidates[size] = -1;
 417
 418         return candidates;
 419 }
 420
 421 /** check_pfx_parity
 422  * helper function which eliminates possible secret states using parity bits
 423  */
 424 static struct Crypto1State*
 425 check_pfx_parity(uint32_t prefix, uint32_t rresp, uint8_t parities[8][8],
 426                 uint32_t odd, uint32_t even, struct Crypto1State* sl)
 427 {
 428         uint32_t ks1, nr, ks2, rr, ks3, c, good = 1;
 429
 430         for(c = 0; good && c < 8; ++c) {
 431                 sl->odd = odd ^ fastfwd[1][c];
 432                 sl->even = even ^ fastfwd[0][c];
 433
 434                 lfsr_rollback_bit(sl, 0, 0);
 435                 lfsr_rollback_bit(sl, 0, 0);
 436
 437                 ks3 = lfsr_rollback_bit(sl, 0, 0);
 438                 ks2 = lfsr_rollback_word(sl, 0, 0);
 439                 ks1 = lfsr_rollback_word(sl, prefix | c << 5, 1);
 440
 441                 nr = ks1 ^ (prefix | c << 5);
 442                 rr = ks2 ^ rresp;
 443
 444                 good &= parity(nr & 0x000000ff) ^ parities[c][3] ^ BIT(ks2, 24);
 445                 good &= parity(rr & 0xff000000) ^ parities[c][4] ^ BIT(ks2, 16);
 446                 good &= parity(rr & 0x00ff0000) ^ parities[c][5] ^ BIT(ks2,  8);
 447                 good &= parity(rr & 0x0000ff00) ^ parities[c][6] ^ BIT(ks2,  0);
 448                 good &= parity(rr & 0x000000ff) ^ parities[c][7] ^ ks3;
 449         }
 450
 451         return sl + good;
 452 }
 453
 454
 455 /** lfsr_common_prefix
 456  * Implentation of the common prefix attack.
 457  */
 458 struct Crypto1State*
 459 lfsr_common_prefix(uint32_t pfx, uint32_t rr, uint8_t ks[8], uint8_t par[8][8])
 460 {
 461         struct Crypto1State *statelist, *s;
 462         uint32_t *odd, *even, *o, *e, top;
 463
 464         odd = lfsr_prefix_ks(ks, 1);
 465         even = lfsr_prefix_ks(ks, 0);
 466
 467         s = statelist = malloc((sizeof *statelist) << 20);
 468         if(!s || !odd || !even) {
 469                 free(statelist);
 470                 statelist = 0;
 471                 goto out;
 472         }
 473
 474         for(o = odd; *o + 1; ++o)
 475                 for(e = even; *e + 1; ++e)
 476                         for(top = 0; top < 64; ++top) {
 477                                 *o += 1 << 21;
 478                                 *e += (!(top & 7) + 1) << 21;
 479                                 s = check_pfx_parity(pfx, rr, par, *o, *e, s);
 480                         }
 481
 482         s->odd = s->even = 0;
 483 out:
 484         free(odd);
 485         free(even);
 486         return statelist;
 487 }