git.zerfleddert.de Git - proxmark3-svn/blob - client/nonce2key/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 /** update_contribution
  35  * helper, calculates the partial linear feedback contributions and puts in MSB
  36  */
  37 static inline void update_contribution(uint32_t *item, const uint32_t mask1, const uint32_t mask2)
  38 {
  39         uint32_t p = *item >> 25;
  40
  41         p = p << 1 | parity(*item & mask1);
  42         p = p << 1 | parity(*item & mask2);
  43         *item = p << 24 | (*item & 0xffffff);
  44 }
  45
  46 /** extend_table
  47  * using a bit of the keystream extend the table of possible lfsr states
  48  */
  49 static inline void extend_table(uint32_t *tbl, uint32_t **end, int bit, int m1, int m2, uint32_t in)
  50 {
  51         in <<= 24;
  52         for(*tbl <<= 1; tbl <= *end; *++tbl <<= 1)
  53                 if(filter(*tbl) ^ filter(*tbl | 1)) {
  54                         *tbl |= filter(*tbl) ^ bit;
  55                         update_contribution(tbl, m1, m2);
  56                         *tbl ^= in;
  57                 } else if(filter(*tbl) == bit) {
  58                         *++*end = tbl[1];
  59                         tbl[1] = tbl[0] | 1;
  60                         update_contribution(tbl, m1, m2);
  61                         *tbl++ ^= in;
  62                         update_contribution(tbl, m1, m2);
  63                         *tbl ^= in;
  64                 } else
  65                         *tbl-- = *(*end)--;
  66 }
  67 /** extend_table_simple
  68  * using a bit of the keystream extend the table of possible lfsr states
  69  */
  70 static inline void extend_table_simple(uint32_t *tbl, uint32_t **end, int bit)
  71 {
  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 {
  91         uint32_t *o, *e;
  92         bucket_info_t bucket_info;
  93
  94         if(rem == -1) {
  95                 for(e = e_head; e <= e_tail; ++e) {
  96                         *e = *e << 1 ^ parity(*e & LF_POLY_EVEN) ^ !!(in & 4);
  97                         for(o = o_head; o <= o_tail; ++o, ++sl) {
  98                                 sl->even = *o;
  99                                 sl->odd = *e ^ parity(*o & LF_POLY_ODD);
 100                                 sl[1].odd = sl[1].even = 0;
 101                         }
 102                 }
 103                 return sl;
 104         }
 105
 106         for(uint32_t i = 0; i < 4 && rem--; i++) {
 107                 oks >>= 1;
 108                 eks >>= 1;
 109                 in >>= 2;
 110                 extend_table(o_head, &o_tail, oks & 1, LF_POLY_EVEN << 1 | 1, LF_POLY_ODD << 1, 0);
 111                 if(o_head > o_tail)
 112                         return sl;
 113
 114                 extend_table(e_head, &e_tail, eks & 1, LF_POLY_ODD, LF_POLY_EVEN << 1 | 1, in & 3);
 115                 if(e_head > e_tail)
 116                         return sl;
 117         }
 118
 119         bucket_sort_intersect(e_head, e_tail, o_head, o_tail, &bucket_info, bucket);
 120
 121         for (int i = bucket_info.numbuckets - 1; i >= 0; i--) {
 122                 sl = recover(bucket_info.bucket_info[1][i].head, bucket_info.bucket_info[1][i].tail, oks,
 123                                          bucket_info.bucket_info[0][i].head, bucket_info.bucket_info[0][i].tail, eks,
 124                                          rem, sl, in, bucket);
 125         }
 126
 127         return sl;
 128 }
 129 /** lfsr_recovery
 130  * recover the state of the lfsr given 32 bits of the keystream
 131  * additionally you can use the in parameter to specify the value
 132  * that was fed into the lfsr at the time the keystream was generated
 133  */
 134 struct Crypto1State* lfsr_recovery32(uint32_t ks2, uint32_t in)
 135 {
 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 (uint32_t 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 (uint32_t 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 static const uint32_t S2[] = {  0x3A557B00, 0x5D2ABD80, 0x2E955EC0, 0x174AAF60,
 203         0x0BA557B0, 0x05D2ABD8, 0x0449DE68, 0x048464B0, 0x42423258, 0x278192A8,
 204         0x156042D0, 0x0AB02168, 0x43F89B30, 0x61FC4D98, 0x765EAD48, 0x7D8FDD20,
 205         0x7EC7EE90, 0x7F63F748, 0x79117020};
 206 static const uint32_t T1[] = {
 207         0x4F37D, 0x279BE, 0x97A6A, 0x4BD35, 0x25E9A, 0x12F4D, 0x097A6, 0x80D66,
 208         0xC4006, 0x62003, 0xB56B4, 0x5AB5A, 0xA9318, 0xD0F39, 0x6879C, 0xB057B,
 209         0x582BD, 0x2C15E, 0x160AF, 0x8F6E2, 0xC3DC4, 0xE5857, 0x72C2B, 0x39615,
 210         0x98DBF, 0xC806A, 0xE0680, 0x70340, 0x381A0, 0x98665, 0x4C332, 0xA272C};
 211 static const uint32_t T2[] = {  0x3C88B810, 0x5E445C08, 0x2982A580, 0x14C152C0,
 212         0x4A60A960, 0x253054B0, 0x52982A58, 0x2FEC9EA8, 0x1156C4D0, 0x08AB6268,
 213         0x42F53AB0, 0x217A9D58, 0x161DC528, 0x0DAE6910, 0x46D73488, 0x25CB11C0,
 214         0x52E588E0, 0x6972C470, 0x34B96238, 0x5CFC3A98, 0x28DE96C8, 0x12CFC0E0,
 215         0x4967E070, 0x64B3F038, 0x74F97398, 0x7CDC3248, 0x38CE92A0, 0x1C674950,
 216         0x0E33A4A8, 0x01B959D0, 0x40DCACE8, 0x26CEDDF0};
 217 static const uint32_t C1[] = { 0x846B5, 0x4235A, 0x211AD};
 218 static const uint32_t C2[] = { 0x1A822E0, 0x21A822E0, 0x21A822E0};
 219 /** Reverse 64 bits of keystream into possible cipher states
 220  * Variation mentioned in the paper. Somewhat optimized version
 221  */
 222 struct Crypto1State* lfsr_recovery64(uint32_t ks2, uint32_t ks3)
 223 {
 224         struct Crypto1State *statelist, *sl;
 225         uint8_t oks[32], eks[32], hi[32];
 226         uint32_t low = 0,  win = 0;
 227         uint32_t *tail, table[1 << 16];
 228         int i, j;
 229
 230         sl = statelist = malloc(sizeof(struct Crypto1State) << 4);
 231         if(!sl)
 232                 return 0;
 233         sl->odd = sl->even = 0;
 234
 235         for(i = 30; i >= 0; i -= 2) {
 236                 oks[i >> 1] = BEBIT(ks2, i);
 237                 oks[16 + (i >> 1)] = BEBIT(ks3, i);
 238         }
 239         for(i = 31; i >= 0; i -= 2) {
 240                 eks[i >> 1] = BEBIT(ks2, i);
 241                 eks[16 + (i >> 1)] = BEBIT(ks3, i);
 242         }
 243
 244         for(i = 0xfffff; i >= 0; --i) {
 245                 if (filter(i) != oks[0])
 246                         continue;
 247
 248                 *(tail = table) = i;
 249                 for(j = 1; tail >= table && j < 29; ++j)
 250                         extend_table_simple(table, &tail, oks[j]);
 251
 252                 if(tail < table)
 253                         continue;
 254
 255                 for(j = 0; j < 19; ++j)
 256                         low = low << 1 | parity(i & S1[j]);
 257                 for(j = 0; j < 32; ++j)
 258                         hi[j] = parity(i & T1[j]);
 259
 260                 for(; tail >= table; --tail) {
 261                         for(j = 0; j < 3; ++j) {
 262                                 *tail = *tail << 1;
 263                                 *tail |= parity((i & C1[j]) ^ (*tail & C2[j]));
 264                                 if(filter(*tail) != oks[29 + j])
 265                                         goto continue2;
 266                         }
 267
 268                         for(j = 0; j < 19; ++j)
 269                                 win = win << 1 | parity(*tail & S2[j]);
 270
 271                         win ^= low;
 272                         for(j = 0; j < 32; ++j) {
 273                                 win = win << 1 ^ hi[j] ^ parity(*tail & T2[j]);
 274                                 if(filter(win) != eks[j])
 275                                         goto continue2;
 276                         }
 277
 278                         *tail = *tail << 1 | parity(LF_POLY_EVEN & *tail);
 279                         sl->odd = *tail ^ parity(LF_POLY_ODD & win);
 280                         sl->even = win;
 281                         ++sl;
 282                         sl->odd = sl->even = 0;
 283                         continue2:;
 284                 }
 285         }
 286         return statelist;
 287 }
 288
 289 /** lfsr_rollback_bit
 290  * Rollback the shift register in order to get previous states
 291  */
 292 uint8_t lfsr_rollback_bit(struct Crypto1State *s, uint32_t in, int fb)
 293 {
 294         int out;
 295         uint8_t ret;
 296         uint32_t t;
 297
 298         s->odd &= 0xffffff;
 299         t = s->odd, s->odd = s->even, s->even = t;
 300
 301         out = s->even & 1;
 302         out ^= LF_POLY_EVEN & (s->even >>= 1);
 303         out ^= LF_POLY_ODD & s->odd;
 304         out ^= !!in;
 305         out ^= (ret = filter(s->odd)) & !!fb;
 306
 307         s->even |= parity(out) << 23;
 308         return ret;
 309 }
 310 /** lfsr_rollback_byte
 311  * Rollback the shift register in order to get previous states
 312  */
 313 uint8_t lfsr_rollback_byte(struct Crypto1State *s, uint32_t in, int fb)
 314 {
 315         /*
 316         int i, ret = 0;
 317         for (i = 7; i >= 0; --i)
 318                 ret |= lfsr_rollback_bit(s, BIT(in, i), fb) << i;
 319 */
 320 // unfold loop 20160112
 321         uint8_t ret = 0;
 322         ret |= lfsr_rollback_bit(s, BIT(in, 7), fb) << 7;
 323         ret |= lfsr_rollback_bit(s, BIT(in, 6), fb) << 6;
 324         ret |= lfsr_rollback_bit(s, BIT(in, 5), fb) << 5;
 325         ret |= lfsr_rollback_bit(s, BIT(in, 4), fb) << 4;
 326         ret |= lfsr_rollback_bit(s, BIT(in, 3), fb) << 3;
 327         ret |= lfsr_rollback_bit(s, BIT(in, 2), fb) << 2;
 328         ret |= lfsr_rollback_bit(s, BIT(in, 1), fb) << 1;
 329         ret |= lfsr_rollback_bit(s, BIT(in, 0), fb) << 0;
 330         return ret;
 331 }
 332 /** lfsr_rollback_word
 333  * Rollback the shift register in order to get previous states
 334  */
 335 uint32_t lfsr_rollback_word(struct Crypto1State *s, uint32_t in, int fb)
 336 {
 337         /*
 338         int i;
 339         uint32_t ret = 0;
 340         for (i = 31; i >= 0; --i)
 341                 ret |= lfsr_rollback_bit(s, BEBIT(in, i), fb) << (i ^ 24);
 342 */
 343 // unfold loop 20160112
 344         uint32_t ret = 0;
 345         ret |= lfsr_rollback_bit(s, BEBIT(in, 31), fb) << (31 ^ 24);
 346         ret |= lfsr_rollback_bit(s, BEBIT(in, 30), fb) << (30 ^ 24);
 347         ret |= lfsr_rollback_bit(s, BEBIT(in, 29), fb) << (29 ^ 24);
 348         ret |= lfsr_rollback_bit(s, BEBIT(in, 28), fb) << (28 ^ 24);
 349         ret |= lfsr_rollback_bit(s, BEBIT(in, 27), fb) << (27 ^ 24);
 350         ret |= lfsr_rollback_bit(s, BEBIT(in, 26), fb) << (26 ^ 24);
 351         ret |= lfsr_rollback_bit(s, BEBIT(in, 25), fb) << (25 ^ 24);
 352         ret |= lfsr_rollback_bit(s, BEBIT(in, 24), fb) << (24 ^ 24);
 353
 354         ret |= lfsr_rollback_bit(s, BEBIT(in, 23), fb) << (23 ^ 24);
 355         ret |= lfsr_rollback_bit(s, BEBIT(in, 22), fb) << (22 ^ 24);
 356         ret |= lfsr_rollback_bit(s, BEBIT(in, 21), fb) << (21 ^ 24);
 357         ret |= lfsr_rollback_bit(s, BEBIT(in, 20), fb) << (20 ^ 24);
 358         ret |= lfsr_rollback_bit(s, BEBIT(in, 19), fb) << (19 ^ 24);
 359         ret |= lfsr_rollback_bit(s, BEBIT(in, 18), fb) << (18 ^ 24);
 360         ret |= lfsr_rollback_bit(s, BEBIT(in, 17), fb) << (17 ^ 24);
 361         ret |= lfsr_rollback_bit(s, BEBIT(in, 16), fb) << (16 ^ 24);
 362
 363         ret |= lfsr_rollback_bit(s, BEBIT(in, 15), fb) << (15 ^ 24);
 364         ret |= lfsr_rollback_bit(s, BEBIT(in, 14), fb) << (14 ^ 24);
 365         ret |= lfsr_rollback_bit(s, BEBIT(in, 13), fb) << (13 ^ 24);
 366         ret |= lfsr_rollback_bit(s, BEBIT(in, 12), fb) << (12 ^ 24);
 367         ret |= lfsr_rollback_bit(s, BEBIT(in, 11), fb) << (11 ^ 24);
 368         ret |= lfsr_rollback_bit(s, BEBIT(in, 10), fb) << (10 ^ 24);
 369         ret |= lfsr_rollback_bit(s, BEBIT(in, 9), fb) << (9 ^ 24);
 370         ret |= lfsr_rollback_bit(s, BEBIT(in, 8), fb) << (8 ^ 24);
 371
 372         ret |= lfsr_rollback_bit(s, BEBIT(in, 7), fb) << (7 ^ 24);
 373         ret |= lfsr_rollback_bit(s, BEBIT(in, 6), fb) << (6 ^ 24);
 374         ret |= lfsr_rollback_bit(s, BEBIT(in, 5), fb) << (5 ^ 24);
 375         ret |= lfsr_rollback_bit(s, BEBIT(in, 4), fb) << (4 ^ 24);
 376         ret |= lfsr_rollback_bit(s, BEBIT(in, 3), fb) << (3 ^ 24);
 377         ret |= lfsr_rollback_bit(s, BEBIT(in, 2), fb) << (2 ^ 24);
 378         ret |= lfsr_rollback_bit(s, BEBIT(in, 1), fb) << (1 ^ 24);
 379         ret |= lfsr_rollback_bit(s, BEBIT(in, 0), fb) << (0 ^ 24);
 380         return ret;
 381 }
 382
 383 /** nonce_distance
 384  * x,y valid tag nonces, then prng_successor(x, nonce_distance(x, y)) = y
 385  */
 386 static uint16_t *dist;
 387 int nonce_distance(uint32_t from, uint32_t to)
 388 {
 389         uint16_t x, i;
 390         if(!dist) {
 391                 dist = malloc(2 << 16);
 392                 if(!dist)
 393                         return -1;
 394                 for (x = 1, i = 1; i; ++i) {
 395                         dist[(x & 0xff) << 8 | x >> 8] = i;
 396                         x = x >> 1 | (x ^ x >> 2 ^ x >> 3 ^ x >> 5) << 15;
 397                 }
 398         }
 399         return (65535 + dist[to >> 16] - dist[from >> 16]) % 65535;
 400 }
 401
 402
 403 static uint32_t fastfwd[2][8] = {
 404         { 0, 0x4BC53, 0xECB1, 0x450E2, 0x25E29, 0x6E27A, 0x2B298, 0x60ECB},
 405         { 0, 0x1D962, 0x4BC53, 0x56531, 0xECB1, 0x135D3, 0x450E2, 0x58980}};
 406
 407
 408 /** lfsr_prefix_ks
 409  *
 410  * Is an exported helper function from the common prefix attack
 411  * Described in the "dark side" paper. It returns an -1 terminated array
 412  * of possible partial(21 bit) secret state.
 413  * The required keystream(ks) needs to contain the keystream that was used to
 414  * encrypt the NACK which is observed when varying only the 3 last bits of Nr
 415  * only correct iff [NR_3] ^ NR_3 does not depend on Nr_3
 416  */
 417 uint32_t *lfsr_prefix_ks(uint8_t ks[8], int isodd)
 418 {
 419         uint32_t *candidates = malloc(4 << 10);
 420         if(!candidates) return 0;
 421
 422         uint32_t c,  entry;
 423         int size = 0, i, good;
 424
 425         for(i = 0; i < 1 << 21; ++i) {
 426                 for(c = 0, good = 1; good && c < 8; ++c) {
 427                         entry = i ^ fastfwd[isodd][c];
 428                         good &= (BIT(ks[c], isodd) == filter(entry >> 1));
 429                         good &= (BIT(ks[c], isodd + 2) == filter(entry));
 430                 }
 431                 if(good)
 432                         candidates[size++] = i;
 433         }
 434
 435         candidates[size] = -1;
 436
 437         return candidates;
 438 }
 439
 440 /** check_pfx_parity
 441  * helper function which eliminates possible secret states using parity bits
 442  */
 443 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)
 444 {
 445         uint32_t ks1, nr, ks2, rr, ks3, c, good = 1;
 446
 447         for(c = 0; good && c < 8; ++c) {
 448                 sl->odd = odd ^ fastfwd[1][c];
 449                 sl->even = even ^ fastfwd[0][c];
 450
 451                 lfsr_rollback_bit(sl, 0, 0);
 452                 lfsr_rollback_bit(sl, 0, 0);
 453
 454                 ks3 = lfsr_rollback_bit(sl, 0, 0);
 455                 ks2 = lfsr_rollback_word(sl, 0, 0);
 456                 ks1 = lfsr_rollback_word(sl, prefix | c << 5, 1);
 457
 458                 nr = ks1 ^ (prefix | c << 5);
 459                 rr = ks2 ^ rresp;
 460
 461                 good &= parity(nr & 0x000000ff) ^ parities[c][3] ^ BIT(ks2, 24);
 462                 good &= parity(rr & 0xff000000) ^ parities[c][4] ^ BIT(ks2, 16);
 463                 good &= parity(rr & 0x00ff0000) ^ parities[c][5] ^ BIT(ks2,  8);
 464                 good &= parity(rr & 0x0000ff00) ^ parities[c][6] ^ BIT(ks2,  0);
 465                 good &= parity(rr & 0x000000ff) ^ parities[c][7] ^ ks3;
 466         }
 467
 468         return sl + good;
 469 }
 470 static struct Crypto1State* check_pfx_parity_ex(uint32_t prefix, uint32_t odd, uint32_t even, struct Crypto1State* sl) {
 471         struct Crypto1State s;
 472         uint32_t c = 0;
 473
 474         s.odd = odd ^ fastfwd[1][c];
 475         s.even = even ^ fastfwd[0][c];
 476
 477         lfsr_rollback_bit(&s, 0, 0);
 478         lfsr_rollback_bit(&s, 0, 0);
 479         lfsr_rollback_bit(&s, 0, 0);
 480
 481         lfsr_rollback_word(&s, 0, 0);
 482         lfsr_rollback_word(&s, prefix | c << 5, 1);
 483
 484         sl->odd = s.odd;
 485         sl->even = s.even;
 486         return ++sl;
 487 }
 488
 489 /** lfsr_common_prefix
 490  * Implentation of the common prefix attack.
 491  * Requires the 28 bit constant prefix used as reader nonce (pfx)
 492  * The reader response used (rr)
 493  * The keystream used to encrypt the observed NACK's (ks)
 494  * The parity bits (par)
 495  * It returns a zero terminated list of possible cipher states after the
 496  * tag nonce was fed in
 497  */
 498
 499 struct Crypto1State* lfsr_common_prefix(uint32_t pfx, uint32_t rr, uint8_t ks[8], uint8_t par[8][8])
 500 {
 501         struct Crypto1State *statelist, *s;
 502         uint32_t *odd, *even, *o, *e, top;
 503
 504         odd = lfsr_prefix_ks(ks, 1);
 505         even = lfsr_prefix_ks(ks, 0);
 506
 507         s = statelist = malloc((sizeof *statelist) << 20);
 508         if(!s || !odd || !even) {
 509                 free(statelist);
 510                 statelist = 0;
 511                 goto out;
 512         }
 513
 514         for(o = odd; *o + 1; ++o)
 515                 for(e = even; *e + 1; ++e)
 516                         for(top = 0; top < 64; ++top) {
 517                                 *o += 1 << 21;
 518                                 *e += (!(top & 7) + 1) << 21;
 519                                 s = check_pfx_parity(pfx, rr, par, *o, *e, s);
 520                         }
 521
 522         s->odd = s->even = 0;
 523 out:
 524         free(odd);
 525         free(even);
 526         return statelist;
 527 }
 528
 529 struct Crypto1State* lfsr_common_prefix_ex(uint32_t pfx, uint8_t ks[8])
 530 {
 531         struct Crypto1State *statelist, *s;
 532         uint32_t *odd, *even, *o, *e, top;
 533
 534         odd = lfsr_prefix_ks(ks, 1);
 535         even = lfsr_prefix_ks(ks, 0);
 536
 537         s = statelist = malloc((sizeof *statelist) << 20);
 538         if(!s || !odd || !even) {
 539                 free(statelist);
 540                 statelist = 0;
 541                 goto out;
 542         }
 543
 544         for(o = odd; *o + 1; ++o)
 545                 for(e = even; *e + 1; ++e)
 546                         for(top = 0; top < 64; ++top) {
 547                                 *o += 1 << 21;
 548                                 *e += (!(top & 7) + 1) << 21;
 549                                 s = check_pfx_parity_ex(pfx, *o, *e, s);
 550                         }
 551
 552         s->odd = s->even = 0;
 553
 554 out:
 555         free(odd);
 556         free(even);
 557         return statelist;
 558 }