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

//-----------------------------------------------------------------------------
// 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
//-----------------------------------------------------------------------------
//
// This program calculates tables with possible states for a given
// bitflip property.
//
//-----------------------------------------------------------------------------

#include <inttypes.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <time.h>
#include "crapto1/crapto1.h"
#include "parity.h"


#define NUM_PART_SUMS 		9
#define BITFLIP_2ND_BYTE	0x0200

typedef enum {
	EVEN_STATE = 0,
	ODD_STATE = 1
} odd_even_t;


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;
}


//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// bitarray functions

#define malloc_bitarray(x) __builtin_assume_aligned(_aligned_malloc(x, __BIGGEST_ALIGNMENT__), __BIGGEST_ALIGNMENT__)
#define free_bitarray(x) _aligned_free(x)

static inline void clear_bitarray24(uint32_t *bitarray)
{
	memset(bitarray, 0x00, sizeof(uint32_t) * (1<<19));
}


static inline uint32_t test_bit24(uint32_t *bitarray, uint32_t index)
{
	return 	bitarray[index>>5] & (0x80000000>>(index&0x0000001f));
}


static inline void set_bit24(uint32_t *bitarray, uint32_t index)
{
	bitarray[index>>5] |= 0x80000000>>(index&0x0000001f);
}


static inline uint32_t next_state(uint32_t *bitset, uint32_t state)
{
	if (++state == 1<<24) return 1<<24;
	uint32_t index = state >> 5;
	uint_fast8_t bit = state & 0x1f;
	uint32_t line = bitset[index] << bit;
	while (bit <= 0x1f) {
		if (line & 0x80000000) return state;
		state++;
		bit++;
		line <<= 1;
	}
	index++;
	while (bitset[index] == 0x00000000 && state < 1<<24) {
		index++;
		state += 0x20;
	}
	if (state >= 1<<24) return 1<<24;
#if defined __GNUC__
	return state + __builtin_clz(bitset[index]);
#else
	bit = 0x00;
	line = bitset[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 *bitset, uint32_t state)
{
	if (++state == 1<<24) return 1<<24;
	uint32_t index = state >> 5;
	uint_fast8_t bit = state & 0x1f;
	uint32_t line = bitset[index] << bit;
	while (bit <= 0x1f) {
		if ((line & 0x80000000) == 0) return state;
		state++;
		bit++;
		line <<= 1;
	}
	index++;
	while (bitset[index] == 0xffffffff && state < 1<<24) {
		index++;
		state += 0x20;
	}
	if (state >= 1<<24) return 1<<24;
#if defined __GNUC__
	return state + __builtin_clz(~bitset[index]);
#else
	bit = 0x00;
	line = bitset[index];
	while (bit <= 0x1f) {
		if ((line & 0x80000000) == 0) return state;
		state++;
		bit++;
		line <<= 1;
	}
	return 1<<24;
#endif
}


static inline uint32_t bitcount(uint32_t a)
{
#if defined __GNUC__
	return __builtin_popcountl(a);
#else
	a = a - ((a >> 1) & 0x55555555);
	a = (a & 0x33333333) + ((a >> 2) & 0x33333333);
	return (((a + (a >> 4)) & 0x0f0f0f0f) * 0x01010101) >> 24;
#endif
}


static inline uint32_t count_states(uint32_t *bitset)
{
	uint32_t count = 0;
	for (uint32_t i = 0; i < (1<<19); i++) {
		count += bitcount(bitset[i]);
	}
	return count;
}


static void write_bitflips_file(odd_even_t odd_even, uint16_t bitflip, int sum_a0, uint32_t *bitset, uint32_t count)
{
	char filename[80];
	sprintf(filename, "bitflip_%d_%03" PRIx16 "_sum%d_states.bin", odd_even, bitflip, sum_a0);
	FILE *outfile = fopen(filename, "wb");
	fwrite(&count, 1, sizeof(count), outfile);
	fwrite(bitset, 1, sizeof(uint32_t)*(1<<19), outfile);
	fclose(outfile);
}


uint32_t *restrict part_sum_a0_bitarrays[2][NUM_PART_SUMS];

static void init_part_sum_bitarrays(void)
{
	printf("init_part_sum_bitarrays()...");
	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);
			}
		}
	}
	printf("done.\n");
}


static void free_part_sum_bitarrays(void) 
{
	printf("free_part_sum_bitarrays()...");
	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]);
	}
	printf("done.\n");
}

uint32_t *restrict sum_a0_bitarray[2];

void init_sum_bitarray(uint16_t sum_a0)
{
	printf("init_sum_bitarray()...\n");
	for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) {
		sum_a0_bitarray[odd_even] = (uint32_t *)malloc_bitarray(sizeof(uint32_t) * (1<<19));
		if (sum_a0_bitarray[odd_even] == NULL) {
			printf("Out of memory error in init_sum_bitarrays(). Aborting...\n");
			exit(4);
		}
		clear_bitarray24(sum_a0_bitarray[odd_even]);
	}
	for (uint8_t p = 0; p < NUM_PART_SUMS; p++) {
		for (uint8_t q = 0; q < NUM_PART_SUMS; q++) {
			if (sum_a0 == 2*p*(16-2*q) + (16-2*p)*2*q) {
				for (uint32_t i = 0; i < (1<<19); i++) {
					sum_a0_bitarray[EVEN_STATE][i] |= part_sum_a0_bitarrays[EVEN_STATE][q][i];
					sum_a0_bitarray[ODD_STATE][i] |= part_sum_a0_bitarrays[ODD_STATE][p][i];
				}
			}
		}
	}
	for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) {
		uint32_t count = count_states(sum_a0_bitarray[odd_even]);
		printf("sum_a0_bitarray[%s] has %d states (%5.2f%%)\n", odd_even==EVEN_STATE?"even":"odd ", count, (float)count/(1<<24)*100.0);
	}
	printf("done.\n");
}

	
static void free_sum_bitarray(void)
{
	printf("free_sum_bitarray()...");
	free_bitarray(sum_a0_bitarray[ODD_STATE]);
	free_bitarray(sum_a0_bitarray[EVEN_STATE]);
	printf("done.\n");
}


