| 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 | |
| 179 | static void write_bitflips_file(odd_even_t odd_even, uint16_t bitflip, int sum_a0, uint32_t *bitset, uint32_t count) |
| 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"); |
| 184 | fwrite(&count, 1, sizeof(count), outfile); |
| 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 == 2*p*(16-2*q) + (16-2*p)*2*q) { |
| 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 |
| 373 | write_bitflips_file(odd_even, bitflip, sum_a0, test_bitarray[odd_even], count[odd_even]); |
| 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 |
| 400 | write_bitflips_file(odd_even, bitflip | BITFLIP_2ND_BYTE, sum_a0, test_bitarray_2nd, count[odd_even]); |
| 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 |
| 485 | write_bitflips_file(odd_even, bitflip|0x100, sum_a0, test_not_bitarray[odd_even], count[odd_even]); |
| 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 |
| 512 | write_bitflips_file(odd_even, bitflip | 0x100 | BITFLIP_2ND_BYTE, sum_a0, test_bitarray_2nd, count[odd_even]); |
| 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 | } |