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