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