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