static void precalculate_bit0_bitflip_bitarrays(uint8_t const bitflip, uint16_t const sum_a0)
{
	// #define TEST_RUN
	#ifdef TEST_RUN
	#define NUM_TEST_STATES	(1<<10)
	#else
	#define NUM_TEST_STATES (1<<23)
	#endif
	
	time_t start_time = time(NULL);
	time_t last_check_time = start_time;
	
	uint32_t *restrict test_bitarray[2];
	uint32_t *restrict test_not_bitarray[2];

	test_bitarray[EVEN_STATE] = malloc_bitarray(sizeof(uint32_t) * (1<<19));
	clear_bitarray24(test_bitarray[EVEN_STATE]);
	test_bitarray[ODD_STATE] = malloc_bitarray(sizeof(uint32_t) * (1<<19));
	clear_bitarray24(test_bitarray[ODD_STATE]);

	test_not_bitarray[EVEN_STATE] = malloc_bitarray(sizeof(uint32_t) * (1<<19));
	clear_bitarray24(test_not_bitarray[EVEN_STATE]);
	test_not_bitarray[ODD_STATE] = malloc_bitarray(sizeof(uint32_t) * (1<<19));
	clear_bitarray24(test_not_bitarray[ODD_STATE]);
	
	uint32_t count[2];
	bool all_odd_states_are_possible_for_notbitflip = false;

	printf("\n\nStarting search for crypto1 states resulting in bitflip property 0x%03x...\n", bitflip);
	for (uint32_t even_state = next_state(sum_a0_bitarray[EVEN_STATE], -1); even_state < NUM_TEST_STATES; even_state = next_state(sum_a0_bitarray[EVEN_STATE], even_state)) {
		bool even_state_is_possible = false;
		time_t time_now = time(NULL);
		if (difftime(time_now, last_check_time) > 5*60) {	// print status every 5 minutes
			float runtime = difftime(time_now, start_time);
			float remaining_time = runtime * ((1<<23) - even_state) / even_state;
			printf("\n%1.1f hours elapsed, expected completion in %1.1f hours (%1.1f days)", runtime/3600, remaining_time/3600, remaining_time/3600/24); 
			last_check_time = time_now;
		}
		for (uint32_t odd_state = next_state(sum_a0_bitarray[ODD_STATE], -1); odd_state < (1<<24); odd_state = next_state(test_bitarray[ODD_STATE], odd_state)) {
			if (even_state_is_possible && test_bit24(test_bitarray[ODD_STATE], odd_state)) continue;
			// load crypto1 state
			struct Crypto1State cs;
			cs.odd = odd_state >> 4;
			cs.even = even_state >> 4;

			// track flipping bits in state
			struct Crypto1DeltaState {
				uint_fast8_t odd;
				uint_fast8_t even;
			} cs_delta;
			cs_delta.odd = 0;
			cs_delta.even = 0;
			
			uint_fast16_t keystream = 0;
			
			// decrypt 9 bits
			for (int i = 0; i < 9; i++) {
				uint_fast8_t keystream_bit = filter(cs.odd & 0x000fffff) ^ filter((cs.odd & 0x000fffff) ^ cs_delta.odd); 
				keystream = keystream << 1 | keystream_bit;
				uint_fast8_t nt_bit = BIT(bitflip, i) ^ keystream_bit;
				uint_fast8_t LSFR_feedback = BIT(cs_delta.odd, 2) ^ BIT(cs_delta.even, 2) ^ BIT(cs_delta.odd, 3); 

				cs_delta.even = cs_delta.even << 1 | (LSFR_feedback ^ nt_bit);
				uint_fast8_t tmp = cs_delta.odd;
				cs_delta.odd = cs_delta.even;
				cs_delta.even = tmp;

				cs.even = cs.odd;
				if (i & 1) {
					cs.odd = odd_state >> (7 - i) / 2;
				} else {
					cs.odd = even_state >> (7 - i) / 2;
				}
			}
			
			if (evenparity32(keystream) == evenparity32(bitflip)) {
				// found valid bitflip state
				even_state_is_possible = true;
				set_bit24(test_bitarray[EVEN_STATE], even_state);
				set_bit24(test_bitarray[EVEN_STATE], 1 << 23 | even_state);
				set_bit24(test_bitarray[ODD_STATE], odd_state);
			} else {
				// found valid !bitflip state
				set_bit24(test_not_bitarray[EVEN_STATE], even_state);
				set_bit24(test_not_bitarray[EVEN_STATE], 1 << 23 | even_state);
				set_bit24(test_not_bitarray[ODD_STATE], odd_state);
			}				
		}
		if (!even_state_is_possible) {
			all_odd_states_are_possible_for_notbitflip = true;
		}
	}

	printf("\nAnalysis completed. Checking for effective bitflip properties...\n");
	for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) {
		count[odd_even] = count_states(test_bitarray[odd_even]);
		if (count[odd_even] != 1<<24) {
			printf("Writing %d possible %s states for bitflip property %03x (%d (%1.2f%%) states eliminated)\n", 
				count[odd_even], 
				odd_even==EVEN_STATE?"even":"odd", 
				bitflip, (1<<24) - count[odd_even],
				(float)((1<<24) - count[odd_even]) / (1<<24) * 100.0);
			#ifndef TEST_RUN
			write_bitflips_file(odd_even, bitflip, sum_a0, test_bitarray[odd_even], count[odd_even]);
			#endif
		} else {
			printf("All %s states for bitflip property %03x are possible. No file written.\n", odd_even==EVEN_STATE?"even":"odd", bitflip);
		}
	}
	uint32_t *restrict test_bitarray_2nd = malloc_bitarray(sizeof(uint32_t) * (1<<19));
	clear_bitarray24(test_bitarray_2nd);
	for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) {
		if (count[odd_even] != 1<<24) {
			for (uint32_t state = 0; state < (1<<24); state += 1<<4) {
				uint32_t line = test_bitarray[odd_even][state>>5];
				uint16_t half_line = state&0x000000010 ? line&0x0000ffff : line>>16;
				if (half_line != 0) {
					for (uint32_t low_bits = 0; low_bits < (1<<4); low_bits++) {
						set_bit24(test_bitarray_2nd, low_bits << 20 | state >> 4);
					}
				}
			}
			count[odd_even] = count_states(test_bitarray_2nd);
			if (count[odd_even] != 1<<24) {
				printf("Writing %d possible %s states for bitflip property %03x (%d (%1.2f%%) states eliminated)\n", 
					count[odd_even], 
					odd_even==EVEN_STATE?"even":"odd", 
					bitflip | BITFLIP_2ND_BYTE, (1<<24) - count[odd_even],
					(float)((1<<24) - count[odd_even]) / (1<<24) * 100.0);
				#ifndef TEST_RUN
				write_bitflips_file(odd_even, bitflip | BITFLIP_2ND_BYTE, sum_a0, test_bitarray_2nd, count[odd_even]);
				#endif
			} else {
				printf("All %s states for bitflip property %03x are possible. No file written.\n", odd_even==EVEN_STATE?"even":"odd", bitflip | BITFLIP_2ND_BYTE);
			}
		} else {
			printf("All %s states for bitflip property %03x are possible. No file written.\n", odd_even==EVEN_STATE?"even":"odd", bitflip | BITFLIP_2ND_BYTE);
		}
	}

	////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	// second run for the remaining "not bitflip" states
	printf("\n\nStarting search for crypto1 states resulting in bitflip property 0x%03x...", bitflip | 0x100);
	start_time = time(NULL);
	last_check_time = start_time;
	for (uint32_t even_state = next_state(sum_a0_bitarray[EVEN_STATE], -1); even_state < NUM_TEST_STATES; even_state = next_state(sum_a0_bitarray[EVEN_STATE], even_state)) {
		bool even_state_is_possible = test_bit24(test_not_bitarray[EVEN_STATE], even_state);
		time_t time_now = time(NULL);
		if (difftime(time_now, last_check_time) > 5*60) {	// print status every 5 minutes
			float runtime = difftime(time_now, start_time);
			float remaining_time = runtime * ((1<<23) - even_state) / even_state;
			printf("\n%1.1f hours elapsed, expected completion in %1.1f hours (%1.1f days)", runtime/3600, remaining_time/3600, remaining_time/3600/24); 
			last_check_time = time_now;
		}
		for (uint32_t odd_state = next_state(sum_a0_bitarray[ODD_STATE], -1); odd_state < (1<<24); odd_state = next_state(sum_a0_bitarray[ODD_STATE], odd_state)) {
			if (even_state_is_possible) {
				if (all_odd_states_are_possible_for_notbitflip) break;
				if (test_bit24(test_not_bitarray[ODD_STATE], odd_state)) continue;
			}
			// load crypto1 state
			struct Crypto1State cs;
			cs.odd = odd_state >> 4;
			cs.even = even_state >> 4;

			// track flipping bits in state
			struct Crypto1DeltaState {
				uint_fast8_t odd;
				uint_fast8_t even;
			} cs_delta;
			cs_delta.odd = 0;
			cs_delta.even = 0;
			
			uint_fast16_t keystream = 0;
			// uint_fast16_t nt = 0;
			
			// decrypt 9 bits
			for (int i = 0; i < 9; i++) {
				uint_fast8_t keystream_bit = filter(cs.odd & 0x000fffff) ^ filter((cs.odd & 0x000fffff) ^ cs_delta.odd); 
				keystream = keystream << 1 | keystream_bit;
				uint_fast8_t nt_bit = BIT(bitflip|0x100, i) ^ keystream_bit;
				uint_fast8_t LSFR_feedback = BIT(cs_delta.odd, 2) ^ BIT(cs_delta.even, 2) ^ BIT(cs_delta.odd, 3); 

				cs_delta.even = cs_delta.even << 1 | (LSFR_feedback ^ nt_bit);
				uint_fast8_t tmp = cs_delta.odd;
				cs_delta.odd = cs_delta.even;
				cs_delta.even = tmp;

				cs.even = cs.odd;
				if (i & 1) {
					cs.odd = odd_state >> (7 - i) / 2;
				} else {
					cs.odd = even_state >> (7 - i) / 2;
				}
			}
			
			if (evenparity32(keystream) != evenparity32(bitflip)) {
				// found valid !bitflip state
				even_state_is_possible = true;
				set_bit24(test_not_bitarray[EVEN_STATE], even_state);
				set_bit24(test_not_bitarray[EVEN_STATE], 1 << 23 | even_state);
				set_bit24(test_not_bitarray[ODD_STATE], odd_state);
			}
		}
	}
	
	printf("\nAnalysis completed. Checking for effective !bitflip properties...\n");
	for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) {
		count[odd_even] = count_states(test_not_bitarray[odd_even]);
		if (count[odd_even] != 1<<24) {
			printf("Writing %d possible %s states for bitflip property %03x (%d (%1.2f%%) states eliminated)\n", 
				count[odd_even], 
				odd_even==EVEN_STATE?"even":"odd", 
				bitflip|0x100, (1<<24) - count[odd_even],
				(float)((1<<24) - count[odd_even]) / (1<<24) * 100.0);
			#ifndef TEST_RUN
			write_bitflips_file(odd_even, bitflip|0x100, sum_a0, test_not_bitarray[odd_even], count[odd_even]);
			#endif
		} else {
			printf("All %s states for bitflip property %03x are possible. No file written.\n", odd_even==EVEN_STATE?"even":"odd", bitflip|0x100);
		}
	}

	clear_bitarray24(test_bitarray_2nd);
	for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) {
		if (count[odd_even] != 1<<24) {
			for (uint32_t state = 0; state < (1<<24); state += 1<<4) {
				uint32_t line = test_not_bitarray[odd_even][state>>5];
				uint16_t half_line = state&0x000000010 ? line&0x0000ffff : line>>16;
				if (half_line != 0) {
					for (uint32_t low_bits = 0; low_bits < (1<<4); low_bits++) {
						set_bit24(test_bitarray_2nd, low_bits << 20 | state >> 4);
					}
				}
			}
			count[odd_even] = count_states(test_bitarray_2nd);
			if (count[odd_even] != 1<<24) {
				printf("Writing %d possible %s states for bitflip property %03x (%d (%1.2f%%) states eliminated)\n", 
					count[odd_even], 
					odd_even==EVEN_STATE?"even":"odd", 
					bitflip | 0x100| BITFLIP_2ND_BYTE, (1<<24) - count[odd_even],
					(float)((1<<24) - count[odd_even]) / (1<<24) * 100.0);
				#ifndef TEST_RUN
				write_bitflips_file(odd_even, bitflip | 0x100 | BITFLIP_2ND_BYTE, sum_a0, test_bitarray_2nd, count[odd_even]);
				#endif
			} else {
				printf("All %s states for bitflip property %03x are possible. No file written.\n", odd_even==EVEN_STATE?"even":"odd", bitflip | 0x100 | BITFLIP_2ND_BYTE);
			}
		} else {
			printf("All %s states for bitflip property %03x are possible. No file written.\n", odd_even==EVEN_STATE?"even":"odd", bitflip | 0x100 | BITFLIP_2ND_BYTE);
		}
	}

	free_bitarray(test_bitarray_2nd);
	free_bitarray(test_not_bitarray[ODD_STATE]);
	free_bitarray(test_not_bitarray[EVEN_STATE]);
	free_bitarray(test_bitarray[ODD_STATE]);
	free_bitarray(test_bitarray[EVEN_STATE]);
	
	exit(0);
}


