X-Git-Url: http://git.zerfleddert.de/cgi-bin/gitweb.cgi/proxmark3-svn/blobdiff_plain/43c3b944e44dd45405e2528185e3f18a314ff9cc..c7b2751136b82bb3c0c61b49cc8cb4008a65d8dd:/client/hardnested/hardnested_bruteforce.c diff --git a/client/hardnested/hardnested_bruteforce.c b/client/hardnested/hardnested_bruteforce.c new file mode 100644 index 00000000..3218c1aa --- /dev/null +++ b/client/hardnested/hardnested_bruteforce.c @@ -0,0 +1,471 @@ +//----------------------------------------------------------------------------- +// Copyright (C) 2016, 2017 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 +//----------------------------------------------------------------------------- +// +// brute forcing is based on @aczids bitsliced brute forcer +// https://github.com/aczid/crypto1_bs with some modifications. Mainly: +// - don't rollback. Start with 2nd byte of nonce instead +// - reuse results of filter subfunctions +// - reuse results of previous nonces if some first bits are identical +// +//----------------------------------------------------------------------------- +// aczid's Copyright notice: +// +// Bit-sliced Crypto-1 brute-forcing implementation +// Builds on the data structures returned by CraptEV1 craptev1_get_space(nonces, threshold, uid) +/* +Copyright (c) 2015-2016 Aram Verstegen + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in +all copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN +THE SOFTWARE. +*/ + +#include "hardnested_bruteforce.h" + +#include +#include +#include +#include +#include +#include +#include "proxmark3.h" +#include "cmdhfmfhard.h" +#include "hardnested_bf_core.h" +#include "ui.h" +#include "util.h" +#include "crapto1/crapto1.h" +#include "parity.h" + +#define NUM_BRUTE_FORCE_THREADS (num_CPUs()) +#define DEFAULT_BRUTE_FORCE_RATE (120000000.0) // if benchmark doesn't succeed +#define TEST_BENCH_SIZE (6000) // number of odd and even states for brute force benchmark +#define TEST_BENCH_FILENAME "hardnested/bf_bench_data.bin" +//#define WRITE_BENCH_FILE + +// debugging options +#define DEBUG_KEY_ELIMINATION +// #define DEBUG_BRUTE_FORCE + +typedef enum { + EVEN_STATE = 0, + ODD_STATE = 1 +} odd_even_t; + +static uint32_t nonces_to_bruteforce = 0; +static uint32_t bf_test_nonce[256]; +static uint8_t bf_test_nonce_2nd_byte[256]; +static uint8_t bf_test_nonce_par[256]; +static uint32_t bucket_count = 0; +static statelist_t* buckets[128]; +static uint32_t keys_found = 0; +static uint64_t num_keys_tested; + + +uint8_t trailing_zeros(uint8_t byte) +{ + static const uint8_t trailing_zeros_LUT[256] = { + 8, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0 + }; + + return trailing_zeros_LUT[byte]; +} + + +bool verify_key(uint32_t cuid, noncelist_t *nonces, uint8_t *best_first_bytes, uint32_t odd, uint32_t even) +{ + struct Crypto1State pcs; + for (uint16_t test_first_byte = 1; test_first_byte < 256; test_first_byte++) { + noncelistentry_t *test_nonce = nonces[best_first_bytes[test_first_byte]].first; + while (test_nonce != NULL) { + pcs.odd = odd; + pcs.even = even; + lfsr_rollback_byte(&pcs, (cuid >> 24) ^ best_first_bytes[0], true); + for (int8_t byte_pos = 3; byte_pos >= 0; byte_pos--) { + uint8_t test_par_enc_bit = (test_nonce->par_enc >> byte_pos) & 0x01; // the encoded parity bit + uint8_t test_byte_enc = (test_nonce->nonce_enc >> (8*byte_pos)) & 0xff; // the encoded nonce byte + uint8_t test_byte_dec = crypto1_byte(&pcs, test_byte_enc /* ^ (cuid >> (8*byte_pos)) */, true) ^ test_byte_enc; // decode the nonce byte + uint8_t ks_par = filter(pcs.odd); // the keystream bit to encode/decode the parity bit + uint8_t test_par_enc2 = ks_par ^ evenparity8(test_byte_dec); // determine the decoded byte's parity and encode it + if (test_par_enc_bit != test_par_enc2) { + return false; + } + } + test_nonce = test_nonce->next; + } + } + return true; +} + + +static void* crack_states_thread(void* x){ + + struct arg { + bool silent; + int thread_ID; + uint32_t cuid; + uint32_t num_acquired_nonces; + uint64_t maximum_states; + noncelist_t *nonces; + uint8_t* best_first_bytes; + } *thread_arg; + + thread_arg = (struct arg *)x; + const int thread_id = thread_arg->thread_ID; + uint32_t current_bucket = thread_id; + while(current_bucket < bucket_count){ + statelist_t *bucket = buckets[current_bucket]; + if(bucket){ +#if defined (DEBUG_BRUTE_FORCE) + printf("Thread %u starts working on bucket %u\n", thread_id, current_bucket); +#endif + const uint64_t key = crack_states_bitsliced(thread_arg->cuid, thread_arg->best_first_bytes, bucket, &keys_found, &num_keys_tested, nonces_to_bruteforce, bf_test_nonce_2nd_byte, thread_arg->nonces); + if(key != -1){ + __sync_fetch_and_add(&keys_found, 1); + char progress_text[80]; + sprintf(progress_text, "Brute force phase completed. Key found: %012" PRIx64, key); + hardnested_print_progress(thread_arg->num_acquired_nonces, progress_text, 0.0, 0); + break; + } else if(keys_found){ + break; + } else { + if (!thread_arg->silent) { + char progress_text[80]; + sprintf(progress_text, "Brute force phase: %6.02f%%", 100.0*(float)num_keys_tested/(float)(thread_arg->maximum_states)); + float remaining_bruteforce = thread_arg->nonces[thread_arg->best_first_bytes[0]].expected_num_brute_force - (float)num_keys_tested/2; + hardnested_print_progress(thread_arg->num_acquired_nonces, progress_text, remaining_bruteforce, 5000); + } + } + } + current_bucket += NUM_BRUTE_FORCE_THREADS; + } + return NULL; +} + + +void prepare_bf_test_nonces(noncelist_t *nonces, uint8_t best_first_byte) +{ + // we do bitsliced brute forcing with best_first_bytes[0] only. + // Extract the corresponding 2nd bytes + noncelistentry_t *test_nonce = nonces[best_first_byte].first; + uint32_t i = 0; + while (test_nonce != NULL) { + bf_test_nonce[i] = test_nonce->nonce_enc; + bf_test_nonce_par[i] = test_nonce->par_enc; + bf_test_nonce_2nd_byte[i] = (test_nonce->nonce_enc >> 16) & 0xff; + test_nonce = test_nonce->next; + i++; + } + nonces_to_bruteforce = i; + + // printf("Nonces to bruteforce: %d\n", nonces_to_bruteforce); + // printf("Common bits of first 4 2nd nonce bytes (before sorting): %u %u %u\n", + // trailing_zeros(bf_test_nonce_2nd_byte[1] ^ bf_test_nonce_2nd_byte[0]), + // trailing_zeros(bf_test_nonce_2nd_byte[2] ^ bf_test_nonce_2nd_byte[1]), + // trailing_zeros(bf_test_nonce_2nd_byte[3] ^ bf_test_nonce_2nd_byte[2])); + + uint8_t best_4[4] = {0}; + int sum_best = -1; + for (uint16_t n1 = 0; n1 < nonces_to_bruteforce; n1++) { + for (uint16_t n2 = 0; n2 < nonces_to_bruteforce; n2++) { + if (n2 != n1) { + for (uint16_t n3 = 0; n3 < nonces_to_bruteforce; n3++) { + if ((n3 != n2 && n3 != n1) || nonces_to_bruteforce < 3 + // && trailing_zeros(bf_test_nonce_2nd_byte[n1] ^ bf_test_nonce_2nd_byte[n2]) + // > trailing_zeros(bf_test_nonce_2nd_byte[n2] ^ bf_test_nonce_2nd_byte[n3]) + ) { + for (uint16_t n4 = 0; n4 < nonces_to_bruteforce; n4++) { + if ((n4 != n3 && n4 != n2 && n4 != n1) || nonces_to_bruteforce < 4 + // && trailing_zeros(bf_test_nonce_2nd_byte[n2] ^ bf_test_nonce_2nd_byte[n3]) + // > trailing_zeros(bf_test_nonce_2nd_byte[n3] ^ bf_test_nonce_2nd_byte[n4]) + ) { + int sum = nonces_to_bruteforce > 1 ? trailing_zeros(bf_test_nonce_2nd_byte[n1] ^ bf_test_nonce_2nd_byte[n2]) : 0.0 + + nonces_to_bruteforce > 2 ? trailing_zeros(bf_test_nonce_2nd_byte[n2] ^ bf_test_nonce_2nd_byte[n3]) : 0.0 + + nonces_to_bruteforce > 3 ? trailing_zeros(bf_test_nonce_2nd_byte[n3] ^ bf_test_nonce_2nd_byte[n4]) : 0.0; + if (sum > sum_best) { + sum_best = sum; + best_4[0] = n1; + best_4[1] = n2; + best_4[2] = n3; + best_4[3] = n4; + } + } + } + } + } + } + } + } + + uint32_t bf_test_nonce_temp[4]; + uint8_t bf_test_nonce_par_temp[4]; + uint8_t bf_test_nonce_2nd_byte_temp[4]; + for (uint8_t i = 0; i < 4 && i < nonces_to_bruteforce; i++) { + bf_test_nonce_temp[i] = bf_test_nonce[best_4[i]]; + + bf_test_nonce_par_temp[i] = bf_test_nonce_par[best_4[i]]; + bf_test_nonce_2nd_byte_temp[i] = bf_test_nonce_2nd_byte[best_4[i]]; + } + for (uint8_t i = 0; i < 4 && i < nonces_to_bruteforce; i++) { + bf_test_nonce[i] = bf_test_nonce_temp[i]; + bf_test_nonce_par[i] = bf_test_nonce_par_temp[i]; + bf_test_nonce_2nd_byte[i] = bf_test_nonce_2nd_byte_temp[i]; + } +} + + +#if defined (WRITE_BENCH_FILE) +static void write_benchfile(statelist_t *candidates) { + + printf("Writing brute force benchmark data..."); + FILE *benchfile = fopen(TEST_BENCH_FILENAME, "wb"); + fwrite(&nonces_to_bruteforce, 1, sizeof(nonces_to_bruteforce), benchfile); + for (uint32_t i = 0; i < nonces_to_bruteforce; i++) { + fwrite(&(bf_test_nonce[i]), 1, sizeof(bf_test_nonce[i]), benchfile); + fwrite(&(bf_test_nonce_par[i]), 1, sizeof(bf_test_nonce_par[i]), benchfile); + } + uint32_t num_states = MIN(candidates->len[EVEN_STATE], TEST_BENCH_SIZE); + fwrite(&num_states, 1, sizeof(num_states), benchfile); + for (uint32_t i = 0; i < num_states; i++) { + fwrite(&(candidates->states[EVEN_STATE][i]), 1, sizeof(uint32_t), benchfile); + } + num_states = MIN(candidates->len[ODD_STATE], TEST_BENCH_SIZE); + fwrite(&num_states, 1, sizeof(num_states), benchfile); + for (uint32_t i = 0; i < num_states; i++) { + fwrite(&(candidates->states[ODD_STATE][i]), 1, sizeof(uint32_t), benchfile); + } + fclose(benchfile); + printf("done.\n"); +} +#endif + + +bool brute_force_bs(float *bf_rate, statelist_t *candidates, uint32_t cuid, uint32_t num_acquired_nonces, uint64_t maximum_states, noncelist_t *nonces, uint8_t *best_first_bytes) +{ +#if defined (WRITE_BENCH_FILE) + write_benchfile(candidates); +#endif + bool silent = (bf_rate != NULL); + + // if (!silent) { + // PrintAndLog("Brute force phase starting."); + // PrintAndLog("Using %u-bit bitslices", MAX_BITSLICES); + // } + + keys_found = 0; + num_keys_tested = 0; + + bitslice_test_nonces(nonces_to_bruteforce, bf_test_nonce, bf_test_nonce_par); + + // count number of states to go + bucket_count = 0; + for (statelist_t *p = candidates; p != NULL; p = p->next) { + if (p->states[ODD_STATE] != NULL && p->states[EVEN_STATE] != NULL) { + buckets[bucket_count] = p; + bucket_count++; + } + } + + uint64_t start_time = msclock(); + // enumerate states using all hardware threads, each thread handles one bucket + // if (!silent) { + // PrintAndLog("Starting %u cracking threads to search %u buckets containing a total of %" PRIu64" states...\n", NUM_BRUTE_FORCE_THREADS, bucket_count, maximum_states); + // printf("Common bits of first 4 2nd nonce bytes: %u %u %u\n", + // trailing_zeros(bf_test_nonce_2nd_byte[1] ^ bf_test_nonce_2nd_byte[0]), + // trailing_zeros(bf_test_nonce_2nd_byte[2] ^ bf_test_nonce_2nd_byte[1]), + // trailing_zeros(bf_test_nonce_2nd_byte[3] ^ bf_test_nonce_2nd_byte[2])); + // } + + pthread_t threads[NUM_BRUTE_FORCE_THREADS]; + struct args { + bool silent; + int thread_ID; + uint32_t cuid; + uint32_t num_acquired_nonces; + uint64_t maximum_states; + noncelist_t *nonces; + uint8_t *best_first_bytes; + } thread_args[NUM_BRUTE_FORCE_THREADS]; + + for(uint32_t i = 0; i < NUM_BRUTE_FORCE_THREADS; i++){ + thread_args[i].thread_ID = i; + thread_args[i].silent = silent; + thread_args[i].cuid = cuid; + thread_args[i].num_acquired_nonces = num_acquired_nonces; + thread_args[i].maximum_states = maximum_states; + thread_args[i].nonces = nonces; + thread_args[i].best_first_bytes = best_first_bytes; + pthread_create(&threads[i], NULL, crack_states_thread, (void*)&thread_args[i]); + } + for(uint32_t i = 0; i < NUM_BRUTE_FORCE_THREADS; i++){ + pthread_join(threads[i], 0); + } + + uint64_t elapsed_time = msclock() - start_time; + + // if (!silent) { + // printf("Brute force completed after testing %" PRIu64" (2^%1.1f) keys in %1.1f seconds at a rate of %1.0f (2^%1.1f) keys per second.\n", + // num_keys_tested, + // log(num_keys_tested) / log(2.0), + // (float)elapsed_time/1000.0, + // (float)num_keys_tested / ((float)elapsed_time / 1000.0), + // log((float)num_keys_tested / ((float)elapsed_time/1000.0)) / log(2.0)); + // } + + if (bf_rate != NULL) { + *bf_rate = (float)num_keys_tested / ((float)elapsed_time / 1000.0); + } + + return (keys_found != 0); +} + + +static bool read_bench_data(statelist_t *test_candidates) { + + size_t bytes_read = 0; + uint32_t temp = 0; + uint32_t num_states = 0; + uint32_t states_read = 0; + + char bench_file_path[strlen(get_my_executable_directory()) + strlen(TEST_BENCH_FILENAME) + 1]; + strcpy(bench_file_path, get_my_executable_directory()); + strcat(bench_file_path, TEST_BENCH_FILENAME); + + FILE *benchfile = fopen(bench_file_path, "rb"); + if (benchfile == NULL) { + return false; + } + bytes_read = fread(&nonces_to_bruteforce, 1, sizeof(nonces_to_bruteforce), benchfile); + if (bytes_read != sizeof(nonces_to_bruteforce)) { + fclose(benchfile); + return false; + } + for (uint16_t i = 0; i < nonces_to_bruteforce && i < 256; i++) { + bytes_read = fread(&bf_test_nonce[i], 1, sizeof(uint32_t), benchfile); + if (bytes_read != sizeof(uint32_t)) { + fclose(benchfile); + return false; + } + bf_test_nonce_2nd_byte[i] = (bf_test_nonce[i] >> 16) & 0xff; + bytes_read = fread(&bf_test_nonce_par[i], 1, sizeof(uint8_t), benchfile); + if (bytes_read != sizeof(uint8_t)) { + fclose(benchfile); + return false; + } + } + bytes_read = fread(&num_states, 1, sizeof(uint32_t), benchfile); + if (bytes_read != sizeof(uint32_t)) { + fclose(benchfile); + return false; + } + for (states_read = 0; states_read < MIN(num_states, TEST_BENCH_SIZE); states_read++) { + bytes_read = fread(test_candidates->states[EVEN_STATE] + states_read, 1, sizeof(uint32_t), benchfile); + if (bytes_read != sizeof(uint32_t)) { + fclose(benchfile); + return false; + } + } + for (uint32_t i = states_read; i < TEST_BENCH_SIZE; i++) { + test_candidates->states[EVEN_STATE][i] = test_candidates->states[EVEN_STATE][i-states_read]; + } + for (uint32_t i = states_read; i < num_states; i++) { + bytes_read = fread(&temp, 1, sizeof(uint32_t), benchfile); + if (bytes_read != sizeof(uint32_t)) { + fclose(benchfile); + return false; + } + } + for (states_read = 0; states_read < MIN(num_states, TEST_BENCH_SIZE); states_read++) { + bytes_read = fread(test_candidates->states[ODD_STATE] + states_read, 1, sizeof(uint32_t), benchfile); + if (bytes_read != sizeof(uint32_t)) { + fclose(benchfile); + return false; + } + } + for (uint32_t i = states_read; i < TEST_BENCH_SIZE; i++) { + test_candidates->states[ODD_STATE][i] = test_candidates->states[ODD_STATE][i-states_read]; + } + + fclose(benchfile); + return true; +} + + +float brute_force_benchmark() +{ + statelist_t test_candidates[NUM_BRUTE_FORCE_THREADS]; + + test_candidates[0].states[ODD_STATE] = malloc((TEST_BENCH_SIZE+1) * sizeof(uint32_t)); + test_candidates[0].states[EVEN_STATE] = malloc((TEST_BENCH_SIZE+1) * sizeof(uint32_t)); + for (uint8_t i = 0; i < NUM_BRUTE_FORCE_THREADS - 1; i++){ + test_candidates[i].next = test_candidates + i + 1; + test_candidates[i+1].states[ODD_STATE] = test_candidates[0].states[ODD_STATE]; + test_candidates[i+1].states[EVEN_STATE] = test_candidates[0].states[EVEN_STATE]; + } + test_candidates[NUM_BRUTE_FORCE_THREADS-1].next = NULL; + + if (!read_bench_data(test_candidates)) { + PrintAndLog("Couldn't read benchmark data. Assuming brute force rate of %1.0f states per second", DEFAULT_BRUTE_FORCE_RATE); + return DEFAULT_BRUTE_FORCE_RATE; + } + + for (uint8_t i = 0; i < NUM_BRUTE_FORCE_THREADS; i++) { + test_candidates[i].len[ODD_STATE] = TEST_BENCH_SIZE; + test_candidates[i].len[EVEN_STATE] = TEST_BENCH_SIZE; + test_candidates[i].states[ODD_STATE][TEST_BENCH_SIZE] = -1; + test_candidates[i].states[EVEN_STATE][TEST_BENCH_SIZE] = -1; + } + + uint64_t maximum_states = TEST_BENCH_SIZE*TEST_BENCH_SIZE*(uint64_t)NUM_BRUTE_FORCE_THREADS; + + float bf_rate; + brute_force_bs(&bf_rate, test_candidates, 0, 0, maximum_states, NULL, 0); + + free(test_candidates[0].states[ODD_STATE]); + free(test_candidates[0].states[EVEN_STATE]); + + return bf_rate; +} + +