1 //-----------------------------------------------------------------------------
2 // Copyright (C) 2015, 2016 by piwi
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
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 //-----------------------------------------------------------------------------
17 #include "cmdhfmfhard.h"
27 #include "proxmark3.h"
32 #include "util_posix.h"
33 #include "crapto1/crapto1.h"
35 #include "hardnested/hardnested_bruteforce.h"
36 #include "hardnested/hardnested_bf_core.h"
37 #include "hardnested/hardnested_bitarray_core.h"
40 #define NUM_CHECK_BITFLIPS_THREADS (num_CPUs())
41 #define NUM_REDUCTION_WORKING_THREADS (num_CPUs())
43 #define IGNORE_BITFLIP_THRESHOLD 0.99 // ignore bitflip arrays which have nearly only valid states
45 #define STATE_FILES_DIRECTORY "hardnested/tables/"
46 #define STATE_FILE_TEMPLATE "bitflip_%d_%03" PRIx16 "_states.bin.z"
48 #define DEBUG_KEY_ELIMINATION
49 // #define DEBUG_REDUCTION
51 static uint16_t sums
[NUM_SUMS
] = {0, 32, 56, 64, 80, 96, 104, 112, 120, 128, 136, 144, 152, 160, 176, 192, 200, 224, 256}; // possible sum property values
53 #define NUM_PART_SUMS 9 // number of possible partial sum property values
60 static uint32_t num_acquired_nonces
= 0;
61 static uint64_t start_time
= 0;
62 static uint16_t effective_bitflip
[2][0x400];
63 static uint16_t num_effective_bitflips
[2] = {0, 0};
64 static uint16_t all_effective_bitflip
[0x400];
65 static uint16_t num_all_effective_bitflips
= 0;
66 static uint16_t num_1st_byte_effective_bitflips
= 0;
67 #define CHECK_1ST_BYTES 0x01
68 #define CHECK_2ND_BYTES 0x02
69 static uint8_t hardnested_stage
= CHECK_1ST_BYTES
;
70 static uint64_t known_target_key
;
71 static uint32_t test_state
[2] = {0,0};
72 static float brute_force_per_second
;
75 static void get_SIMD_instruction_set(char* instruction_set
) {
76 switch(GetSIMDInstrAuto()) {
78 strcpy(instruction_set
, "AVX512F");
81 strcpy(instruction_set
, "AVX2");
84 strcpy(instruction_set
, "AVX");
87 strcpy(instruction_set
, "SSE2");
90 strcpy(instruction_set
, "MMX");
93 strcpy(instruction_set
, "no");
99 static void print_progress_header(void) {
100 char progress_text
[80];
101 char instr_set
[12] = {0};
102 get_SIMD_instruction_set(instr_set
);
103 sprintf(progress_text
, "Start using %d threads and %s SIMD core", num_CPUs(), instr_set
);
105 PrintAndLog(" time | #nonces | Activity | expected to brute force");
106 PrintAndLog(" | | | #states | time ");
107 PrintAndLog("------------------------------------------------------------------------------------------------------");
108 PrintAndLog(" 0 | 0 | %-55s | |", progress_text
);
112 void hardnested_print_progress(uint32_t nonces
, char *activity
, float brute_force
, uint64_t min_diff_print_time
) {
113 static uint64_t last_print_time
= 0;
114 if (msclock() - last_print_time
> min_diff_print_time
) {
115 last_print_time
= msclock();
116 uint64_t total_time
= msclock() - start_time
;
117 float brute_force_time
= brute_force
/ brute_force_per_second
;
118 char brute_force_time_string
[20];
119 if (brute_force_time
< 90) {
120 sprintf(brute_force_time_string
, "%2.0fs", brute_force_time
);
121 } else if (brute_force_time
< 60 * 90) {
122 sprintf(brute_force_time_string
, "%2.0fmin", brute_force_time
/60);
123 } else if (brute_force_time
< 60 * 60 * 36) {
124 sprintf(brute_force_time_string
, "%2.0fh", brute_force_time
/(60*60));
126 sprintf(brute_force_time_string
, "%2.0fd", brute_force_time
/(60*60*24));
128 PrintAndLog(" %7.0f | %7d | %-55s | %15.0f | %5s", (float)total_time
/1000.0, nonces
, activity
, brute_force
, brute_force_time_string
);
133 //////////////////////////////////////////////////////////////////////////////////////////////////////////////////
134 // bitarray functions
136 static inline void clear_bitarray24(uint32_t *bitarray
)
138 memset(bitarray
, 0x00, sizeof(uint32_t) * (1<<19));
142 static inline void set_bitarray24(uint32_t *bitarray
)
144 memset(bitarray
, 0xff, sizeof(uint32_t) * (1<<19));
148 static inline void set_bit24(uint32_t *bitarray
, uint32_t index
)
150 bitarray
[index
>>5] |= 0x80000000>>(index
&0x0000001f);
154 static inline uint32_t test_bit24(uint32_t *bitarray
, uint32_t index
)
156 return bitarray
[index
>>5] & (0x80000000>>(index
&0x0000001f));
160 static inline uint32_t next_state(uint32_t *bitarray
, uint32_t state
)
162 if (++state
== 1<<24) return 1<<24;
163 uint32_t index
= state
>> 5;
164 uint_fast8_t bit
= state
& 0x1f;
165 uint32_t line
= bitarray
[index
] << bit
;
166 while (bit
<= 0x1f) {
167 if (line
& 0x80000000) return state
;
173 while (bitarray
[index
] == 0x00000000 && state
< 1<<24) {
177 if (state
>= 1<<24) return 1<<24;
179 return state
+ __builtin_clz(bitarray
[index
]);
182 line
= bitarray
[index
];
183 while (bit
<= 0x1f) {
184 if (line
& 0x80000000) return state
;
196 #define BITFLIP_2ND_BYTE 0x0200
199 //////////////////////////////////////////////////////////////////////////////////////////////////////////////////
200 // bitflip property bitarrays
202 static uint32_t *bitflip_bitarrays
[2][0x400];
203 static uint32_t count_bitflip_bitarrays
[2][0x400];
205 static int compare_count_bitflip_bitarrays(const void *b1
, const void *b2
)
207 uint64_t count1
= (uint64_t)count_bitflip_bitarrays
[ODD_STATE
][*(uint16_t *)b1
] * count_bitflip_bitarrays
[EVEN_STATE
][*(uint16_t *)b1
];
208 uint64_t count2
= (uint64_t)count_bitflip_bitarrays
[ODD_STATE
][*(uint16_t *)b2
] * count_bitflip_bitarrays
[EVEN_STATE
][*(uint16_t *)b2
];
209 return (count1
> count2
) - (count2
> count1
);
213 static voidpf
inflate_malloc(voidpf opaque
, uInt items
, uInt size
)
215 return malloc(items
*size
);
219 static void inflate_free(voidpf opaque
, voidpf address
)
224 #define OUTPUT_BUFFER_LEN 80
225 #define INPUT_BUFFER_LEN 80
227 //----------------------------------------------------------------------------
228 // Initialize decompression of the respective (HF or LF) FPGA stream
229 //----------------------------------------------------------------------------
230 static void init_inflate(z_streamp compressed_stream
, uint8_t *input_buffer
, uint32_t insize
, uint8_t *output_buffer
, uint32_t outsize
)
233 // initialize z_stream structure for inflate:
234 compressed_stream
->next_in
= input_buffer
;
235 compressed_stream
->avail_in
= insize
;
236 compressed_stream
->next_out
= output_buffer
;
237 compressed_stream
->avail_out
= outsize
;
238 compressed_stream
->zalloc
= &inflate_malloc
;
239 compressed_stream
->zfree
= &inflate_free
;
241 inflateInit2(compressed_stream
, 0);
246 static void init_bitflip_bitarrays(void)
248 #if defined (DEBUG_REDUCTION)
253 z_stream compressed_stream
;
255 char state_files_path
[strlen(get_my_executable_directory()) + strlen(STATE_FILES_DIRECTORY
) + strlen(STATE_FILE_TEMPLATE
) + 1];
256 char state_file_name
[strlen(STATE_FILE_TEMPLATE
)+1];
258 for (odd_even_t odd_even
= EVEN_STATE
; odd_even
<= ODD_STATE
; odd_even
++) {
259 num_effective_bitflips
[odd_even
] = 0;
260 for (uint16_t bitflip
= 0x001; bitflip
< 0x400; bitflip
++) {
261 bitflip_bitarrays
[odd_even
][bitflip
] = NULL
;
262 count_bitflip_bitarrays
[odd_even
][bitflip
] = 1<<24;
263 sprintf(state_file_name
, STATE_FILE_TEMPLATE
, odd_even
, bitflip
);
264 strcpy(state_files_path
, get_my_executable_directory());
265 strcat(state_files_path
, STATE_FILES_DIRECTORY
);
266 strcat(state_files_path
, state_file_name
);
267 FILE *statesfile
= fopen(state_files_path
, "rb");
268 if (statesfile
== NULL
) {
271 fseek(statesfile
, 0, SEEK_END
);
272 uint32_t filesize
= (uint32_t)ftell(statesfile
);
274 uint8_t input_buffer
[filesize
];
275 size_t bytesread
= fread(input_buffer
, 1, filesize
, statesfile
);
276 if (bytesread
!= filesize
) {
277 printf("File read error with %s. Aborting...\n", state_file_name
);
283 init_inflate(&compressed_stream
, input_buffer
, filesize
, (uint8_t *)&count
, sizeof(count
));
284 inflate(&compressed_stream
, Z_SYNC_FLUSH
);
285 if ((float)count
/(1<<24) < IGNORE_BITFLIP_THRESHOLD
) {
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
);
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
);
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);
307 inflateEnd(&compressed_stream
);
310 effective_bitflip
[odd_even
][num_effective_bitflips
[odd_even
]] = 0x400; // EndOfList marker
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
];
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
];
325 all_effective_bitflip
[num_all_effective_bitflips
++] = effective_bitflip
[EVEN_STATE
][i
];
328 if (!(all_effective_bitflip
[num_all_effective_bitflips
-1] & BITFLIP_2ND_BYTE
)) {
329 num_1st_byte_effective_bitflips
= num_all_effective_bitflips
;
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
]);
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
]);
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);
352 static void free_bitflip_bitarrays(void)
354 for (int16_t bitflip
= 0x3ff; bitflip
> 0x000; bitflip
--) {
355 free_bitarray(bitflip_bitarrays
[ODD_STATE
][bitflip
]);
357 for (int16_t bitflip
= 0x3ff; bitflip
> 0x000; bitflip
--) {
358 free_bitarray(bitflip_bitarrays
[EVEN_STATE
][bitflip
]);
363 //////////////////////////////////////////////////////////////////////////////////////////////////////////////////
364 // sum property bitarrays
366 static uint32_t *part_sum_a0_bitarrays
[2][NUM_PART_SUMS
];
367 static uint32_t *part_sum_a8_bitarrays
[2][NUM_PART_SUMS
];
368 static uint32_t *sum_a0_bitarrays
[2][NUM_SUMS
];
370 static uint16_t PartialSumProperty(uint32_t state
, odd_even_t odd_even
)
373 for (uint16_t j
= 0; j
< 16; j
++) {
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) ;
381 part_sum
^= 1; // XOR 1 cancelled out for the other 8 bits
383 for (uint16_t i
= 0; i
< 4; i
++) {
384 st
= (st
<< 1) | ((j
>> (3-i
)) & 0x01) ;
385 part_sum
^= filter(st
);
394 static void init_part_sum_bitarrays(void)
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");
403 clear_bitarray24(part_sum_a0_bitarrays
[odd_even
][part_sum_a0
]);
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
);
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");
423 clear_bitarray24(part_sum_a8_bitarrays
[odd_even
][part_sum_a8
]);
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);
438 static void free_part_sum_bitarrays(void)
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
]);
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
]);
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
]);
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
]);
455 static void init_sum_bitarrays(void)
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");
464 clear_bitarray24(sum_a0_bitarrays
[odd_even
][sum_a0
]);
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
]);
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);
485 static void free_sum_bitarrays(void)
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
]);
494 #ifdef DEBUG_KEY_ELIMINATION
495 char failstr
[250] = "";
498 static 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
502 static float my_p_K
[NUM_SUMS
];
504 static const float *p_K
;
506 static uint32_t cuid
;
507 static noncelist_t nonces
[256];
508 static uint8_t best_first_bytes
[256];
509 static uint64_t maximum_states
= 0;
510 static uint8_t best_first_byte_smallest_bitarray
= 0;
511 static uint16_t first_byte_Sum
= 0;
512 static uint16_t first_byte_num
= 0;
513 static bool write_stats
= false;
514 static FILE *fstats
= NULL
;
515 static uint32_t *all_bitflips_bitarray
[2];
516 static uint32_t num_all_bitflips_bitarray
[2];
517 static bool all_bitflips_bitarray_dirty
[2];
518 static uint64_t last_sample_clock
= 0;
519 static uint64_t sample_period
= 0;
520 static uint64_t num_keys_tested
= 0;
521 static statelist_t
*candidates
= NULL
;
524 static int add_nonce(uint32_t nonce_enc
, uint8_t par_enc
)
526 uint8_t first_byte
= nonce_enc
>> 24;
527 noncelistentry_t
*p1
= nonces
[first_byte
].first
;
528 noncelistentry_t
*p2
= NULL
;
530 if (p1
== NULL
) { // first nonce with this 1st byte
532 first_byte_Sum
+= evenparity32((nonce_enc
& 0xff000000) | (par_enc
& 0x08));
535 while (p1
!= NULL
&& (p1
->nonce_enc
& 0x00ff0000) < (nonce_enc
& 0x00ff0000)) {
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
));
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
));
550 p2
= p2
->next
= malloc(sizeof(noncelistentry_t
));
552 } else { // we have seen this 2nd byte before. Nothing to add or insert.
556 // add or insert new data
558 p2
->nonce_enc
= nonce_enc
;
559 p2
->par_enc
= par_enc
;
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
568 static void init_nonce_memory(void)
570 for (uint16_t i
= 0; i
< 256; i
++) {
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;
578 nonces
[i
].sum_a8_guess_dirty
= false;
579 for (uint16_t bitflip
= 0x000; bitflip
< 0x400; bitflip
++) {
580 nonces
[i
].BitFlips
[bitflip
] = 0;
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");
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");
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;
604 static void free_nonce_list(noncelistentry_t
*p
)
609 free_nonce_list(p
->next
);
615 static void free_nonces_memory(void)
617 for (uint16_t i
= 0; i
< 256; i
++) {
618 free_nonce_list(nonces
[i
].first
);
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
]);
627 // static double p_hypergeometric_cache[257][NUM_SUMS][257];
629 // #define CACHE_INVALID -1.0
630 // static void init_p_hypergeometric_cache(void)
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;
642 static double p_hypergeometric(uint16_t i_K
, uint16_t n
, uint16_t k
)
644 // for efficient computation we are using the recursive definition
646 // P(X=k) = P(X=k-1) * --------------------
649 // (N-K)*(N-K-1)*...*(N-K-n+1)
650 // P(X=0) = -----------------------------
651 // N*(N-1)*...*(N-n+1)
654 uint16_t const N
= 256;
655 uint16_t K
= sums
[i_K
];
657 // if (p_hypergeometric_cache[n][i_K][k] != CACHE_INVALID) {
658 // return p_hypergeometric_cache[n][i_K][k];
661 if (n
-k
> N
-K
|| k
> K
) return 0.0; // avoids log(x<=0) in calculation below
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
);
668 for (int16_t i
= N
; i
>= N
-n
+1; i
--) {
669 log_result
-= log(i
);
671 // p_hypergeometric_cache[n][i_K][k] = exp(log_result);
672 return exp(log_result
);
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
);
679 for (int16_t i
= K
+1; i
<= N
; i
++) {
680 log_result
-= log(i
);
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
)));
691 static float sum_probability(uint16_t i_K
, uint16_t n
, uint16_t k
)
693 if (k
> sums
[i_K
]) return 0.0;
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
];
698 for (uint16_t i
= 0; i
< NUM_SUMS
; i
++) {
699 p_T_is_k
+= p_K
[i
] * p_hypergeometric(i
, n
, k
);
701 return(p_T_is_k_when_S_is_K
* p_S_is_K
/ p_T_is_k
);
705 static uint32_t part_sum_count
[2][NUM_PART_SUMS
][NUM_PART_SUMS
];
707 static void init_allbitflips_array(void)
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...");
715 set_bitarray24(bitset
);
716 all_bitflips_bitarray_dirty
[odd_even
] = false;
717 num_all_bitflips_bitarray
[odd_even
] = 1<<24;
722 static void update_allbitflips_array(void)
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;
741 static uint32_t estimated_num_states_part_sum_coarse(uint16_t part_sum_a0_idx
, uint16_t part_sum_a8_idx
, odd_even_t odd_even
)
743 return part_sum_count
[odd_even
][part_sum_a0_idx
][part_sum_a8_idx
];
747 static uint32_t estimated_num_states_part_sum(uint8_t first_byte
, uint16_t part_sum_a0_idx
, uint16_t part_sum_a8_idx
, odd_even_t odd_even
)
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
]);
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
]);
760 // estimate reduction by all_bitflips_match()
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);
770 static uint64_t estimated_num_states(uint8_t first_byte
, uint16_t sum_a0
, uint16_t sum_a8
)
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
);
791 static uint64_t estimated_num_states_coarse(uint16_t sum_a0
, uint16_t sum_a8
)
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
);
812 static void update_p_K(void)
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
);
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
;
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]);
834 static void update_sum_bitarrays(odd_even_t odd_even
)
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
]);
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
]);
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
]);
850 all_bitflips_bitarray_dirty
[odd_even
] = false;
855 static int compare_expected_num_brute_force(const void *b1
, const void *b2
)
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
);
865 static int compare_sum_a8_guess(const void *b1
, const void *b2
)
867 float prob1
= ((guess_sum_a8_t
*)b1
)->prob
;
868 float prob2
= ((guess_sum_a8_t
*)b2
)->prob
;
869 return (prob1
< prob2
) - (prob1
> prob2
);
874 static float check_smallest_bitflip_bitarrays(void)
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
;
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));
893 return (float)smallest
/2.0;
897 static void update_expected_brute_force(uint8_t best_byte
) {
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
;
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
;
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;
918 static float sort_best_first_bytes(void)
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;
935 // sort based on expected number of states to brute force
936 qsort(best_first_bytes
, 256, 1, compare_expected_num_brute_force
);
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
]);
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);
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);
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);
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]);
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;
972 // for (uint8_t j = 0; j < NUM_SUMS; j++) {
973 // nonces[first_byte].sum_a8_guess[j].prob /= fix_probs;
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]);
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;
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
;
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
;
1004 return nonces
[best_first_bytes
[0]].expected_num_brute_force
;
1008 static float update_reduction_rate(float last
, bool init
)
1011 static float queue
[QUEUE_LEN
];
1013 for (uint16_t i
= 0; i
< QUEUE_LEN
-1; i
++) {
1015 queue
[i
] = (float)(1LL << 48);
1017 queue
[i
] = queue
[i
+1];
1021 queue
[QUEUE_LEN
-1] = (float)(1LL << 48);
1023 queue
[QUEUE_LEN
-1] = last
;
1026 // linear regression
1029 for (uint16_t i
= 0; i
< QUEUE_LEN
; i
++) {
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
);
1043 float reduction_rate
= -1.0 * dev_xy
/ dev_x2
; // the negative slope of the linear regression
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);
1048 return reduction_rate
;
1052 static bool shrink_key_space(float *brute_forces
)
1054 #if defined(DEBUG_REDUCTION)
1055 printf("shrink_key_space() with stage = 0x%02x\n", hardnested_stage
);
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();
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);
1069 static void estimate_sum_a8(void)
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
);
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;
1086 static int read_nonce_file(void)
1088 FILE *fnonces
= NULL
;
1092 uint8_t read_buf
[9];
1093 uint32_t nt_enc1
, nt_enc2
;
1096 num_acquired_nonces
= 0;
1097 if ((fnonces
= fopen("nonces.bin","rb")) == NULL
) {
1098 PrintAndLog("Could not open file nonces.bin");
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.");
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);
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
);
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);
1131 for (uint16_t i
= 0; i
< NUM_SUMS
; i
++) {
1132 if (first_byte_Sum
== sums
[i
]) {
1142 noncelistentry_t
*SearchFor2ndByte(uint8_t b1
, uint8_t b2
)
1144 noncelistentry_t
*p
= nonces
[b1
].first
;
1146 if ((p
->nonce_enc
>> 16 & 0xff) == b2
) {
1155 static bool timeout(void)
1157 return (msclock() > last_sample_clock
+ sample_period
);
1162 #ifdef __has_attribute
1163 #if __has_attribute(force_align_arg_pointer)
1164 __attribute__((force_align_arg_pointer
))
1167 *check_for_BitFlipProperties_thread(void *args
)
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];
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
);
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;
1198 // printf("bitflip: %d old: %d, new: %d ", bitflip, old_count, nonces[i].num_states_bitarray[odd_even]);
1204 ((uint8_t *)args
)[1] = num_1st_byte_effective_bitflips
- bitflip_idx
- 1; // bitflips still to go in stage 1
1208 ((uint8_t *)args
)[1] = 0; // stage 1 definitely completed
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
);
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;
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]));
1255 static void check_for_BitFlipProperties(bool time_budget
)
1257 // create and run worker threads
1258 pthread_t thread_id
[NUM_CHECK_BITFLIPS_THREADS
];
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
;
1267 args
[NUM_CHECK_BITFLIPS_THREADS
-1][1] = MAX(args
[NUM_CHECK_BITFLIPS_THREADS
-1][1], 255);
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
]);
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
);
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
1288 #if defined (DEBUG_REDUCTION)
1289 if (hardnested_stage
& CHECK_1ST_BYTES
) printf("stage 1 not completed yet\n");
1294 static void update_nonce_data(bool time_budget
)
1296 check_for_BitFlipProperties(time_budget
);
1297 update_allbitflips_array();
1298 update_sum_bitarrays(EVEN_STATE
);
1299 update_sum_bitarrays(ODD_STATE
);
1305 static void apply_sum_a0(void)
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;
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;
1320 static void simulate_MFplus_RNG(uint32_t test_cuid
, uint64_t test_key
, uint32_t *nt_enc
, uint8_t *par_enc
)
1322 struct Crypto1State sim_cs
= {0, 0};
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);
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
;
1344 static void simulate_acquire_nonces()
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;
1353 bool reported_suma8
= false;
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);
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
);
1365 num_acquired_nonces
= 0;
1368 uint32_t nt_enc
= 0;
1369 uint8_t par_enc
= 0;
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
);
1377 last_sample_clock
= msclock();
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
]) {
1387 hardnested_stage
|= CHECK_2ND_BYTES
;
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;
1398 hardnested_print_progress(num_acquired_nonces
, "Apply bit flip properties", brute_force
, 0);
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);
1405 } while (!acquisition_completed
);
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
1414 fprintf(fstats
, "%" PRId32
";%" PRId32
";%1.0f;", total_num_nonces
, num_acquired_nonces
, difftime(end_time
,time1
));
1419 static int acquire_nonces(uint8_t blockNo
, uint8_t keyType
, uint8_t *key
, uint8_t trgBlockNo
, uint8_t trgKeyType
, bool nonce_file_write
, bool slow
)
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;
1428 uint8_t write_buf
[9];
1429 uint32_t total_num_nonces
= 0;
1431 bool reported_suma8
= false;
1432 FILE *fnonces
= NULL
;
1435 num_acquired_nonces
= 0;
1437 clearCommandBuffer();
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);
1449 if (field_off
) break;
1452 if (!WaitForResponseTimeout(CMD_ACK
, &resp
, 3000)) return 1;
1454 if (resp
.arg
[0]) return resp
.arg
[0]; // error during nested_hard
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");
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
);
1472 uint32_t nt_enc1
, nt_enc2
;
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);
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);
1486 if (nonce_file_write
) {
1487 fwrite(bufp
, 1, 9, fnonces
);
1491 total_num_nonces
+= num_sampled_nonces
;
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
]) {
1501 hardnested_stage
|= CHECK_2ND_BYTES
;
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;
1512 hardnested_print_progress(num_acquired_nonces
, "Apply bit flip properties", brute_force
, 0);
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);
1521 if (acquisition_completed
) {
1522 field_off
= true; // switch off field with next SendCommand and then finish
1526 if (!WaitForResponseTimeout(CMD_ACK
, &resp
, 3000)) {
1527 if (nonce_file_write
) {
1533 if (nonce_file_write
) {
1536 return resp
.arg
[0]; // error during nested_hard
1542 if (msclock() - last_sample_clock
< sample_period
) {
1543 sample_period
= msclock() - last_sample_clock
;
1545 last_sample_clock
= msclock();
1547 } while (!acquisition_completed
|| field_off
);
1549 if (nonce_file_write
) {
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));
1562 static inline bool invariant_holds(uint_fast8_t byte_diff
, uint_fast32_t state1
, uint_fast32_t state2
, uint_fast8_t bit
, uint_fast8_t state_bit
)
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
1574 static inline bool invalid_state(uint_fast8_t byte_diff
, uint_fast32_t state1
, uint_fast32_t state2
, uint_fast8_t bit
, uint_fast8_t state_bit
)
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
1585 static inline bool remaining_bits_match(uint_fast8_t num_common_bits
, uint_fast8_t byte_diff
, uint_fast32_t state1
, uint_fast32_t state2
, odd_even_t odd_even
)
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;
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;
1612 return true; // valid state
1616 static pthread_mutex_t statelist_cache_mutex
;
1617 static pthread_mutex_t book_of_work_mutex
;
1626 static struct sl_cache_entry
{
1629 work_status_t cache_status
;
1630 } sl_cache
[NUM_PART_SUMS
][NUM_PART_SUMS
][2];
1633 static void init_statelist_cache(void)
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
;
1645 pthread_mutex_unlock(&statelist_cache_mutex
);
1649 static void free_statelist_cache(void)
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
);
1659 pthread_mutex_unlock(&statelist_cache_mutex
);
1663 #ifdef DEBUG_KEY_ELIMINATION
1664 static inline bool bitflips_match(uint8_t byte
, uint32_t state
, odd_even_t odd_even
, bool quiet
)
1666 static inline bool bitflips_match(uint8_t byte
, uint32_t state
, odd_even_t odd_even
)
1669 uint32_t *bitset
= nonces
[byte
].states_bitarray
[odd_even
];
1670 bool possible
= test_bit24(bitset
, state
);
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");
1685 static uint_fast8_t reverse(uint_fast8_t byte
)
1687 uint_fast8_t rev_byte
= 0;
1689 for (uint8_t i
= 0; i
< 8; i
++) {
1691 rev_byte
|= (byte
>> i
) & 0x01;
1698 static bool all_bitflips_match(uint8_t byte
, uint32_t state
, odd_even_t odd_even
)
1700 uint32_t masks
[2][8] = {{0x00fffff0, 0x00fffff8, 0x00fffff8, 0x00fffffc, 0x00fffffc, 0x00fffffe, 0x00fffffe, 0x00ffffff},
1701 {0x00fffff0, 0x00fffff0, 0x00fffff8, 0x00fffff8, 0x00fffffc, 0x00fffffc, 0x00fffffe, 0x00fffffe} };
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)) {
1714 if (bitflips_match(byte2
, (state
& mask
) | remaining_bits
, odd_even
)) {
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");
1741 static void bitarray_to_list(uint8_t byte
, uint32_t *bitarray
, uint32_t *state_list
, uint32_t *len
, odd_even_t odd_even
)
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
)) {
1749 // add End Of List marker
1751 *len
= p
- state_list
;
1755 static void add_cached_states(statelist_t
*candidates
, uint16_t part_sum_a0
, uint16_t part_sum_a8
, odd_even_t odd_even
)
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
;
1763 static void add_matching_states(statelist_t
*candidates
, uint8_t part_sum_a0
, uint8_t part_sum_a8
, odd_even_t odd_even
)
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");
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
]);
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
];
1782 // for (uint32_t i = 0; i < (1<<19); i++) {
1783 // candidates_bitarray[i] = bitarray_a0[i] & bitarray_a8[i] & bitarray_bitflips[i];
1785 bitarray_AND4(candidates_bitarray
, bitarray_a0
, bitarray_a8
, bitarray_bitflips
);
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));
1794 free_bitarray(candidates_bitarray
);
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
);
1807 static statelist_t
*add_more_candidates(void)
1809 statelist_t
*new_candidates
= candidates
;
1810 if (candidates
== NULL
) {
1811 candidates
= (statelist_t
*)malloc(sizeof(statelist_t
));
1812 new_candidates
= candidates
;
1814 new_candidates
= candidates
;
1815 while (new_candidates
->next
!= NULL
) {
1816 new_candidates
= new_candidates
->next
;
1818 new_candidates
= new_candidates
->next
= (statelist_t
*)malloc(sizeof(statelist_t
));
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
;
1829 static void add_bitflip_candidates(uint8_t byte
)
1831 statelist_t
*candidates
= add_more_candidates();
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");
1841 bitarray_to_list(byte
, nonces
[byte
].states_bitarray
[odd_even
], candidates
->states
[odd_even
], &(candidates
->len
[odd_even
]), odd_even
);
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));
1851 static bool TestIfKeyExists(uint64_t key
)
1853 struct Crypto1State
*pcs
;
1854 pcs
= crypto1_create(key
);
1855 crypto1_byte(pcs
, (cuid
>> 24) ^ best_first_bytes
[0], true);
1857 uint32_t state_odd
= pcs
->odd
& 0x00ffffff;
1858 uint32_t state_even
= pcs
->even
& 0x00ffffff;
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
) {
1874 while (*p_even
!= 0xffffffff) {
1875 if ((*p_even
& 0x00ffffff) == state_even
) {
1880 count
+= (uint64_t)(p_odd
- p
->states
[ODD_STATE
]) * (uint64_t)(p_even
- p
->states
[EVEN_STATE
]);
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
);
1890 num_keys_tested
+= count
;
1891 hardnested_print_progress(num_acquired_nonces
, "(Test: Key NOT found)", 0.0, 0);
1893 crypto1_destroy(pcs
);
1898 static work_status_t book_of_work
[NUM_PART_SUMS
][NUM_PART_SUMS
][NUM_PART_SUMS
][NUM_PART_SUMS
];
1901 static void init_book_of_work(void)
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
;
1916 #ifdef __has_attribute
1917 #if __has_attribute(force_align_arg_pointer)
1918 __attribute__((force_align_arg_pointer
))
1921 *generate_candidates_worker_thread(void *args
)
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];
1928 bool there_might_be_more_work
= true;
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
);
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;
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();
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;
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;
1970 bool work_required
= true;
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;
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;
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;
1991 if (!work_required
) {
1992 pthread_mutex_unlock(&statelist_cache_mutex
);
1993 pthread_mutex_unlock(&book_of_work_mutex
);
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;
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
);
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
;
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
);
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");
2057 } while (there_might_be_more_work
);
2063 static void generate_candidates(uint8_t sum_a0_idx
, uint8_t sum_a8_idx
)
2065 // printf("Generating crypto1 state candidates... \n");
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]);
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));
2079 init_statelist_cache();
2080 init_book_of_work();
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
);
2086 // create and run worker threads
2087 pthread_t thread_id
[NUM_REDUCTION_WORKING_THREADS
];
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
;
2094 pthread_create(thread_id
+ i
, NULL
, generate_candidates_worker_thread
, sums
[i
]);
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
);
2103 pthread_mutex_destroy(&statelist_cache_mutex
);
2106 for (statelist_t
*sl
= candidates
; sl
!= NULL
; sl
= sl
->next
) {
2107 maximum_states
+= (uint64_t)sl
->len
[ODD_STATE
] * sl
->len
[EVEN_STATE
];
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
;
2116 update_expected_brute_force(best_first_bytes
[0]);
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);
2122 static void free_candidates_memory(statelist_t
*sl
)
2127 free_candidates_memory(sl
->next
);
2133 static void pre_XOR_nonces(void)
2135 // prepare acquired nonces for faster brute forcing.
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
;
2152 static bool brute_force(void)
2154 if (known_target_key
!= -1) {
2155 TestIfKeyExists(known_target_key
);
2157 return brute_force_bs(NULL
, candidates
, cuid
, num_acquired_nonces
, maximum_states
, nonces
, best_first_bytes
);
2161 static uint16_t SumProperty(struct Crypto1State
*s
)
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
);
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();
2179 for (uint16_t i = 0; i < 257; i++) {
2182 for (uint16_t i = 0; i < 17; i++) {
2183 statistics_odd[i] = 0;
2184 statistics_even[i] = 0;
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(".");
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);
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);
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);
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();
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;
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(".");
2242 printf("\nTests: Probability Distribution of a8 depending on a0:\n");
2244 for (uint16_t i = 0; i < NUM_SUMS; i++) {
2245 printf("%7d ", sums[i]);
2247 printf("\n-------------------------------------------------------------------------------------------------------------------------------------------\n");
2249 for (uint16_t i = 0; i < NUM_SUMS; i++) {
2250 printf("%7.5f ", (float)statistics_a0[sums[i]] / NUM_STATISTICS);
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]]);
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);
2263 /* #define NUM_STATISTICS 100000LL
2264 uint64_t statistics_a8[257];
2265 struct Crypto1State cs;
2266 uint64_t time1 = msclock();
2268 printf("\nTests: Probability Distribution of a8 depending on first byte:\n");
2270 for (uint16_t i = 0; i < NUM_SUMS; i++) {
2271 printf("%7d ", sums[i]);
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;
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;
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);
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);
2294 /* printf("Tests: Sum Probabilities based on Partial Sums\n");
2295 for (uint16_t i = 0; i < 257; i++) {
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);
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);
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],
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],
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],
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);
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);
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);
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);
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);
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]);
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 ");
2406 // if (known_target_key != -1) {
2407 // int16_t p = -1, q = -1, r = -1, s = -1;
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) {
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) {
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);
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);
2453 printf("parsum oldparity = %d, time = %1.5fsec\n", par_sum, (float)(msclock() - time1p)/1000.0);
2457 for (uint32_t i = 0; i < 100000000; i++) {
2458 par_sum += evenparity32(i);
2460 printf("parsum newparity = %d, time = %1.5fsec\n", par_sum, (float)(msclock() - time1p)/1000.0);
2466 static void Tests2(void)
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
);
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 ");
2492 static uint16_t real_sum_a8
= 0;
2494 static void set_test_state(uint8_t byte
)
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
);
2506 int mfnestedhard(uint8_t blockNo
, uint8_t keyType
, uint8_t *key
, uint8_t trgBlockNo
, uint8_t trgKeyType
, uint8_t *trgkey
, bool nonce_file_read
, bool nonce_file_write
, bool slow
, int tests
)
2508 char progress_text
[80];
2510 char instr_set
[12] = {0};
2511 get_SIMD_instruction_set(instr_set
);
2512 PrintAndLog("Using %s SIMD core.", instr_set
);
2514 srand((unsigned) time(NULL
));
2515 brute_force_per_second
= brute_force_benchmark();
2516 write_stats
= false;
2519 // set the correct locale for the stats printing
2521 setlocale(LC_NUMERIC
, "");
2522 if ((fstats
= fopen("hardnested_stats.txt","a")) == NULL
) {
2523 PrintAndLog("Could not create/open file hardnested_stats.txt");
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);
2536 known_target_key
= -1;
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);
2546 simulate_acquire_nonces();
2548 set_test_state(best_first_bytes
[0]);
2551 free_bitflip_bitarrays();
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
);
2557 #ifdef DEBUG_KEY_ELIMINATION
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
);
2573 for (statelist_t
*sl
= candidates
; sl
!= NULL
; sl
= sl
->next
) {
2574 maximum_states
+= (uint64_t)sl
->len
[ODD_STATE
] * sl
->len
[EVEN_STATE
];
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
;
2580 prepare_bf_test_nonces(nonces
, best_first_bytes
[0]);
2581 hardnested_print_progress(num_acquired_nonces
, "Starting brute force...", expected_brute_force1
, 0);
2582 key_found
= brute_force();
2583 free(candidates
->states
[ODD_STATE
]);
2584 free(candidates
->states
[EVEN_STATE
]);
2585 free_candidates_memory(candidates
);
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);
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);
2601 hardnested_print_progress(num_acquired_nonces
, "Starting brute force...", expected_brute_force
, 0);
2602 key_found
= brute_force();
2603 free_statelist_cache();
2604 free_candidates_memory(candidates
);
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]);
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
);
2618 fprintf(fstats
, "%1.0f;%d\n", log(num_keys_tested
)/log(2.0), (float)num_keys_tested
/brute_force_per_second
, key_found
);
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();
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);
2640 if (nonce_file_read
) { // use pre-acquired data from file nonces.bin
2641 if (read_nonce_file() != 0) {
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();
2650 hardnested_stage
= CHECK_1ST_BYTES
| CHECK_2ND_BYTES
;
2651 update_nonce_data(false);
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
);
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();
2667 if (trgkey
!= NULL
) {
2668 known_target_key
= bytes_to_num(trgkey
, 6);
2669 set_test_state(best_first_bytes
[0]);
2671 known_target_key
= -1;
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
);
2689 for (statelist_t
*sl
= candidates
; sl
!= NULL
; sl
= sl
->next
) {
2690 maximum_states
+= (uint64_t)sl
->len
[ODD_STATE
] * sl
->len
[EVEN_STATE
];
2692 // printf("Number of remaining possible keys: %" PRIu64 " (2^%1.1f)\n", maximum_states, log(maximum_states)/log(2.0));
2693 best_first_bytes
[0] = best_first_byte_smallest_bitarray
;
2695 prepare_bf_test_nonces(nonces
, best_first_bytes
[0]);
2696 hardnested_print_progress(num_acquired_nonces
, "Starting brute force...", expected_brute_force1
, 0);
2697 key_found
= brute_force();
2698 free(candidates
->states
[ODD_STATE
]);
2699 free(candidates
->states
[EVEN_STATE
]);
2700 free_candidates_memory(candidates
);
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);
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);
2716 hardnested_print_progress(num_acquired_nonces
, "Starting brute force...", expected_brute_force
, 0);
2717 key_found
= brute_force();
2718 free_statelist_cache();
2719 free_candidates_memory(candidates
);
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]);
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();