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


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