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