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 /** lfsr_rollback_word
 413  * Rollback the shift register in order to get previous states
 414  */
 415 void lfsr_rollback_word(struct Crypto1State *s, uint32_t in, int fb)
 416 {
 417         int i;
 418         for (i = 31; i >= 0; --i)
 419                 lfsr_rollback_bit(s, BEBIT(in, i), fb);
 420 }
 421
 422 /** nonce_distance
 423  * x,y valid tag nonces, then prng_successor(x, nonce_distance(x, y)) = y
 424  */
 425 static uint16_t *dist = 0;
 426 int nonce_distance(uint32_t from, uint32_t to)
 427 {
 428         uint16_t x, i;
 429         if(!dist) {
 430                 dist = malloc(2 << 16);
 431                 if(!dist)
 432                         return -1;
 433                 for (x = i = 1; i; ++i) {
 434                         dist[(x & 0xff) << 8 | x >> 8] = i;
 435                         x = x >> 1 | (x ^ x >> 2 ^ x >> 3 ^ x >> 5) << 15;
 436                 }
 437         }
 438         return (65535 + dist[to >> 16] - dist[from >> 16]) % 65535;
 439 }
 440
 441
 442 static uint32_t fastfwd[2][8] = {
 443         { 0, 0x4BC53, 0xECB1, 0x450E2, 0x25E29, 0x6E27A, 0x2B298, 0x60ECB},
 444         { 0, 0x1D962, 0x4BC53, 0x56531, 0xECB1, 0x135D3, 0x450E2, 0x58980}};
 445
 446
 447 /** lfsr_prefix_ks
 448  *
 449  * Is an exported helper function from the common prefix attack
 450  * Described in the "dark side" paper. It returns an -1 terminated array
 451  * of possible partial(21 bit) secret state.
 452  * The required keystream(ks) needs to contain the keystream that was used to
 453  * encrypt the NACK which is observed when varying only the 4 last bits of Nr
 454  * only correct iff [NR_3] ^ NR_3 does not depend on Nr_3
 455  */
 456 uint32_t *lfsr_prefix_ks(uint8_t ks[8], int isodd)
 457 {
 458         uint32_t *candidates = malloc(4 << 21);
 459         uint32_t c,  entry;
 460         int size, i;
 461
 462         if(!candidates)
 463                 return 0;
 464
 465         size = (1 << 21) - 1;
 466         for(i = 0; i <= size; ++i)
 467                 candidates[i] = i;
 468
 469         for(c = 0;  c < 8; ++c)
 470                 for(i = 0;i <= size; ++i) {
 471                         entry = candidates[i] ^ fastfwd[isodd][c];
 472
 473                         if(filter(entry >> 1) == BIT(ks[c], isodd))
 474                                 if(filter(entry) == BIT(ks[c], isodd + 2))
 475                                         continue;
 476
 477                         candidates[i--] = candidates[size--];
 478                 }
 479
 480         candidates[size + 1] = -1;
 481
 482         return candidates;
 483 }
 484
 485 /** brute_top
 486  * helper function which eliminates possible secret states using parity bits
 487  */
 488 static struct Crypto1State*
 489 brute_top(uint32_t prefix, uint32_t rresp, unsigned char parities[8][8],
 490           uint32_t odd, uint32_t even, struct Crypto1State* sl, uint8_t no_chk)
 491 {
 492         struct Crypto1State s;
 493         uint32_t ks1, nr, ks2, rr, ks3, good, c;
 494
 495         for(c = 0; c < 8; ++c) {
 496                 s.odd = odd ^ fastfwd[1][c];
 497                 s.even = even ^ fastfwd[0][c];
 498
 499                 lfsr_rollback_bit(&s, 0, 0);
 500                 lfsr_rollback_bit(&s, 0, 0);
 501                 lfsr_rollback_bit(&s, 0, 0);
 502
 503                 lfsr_rollback_word(&s, 0, 0);
 504                 lfsr_rollback_word(&s, prefix | c << 5, 1);
 505
 506                 sl->odd = s.odd;
 507                 sl->even = s.even;
 508
 509                 if (no_chk)
 510                         break;
 511
 512                 ks1 = crypto1_word(&s, prefix | c << 5, 1);
 513                 ks2 = crypto1_word(&s,0,0);
 514                 ks3 = crypto1_word(&s, 0,0);
 515                 nr = ks1 ^ (prefix | c << 5);
 516                 rr = ks2 ^ rresp;
 517
 518                 good = 1;
 519                 good &= parity(nr & 0x000000ff) ^ parities[c][3] ^ BIT(ks2, 24);
 520                 good &= parity(rr & 0xff000000) ^ parities[c][4] ^ BIT(ks2, 16);
 521                 good &= parity(rr & 0x00ff0000) ^ parities[c][5] ^ BIT(ks2,  8);
 522                 good &= parity(rr & 0x0000ff00) ^ parities[c][6] ^ BIT(ks2,  0);
 523                 good &= parity(rr & 0x000000ff) ^ parities[c][7] ^ BIT(ks3, 24);
 524
 525                 if(!good)
 526                         return sl;
 527         }
 528
 529         return ++sl;
 530 }
 531
 532
 533 /** lfsr_common_prefix
 534  * Implentation of the common prefix attack.
 535  * Requires the 28 bit constant prefix used as reader nonce (pfx)
 536  * The reader response used (rr)
 537  * The keystream used to encrypt the observed NACK's (ks)
 538  * The parity bits (par)
 539  * It returns a zero terminated list of possible cipher states after the
 540  * tag nonce was fed in
 541  */
 542 struct Crypto1State* lfsr_common_prefix(uint32_t pfx, uint32_t rr, uint8_t ks[8], uint8_t par[8][8], uint8_t no_par)
 543 {
 544         struct Crypto1State *statelist, *s;
 545         uint32_t *odd, *even, *o, *e, top;
 546
 547         odd = lfsr_prefix_ks(ks, 1);
 548         even = lfsr_prefix_ks(ks, 0);
 549
 550         statelist = malloc((sizeof *statelist) << 21);  //how large should be?
 551         if(!statelist || !odd || !even)
 552         {
 553                 free(statelist);
 554                 free(odd);
 555                 free(even);
 556                 return 0;
 557         }
 558
 559         s = statelist;
 560         for(o = odd; *o != -1; ++o)
 561                 for(e = even; *e != -1; ++e)
 562                         for(top = 0; top < 64; ++top) {
 563                                 *o = (*o & 0x1fffff) | (top << 21);
 564                                 *e = (*e & 0x1fffff) | (top >> 3) << 21;
 565                                 s = brute_top(pfx, rr, par, *o, *e, s, no_par);
 566                         }
 567
 568         s->odd = s->even = -1;
 569         //printf("state count = %d\n",s-statelist);
 570
 571         free(odd);
 572         free(even);
 573
 574         return statelist;
 575 }
 576
 577 /*
 578 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)
 579 {
 580     long long int amount = 0;
 581     struct Crypto1State *statelist, *s;
 582     uint32_t *odd, *even, *o, *e, top;
 583
 584     odd = lfsr_prefix_ks(ks, 1);
 585     even = lfsr_prefix_ks(ks, 0);
 586
 587     s = statelist = malloc((sizeof *statelist) << 20);
 588     if(!s || !odd || !even) {
 589                 free(odd);
 590                 free(even);
 591                 free(statelist);
 592                 return 0;
 593     }
 594
 595     char filename[50] = "archivo.txt";
 596     sprintf(filename, "logs/%x.txt", nt);
 597     PrintAndLog("Name: %s\n", filename);
 598     FILE *file = fopen(filename,"w+");
 599         if ( !file ) {
 600                 s->odd = s->even = 0;
 601                 free(odd);
 602                 free(even);
 603                 PrintAndLog("Failed to create file");
 604                 return 0;
 605         }
 606     PrintAndLog("Creating file... ");
 607         uint32_t xored = uid^nt;
 608
 609     int lastOdd = 0;
 610     for(o = odd; *o + 1; ++o)
 611         for(e = even; *e + 1; ++e)
 612             for(top = 0; top < 64; ++top) {
 613                 *o += 1 << 21;
 614                 *e += (!(top & 7) + 1) << 21;
 615
 616                 //added by MG
 617                 if(lastOdd != statelist->odd){
 618                                         // Here I create a temporal crypto1 state,
 619                                         // where I load the odd and even state and work with it,
 620                                         // in order not to interfere with regular mechanism, This is what I save to file
 621                                         struct Crypto1State *state;
 622                     lastOdd = state->odd = statelist->odd; state->even = statelist->even;
 623                     lfsr_rollback_word(state,xored,0);
 624                     fprintf(file,"%x %x \n",state->odd,state->even);
 625                     amount++;
 626                 }
 627                 //s = check_pfx_parity(pfx, rr, par, *o, *e, s); //This is not useful at all when attacking chineese cards
 628                                 s = brute_top(pfx, rr, par, *o, *e, s, no_par);
 629             }
 630
 631         PrintAndLog("File created, amount %u\n",amount);
 632         fclose(file);
 633         s->odd = s->even = 0;
 634         free(odd);
 635         free(even);
 636     return statelist;
 637 }
 638  */