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