int main (int argc, char *argv[]) {

	unsigned int bitflip_in;
	int sum_a0;
	
	printf("Create tables required by hardnested attack.\n");
	printf("Expect a runtime in the range of days or weeks.\n");
	printf("Single thread only. If you want to use several threads, start it multiple times :-)\n\n");

	if (argc != 2 && argc != 3) {
		printf(" syntax: %s <bitflip property> [<Sum_a0>]\n\n", argv[0]);
		printf(" example: %s 1f\n", argv[0]);
		return 1;
	}

	sscanf(argv[1],"%x", &bitflip_in);

	if (bitflip_in > 255) {
		printf("Bitflip property must be less than or equal to 0xff\n\n");
		return 1;
	}
	
	if(argc == 3) {
		sscanf(argv[2], "%d", &sum_a0);
	}

	switch (sum_a0) {
		case 0:
		case  32:
		case  56:
		case  64:
		case  80:
		case  96:
		case  104:
		case  112:
		case  120:
		case  128:
		case  136:
		case  144:
		case  152:
		case  160:
		case  176:
		case  192:
		case  200:
		case  224:
		case  256: break;
		default: sum_a0 = -1;
	}
	
	printf("Calculating for bitflip = %02x, sum_a0 = %d\n", bitflip_in, sum_a0);
	
	init_part_sum_bitarrays();
	init_sum_bitarray(sum_a0);
	
	precalculate_bit0_bitflip_bitarrays(bitflip_in, sum_a0);

	free_sum_bitarray();
	free_part_sum_bitarrays();
	
	return 0;
}
Commit	Line	Data
c48c4d78	1	//-----------------------------------------------------------------------------
	2	// Copyright (C) 2015, 2016 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	// This program calculates tables with possible states for a given
	18	// bitflip property.
	19	//
	20	//-----------------------------------------------------------------------------
	21
	22	#include <inttypes.h>
	23	#include <stdbool.h>
	24	#include <stdlib.h>
	25	#include <string.h>
	26	#include <stdio.h>
	27	#include <time.h>
	28	#include "crapto1/crapto1.h"
	29	#include "parity.h"
	30
	31
	32	#define NUM_PART_SUMS 9
	33	#define BITFLIP_2ND_BYTE 0x0200
	34
	35	typedef enum {
	36	EVEN_STATE = 0,
	37	ODD_STATE = 1
	38	} odd_even_t;
	39
	40
	41	static uint16_t PartialSumProperty(uint32_t state, odd_even_t odd_even)
	42	{
	43	uint16_t sum = 0;
	44	for (uint16_t j = 0; j < 16; j++) {
	45	uint32_t st = state;
	46	uint16_t part_sum = 0;
	47	if (odd_even == ODD_STATE) {
	48	for (uint16_t i = 0; i < 5; i++) {
	49	part_sum ^= filter(st);
	50	st = (st << 1) \| ((j >> (3-i)) & 0x01) ;
	51	}
	52	part_sum ^= 1; // XOR 1 cancelled out for the other 8 bits
	53	} else {
	54	for (uint16_t i = 0; i < 4; i++) {
	55	st = (st << 1) \| ((j >> (3-i)) & 0x01) ;
	56	part_sum ^= filter(st);
	57	}
	58	}
	59	sum += part_sum;
	60	}
	61	return sum;
	62	}
	63
	64
