common/crapto1/crapto1.c

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