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