cvs.zerfleddert.de Git - proxmark3-svn/blob - client/nonce2key/crapto1.c

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