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