[proxmark3-svn] / client / hardnested / hardnested_bruteforce.c

//-----------------------------------------------------------------------------
// 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 <stdlib.h>
#include "proxmark3.h"
#include "cmdhfmfhard.h"
#include "hardnested_bf_core.h"
#include "ui.h"
#include "util.h"
#include "util_posix.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;
}
Commit	Line	Data
c48c4d78	1	//-----------------------------------------------------------------------------
	2	// Copyright (C) 2016, 2017 by piwi
	3	//
	4	// This code is licensed to you under the terms of the GNU GPL, version 2 or,
	5	// at your option, any later version. See the LICENSE.txt file for the text of
	6	// the license.
	7	//-----------------------------------------------------------------------------
	8	// Implements a card only attack based on crypto text (encrypted nonces
	9	// received during a nested authentication) only. Unlike other card only
	10	// attacks this doesn't rely on implementation errors but only on the
	11	// inherent weaknesses of the crypto1 cypher. Described in
	12	// Carlo Meijer, Roel Verdult, "Ciphertext-only Cryptanalysis on Hardened
	13	// Mifare Classic Cards" in Proceedings of the 22nd ACM SIGSAC Conference on
	14	// Computer and Communications Security, 2015
	15	//-----------------------------------------------------------------------------
	16	//
	17	// brute forcing is based on @aczids bitsliced brute forcer
	18	// https://github.com/aczid/crypto1_bs with some modifications. Mainly:
	19	// - don't rollback. Start with 2nd byte of nonce instead
	20	// - reuse results of filter subfunctions
	21	// - reuse results of previous nonces if some first bits are identical
	22	//
	23	//-----------------------------------------------------------------------------
	24	// aczid's Copyright notice:
	25	//
	26	// Bit-sliced Crypto-1 brute-forcing implementation
	27	// Builds on the data structures returned by CraptEV1 craptev1_get_space(nonces, threshold, uid)
	28	/*
	29	Copyright (c) 2015-2016 Aram Verstegen
	30
	31	Permission is hereby granted, free of charge, to any person obtaining a copy
	32	of this software and associated documentation files (the "Software"), to deal
	33	in the Software without restriction, including without limitation the rights
	34	to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
	35	copies of the Software, and to permit persons to whom the Software is
	36	furnished to do so, subject to the following conditions:
	37
	38	The above copyright notice and this permission notice shall be included in
	39	all copies or substantial portions of the Software.
	40
	41	THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
	42	IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
	43	FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
	44	AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
	45	LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
	46	OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
	47	THE SOFTWARE.
	48	*/
	49
	50	#include "hardnested_bruteforce.h"
	51
	52	#include <inttypes.h>
	53	#include <stdbool.h>
	54	#include <stdio.h>
	55	#include <pthread.h>
	56	#include <string.h>
c3d117a8	57	#include <stdlib.h>
c48c4d78	58	#include "proxmark3.h"
	59	#include "cmdhfmfhard.h"
	60	#include "hardnested_bf_core.h"
	61	#include "ui.h"
	62	#include "util.h"