65	//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
66	// bitarray functions
67
68	#define malloc_bitarray(x) __builtin_assume_aligned(_aligned_malloc(x, __BIGGEST_ALIGNMENT__), __BIGGEST_ALIGNMENT__)
69	#define free_bitarray(x) _aligned_free(x)
70
71	static inline void clear_bitarray24(uint32_t *bitarray)
72	{
73	memset(bitarray, 0x00, sizeof(uint32_t) * (1<<19));
74	}
75
76
77	static inline uint32_t test_bit24(uint32_t *bitarray, uint32_t index)
78	{
79	return bitarray[index>>5] & (0x80000000>>(index&0x0000001f));
80	}
81
82
83	static inline void set_bit24(uint32_t *bitarray, uint32_t index)
84	{
85	bitarray[index>>5] \|= 0x80000000>>(index&0x0000001f);
86	}
87
88
89	static inline uint32_t next_state(uint32_t *bitset, uint32_t state)
90	{
91	if (++state == 1<<24) return 1<<24;
92	uint32_t index = state >> 5;
93	uint_fast8_t bit = state & 0x1f;
94	uint32_t line = bitset[index] << bit;
95	while (bit <= 0x1f) {
96	if (line & 0x80000000) return state;
97	state++;
98	bit++;
99	line <<= 1;
100	}
101	index++;
102	while (bitset[index] == 0x00000000 && state < 1<<24) {
103	index++;
104	state += 0x20;
105	}
106	if (state >= 1<<24) return 1<<24;
107	#if defined __GNUC__
108	return state + __builtin_clz(bitset[index]);
109	#else
110	bit = 0x00;
111	line = bitset[index];
112	while (bit <= 0x1f) {
113	if (line & 0x80000000) return state;
114	state++;
115	bit++;
116	line <<= 1;
117	}
118	return 1<<24;
119	#endif
120	}
121
122
123	static inline uint32_t next_not_state(uint32_t *bitset, uint32_t state)
124	{
125	if (++state == 1<<24) return 1<<24;
126	uint32_t index = state >> 5;
127	uint_fast8_t bit = state & 0x1f;
128	uint32_t line = bitset[index] << bit;
129	while (bit <= 0x1f) {
130	if ((line & 0x80000000) == 0) return state;
131	state++;
132	bit++;
133	line <<= 1;
134	}
135	index++;
136	while (bitset[index] == 0xffffffff && state < 1<<24) {
137	index++;
138	state += 0x20;
139	}
140	if (state >= 1<<24) return 1<<24;
141	#if defined __GNUC__
142	return state + __builtin_clz(~bitset[index]);
143	#else
144	bit = 0x00;
145	line = bitset[index];
146	while (bit <= 0x1f) {
147	if ((line & 0x80000000) == 0) return state;
148	state++;
149	bit++;
150	line <<= 1;
151	}
152	return 1<<24;
153	#endif
154	}
155
156
157	static inline uint32_t bitcount(uint32_t a)
158	{
159	#if defined __GNUC__
160	return __builtin_popcountl(a);
161	#else
162	a = a - ((a >> 1) & 0x55555555);
163	a = (a & 0x33333333) + ((a >> 2) & 0x33333333);
164	return (((a + (a >> 4)) & 0x0f0f0f0f) * 0x01010101) >> 24;
165	#endif
166	}
167
168
169	static inline uint32_t count_states(uint32_t *bitset)
170	{
171	uint32_t count = 0;
172	for (uint32_t i = 0; i < (1<<19); i++) {
173	count += bitcount(bitset[i]);
174	}
175	return count;
176	}
177
178
7f9e4c25	179	static void write_bitflips_file(odd_even_t odd_even, uint16_t bitflip, int sum_a0, uint32_t *bitset, uint32_t count)
c48c4d78	180	{
	181	char filename[80];
	182	sprintf(filename, "bitflip_%d_%03" PRIx16 "_sum%d_states.bin", odd_even, bitflip, sum_a0);
	183	FILE *outfile = fopen(filename, "wb");
7f9e4c25	184	fwrite(&count, 1, sizeof(count), outfile);
c48c4d78	185	fwrite(bitset, 1, sizeof(uint32_t)*(1<<19), outfile);
	186	fclose(outfile);
	187	}
	188
	189
	190	uint32_t *restrict part_sum_a0_bitarrays[2][NUM_PART_SUMS];
	191
	192	static void init_part_sum_bitarrays(void)
	193	{
	194	printf("init_part_sum_bitarrays()...");
	195	for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) {
	196	for (uint16_t part_sum_a0 = 0; part_sum_a0 < NUM_PART_SUMS; part_sum_a0++) {
	197	part_sum_a0_bitarrays[odd_even][part_sum_a0] = (uint32_t )malloc_bitarray(sizeof(uint32_t) (1<<19));
	198	if (part_sum_a0_bitarrays[odd_even][part_sum_a0] == NULL) {
	199	printf("Out of memory error in init_part_suma0_statelists(). Aborting...\n");
	200	exit(4);
	201	}
	202	clear_bitarray24(part_sum_a0_bitarrays[odd_even][part_sum_a0]);
	203	}
	204	}
	205	for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) {
	206	//printf("(%d, %" PRIu16 ")...", odd_even, part_sum_a0);
	207	for (uint32_t state = 0; state < (1<<20); state++) {
	208	uint16_t part_sum_a0 = PartialSumProperty(state, odd_even) / 2;
	209	for (uint16_t low_bits = 0; low_bits < 1<<4; low_bits++) {
	210	set_bit24(part_sum_a0_bitarrays[odd_even][part_sum_a0], state<<4 \| low_bits);
	211	}
	212	}
	213	}
	214	printf("done.\n");
	215	}
	216
	217
	218	static void free_part_sum_bitarrays(void)
	219	{
	220	printf("free_part_sum_bitarrays()...");
	221	for (int16_t part_sum_a0 = (NUM_PART_SUMS-1); part_sum_a0 >= 0; part_sum_a0--) {
	222	free_bitarray(part_sum_a0_bitarrays[ODD_STATE][part_sum_a0]);
	223	}
	224	for (int16_t part_sum_a0 = (NUM_PART_SUMS-1); part_sum_a0 >= 0; part_sum_a0--) {
	225	free_bitarray(part_sum_a0_bitarrays[EVEN_STATE][part_sum_a0]);
	226	}
	227	printf("done.\n");
	228	}
	229
	230	uint32_t *restrict sum_a0_bitarray[2];
	231
	232	void init_sum_bitarray(uint16_t sum_a0)
	233	{
	234	printf("init_sum_bitarray()...\n");
	235	for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) {
	236	sum_a0_bitarray[odd_even] = (uint32_t )malloc_bitarray(sizeof(uint32_t) (1<<19));
	237	if (sum_a0_bitarray[odd_even] == NULL) {
	238	printf("Out of memory error in init_sum_bitarrays(). Aborting...\n");
	239	exit(4);
	240	}
	241	clear_bitarray24(sum_a0_bitarray[odd_even]);
	242	}
	243	for (uint8_t p = 0; p < NUM_PART_SUMS; p++) {
	244	for (uint8_t q = 0; q < NUM_PART_SUMS; q++) {
	245	if (sum_a0 == 2p(16-2q) + (16-2p)2q) {
	246	for (uint32_t i = 0; i < (1<<19); i++) {
	247	sum_a0_bitarray[EVEN_STATE][i] \|= part_sum_a0_bitarrays[EVEN_STATE][q][i];
	248	sum_a0_bitarray[ODD_STATE][i] \|= part_sum_a0_bitarrays[ODD_STATE][p][i];
249	}
250	}
251	}
252	}
253	for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) {
254	uint32_t count = count_states(sum_a0_bitarray[odd_even]);
255	printf("sum_a0_bitarray[%s] has %d states (%5.2f%%)\n", odd_even==EVEN_STATE?"even":"odd ", count, (float)count/(1<<24)*100.0);
256	}
257	printf("done.\n");
258	}
259
260
261	static void free_sum_bitarray(void)
262	{
263	printf("free_sum_bitarray()...");
264	free_bitarray(sum_a0_bitarray[ODD_STATE]);
265	free_bitarray(sum_a0_bitarray[EVEN_STATE]);
266	printf("done.\n");
267	}
268
269
270	static void precalculate_bit0_bitflip_bitarrays(uint8_t const bitflip, uint16_t const sum_a0)
271	{
272	// #define TEST_RUN
273	#ifdef TEST_RUN
274	#define NUM_TEST_STATES (1<<10)
275	#else
276	#define NUM_TEST_STATES (1<<23)
277	#endif
278
279	time_t start_time = time(NULL);
280	time_t last_check_time = start_time;
281
282	uint32_t *restrict test_bitarray[2];
283	uint32_t *restrict test_not_bitarray[2];
284
285	test_bitarray[EVEN_STATE] = malloc_bitarray(sizeof(uint32_t) * (1<<19));
286	clear_bitarray24(test_bitarray[EVEN_STATE]);
287	test_bitarray[ODD_STATE] = malloc_bitarray(sizeof(uint32_t) * (1<<19));
288	clear_bitarray24(test_bitarray[ODD_STATE]);
289
290	test_not_bitarray[EVEN_STATE] = malloc_bitarray(sizeof(uint32_t) * (1<<19));
291	clear_bitarray24(test_not_bitarray[EVEN_STATE]);
292	test_not_bitarray[ODD_STATE] = malloc_bitarray(sizeof(uint32_t) * (1<<19));
293	clear_bitarray24(test_not_bitarray[ODD_STATE]);
294
295	uint32_t count[2];
296	bool all_odd_states_are_possible_for_notbitflip = false;
297
298	printf("\n\nStarting search for crypto1 states resulting in bitflip property 0x%03x...\n", bitflip);
299	for (uint32_t even_state = next_state(sum_a0_bitarray[EVEN_STATE], -1); even_state < NUM_TEST_STATES; even_state = next_state(sum_a0_bitarray[EVEN_STATE], even_state)) {
300	bool even_state_is_possible = false;
301	time_t time_now = time(NULL);
302	if (difftime(time_now, last_check_time) > 5*60) { // print status every 5 minutes
303	float runtime = difftime(time_now, start_time);
304	float remaining_time = runtime * ((1<<23) - even_state) / even_state;
305	printf("\n%1.1f hours elapsed, expected completion in %1.1f hours (%1.1f days)", runtime/3600, remaining_time/3600, remaining_time/3600/24);
306	last_check_time = time_now;
307	}
308	for (uint32_t odd_state = next_state(sum_a0_bitarray[ODD_STATE], -1); odd_state < (1<<24); odd_state = next_state(test_bitarray[ODD_STATE], odd_state)) {
309	if (even_state_is_possible && test_bit24(test_bitarray[ODD_STATE], odd_state)) continue;
310	// load crypto1 state
311	struct Crypto1State cs;
312	cs.odd = odd_state >> 4;
313	cs.even = even_state >> 4;
314
315	// track flipping bits in state
316	struct Crypto1DeltaState {
317	uint_fast8_t odd;
318	uint_fast8_t even;
319	} cs_delta;
320	cs_delta.odd = 0;
321	cs_delta.even = 0;
322
323	uint_fast16_t keystream = 0;
324
325	// decrypt 9 bits
326	for (int i = 0; i < 9; i++) {
327	uint_fast8_t keystream_bit = filter(cs.odd & 0x000fffff) ^ filter((cs.odd & 0x000fffff) ^ cs_delta.odd);
328	keystream = keystream << 1 \| keystream_bit;
329	uint_fast8_t nt_bit = BIT(bitflip, i) ^ keystream_bit;
330	uint_fast8_t LSFR_feedback = BIT(cs_delta.odd, 2) ^ BIT(cs_delta.even, 2) ^ BIT(cs_delta.odd, 3);
331
332	cs_delta.even = cs_delta.even << 1 \| (LSFR_feedback ^ nt_bit);
333	uint_fast8_t tmp = cs_delta.odd;
334	cs_delta.odd = cs_delta.even;
335	cs_delta.even = tmp;
336
337	cs.even = cs.odd;
338	if (i & 1) {
339	cs.odd = odd_state >> (7 - i) / 2;
340	} else {
341	cs.odd = even_state >> (7 - i) / 2;
342	}
343	}
344
345	if (evenparity32(keystream) == evenparity32(bitflip)) {
346	// found valid bitflip state
347	even_state_is_possible = true;
348	set_bit24(test_bitarray[EVEN_STATE], even_state);
349	set_bit24(test_bitarray[EVEN_STATE], 1 << 23 \| even_state);
350	set_bit24(test_bitarray[ODD_STATE], odd_state);
351	} else {
352	// found valid !bitflip state
353	set_bit24(test_not_bitarray[EVEN_STATE], even_state);
354	set_bit24(test_not_bitarray[EVEN_STATE], 1 << 23 \| even_state);
355	set_bit24(test_not_bitarray[ODD_STATE], odd_state);
356	}
357	}
358	if (!even_state_is_possible) {
359	all_odd_states_are_possible_for_notbitflip = true;
360	}
361	}
362
363	printf("\nAnalysis completed. Checking for effective bitflip properties...\n");
364	for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) {
365	count[odd_even] = count_states(test_bitarray[odd_even]);
366	if (count[odd_even] != 1<<24) {
367	printf("Writing %d possible %s states for bitflip property %03x (%d (%1.2f%%) states eliminated)\n",
368	count[odd_even],
369	odd_even==EVEN_STATE?"even":"odd",
370	bitflip, (1<<24) - count[odd_even],
371	(float)((1<<24) - count[odd_even]) / (1<<24) * 100.0);
372	#ifndef TEST_RUN
7f9e4c25	373	write_bitflips_file(odd_even, bitflip, sum_a0, test_bitarray[odd_even], count[odd_even]);
c48c4d78	374	#endif
	375	} else {
	376	printf("All %s states for bitflip property %03x are possible. No file written.\n", odd_even==EVEN_STATE?"even":"odd", bitflip);
	377	}
	378	}
	379	uint32_t restrict test_bitarray_2nd = malloc_bitarray(sizeof(uint32_t) (1<<19));
	380	clear_bitarray24(test_bitarray_2nd);
	381	for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) {
	382	if (count[odd_even] != 1<<24) {
	383	for (uint32_t state = 0; state < (1<<24); state += 1<<4) {
	384	uint32_t line = test_bitarray[odd_even][state>>5];
	385	uint16_t half_line = state&0x000000010 ? line&0x0000ffff : line>>16;
	386	if (half_line != 0) {
	387	for (uint32_t low_bits = 0; low_bits < (1<<4); low_bits++) {
	388	set_bit24(test_bitarray_2nd, low_bits << 20 \| state >> 4);
	389	}
	390	}
	391	}
	392	count[odd_even] = count_states(test_bitarray_2nd);
	393	if (count[odd_even] != 1<<24) {
	394	printf("Writing %d possible %s states for bitflip property %03x (%d (%1.2f%%) states eliminated)\n",
	395	count[odd_even],
	396	odd_even==EVEN_STATE?"even":"odd",
	397	bitflip \| BITFLIP_2ND_BYTE, (1<<24) - count[odd_even],
	398	(float)((1<<24) - count[odd_even]) / (1<<24) * 100.0);
	399	#ifndef TEST_RUN
7f9e4c25	400	write_bitflips_file(odd_even, bitflip \| BITFLIP_2ND_BYTE, sum_a0, test_bitarray_2nd, count[odd_even]);
c48c4d78	401	#endif
	402	} else {
	403	printf("All %s states for bitflip property %03x are possible. No file written.\n", odd_even==EVEN_STATE?"even":"odd", bitflip \| BITFLIP_2ND_BYTE);
	404	}
	405	} else {
	406	printf("All %s states for bitflip property %03x are possible. No file written.\n", odd_even==EVEN_STATE?"even":"odd", bitflip \| BITFLIP_2ND_BYTE);
	407	}
	408	}
	409
	410	////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	411	// second run for the remaining "not bitflip" states
	412	printf("\n\nStarting search for crypto1 states resulting in bitflip property 0x%03x...", bitflip \| 0x100);
	413	start_time = time(NULL);
	414	last_check_time = start_time;
	415	for (uint32_t even_state = next_state(sum_a0_bitarray[EVEN_STATE], -1); even_state < NUM_TEST_STATES; even_state = next_state(sum_a0_bitarray[EVEN_STATE], even_state)) {
	416	bool even_state_is_possible = test_bit24(test_not_bitarray[EVEN_STATE], even_state);
	417	time_t time_now = time(NULL);
	418	if (difftime(time_now, last_check_time) > 5*60) { // print status every 5 minutes
	419	float runtime = difftime(time_now, start_time);
	420	float remaining_time = runtime * ((1<<23) - even_state) / even_state;
	421	printf("\n%1.1f hours elapsed, expected completion in %1.1f hours (%1.1f days)", runtime/3600, remaining_time/3600, remaining_time/3600/24);
	422	last_check_time = time_now;
	423	}
	424	for (uint32_t odd_state = next_state(sum_a0_bitarray[ODD_STATE], -1); odd_state < (1<<24); odd_state = next_state(sum_a0_bitarray[ODD_STATE], odd_state)) {
	425	if (even_state_is_possible) {
	426	if (all_odd_states_are_possible_for_notbitflip) break;
	427	if (test_bit24(test_not_bitarray[ODD_STATE], odd_state)) continue;
	428	}
	429	// load crypto1 state
	430	struct Crypto1State cs;
	431	cs.odd = odd_state >> 4;
	432	cs.even = even_state >> 4;
	433
	434	// track flipping bits in state
	435	struct Crypto1DeltaState {
	436	uint_fast8_t odd;
	437	uint_fast8_t even;
	438	} cs_delta;
	439	cs_delta.odd = 0;
	440	cs_delta.even = 0;
	441
	442	uint_fast16_t keystream = 0;
	443	// uint_fast16_t nt = 0;
	444
	445	// decrypt 9 bits
	446	for (int i = 0; i < 9; i++) {
	447	uint_fast8_t keystream_bit = filter(cs.odd & 0x000fffff) ^ filter((cs.odd & 0x000fffff) ^ cs_delta.odd);
	448	keystream = keystream << 1 \| keystream_bit;
	449	uint_fast8_t nt_bit = BIT(bitflip\|0x100, i) ^ keystream_bit;
	450	uint_fast8_t LSFR_feedback = BIT(cs_delta.odd, 2) ^ BIT(cs_delta.even, 2) ^ BIT(cs_delta.odd, 3);
	451
	452	cs_delta.even = cs_delta.even << 1 \| (LSFR_feedback ^ nt_bit);
	453	uint_fast8_t tmp = cs_delta.odd;
	454	cs_delta.odd = cs_delta.even;
	455	cs_delta.even = tmp;
	456
	457	cs.even = cs.odd;
	458	if (i & 1) {
	459	cs.odd = odd_state >> (7 - i) / 2;
	460	} else {
	461	cs.odd = even_state >> (7 - i) / 2;
	462	}
	463	}
	464
465	if (evenparity32(keystream) != evenparity32(bitflip)) {
466	// found valid !bitflip state
467	even_state_is_possible = true;
468	set_bit24(test_not_bitarray[EVEN_STATE], even_state);
469	set_bit24(test_not_bitarray[EVEN_STATE], 1 << 23 \| even_state);
470	set_bit24(test_not_bitarray[ODD_STATE], odd_state);
471	}
472	}
473	}
474
475	printf("\nAnalysis completed. Checking for effective !bitflip properties...\n");
476	for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) {
477	count[odd_even] = count_states(test_not_bitarray[odd_even]);
478	if (count[odd_even] != 1<<24) {
479	printf("Writing %d possible %s states for bitflip property %03x (%d (%1.2f%%) states eliminated)\n",
480	count[odd_even],
481	odd_even==EVEN_STATE?"even":"odd",
482	bitflip\|0x100, (1<<24) - count[odd_even],
483	(float)((1<<24) - count[odd_even]) / (1<<24) * 100.0);
484	#ifndef TEST_RUN
7f9e4c25	485	write_bitflips_file(odd_even, bitflip\|0x100, sum_a0, test_not_bitarray[odd_even], count[odd_even]);
c48c4d78	486	#endif
	487	} else {
	488	printf("All %s states for bitflip property %03x are possible. No file written.\n", odd_even==EVEN_STATE?"even":"odd", bitflip\|0x100);
	489	}
	490	}
	491
	492	clear_bitarray24(test_bitarray_2nd);
	493	for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) {
	494	if (count[odd_even] != 1<<24) {
	495	for (uint32_t state = 0; state < (1<<24); state += 1<<4) {
	496	uint32_t line = test_not_bitarray[odd_even][state>>5];
	497	uint16_t half_line = state&0x000000010 ? line&0x0000ffff : line>>16;
	498	if (half_line != 0) {
	499	for (uint32_t low_bits = 0; low_bits < (1<<4); low_bits++) {
	500	set_bit24(test_bitarray_2nd, low_bits << 20 \| state >> 4);
	501	}
	502	}
	503	}
	504	count[odd_even] = count_states(test_bitarray_2nd);
	505	if (count[odd_even] != 1<<24) {
	506	printf("Writing %d possible %s states for bitflip property %03x (%d (%1.2f%%) states eliminated)\n",
	507	count[odd_even],
	508	odd_even==EVEN_STATE?"even":"odd",
	509	bitflip \| 0x100\| BITFLIP_2ND_BYTE, (1<<24) - count[odd_even],
	510	(float)((1<<24) - count[odd_even]) / (1<<24) * 100.0);
	511	#ifndef TEST_RUN
7f9e4c25	512	write_bitflips_file(odd_even, bitflip \| 0x100 \| BITFLIP_2ND_BYTE, sum_a0, test_bitarray_2nd, count[odd_even]);
c48c4d78	513	#endif
	514	} else {
	515	printf("All %s states for bitflip property %03x are possible. No file written.\n", odd_even==EVEN_STATE?"even":"odd", bitflip \| 0x100 \| BITFLIP_2ND_BYTE);
	516	}
	517	} else {
	518	printf("All %s states for bitflip property %03x are possible. No file written.\n", odd_even==EVEN_STATE?"even":"odd", bitflip \| 0x100 \| BITFLIP_2ND_BYTE);
	519	}
	520	}
	521
	522	free_bitarray(test_bitarray_2nd);
	523	free_bitarray(test_not_bitarray[ODD_STATE]);
	524	free_bitarray(test_not_bitarray[EVEN_STATE]);
	525	free_bitarray(test_bitarray[ODD_STATE]);
	526	free_bitarray(test_bitarray[EVEN_STATE]);
	527
	528	exit(0);
	529	}
	530
	531
	532	int main (int argc, char *argv[]) {
	533
	534	unsigned int bitflip_in;
	535	int sum_a0;
	536
	537	printf("Create tables required by hardnested attack.\n");
	538	printf("Expect a runtime in the range of days or weeks.\n");
	539	printf("Single thread only. If you want to use several threads, start it multiple times :-)\n\n");
	540
	541	if (argc != 2 && argc != 3) {
	542	printf(" syntax: %s <bitflip property> [<Sum_a0>]\n\n", argv[0]);
	543	printf(" example: %s 1f\n", argv[0]);
	544	return 1;
	545	}
	546
	547	sscanf(argv[1],"%x", &bitflip_in);
	548
	549	if (bitflip_in > 255) {
	550	printf("Bitflip property must be less than or equal to 0xff\n\n");
	551	return 1;
	552	}
	553
	554	if(argc == 3) {
	555	sscanf(argv[2], "%d", &sum_a0);
	556	}
	557
	558	switch (sum_a0) {
	559	case 0:
	560	case 32:
	561	case 56:
	562	case 64:
	563	case 80:
	564	case 96:
	565	case 104:
	566	case 112:
	567	case 120:
	568	case 128:
	569	case 136:
	570	case 144:
	571	case 152:
	572	case 160:
	573	case 176:
	574	case 192:
	575	case 200:
	576	case 224:
577	case 256: break;
578	default: sum_a0 = -1;
579	}
580
581	printf("Calculating for bitflip = %02x, sum_a0 = %d\n", bitflip_in, sum_a0);
582
583	init_part_sum_bitarrays();
584	init_sum_bitarray(sum_a0);
585
586	precalculate_bit0_bitflip_bitarrays(bitflip_in, sum_a0);
587
588	free_sum_bitarray();
589	free_part_sum_bitarrays();
590
591	return 0;
592	}