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


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