]> cvs.zerfleddert.de Git - proxmark3-svn/blob - client/cmdhfmfhard.c
projects / proxmark3-svn / blob
? search:


be618d6e7286d9583d13d6dd6f2476eb95fef98e
[proxmark3-svn] / client / cmdhfmfhard.c
1 //-----------------------------------------------------------------------------
2 // Copyright (C) 2015, 2016 by 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 "cmdhfmfhard.h"
18
19 #include <stdio.h>
20 #include <stdlib.h>
21 #include <inttypes.h>
22 #include <string.h>
23 #include <time.h>
24 #include <pthread.h>
25 #include <locale.h>
26 #include <math.h>
27 #include "proxmark3.h"
28 #include "comms.h"
29 #include "cmdmain.h"
30 #include "ui.h"
31 #include "util.h"
32 #include "util_posix.h"
33 #include "crapto1/crapto1.h"
34 #include "parity.h"
35 #include "hardnested/hardnested_bruteforce.h"
36 #include "hardnested/hardnested_bf_core.h"
37 #include "hardnested/hardnested_bitarray_core.h"
38 #include "zlib.h"
39
40 #define NUM_CHECK_BITFLIPS_THREADS (num_CPUs())
41 #define NUM_REDUCTION_WORKING_THREADS (num_CPUs())
42
43 #define IGNORE_BITFLIP_THRESHOLD 0.99 // ignore bitflip arrays which have nearly only valid states
44
45 #define STATE_FILES_DIRECTORY "hardnested/tables/"
46 #define STATE_FILE_TEMPLATE "bitflip_%d_%03" PRIx16 "_states.bin.z"
47
48 #define DEBUG_KEY_ELIMINATION
49 // #define DEBUG_REDUCTION
50
51 static uint16_t sums[NUM_SUMS] = {0, 32, 56, 64, 80, 96, 104, 112, 120, 128, 136, 144, 152, 160, 176, 192, 200, 224, 256}; // possible sum property values
52
53 #define NUM_PART_SUMS 9 // number of possible partial sum property values
54
55 typedef enum {
56 EVEN_STATE = 0,
57 ODD_STATE = 1
58 } odd_even_t;
59
60 static uint32_t num_acquired_nonces = 0;
61 static uint64_t start_time = 0;
62 static uint16_t effective_bitflip[2][0x400];
63 static uint16_t num_effective_bitflips[2] = {0, 0};
64 static uint16_t all_effective_bitflip[0x400];
65 static uint16_t num_all_effective_bitflips = 0;
66 static uint16_t num_1st_byte_effective_bitflips = 0;
67 #define CHECK_1ST_BYTES 0x01
68 #define CHECK_2ND_BYTES 0x02
69 static uint8_t hardnested_stage = CHECK_1ST_BYTES;
70 static uint64_t known_target_key;
71 static uint32_t test_state[2] = {0,0};
72 static float brute_force_per_second;
73
74
75 static void get_SIMD_instruction_set(char* instruction_set) {
76 switch(GetSIMDInstrAuto()) {
77 case SIMD_AVX512:
78 strcpy(instruction_set, "AVX512F");
79 break;
80 case SIMD_AVX2:
81 strcpy(instruction_set, "AVX2");
82 break;
83 case SIMD_AVX:
84 strcpy(instruction_set, "AVX");
85 break;
86 case SIMD_SSE2:
87 strcpy(instruction_set, "SSE2");
88 break;
89 case SIMD_MMX:
90 strcpy(instruction_set, "MMX");
91 break;
92 default:
93 strcpy(instruction_set, "no");
94 break;
95 }
96 }
97
98
99 static void print_progress_header(void) {
100 char progress_text[80];
101 char instr_set[12] = {0};
102 get_SIMD_instruction_set(instr_set);
103 sprintf(progress_text, "Start using %d threads and %s SIMD core", num_CPUs(), instr_set);
104 PrintAndLog("\n\n");
105 PrintAndLog(" time | #nonces | Activity | expected to brute force");
106 PrintAndLog(" | | | #states | time ");
107 PrintAndLog("------------------------------------------------------------------------------------------------------");
108 PrintAndLog(" 0 | 0 | %-55s | |", progress_text);
109 }
110
111
112 void hardnested_print_progress(uint32_t nonces, char *activity, float brute_force, uint64_t min_diff_print_time) {
113 static uint64_t last_print_time = 0;
114 if (msclock() - last_print_time > min_diff_print_time) {
115 last_print_time = msclock();
116 uint64_t total_time = msclock() - start_time;
117 float brute_force_time = brute_force / brute_force_per_second;
118 char brute_force_time_string[20];
119 if (brute_force_time < 90) {
120 sprintf(brute_force_time_string, "%2.0fs", brute_force_time);
121 } else if (brute_force_time < 60 * 90) {
122 sprintf(brute_force_time_string, "%2.0fmin", brute_force_time/60);
123 } else if (brute_force_time < 60 * 60 * 36) {
124 sprintf(brute_force_time_string, "%2.0fh", brute_force_time/(60*60));
125 } else {
126 sprintf(brute_force_time_string, "%2.0fd", brute_force_time/(60*60*24));
127 }
128 PrintAndLog(" %7.0f | %7d | %-55s | %15.0f | %5s", (float)total_time/1000.0, nonces, activity, brute_force, brute_force_time_string);
129 }
130 }
131
132
133 //////////////////////////////////////////////////////////////////////////////////////////////////////////////////
134 // bitarray functions
135
136 static inline void clear_bitarray24(uint32_t *bitarray)
137 {
138 memset(bitarray, 0x00, sizeof(uint32_t) * (1<<19));
139 }
140
141
142 static inline void set_bitarray24(uint32_t *bitarray)
143 {
144 memset(bitarray, 0xff, sizeof(uint32_t) * (1<<19));
145 }
146
147
148 static inline void set_bit24(uint32_t *bitarray, uint32_t index)
149 {
150 bitarray[index>>5] |= 0x80000000>>(index&0x0000001f);
151 }
152
153
154 static inline uint32_t test_bit24(uint32_t *bitarray, uint32_t index)
155 {
156 return bitarray[index>>5] & (0x80000000>>(index&0x0000001f));
157 }
158
159
160 static inline uint32_t next_state(uint32_t *bitarray, uint32_t state)
161 {
162 if (++state == 1<<24) return 1<<24;
163 uint32_t index = state >> 5;
164 uint_fast8_t bit = state & 0x1f;
165 uint32_t line = bitarray[index] << bit;
166 while (bit <= 0x1f) {
167 if (line & 0x80000000) return state;
168 state++;
169 bit++;
170 line <<= 1;
171 }
172 index++;
173 while (bitarray[index] == 0x00000000 && state < 1<<24) {
174 index++;
175 state += 0x20;
176 }
177 if (state >= 1<<24) return 1<<24;
178 #if defined __GNUC__
179 return state + __builtin_clz(bitarray[index]);
180 #else
181 bit = 0x00;
182 line = bitarray[index];
183 while (bit <= 0x1f) {
184 if (line & 0x80000000) return state;
185 state++;
186 bit++;
187 line <<= 1;
188 }
189 return 1<<24;
190 #endif
191 }
192
193
194
195
196 #define BITFLIP_2ND_BYTE 0x0200
197
198
199 //////////////////////////////////////////////////////////////////////////////////////////////////////////////////
200 // bitflip property bitarrays
201
202 static uint32_t *bitflip_bitarrays[2][0x400];
203 static uint32_t count_bitflip_bitarrays[2][0x400];
204
205 static int compare_count_bitflip_bitarrays(const void *b1, const void *b2)
206 {
207 uint64_t count1 = (uint64_t)count_bitflip_bitarrays[ODD_STATE][*(uint16_t *)b1] * count_bitflip_bitarrays[EVEN_STATE][*(uint16_t *)b1];
208 uint64_t count2 = (uint64_t)count_bitflip_bitarrays[ODD_STATE][*(uint16_t *)b2] * count_bitflip_bitarrays[EVEN_STATE][*(uint16_t *)b2];
209 return (count1 > count2) - (count2 > count1);
210 }
211
212
213 static voidpf inflate_malloc(voidpf opaque, uInt items, uInt size)
214 {
215 return malloc(items*size);
216 }
217
218
219 static void inflate_free(voidpf opaque, voidpf address)
220 {
221 free(address);
222 }
223
224 #define OUTPUT_BUFFER_LEN 80
225 #define INPUT_BUFFER_LEN 80
226
227 //----------------------------------------------------------------------------
228 // Initialize decompression of the respective (HF or LF) FPGA stream
229 //----------------------------------------------------------------------------
230 static void init_inflate(z_streamp compressed_stream, uint8_t *input_buffer, uint32_t insize, uint8_t *output_buffer, uint32_t outsize)
231 {
232
233 // initialize z_stream structure for inflate:
234 compressed_stream->next_in = input_buffer;
235 compressed_stream->avail_in = insize;
236 compressed_stream->next_out = output_buffer;
237 compressed_stream->avail_out = outsize;
238 compressed_stream->zalloc = &inflate_malloc;
239 compressed_stream->zfree = &inflate_free;
240
241 inflateInit2(compressed_stream, 0);
242
243 }
244
245
246 static void init_bitflip_bitarrays(void)
247 {
248 #if defined (DEBUG_REDUCTION)
249 uint8_t line = 0;
250 #endif
251
252
253 z_stream compressed_stream;
254
255 char state_files_path[strlen(get_my_executable_directory()) + strlen(STATE_FILES_DIRECTORY) + strlen(STATE_FILE_TEMPLATE) + 1];
256 char state_file_name[strlen(STATE_FILE_TEMPLATE)+1];
257
258 for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) {
259 num_effective_bitflips[odd_even] = 0;
260 for (uint16_t bitflip = 0x001; bitflip < 0x400; bitflip++) {
261 bitflip_bitarrays[odd_even][bitflip] = NULL;
262 count_bitflip_bitarrays[odd_even][bitflip] = 1<<24;
263 sprintf(state_file_name, STATE_FILE_TEMPLATE, odd_even, bitflip);
264 strcpy(state_files_path, get_my_executable_directory());
265 strcat(state_files_path, STATE_FILES_DIRECTORY);
266 strcat(state_files_path, state_file_name);
267 FILE *statesfile = fopen(state_files_path, "rb");
268 if (statesfile == NULL) {
269 continue;
270 } else {
271 fseek(statesfile, 0, SEEK_END);
272 uint32_t filesize = (uint32_t)ftell(statesfile);
273 rewind(statesfile);
274 uint8_t input_buffer[filesize];
275 size_t bytesread = fread(input_buffer, 1, filesize, statesfile);
276 if (bytesread != filesize) {
277 printf("File read error with %s. Aborting...\n", state_file_name);
278 fclose(statesfile);
279 inflateEnd(&compressed_stream);
280 exit(5);
281 }
282 fclose(statesfile);
283 uint32_t count = 0;
284 init_inflate(&compressed_stream, input_buffer, filesize, (uint8_t *)&count, sizeof(count));
285 inflate(&compressed_stream, Z_SYNC_FLUSH);
286 if ((float)count/(1<<24) < IGNORE_BITFLIP_THRESHOLD) {
287 uint32_t *bitset = (uint32_t *)malloc_bitarray(sizeof(uint32_t) * (1<<19));
288 if (bitset == NULL) {
289 printf("Out of memory error in init_bitflip_statelists(). Aborting...\n");
290 inflateEnd(&compressed_stream);
291 exit(4);
292 }
293 compressed_stream.next_out = (uint8_t *)bitset;
294 compressed_stream.avail_out = sizeof(uint32_t) * (1<<19);
295 inflate(&compressed_stream, Z_SYNC_FLUSH);
296 effective_bitflip[odd_even][num_effective_bitflips[odd_even]++] = bitflip;
297 bitflip_bitarrays[odd_even][bitflip] = bitset;
298 count_bitflip_bitarrays[odd_even][bitflip] = count;
299 #if defined (DEBUG_REDUCTION)
300 printf("(%03" PRIx16 " %s:%5.1f%%) ", bitflip, odd_even?"odd ":"even", (float)count/(1<<24)*100.0);
301 line++;
302 if (line == 8) {
303 printf("\n");
304 line = 0;
305 }
306 #endif
307 }
308 inflateEnd(&compressed_stream);
309 }
310 }
311 effective_bitflip[odd_even][num_effective_bitflips[odd_even]] = 0x400; // EndOfList marker
312 }
313
314 uint16_t i = 0;
315 uint16_t j = 0;
316 num_all_effective_bitflips = 0;
317 num_1st_byte_effective_bitflips = 0;
318 while (i < num_effective_bitflips[EVEN_STATE] || j < num_effective_bitflips[ODD_STATE]) {
319 if (effective_bitflip[EVEN_STATE][i] < effective_bitflip[ODD_STATE][j]) {
320 all_effective_bitflip[num_all_effective_bitflips++] = effective_bitflip[EVEN_STATE][i];
321 i++;
322 } else if (effective_bitflip[EVEN_STATE][i] > effective_bitflip[ODD_STATE][j]) {
323 all_effective_bitflip[num_all_effective_bitflips++] = effective_bitflip[ODD_STATE][j];
324 j++;
325 } else {
326 all_effective_bitflip[num_all_effective_bitflips++] = effective_bitflip[EVEN_STATE][i];
327 i++; j++;
328 }
329 if (!(all_effective_bitflip[num_all_effective_bitflips-1] & BITFLIP_2ND_BYTE)) {
330 num_1st_byte_effective_bitflips = num_all_effective_bitflips;
331 }
332 }
333 qsort(all_effective_bitflip, num_1st_byte_effective_bitflips, sizeof(uint16_t), compare_count_bitflip_bitarrays);
334 #if defined (DEBUG_REDUCTION)
335 printf("\n1st byte effective bitflips (%d): \n", num_1st_byte_effective_bitflips);
336 for(uint16_t i = 0; i < num_1st_byte_effective_bitflips; i++) {
337 printf("%03x ", all_effective_bitflip[i]);
338 }
339 #endif
340 qsort(all_effective_bitflip+num_1st_byte_effective_bitflips, num_all_effective_bitflips - num_1st_byte_effective_bitflips, sizeof(uint16_t), compare_count_bitflip_bitarrays);
341 #if defined (DEBUG_REDUCTION)
342 printf("\n2nd byte effective bitflips (%d): \n", num_all_effective_bitflips - num_1st_byte_effective_bitflips);
343 for(uint16_t i = num_1st_byte_effective_bitflips; i < num_all_effective_bitflips; i++) {
344 printf("%03x ", all_effective_bitflip[i]);
345 }
346 #endif
347 char progress_text[80];
348 sprintf(progress_text, "Using %d precalculated bitflip state tables", num_all_effective_bitflips);
349 hardnested_print_progress(0, progress_text, (float)(1LL<<47), 0);
350 }
351
352
353 static void free_bitflip_bitarrays(void)
354 {
355 for (int16_t bitflip = 0x3ff; bitflip > 0x000; bitflip--) {
356 free_bitarray(bitflip_bitarrays[ODD_STATE][bitflip]);
357 }
358 for (int16_t bitflip = 0x3ff; bitflip > 0x000; bitflip--) {
359 free_bitarray(bitflip_bitarrays[EVEN_STATE][bitflip]);
360 }
361 }
362
363
364 //////////////////////////////////////////////////////////////////////////////////////////////////////////////////
365 // sum property bitarrays
366
367 static uint32_t *part_sum_a0_bitarrays[2][NUM_PART_SUMS];
368 static uint32_t *part_sum_a8_bitarrays[2][NUM_PART_SUMS];
369 static uint32_t *sum_a0_bitarrays[2][NUM_SUMS];
370
371 static uint16_t PartialSumProperty(uint32_t state, odd_even_t odd_even)
372 {
373 uint16_t sum = 0;
374 for (uint16_t j = 0; j < 16; j++) {
375 uint32_t st = state;
376 uint16_t part_sum = 0;
377 if (odd_even == ODD_STATE) {
378 for (uint16_t i = 0; i < 5; i++) {
379 part_sum ^= filter(st);
380 st = (st << 1) | ((j >> (3-i)) & 0x01) ;
381 }
382 part_sum ^= 1; // XOR 1 cancelled out for the other 8 bits
383 } else {
384 for (uint16_t i = 0; i < 4; i++) {
385 st = (st << 1) | ((j >> (3-i)) & 0x01) ;
386 part_sum ^= filter(st);
387 }
388 }
389 sum += part_sum;
390 }
391 return sum;
392 }
393
394
395 static void init_part_sum_bitarrays(void)
396 {
397 for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) {
398 for (uint16_t part_sum_a0 = 0; part_sum_a0 < NUM_PART_SUMS; part_sum_a0++) {
399 part_sum_a0_bitarrays[odd_even][part_sum_a0] = (uint32_t *)malloc_bitarray(sizeof(uint32_t) * (1<<19));
400 if (part_sum_a0_bitarrays[odd_even][part_sum_a0] == NULL) {
401 printf("Out of memory error in init_part_suma0_statelists(). Aborting...\n");
402 exit(4);
403 }
404 clear_bitarray24(part_sum_a0_bitarrays[odd_even][part_sum_a0]);
405 }
406 }
407 for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) {
408 //printf("(%d, %" PRIu16 ")...", odd_even, part_sum_a0);
409 for (uint32_t state = 0; state < (1<<20); state++) {
410 uint16_t part_sum_a0 = PartialSumProperty(state, odd_even) / 2;
411 for (uint16_t low_bits = 0; low_bits < 1<<4; low_bits++) {
412 set_bit24(part_sum_a0_bitarrays[odd_even][part_sum_a0], state<<4 | low_bits);
413 }
414 }
415 }
416
417 for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) {
418 for (uint16_t part_sum_a8 = 0; part_sum_a8 < NUM_PART_SUMS; part_sum_a8++) {
419 part_sum_a8_bitarrays[odd_even][part_sum_a8] = (uint32_t *)malloc_bitarray(sizeof(uint32_t) * (1<<19));
420 if (part_sum_a8_bitarrays[odd_even][part_sum_a8] == NULL) {
421 printf("Out of memory error in init_part_suma8_statelists(). Aborting...\n");
422 exit(4);
423 }
424 clear_bitarray24(part_sum_a8_bitarrays[odd_even][part_sum_a8]);
425 }
426 }
427 for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) {
428 //printf("(%d, %" PRIu16 ")...", odd_even, part_sum_a8);
429 for (uint32_t state = 0; state < (1<<20); state++) {
430 uint16_t part_sum_a8 = PartialSumProperty(state, odd_even) / 2;
431 for (uint16_t high_bits = 0; high_bits < 1<<4; high_bits++) {
432 set_bit24(part_sum_a8_bitarrays[odd_even][part_sum_a8], state | high_bits<<20);
433 }
434 }
435 }
436 }
437
438
439 static void free_part_sum_bitarrays(void)
440 {
441 for (int16_t part_sum_a8 = (NUM_PART_SUMS-1); part_sum_a8 >= 0; part_sum_a8--) {
442 free_bitarray(part_sum_a8_bitarrays[ODD_STATE][part_sum_a8]);
443 }
444 for (int16_t part_sum_a8 = (NUM_PART_SUMS-1); part_sum_a8 >= 0; part_sum_a8--) {
445 free_bitarray(part_sum_a8_bitarrays[EVEN_STATE][part_sum_a8]);
446 }
447 for (int16_t part_sum_a0 = (NUM_PART_SUMS-1); part_sum_a0 >= 0; part_sum_a0--) {
448 free_bitarray(part_sum_a0_bitarrays[ODD_STATE][part_sum_a0]);
449 }
450 for (int16_t part_sum_a0 = (NUM_PART_SUMS-1); part_sum_a0 >= 0; part_sum_a0--) {
451 free_bitarray(part_sum_a0_bitarrays[EVEN_STATE][part_sum_a0]);
452 }
453 }
454
455
456 static void init_sum_bitarrays(void)
457 {
458 for (uint16_t sum_a0 = 0; sum_a0 < NUM_SUMS; sum_a0++) {
459 for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) {
460 sum_a0_bitarrays[odd_even][sum_a0] = (uint32_t *)malloc_bitarray(sizeof(uint32_t) * (1<<19));
461 if (sum_a0_bitarrays[odd_even][sum_a0] == NULL) {
462 printf("Out of memory error in init_sum_bitarrays(). Aborting...\n");
463 exit(4);
464 }
465 clear_bitarray24(sum_a0_bitarrays[odd_even][sum_a0]);
466 }
467 }
468 for (uint8_t p = 0; p < NUM_PART_SUMS; p++) {
469 for (uint8_t q = 0; q < NUM_PART_SUMS; q++) {
470 uint16_t sum_a0 = 2*p*(16-2*q) + (16-2*p)*2*q;
471 uint16_t sum_a0_idx = 0;
472 while (sums[sum_a0_idx] != sum_a0) sum_a0_idx++;
473 bitarray_OR(sum_a0_bitarrays[EVEN_STATE][sum_a0_idx], part_sum_a0_bitarrays[EVEN_STATE][q]);
474 bitarray_OR(sum_a0_bitarrays[ODD_STATE][sum_a0_idx], part_sum_a0_bitarrays[ODD_STATE][p]);
475 }
476 }
477 // for (uint16_t sum_a0 = 0; sum_a0 < NUM_SUMS; sum_a0++) {
478 // for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) {
479 // uint32_t count = count_states(sum_a0_bitarrays[odd_even][sum_a0]);
480 // printf("sum_a0_bitarray[%s][%d] has %d states (%5.2f%%)\n", odd_even==EVEN_STATE?"even":"odd ", sums[sum_a0], count, (float)count/(1<<24)*100.0);
481 // }
482 // }
483 }
484
485
486 static void free_sum_bitarrays(void)
487 {
488 for (int8_t sum_a0 = NUM_SUMS-1; sum_a0 >= 0; sum_a0--) {
489 free_bitarray(sum_a0_bitarrays[ODD_STATE][sum_a0]);
490 free_bitarray(sum_a0_bitarrays[EVEN_STATE][sum_a0]);
491 }
492 }
493
494
495 #ifdef DEBUG_KEY_ELIMINATION
496 char failstr[250] = "";
497 #endif
498
499 static const float p_K0[NUM_SUMS] = { // the probability that a random nonce has a Sum Property K
500 0.0290, 0.0083, 0.0006, 0.0339, 0.0048, 0.0934, 0.0119, 0.0489, 0.0602, 0.4180, 0.0602, 0.0489, 0.0119, 0.0934, 0.0048, 0.0339, 0.0006, 0.0083, 0.0290
501 };
502
503 static float my_p_K[NUM_SUMS];
504
505 static const float *p_K;
506
507 static uint32_t cuid;
508 static noncelist_t nonces[256];
509 static uint8_t best_first_bytes[256];
510 static uint64_t maximum_states = 0;
511 static uint8_t best_first_byte_smallest_bitarray = 0;
512 static uint16_t first_byte_Sum = 0;
513 static uint16_t first_byte_num = 0;
514 static bool write_stats = false;
515 static FILE *fstats = NULL;
516 static uint32_t *all_bitflips_bitarray[2];
517 static uint32_t num_all_bitflips_bitarray[2];
518 static bool all_bitflips_bitarray_dirty[2];
519 static uint64_t last_sample_clock = 0;
520 static uint64_t sample_period = 0;
521 static uint64_t num_keys_tested = 0;
522 static statelist_t *candidates = NULL;
523
524
525 static int add_nonce(uint32_t nonce_enc, uint8_t par_enc)
526 {
527 uint8_t first_byte = nonce_enc >> 24;
528 noncelistentry_t *p1 = nonces[first_byte].first;
529 noncelistentry_t *p2 = NULL;
530
531 if (p1 == NULL) { // first nonce with this 1st byte
532 first_byte_num++;
533 first_byte_Sum += evenparity32((nonce_enc & 0xff000000) | (par_enc & 0x08));
534 }
535
536 while (p1 != NULL && (p1->nonce_enc & 0x00ff0000) < (nonce_enc & 0x00ff0000)) {
537 p2 = p1;
538 p1 = p1->next;
539 }
540
541 if (p1 == NULL) { // need to add at the end of the list
542 if (p2 == NULL) { // list is empty yet. Add first entry.
543 p2 = nonces[first_byte].first = malloc(sizeof(noncelistentry_t));
544 } else { // add new entry at end of existing list.
545 p2 = p2->next = malloc(sizeof(noncelistentry_t));
546 }
547 } else if ((p1->nonce_enc & 0x00ff0000) != (nonce_enc & 0x00ff0000)) { // found distinct 2nd byte. Need to insert.
548 if (p2 == NULL) { // need to insert at start of list
549 p2 = nonces[first_byte].first = malloc(sizeof(noncelistentry_t));
550 } else {
551 p2 = p2->next = malloc(sizeof(noncelistentry_t));
552 }
553 } else { // we have seen this 2nd byte before. Nothing to add or insert.
554 return (0);
555 }
556
557 // add or insert new data
558 p2->next = p1;
559 p2->nonce_enc = nonce_enc;
560 p2->par_enc = par_enc;
561
562 nonces[first_byte].num++;
563 nonces[first_byte].Sum += evenparity32((nonce_enc & 0x00ff0000) | (par_enc & 0x04));
564 nonces[first_byte].sum_a8_guess_dirty = true; // indicates that we need to recalculate the Sum(a8) probability for this first byte
565 return (1); // new nonce added
566 }
567
568
569 static void init_nonce_memory(void)
570 {
571 for (uint16_t i = 0; i < 256; i++) {
572 nonces[i].num = 0;
573 nonces[i].Sum = 0;
574 nonces[i].first = NULL;
575 for (uint16_t j = 0; j < NUM_SUMS; j++) {
576 nonces[i].sum_a8_guess[j].sum_a8_idx = j;
577 nonces[i].sum_a8_guess[j].prob = 0.0;
578 }
579 nonces[i].sum_a8_guess_dirty = false;
580 for (uint16_t bitflip = 0x000; bitflip < 0x400; bitflip++) {
581 nonces[i].BitFlips[bitflip] = 0;
582 }
583 nonces[i].states_bitarray[EVEN_STATE] = (uint32_t *)malloc_bitarray(sizeof(uint32_t) * (1<<19));
584 if (nonces[i].states_bitarray[EVEN_STATE] == NULL) {
585 printf("Out of memory error in init_nonce_memory(). Aborting...\n");
586 exit(4);
587 }
588 set_bitarray24(nonces[i].states_bitarray[EVEN_STATE]);
589 nonces[i].num_states_bitarray[EVEN_STATE] = 1 << 24;
590 nonces[i].states_bitarray[ODD_STATE] = (uint32_t *)malloc_bitarray(sizeof(uint32_t) * (1<<19));
591 if (nonces[i].states_bitarray[ODD_STATE] == NULL) {
592 printf("Out of memory error in init_nonce_memory(). Aborting...\n");
593 exit(4);
594 }
595 set_bitarray24(nonces[i].states_bitarray[ODD_STATE]);
596 nonces[i].num_states_bitarray[ODD_STATE] = 1 << 24;
597 nonces[i].all_bitflips_dirty[EVEN_STATE] = false;
598 nonces[i].all_bitflips_dirty[ODD_STATE] = false;
599 }
600 first_byte_num = 0;
601 first_byte_Sum = 0;
602 }
603
604
605 static void free_nonce_list(noncelistentry_t *p)
606 {
607 if (p == NULL) {
608 return;
609 } else {
610 free_nonce_list(p->next);
611 free(p);
612 }
613 }
614
615
616 static void free_nonces_memory(void)
617 {
618 for (uint16_t i = 0; i < 256; i++) {
619 free_nonce_list(nonces[i].first);
620 }
621 for (int i = 255; i >= 0; i--) {
622 free_bitarray(nonces[i].states_bitarray[ODD_STATE]);
623 free_bitarray(nonces[i].states_bitarray[EVEN_STATE]);
624 }
625 }
626
627
628 // static double p_hypergeometric_cache[257][NUM_SUMS][257];
629
630 // #define CACHE_INVALID -1.0
631 // static void init_p_hypergeometric_cache(void)
632 // {
633 // for (uint16_t n = 0; n <= 256; n++) {
634 // for (uint16_t i_K = 0; i_K < NUM_SUMS; i_K++) {
635 // for (uint16_t k = 0; k <= 256; k++) {
636 // p_hypergeometric_cache[n][i_K][k] = CACHE_INVALID;
637 // }
638 // }
639 // }
640 // }
641
642
643 static double p_hypergeometric(uint16_t i_K, uint16_t n, uint16_t k)
644 {
645 // for efficient computation we are using the recursive definition
646 // (K-k+1) * (n-k+1)
647 // P(X=k) = P(X=k-1) * --------------------
648 // k * (N-K-n+k)
649 // and
650 // (N-K)*(N-K-1)*...*(N-K-n+1)
651 // P(X=0) = -----------------------------
652 // N*(N-1)*...*(N-n+1)
653
654
655 uint16_t const N = 256;
656 uint16_t K = sums[i_K];
657
658 // if (p_hypergeometric_cache[n][i_K][k] != CACHE_INVALID) {
659 // return p_hypergeometric_cache[n][i_K][k];
660 // }
661
662 if (n-k > N-K || k > K) return 0.0; // avoids log(x<=0) in calculation below
663 if (k == 0) {
664 // use logarithms to avoid overflow with huge factorials (double type can only hold 170!)
665 double log_result = 0.0;
666 for (int16_t i = N-K; i >= N-K-n+1; i--) {
667 log_result += log(i);
668 }
669 for (int16_t i = N; i >= N-n+1; i--) {
670 log_result -= log(i);
671 }
672 // p_hypergeometric_cache[n][i_K][k] = exp(log_result);
673 return exp(log_result);
674 } else {
675 if (n-k == N-K) { // special case. The published recursion below would fail with a divide by zero exception
676 double log_result = 0.0;
677 for (int16_t i = k+1; i <= n; i++) {
678 log_result += log(i);
679 }
680 for (int16_t i = K+1; i <= N; i++) {
681 log_result -= log(i);
682 }
683 // p_hypergeometric_cache[n][i_K][k] = exp(log_result);
684 return exp(log_result);
685 } else { // recursion
686 return (p_hypergeometric(i_K, n, k-1) * (K-k+1) * (n-k+1) / (k * (N-K-n+k)));
687 }
688 }
689 }
690
691
692 static float sum_probability(uint16_t i_K, uint16_t n, uint16_t k)
693 {
694 if (k > sums[i_K]) return 0.0;
695
696 double p_T_is_k_when_S_is_K = p_hypergeometric(i_K, n, k);
697 double p_S_is_K = p_K[i_K];
698 double p_T_is_k = 0;
699 for (uint16_t i = 0; i < NUM_SUMS; i++) {
700 p_T_is_k += p_K[i] * p_hypergeometric(i, n, k);
701 }
702 return(p_T_is_k_when_S_is_K * p_S_is_K / p_T_is_k);
703 }
704
705
706 static uint32_t part_sum_count[2][NUM_PART_SUMS][NUM_PART_SUMS];
707
708 static void init_allbitflips_array(void)
709 {
710 for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) {
711 uint32_t *bitset = all_bitflips_bitarray[odd_even] = (uint32_t *)malloc_bitarray(sizeof(uint32_t) * (1<<19));
712 if (bitset == NULL) {
713 printf("Out of memory in init_allbitflips_array(). Aborting...");
714 exit(4);
715 }
716 set_bitarray24(bitset);
717 all_bitflips_bitarray_dirty[odd_even] = false;
718 num_all_bitflips_bitarray[odd_even] = 1<<24;
719 }
720 }
721
722
723 static void update_allbitflips_array(void)
724 {
725 if (hardnested_stage & CHECK_2ND_BYTES) {
726 for (uint16_t i = 0; i < 256; i++) {
727 for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) {
728 if (nonces[i].all_bitflips_dirty[odd_even]) {
729 uint32_t old_count = num_all_bitflips_bitarray[odd_even];
730 num_all_bitflips_bitarray[odd_even] = count_bitarray_low20_AND(all_bitflips_bitarray[odd_even], nonces[i].states_bitarray[odd_even]);
731 nonces[i].all_bitflips_dirty[odd_even] = false;
732 if (num_all_bitflips_bitarray[odd_even] != old_count) {
733 all_bitflips_bitarray_dirty[odd_even] = true;
734 }
735 }
736 }
737 }
738 }
739 }
740
741
742 static uint32_t estimated_num_states_part_sum_coarse(uint16_t part_sum_a0_idx, uint16_t part_sum_a8_idx, odd_even_t odd_even)
743 {
744 return part_sum_count[odd_even][part_sum_a0_idx][part_sum_a8_idx];
745 }
746
747
748 static uint32_t estimated_num_states_part_sum(uint8_t first_byte, uint16_t part_sum_a0_idx, uint16_t part_sum_a8_idx, odd_even_t odd_even)
749 {
750 if (odd_even == ODD_STATE) {
751 return count_bitarray_AND3(part_sum_a0_bitarrays[odd_even][part_sum_a0_idx],
752 part_sum_a8_bitarrays[odd_even][part_sum_a8_idx],
753 nonces[first_byte].states_bitarray[odd_even]);
754 } else {
755 return count_bitarray_AND4(part_sum_a0_bitarrays[odd_even][part_sum_a0_idx],
756 part_sum_a8_bitarrays[odd_even][part_sum_a8_idx],
757 nonces[first_byte].states_bitarray[odd_even],
758 nonces[first_byte^0x80].states_bitarray[odd_even]);
759 }
760
761 // estimate reduction by all_bitflips_match()
762 // if (odd_even) {
763 // float p_bitflip = (float)nonces[first_byte ^ 0x80].num_states_bitarray[ODD_STATE] / num_all_bitflips_bitarray[ODD_STATE];
764 // return (float)count * p_bitflip; //(p_bitflip - 0.25*p_bitflip*p_bitflip);
765 // } else {
766 // return count;
767 // }
768 }
769
770
771 static uint64_t estimated_num_states(uint8_t first_byte, uint16_t sum_a0, uint16_t sum_a8)
772 {
773 uint64_t num_states = 0;
774 for (uint8_t p = 0; p < NUM_PART_SUMS; p++) {
775 for (uint8_t q = 0; q < NUM_PART_SUMS; q++) {
776 if (2*p*(16-2*q) + (16-2*p)*2*q == sum_a0) {
777 for (uint8_t r = 0; r < NUM_PART_SUMS; r++) {
778 for (uint8_t s = 0; s < NUM_PART_SUMS; s++) {
779 if (2*r*(16-2*s) + (16-2*r)*2*s == sum_a8) {
780 num_states += (uint64_t)estimated_num_states_part_sum(first_byte, p, r, ODD_STATE)
781 * estimated_num_states_part_sum(first_byte, q, s, EVEN_STATE);
782 }
783 }
784 }
785 }
786 }
787 }
788 return num_states;
789 }
790
791
792 static uint64_t estimated_num_states_coarse(uint16_t sum_a0, uint16_t sum_a8)
793 {
794 uint64_t num_states = 0;
795 for (uint8_t p = 0; p < NUM_PART_SUMS; p++) {
796 for (uint8_t q = 0; q < NUM_PART_SUMS; q++) {
797 if (2*p*(16-2*q) + (16-2*p)*2*q == sum_a0) {
798 for (uint8_t r = 0; r < NUM_PART_SUMS; r++) {
799 for (uint8_t s = 0; s < NUM_PART_SUMS; s++) {
800 if (2*r*(16-2*s) + (16-2*r)*2*s == sum_a8) {
801 num_states += (uint64_t)estimated_num_states_part_sum_coarse(p, r, ODD_STATE)
802 * estimated_num_states_part_sum_coarse(q, s, EVEN_STATE);
803 }
804 }
805 }
806 }
807 }
808 }
809 return num_states;
810 }
811
812
813 static void update_p_K(void)
814 {
815 if (hardnested_stage & CHECK_2ND_BYTES) {
816 uint64_t total_count = 0;
817 uint16_t sum_a0 = sums[first_byte_Sum];
818 for (uint8_t sum_a8_idx = 0; sum_a8_idx < NUM_SUMS; sum_a8_idx++) {
819 uint16_t sum_a8 = sums[sum_a8_idx];
820 total_count += estimated_num_states_coarse(sum_a0, sum_a8);
821 }
822 for (uint8_t sum_a8_idx = 0; sum_a8_idx < NUM_SUMS; sum_a8_idx++) {
823 uint16_t sum_a8 = sums[sum_a8_idx];
824 my_p_K[sum_a8_idx] = (float)estimated_num_states_coarse(sum_a0, sum_a8) / total_count;
825 }
826 // printf("my_p_K = [");
827 // for (uint8_t sum_a8_idx = 0; sum_a8_idx < NUM_SUMS; sum_a8_idx++) {
828 // printf("%7.4f ", my_p_K[sum_a8_idx]);
829 // }
830 p_K = my_p_K;
831 }
832 }
833
834
835 static void update_sum_bitarrays(odd_even_t odd_even)
836 {
837 if (all_bitflips_bitarray_dirty[odd_even]) {
838 for (uint8_t part_sum = 0; part_sum < NUM_PART_SUMS; part_sum++) {
839 bitarray_AND(part_sum_a0_bitarrays[odd_even][part_sum], all_bitflips_bitarray[odd_even]);
840 bitarray_AND(part_sum_a8_bitarrays[odd_even][part_sum], all_bitflips_bitarray[odd_even]);
841 }
842 for (uint16_t i = 0; i < 256; i++) {
843 nonces[i].num_states_bitarray[odd_even] = count_bitarray_AND(nonces[i].states_bitarray[odd_even], all_bitflips_bitarray[odd_even]);
844 }
845 for (uint8_t part_sum_a0 = 0; part_sum_a0 < NUM_PART_SUMS; part_sum_a0++) {
846 for (uint8_t part_sum_a8 = 0; part_sum_a8 < NUM_PART_SUMS; part_sum_a8++) {
847 part_sum_count[odd_even][part_sum_a0][part_sum_a8]
848 += count_bitarray_AND2(part_sum_a0_bitarrays[odd_even][part_sum_a0], part_sum_a8_bitarrays[odd_even][part_sum_a8]);
849 }
850 }
851 all_bitflips_bitarray_dirty[odd_even] = false;
852 }
853 }
854
855
856 static int compare_expected_num_brute_force(const void *b1, const void *b2)
857 {
858 uint8_t index1 = *(uint8_t *)b1;
859 uint8_t index2 = *(uint8_t *)b2;
860 float score1 = nonces[index1].expected_num_brute_force;
861 float score2 = nonces[index2].expected_num_brute_force;
862 return (score1 > score2) - (score1 < score2);
863 }
864
865
866 static int compare_sum_a8_guess(const void *b1, const void *b2)
867 {
868 float prob1 = ((guess_sum_a8_t *)b1)->prob;
869 float prob2 = ((guess_sum_a8_t *)b2)->prob;
870 return (prob1 < prob2) - (prob1 > prob2);
871
872 }
873
874
875 static float check_smallest_bitflip_bitarrays(void)
876 {
877 uint32_t num_odd, num_even;
878 uint64_t smallest = 1LL << 48;
879 // initialize best_first_bytes, do a rough estimation on remaining states
880 for (uint16_t i = 0; i < 256; i++) {
881 num_odd = nonces[i].num_states_bitarray[ODD_STATE];
882 num_even = nonces[i].num_states_bitarray[EVEN_STATE]; // * (float)nonces[i^0x80].num_states_bitarray[EVEN_STATE] / num_all_bitflips_bitarray[EVEN_STATE];
883 if ((uint64_t)num_odd * num_even < smallest) {
884 smallest = (uint64_t)num_odd * num_even;
885 best_first_byte_smallest_bitarray = i;
886 }
887 }
888
889 #if defined (DEBUG_REDUCTION)
890 num_odd = nonces[best_first_byte_smallest_bitarray].num_states_bitarray[ODD_STATE];
891 num_even = nonces[best_first_byte_smallest_bitarray].num_states_bitarray[EVEN_STATE]; // * (float)nonces[best_first_byte_smallest_bitarray^0x80].num_states_bitarray[EVEN_STATE] / num_all_bitflips_bitarray[EVEN_STATE];
892 printf("0x%02x: %8d * %8d = %12" PRIu64 " (2^%1.1f)\n", best_first_byte_smallest_bitarray, num_odd, num_even, (uint64_t)num_odd * num_even, log((uint64_t)num_odd * num_even)/log(2.0));
893 #endif
894 return (float)smallest/2.0;
895 }
896
897
898 static void update_expected_brute_force(uint8_t best_byte) {
899
900 float total_prob = 0.0;
901 for (uint8_t i = 0; i < NUM_SUMS; i++) {
902 total_prob += nonces[best_byte].sum_a8_guess[i].prob;
903 }
904 // linear adjust probabilities to result in total_prob = 1.0;
905 for (uint8_t i = 0; i < NUM_SUMS; i++) {
906 nonces[best_byte].sum_a8_guess[i].prob /= total_prob;
907 }
908 float prob_all_failed = 1.0;
909 nonces[best_byte].expected_num_brute_force = 0.0;
910 for (uint8_t i = 0; i < NUM_SUMS; i++) {
911 nonces[best_byte].expected_num_brute_force += nonces[best_byte].sum_a8_guess[i].prob * (float)nonces[best_byte].sum_a8_guess[i].num_states / 2.0;
912 prob_all_failed -= nonces[best_byte].sum_a8_guess[i].prob;
913 nonces[best_byte].expected_num_brute_force += prob_all_failed * (float)nonces[best_byte].sum_a8_guess[i].num_states / 2.0;
914 }
915 return;
916 }
917
918
919 static float sort_best_first_bytes(void)
920 {
921
922 // initialize best_first_bytes, do a rough estimation on remaining states for each Sum_a8 property
923 // and the expected number of states to brute force
924 for (uint16_t i = 0; i < 256; i++) {
925 best_first_bytes[i] = i;
926 float prob_all_failed = 1.0;
927 nonces[i].expected_num_brute_force = 0.0;
928 for (uint8_t j = 0; j < NUM_SUMS; j++) {
929 nonces[i].sum_a8_guess[j].num_states = estimated_num_states_coarse(sums[first_byte_Sum], sums[nonces[i].sum_a8_guess[j].sum_a8_idx]);
930 nonces[i].expected_num_brute_force += nonces[i].sum_a8_guess[j].prob * (float)nonces[i].sum_a8_guess[j].num_states / 2.0;
931 prob_all_failed -= nonces[i].sum_a8_guess[j].prob;
932 nonces[i].expected_num_brute_force += prob_all_failed * (float)nonces[i].sum_a8_guess[j].num_states / 2.0;
933 }
934 }
935
936 // sort based on expected number of states to brute force
937 qsort(best_first_bytes, 256, 1, compare_expected_num_brute_force);
938
939 // printf("refine estimations: ");
940 #define NUM_REFINES 1
941 // refine scores for the best:
942 for (uint16_t i = 0; i < NUM_REFINES; i++) {
943 // printf("%d...", i);
944 uint16_t first_byte = best_first_bytes[i];
945 for (uint8_t j = 0; j < NUM_SUMS && nonces[first_byte].sum_a8_guess[j].prob > 0.05; j++) {
946 nonces[first_byte].sum_a8_guess[j].num_states = estimated_num_states(first_byte, sums[first_byte_Sum], sums[nonces[first_byte].sum_a8_guess[j].sum_a8_idx]);
947 }
948 // while (nonces[first_byte].sum_a8_guess[0].num_states == 0
949 // || nonces[first_byte].sum_a8_guess[1].num_states == 0
950 // || nonces[first_byte].sum_a8_guess[2].num_states == 0) {
951 // if (nonces[first_byte].sum_a8_guess[0].num_states == 0) {
952 // nonces[first_byte].sum_a8_guess[0].prob = 0.0;
953 // printf("(0x%02x,%d)", first_byte, 0);
954 // }
955 // if (nonces[first_byte].sum_a8_guess[1].num_states == 0) {
956 // nonces[first_byte].sum_a8_guess[1].prob = 0.0;
957 // printf("(0x%02x,%d)", first_byte, 1);
958 // }
959 // if (nonces[first_byte].sum_a8_guess[2].num_states == 0) {
960 // nonces[first_byte].sum_a8_guess[2].prob = 0.0;
961 // printf("(0x%02x,%d)", first_byte, 2);
962 // }
963 // printf("|");
964 // qsort(nonces[first_byte].sum_a8_guess, NUM_SUMS, sizeof(guess_sum_a8_t), compare_sum_a8_guess);
965 // for (uint8_t j = 0; j < NUM_SUMS && nonces[first_byte].sum_a8_guess[j].prob > 0.05; j++) {
966 // nonces[first_byte].sum_a8_guess[j].num_states = estimated_num_states(first_byte, sums[first_byte_Sum], sums[nonces[first_byte].sum_a8_guess[j].sum_a8_idx]);
967 // }
968 // }
969 // float fix_probs = 0.0;
970 // for (uint8_t j = 0; j < NUM_SUMS; j++) {
971 // fix_probs += nonces[first_byte].sum_a8_guess[j].prob;
972 // }
973 // for (uint8_t j = 0; j < NUM_SUMS; j++) {
974 // nonces[first_byte].sum_a8_guess[j].prob /= fix_probs;
975 // }
976 // for (uint8_t j = 0; j < NUM_SUMS && nonces[first_byte].sum_a8_guess[j].prob > 0.05; j++) {
977 // nonces[first_byte].sum_a8_guess[j].num_states = estimated_num_states(first_byte, sums[first_byte_Sum], sums[nonces[first_byte].sum_a8_guess[j].sum_a8_idx]);
978 // }
979 float prob_all_failed = 1.0;
980 nonces[first_byte].expected_num_brute_force = 0.0;
981 for (uint8_t j = 0; j < NUM_SUMS; j++) {
982 nonces[first_byte].expected_num_brute_force += nonces[first_byte].sum_a8_guess[j].prob * (float)nonces[first_byte].sum_a8_guess[j].num_states / 2.0;
983 prob_all_failed -= nonces[first_byte].sum_a8_guess[j].prob;
984 nonces[first_byte].expected_num_brute_force += prob_all_failed * (float)nonces[first_byte].sum_a8_guess[j].num_states / 2.0;
985 }
986 }
987
988 // copy best byte to front:
989 float least_expected_brute_force = (1LL << 48);
990 uint8_t best_byte = 0;
991 for (uint16_t i = 0; i < 10; i++) {
992 uint16_t first_byte = best_first_bytes[i];
993 if (nonces[first_byte].expected_num_brute_force < least_expected_brute_force) {
994 least_expected_brute_force = nonces[first_byte].expected_num_brute_force;
995 best_byte = i;
996 }
997 }
998 if (best_byte != 0) {
999 // printf("0x%02x <-> 0x%02x", best_first_bytes[0], best_first_bytes[best_byte]);
1000 uint8_t tmp = best_first_bytes[0];
1001 best_first_bytes[0] = best_first_bytes[best_byte];
1002 best_first_bytes[best_byte] = tmp;
1003 }
1004
1005 return nonces[best_first_bytes[0]].expected_num_brute_force;
1006 }
1007
1008
1009 static float update_reduction_rate(float last, bool init)
1010 {
1011 #define QUEUE_LEN 4
1012 static float queue[QUEUE_LEN];
1013
1014 for (uint16_t i = 0; i < QUEUE_LEN-1; i++) {
1015 if (init) {
1016 queue[i] = (float)(1LL << 48);
1017 } else {
1018 queue[i] = queue[i+1];
1019 }
1020 }
1021 if (init) {
1022 queue[QUEUE_LEN-1] = (float)(1LL << 48);
1023 } else {
1024 queue[QUEUE_LEN-1] = last;
1025 }
1026
1027 // linear regression
1028 float avg_y = 0.0;
1029 float avg_x = 0.0;
1030 for (uint16_t i = 0; i < QUEUE_LEN; i++) {
1031 avg_x += i;
1032 avg_y += queue[i];
1033 }
1034 avg_x /= QUEUE_LEN;
1035 avg_y /= QUEUE_LEN;
1036
1037 float dev_xy = 0.0;
1038 float dev_x2 = 0.0;
1039 for (uint16_t i = 0; i < QUEUE_LEN; i++) {
1040 dev_xy += (i - avg_x)*(queue[i] - avg_y);
1041 dev_x2 += (i - avg_x)*(i - avg_x);
1042 }
1043
1044 float reduction_rate = -1.0 * dev_xy / dev_x2; // the negative slope of the linear regression
1045
1046 #if defined (DEBUG_REDUCTION)
1047 printf("update_reduction_rate(%1.0f) = %1.0f per sample, brute_force_per_sample = %1.0f\n", last, reduction_rate, brute_force_per_second * (float)sample_period / 1000.0);
1048 #endif
1049 return reduction_rate;
1050 }
1051
1052
1053 static bool shrink_key_space(float *brute_forces)
1054 {
1055 #if defined(DEBUG_REDUCTION)
1056 printf("shrink_key_space() with stage = 0x%02x\n", hardnested_stage);
1057 #endif
1058 float brute_forces1 = check_smallest_bitflip_bitarrays();
1059 float brute_forces2 = (float)(1LL << 47);
1060 if (hardnested_stage & CHECK_2ND_BYTES) {
1061 brute_forces2 = sort_best_first_bytes();
1062 }
1063 *brute_forces = MIN(brute_forces1, brute_forces2);
1064 float reduction_rate = update_reduction_rate(*brute_forces, false);
1065 return ((hardnested_stage & CHECK_2ND_BYTES)
1066 && reduction_rate >= 0.0 && reduction_rate < brute_force_per_second * sample_period / 1000.0);
1067 }
1068
1069
1070 static void estimate_sum_a8(void)
1071 {
1072 if (first_byte_num == 256) {
1073 for (uint16_t i = 0; i < 256; i++) {
1074 if (nonces[i].sum_a8_guess_dirty) {
1075 for (uint16_t j = 0; j < NUM_SUMS; j++ ) {
1076 uint16_t sum_a8_idx = nonces[i].sum_a8_guess[j].sum_a8_idx;
1077 nonces[i].sum_a8_guess[j].prob = sum_probability(sum_a8_idx, nonces[i].num, nonces[i].Sum);
1078 }
1079 qsort(nonces[i].sum_a8_guess, NUM_SUMS, sizeof(guess_sum_a8_t), compare_sum_a8_guess);
1080 nonces[i].sum_a8_guess_dirty = false;
1081 }
1082 }
1083 }
1084 }
1085
1086
1087 static int read_nonce_file(void)
1088 {
1089 FILE *fnonces = NULL;
1090 size_t bytes_read;
1091 uint8_t trgBlockNo;
1092 uint8_t trgKeyType;
1093 uint8_t read_buf[9];
1094 uint32_t nt_enc1, nt_enc2;
1095 uint8_t par_enc;
1096
1097 num_acquired_nonces = 0;
1098 if ((fnonces = fopen("nonces.bin","rb")) == NULL) {
1099 PrintAndLog("Could not open file nonces.bin");
1100 return 1;
1101 }
1102
1103 hardnested_print_progress(0, "Reading nonces from file nonces.bin...", (float)(1LL<<47), 0);
1104 bytes_read = fread(read_buf, 1, 6, fnonces);
1105 if (bytes_read != 6) {
1106 PrintAndLog("File reading error.");
1107 fclose(fnonces);
1108 return 1;
1109 }
1110 cuid = bytes_to_num(read_buf, 4);
1111 trgBlockNo = bytes_to_num(read_buf+4, 1);
1112 trgKeyType = bytes_to_num(read_buf+5, 1);
1113
1114 bytes_read = fread(read_buf, 1, 9, fnonces);
1115 while (bytes_read == 9) {
1116 nt_enc1 = bytes_to_num(read_buf, 4);
1117 nt_enc2 = bytes_to_num(read_buf+4, 4);
1118 par_enc = bytes_to_num(read_buf+8, 1);
1119 add_nonce(nt_enc1, par_enc >> 4);
1120 add_nonce(nt_enc2, par_enc & 0x0f);
1121 num_acquired_nonces += 2;
1122 bytes_read = fread(read_buf, 1, 9, fnonces);
1123 }
1124 fclose(fnonces);
1125
1126 char progress_string[80];
1127 sprintf(progress_string, "Read %d nonces from file. cuid=%08x", num_acquired_nonces, cuid);
1128 hardnested_print_progress(num_acquired_nonces, progress_string, (float)(1LL<<47), 0);
1129 sprintf(progress_string, "Target Block=%d, Keytype=%c", trgBlockNo, trgKeyType==0?'A':'B');
1130 hardnested_print_progress(num_acquired_nonces, progress_string, (float)(1LL<<47), 0);
1131
1132 for (uint16_t i = 0; i < NUM_SUMS; i++) {
1133 if (first_byte_Sum == sums[i]) {
1134 first_byte_Sum = i;
1135 break;
1136 }
1137 }
1138
1139 return 0;
1140 }
1141
1142
1143 noncelistentry_t *SearchFor2ndByte(uint8_t b1, uint8_t b2)
1144 {
1145 noncelistentry_t *p = nonces[b1].first;
1146 while (p != NULL) {
1147 if ((p->nonce_enc >> 16 & 0xff) == b2) {
1148 return p;
1149 }
1150 p = p->next;
1151 }
1152 return NULL;
1153 }
1154
1155
1156 static bool timeout(void)
1157 {
1158 return (msclock() > last_sample_clock + sample_period);
1159 }
1160
1161
1162 static void
1163 #ifdef __has_attribute
1164 #if __has_attribute(force_align_arg_pointer)
1165 __attribute__((force_align_arg_pointer))
1166 #endif
1167 #endif
1168 *check_for_BitFlipProperties_thread(void *args)
1169 {
1170 uint8_t first_byte = ((uint8_t *)args)[0];
1171 uint8_t last_byte = ((uint8_t *)args)[1];
1172 uint8_t time_budget = ((uint8_t *)args)[2];
1173
1174 if (hardnested_stage & CHECK_1ST_BYTES) {
1175 // for (uint16_t bitflip = 0x001; bitflip < 0x200; bitflip++) {
1176 for (uint16_t bitflip_idx = 0; bitflip_idx < num_1st_byte_effective_bitflips; bitflip_idx++) {
1177 uint16_t bitflip = all_effective_bitflip[bitflip_idx];
1178 if (time_budget & timeout()) {
1179 #if defined (DEBUG_REDUCTION)
1180 printf("break at bitflip_idx %d...", bitflip_idx);
1181 #endif
1182 return NULL;
1183 }
1184 for (uint16_t i = first_byte; i <= last_byte; i++) {
1185 if (nonces[i].BitFlips[bitflip] == 0 && nonces[i].BitFlips[bitflip ^ 0x100] == 0
1186 && nonces[i].first != NULL && nonces[i^(bitflip&0xff)].first != NULL) {
1187 uint8_t parity1 = (nonces[i].first->par_enc) >> 3; // parity of first byte
1188 uint8_t parity2 = (nonces[i^(bitflip&0xff)].first->par_enc) >> 3; // parity of nonce with bits flipped
1189 if ((parity1 == parity2 && !(bitflip & 0x100)) // bitflip
1190 || (parity1 != parity2 && (bitflip & 0x100))) { // not bitflip
1191 nonces[i].BitFlips[bitflip] = 1;
1192 for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) {
1193 if (bitflip_bitarrays[odd_even][bitflip] != NULL) {
1194 uint32_t old_count = nonces[i].num_states_bitarray[odd_even];
1195 nonces[i].num_states_bitarray[odd_even] = count_bitarray_AND(nonces[i].states_bitarray[odd_even], bitflip_bitarrays[odd_even][bitflip]);
1196 if (nonces[i].num_states_bitarray[odd_even] != old_count) {
1197 nonces[i].all_bitflips_dirty[odd_even] = true;
1198 }
1199 // printf("bitflip: %d old: %d, new: %d ", bitflip, old_count, nonces[i].num_states_bitarray[odd_even]);
1200 }
1201 }
1202 }
1203 }
1204 }
1205 ((uint8_t *)args)[1] = num_1st_byte_effective_bitflips - bitflip_idx - 1; // bitflips still to go in stage 1
1206 }
1207 }
1208
1209 ((uint8_t *)args)[1] = 0; // stage 1 definitely completed
1210
1211 if (hardnested_stage & CHECK_2ND_BYTES) {
1212 for (uint16_t bitflip_idx = num_1st_byte_effective_bitflips; bitflip_idx < num_all_effective_bitflips; bitflip_idx++) {
1213 uint16_t bitflip = all_effective_bitflip[bitflip_idx];
1214 if (time_budget & timeout()) {
1215 #if defined (DEBUG_REDUCTION)
1216 printf("break at bitflip_idx %d...", bitflip_idx);
1217 #endif
1218 return NULL;
1219 }
1220 for (uint16_t i = first_byte; i <= last_byte; i++) {
1221 // Check for Bit Flip Property of 2nd bytes
1222 if (nonces[i].BitFlips[bitflip] == 0) {
1223 for (uint16_t j = 0; j < 256; j++) { // for each 2nd Byte
1224 noncelistentry_t *byte1 = SearchFor2ndByte(i, j);
1225 noncelistentry_t *byte2 = SearchFor2ndByte(i, j^(bitflip&0xff));
1226 if (byte1 != NULL && byte2 != NULL) {
1227 uint8_t parity1 = byte1->par_enc >> 2 & 0x01; // parity of 2nd byte
1228 uint8_t parity2 = byte2->par_enc >> 2 & 0x01; // parity of 2nd byte with bits flipped
1229 if ((parity1 == parity2 && !(bitflip&0x100)) // bitflip
1230 || (parity1 != parity2 && (bitflip&0x100))) { // not bitflip
1231 nonces[i].BitFlips[bitflip] = 1;
1232 for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) {
1233 if (bitflip_bitarrays[odd_even][bitflip] != NULL) {
1234 uint32_t old_count = nonces[i].num_states_bitarray[odd_even];
1235 nonces[i].num_states_bitarray[odd_even] = count_bitarray_AND(nonces[i].states_bitarray[odd_even], bitflip_bitarrays[odd_even][bitflip]);
1236 if (nonces[i].num_states_bitarray[odd_even] != old_count) {
1237 nonces[i].all_bitflips_dirty[odd_even] = true;
1238 }
1239 }
1240 }
1241 break;
1242 }
1243 }
1244 }
1245 }
1246 // printf("states_bitarray[0][%" PRIu16 "] contains %d ones.\n", i, count_states(nonces[i].states_bitarray[EVEN_STATE]));
1247 // printf("states_bitarray[1][%" PRIu16 "] contains %d ones.\n", i, count_states(nonces[i].states_bitarray[ODD_STATE]));
1248 }
1249 }
1250 }
1251
1252 return NULL;
1253 }
1254
1255
1256 static void check_for_BitFlipProperties(bool time_budget)
1257 {
1258 // create and run worker threads
1259 pthread_t thread_id[NUM_CHECK_BITFLIPS_THREADS];
1260
1261 uint8_t args[NUM_CHECK_BITFLIPS_THREADS][3];
1262 uint16_t bytes_per_thread = (256 + (NUM_CHECK_BITFLIPS_THREADS/2)) / NUM_CHECK_BITFLIPS_THREADS;
1263 for (uint8_t i = 0; i < NUM_CHECK_BITFLIPS_THREADS; i++) {
1264 args[i][0] = i * bytes_per_thread;
1265 args[i][1] = MIN(args[i][0]+bytes_per_thread-1, 255);
1266 args[i][2] = time_budget;
1267 }
1268 args[NUM_CHECK_BITFLIPS_THREADS-1][1] = MAX(args[NUM_CHECK_BITFLIPS_THREADS-1][1], 255);
1269
1270 // start threads
1271 for (uint8_t i = 0; i < NUM_CHECK_BITFLIPS_THREADS; i++) {
1272 pthread_create(&thread_id[i], NULL, check_for_BitFlipProperties_thread, args[i]);
1273 }
1274
1275 // wait for threads to terminate:
1276 for (uint8_t i = 0; i < NUM_CHECK_BITFLIPS_THREADS; i++) {
1277 pthread_join(thread_id[i], NULL);
1278 }
1279
1280 if (hardnested_stage & CHECK_2ND_BYTES) {
1281 hardnested_stage &= ~CHECK_1ST_BYTES; // we are done with 1st stage, except...
1282 for (uint16_t i = 0; i < NUM_CHECK_BITFLIPS_THREADS; i++) {
1283 if (args[i][1] != 0) {
1284 hardnested_stage |= CHECK_1ST_BYTES; // ... when any of the threads didn't complete in time
1285 break;
1286 }
1287 }
1288 }
1289 #if defined (DEBUG_REDUCTION)
1290 if (hardnested_stage & CHECK_1ST_BYTES) printf("stage 1 not completed yet\n");
1291 #endif
1292 }
1293
1294
1295 static void update_nonce_data(bool time_budget)
1296 {
1297 check_for_BitFlipProperties(time_budget);
1298 update_allbitflips_array();
1299 update_sum_bitarrays(EVEN_STATE);
1300 update_sum_bitarrays(ODD_STATE);
1301 update_p_K();
1302 estimate_sum_a8();
1303 }
1304
1305
1306 static void apply_sum_a0(void)
1307 {
1308 uint32_t old_count = num_all_bitflips_bitarray[EVEN_STATE];
1309 num_all_bitflips_bitarray[EVEN_STATE] = count_bitarray_AND(all_bitflips_bitarray[EVEN_STATE], sum_a0_bitarrays[EVEN_STATE][first_byte_Sum]);
1310 if (num_all_bitflips_bitarray[EVEN_STATE] != old_count) {
1311 all_bitflips_bitarray_dirty[EVEN_STATE] = true;
1312 }
1313 old_count = num_all_bitflips_bitarray[ODD_STATE];
1314 num_all_bitflips_bitarray[ODD_STATE] = count_bitarray_AND(all_bitflips_bitarray[ODD_STATE], sum_a0_bitarrays[ODD_STATE][first_byte_Sum]);
1315 if (num_all_bitflips_bitarray[ODD_STATE] != old_count) {
1316 all_bitflips_bitarray_dirty[ODD_STATE] = true;
1317 }
1318 }
1319
1320
1321 static void simulate_MFplus_RNG(uint32_t test_cuid, uint64_t test_key, uint32_t *nt_enc, uint8_t *par_enc)
1322 {
1323 struct Crypto1State sim_cs = {0, 0};
1324
1325 // init cryptostate with key:
1326 for(int8_t i = 47; i > 0; i -= 2) {
1327 sim_cs.odd = sim_cs.odd << 1 | BIT(test_key, (i - 1) ^ 7);
1328 sim_cs.even = sim_cs.even << 1 | BIT(test_key, i ^ 7);
1329 }
1330
1331 *par_enc = 0;
1332 uint32_t nt = (rand() & 0xff) << 24 | (rand() & 0xff) << 16 | (rand() & 0xff) << 8 | (rand() & 0xff);
1333 for (int8_t byte_pos = 3; byte_pos >= 0; byte_pos--) {
1334 uint8_t nt_byte_dec = (nt >> (8*byte_pos)) & 0xff;
1335 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
1336 *nt_enc = (*nt_enc << 8) | nt_byte_enc;
1337 uint8_t ks_par = filter(sim_cs.odd); // the keystream bit to encode/decode the parity bit
1338 uint8_t nt_byte_par_enc = ks_par ^ oddparity8(nt_byte_dec); // determine the nt byte's parity and encode it
1339 *par_enc = (*par_enc << 1) | nt_byte_par_enc;
1340 }
1341
1342 }
1343
1344
1345 static void simulate_acquire_nonces()
1346 {
1347 time_t time1 = time(NULL);
1348 last_sample_clock = 0;
1349 sample_period = 1000; // for simulation
1350 hardnested_stage = CHECK_1ST_BYTES;
1351 bool acquisition_completed = false;
1352 uint32_t total_num_nonces = 0;
1353 float brute_force;
1354 bool reported_suma8 = false;
1355
1356 cuid = (rand() & 0xff) << 24 | (rand() & 0xff) << 16 | (rand() & 0xff) << 8 | (rand() & 0xff);
1357 if (known_target_key == -1) {
1358 known_target_key = ((uint64_t)rand() & 0xfff) << 36 | ((uint64_t)rand() & 0xfff) << 24 | ((uint64_t)rand() & 0xfff) << 12 | ((uint64_t)rand() & 0xfff);
1359 }
1360
1361 char progress_text[80];
1362 sprintf(progress_text, "Simulating key %012" PRIx64 ", cuid %08" PRIx32 " ...", known_target_key, cuid);
1363 hardnested_print_progress(0, progress_text, (float)(1LL<<47), 0);
1364 fprintf(fstats, "%012" PRIx64 ";%" PRIx32 ";", known_target_key, cuid);
1365
1366 num_acquired_nonces = 0;
1367
1368 do {
1369 uint32_t nt_enc = 0;
1370 uint8_t par_enc = 0;
1371
1372 for (uint16_t i = 0; i < 113; i++) {
1373 simulate_MFplus_RNG(cuid, known_target_key, &nt_enc, &par_enc);
1374 num_acquired_nonces += add_nonce(nt_enc, par_enc);
1375 total_num_nonces++;
1376 }
1377
1378 last_sample_clock = msclock();
1379
1380 if (first_byte_num == 256 ) {
1381 if (hardnested_stage == CHECK_1ST_BYTES) {
1382 for (uint16_t i = 0; i < NUM_SUMS; i++) {
1383 if (first_byte_Sum == sums[i]) {
1384 first_byte_Sum = i;
1385 break;
1386 }
1387 }
1388 hardnested_stage |= CHECK_2ND_BYTES;
1389 apply_sum_a0();
1390 }
1391 update_nonce_data(true);
1392 acquisition_completed = shrink_key_space(&brute_force);
1393 if (!reported_suma8) {
1394 char progress_string[80];
1395 sprintf(progress_string, "Apply Sum property. Sum(a0) = %d", sums[first_byte_Sum]);
1396 hardnested_print_progress(num_acquired_nonces, progress_string, brute_force, 0);
1397 reported_suma8 = true;
1398 } else {
1399 hardnested_print_progress(num_acquired_nonces, "Apply bit flip properties", brute_force, 0);
1400 }
1401 } else {
1402 update_nonce_data(true);
1403 acquisition_completed = shrink_key_space(&brute_force);
1404 hardnested_print_progress(num_acquired_nonces, "Apply bit flip properties", brute_force, 0);
1405 }
1406 } while (!acquisition_completed);
1407
1408 time_t end_time = time(NULL);
1409 // PrintAndLog("Acquired a total of %" PRId32" nonces in %1.0f seconds (%1.0f nonces/minute)",
1410 // num_acquired_nonces,
1411 // difftime(end_time, time1),
1412 // difftime(end_time, time1)!=0.0?(float)total_num_nonces*60.0/difftime(end_time, time1):INFINITY
1413 // );
1414
1415 fprintf(fstats, "%" PRId32 ";%" PRId32 ";%1.0f;", total_num_nonces, num_acquired_nonces, difftime(end_time,time1));
1416
1417 }
1418
1419
1420 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)
1421 {
1422 last_sample_clock = msclock();
1423 sample_period = 2000; // initial rough estimate. Will be refined.
1424 bool initialize = true;
1425 bool field_off = false;
1426 hardnested_stage = CHECK_1ST_BYTES;
1427 bool acquisition_completed = false;
1428 uint32_t flags = 0;
1429 uint8_t write_buf[9];
1430 uint32_t total_num_nonces = 0;
1431 float brute_force;
1432 bool reported_suma8 = false;
1433 FILE *fnonces = NULL;
1434 UsbCommand resp;
1435
1436 num_acquired_nonces = 0;
1437
1438 clearCommandBuffer();
1439
1440 do {
1441 flags = 0;
1442 flags |= initialize ? 0x0001 : 0;
1443 flags |= slow ? 0x0002 : 0;
1444 flags |= field_off ? 0x0004 : 0;
1445 UsbCommand c = {CMD_MIFARE_ACQUIRE_ENCRYPTED_NONCES, {blockNo + keyType * 0x100, trgBlockNo + trgKeyType * 0x100, flags}};
1446 memcpy(c.d.asBytes, key, 6);
1447
1448 SendCommand(&c);
1449
1450 if (field_off) break;
1451
1452 if (initialize) {
1453 if (!WaitForResponseTimeout(CMD_ACK, &resp, 3000)) return 1;
1454
1455 if (resp.arg[0]) return resp.arg[0]; // error during nested_hard
1456
1457 cuid = resp.arg[1];
1458 // PrintAndLog("Acquiring nonces for CUID 0x%08x", cuid);
1459 if (nonce_file_write && fnonces == NULL) {
1460 if ((fnonces = fopen("nonces.bin","wb")) == NULL) {
1461 PrintAndLog("Could not create file nonces.bin");
1462 return 3;
1463 }
1464 hardnested_print_progress(0, "Writing acquired nonces to binary file nonces.bin", (float)(1LL<<47), 0);
1465 num_to_bytes(cuid, 4, write_buf);
1466 fwrite(write_buf, 1, 4, fnonces);
1467 fwrite(&trgBlockNo, 1, 1, fnonces);
1468 fwrite(&trgKeyType, 1, 1, fnonces);
1469 }
1470 }
1471
1472 if (!initialize) {
1473 uint32_t nt_enc1, nt_enc2;
1474 uint8_t par_enc;
1475 uint16_t num_sampled_nonces = resp.arg[2];
1476 uint8_t *bufp = resp.d.asBytes;
1477 for (uint16_t i = 0; i < num_sampled_nonces; i+=2) {
1478 nt_enc1 = bytes_to_num(bufp, 4);
1479 nt_enc2 = bytes_to_num(bufp+4, 4);
1480 par_enc = bytes_to_num(bufp+8, 1);
1481
1482 //printf("Encrypted nonce: %08x, encrypted_parity: %02x\n", nt_enc1, par_enc >> 4);
1483 num_acquired_nonces += add_nonce(nt_enc1, par_enc >> 4);
1484 //printf("Encrypted nonce: %08x, encrypted_parity: %02x\n", nt_enc2, par_enc & 0x0f);
1485 num_acquired_nonces += add_nonce(nt_enc2, par_enc & 0x0f);
1486
1487 if (nonce_file_write) {
1488 fwrite(bufp, 1, 9, fnonces);
1489 }
1490 bufp += 9;
1491 }
1492 total_num_nonces += num_sampled_nonces;
1493
1494 if (first_byte_num == 256 ) {
1495 if (hardnested_stage == CHECK_1ST_BYTES) {
1496 for (uint16_t i = 0; i < NUM_SUMS; i++) {
1497 if (first_byte_Sum == sums[i]) {
1498 first_byte_Sum = i;
1499 break;
1500 }
1501 }
1502 hardnested_stage |= CHECK_2ND_BYTES;
1503 apply_sum_a0();
1504 }
1505 update_nonce_data(true);
1506 acquisition_completed = shrink_key_space(&brute_force);
1507 if (!reported_suma8) {
1508 char progress_string[80];
1509 sprintf(progress_string, "Apply Sum property. Sum(a0) = %d", sums[first_byte_Sum]);
1510 hardnested_print_progress(num_acquired_nonces, progress_string, brute_force, 0);
1511 reported_suma8 = true;
1512 } else {
1513 hardnested_print_progress(num_acquired_nonces, "Apply bit flip properties", brute_force, 0);
1514 }
1515 } else {
1516 update_nonce_data(true);
1517 acquisition_completed = shrink_key_space(&brute_force);
1518 hardnested_print_progress(num_acquired_nonces, "Apply bit flip properties", brute_force, 0);
1519 }
1520 }
1521
1522 if (acquisition_completed) {
1523 field_off = true; // switch off field with next SendCommand and then finish
1524 }
1525
1526 if (!initialize) {
1527 if (!WaitForResponseTimeout(CMD_ACK, &resp, 3000)) {
1528 if (nonce_file_write) {
1529 fclose(fnonces);
1530 }
1531 return 1;
1532 }
1533 if (resp.arg[0]) {
1534 if (nonce_file_write) {
1535 fclose(fnonces);
1536 }
1537 return resp.arg[0]; // error during nested_hard
1538 }
1539 }
1540
1541 initialize = false;
1542
1543 if (msclock() - last_sample_clock < sample_period) {
1544 sample_period = msclock() - last_sample_clock;
1545 }
1546 last_sample_clock = msclock();
1547
1548 } while (!acquisition_completed || field_off);
1549
1550 if (nonce_file_write) {
1551 fclose(fnonces);
1552 }
1553
1554 // PrintAndLog("Sampled a total of %d nonces in %d seconds (%0.0f nonces/minute)",
1555 // total_num_nonces,
1556 // time(NULL)-time1,
1557 // (float)total_num_nonces*60.0/(time(NULL)-time1));
1558
1559 return 0;
1560 }
1561
1562
1563 static inline bool invariant_holds(uint_fast8_t byte_diff, uint_fast32_t state1, uint_fast32_t state2, uint_fast8_t bit, uint_fast8_t state_bit)
1564 {
1565 uint_fast8_t j_1_bit_mask = 0x01 << (bit-1);
1566 uint_fast8_t bit_diff = byte_diff & j_1_bit_mask; // difference of (j-1)th bit
1567 uint_fast8_t filter_diff = filter(state1 >> (4-state_bit)) ^ filter(state2 >> (4-state_bit)); // difference in filter function
1568 uint_fast8_t mask_y12_y13 = 0xc0 >> state_bit;
1569 uint_fast8_t state_bits_diff = (state1 ^ state2) & mask_y12_y13; // difference in state bits 12 and 13
1570 uint_fast8_t all_diff = evenparity8(bit_diff ^ state_bits_diff ^ filter_diff); // use parity function to XOR all bits
1571 return !all_diff;
1572 }
1573
1574
1575 static inline bool invalid_state(uint_fast8_t byte_diff, uint_fast32_t state1, uint_fast32_t state2, uint_fast8_t bit, uint_fast8_t state_bit)
1576 {
1577 uint_fast8_t j_bit_mask = 0x01 << bit;
1578 uint_fast8_t bit_diff = byte_diff & j_bit_mask; // difference of jth bit
1579 uint_fast8_t mask_y13_y16 = 0x48 >> state_bit;
1580 uint_fast8_t state_bits_diff = (state1 ^ state2) & mask_y13_y16; // difference in state bits 13 and 16
1581 uint_fast8_t all_diff = evenparity8(bit_diff ^ state_bits_diff); // use parity function to XOR all bits
1582 return all_diff;
1583 }
1584
1585
1586 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)
1587 {
1588 if (odd_even) {
1589 // odd bits
1590 switch (num_common_bits) {
1591 case 0: if (!invariant_holds(byte_diff, state1, state2, 1, 0)) return true;
1592 case 1: if (invalid_state(byte_diff, state1, state2, 1, 0)) return false;
1593 case 2: if (!invariant_holds(byte_diff, state1, state2, 3, 1)) return true;
1594 case 3: if (invalid_state(byte_diff, state1, state2, 3, 1)) return false;
1595 case 4: if (!invariant_holds(byte_diff, state1, state2, 5, 2)) return true;
1596 case 5: if (invalid_state(byte_diff, state1, state2, 5, 2)) return false;
1597 case 6: if (!invariant_holds(byte_diff, state1, state2, 7, 3)) return true;
1598 case 7: if (invalid_state(byte_diff, state1, state2, 7, 3)) return false;
1599 }
1600 } else {
1601 // even bits
1602 switch (num_common_bits) {
1603 case 0: if (invalid_state(byte_diff, state1, state2, 0, 0)) return false;
1604 case 1: if (!invariant_holds(byte_diff, state1, state2, 2, 1)) return true;
1605 case 2: if (invalid_state(byte_diff, state1, state2, 2, 1)) return false;
1606 case 3: if (!invariant_holds(byte_diff, state1, state2, 4, 2)) return true;
1607 case 4: if (invalid_state(byte_diff, state1, state2, 4, 2)) return false;
1608 case 5: if (!invariant_holds(byte_diff, state1, state2, 6, 3)) return true;
1609 case 6: if (invalid_state(byte_diff, state1, state2, 6, 3)) return false;
1610 }
1611 }
1612
1613 return true; // valid state
1614 }
1615
1616
1617 static pthread_mutex_t statelist_cache_mutex;
1618 static pthread_mutex_t book_of_work_mutex;
1619
1620
1621 typedef enum {
1622 TO_BE_DONE,
1623 WORK_IN_PROGRESS,
1624 COMPLETED
1625 } work_status_t;
1626
1627 static struct sl_cache_entry {
1628 uint32_t *sl;
1629 uint32_t len;
1630 work_status_t cache_status;
1631 } sl_cache[NUM_PART_SUMS][NUM_PART_SUMS][2];
1632
1633
1634 static void init_statelist_cache(void)
1635 {
1636 pthread_mutex_lock(&statelist_cache_mutex);
1637 for (uint16_t i = 0; i < NUM_PART_SUMS; i++) {
1638 for (uint16_t j = 0; j < NUM_PART_SUMS; j++) {
1639 for (uint16_t k = 0; k < 2; k++) {
1640 sl_cache[i][j][k].sl = NULL;
1641 sl_cache[i][j][k].len = 0;
1642 sl_cache[i][j][k].cache_status = TO_BE_DONE;
1643 }
1644 }
1645 }
1646 pthread_mutex_unlock(&statelist_cache_mutex);
1647 }
1648
1649
1650 static void free_statelist_cache(void)
1651 {
1652 pthread_mutex_lock(&statelist_cache_mutex);
1653 for (uint16_t i = 0; i < NUM_PART_SUMS; i++) {
1654 for (uint16_t j = 0; j < NUM_PART_SUMS; j++) {
1655 for (uint16_t k = 0; k < 2; k++) {
1656 free(sl_cache[i][j][k].sl);
1657 }
1658 }
1659 }
1660 pthread_mutex_unlock(&statelist_cache_mutex);
1661 }
1662
1663
1664 #ifdef DEBUG_KEY_ELIMINATION
1665 static inline bool bitflips_match(uint8_t byte, uint32_t state, odd_even_t odd_even, bool quiet)
1666 #else
1667 static inline bool bitflips_match(uint8_t byte, uint32_t state, odd_even_t odd_even)
1668 #endif
1669 {
1670 uint32_t *bitset = nonces[byte].states_bitarray[odd_even];
1671 bool possible = test_bit24(bitset, state);
1672 if (!possible) {
1673 #ifdef DEBUG_KEY_ELIMINATION
1674 if (!quiet && known_target_key != -1 && state == test_state[odd_even]) {
1675 printf("Initial state lists: %s test state eliminated by bitflip property.\n", odd_even==EVEN_STATE?"even":"odd");
1676 sprintf(failstr, "Initial %s Byte Bitflip property", odd_even==EVEN_STATE?"even":"odd");
1677 }
1678 #endif
1679 return false;
1680 } else {
1681 return true;
1682 }
1683 }
1684
1685
1686 static uint_fast8_t reverse(uint_fast8_t byte)
1687 {
1688 uint_fast8_t rev_byte = 0;
1689
1690 for (uint8_t i = 0; i < 8; i++) {
1691 rev_byte <<= 1;
1692 rev_byte |= (byte >> i) & 0x01;
1693 }
1694
1695 return rev_byte;
1696 }
1697
1698
1699 static bool all_bitflips_match(uint8_t byte, uint32_t state, odd_even_t odd_even)
1700 {
1701 uint32_t masks[2][8] = {{0x00fffff0, 0x00fffff8, 0x00fffff8, 0x00fffffc, 0x00fffffc, 0x00fffffe, 0x00fffffe, 0x00ffffff},
1702 {0x00fffff0, 0x00fffff0, 0x00fffff8, 0x00fffff8, 0x00fffffc, 0x00fffffc, 0x00fffffe, 0x00fffffe} };
1703
1704 for (uint16_t i = 1; i < 256; i++) {
1705 uint_fast8_t bytes_diff = reverse(i); // start with most common bits
1706 uint_fast8_t byte2 = byte ^ bytes_diff;
1707 uint_fast8_t num_common = trailing_zeros(bytes_diff);
1708 uint32_t mask = masks[odd_even][num_common];
1709 bool found_match = false;
1710 for (uint8_t remaining_bits = 0; remaining_bits <= (~mask & 0xff); remaining_bits++) {
1711 if (remaining_bits_match(num_common, bytes_diff, state, (state & mask) | remaining_bits, odd_even)) {
1712 #ifdef DEBUG_KEY_ELIMINATION
1713 if (bitflips_match(byte2, (state & mask) | remaining_bits, odd_even, true)) {
1714 #else
1715 if (bitflips_match(byte2, (state & mask) | remaining_bits, odd_even)) {
1716 #endif
1717 found_match = true;
1718 break;
1719 }
1720 }
1721 }
1722 if (!found_match) {
1723 #ifdef DEBUG_KEY_ELIMINATION
1724 if (known_target_key != -1 && state == test_state[odd_even]) {
1725 printf("all_bitflips_match() 1st Byte: %s test state (0x%06x): Eliminated. Bytes = %02x, %02x, Common Bits = %d\n",
1726 odd_even==ODD_STATE?"odd":"even",
1727 test_state[odd_even],
1728 byte, byte2, num_common);
1729 if (failstr[0] == '\0') {
1730 sprintf(failstr, "Other 1st Byte %s, all_bitflips_match(), no match", odd_even?"odd":"even");
1731 }
1732 }
1733 #endif
1734 return false;
1735 }
1736 }
1737
1738 return true;
1739 }
1740
1741
1742 static void bitarray_to_list(uint8_t byte, uint32_t *bitarray, uint32_t *state_list, uint32_t *len, odd_even_t odd_even)
1743 {
1744 uint32_t *p = state_list;
1745 for (uint32_t state = next_state(bitarray, -1L); state < (1<<24); state = next_state(bitarray, state)) {
1746 if (all_bitflips_match(byte, state, odd_even)) {
1747 *p++ = state;
1748 }
1749 }
1750 // add End Of List marker
1751 *p = 0xffffffff;
1752 *len = p - state_list;
1753 }
1754
1755
1756 static void add_cached_states(statelist_t *candidates, uint16_t part_sum_a0, uint16_t part_sum_a8, odd_even_t odd_even)
1757 {
1758 candidates->states[odd_even] = sl_cache[part_sum_a0/2][part_sum_a8/2][odd_even].sl;
1759 candidates->len[odd_even] = sl_cache[part_sum_a0/2][part_sum_a8/2][odd_even].len;
1760 return;
1761 }
1762
1763
1764 static void add_matching_states(statelist_t *candidates, uint8_t part_sum_a0, uint8_t part_sum_a8, odd_even_t odd_even)
1765 {
1766 uint32_t worstcase_size = 1<<20;
1767 candidates->states[odd_even] = (uint32_t *)malloc(sizeof(uint32_t) * worstcase_size);
1768 if (candidates->states[odd_even] == NULL) {
1769 PrintAndLog("Out of memory error in add_matching_states() - statelist.\n");
1770 exit(4);
1771 }
1772 uint32_t *candidates_bitarray = (uint32_t *)malloc_bitarray(sizeof(uint32_t) * (1<<19));
1773 if (candidates_bitarray == NULL) {
1774 PrintAndLog("Out of memory error in add_matching_states() - bitarray.\n");
1775 free(candidates->states[odd_even]);
1776 exit(4);
1777 }
1778
1779 uint32_t *bitarray_a0 = part_sum_a0_bitarrays[odd_even][part_sum_a0/2];
1780 uint32_t *bitarray_a8 = part_sum_a8_bitarrays[odd_even][part_sum_a8/2];
1781 uint32_t *bitarray_bitflips = nonces[best_first_bytes[0]].states_bitarray[odd_even];
1782
1783 // for (uint32_t i = 0; i < (1<<19); i++) {
1784 // candidates_bitarray[i] = bitarray_a0[i] & bitarray_a8[i] & bitarray_bitflips[i];
1785 // }
1786 bitarray_AND4(candidates_bitarray, bitarray_a0, bitarray_a8, bitarray_bitflips);
1787
1788 bitarray_to_list(best_first_bytes[0], candidates_bitarray, candidates->states[odd_even], &(candidates->len[odd_even]), odd_even);
1789 if (candidates->len[odd_even] == 0) {
1790 free(candidates->states[odd_even]);
1791 candidates->states[odd_even] = NULL;
1792 } else if (candidates->len[odd_even] + 1 < worstcase_size) {
1793 candidates->states[odd_even] = realloc(candidates->states[odd_even], sizeof(uint32_t) * (candidates->len[odd_even] + 1));
1794 }
1795 free_bitarray(candidates_bitarray);
1796
1797
1798 pthread_mutex_lock(&statelist_cache_mutex);
1799 sl_cache[part_sum_a0/2][part_sum_a8/2][odd_even].sl = candidates->states[odd_even];
1800 sl_cache[part_sum_a0/2][part_sum_a8/2][odd_even].len = candidates->len[odd_even];
1801 sl_cache[part_sum_a0/2][part_sum_a8/2][odd_even].cache_status = COMPLETED;
1802 pthread_mutex_unlock(&statelist_cache_mutex);
1803
1804 return;
1805 }
1806
1807
1808 static statelist_t *add_more_candidates(void)
1809 {
1810 statelist_t *new_candidates = candidates;
1811 if (candidates == NULL) {
1812 candidates = (statelist_t *)malloc(sizeof(statelist_t));
1813 new_candidates = candidates;
1814 } else {
1815 new_candidates = candidates;
1816 while (new_candidates->next != NULL) {
1817 new_candidates = new_candidates->next;
1818 }
1819 new_candidates = new_candidates->next = (statelist_t *)malloc(sizeof(statelist_t));
1820 }
1821 new_candidates->next = NULL;
1822 new_candidates->len[ODD_STATE] = 0;
1823 new_candidates->len[EVEN_STATE] = 0;
1824 new_candidates->states[ODD_STATE] = NULL;
1825 new_candidates->states[EVEN_STATE] = NULL;
1826 return new_candidates;
1827 }
1828
1829
1830 static void add_bitflip_candidates(uint8_t byte)
1831 {
1832 statelist_t *candidates = add_more_candidates();
1833
1834 for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) {
1835 uint32_t worstcase_size = nonces[byte].num_states_bitarray[odd_even] + 1;
1836 candidates->states[odd_even] = (uint32_t *)malloc(sizeof(uint32_t) * worstcase_size);
1837 if (candidates->states[odd_even] == NULL) {
1838 PrintAndLog("Out of memory error in add_bitflip_candidates().\n");
1839 exit(4);
1840 }
1841
1842 bitarray_to_list(byte, nonces[byte].states_bitarray[odd_even], candidates->states[odd_even], &(candidates->len[odd_even]), odd_even);
1843
1844 if (candidates->len[odd_even] + 1 < worstcase_size) {
1845 candidates->states[odd_even] = realloc(candidates->states[odd_even], sizeof(uint32_t) * (candidates->len[odd_even] + 1));
1846 }
1847 }
1848 return;
1849 }
1850
1851
1852 static bool TestIfKeyExists(uint64_t key)
1853 {
1854 struct Crypto1State *pcs;
1855 pcs = crypto1_create(key);
1856 crypto1_byte(pcs, (cuid >> 24) ^ best_first_bytes[0], true);
1857
1858 uint32_t state_odd = pcs->odd & 0x00ffffff;
1859 uint32_t state_even = pcs->even & 0x00ffffff;
1860
1861 uint64_t count = 0;
1862 for (statelist_t *p = candidates; p != NULL; p = p->next) {
1863 bool found_odd = false;
1864 bool found_even = false;
1865 uint32_t *p_odd = p->states[ODD_STATE];
1866 uint32_t *p_even = p->states[EVEN_STATE];
1867 if (p_odd != NULL && p_even != NULL) {
1868 while (*p_odd != 0xffffffff) {
1869 if ((*p_odd & 0x00ffffff) == state_odd) {
1870 found_odd = true;
1871 break;
1872 }
1873 p_odd++;
1874 }
1875 while (*p_even != 0xffffffff) {
1876 if ((*p_even & 0x00ffffff) == state_even) {
1877 found_even = true;
1878 }
1879 p_even++;
1880 }
1881 count += (uint64_t)(p_odd - p->states[ODD_STATE]) * (uint64_t)(p_even - p->states[EVEN_STATE]);
1882 }
1883 if (found_odd && found_even) {
1884 num_keys_tested += count;
1885 hardnested_print_progress(num_acquired_nonces, "(Test: Key found)", 0.0, 0);
1886 crypto1_destroy(pcs);
1887 return true;
1888 }
1889 }
1890
1891 num_keys_tested += count;
1892 hardnested_print_progress(num_acquired_nonces, "(Test: Key NOT found)", 0.0, 0);
1893
1894 crypto1_destroy(pcs);
1895 return false;
1896 }
1897
1898
1899 static work_status_t book_of_work[NUM_PART_SUMS][NUM_PART_SUMS][NUM_PART_SUMS][NUM_PART_SUMS];
1900
1901
1902 static void init_book_of_work(void)
1903 {
1904 for (uint8_t p = 0; p < NUM_PART_SUMS; p++) {
1905 for (uint8_t q = 0; q < NUM_PART_SUMS; q++) {
1906 for (uint8_t r = 0; r < NUM_PART_SUMS; r++) {
1907 for (uint8_t s = 0; s < NUM_PART_SUMS; s++) {
1908 book_of_work[p][q][r][s] = TO_BE_DONE;
1909 }
1910 }
1911 }
1912 }
1913 }
1914
1915
1916 static void
1917 #ifdef __has_attribute
1918 #if __has_attribute(force_align_arg_pointer)
1919 __attribute__((force_align_arg_pointer))
1920 #endif
1921 #endif
1922 *generate_candidates_worker_thread(void *args)
1923 {
1924 uint16_t *sum_args = (uint16_t *)args;
1925 uint16_t sum_a0 = sums[sum_args[0]];
1926 uint16_t sum_a8 = sums[sum_args[1]];
1927 // uint16_t my_thread_number = sums[2];
1928
1929 bool there_might_be_more_work = true;
1930 do {
1931 there_might_be_more_work = false;
1932 for (uint8_t p = 0; p < NUM_PART_SUMS; p++) {
1933 for (uint8_t q = 0; q < NUM_PART_SUMS; q++) {
1934 if (2*p*(16-2*q) + (16-2*p)*2*q == sum_a0) {
1935 // printf("Reducing Partial Statelists (p,q) = (%d,%d) with lengths %d, %d\n",
1936 // p, q, partial_statelist[p].len[ODD_STATE], partial_statelist[q].len[EVEN_STATE]);
1937 for (uint8_t r = 0; r < NUM_PART_SUMS; r++) {
1938 for (uint8_t s = 0; s < NUM_PART_SUMS; s++) {
1939 if (2*r*(16-2*s) + (16-2*r)*2*s == sum_a8) {
1940 pthread_mutex_lock(&book_of_work_mutex);
1941 if (book_of_work[p][q][r][s] != TO_BE_DONE) { // this has been done or is currently been done by another thread. Look for some other work.
1942 pthread_mutex_unlock(&book_of_work_mutex);
1943 continue;
1944 }
1945
1946 pthread_mutex_lock(&statelist_cache_mutex);
1947 if (sl_cache[p][r][ODD_STATE].cache_status == WORK_IN_PROGRESS
1948 || sl_cache[q][s][EVEN_STATE].cache_status == WORK_IN_PROGRESS) { // defer until not blocked by another thread.
1949 pthread_mutex_unlock(&statelist_cache_mutex);
1950 pthread_mutex_unlock(&book_of_work_mutex);
1951 there_might_be_more_work = true;
1952 continue;
1953 }
1954
1955 // we finally can do some work.
1956 book_of_work[p][q][r][s] = WORK_IN_PROGRESS;
1957 statelist_t *current_candidates = add_more_candidates();
1958
1959 // Check for cached results and add them first
1960 bool odd_completed = false;
1961 if (sl_cache[p][r][ODD_STATE].cache_status == COMPLETED) {
1962 add_cached_states(current_candidates, 2*p, 2*r, ODD_STATE);
1963 odd_completed = true;
1964 }
1965 bool even_completed = false;
1966 if (sl_cache[q][s][EVEN_STATE].cache_status == COMPLETED) {
1967 add_cached_states(current_candidates, 2*q, 2*s, EVEN_STATE);
1968 even_completed = true;
1969 }
1970
1971 bool work_required = true;
1972
1973 // if there had been two cached results, there is no more work to do
1974 if (even_completed && odd_completed) {
1975 work_required = false;
1976 }
1977
1978 // if there had been one cached empty result, there is no need to calculate the other part:
1979 if (work_required) {
1980 if (even_completed && !current_candidates->len[EVEN_STATE]) {
1981 current_candidates->len[ODD_STATE] = 0;
1982 current_candidates->states[ODD_STATE] = NULL;
1983 work_required = false;
1984 }
1985 if (odd_completed && !current_candidates->len[ODD_STATE]) {
1986 current_candidates->len[EVEN_STATE] = 0;
1987 current_candidates->states[EVEN_STATE] = NULL;
1988 work_required = false;
1989 }
1990 }
1991
1992 if (!work_required) {
1993 pthread_mutex_unlock(&statelist_cache_mutex);
1994 pthread_mutex_unlock(&book_of_work_mutex);
1995 } else {
1996 // we really need to calculate something
1997 if (even_completed) { // we had one cache hit with non-zero even states
1998 // printf("Thread #%u: start working on odd states p=%2d, r=%2d...\n", my_thread_number, p, r);
1999 sl_cache[p][r][ODD_STATE].cache_status = WORK_IN_PROGRESS;
2000 pthread_mutex_unlock(&statelist_cache_mutex);
2001 pthread_mutex_unlock(&book_of_work_mutex);
2002 add_matching_states(current_candidates, 2*p, 2*r, ODD_STATE);
2003 work_required = false;
2004 } else if (odd_completed) { // we had one cache hit with non-zero odd_states
2005 // printf("Thread #%u: start working on even states q=%2d, s=%2d...\n", my_thread_number, q, s);
2006 sl_cache[q][s][EVEN_STATE].cache_status = WORK_IN_PROGRESS;
2007 pthread_mutex_unlock(&statelist_cache_mutex);
2008 pthread_mutex_unlock(&book_of_work_mutex);
2009 add_matching_states(current_candidates, 2*q, 2*s, EVEN_STATE);
2010 work_required = false;
2011 }
2012 }
2013
2014 if (work_required) { // we had no cached result. Need to calculate both odd and even
2015 sl_cache[p][r][ODD_STATE].cache_status = WORK_IN_PROGRESS;
2016 sl_cache[q][s][EVEN_STATE].cache_status = WORK_IN_PROGRESS;
2017 pthread_mutex_unlock(&statelist_cache_mutex);
2018 pthread_mutex_unlock(&book_of_work_mutex);
2019
2020 add_matching_states(current_candidates, 2*p, 2*r, ODD_STATE);
2021 if(current_candidates->len[ODD_STATE]) {
2022 // printf("Thread #%u: start working on even states q=%2d, s=%2d...\n", my_thread_number, q, s);
2023 add_matching_states(current_candidates, 2*q, 2*s, EVEN_STATE);
2024 } else { // no need to calculate even states yet
2025 pthread_mutex_lock(&statelist_cache_mutex);
2026 sl_cache[q][s][EVEN_STATE].cache_status = TO_BE_DONE;
2027 pthread_mutex_unlock(&statelist_cache_mutex);
2028 current_candidates->len[EVEN_STATE] = 0;
2029 current_candidates->states[EVEN_STATE] = NULL;
2030 }
2031 }
2032
2033 // update book of work
2034 pthread_mutex_lock(&book_of_work_mutex);
2035 book_of_work[p][q][r][s] = COMPLETED;
2036 pthread_mutex_unlock(&book_of_work_mutex);
2037
2038 // if ((uint64_t)current_candidates->len[ODD_STATE] * current_candidates->len[EVEN_STATE]) {
2039 // printf("Candidates for p=%2u, q=%2u, r=%2u, s=%2u: %" PRIu32 " * %" PRIu32 " = %" PRIu64 " (2^%0.1f)\n",
2040 // 2*p, 2*q, 2*r, 2*s, current_candidates->len[ODD_STATE], current_candidates->len[EVEN_STATE],
2041 // (uint64_t)current_candidates->len[ODD_STATE] * current_candidates->len[EVEN_STATE],
2042 // log((uint64_t)current_candidates->len[ODD_STATE] * current_candidates->len[EVEN_STATE])/log(2));
2043 // uint32_t estimated_odd = estimated_num_states_part_sum(best_first_bytes[0], p, r, ODD_STATE);
2044 // uint32_t estimated_even= estimated_num_states_part_sum(best_first_bytes[0], q, s, EVEN_STATE);
2045 // uint64_t estimated_total = (uint64_t)estimated_odd * estimated_even;
2046 // printf("Estimated: %" PRIu32 " * %" PRIu32 " = %" PRIu64 " (2^%0.1f)\n", estimated_odd, estimated_even, estimated_total, log(estimated_total) / log(2));
2047 // if (estimated_odd < current_candidates->len[ODD_STATE] || estimated_even < current_candidates->len[EVEN_STATE]) {
2048 // printf("############################################################################ERROR! ESTIMATED < REAL !!!\n");
2049 // //exit(2);
2050 // }
2051 // }
2052 }
2053 }
2054 }
2055 }
2056 }
2057 }
2058 } while (there_might_be_more_work);
2059
2060 return NULL;
2061 }
2062
2063
2064 static void generate_candidates(uint8_t sum_a0_idx, uint8_t sum_a8_idx)
2065 {
2066 // printf("Generating crypto1 state candidates... \n");
2067
2068 // estimate maximum candidate states
2069 // maximum_states = 0;
2070 // for (uint16_t sum_odd = 0; sum_odd <= 16; sum_odd += 2) {
2071 // for (uint16_t sum_even = 0; sum_even <= 16; sum_even += 2) {
2072 // if (sum_odd*(16-sum_even) + (16-sum_odd)*sum_even == sum_a0) {
2073 // maximum_states += (uint64_t)count_states(part_sum_a0_bitarrays[EVEN_STATE][sum_even/2])
2074 // * count_states(part_sum_a0_bitarrays[ODD_STATE][sum_odd/2]);
2075 // }
2076 // }
2077 // }
2078 // printf("Number of possible keys with Sum(a0) = %d: %" PRIu64 " (2^%1.1f)\n", sum_a0, maximum_states, log(maximum_states)/log(2.0));
2079
2080 init_statelist_cache();
2081 init_book_of_work();
2082
2083 // create mutexes for accessing the statelist cache and our "book of work"
2084 pthread_mutex_init(&statelist_cache_mutex, NULL);
2085 pthread_mutex_init(&book_of_work_mutex, NULL);
2086
2087 // create and run worker threads
2088 pthread_t thread_id[NUM_REDUCTION_WORKING_THREADS];
2089
2090 uint16_t sums[NUM_REDUCTION_WORKING_THREADS][3];
2091 for (uint16_t i = 0; i < NUM_REDUCTION_WORKING_THREADS; i++) {
2092 sums[i][0] = sum_a0_idx;
2093 sums[i][1] = sum_a8_idx;
2094 sums[i][2] = i+1;
2095 pthread_create(thread_id + i, NULL, generate_candidates_worker_thread, sums[i]);
2096 }
2097
2098 // wait for threads to terminate:
2099 for (uint16_t i = 0; i < NUM_REDUCTION_WORKING_THREADS; i++) {
2100 pthread_join(thread_id[i], NULL);
2101 }
2102
2103 // clean up mutex
2104 pthread_mutex_destroy(&statelist_cache_mutex);
2105
2106 maximum_states = 0;
2107 for (statelist_t *sl = candidates; sl != NULL; sl = sl->next) {
2108 maximum_states += (uint64_t)sl->len[ODD_STATE] * sl->len[EVEN_STATE];
2109 }
2110
2111 for (uint8_t i = 0; i < NUM_SUMS; i++) {
2112 if (nonces[best_first_bytes[0]].sum_a8_guess[i].sum_a8_idx == sum_a8_idx) {
2113 nonces[best_first_bytes[0]].sum_a8_guess[i].num_states = maximum_states;
2114 break;
2115 }
2116 }
2117 update_expected_brute_force(best_first_bytes[0]);
2118
2119 hardnested_print_progress(num_acquired_nonces, "Apply Sum(a8) and all bytes bitflip properties", nonces[best_first_bytes[0]].expected_num_brute_force, 0);
2120 }
2121
2122
2123 static void free_candidates_memory(statelist_t *sl)
2124 {
2125 if (sl == NULL) {
2126 return;
2127 } else {
2128 free_candidates_memory(sl->next);
2129 free(sl);
2130 }
2131 }
2132
2133
2134 static void pre_XOR_nonces(void)
2135 {
2136 // prepare acquired nonces for faster brute forcing.
2137
2138 // XOR the cryptoUID and its parity
2139 for (uint16_t i = 0; i < 256; i++) {
2140 noncelistentry_t *test_nonce = nonces[i].first;
2141 while (test_nonce != NULL) {
2142 test_nonce->nonce_enc ^= cuid;
2143 test_nonce->par_enc ^= oddparity8(cuid >> 0 & 0xff) << 0;
2144 test_nonce->par_enc ^= oddparity8(cuid >> 8 & 0xff) << 1;
2145 test_nonce->par_enc ^= oddparity8(cuid >> 16 & 0xff) << 2;
2146 test_nonce->par_enc ^= oddparity8(cuid >> 24 & 0xff) << 3;
2147 test_nonce = test_nonce->next;
2148 }
2149 }
2150 }
2151
2152
2153 static bool brute_force(void)
2154 {
2155 if (known_target_key != -1) {
2156 TestIfKeyExists(known_target_key);
2157 }
2158 return brute_force_bs(NULL, candidates, cuid, num_acquired_nonces, maximum_states, nonces, best_first_bytes);
2159 }
2160
2161
2162 static uint16_t SumProperty(struct Crypto1State *s)
2163 {
2164 uint16_t sum_odd = PartialSumProperty(s->odd, ODD_STATE);
2165 uint16_t sum_even = PartialSumProperty(s->even, EVEN_STATE);
2166 return (sum_odd*(16-sum_even) + (16-sum_odd)*sum_even);
2167 }
2168
2169
2170 static void Tests()
2171 {
2172
2173 /* #define NUM_STATISTICS 100000
2174 uint32_t statistics_odd[17];
2175 uint64_t statistics[257];
2176 uint32_t statistics_even[17];
2177 struct Crypto1State cs;
2178 uint64_t time1 = msclock();
2179
2180 for (uint16_t i = 0; i < 257; i++) {
2181 statistics[i] = 0;
2182 }
2183 for (uint16_t i = 0; i < 17; i++) {
2184 statistics_odd[i] = 0;
2185 statistics_even[i] = 0;
2186 }
2187
2188 for (uint64_t i = 0; i < NUM_STATISTICS; i++) {
2189 cs.odd = (rand() & 0xfff) << 12 | (rand() & 0xfff);
2190 cs.even = (rand() & 0xfff) << 12 | (rand() & 0xfff);
2191 uint16_t sum_property = SumProperty(&cs);
2192 statistics[sum_property] += 1;
2193 sum_property = PartialSumProperty(cs.even, EVEN_STATE);
2194 statistics_even[sum_property]++;
2195 sum_property = PartialSumProperty(cs.odd, ODD_STATE);
2196 statistics_odd[sum_property]++;
2197 if (i%(NUM_STATISTICS/100) == 0) printf(".");
2198 }
2199
2200 printf("\nTests: Calculated %d Sum properties in %0.3f seconds (%0.0f calcs/second)\n", NUM_STATISTICS, ((float)msclock() - time1)/1000.0, NUM_STATISTICS/((float)msclock() - time1)*1000.0);
2201 for (uint16_t i = 0; i < 257; i++) {
2202 if (statistics[i] != 0) {
2203 printf("probability[%3d] = %0.5f\n", i, (float)statistics[i]/NUM_STATISTICS);
2204 }
2205 }
2206 for (uint16_t i = 0; i <= 16; i++) {
2207 if (statistics_odd[i] != 0) {
2208 printf("probability odd [%2d] = %0.5f\n", i, (float)statistics_odd[i]/NUM_STATISTICS);
2209 }
2210 }
2211 for (uint16_t i = 0; i <= 16; i++) {
2212 if (statistics_odd[i] != 0) {
2213 printf("probability even [%2d] = %0.5f\n", i, (float)statistics_even[i]/NUM_STATISTICS);
2214 }
2215 }
2216 */
2217
2218 /* #define NUM_STATISTICS 100000000LL
2219 uint64_t statistics_a0[257];
2220 uint64_t statistics_a8[257][257];
2221 struct Crypto1State cs;
2222 uint64_t time1 = msclock();
2223
2224 for (uint16_t i = 0; i < 257; i++) {
2225 statistics_a0[i] = 0;
2226 for (uint16_t j = 0; j < 257; j++) {
2227 statistics_a8[i][j] = 0;
2228 }
2229 }
2230
2231 for (uint64_t i = 0; i < NUM_STATISTICS; i++) {
2232 cs.odd = (rand() & 0xfff) << 12 | (rand() & 0xfff);
2233 cs.even = (rand() & 0xfff) << 12 | (rand() & 0xfff);
2234 uint16_t sum_property_a0 = SumProperty(&cs);
2235 statistics_a0[sum_property_a0]++;
2236 uint8_t first_byte = rand() & 0xff;
2237 crypto1_byte(&cs, first_byte, true);
2238 uint16_t sum_property_a8 = SumProperty(&cs);
2239 statistics_a8[sum_property_a0][sum_property_a8] += 1;
2240 if (i%(NUM_STATISTICS/100) == 0) printf(".");
2241 }
2242
2243 printf("\nTests: Probability Distribution of a8 depending on a0:\n");
2244 printf("\n ");
2245 for (uint16_t i = 0; i < NUM_SUMS; i++) {
2246 printf("%7d ", sums[i]);
2247 }
2248 printf("\n-------------------------------------------------------------------------------------------------------------------------------------------\n");
2249 printf("a0: ");
2250 for (uint16_t i = 0; i < NUM_SUMS; i++) {
2251 printf("%7.5f ", (float)statistics_a0[sums[i]] / NUM_STATISTICS);
2252 }
2253 printf("\n");
2254 for (uint16_t i = 0; i < NUM_SUMS; i++) {
2255 printf("%3d ", sums[i]);
2256 for (uint16_t j = 0; j < NUM_SUMS; j++) {
2257 printf("%7.5f ", (float)statistics_a8[sums[i]][sums[j]] / statistics_a0[sums[i]]);
2258 }
2259 printf("\n");
2260 }
2261 printf("\nTests: Calculated %"lld" Sum properties in %0.3f seconds (%0.0f calcs/second)\n", NUM_STATISTICS, ((float)msclock() - time1)/1000.0, NUM_STATISTICS/((float)msclock() - time1)*1000.0);
2262 */
2263
2264 /* #define NUM_STATISTICS 100000LL
2265 uint64_t statistics_a8[257];
2266 struct Crypto1State cs;
2267 uint64_t time1 = msclock();
2268
2269 printf("\nTests: Probability Distribution of a8 depending on first byte:\n");
2270 printf("\n ");
2271 for (uint16_t i = 0; i < NUM_SUMS; i++) {
2272 printf("%7d ", sums[i]);
2273 }
2274 printf("\n-------------------------------------------------------------------------------------------------------------------------------------------\n");
2275 for (uint16_t first_byte = 0; first_byte < 256; first_byte++) {
2276 for (uint16_t i = 0; i < 257; i++) {
2277 statistics_a8[i] = 0;
2278 }
2279 for (uint64_t i = 0; i < NUM_STATISTICS; i++) {
2280 cs.odd = (rand() & 0xfff) << 12 | (rand() & 0xfff);
2281 cs.even = (rand() & 0xfff) << 12 | (rand() & 0xfff);
2282 crypto1_byte(&cs, first_byte, true);
2283 uint16_t sum_property_a8 = SumProperty(&cs);
2284 statistics_a8[sum_property_a8] += 1;
2285 }
2286 printf("%03x ", first_byte);
2287 for (uint16_t j = 0; j < NUM_SUMS; j++) {
2288 printf("%7.5f ", (float)statistics_a8[sums[j]] / NUM_STATISTICS);
2289 }
2290 printf("\n");
2291 }
2292 printf("\nTests: Calculated %"lld" Sum properties in %0.3f seconds (%0.0f calcs/second)\n", NUM_STATISTICS, ((float)msclock() - time1)/1000.0, NUM_STATISTICS/((float)msclock() - time1)*1000.0);
2293 */
2294
2295 /* printf("Tests: Sum Probabilities based on Partial Sums\n");
2296 for (uint16_t i = 0; i < 257; i++) {
2297 statistics[i] = 0;
2298 }
2299 uint64_t num_states = 0;
2300 for (uint16_t oddsum = 0; oddsum <= 16; oddsum += 2) {
2301 for (uint16_t evensum = 0; evensum <= 16; evensum += 2) {
2302 uint16_t sum = oddsum*(16-evensum) + (16-oddsum)*evensum;
2303 statistics[sum] += (uint64_t)partial_statelist[oddsum].len[ODD_STATE] * partial_statelist[evensum].len[EVEN_STATE] * (1<<8);
2304 num_states += (uint64_t)partial_statelist[oddsum].len[ODD_STATE] * partial_statelist[evensum].len[EVEN_STATE] * (1<<8);
2305 }
2306 }
2307 printf("num_states = %"lld", expected %"lld"\n", num_states, (1LL<<48));
2308 for (uint16_t i = 0; i < 257; i++) {
2309 if (statistics[i] != 0) {
2310 printf("probability[%3d] = %0.5f\n", i, (float)statistics[i]/num_states);
2311 }
2312 }
2313 */
2314
2315 /* struct Crypto1State *pcs;
2316 pcs = crypto1_create(0xffffffffffff);
2317 printf("\nTests: for key = 0xffffffffffff:\nSum(a0) = %d\nodd_state = 0x%06x\neven_state = 0x%06x\n",
2318 SumProperty(pcs), pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff);
2319 crypto1_byte(pcs, (cuid >> 24) ^ best_first_bytes[0], true);
2320 printf("After adding best first byte 0x%02x:\nSum(a8) = %d\nodd_state = 0x%06x\neven_state = 0x%06x\n",
2321 best_first_bytes[0],
2322 SumProperty(pcs),
2323 pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff);
2324 //test_state_odd = pcs->odd & 0x00ffffff;
2325 //test_state_even = pcs->even & 0x00ffffff;
2326 crypto1_destroy(pcs);
2327 pcs = crypto1_create(0xa0a1a2a3a4a5);
2328 printf("Tests: for key = 0xa0a1a2a3a4a5:\nSum(a0) = %d\nodd_state = 0x%06x\neven_state = 0x%06x\n",
2329 SumProperty(pcs), pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff);
2330 crypto1_byte(pcs, (cuid >> 24) ^ best_first_bytes[0], true);
2331 printf("After adding best first byte 0x%02x:\nSum(a8) = %d\nodd_state = 0x%06x\neven_state = 0x%06x\n",
2332 best_first_bytes[0],
2333 SumProperty(pcs),
2334 pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff);
2335 //test_state_odd = pcs->odd & 0x00ffffff;
2336 //test_state_even = pcs->even & 0x00ffffff;
2337 crypto1_destroy(pcs);
2338 pcs = crypto1_create(0xa6b9aa97b955);
2339 printf("Tests: for key = 0xa6b9aa97b955:\nSum(a0) = %d\nodd_state = 0x%06x\neven_state = 0x%06x\n",
2340 SumProperty(pcs), pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff);
2341 crypto1_byte(pcs, (cuid >> 24) ^ best_first_bytes[0], true);
2342 printf("After adding best first byte 0x%02x:\nSum(a8) = %d\nodd_state = 0x%06x\neven_state = 0x%06x\n",
2343 best_first_bytes[0],
2344 SumProperty(pcs),
2345 pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff);
2346 test_state_odd = pcs->odd & 0x00ffffff;
2347 test_state_even = pcs->even & 0x00ffffff;
2348 crypto1_destroy(pcs);
2349 */
2350
2351 // printf("\nTests: Sorted First Bytes:\n");
2352 // for (uint16_t i = 0; i < 20; i++) {
2353 // uint8_t best_byte = best_first_bytes[i];
2354 // //printf("#%03d Byte: %02x, n = %3d, k = %3d, Sum(a8): %3d, Confidence: %5.1f%%\n",
2355 // printf("#%03d Byte: %02x, n = %3d, k = %3d, Sum(a8) = ", i, best_byte, nonces[best_byte].num, nonces[best_byte].Sum);
2356 // for (uint16_t j = 0; j < 3; j++) {
2357 // printf("%3d @ %4.1f%%, ", sums[nonces[best_byte].sum_a8_guess[j].sum_a8_idx], nonces[best_byte].sum_a8_guess[j].prob * 100.0);
2358 // }
2359 // printf(" %12" PRIu64 ", %12" PRIu64 ", %12" PRIu64 ", exp_brute: %12.0f\n",
2360 // nonces[best_byte].sum_a8_guess[0].num_states,
2361 // nonces[best_byte].sum_a8_guess[1].num_states,
2362 // nonces[best_byte].sum_a8_guess[2].num_states,
2363 // nonces[best_byte].expected_num_brute_force);
2364 // }
2365
2366 // printf("\nTests: Actual BitFlipProperties of best byte:\n");
2367 // printf("[%02x]:", best_first_bytes[0]);
2368 // for (uint16_t bitflip_idx = 0; bitflip_idx < num_all_effective_bitflips; bitflip_idx++) {
2369 // uint16_t bitflip_prop = all_effective_bitflip[bitflip_idx];
2370 // if (nonces[best_first_bytes[0]].BitFlips[bitflip_prop]) {
2371 // printf(" %03" PRIx16 , bitflip_prop);
2372 // }
2373 // }
2374 // printf("\n");
2375
2376 // printf("\nTests2: Actual BitFlipProperties of first_byte_smallest_bitarray:\n");
2377 // printf("[%02x]:", best_first_byte_smallest_bitarray);
2378 // for (uint16_t bitflip_idx = 0; bitflip_idx < num_all_effective_bitflips; bitflip_idx++) {
2379 // uint16_t bitflip_prop = all_effective_bitflip[bitflip_idx];
2380 // if (nonces[best_first_byte_smallest_bitarray].BitFlips[bitflip_prop]) {
2381 // printf(" %03" PRIx16 , bitflip_prop);
2382 // }
2383 // }
2384 // printf("\n");
2385
2386 if (known_target_key != -1) {
2387 for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) {
2388 uint32_t *bitset = nonces[best_first_bytes[0]].states_bitarray[odd_even];
2389 if (!test_bit24(bitset, test_state[odd_even])) {
2390 printf("\nBUG: known target key's %s state is not member of first nonce byte's (0x%02x) states_bitarray!\n",
2391 odd_even==EVEN_STATE?"even":"odd ",
2392 best_first_bytes[0]);
2393 }
2394 }
2395 }
2396
2397 if (known_target_key != -1) {
2398 for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) {
2399 uint32_t *bitset = all_bitflips_bitarray[odd_even];
2400 if (!test_bit24(bitset, test_state[odd_even])) {
2401 printf("\nBUG: known target key's %s state is not member of all_bitflips_bitarray!\n",
2402 odd_even==EVEN_STATE?"even":"odd ");
2403 }
2404 }
2405 }
2406
2407 // if (known_target_key != -1) {
2408 // int16_t p = -1, q = -1, r = -1, s = -1;
2409
2410 // printf("\nTests: known target key is member of these partial sum_a0 bitsets:\n");
2411 // for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) {
2412 // printf("%s", odd_even==EVEN_STATE?"even:":"odd: ");
2413 // for (uint16_t i = 0; i < NUM_PART_SUMS; i++) {
2414 // uint32_t *bitset = part_sum_a0_bitarrays[odd_even][i];
2415 // if (test_bit24(bitset, test_state[odd_even])) {
2416 // printf("%d ", i);
2417 // if (odd_even == ODD_STATE) {
2418 // p = 2*i;
2419 // } else {
2420 // q = 2*i;
2421 // }
2422 // }
2423 // }
2424 // printf("\n");
2425 // }
2426
2427 // printf("\nTests: known target key is member of these partial sum_a8 bitsets:\n");
2428 // for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) {
2429 // printf("%s", odd_even==EVEN_STATE?"even:":"odd: ");
2430 // for (uint16_t i = 0; i < NUM_PART_SUMS; i++) {
2431 // uint32_t *bitset = part_sum_a8_bitarrays[odd_even][i];
2432 // if (test_bit24(bitset, test_state[odd_even])) {
2433 // printf("%d ", i);
2434 // if (odd_even == ODD_STATE) {
2435 // r = 2*i;
2436 // } else {
2437 // s = 2*i;
2438 // }
2439 // }
2440 // }
2441 // printf("\n");
2442 // }
2443
2444 // printf("Sum(a0) = p*(16-q) + (16-p)*q = %d*(16-%d) + (16-%d)*%d = %d\n", p, q, p, q, p*(16-q)+(16-p)*q);
2445 // printf("Sum(a8) = r*(16-s) + (16-r)*s = %d*(16-%d) + (16-%d)*%d = %d\n", r, s, r, s, r*(16-s)+(16-r)*s);
2446 // }
2447
2448 /* printf("\nTests: parity performance\n");
2449 uint64_t time1p = msclock();
2450 uint32_t par_sum = 0;
2451 for (uint32_t i = 0; i < 100000000; i++) {
2452 par_sum += parity(i);
2453 }
2454 printf("parsum oldparity = %d, time = %1.5fsec\n", par_sum, (float)(msclock() - time1p)/1000.0);
2455
2456 time1p = msclock();
2457 par_sum = 0;
2458 for (uint32_t i = 0; i < 100000000; i++) {
2459 par_sum += evenparity32(i);
2460 }
2461 printf("parsum newparity = %d, time = %1.5fsec\n", par_sum, (float)(msclock() - time1p)/1000.0);
2462 */
2463
2464 }
2465
2466
2467 static void Tests2(void)
2468 {
2469 if (known_target_key != -1) {
2470 for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) {
2471 uint32_t *bitset = nonces[best_first_byte_smallest_bitarray].states_bitarray[odd_even];
2472 if (!test_bit24(bitset, test_state[odd_even])) {
2473 printf("\nBUG: known target key's %s state is not member of first nonce byte's (0x%02x) states_bitarray!\n",
2474 odd_even==EVEN_STATE?"even":"odd ",
2475 best_first_byte_smallest_bitarray);
2476 }
2477 }
2478 }
2479
2480 if (known_target_key != -1) {
2481 for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) {
2482 uint32_t *bitset = all_bitflips_bitarray[odd_even];
2483 if (!test_bit24(bitset, test_state[odd_even])) {
2484 printf("\nBUG: known target key's %s state is not member of all_bitflips_bitarray!\n",
2485 odd_even==EVEN_STATE?"even":"odd ");
2486 }
2487 }
2488 }
2489
2490 }
2491
2492
2493 static uint16_t real_sum_a8 = 0;
2494
2495 static void set_test_state(uint8_t byte)
2496 {
2497 struct Crypto1State *pcs;
2498 pcs = crypto1_create(known_target_key);
2499 crypto1_byte(pcs, (cuid >> 24) ^ byte, true);
2500 test_state[ODD_STATE] = pcs->odd & 0x00ffffff;
2501 test_state[EVEN_STATE] = pcs->even & 0x00ffffff;
2502 real_sum_a8 = SumProperty(pcs);
2503 crypto1_destroy(pcs);
2504 }
2505
2506
2507 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)
2508 {
2509 char progress_text[80];
2510
2511 char instr_set[12] = {0};
2512 get_SIMD_instruction_set(instr_set);
2513 PrintAndLog("Using %s SIMD core.", instr_set);
2514
2515 srand((unsigned) time(NULL));
2516 brute_force_per_second = brute_force_benchmark();
2517 write_stats = false;
2518
2519 if (tests) {
2520 // set the correct locale for the stats printing
2521 write_stats = true;
2522 setlocale(LC_NUMERIC, "");
2523 if ((fstats = fopen("hardnested_stats.txt","a")) == NULL) {
2524 PrintAndLog("Could not create/open file hardnested_stats.txt");
2525 return 3;
2526 }
2527 for (uint32_t i = 0; i < tests; i++) {
2528 start_time = msclock();
2529 print_progress_header();
2530 sprintf(progress_text, "Brute force benchmark: %1.0f million (2^%1.1f) keys/s", brute_force_per_second/1000000, log(brute_force_per_second)/log(2.0));
2531 hardnested_print_progress(0, progress_text, (float)(1LL<<47), 0);
2532 sprintf(progress_text, "Starting Test #%" PRIu32 " ...", i+1);
2533 hardnested_print_progress(0, progress_text, (float)(1LL<<47), 0);
2534 if (trgkey != NULL) {
2535 known_target_key = bytes_to_num(trgkey, 6);
2536 } else {
2537 known_target_key = -1;
2538 }
2539
2540 init_bitflip_bitarrays();
2541 init_part_sum_bitarrays();
2542 init_sum_bitarrays();
2543 init_allbitflips_array();
2544 init_nonce_memory();
2545 update_reduction_rate(0.0, true);
2546
2547 simulate_acquire_nonces();
2548
2549 set_test_state(best_first_bytes[0]);
2550
2551 Tests();
2552 free_bitflip_bitarrays();
2553
2554 fprintf(fstats, "%" PRIu16 ";%1.1f;", sums[first_byte_Sum], log(p_K0[first_byte_Sum])/log(2.0));
2555 fprintf(fstats, "%" PRIu16 ";%1.1f;", sums[nonces[best_first_bytes[0]].sum_a8_guess[0].sum_a8_idx], log(p_K[nonces[best_first_bytes[0]].sum_a8_guess[0].sum_a8_idx])/log(2.0));
2556 fprintf(fstats, "%" PRIu16 ";", real_sum_a8);
2557
2558 #ifdef DEBUG_KEY_ELIMINATION
2559 failstr[0] = '\0';
2560 #endif
2561 bool key_found = false;
2562 num_keys_tested = 0;
2563 uint32_t num_odd = nonces[best_first_byte_smallest_bitarray].num_states_bitarray[ODD_STATE];
2564 uint32_t num_even = nonces[best_first_byte_smallest_bitarray].num_states_bitarray[EVEN_STATE];
2565 float expected_brute_force1 = (float)num_odd * num_even / 2.0;
2566 float expected_brute_force2 = nonces[best_first_bytes[0]].expected_num_brute_force;
2567 fprintf(fstats, "%1.1f;%1.1f;", log(expected_brute_force1)/log(2.0), log(expected_brute_force2)/log(2.0));
2568 if (expected_brute_force1 < expected_brute_force2) {
2569 hardnested_print_progress(num_acquired_nonces, "(Ignoring Sum(a8) properties)", expected_brute_force1, 0);
2570 set_test_state(best_first_byte_smallest_bitarray);
2571 add_bitflip_candidates(best_first_byte_smallest_bitarray);
2572 Tests2();
2573 maximum_states = 0;
2574 for (statelist_t *sl = candidates; sl != NULL; sl = sl->next) {
2575 maximum_states += (uint64_t)sl->len[ODD_STATE] * sl->len[EVEN_STATE];
2576 }
2577 //printf("Number of remaining possible keys: %" PRIu64 " (2^%1.1f)\n", maximum_states, log(maximum_states)/log(2.0));
2578 // fprintf("fstats, "%" PRIu64 ";", maximum_states);
2579 best_first_bytes[0] = best_first_byte_smallest_bitarray;
2580 pre_XOR_nonces();
2581 prepare_bf_test_nonces(nonces, best_first_bytes[0]);
2582 hardnested_print_progress(num_acquired_nonces, "Starting brute force...", expected_brute_force1, 0);
2583 key_found = brute_force();
2584 free(candidates->states[ODD_STATE]);
2585 free(candidates->states[EVEN_STATE]);
2586 free_candidates_memory(candidates);
2587 candidates = NULL;
2588 } else {
2589 pre_XOR_nonces();
2590 prepare_bf_test_nonces(nonces, best_first_bytes[0]);
2591 for (uint8_t j = 0; j < NUM_SUMS && !key_found; j++) {
2592 float expected_brute_force = nonces[best_first_bytes[0]].expected_num_brute_force;
2593 sprintf(progress_text, "(%d. guess: Sum(a8) = %" PRIu16 ")", j+1, sums[nonces[best_first_bytes[0]].sum_a8_guess[j].sum_a8_idx]);
2594 hardnested_print_progress(num_acquired_nonces, progress_text, expected_brute_force, 0);
2595 if (sums[nonces[best_first_bytes[0]].sum_a8_guess[j].sum_a8_idx] != real_sum_a8) {
2596 sprintf(progress_text, "(Estimated Sum(a8) is WRONG! Correct Sum(a8) = %" PRIu16 ")", real_sum_a8);
2597 hardnested_print_progress(num_acquired_nonces, progress_text, expected_brute_force, 0);
2598 }
2599 // printf("Estimated remaining states: %" PRIu64 " (2^%1.1f)\n", nonces[best_first_bytes[0]].sum_a8_guess[j].num_states, log(nonces[best_first_bytes[0]].sum_a8_guess[j].num_states)/log(2.0));
2600 generate_candidates(first_byte_Sum, nonces[best_first_bytes[0]].sum_a8_guess[j].sum_a8_idx);
2601 // printf("Time for generating key candidates list: %1.0f sec (%1.1f sec CPU)\n", difftime(time(NULL), start_time), (float)(msclock() - start_clock)/1000.0);
2602 hardnested_print_progress(num_acquired_nonces, "Starting brute force...", expected_brute_force, 0);
2603 key_found = brute_force();
2604 free_statelist_cache();
2605 free_candidates_memory(candidates);
2606 candidates = NULL;
2607 if (!key_found) {
2608 // update the statistics
2609 nonces[best_first_bytes[0]].sum_a8_guess[j].prob = 0;
2610 nonces[best_first_bytes[0]].sum_a8_guess[j].num_states = 0;
2611 // and calculate new expected number of brute forces
2612 update_expected_brute_force(best_first_bytes[0]);
2613 }
2614 }
2615 }
2616 #ifdef DEBUG_KEY_ELIMINATION
2617 fprintf(fstats, "%1.1f;%1.0f;%d;%s\n", log(num_keys_tested)/log(2.0), (float)num_keys_tested/brute_force_per_second, key_found, failstr);
2618 #else
2619 fprintf(fstats, "%1.0f;%d\n", log(num_keys_tested)/log(2.0), (float)num_keys_tested/brute_force_per_second, key_found);
2620 #endif
2621
2622 free_nonces_memory();
2623 free_bitarray(all_bitflips_bitarray[ODD_STATE]);
2624 free_bitarray(all_bitflips_bitarray[EVEN_STATE]);
2625 free_sum_bitarrays();
2626 free_part_sum_bitarrays();
2627 }
2628 fclose(fstats);
2629 } else {
2630 start_time = msclock();
2631 print_progress_header();
2632 sprintf(progress_text, "Brute force benchmark: %1.0f million (2^%1.1f) keys/s", brute_force_per_second/1000000, log(brute_force_per_second)/log(2.0));
2633 hardnested_print_progress(0, progress_text, (float)(1LL<<47), 0);
2634 init_bitflip_bitarrays();
2635 init_part_sum_bitarrays();
2636 init_sum_bitarrays();
2637 init_allbitflips_array();
2638 init_nonce_memory();
2639 update_reduction_rate(0.0, true);
2640
2641 if (nonce_file_read) { // use pre-acquired data from file nonces.bin
2642 if (read_nonce_file() != 0) {
2643 free_bitflip_bitarrays();
2644 free_nonces_memory();
2645 free_bitarray(all_bitflips_bitarray[ODD_STATE]);
2646 free_bitarray(all_bitflips_bitarray[EVEN_STATE]);
2647 free_sum_bitarrays();
2648 free_part_sum_bitarrays();
2649 return 3;
2650 }
2651 hardnested_stage = CHECK_1ST_BYTES | CHECK_2ND_BYTES;
2652 update_nonce_data(false);
2653 float brute_force;
2654 shrink_key_space(&brute_force);
2655 } else { // acquire nonces.
2656 uint16_t is_OK = acquire_nonces(blockNo, keyType, key, trgBlockNo, trgKeyType, nonce_file_write, slow);
2657 if (is_OK != 0) {
2658 free_bitflip_bitarrays();
2659 free_nonces_memory();
2660 free_bitarray(all_bitflips_bitarray[ODD_STATE]);
2661 free_bitarray(all_bitflips_bitarray[EVEN_STATE]);
2662 free_sum_bitarrays();
2663 free_part_sum_bitarrays();
2664 return is_OK;
2665 }
2666 }
2667
2668 if (trgkey != NULL) {
2669 known_target_key = bytes_to_num(trgkey, 6);
2670 set_test_state(best_first_bytes[0]);
2671 } else {
2672 known_target_key = -1;
2673 }
2674
2675 Tests();
2676
2677 free_bitflip_bitarrays();
2678 bool key_found = false;
2679 num_keys_tested = 0;
2680 uint32_t num_odd = nonces[best_first_byte_smallest_bitarray].num_states_bitarray[ODD_STATE];
2681 uint32_t num_even = nonces[best_first_byte_smallest_bitarray].num_states_bitarray[EVEN_STATE];
2682 float expected_brute_force1 = (float)num_odd * num_even / 2.0;
2683 float expected_brute_force2 = nonces[best_first_bytes[0]].expected_num_brute_force;
2684 if (expected_brute_force1 < expected_brute_force2) {
2685 hardnested_print_progress(num_acquired_nonces, "(Ignoring Sum(a8) properties)", expected_brute_force1, 0);
2686 set_test_state(best_first_byte_smallest_bitarray);
2687 add_bitflip_candidates(best_first_byte_smallest_bitarray);
2688 Tests2();
2689 maximum_states = 0;
2690 for (statelist_t *sl = candidates; sl != NULL; sl = sl->next) {
2691 maximum_states += (uint64_t)sl->len[ODD_STATE] * sl->len[EVEN_STATE];
2692 }
2693 // printf("Number of remaining possible keys: %" PRIu64 " (2^%1.1f)\n", maximum_states, log(maximum_states)/log(2.0));
2694 best_first_bytes[0] = best_first_byte_smallest_bitarray;
2695 pre_XOR_nonces();
2696 prepare_bf_test_nonces(nonces, best_first_bytes[0]);
2697 hardnested_print_progress(num_acquired_nonces, "Starting brute force...", expected_brute_force1, 0);
2698 key_found = brute_force();
2699 free(candidates->states[ODD_STATE]);
2700 free(candidates->states[EVEN_STATE]);
2701 free_candidates_memory(candidates);
2702 candidates = NULL;
2703 } else {
2704 pre_XOR_nonces();
2705 prepare_bf_test_nonces(nonces, best_first_bytes[0]);
2706 for (uint8_t j = 0; j < NUM_SUMS && !key_found; j++) {
2707 float expected_brute_force = nonces[best_first_bytes[0]].expected_num_brute_force;
2708 sprintf(progress_text, "(%d. guess: Sum(a8) = %" PRIu16 ")", j+1, sums[nonces[best_first_bytes[0]].sum_a8_guess[j].sum_a8_idx]);
2709 hardnested_print_progress(num_acquired_nonces, progress_text, expected_brute_force, 0);
2710 if (trgkey != NULL && sums[nonces[best_first_bytes[0]].sum_a8_guess[j].sum_a8_idx] != real_sum_a8) {
2711 sprintf(progress_text, "(Estimated Sum(a8) is WRONG! Correct Sum(a8) = %" PRIu16 ")", real_sum_a8);
2712 hardnested_print_progress(num_acquired_nonces, progress_text, expected_brute_force, 0);
2713 }
2714 // printf("Estimated remaining states: %" PRIu64 " (2^%1.1f)\n", nonces[best_first_bytes[0]].sum_a8_guess[j].num_states, log(nonces[best_first_bytes[0]].sum_a8_guess[j].num_states)/log(2.0));
2715 generate_candidates(first_byte_Sum, nonces[best_first_bytes[0]].sum_a8_guess[j].sum_a8_idx);
2716 // printf("Time for generating key candidates list: %1.0f sec (%1.1f sec CPU)\n", difftime(time(NULL), start_time), (float)(msclock() - start_clock)/1000.0);
2717 hardnested_print_progress(num_acquired_nonces, "Starting brute force...", expected_brute_force, 0);
2718 key_found = brute_force();
2719 free_statelist_cache();
2720 free_candidates_memory(candidates);
2721 candidates = NULL;
2722 if (!key_found) {
2723 // update the statistics
2724 nonces[best_first_bytes[0]].sum_a8_guess[j].prob = 0;
2725 nonces[best_first_bytes[0]].sum_a8_guess[j].num_states = 0;
2726 // and calculate new expected number of brute forces
2727 update_expected_brute_force(best_first_bytes[0]);
2728 }
2729
2730 }
2731 }
2732
2733 free_nonces_memory();
2734 free_bitarray(all_bitflips_bitarray[ODD_STATE]);
2735 free_bitarray(all_bitflips_bitarray[EVEN_STATE]);
2736 free_sum_bitarrays();
2737 free_part_sum_bitarrays();
2738 }
2739
2740 return 0;
2741 }
Proxmark3 GIT tracking
Impressum, Datenschutz