git.zerfleddert.de Git - proxmark3-svn/blob - client/cmdhfmfhard.c

   1 //-----------------------------------------------------------------------------
   2 // Copyright (C) 2015 piwi
   3 //
   4 // This code is licensed to you under the terms of the GNU GPL, version 2 or,
   5 // at your option, any later version. See the LICENSE.txt file for the text of
   6 // the license.
   7 //-----------------------------------------------------------------------------
   8 // Implements a card only attack based on crypto text (encrypted nonces
   9 // received during a nested authentication) only. Unlike other card only
  10 // attacks this doesn't rely on implementation errors but only on the
  11 // inherent weaknesses of the crypto1 cypher. Described in
  12 //   Carlo Meijer, Roel Verdult, "Ciphertext-only Cryptanalysis on Hardened
  13 //   Mifare Classic Cards" in Proceedings of the 22nd ACM SIGSAC Conference on
  14 //   Computer and Communications Security, 2015
  15 //-----------------------------------------------------------------------------
  16
  17 #include <stdio.h>
  18 #include <stdlib.h>
  19 #include <string.h>
  20 #include <pthread.h>
  21 #include <locale.h>
  22 #include <math.h>
  23 #include "proxmark3.h"
  24 #include "cmdmain.h"
  25 #include "ui.h"
  26 #include "util.h"
  27 #include "nonce2key/crapto1.h"
  28 #include "parity.h"
  29
  30 // uint32_t test_state_odd = 0;
  31 // uint32_t test_state_even = 0;
  32
  33 #define CONFIDENCE_THRESHOLD    0.95            // Collect nonces until we are certain enough that the following brute force is successfull
  34 #define GOOD_BYTES_REQUIRED             30
  35
  36
  37 static const float p_K[257] = {         // the probability that a random nonce has a Sum Property == K
  38         0.0290, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
  39         0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
  40         0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
  41         0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
  42         0.0083, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
  43         0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
  44         0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
  45         0.0006, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
  46         0.0339, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
  47         0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
  48         0.0048, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
  49         0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
  50         0.0934, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
  51         0.0119, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
  52         0.0489, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
  53         0.0602, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
  54         0.4180, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
  55         0.0602, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
  56         0.0489, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
  57         0.0119, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
  58         0.0934, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
  59         0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
  60         0.0048, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
  61         0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
  62         0.0339, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
  63         0.0006, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
  64         0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
  65         0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
  66         0.0083, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
  67         0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
  68         0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
  69         0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
  70         0.0290 };
  71
  72
  73 typedef struct noncelistentry {
  74         uint32_t nonce_enc;
  75         uint8_t par_enc;
  76         void *next;
  77 } noncelistentry_t;
  78
  79 typedef struct noncelist {
  80         uint16_t num;
  81         uint16_t Sum;
  82         uint16_t Sum8_guess;
  83         uint8_t BitFlip[2];
  84         float Sum8_prob;
  85         bool updated;
  86         noncelistentry_t *first;
  87         float score1, score2;
  88 } noncelist_t;
  89
  90
  91 static uint32_t cuid = 0;
  92 static noncelist_t nonces[256];
  93 static uint8_t best_first_bytes[256];
  94 static uint16_t first_byte_Sum = 0;
  95 static uint16_t first_byte_num = 0;
  96 static uint16_t num_good_first_bytes = 0;
  97 static uint64_t maximum_states = 0;
  98 static uint64_t known_target_key;
  99 static bool write_stats = false;
 100 static FILE *fstats = NULL;
 101
 102
 103 typedef enum {
 104         EVEN_STATE = 0,
 105         ODD_STATE = 1
 106 } odd_even_t;
 107
 108 #define STATELIST_INDEX_WIDTH 16
 109 #define STATELIST_INDEX_SIZE (1<<STATELIST_INDEX_WIDTH)
 110
 111 typedef struct {
 112         uint32_t *states[2];
 113         uint32_t len[2];
 114         uint32_t *index[2][STATELIST_INDEX_SIZE];
 115 } partial_indexed_statelist_t;
 116
 117 typedef struct {
 118         uint32_t *states[2];
 119         uint32_t len[2];
 120         void* next;
 121 } statelist_t;
 122
 123
 124 static partial_indexed_statelist_t partial_statelist[17];
 125 static partial_indexed_statelist_t statelist_bitflip;
 126
 127 static statelist_t *candidates = NULL;
 128
 129
 130 static int add_nonce(uint32_t nonce_enc, uint8_t par_enc)
 131 {
 132         uint8_t first_byte = nonce_enc >> 24;
 133         noncelistentry_t *p1 = nonces[first_byte].first;
 134         noncelistentry_t *p2 = NULL;
 135
 136         if (p1 == NULL) {                       // first nonce with this 1st byte
 137                 first_byte_num++;
 138                 first_byte_Sum += evenparity32((nonce_enc & 0xff000000) | (par_enc & 0x08));
 139                 // printf("Adding nonce 0x%08x, par_enc 0x%02x, parity(0x%08x) = %d\n",
 140                         // nonce_enc,
 141                         // par_enc,
 142                         // (nonce_enc & 0xff000000) | (par_enc & 0x08) |0x01,
 143                         // parity((nonce_enc & 0xff000000) | (par_enc & 0x08));
 144         }
 145
 146         while (p1 != NULL && (p1->nonce_enc & 0x00ff0000) < (nonce_enc & 0x00ff0000)) {
 147                 p2 = p1;
 148                 p1 = p1->next;
 149         }
 150
 151         if (p1 == NULL) {                                                                                                                                       // need to add at the end of the list
 152                 if (p2 == NULL) {                       // list is empty yet. Add first entry.
 153                         p2 = nonces[first_byte].first = malloc(sizeof(noncelistentry_t));
 154                 } else {                                        // add new entry at end of existing list.
 155                         p2 = p2->next = malloc(sizeof(noncelistentry_t));
 156                 }
 157         } else if ((p1->nonce_enc & 0x00ff0000) != (nonce_enc & 0x00ff0000)) {                          // found distinct 2nd byte. Need to insert.
 158                 if (p2 == NULL) {                       // need to insert at start of list
 159                         p2 = nonces[first_byte].first = malloc(sizeof(noncelistentry_t));
 160                 } else {
 161                         p2 = p2->next = malloc(sizeof(noncelistentry_t));
 162                 }
 163         } else {                                                                                        // we have seen this 2nd byte before. Nothing to add or insert.
 164                 return (0);
 165         }
 166
 167         // add or insert new data
 168         p2->next = p1;
 169         p2->nonce_enc = nonce_enc;
 170         p2->par_enc = par_enc;
 171
 172         nonces[first_byte].num++;
 173         nonces[first_byte].Sum += evenparity32((nonce_enc & 0x00ff0000) | (par_enc & 0x04));
 174         nonces[first_byte].updated = true;   // indicates that we need to recalculate the Sum(a8) probability for this first byte
 175
 176         return (1);                             // new nonce added
 177 }
 178
 179
 180 static void init_nonce_memory(void)
 181 {
 182         for (uint16_t i = 0; i < 256; i++) {
 183                 nonces[i].num = 0;
 184                 nonces[i].Sum = 0;
 185                 nonces[i].Sum8_guess = 0;
 186                 nonces[i].Sum8_prob = 0.0;
 187                 nonces[i].updated = true;
 188                 nonces[i].first = NULL;
 189         }
 190         first_byte_num = 0;
 191         first_byte_Sum = 0;
 192         num_good_first_bytes = 0;
 193 }
 194
 195
 196 static void free_nonce_list(noncelistentry_t *p)
 197 {
 198         if (p == NULL) {
 199                 return;
 200         } else {
 201                 free_nonce_list(p->next);
 202                 free(p);
 203         }
 204 }
 205
 206
 207 static void free_nonces_memory(void)
 208 {
 209         for (uint16_t i = 0; i < 256; i++) {
 210                 free_nonce_list(nonces[i].first);
 211         }
 212 }
 213
 214
 215 static uint16_t PartialSumProperty(uint32_t state, odd_even_t odd_even)
 216 {
 217         uint16_t sum = 0;
 218         for (uint16_t j = 0; j < 16; j++) {
 219                 uint32_t st = state;
 220                 uint16_t part_sum = 0;
 221                 if (odd_even == ODD_STATE) {
 222                         for (uint16_t i = 0; i < 5; i++) {
 223                                 part_sum ^= filter(st);
 224                                 st = (st << 1) | ((j >> (3-i)) & 0x01) ;
 225                         }
 226                         part_sum ^= 1;          // XOR 1 cancelled out for the other 8 bits
 227                 } else {
 228                         for (uint16_t i = 0; i < 4; i++) {
 229                                 st = (st << 1) | ((j >> (3-i)) & 0x01) ;
 230                                 part_sum ^= filter(st);
 231                         }
 232                 }
 233                 sum += part_sum;
 234         }
 235         return sum;
 236 }
 237
 238
 239 // static uint16_t SumProperty(struct Crypto1State *s)
 240 // {
 241         // uint16_t sum_odd = PartialSumProperty(s->odd, ODD_STATE);
 242         // uint16_t sum_even = PartialSumProperty(s->even, EVEN_STATE);
 243         // return (sum_odd*(16-sum_even) + (16-sum_odd)*sum_even);
 244 // }
 245
 246
 247 static double p_hypergeometric(uint16_t N, uint16_t K, uint16_t n, uint16_t k)
 248 {
 249         // for efficient computation we are using the recursive definition
 250         //                                              (K-k+1) * (n-k+1)
 251         // P(X=k) = P(X=k-1) * --------------------
 252         //                                                 k * (N-K-n+k)
 253         // and
 254         //           (N-K)*(N-K-1)*...*(N-K-n+1)
 255         // P(X=0) = -----------------------------
 256         //               N*(N-1)*...*(N-n+1)
 257
 258         if (n-k > N-K || k > K) return 0.0;     // avoids log(x<=0) in calculation below
 259         if (k == 0) {
 260                 // use logarithms to avoid overflow with huge factorials (double type can only hold 170!)
 261                 double log_result = 0.0;
 262                 for (int16_t i = N-K; i >= N-K-n+1; i--) {
 263                         log_result += log(i);
 264                 }
 265                 for (int16_t i = N; i >= N-n+1; i--) {
 266                         log_result -= log(i);
 267                 }
 268                 return exp(log_result);
 269         } else {
 270                 if (n-k == N-K) {       // special case. The published recursion below would fail with a divide by zero exception
 271                         double log_result = 0.0;
 272                         for (int16_t i = k+1; i <= n; i++) {
 273                                 log_result += log(i);
 274                         }
 275                         for (int16_t i = K+1; i <= N; i++) {
 276                                 log_result -= log(i);
 277                         }
 278                         return exp(log_result);
 279                 } else {                        // recursion
 280                         return (p_hypergeometric(N, K, n, k-1) * (K-k+1) * (n-k+1) / (k * (N-K-n+k)));
 281                 }
 282         }
 283 }
 284
 285
 286 static float sum_probability(uint16_t K, uint16_t n, uint16_t k)
 287 {
 288         const uint16_t N = 256;
 289
 290         if (k > K || p_K[K] == 0.0) return 0.0;
 291
 292         double p_T_is_k_when_S_is_K = p_hypergeometric(N, K, n, k);
 293         double p_S_is_K = p_K[K];
 294         double p_T_is_k = 0;
 295         for (uint16_t i = 0; i <= 256; i++) {
 296                 if (p_K[i] != 0.0) {
 297                         p_T_is_k += p_K[i] * p_hypergeometric(N, i, n, k);
 298                 }
 299         }
 300         return(p_T_is_k_when_S_is_K * p_S_is_K / p_T_is_k);
 301 }
 302
 303
 304
 305
 306 static inline uint_fast8_t common_bits(uint_fast8_t bytes_diff)
 307 {
 308         static const uint_fast8_t common_bits_LUT[256] = {
 309                 8, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
 310                 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
 311                 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
 312                 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
 313                 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
 314                 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
 315                 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
 316                 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
 317                 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
 318                 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
 319                 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
 320                 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
 321                 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
 322                 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
 323                 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
 324                 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
 325         };
 326
 327         return common_bits_LUT[bytes_diff];
 328 }
 329
 330
 331 static void Tests()
 332 {
 333         // printf("Tests: Partial Statelist sizes\n");
 334         // for (uint16_t i = 0; i <= 16; i+=2) {
 335                 // printf("Partial State List Odd [%2d] has %8d entries\n", i, partial_statelist[i].len[ODD_STATE]);
 336         // }
 337         // for (uint16_t i = 0; i <= 16; i+=2) {
 338                 // printf("Partial State List Even      [%2d] has %8d entries\n", i, partial_statelist[i].len[EVEN_STATE]);
 339         // }
 340
 341         // #define NUM_STATISTICS 100000
 342         // uint32_t statistics_odd[17];
 343         // uint64_t statistics[257];
 344         // uint32_t statistics_even[17];
 345         // struct Crypto1State cs;
 346         // time_t time1 = clock();
 347
 348         // for (uint16_t i = 0; i < 257; i++) {
 349                 // statistics[i] = 0;
 350         // }
 351         // for (uint16_t i = 0; i < 17; i++) {
 352                 // statistics_odd[i] = 0;
 353                 // statistics_even[i] = 0;
 354         // }
 355
 356         // for (uint64_t i = 0; i < NUM_STATISTICS; i++) {
 357                 // cs.odd = (rand() & 0xfff) << 12 | (rand() & 0xfff);
 358                 // cs.even = (rand() & 0xfff) << 12 | (rand() & 0xfff);
 359                 // uint16_t sum_property = SumProperty(&cs);
 360                 // statistics[sum_property] += 1;
 361                 // sum_property = PartialSumProperty(cs.even, EVEN_STATE);
 362                 // statistics_even[sum_property]++;
 363                 // sum_property = PartialSumProperty(cs.odd, ODD_STATE);
 364                 // statistics_odd[sum_property]++;
 365                 // if (i%(NUM_STATISTICS/100) == 0) printf(".");
 366         // }
 367
 368         // printf("\nTests: Calculated %d Sum properties in %0.3f seconds (%0.0f calcs/second)\n", NUM_STATISTICS, ((float)clock() - time1)/CLOCKS_PER_SEC, NUM_STATISTICS/((float)clock() - time1)*CLOCKS_PER_SEC);
 369         // for (uint16_t i = 0; i < 257; i++) {
 370                 // if (statistics[i] != 0) {
 371                         // printf("probability[%3d] = %0.5f\n", i, (float)statistics[i]/NUM_STATISTICS);
 372                 // }
 373         // }
 374         // for (uint16_t i = 0; i <= 16; i++) {
 375                 // if (statistics_odd[i] != 0) {
 376                         // printf("probability odd [%2d] = %0.5f\n", i, (float)statistics_odd[i]/NUM_STATISTICS);
 377                 // }
 378         // }
 379         // for (uint16_t i = 0; i <= 16; i++) {
 380                 // if (statistics_odd[i] != 0) {
 381                         // printf("probability even [%2d] = %0.5f\n", i, (float)statistics_even[i]/NUM_STATISTICS);
 382                 // }
 383         // }
 384
 385         // printf("Tests: Sum Probabilities based on Partial Sums\n");
 386         // for (uint16_t i = 0; i < 257; i++) {
 387                 // statistics[i] = 0;
 388         // }
 389         // uint64_t num_states = 0;
 390         // for (uint16_t oddsum = 0; oddsum <= 16; oddsum += 2) {
 391                 // for (uint16_t evensum = 0; evensum <= 16; evensum += 2) {
 392                         // uint16_t sum = oddsum*(16-evensum) + (16-oddsum)*evensum;
 393                         // statistics[sum] += (uint64_t)partial_statelist[oddsum].len[ODD_STATE] * partial_statelist[evensum].len[EVEN_STATE] * (1<<8);
 394                         // num_states += (uint64_t)partial_statelist[oddsum].len[ODD_STATE] * partial_statelist[evensum].len[EVEN_STATE] * (1<<8);
 395                 // }
 396         // }
 397         // printf("num_states = %lld, expected %lld\n", num_states, (1LL<<48));
 398         // for (uint16_t i = 0; i < 257; i++) {
 399                 // if (statistics[i] != 0) {
 400                         // printf("probability[%3d] = %0.5f\n", i, (float)statistics[i]/num_states);
 401                 // }
 402         // }
 403
 404         // printf("\nTests: Hypergeometric Probability for selected parameters\n");
 405         // printf("p_hypergeometric(256, 206, 255, 206) = %0.8f\n", p_hypergeometric(256, 206, 255, 206));
 406         // printf("p_hypergeometric(256, 206, 255, 205) = %0.8f\n", p_hypergeometric(256, 206, 255, 205));
 407         // printf("p_hypergeometric(256, 156, 1, 1) = %0.8f\n", p_hypergeometric(256, 156, 1, 1));
 408         // printf("p_hypergeometric(256, 156, 1, 0) = %0.8f\n", p_hypergeometric(256, 156, 1, 0));
 409         // printf("p_hypergeometric(256, 1, 1, 1) = %0.8f\n", p_hypergeometric(256, 1, 1, 1));
 410         // printf("p_hypergeometric(256, 1, 1, 0) = %0.8f\n", p_hypergeometric(256, 1, 1, 0));
 411
 412         // struct Crypto1State *pcs;
 413         // pcs = crypto1_create(0xffffffffffff);
 414         // printf("\nTests: for key = 0xffffffffffff:\nSum(a0) = %d\nodd_state =  0x%06x\neven_state = 0x%06x\n",
 415                 // SumProperty(pcs), pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff);
 416         // crypto1_byte(pcs, (cuid >> 24) ^ best_first_bytes[0], true);
 417         // printf("After adding best first byte 0x%02x:\nSum(a8) = %d\nodd_state =  0x%06x\neven_state = 0x%06x\n",
 418                 // best_first_bytes[0],
 419                 // SumProperty(pcs),
 420                 // pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff);
 421         // //test_state_odd = pcs->odd & 0x00ffffff;
 422         // //test_state_even = pcs->even & 0x00ffffff;
 423         // crypto1_destroy(pcs);
 424         // pcs = crypto1_create(0xa0a1a2a3a4a5);
 425         // printf("Tests: for key = 0xa0a1a2a3a4a5:\nSum(a0) = %d\nodd_state =  0x%06x\neven_state = 0x%06x\n",
 426                 // SumProperty(pcs), pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff);
 427         // crypto1_byte(pcs, (cuid >> 24) ^ best_first_bytes[0], true);
 428         // printf("After adding best first byte 0x%02x:\nSum(a8) = %d\nodd_state =  0x%06x\neven_state = 0x%06x\n",
 429                 // best_first_bytes[0],
 430                 // SumProperty(pcs),
 431                 // pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff);
 432         // //test_state_odd = pcs->odd & 0x00ffffff;
 433         // //test_state_even = pcs->even & 0x00ffffff;
 434         // crypto1_destroy(pcs);
 435         // pcs = crypto1_create(0xa6b9aa97b955);
 436         // printf("Tests: for key = 0xa6b9aa97b955:\nSum(a0) = %d\nodd_state =  0x%06x\neven_state = 0x%06x\n",
 437                 // SumProperty(pcs), pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff);
 438         // crypto1_byte(pcs, (cuid >> 24) ^ best_first_bytes[0], true);
 439         // printf("After adding best first byte 0x%02x:\nSum(a8) = %d\nodd_state =  0x%06x\neven_state = 0x%06x\n",
 440                 // best_first_bytes[0],
 441                 // SumProperty(pcs),
 442                 // pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff);
 443         //test_state_odd = pcs->odd & 0x00ffffff;
 444         //test_state_even = pcs->even & 0x00ffffff;
 445         // crypto1_destroy(pcs);
 446
 447
 448
 449         // printf("\nTests: number of states with BitFlipProperty: %d, (= %1.3f%% of total states)\n", statelist_bitflip.len[0], 100.0 * statelist_bitflip.len[0] / (1<<20));
 450
 451         printf("\nTests: Actual BitFlipProperties odd/even:\n");
 452         for (uint16_t i = 0; i < 256; i++) {
 453                 printf("[%02x]:%c  ", i, nonces[i].BitFlip[ODD_STATE]?'o':nonces[i].BitFlip[EVEN_STATE]?'e':' ');
 454                 if (i % 8 == 7) {
 455                         printf("\n");
 456                 }
 457         }
 458
 459         printf("\nTests: Sorted First Bytes:\n");
 460         for (uint16_t i = 0; i < 256; i++) {
 461                 uint8_t best_byte = best_first_bytes[i];
 462                 printf("#%03d Byte: %02x, n = %3d, k = %3d, Sum(a8): %3d, Confidence: %5.1f%%, Bitflip: %c\n",
 463                 //printf("#%03d Byte: %02x, n = %3d, k = %3d, Sum(a8): %3d, Confidence: %5.1f%%, Bitflip: %c, score1: %1.5f, score2: %1.0f\n",
 464                         i, best_byte,
 465                         nonces[best_byte].num,
 466                         nonces[best_byte].Sum,
 467                         nonces[best_byte].Sum8_guess,
 468                         nonces[best_byte].Sum8_prob * 100,
 469                         nonces[best_byte].BitFlip[ODD_STATE]?'o':nonces[best_byte].BitFlip[EVEN_STATE]?'e':' '
 470                         //nonces[best_byte].score1,
 471                         //nonces[best_byte].score2
 472                         );
 473         }
 474
 475         // printf("\nTests: parity performance\n");
 476         // time_t time1p = clock();
 477         // uint32_t par_sum = 0;
 478         // for (uint32_t i = 0; i < 100000000; i++) {
 479                 // par_sum += parity(i);
 480         // }
 481         // printf("parsum oldparity = %d, time = %1.5fsec\n", par_sum, (float)(clock() - time1p)/CLOCKS_PER_SEC);
 482
 483         // time1p = clock();
 484         // par_sum = 0;
 485         // for (uint32_t i = 0; i < 100000000; i++) {
 486                 // par_sum += evenparity32(i);
 487         // }
 488         // printf("parsum newparity = %d, time = %1.5fsec\n", par_sum, (float)(clock() - time1p)/CLOCKS_PER_SEC);
 489
 490
 491 }
 492
 493
 494 static void sort_best_first_bytes(void)
 495 {
 496         // sort based on probability for correct guess
 497         for (uint16_t i = 0; i < 256; i++ ) {
 498                 uint16_t j = 0;
 499                 float prob1 = nonces[i].Sum8_prob;
 500                 float prob2 = nonces[best_first_bytes[0]].Sum8_prob;
 501                 while (prob1 < prob2 && j < i) {
 502                         prob2 = nonces[best_first_bytes[++j]].Sum8_prob;
 503                 }
 504                 if (j < i) {
 505                         for (uint16_t k = i; k > j; k--) {
 506                                 best_first_bytes[k] = best_first_bytes[k-1];
 507                         }
 508                 }
 509                         best_first_bytes[j] = i;
 510                 }
 511
 512         // determine how many are above the CONFIDENCE_THRESHOLD
 513         uint16_t num_good_nonces = 0;
 514         for (uint16_t i = 0; i < 256; i++) {
 515                 if (nonces[best_first_bytes[i]].Sum8_prob >= CONFIDENCE_THRESHOLD) {
 516                         ++num_good_nonces;
 517                 }
 518         }
 519
 520         uint16_t best_first_byte = 0;
 521
 522         // select the best possible first byte based on number of common bits with all {b'}
 523         // uint16_t max_common_bits = 0;
 524         // for (uint16_t i = 0; i < num_good_nonces; i++) {
 525                 // uint16_t sum_common_bits = 0;
 526                 // for (uint16_t j = 0; j < num_good_nonces; j++) {
 527                         // if (i != j) {
 528                                 // sum_common_bits += common_bits(best_first_bytes[i],best_first_bytes[j]);
 529                         // }
 530                 // }
 531                 // if (sum_common_bits > max_common_bits) {
 532                         // max_common_bits = sum_common_bits;
 533                         // best_first_byte = i;
 534                 // }
 535         // }
 536
 537         // select best possible first byte {b} based on least likely sum/bitflip property
 538         float min_p_K = 1.0;
 539         for (uint16_t i = 0; i < num_good_nonces; i++ ) {
 540                 uint16_t sum8 = nonces[best_first_bytes[i]].Sum8_guess;
 541                 float bitflip_prob = 1.0;
 542                 if (nonces[best_first_bytes[i]].BitFlip[ODD_STATE] || nonces[best_first_bytes[i]].BitFlip[EVEN_STATE]) {
 543                         bitflip_prob = 0.09375;
 544                 }
 545                 nonces[best_first_bytes[i]].score1 = p_K[sum8] * bitflip_prob;
 546                 if (p_K[sum8] * bitflip_prob <= min_p_K) {
 547                         min_p_K = p_K[sum8] * bitflip_prob;
 548                 }
 549         }
 550
 551
 552         // use number of commmon bits as a tie breaker
 553         uint16_t max_common_bits = 0;
 554         for (uint16_t i = 0; i < num_good_nonces; i++) {
 555                 float bitflip_prob = 1.0;
 556                 if (nonces[best_first_bytes[i]].BitFlip[ODD_STATE] || nonces[best_first_bytes[i]].BitFlip[EVEN_STATE]) {
 557                         bitflip_prob = 0.09375;
 558                 }
 559                 if (p_K[nonces[best_first_bytes[i]].Sum8_guess] * bitflip_prob == min_p_K) {
 560                         uint16_t sum_common_bits = 0;
 561                         for (uint16_t j = 0; j < num_good_nonces; j++) {
 562                                 sum_common_bits += common_bits(best_first_bytes[i] ^ best_first_bytes[j]);
 563                         }
 564                         nonces[best_first_bytes[i]].score2 = sum_common_bits;
 565                         if (sum_common_bits > max_common_bits) {
 566                                 max_common_bits = sum_common_bits;
 567                                 best_first_byte = i;
 568                         }
 569                 }
 570         }
 571
 572         // swap best possible first byte to the pole position
 573         uint16_t temp = best_first_bytes[0];
 574         best_first_bytes[0] = best_first_bytes[best_first_byte];
 575         best_first_bytes[best_first_byte] = temp;
 576
 577 }
 578
 579
 580 static uint16_t estimate_second_byte_sum(void)
 581 {
 582
 583         for (uint16_t first_byte = 0; first_byte < 256; first_byte++) {
 584                 float Sum8_prob = 0.0;
 585                 uint16_t Sum8 = 0;
 586                 if (nonces[first_byte].updated) {
 587                         for (uint16_t sum = 0; sum <= 256; sum++) {
 588                                 float prob = sum_probability(sum, nonces[first_byte].num, nonces[first_byte].Sum);
 589                                 if (prob > Sum8_prob) {
 590                                         Sum8_prob = prob;
 591                                         Sum8 = sum;
 592                                 }
 593                         }
 594                         nonces[first_byte].Sum8_guess = Sum8;
 595                         nonces[first_byte].Sum8_prob = Sum8_prob;
 596                         nonces[first_byte].updated = false;
 597                 }
 598         }
 599
 600         sort_best_first_bytes();
 601
 602         uint16_t num_good_nonces = 0;
 603         for (uint16_t i = 0; i < 256; i++) {
 604                 if (nonces[best_first_bytes[i]].Sum8_prob >= CONFIDENCE_THRESHOLD) {
 605                         ++num_good_nonces;
 606                 }
 607         }
 608
 609         return num_good_nonces;
 610 }
 611
 612
 613 static int read_nonce_file(void)
 614 {
 615         FILE *fnonces = NULL;
 616         uint8_t trgBlockNo;
 617         uint8_t trgKeyType;
 618         uint8_t read_buf[9];
 619         uint32_t nt_enc1, nt_enc2;
 620         uint8_t par_enc;
 621         int total_num_nonces = 0;
 622
 623         if ((fnonces = fopen("nonces.bin","rb")) == NULL) {
 624                 PrintAndLog("Could not open file nonces.bin");
 625                 return 1;
 626         }
 627
 628         PrintAndLog("Reading nonces from file nonces.bin...");
 629         size_t bytes_read = fread(read_buf, 1, 6, fnonces);
 630         if ( bytes_read == 0) {
 631                 PrintAndLog("File reading error.");
 632                 fclose(fnonces);
 633                 return 1;
 634         }
 635         cuid = bytes_to_num(read_buf, 4);
 636         trgBlockNo = bytes_to_num(read_buf+4, 1);
 637         trgKeyType = bytes_to_num(read_buf+5, 1);
 638
 639         while (fread(read_buf, 1, 9, fnonces) == 9) {
 640                 nt_enc1 = bytes_to_num(read_buf, 4);
 641                 nt_enc2 = bytes_to_num(read_buf+4, 4);
 642                 par_enc = bytes_to_num(read_buf+8, 1);
 643                 //printf("Encrypted nonce: %08x, encrypted_parity: %02x\n", nt_enc1, par_enc >> 4);
 644                 //printf("Encrypted nonce: %08x, encrypted_parity: %02x\n", nt_enc2, par_enc & 0x0f);
 645                 add_nonce(nt_enc1, par_enc >> 4);
 646                 add_nonce(nt_enc2, par_enc & 0x0f);
 647                 total_num_nonces += 2;
 648         }
 649         fclose(fnonces);
 650         PrintAndLog("Read %d nonces from file. cuid=%08x, Block=%d, Keytype=%c", total_num_nonces, cuid, trgBlockNo, trgKeyType==0?'A':'B');
 651
 652         return 0;
 653 }
 654
 655
 656 static void Check_for_FilterFlipProperties(void)
 657 {
 658         printf("Checking for Filter Flip Properties...\n");
 659
 660         uint16_t num_bitflips = 0;
 661
 662         for (uint16_t i = 0; i < 256; i++) {
 663                 nonces[i].BitFlip[ODD_STATE] = false;
 664                 nonces[i].BitFlip[EVEN_STATE] = false;
 665         }
 666
 667         for (uint16_t i = 0; i < 256; i++) {
 668                 uint8_t parity1 = (nonces[i].first->par_enc) >> 3;                              // parity of first byte
 669                 uint8_t parity2_odd = (nonces[i^0x80].first->par_enc) >> 3;     // XOR 0x80 = last bit flipped
 670                 uint8_t parity2_even = (nonces[i^0x40].first->par_enc) >> 3;    // XOR 0x40 = second last bit flipped
 671
 672                 if (parity1 == parity2_odd) {                           // has Bit Flip Property for odd bits
 673                         nonces[i].BitFlip[ODD_STATE] = true;
 674                         num_bitflips++;
 675                 } else if (parity1 == parity2_even) {           // has Bit Flip Property for even bits
 676                         nonces[i].BitFlip[EVEN_STATE] = true;
 677                         num_bitflips++;
 678                 }
 679         }
 680
 681         if (write_stats) {
 682                 fprintf(fstats, "%d;", num_bitflips);
 683         }
 684 }
 685
 686
 687 static void simulate_MFplus_RNG(uint32_t test_cuid, uint64_t test_key, uint32_t *nt_enc, uint8_t *par_enc)
 688 {
 689         struct Crypto1State sim_cs;
 690         sim_cs.odd = sim_cs.even = 0;
 691
 692         // init cryptostate with key:
 693         for(int8_t i = 47; i > 0; i -= 2) {
 694                 sim_cs.odd  = sim_cs.odd  << 1 | BIT(test_key, (i - 1) ^ 7);
 695                 sim_cs.even = sim_cs.even << 1 | BIT(test_key, i ^ 7);
 696         }
 697
 698         *par_enc = 0;
 699         uint32_t nt = (rand() & 0xff) << 24 | (rand() & 0xff) << 16 | (rand() & 0xff) << 8 | (rand() & 0xff);
 700         for (int8_t byte_pos = 3; byte_pos >= 0; byte_pos--) {
 701                 uint8_t nt_byte_dec = (nt >> (8*byte_pos)) & 0xff;
 702                 uint8_t nt_byte_enc = crypto1_byte(&sim_cs, nt_byte_dec ^ (test_cuid >> (8*byte_pos)), false) ^ nt_byte_dec;    // encode the nonce byte
 703                 *nt_enc = (*nt_enc << 8) | nt_byte_enc;
 704                 uint8_t ks_par = filter(sim_cs.odd);                                                                                    // the keystream bit to encode/decode the parity bit
 705                 uint8_t nt_byte_par_enc = ks_par ^ oddparity8(nt_byte_dec);                                             // determine the nt byte's parity and encode it
 706                 *par_enc = (*par_enc << 1) | nt_byte_par_enc;
 707         }
 708
 709 }
 710
 711
 712 static void simulate_acquire_nonces()
 713 {
 714         clock_t time1 = clock();
 715         bool filter_flip_checked = false;
 716         uint32_t total_num_nonces = 0;
 717         uint32_t next_fivehundred = 500;
 718         uint32_t total_added_nonces = 0;
 719
 720         cuid = (rand() & 0xff) << 24 | (rand() & 0xff) << 16 | (rand() & 0xff) << 8 | (rand() & 0xff);
 721         known_target_key = ((uint64_t)rand() & 0xfff) << 36 | ((uint64_t)rand() & 0xfff) << 24 | ((uint64_t)rand() & 0xfff) << 12 | ((uint64_t)rand() & 0xfff);
 722
 723         printf("Simulating nonce acquisition for target key %012"llx", cuid %08x ...\n", known_target_key, cuid);
 724         fprintf(fstats, "%012"llx";%08x;", known_target_key, cuid);
 725
 726         do {
 727                 uint32_t nt_enc = 0;
 728                 uint8_t par_enc = 0;
 729
 730                 simulate_MFplus_RNG(cuid, known_target_key, &nt_enc, &par_enc);
 731                 //printf("Simulated RNG: nt_enc1: %08x, nt_enc2: %08x, par_enc: %02x\n", nt_enc1, nt_enc2, par_enc);
 732                 total_added_nonces += add_nonce(nt_enc, par_enc);
 733                 total_num_nonces++;
 734
 735                 if (first_byte_num == 256 ) {
 736                         // printf("first_byte_num = %d, first_byte_Sum = %d\n", first_byte_num, first_byte_Sum);
 737                         if (!filter_flip_checked) {
 738                                 Check_for_FilterFlipProperties();
 739                                 filter_flip_checked = true;
 740                         }
 741                         num_good_first_bytes = estimate_second_byte_sum();
 742                         if (total_num_nonces > next_fivehundred) {
 743                                 next_fivehundred = (total_num_nonces/500+1) * 500;
 744                                 printf("Acquired %5d nonces (%5d with distinct bytes 0 and 1). Number of bytes with probability for correctly guessed Sum(a8) > %1.1f%%: %d\n",
 745                                         total_num_nonces,
 746                                         total_added_nonces,
 747                                         CONFIDENCE_THRESHOLD * 100.0,
 748                                         num_good_first_bytes);
 749                         }
 750                 }
 751
 752         } while (num_good_first_bytes < GOOD_BYTES_REQUIRED);
 753
 754         time1 = clock() - time1;
 755         if ( time1 > 0 ) {
 756         PrintAndLog("Acquired a total of %d nonces in %1.1f seconds (%0.0f nonces/minute)",
 757                 total_num_nonces,
 758                 ((float)time1)/CLOCKS_PER_SEC,
 759                 total_num_nonces * 60.0 * CLOCKS_PER_SEC/(float)time1);
 760         }
 761         fprintf(fstats, "%d;%d;%d;%1.2f;", total_num_nonces, total_added_nonces, num_good_first_bytes, CONFIDENCE_THRESHOLD);
 762
 763 }
 764
 765
 766 static int acquire_nonces(uint8_t blockNo, uint8_t keyType, uint8_t *key, uint8_t trgBlockNo, uint8_t trgKeyType, bool nonce_file_write, bool slow)
 767 {
 768         clock_t time1 = clock();
 769         bool initialize = true;
 770         bool field_off = false;
 771         bool finished = false;
 772         bool filter_flip_checked = false;
 773         uint32_t flags = 0;
 774         uint8_t write_buf[9];
 775         uint32_t total_num_nonces = 0;
 776         uint32_t next_fivehundred = 500;
 777         uint32_t total_added_nonces = 0;
 778         FILE *fnonces = NULL;
 779         UsbCommand resp;
 780
 781         printf("Acquiring nonces...\n");
 782
 783         clearCommandBuffer();
 784
 785         do {
 786                 flags = 0;
 787                 flags |= initialize ? 0x0001 : 0;
 788                 flags |= slow ? 0x0002 : 0;
 789                 flags |= field_off ? 0x0004 : 0;
 790                 UsbCommand c = {CMD_MIFARE_ACQUIRE_ENCRYPTED_NONCES, {blockNo + keyType * 0x100, trgBlockNo + trgKeyType * 0x100, flags}};
 791                 memcpy(c.d.asBytes, key, 6);
 792
 793                 SendCommand(&c);
 794
 795                 if (field_off) finished = true;
 796
 797                 if (initialize) {
 798                         if (!WaitForResponseTimeout(CMD_ACK, &resp, 3000)) return 1;
 799                         if (resp.arg[0]) return resp.arg[0];  // error during nested_hard
 800
 801                         cuid = resp.arg[1];
 802                         // PrintAndLog("Acquiring nonces for CUID 0x%08x", cuid);
 803                         if (nonce_file_write && fnonces == NULL) {
 804                                 if ((fnonces = fopen("nonces.bin","wb")) == NULL) {
 805                                         PrintAndLog("Could not create file nonces.bin");
 806                                         return 3;
 807                                 }
 808                                 PrintAndLog("Writing acquired nonces to binary file nonces.bin");
 809                                 num_to_bytes(cuid, 4, write_buf);
 810                                 fwrite(write_buf, 1, 4, fnonces);
 811                                 fwrite(&trgBlockNo, 1, 1, fnonces);
 812                                 fwrite(&trgKeyType, 1, 1, fnonces);
 813                         }
 814                 }
 815
 816                 if (!initialize) {
 817                         uint32_t nt_enc1, nt_enc2;
 818                         uint8_t par_enc;
 819                         uint16_t num_acquired_nonces = resp.arg[2];
 820                         uint8_t *bufp = resp.d.asBytes;
 821                         for (uint16_t i = 0; i < num_acquired_nonces; i+=2) {
 822                                 nt_enc1 = bytes_to_num(bufp, 4);
 823                                 nt_enc2 = bytes_to_num(bufp+4, 4);
 824                                 par_enc = bytes_to_num(bufp+8, 1);
 825
 826                                 //printf("Encrypted nonce: %08x, encrypted_parity: %02x\n", nt_enc1, par_enc >> 4);
 827                                 total_added_nonces += add_nonce(nt_enc1, par_enc >> 4);
 828                                 //printf("Encrypted nonce: %08x, encrypted_parity: %02x\n", nt_enc2, par_enc & 0x0f);
 829                                 total_added_nonces += add_nonce(nt_enc2, par_enc & 0x0f);
 830
 831
 832                                 if (nonce_file_write) {
 833                                         fwrite(bufp, 1, 9, fnonces);
 834                                 }
 835
 836                                 bufp += 9;
 837                         }
 838
 839                         total_num_nonces += num_acquired_nonces;
 840                 }
 841
 842                 if (first_byte_num == 256 ) {
 843                         // printf("first_byte_num = %d, first_byte_Sum = %d\n", first_byte_num, first_byte_Sum);
 844                         if (!filter_flip_checked) {
 845                                 Check_for_FilterFlipProperties();
 846                                 filter_flip_checked = true;
 847                         }
 848                         num_good_first_bytes = estimate_second_byte_sum();
 849                         if (total_num_nonces > next_fivehundred) {
 850                                 next_fivehundred = (total_num_nonces/500+1) * 500;
 851                                 printf("Acquired %5d nonces (%5d with distinct bytes 0 and 1). Number of bytes with probability for correctly guessed Sum(a8) > %1.1f%%: %d\n",
 852                                         total_num_nonces,
 853                                         total_added_nonces,
 854                                         CONFIDENCE_THRESHOLD * 100.0,
 855                                         num_good_first_bytes);
 856                         }
 857                         if (num_good_first_bytes >= GOOD_BYTES_REQUIRED) {
 858                                 field_off = true;       // switch off field with next SendCommand and then finish
 859                         }
 860                 }
 861
 862                 if (!initialize) {
 863                         if (!WaitForResponseTimeout(CMD_ACK, &resp, 3000)) {
 864                                 fclose(fnonces);
 865                                 return 1;
 866                         }
 867                         if (resp.arg[0]) {
 868                                 fclose(fnonces);
 869                                 return resp.arg[0];  // error during nested_hard
 870                         }
 871                 }
 872
 873                 initialize = false;
 874
 875         } while (!finished);
 876
 877
 878         if (nonce_file_write) {
 879                 fclose(fnonces);
 880         }
 881
 882         time1 = clock() - time1;
 883         if ( time1 > 0 ) {
 884         PrintAndLog("Acquired a total of %d nonces in %1.1f seconds (%0.0f nonces/minute)",
 885                 total_num_nonces,
 886                 ((float)time1)/CLOCKS_PER_SEC,
 887                 total_num_nonces * 60.0 * CLOCKS_PER_SEC/(float)time1
 888                 );
 889         }
 890         return 0;
 891 }
 892
 893
 894 static int init_partial_statelists(void)
 895 {
 896         const uint32_t sizes_odd[17] = { 126757, 0, 18387, 0, 74241, 0, 181737, 0, 248801, 0, 182033, 0, 73421, 0, 17607, 0, 125601 };
 897         const uint32_t sizes_even[17] = { 125723, 0, 17867, 0, 74305, 0, 178707, 0, 248801, 0, 185063, 0, 73356, 0, 18127, 0, 126634 };
 898
 899         printf("Allocating memory for partial statelists...\n");
 900         for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) {
 901                 for (uint16_t i = 0; i <= 16; i+=2) {
 902                         partial_statelist[i].len[odd_even] = 0;
 903                         uint32_t num_of_states = odd_even == ODD_STATE ? sizes_odd[i] : sizes_even[i];
 904                         partial_statelist[i].states[odd_even] = malloc(sizeof(uint32_t) * num_of_states);
 905                         if (partial_statelist[i].states[odd_even] == NULL) {
 906                                 PrintAndLog("Cannot allocate enough memory. Aborting");
 907                                 return 4;
 908                         }
 909                         for (uint32_t j = 0; j < STATELIST_INDEX_SIZE; j++) {
 910                                 partial_statelist[i].index[odd_even][j] = NULL;
 911                         }
 912                 }
 913         }
 914
 915         printf("Generating partial statelists...\n");
 916         for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) {
 917                 uint32_t index = -1;
 918                 uint32_t num_of_states = 1<<20;
 919                 for (uint32_t state = 0; state < num_of_states; state++) {
 920                         uint16_t sum_property = PartialSumProperty(state, odd_even);
 921                         uint32_t *p = partial_statelist[sum_property].states[odd_even];
 922                         p += partial_statelist[sum_property].len[odd_even];
 923                         *p = state;
 924                         partial_statelist[sum_property].len[odd_even]++;
 925                         uint32_t index_mask = (STATELIST_INDEX_SIZE-1) << (20-STATELIST_INDEX_WIDTH);
 926                         if ((state & index_mask) != index) {
 927                                 index = state & index_mask;
 928                         }
 929                         if (partial_statelist[sum_property].index[odd_even][index >> (20-STATELIST_INDEX_WIDTH)] == NULL) {
 930                                 partial_statelist[sum_property].index[odd_even][index >> (20-STATELIST_INDEX_WIDTH)] = p;
 931                         }
 932                 }
 933                 // add End Of List markers
 934                 for (uint16_t i = 0; i <= 16; i += 2) {
 935                         uint32_t *p = partial_statelist[i].states[odd_even];
 936                         p += partial_statelist[i].len[odd_even];
 937                         *p = 0xffffffff;
 938                 }
 939         }
 940
 941         return 0;
 942 }
 943
 944
 945 static void init_BitFlip_statelist(void)
 946 {
 947         printf("Generating bitflip statelist...\n");
 948         uint32_t *p = statelist_bitflip.states[0] = malloc(sizeof(uint32_t) * 1<<20);
 949         uint32_t index = -1;
 950         uint32_t index_mask = (STATELIST_INDEX_SIZE-1) << (20-STATELIST_INDEX_WIDTH);
 951         for (uint32_t state = 0; state < (1 << 20); state++) {
 952                 if (filter(state) != filter(state^1)) {
 953                         if ((state & index_mask) != index) {
 954                                 index = state & index_mask;
 955                         }
 956                         if (statelist_bitflip.index[0][index >> (20-STATELIST_INDEX_WIDTH)] == NULL) {
 957                                 statelist_bitflip.index[0][index >> (20-STATELIST_INDEX_WIDTH)] = p;
 958                         }
 959                         *p++ = state;
 960                 }
 961         }
 962         // set len and add End Of List marker
 963         statelist_bitflip.len[0] = p - statelist_bitflip.states[0];
 964         *p = 0xffffffff;
 965         statelist_bitflip.states[0] = realloc(statelist_bitflip.states[0], sizeof(uint32_t) * (statelist_bitflip.len[0] + 1));
 966 }
 967
 968
 969 static inline uint32_t *find_first_state(uint32_t state, uint32_t mask, partial_indexed_statelist_t *sl, odd_even_t odd_even)
 970 {
 971         uint32_t *p = sl->index[odd_even][(state & mask) >> (20-STATELIST_INDEX_WIDTH)];                // first Bits as index
 972
 973         if (p == NULL) return NULL;
 974         while (*p < (state & mask)) p++;
 975         if (*p == 0xffffffff) return NULL;                                      // reached end of list, no match
 976         if ((*p & mask) == (state & mask)) return p;            // found a match.
 977         return NULL;                                                                            // no match
 978 }
 979
 980
 981 static inline bool /*__attribute__((always_inline))*/ invariant_holds(uint_fast8_t byte_diff, uint_fast32_t state1, uint_fast32_t state2, uint_fast8_t bit, uint_fast8_t state_bit)
 982 {
 983         uint_fast8_t j_1_bit_mask = 0x01 << (bit-1);
 984         uint_fast8_t bit_diff = byte_diff & j_1_bit_mask;                                                                               // difference of (j-1)th bit
 985         uint_fast8_t filter_diff = filter(state1 >> (4-state_bit)) ^ filter(state2 >> (4-state_bit));   // difference in filter function
 986         uint_fast8_t mask_y12_y13 = 0xc0 >> state_bit;
 987         uint_fast8_t state_bits_diff = (state1 ^ state2) & mask_y12_y13;                                                // difference in state bits 12 and 13
 988         uint_fast8_t all_diff = evenparity8(bit_diff ^ state_bits_diff ^ filter_diff);                  // use parity function to XOR all bits
 989         return !all_diff;
 990 }
 991
 992
 993 static inline bool /*__attribute__((always_inline))*/ invalid_state(uint_fast8_t byte_diff, uint_fast32_t state1, uint_fast32_t state2, uint_fast8_t bit, uint_fast8_t state_bit)
 994 {
 995         uint_fast8_t j_bit_mask = 0x01 << bit;
 996         uint_fast8_t bit_diff = byte_diff & j_bit_mask;                                                                                 // difference of jth bit
 997         uint_fast8_t mask_y13_y16 = 0x48 >> state_bit;
 998         uint_fast8_t state_bits_diff = (state1 ^ state2) & mask_y13_y16;                                                // difference in state bits 13 and 16
 999         uint_fast8_t all_diff = evenparity8(bit_diff ^ state_bits_diff);                                                // use parity function to XOR all bits
1000         return all_diff;
1001 }
1002
1003
1004 static inline bool remaining_bits_match(uint_fast8_t num_common_bits, uint_fast8_t byte_diff, uint_fast32_t state1, uint_fast32_t state2, odd_even_t odd_even)
1005 {
1006         if (odd_even) {
1007                 // odd bits
1008                 switch (num_common_bits) {
1009                         case 0: if (!invariant_holds(byte_diff, state1, state2, 1, 0)) return true;
1010                         case 1: if (invalid_state(byte_diff, state1, state2, 1, 0)) return false;
1011                         case 2: if (!invariant_holds(byte_diff, state1, state2, 3, 1)) return true;
1012                         case 3: if (invalid_state(byte_diff, state1, state2, 3, 1)) return false;
1013                         case 4: if (!invariant_holds(byte_diff, state1, state2, 5, 2)) return true;
1014                         case 5: if (invalid_state(byte_diff, state1, state2, 5, 2)) return false;
1015                         case 6: if (!invariant_holds(byte_diff, state1, state2, 7, 3)) return true;
1016                         case 7: if (invalid_state(byte_diff, state1, state2, 7, 3)) return false;
1017                 }
1018         } else {
1019                 // even bits
1020                 switch (num_common_bits) {
1021                         case 0: if (invalid_state(byte_diff, state1, state2, 0, 0)) return false;
1022                         case 1: if (!invariant_holds(byte_diff, state1, state2, 2, 1)) return true;
1023                         case 2: if (invalid_state(byte_diff, state1, state2, 2, 1)) return false;
1024                         case 3: if (!invariant_holds(byte_diff, state1, state2, 4, 2)) return true;
1025                         case 4: if (invalid_state(byte_diff, state1, state2, 4, 2)) return false;
1026                         case 5: if (!invariant_holds(byte_diff, state1, state2, 6, 3)) return true;
1027                         case 6: if (invalid_state(byte_diff, state1, state2, 6, 3)) return false;
1028                 }
1029         }
1030
1031         return true;                                    // valid state
1032 }
1033
1034
1035 static bool all_other_first_bytes_match(uint32_t state, odd_even_t odd_even)
1036 {
1037         for (uint16_t i = 1; i < num_good_first_bytes; i++) {
1038                 uint16_t sum_a8 = nonces[best_first_bytes[i]].Sum8_guess;
1039                 uint_fast8_t bytes_diff = best_first_bytes[0] ^ best_first_bytes[i];
1040                 uint_fast8_t j = common_bits(bytes_diff);
1041                 uint32_t mask = 0xfffffff0;
1042                 if (odd_even == ODD_STATE) {
1043                         mask >>= j/2;
1044                 } else {
1045                         mask >>= (j+1)/2;
1046                 }
1047                 mask &= 0x000fffff;
1048                 //printf("bytes 0x%02x and 0x%02x: %d common bits, mask = 0x%08x, state = 0x%08x, sum_a8 = %d", best_first_bytes[0], best_first_bytes[i], j, mask, state, sum_a8);
1049                 bool found_match = false;
1050                 for (uint16_t r = 0; r <= 16 && !found_match; r += 2) {
1051                         for (uint16_t s = 0; s <= 16 && !found_match; s += 2) {
1052                                 if (r*(16-s) + (16-r)*s == sum_a8) {
1053                                         //printf("Checking byte 0x%02x for partial sum (%s) %d\n", best_first_bytes[i], odd_even==ODD_STATE?"odd":"even", odd_even==ODD_STATE?r:s);
1054                                         uint16_t part_sum_a8 = (odd_even == ODD_STATE) ? r : s;
1055                                         uint32_t *p = find_first_state(state, mask, &partial_statelist[part_sum_a8], odd_even);
1056                                         if (p != NULL) {
1057                                                 while ((state & mask) == (*p & mask) && (*p != 0xffffffff)) {
1058                                                         if (remaining_bits_match(j, bytes_diff, state, (state&0x00fffff0) | *p, odd_even)) {
1059                                                                 found_match = true;
1060                                                                 // if ((odd_even == ODD_STATE && state == test_state_odd)
1061                                                                         // || (odd_even == EVEN_STATE && state == test_state_even)) {
1062                                                                         // printf("all_other_first_bytes_match(): %s test state: remaining bits matched. Bytes = %02x, %02x, Common Bits=%d, mask=0x%08x, PartSum(a8)=%d\n",
1063                                                                                 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1064                                                                 // }
1065                                                                 break;
1066                                                         } else {
1067                                                                 // if ((odd_even == ODD_STATE && state == test_state_odd)
1068                                                                         // || (odd_even == EVEN_STATE && state == test_state_even)) {
1069                                                                         // printf("all_other_first_bytes_match(): %s test state: remaining bits didn't match. Bytes = %02x, %02x, Common Bits=%d, mask=0x%08x, PartSum(a8)=%d\n",
1070                                                                                 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1071                                                                 // }
1072                                                         }
1073                                                         p++;
1074                                                 }
1075                                         } else {
1076                                                 // if ((odd_even == ODD_STATE && state == test_state_odd)
1077                                                         // || (odd_even == EVEN_STATE && state == test_state_even)) {
1078                                                         // printf("all_other_first_bytes_match(): %s test state: couldn't find a matching state. Bytes = %02x, %02x, Common Bits=%d, mask=0x%08x, PartSum(a8)=%d\n",
1079                                                                 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1080                                                 // }
1081                                         }
1082                                 }
1083                         }
1084                 }
1085
1086                 if (!found_match) {
1087                         // if ((odd_even == ODD_STATE && state == test_state_odd)
1088                                 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1089                                 // printf("all_other_first_bytes_match(): %s test state: Eliminated. Bytes = %02x, %02x, Common Bits = %d\n", odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j);
1090                         // }
1091                         return false;
1092                 }
1093         }
1094
1095         return true;
1096 }
1097
1098
1099 static bool all_bit_flips_match(uint32_t state, odd_even_t odd_even)
1100 {
1101         for (uint16_t i = 0; i < 256; i++) {
1102                 if (nonces[i].BitFlip[odd_even] && i != best_first_bytes[0]) {
1103                         uint_fast8_t bytes_diff = best_first_bytes[0] ^ i;
1104                         uint_fast8_t j = common_bits(bytes_diff);
1105                         uint32_t mask = 0xfffffff0;
1106                         if (odd_even == ODD_STATE) {
1107                                 mask >>= j/2;
1108                         } else {
1109                                 mask >>= (j+1)/2;
1110                         }
1111                         mask &= 0x000fffff;
1112                         //printf("bytes 0x%02x and 0x%02x: %d common bits, mask = 0x%08x, state = 0x%08x, sum_a8 = %d", best_first_bytes[0], best_first_bytes[i], j, mask, state, sum_a8);
1113                         bool found_match = false;
1114                         uint32_t *p = find_first_state(state, mask, &statelist_bitflip, 0);
1115                         if (p != NULL) {
1116                                 while ((state & mask) == (*p & mask) && (*p != 0xffffffff)) {
1117                                         if (remaining_bits_match(j, bytes_diff, state, (state&0x00fffff0) | *p, odd_even)) {
1118                                                 found_match = true;
1119                                                 // if ((odd_even == ODD_STATE && state == test_state_odd)
1120                                                         // || (odd_even == EVEN_STATE && state == test_state_even)) {
1121                                                         // printf("all_other_first_bytes_match(): %s test state: remaining bits matched. Bytes = %02x, %02x, Common Bits=%d, mask=0x%08x, PartSum(a8)=%d\n",
1122                                                                 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1123                                                 // }
1124                                                 break;
1125                                         } else {
1126                                                 // if ((odd_even == ODD_STATE && state == test_state_odd)
1127                                                         // || (odd_even == EVEN_STATE && state == test_state_even)) {
1128                                                         // printf("all_other_first_bytes_match(): %s test state: remaining bits didn't match. Bytes = %02x, %02x, Common Bits=%d, mask=0x%08x, PartSum(a8)=%d\n",
1129                                                                 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1130                                                 // }
1131                                         }
1132                                         p++;
1133                                 }
1134                         } else {
1135                                 // if ((odd_even == ODD_STATE && state == test_state_odd)
1136                                         // || (odd_even == EVEN_STATE && state == test_state_even)) {
1137                                         // printf("all_other_first_bytes_match(): %s test state: couldn't find a matching state. Bytes = %02x, %02x, Common Bits=%d, mask=0x%08x, PartSum(a8)=%d\n",
1138                                                 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1139                                 // }
1140                         }
1141                         if (!found_match) {
1142                                 // if ((odd_even == ODD_STATE && state == test_state_odd)
1143                                         // || (odd_even == EVEN_STATE && state == test_state_even)) {
1144                                         // printf("all_other_first_bytes_match(): %s test state: Eliminated. Bytes = %02x, %02x, Common Bits = %d\n", odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j);
1145                                 // }
1146                                 return false;
1147                         }
1148                 }
1149
1150         }
1151
1152         return true;
1153 }
1154
1155
1156 static struct sl_cache_entry {
1157         uint32_t *sl;
1158         uint32_t len;
1159         } sl_cache[17][17][2];
1160
1161
1162 static void init_statelist_cache(void)
1163 {
1164         for (uint16_t i = 0; i < 17; i+=2) {
1165                 for (uint16_t j = 0; j < 17; j+=2) {
1166                         for (uint16_t k = 0; k < 2; k++) {
1167                                 sl_cache[i][j][k].sl = NULL;
1168                                 sl_cache[i][j][k].len = 0;
1169                         }
1170                 }
1171         }
1172 }
1173
1174
1175 static int add_matching_states(statelist_t *candidates, uint16_t part_sum_a0, uint16_t part_sum_a8, odd_even_t odd_even)
1176 {
1177         uint32_t worstcase_size = 1<<20;
1178
1179         // check cache for existing results
1180         if (sl_cache[part_sum_a0][part_sum_a8][odd_even].sl != NULL) {
1181                 candidates->states[odd_even] = sl_cache[part_sum_a0][part_sum_a8][odd_even].sl;
1182                 candidates->len[odd_even] = sl_cache[part_sum_a0][part_sum_a8][odd_even].len;
1183                 return 0;
1184         }
1185
1186         candidates->states[odd_even] = (uint32_t *)malloc(sizeof(uint32_t) * worstcase_size);
1187         if (candidates->states[odd_even] == NULL) {
1188                 PrintAndLog("Out of memory error.\n");
1189                 return 4;
1190         }
1191         uint32_t *add_p = candidates->states[odd_even];
1192         for (uint32_t *p1 = partial_statelist[part_sum_a0].states[odd_even]; *p1 != 0xffffffff; p1++) {
1193                 uint32_t search_mask = 0x000ffff0;
1194                 uint32_t *p2 = find_first_state((*p1 << 4), search_mask, &partial_statelist[part_sum_a8], odd_even);
1195                 if (p2 != NULL) {
1196                         while (((*p1 << 4) & search_mask) == (*p2 & search_mask) && *p2 != 0xffffffff) {
1197                                 if ((nonces[best_first_bytes[0]].BitFlip[odd_even] && find_first_state((*p1 << 4) | *p2, 0x000fffff, &statelist_bitflip, 0))
1198                                         || !nonces[best_first_bytes[0]].BitFlip[odd_even]) {
1199                                 if (all_other_first_bytes_match((*p1 << 4) | *p2, odd_even)) {
1200                                         if (all_bit_flips_match((*p1 << 4) | *p2, odd_even)) {
1201                                                         *add_p++ = (*p1 << 4) | *p2;
1202                                                 }
1203                                 }
1204                                 }
1205                                 p2++;
1206                         }
1207                 }
1208         }
1209
1210         // set end of list marker and len
1211         *add_p = 0xffffffff;
1212         candidates->len[odd_even] = add_p - candidates->states[odd_even];
1213
1214         candidates->states[odd_even] = realloc(candidates->states[odd_even], sizeof(uint32_t) * (candidates->len[odd_even] + 1));
1215
1216         sl_cache[part_sum_a0][part_sum_a8][odd_even].sl = candidates->states[odd_even];
1217         sl_cache[part_sum_a0][part_sum_a8][odd_even].len = candidates->len[odd_even];
1218
1219         return 0;
1220 }
1221
1222
1223 static statelist_t *add_more_candidates(statelist_t *current_candidates)
1224 {
1225         statelist_t *new_candidates = NULL;
1226         if (current_candidates == NULL) {
1227                 if (candidates == NULL) {
1228                         candidates = (statelist_t *)malloc(sizeof(statelist_t));
1229                 }
1230                 new_candidates = candidates;
1231         } else {
1232                 new_candidates = current_candidates->next = (statelist_t *)malloc(sizeof(statelist_t));
1233         }
1234         new_candidates->next = NULL;
1235         new_candidates->len[ODD_STATE] = 0;
1236         new_candidates->len[EVEN_STATE] = 0;
1237         new_candidates->states[ODD_STATE] = NULL;
1238         new_candidates->states[EVEN_STATE] = NULL;
1239         return new_candidates;
1240 }
1241
1242
1243 static void TestIfKeyExists(uint64_t key)
1244 {
1245         struct Crypto1State *pcs;
1246         pcs = crypto1_create(key);
1247         crypto1_byte(pcs, (cuid >> 24) ^ best_first_bytes[0], true);
1248
1249         uint32_t state_odd = pcs->odd & 0x00ffffff;
1250         uint32_t state_even = pcs->even & 0x00ffffff;
1251         //printf("Tests: searching for key %llx after first byte 0x%02x (state_odd = 0x%06x, state_even = 0x%06x) ...\n", key, best_first_bytes[0], state_odd, state_even);
1252
1253         uint64_t count = 0;
1254         for (statelist_t *p = candidates; p != NULL; p = p->next) {
1255                 bool found_odd = false;
1256                 bool found_even = false;
1257                 uint32_t *p_odd = p->states[ODD_STATE];
1258                 uint32_t *p_even = p->states[EVEN_STATE];
1259                 while (*p_odd != 0xffffffff) {
1260                         if ((*p_odd & 0x00ffffff) == state_odd) {
1261                                 found_odd = true;
1262                                 break;
1263                         }
1264                         p_odd++;
1265                 }
1266                 while (*p_even != 0xffffffff) {
1267                         if ((*p_even & 0x00ffffff) == state_even) {
1268                                 found_even = true;
1269                         }
1270                         p_even++;
1271                 }
1272                 count += (p_odd - p->states[ODD_STATE]) * (p_even - p->states[EVEN_STATE]);
1273                 if (found_odd && found_even) {
1274                         PrintAndLog("Key Found after testing %lld (2^%1.1f) out of %lld (2^%1.1f) keys. A brute force would have taken approx %lld minutes.",
1275                                 count, log(count)/log(2),
1276                                 maximum_states, log(maximum_states)/log(2),
1277                                 (count>>23)/60);
1278                         if (write_stats) {
1279                                 fprintf(fstats, "1\n");
1280                         }
1281                         crypto1_destroy(pcs);
1282                         return;
1283                 }
1284         }
1285
1286         printf("Key NOT found!\n");
1287         if (write_stats) {
1288                 fprintf(fstats, "0\n");
1289         }
1290         crypto1_destroy(pcs);
1291 }
1292
1293
1294 static void generate_candidates(uint16_t sum_a0, uint16_t sum_a8)
1295 {
1296         printf("Generating crypto1 state candidates... \n");
1297
1298         statelist_t *current_candidates = NULL;
1299         // estimate maximum candidate states
1300         maximum_states = 0;
1301         for (uint16_t sum_odd = 0; sum_odd <= 16; sum_odd += 2) {
1302                 for (uint16_t sum_even = 0; sum_even <= 16; sum_even += 2) {
1303                         if (sum_odd*(16-sum_even) + (16-sum_odd)*sum_even == sum_a0) {
1304                                 maximum_states += (uint64_t)partial_statelist[sum_odd].len[ODD_STATE] * partial_statelist[sum_even].len[EVEN_STATE] * (1<<8);
1305                         }
1306                 }
1307         }
1308         printf("Number of possible keys with Sum(a0) = %d: %"PRIu64" (2^%1.1f)\n", sum_a0, maximum_states, log(maximum_states)/log(2.0));
1309
1310         init_statelist_cache();
1311
1312         for (uint16_t p = 0; p <= 16; p += 2) {
1313                 for (uint16_t q = 0; q <= 16; q += 2) {
1314                         if (p*(16-q) + (16-p)*q == sum_a0) {
1315                                 printf("Reducing Partial Statelists (p,q) = (%d,%d) with lengths %d, %d\n",
1316                                                 p, q, partial_statelist[p].len[ODD_STATE], partial_statelist[q].len[EVEN_STATE]);
1317                                 for (uint16_t r = 0; r <= 16; r += 2) {
1318                                         for (uint16_t s = 0; s <= 16; s += 2) {
1319                                                 if (r*(16-s) + (16-r)*s == sum_a8) {
1320                                                         current_candidates = add_more_candidates(current_candidates);
1321                                                         // check for the smallest partial statelist. Try this first - it might give 0 candidates
1322                                                         // and eliminate the need to calculate the other part
1323                                                         if (MIN(partial_statelist[p].len[ODD_STATE], partial_statelist[r].len[ODD_STATE])
1324                                                                         < MIN(partial_statelist[q].len[EVEN_STATE], partial_statelist[s].len[EVEN_STATE])) {
1325                                                         add_matching_states(current_candidates, p, r, ODD_STATE);
1326                                                                 if(current_candidates->len[ODD_STATE]) {
1327                                                         add_matching_states(current_candidates, q, s, EVEN_STATE);
1328                                                                 } else {
1329                                                                         current_candidates->len[EVEN_STATE] = 0;
1330                                                                         uint32_t *p = current_candidates->states[EVEN_STATE] = malloc(sizeof(uint32_t));
1331                                                                         *p = 0xffffffff;
1332                                                                 }
1333                                                         } else {
1334                                                                 add_matching_states(current_candidates, q, s, EVEN_STATE);
1335                                                                 if(current_candidates->len[EVEN_STATE]) {
1336                                                                         add_matching_states(current_candidates, p, r, ODD_STATE);
1337                                                                 } else {
1338                                                                         current_candidates->len[ODD_STATE] = 0;
1339                                                                         uint32_t *p = current_candidates->states[ODD_STATE] = malloc(sizeof(uint32_t));
1340                                                                         *p = 0xffffffff;
1341                                                                 }
1342                                                         }
1343                                                         printf("Odd  state candidates: %6d (2^%0.1f)\n", current_candidates->len[ODD_STATE], log(current_candidates->len[ODD_STATE])/log(2));
1344                                                         printf("Even state candidates: %6d (2^%0.1f)\n", current_candidates->len[EVEN_STATE], log(current_candidates->len[EVEN_STATE])/log(2));
1345                                                 }
1346                                         }
1347                                 }
1348                         }
1349                 }
1350         }
1351
1352
1353         maximum_states = 0;
1354         for (statelist_t *sl = candidates; sl != NULL; sl = sl->next) {
1355                 maximum_states += (uint64_t)sl->len[ODD_STATE] * sl->len[EVEN_STATE];
1356         }
1357         printf("Number of remaining possible keys: %"PRIu64" (2^%1.1f)\n", maximum_states, log(maximum_states)/log(2.0));
1358         if (write_stats) {
1359                 if (maximum_states != 0) {
1360                         fprintf(fstats, "%1.1f;", log(maximum_states)/log(2.0));
1361                 } else {
1362                         fprintf(fstats, "%1.1f;", 0.0);
1363                 }
1364         }
1365 }
1366
1367
1368 static void     free_candidates_memory(statelist_t *sl)
1369 {
1370         if (sl == NULL) {
1371                 return;
1372         } else {
1373                 free_candidates_memory(sl->next);
1374                 free(sl);
1375         }
1376 }
1377
1378
1379 static void free_statelist_cache(void)
1380 {
1381         for (uint16_t i = 0; i < 17; i+=2) {
1382                 for (uint16_t j = 0; j < 17; j+=2) {
1383                         for (uint16_t k = 0; k < 2; k++) {
1384                                 free(sl_cache[i][j][k].sl);
1385                         }
1386                 }
1387         }
1388 }
1389
1390
1391 static void brute_force(void)
1392 {
1393         if (known_target_key != -1) {
1394                 PrintAndLog("Looking for known target key in remaining key space...");
1395                 TestIfKeyExists(known_target_key);
1396         } else {
1397                 PrintAndLog("Brute Force phase is not implemented.");
1398         }
1399
1400 }
1401
1402
1403 int mfnestedhard(uint8_t blockNo, uint8_t keyType, uint8_t *key, uint8_t trgBlockNo, uint8_t trgKeyType, uint8_t *trgkey, bool nonce_file_read, bool nonce_file_write, bool slow, int tests)
1404 {
1405         // initialize Random number generator
1406         time_t t;
1407         srand((unsigned) time(&t));
1408
1409         if (trgkey != NULL) {
1410                 known_target_key = bytes_to_num(trgkey, 6);
1411         } else {
1412                 known_target_key = -1;
1413         }
1414
1415         init_partial_statelists();
1416         init_BitFlip_statelist();
1417         write_stats = false;
1418
1419         if (tests) {
1420                 // set the correct locale for the stats printing
1421                 setlocale(LC_ALL, "");
1422                 write_stats = true;
1423                 if ((fstats = fopen("hardnested_stats.txt","a")) == NULL) {
1424                         PrintAndLog("Could not create/open file hardnested_stats.txt");
1425                         return 3;
1426                 }
1427                 for (uint32_t i = 0; i < tests; i++) {
1428                         init_nonce_memory();
1429                         simulate_acquire_nonces();
1430                         Tests();
1431                         printf("Sum(a0) = %d\n", first_byte_Sum);
1432                         fprintf(fstats, "%d;", first_byte_Sum);
1433                         generate_candidates(first_byte_Sum, nonces[best_first_bytes[0]].Sum8_guess);
1434                         brute_force();
1435                         free_nonces_memory();
1436                         free_statelist_cache();
1437                         free_candidates_memory(candidates);
1438                         candidates = NULL;
1439                 }
1440                 fclose(fstats);
1441         } else {
1442                 init_nonce_memory();
1443                 if (nonce_file_read) {          // use pre-acquired data from file nonces.bin
1444                         if (read_nonce_file() != 0) {
1445                                 return 3;
1446                         }
1447                         Check_for_FilterFlipProperties();
1448                         num_good_first_bytes = MIN(estimate_second_byte_sum(), GOOD_BYTES_REQUIRED);
1449                 } else {                                        // acquire nonces.
1450                         uint16_t is_OK = acquire_nonces(blockNo, keyType, key, trgBlockNo, trgKeyType, nonce_file_write, slow);
1451                         if (is_OK != 0) {
1452                                 return is_OK;
1453                         }
1454                 }
1455
1456                 Tests();
1457
1458                 PrintAndLog("");
1459                 PrintAndLog("Sum(a0) = %d", first_byte_Sum);
1460                 // PrintAndLog("Best 10 first bytes: %02x, %02x, %02x, %02x, %02x, %02x, %02x, %02x, %02x, %02x",
1461                         // best_first_bytes[0],
1462                         // best_first_bytes[1],
1463                         // best_first_bytes[2],
1464                         // best_first_bytes[3],
1465                         // best_first_bytes[4],
1466                         // best_first_bytes[5],
1467                         // best_first_bytes[6],
1468                         // best_first_bytes[7],
1469                         // best_first_bytes[8],
1470                         // best_first_bytes[9]  );
1471                 PrintAndLog("Number of first bytes with confidence > %2.1f%%: %d", CONFIDENCE_THRESHOLD*100.0, num_good_first_bytes);
1472
1473                 clock_t time1 = clock();
1474                 generate_candidates(first_byte_Sum, nonces[best_first_bytes[0]].Sum8_guess);
1475                 time1 = clock() - time1;
1476                 if ( time1 > 0 )
1477                         PrintAndLog("Time for generating key candidates list: %1.0f seconds", ((float)time1)/CLOCKS_PER_SEC);
1478
1479                 brute_force();
1480                 free_nonces_memory();
1481                 free_statelist_cache();
1482                 free_candidates_memory(candidates);
1483                 candidates = NULL;
1484         }
1485         return 0;
1486 }
1487
1488