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