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