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