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