--- /dev/null
+//-----------------------------------------------------------------------------
+// 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 <inttypes.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <pthread.h>
+#include <string.h>
+#include <malloc.h>
+#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;
+}
+
+
projects / proxmark3-svn / blobdiff