git.zerfleddert.de Git - proxmark3-svn/blob - tools/mfkey/crapto1.c

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