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