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