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