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