ec9c7112	63	#include "util_posix.h"
c48c4d78	64	#include "crapto1/crapto1.h"
	65	#include "parity.h"
	66
	67	#define NUM_BRUTE_FORCE_THREADS (num_CPUs())
	68	#define DEFAULT_BRUTE_FORCE_RATE (120000000.0) // if benchmark doesn't succeed
	69	#define TEST_BENCH_SIZE (6000) // number of odd and even states for brute force benchmark
	70	#define TEST_BENCH_FILENAME "hardnested/bf_bench_data.bin"
	71	//#define WRITE_BENCH_FILE
	72
	73	// debugging options
	74	#define DEBUG_KEY_ELIMINATION
	75	// #define DEBUG_BRUTE_FORCE
	76
	77	typedef enum {
	78	EVEN_STATE = 0,
	79	ODD_STATE = 1
	80	} odd_even_t;
	81
	82	static uint32_t nonces_to_bruteforce = 0;
	83	static uint32_t bf_test_nonce[256];
	84	static uint8_t bf_test_nonce_2nd_byte[256];
	85	static uint8_t bf_test_nonce_par[256];
	86	static uint32_t bucket_count = 0;
	87	static statelist_t* buckets[128];
	88	static uint32_t keys_found = 0;
	89	static uint64_t num_keys_tested;
	90
	91
	92	uint8_t trailing_zeros(uint8_t byte)
	93	{
	94	static const uint8_t trailing_zeros_LUT[256] = {
	95	8, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	96	4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	97	5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	98	4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	99	6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	100	4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	101	5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	102	4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	103	7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	104	4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	105	5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	106	4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	107	6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	108	4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	109	5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	110	4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
	111	};
	112
	113	return trailing_zeros_LUT[byte];
	114	}
	115
	116
	117	bool verify_key(uint32_t cuid, noncelist_t nonces, uint8_t best_first_bytes, uint32_t odd, uint32_t even)
	118	{
	119	struct Crypto1State pcs;
	120	for (uint16_t test_first_byte = 1; test_first_byte < 256; test_first_byte++) {
	121	noncelistentry_t *test_nonce = nonces[best_first_bytes[test_first_byte]].first;
	122	while (test_nonce != NULL) {
	123	pcs.odd = odd;
	124	pcs.even = even;
	125	lfsr_rollback_byte(&pcs, (cuid >> 24) ^ best_first_bytes[0], true);
	126	for (int8_t byte_pos = 3; byte_pos >= 0; byte_pos--) {
	127	uint8_t test_par_enc_bit = (test_nonce->par_enc >> byte_pos) & 0x01; // the encoded parity bit
128	uint8_t test_byte_enc = (test_nonce->nonce_enc >> (8*byte_pos)) & 0xff; // the encoded nonce byte
129	uint8_t test_byte_dec = crypto1_byte(&pcs, test_byte_enc /* ^ (cuid >> (8byte_pos)) /, true) ^ test_byte_enc; // decode the nonce byte
130	uint8_t ks_par = filter(pcs.odd); // the keystream bit to encode/decode the parity bit
131	uint8_t test_par_enc2 = ks_par ^ evenparity8(test_byte_dec); // determine the decoded byte's parity and encode it
132	if (test_par_enc_bit != test_par_enc2) {
133	return false;
134	}
135	}
136	test_nonce = test_nonce->next;
137	}
138	}
139	return true;
140	}
141
142
143	static void* crack_states_thread(void* x){
144
145	struct arg {
146	bool silent;
147	int thread_ID;
148	uint32_t cuid;
149	uint32_t num_acquired_nonces;
150	uint64_t maximum_states;
151	noncelist_t *nonces;
152	uint8_t* best_first_bytes;
153	} *thread_arg;
154
155	thread_arg = (struct arg *)x;
156	const int thread_id = thread_arg->thread_ID;
157	uint32_t current_bucket = thread_id;
158	while(current_bucket < bucket_count){
159	statelist_t *bucket = buckets[current_bucket];
160	if(bucket){
161	#if defined (DEBUG_BRUTE_FORCE)
162	printf("Thread %u starts working on bucket %u\n", thread_id, current_bucket);
163	#endif
164	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);
165	if(key != -1){
166	__sync_fetch_and_add(&keys_found, 1);
167	char progress_text[80];
168	sprintf(progress_text, "Brute force phase completed. Key found: %012" PRIx64, key);
169	hardnested_print_progress(thread_arg->num_acquired_nonces, progress_text, 0.0, 0);
170	break;
171	} else if(keys_found){
172	break;
173	} else {
174	if (!thread_arg->silent) {
175	char progress_text[80];
176	sprintf(progress_text, "Brute force phase: %6.02f%%", 100.0*(float)num_keys_tested/(float)(thread_arg->maximum_states));
177	float remaining_bruteforce = thread_arg->nonces[thread_arg->best_first_bytes[0]].expected_num_brute_force - (float)num_keys_tested/2;
178	hardnested_print_progress(thread_arg->num_acquired_nonces, progress_text, remaining_bruteforce, 5000);
179	}
180	}
181	}
182	current_bucket += NUM_BRUTE_FORCE_THREADS;
183	}
184	return NULL;
185	}
186
187
188	void prepare_bf_test_nonces(noncelist_t *nonces, uint8_t best_first_byte)
189	{
190	// we do bitsliced brute forcing with best_first_bytes[0] only.
191	// Extract the corresponding 2nd bytes
192	noncelistentry_t *test_nonce = nonces[best_first_byte].first;
193	uint32_t i = 0;
194	while (test_nonce != NULL) {
195	bf_test_nonce[i] = test_nonce->nonce_enc;
196	bf_test_nonce_par[i] = test_nonce->par_enc;
197	bf_test_nonce_2nd_byte[i] = (test_nonce->nonce_enc >> 16) & 0xff;
198	test_nonce = test_nonce->next;
199	i++;
200	}
201	nonces_to_bruteforce = i;
202
203	// printf("Nonces to bruteforce: %d\n", nonces_to_bruteforce);
204	// printf("Common bits of first 4 2nd nonce bytes (before sorting): %u %u %u\n",
205	// trailing_zeros(bf_test_nonce_2nd_byte[1] ^ bf_test_nonce_2nd_byte[0]),
206	// trailing_zeros(bf_test_nonce_2nd_byte[2] ^ bf_test_nonce_2nd_byte[1]),
207	// trailing_zeros(bf_test_nonce_2nd_byte[3] ^ bf_test_nonce_2nd_byte[2]));
208
209	uint8_t best_4[4] = {0};
210	int sum_best = -1;
211	for (uint16_t n1 = 0; n1 < nonces_to_bruteforce; n1++) {
212	for (uint16_t n2 = 0; n2 < nonces_to_bruteforce; n2++) {
213	if (n2 != n1) {
214	for (uint16_t n3 = 0; n3 < nonces_to_bruteforce; n3++) {
215	if ((n3 != n2 && n3 != n1) \|\| nonces_to_bruteforce < 3
216	// && trailing_zeros(bf_test_nonce_2nd_byte[n1] ^ bf_test_nonce_2nd_byte[n2])
217	// > trailing_zeros(bf_test_nonce_2nd_byte[n2] ^ bf_test_nonce_2nd_byte[n3])
218	) {
219	for (uint16_t n4 = 0; n4 < nonces_to_bruteforce; n4++) {
220	if ((n4 != n3 && n4 != n2 && n4 != n1) \|\| nonces_to_bruteforce < 4
221	// && trailing_zeros(bf_test_nonce_2nd_byte[n2] ^ bf_test_nonce_2nd_byte[n3])
222	// > trailing_zeros(bf_test_nonce_2nd_byte[n3] ^ bf_test_nonce_2nd_byte[n4])
223	) {
224	int sum = nonces_to_bruteforce > 1 ? trailing_zeros(bf_test_nonce_2nd_byte[n1] ^ bf_test_nonce_2nd_byte[n2]) : 0.0
225	+ nonces_to_bruteforce > 2 ? trailing_zeros(bf_test_nonce_2nd_byte[n2] ^ bf_test_nonce_2nd_byte[n3]) : 0.0
226	+ nonces_to_bruteforce > 3 ? trailing_zeros(bf_test_nonce_2nd_byte[n3] ^ bf_test_nonce_2nd_byte[n4]) : 0.0;
227	if (sum > sum_best) {
228	sum_best = sum;
229	best_4[0] = n1;
230	best_4[1] = n2;
231	best_4[2] = n3;
232	best_4[3] = n4;
233	}
234	}
235	}
236	}
237	}
238	}
239	}
240	}
241
242	uint32_t bf_test_nonce_temp[4];
243	uint8_t bf_test_nonce_par_temp[4];
244	uint8_t bf_test_nonce_2nd_byte_temp[4];
245	for (uint8_t i = 0; i < 4 && i < nonces_to_bruteforce; i++) {
246	bf_test_nonce_temp[i] = bf_test_nonce[best_4[i]];
247
248	bf_test_nonce_par_temp[i] = bf_test_nonce_par[best_4[i]];
249	bf_test_nonce_2nd_byte_temp[i] = bf_test_nonce_2nd_byte[best_4[i]];
250	}
251	for (uint8_t i = 0; i < 4 && i < nonces_to_bruteforce; i++) {
252	bf_test_nonce[i] = bf_test_nonce_temp[i];
253	bf_test_nonce_par[i] = bf_test_nonce_par_temp[i];
254	bf_test_nonce_2nd_byte[i] = bf_test_nonce_2nd_byte_temp[i];
255	}
256	}
257
258
259	#if defined (WRITE_BENCH_FILE)
260	static void write_benchfile(statelist_t *candidates) {
261
262	printf("Writing brute force benchmark data...");
263	FILE *benchfile = fopen(TEST_BENCH_FILENAME, "wb");
264	fwrite(&nonces_to_bruteforce, 1, sizeof(nonces_to_bruteforce), benchfile);
265	for (uint32_t i = 0; i < nonces_to_bruteforce; i++) {
266	fwrite(&(bf_test_nonce[i]), 1, sizeof(bf_test_nonce[i]), benchfile);
267	fwrite(&(bf_test_nonce_par[i]), 1, sizeof(bf_test_nonce_par[i]), benchfile);
268	}
269	uint32_t num_states = MIN(candidates->len[EVEN_STATE], TEST_BENCH_SIZE);
270	fwrite(&num_states, 1, sizeof(num_states), benchfile);
271	for (uint32_t i = 0; i < num_states; i++) {
272	fwrite(&(candidates->states[EVEN_STATE][i]), 1, sizeof(uint32_t), benchfile);
273	}
274	num_states = MIN(candidates->len[ODD_STATE], TEST_BENCH_SIZE);
275	fwrite(&num_states, 1, sizeof(num_states), benchfile);
276	for (uint32_t i = 0; i < num_states; i++) {
277	fwrite(&(candidates->states[ODD_STATE][i]), 1, sizeof(uint32_t), benchfile);
278	}
279	fclose(benchfile);
280	printf("done.\n");
281	}
282	#endif
283
284
285	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)
286	{
287	#if defined (WRITE_BENCH_FILE)
288	write_benchfile(candidates);
289	#endif
290	bool silent = (bf_rate != NULL);
291
292	// if (!silent) {
293	// PrintAndLog("Brute force phase starting.");
294	// PrintAndLog("Using %u-bit bitslices", MAX_BITSLICES);
295	// }
296
297	keys_found = 0;
298	num_keys_tested = 0;
299
300	bitslice_test_nonces(nonces_to_bruteforce, bf_test_nonce, bf_test_nonce_par);
301
302	// count number of states to go
303	bucket_count = 0;
304	for (statelist_t *p = candidates; p != NULL; p = p->next) {
305	if (p->states[ODD_STATE] != NULL && p->states[EVEN_STATE] != NULL) {
306	buckets[bucket_count] = p;
307	bucket_count++;
308	}
309	}
310
311	uint64_t start_time = msclock();
312	// enumerate states using all hardware threads, each thread handles one bucket
313	// if (!silent) {
314	// PrintAndLog("Starting %u cracking threads to search %u buckets containing a total of %" PRIu64" states...\n", NUM_BRUTE_FORCE_THREADS, bucket_count, maximum_states);
315	// printf("Common bits of first 4 2nd nonce bytes: %u %u %u\n",
316	// trailing_zeros(bf_test_nonce_2nd_byte[1] ^ bf_test_nonce_2nd_byte[0]),
317	// trailing_zeros(bf_test_nonce_2nd_byte[2] ^ bf_test_nonce_2nd_byte[1]),
318	// trailing_zeros(bf_test_nonce_2nd_byte[3] ^ bf_test_nonce_2nd_byte[2]));
319	// }
320
321	pthread_t threads[NUM_BRUTE_FORCE_THREADS];
322	struct args {
323	bool silent;
324	int thread_ID;
325	uint32_t cuid;
326	uint32_t num_acquired_nonces;
327	uint64_t maximum_states;
328	noncelist_t *nonces;
329	uint8_t *best_first_bytes;
330	} thread_args[NUM_BRUTE_FORCE_THREADS];
331
332	for(uint32_t i = 0; i < NUM_BRUTE_FORCE_THREADS; i++){
333	thread_args[i].thread_ID = i;
334	thread_args[i].silent = silent;
335	thread_args[i].cuid = cuid;
336	thread_args[i].num_acquired_nonces = num_acquired_nonces;
337	thread_args[i].maximum_states = maximum_states;
338	thread_args[i].nonces = nonces;
339	thread_args[i].best_first_bytes = best_first_bytes;
340	pthread_create(&threads[i], NULL, crack_states_thread, (void*)&thread_args[i]);
341	}
342	for(uint32_t i = 0; i < NUM_BRUTE_FORCE_THREADS; i++){
343	pthread_join(threads[i], 0);
344	}
345
346	uint64_t elapsed_time = msclock() - start_time;
347
348	// if (!silent) {
349	// 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",
350	// num_keys_tested,
351	// log(num_keys_tested) / log(2.0),
352	// (float)elapsed_time/1000.0,
353	// (float)num_keys_tested / ((float)elapsed_time / 1000.0),
354	// log((float)num_keys_tested / ((float)elapsed_time/1000.0)) / log(2.0));
355	// }
356
357	if (bf_rate != NULL) {
358	*bf_rate = (float)num_keys_tested / ((float)elapsed_time / 1000.0);
359	}
360
361	return (keys_found != 0);
362	}
363
364
365	static bool read_bench_data(statelist_t *test_candidates) {
366
367	size_t bytes_read = 0;
368	uint32_t temp = 0;
369	uint32_t num_states = 0;
370	uint32_t states_read = 0;
371
372	char bench_file_path[strlen(get_my_executable_directory()) + strlen(TEST_BENCH_FILENAME) + 1];
373	strcpy(bench_file_path, get_my_executable_directory());
374	strcat(bench_file_path, TEST_BENCH_FILENAME);
375
376	FILE *benchfile = fopen(bench_file_path, "rb");
377	if (benchfile == NULL) {
378	return false;
379	}
380	bytes_read = fread(&nonces_to_bruteforce, 1, sizeof(nonces_to_bruteforce), benchfile);
381	if (bytes_read != sizeof(nonces_to_bruteforce)) {
382	fclose(benchfile);
383	return false;
384	}
385	for (uint16_t i = 0; i < nonces_to_bruteforce && i < 256; i++) {
386	bytes_read = fread(&bf_test_nonce[i], 1, sizeof(uint32_t), benchfile);
387	if (bytes_read != sizeof(uint32_t)) {
388	fclose(benchfile);
389	return false;
390	}
391	bf_test_nonce_2nd_byte[i] = (bf_test_nonce[i] >> 16) & 0xff;
392	bytes_read = fread(&bf_test_nonce_par[i], 1, sizeof(uint8_t), benchfile);
393	if (bytes_read != sizeof(uint8_t)) {
394	fclose(benchfile);
395	return false;
396	}
397	}
398	bytes_read = fread(&num_states, 1, sizeof(uint32_t), benchfile);
399	if (bytes_read != sizeof(uint32_t)) {
400	fclose(benchfile);
401	return false;
402	}
403	for (states_read = 0; states_read < MIN(num_states, TEST_BENCH_SIZE); states_read++) {
404	bytes_read = fread(test_candidates->states[EVEN_STATE] + states_read, 1, sizeof(uint32_t), benchfile);
405	if (bytes_read != sizeof(uint32_t)) {
406	fclose(benchfile);
407	return false;
408	}
409	}
410	for (uint32_t i = states_read; i < TEST_BENCH_SIZE; i++) {
411	test_candidates->states[EVEN_STATE][i] = test_candidates->states[EVEN_STATE][i-states_read];
412	}
413	for (uint32_t i = states_read; i < num_states; i++) {
414	bytes_read = fread(&temp, 1, sizeof(uint32_t), benchfile);
415	if (bytes_read != sizeof(uint32_t)) {
416	fclose(benchfile);
417	return false;
418	}
419	}
420	for (states_read = 0; states_read < MIN(num_states, TEST_BENCH_SIZE); states_read++) {
421	bytes_read = fread(test_candidates->states[ODD_STATE] + states_read, 1, sizeof(uint32_t), benchfile);
422	if (bytes_read != sizeof(uint32_t)) {
423	fclose(benchfile);
424	return false;
425	}
426	}
427	for (uint32_t i = states_read; i < TEST_BENCH_SIZE; i++) {
428	test_candidates->states[ODD_STATE][i] = test_candidates->states[ODD_STATE][i-states_read];
429	}
430
431	fclose(benchfile);
432	return true;
433	}
434
435
436	float brute_force_benchmark()
437	{
438	statelist_t test_candidates[NUM_BRUTE_FORCE_THREADS];
439
440	test_candidates[0].states[ODD_STATE] = malloc((TEST_BENCH_SIZE+1) * sizeof(uint32_t));
441	test_candidates[0].states[EVEN_STATE] = malloc((TEST_BENCH_SIZE+1) * sizeof(uint32_t));
442	for (uint8_t i = 0; i < NUM_BRUTE_FORCE_THREADS - 1; i++){
443	test_candidates[i].next = test_candidates + i + 1;
444	test_candidates[i+1].states[ODD_STATE] = test_candidates[0].states[ODD_STATE];
445	test_candidates[i+1].states[EVEN_STATE] = test_candidates[0].states[EVEN_STATE];
446	}
447	test_candidates[NUM_BRUTE_FORCE_THREADS-1].next = NULL;
448
449	if (!read_bench_data(test_candidates)) {
450	PrintAndLog("Couldn't read benchmark data. Assuming brute force rate of %1.0f states per second", DEFAULT_BRUTE_FORCE_RATE);
451	return DEFAULT_BRUTE_FORCE_RATE;
452	}
453
454	for (uint8_t i = 0; i < NUM_BRUTE_FORCE_THREADS; i++) {
455	test_candidates[i].len[ODD_STATE] = TEST_BENCH_SIZE;
456	test_candidates[i].len[EVEN_STATE] = TEST_BENCH_SIZE;
457	test_candidates[i].states[ODD_STATE][TEST_BENCH_SIZE] = -1;
458	test_candidates[i].states[EVEN_STATE][TEST_BENCH_SIZE] = -1;
459	}
460
461	uint64_t maximum_states = TEST_BENCH_SIZETEST_BENCH_SIZE(uint64_t)NUM_BRUTE_FORCE_THREADS;
462
463	float bf_rate;
464	brute_force_bs(&bf_rate, test_candidates, 0, 0, maximum_states, NULL, 0);
465
466	free(test_candidates[0].states[ODD_STATE]);
467	free(test_candidates[0].states[EVEN_STATE]);
468
469	return bf_rate;
470	}
471
472