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