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


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