git.zerfleddert.de Git - proxmark3-svn/blob - client/hardnested/hardnested_bf_core.c

   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_bf_core.h"
  51
  52 #include <stdint.h>
  53 #include <stdbool.h>
  54 #include <stdlib.h>
  55 #ifndef __APPLE__
  56 #include <malloc.h>
  57 #endif
  58 #include <stdio.h>
  59 #include <string.h>
  60 #include "crapto1/crapto1.h"
  61 #include "parity.h"
  62
  63 // bitslice type
  64 // while AVX supports 256 bit vector floating point operations, we need integer operations for boolean logic
  65 // same for AVX2 and 512 bit vectors
  66 // using larger vectors works but seems to generate more register pressure
  67 #if defined(__AVX512F__)
  68 #define MAX_BITSLICES 512
  69 #elif defined(__AVX2__)
  70 #define MAX_BITSLICES 256
  71 #elif defined(__AVX__)
  72 #define MAX_BITSLICES 128
  73 #elif defined(__SSE2__)
  74 #define MAX_BITSLICES 128
  75 #else // MMX or SSE or NOSIMD
  76 #define MAX_BITSLICES 64
  77 #endif
  78
  79 #define VECTOR_SIZE (MAX_BITSLICES/8)
  80 typedef unsigned int __attribute__((aligned(VECTOR_SIZE))) __attribute__((vector_size(VECTOR_SIZE))) bitslice_value_t;
  81 typedef union {
  82         bitslice_value_t value;
  83         uint64_t bytes64[MAX_BITSLICES/64];
  84         uint8_t bytes[MAX_BITSLICES/8];
  85 } bitslice_t;
  86
  87 // filter function (f20)
  88 // sourced from ``Wirelessly Pickpocketing a Mifare Classic Card'' by Flavio Garcia, Peter van Rossum, Roel Verdult and Ronny Wichers Schreur
  89 #define f20a(a,b,c,d) (((a|b)^(a&d))^(c&((a^b)|d)))
  90 #define f20b(a,b,c,d) (((a&b)|c)^((a^b)&(c|d)))
  91 #define f20c(a,b,c,d,e) ((a|((b|e)&(d^e)))^((a^(b&d))&((c^d)|(b&e))))
  92
  93 // bit indexing
  94 #define get_bit(n, word) (((word) >> (n)) & 1)
  95 #define get_vector_bit(slice, value) get_bit((slice)&0x3f, value.bytes64[(slice)>>6])
  96
  97 // size of crypto-1 state
  98 #define STATE_SIZE 48
  99 // size of nonce to be decrypted
 100 #define KEYSTREAM_SIZE 24
 101
 102 // endianness conversion
 103 #define rev32(word) ((((word) & 0xff) << 24) | ((((word) >> 8) & 0xff) << 16) | ((((word) >> 16) & 0xff) << 8) | ((((word) >> 24) & 0xff)))
 104
 105 // this needs to be compiled several times for each instruction set.
 106 // For each instruction set, define a dedicated function name:
 107 #if defined (__AVX512F__)
 108 #define BITSLICE_TEST_NONCES bitslice_test_nonces_AVX512
 109 #define CRACK_STATES_BITSLICED crack_states_bitsliced_AVX512
 110 #elif defined (__AVX2__)
 111 #define BITSLICE_TEST_NONCES bitslice_test_nonces_AVX2
 112 #define CRACK_STATES_BITSLICED crack_states_bitsliced_AVX2
 113 #elif defined (__AVX__)
 114 #define BITSLICE_TEST_NONCES bitslice_test_nonces_AVX
 115 #define CRACK_STATES_BITSLICED crack_states_bitsliced_AVX
 116 #elif defined (__SSE2__)
 117 #define BITSLICE_TEST_NONCES bitslice_test_nonces_SSE2
 118 #define CRACK_STATES_BITSLICED crack_states_bitsliced_SSE2
 119 #elif defined (__MMX__)
 120 #define BITSLICE_TEST_NONCES bitslice_test_nonces_MMX
 121 #define CRACK_STATES_BITSLICED crack_states_bitsliced_MMX
 122 #else
 123 #define BITSLICE_TEST_NONCES bitslice_test_nonces_NOSIMD
 124 #define CRACK_STATES_BITSLICED crack_states_bitsliced_NOSIMD
 125 #endif
 126
 127 // typedefs and declaration of functions:
 128 typedef const uint64_t crack_states_bitsliced_t(uint32_t, uint8_t*, statelist_t*, uint32_t*, uint64_t*, uint32_t, uint8_t*, noncelist_t*);
 129 crack_states_bitsliced_t crack_states_bitsliced_AVX512;
 130 crack_states_bitsliced_t crack_states_bitsliced_AVX2;
 131 crack_states_bitsliced_t crack_states_bitsliced_AVX;
 132 crack_states_bitsliced_t crack_states_bitsliced_SSE2;
 133 crack_states_bitsliced_t crack_states_bitsliced_MMX;
 134 crack_states_bitsliced_t crack_states_bitsliced_NOSIMD;
 135 crack_states_bitsliced_t crack_states_bitsliced_dispatch;
 136
 137 typedef void bitslice_test_nonces_t(uint32_t, uint32_t*, uint8_t*);
 138 bitslice_test_nonces_t bitslice_test_nonces_AVX512;
 139 bitslice_test_nonces_t bitslice_test_nonces_AVX2;
 140 bitslice_test_nonces_t bitslice_test_nonces_AVX;
 141 bitslice_test_nonces_t bitslice_test_nonces_SSE2;
 142 bitslice_test_nonces_t bitslice_test_nonces_MMX;
 143 bitslice_test_nonces_t bitslice_test_nonces_NOSIMD;
 144 bitslice_test_nonces_t bitslice_test_nonces_dispatch;
 145
 146 #if defined (_WIN32)
 147 #define malloc_bitslice(x) __builtin_assume_aligned(_aligned_malloc((x), MAX_BITSLICES/8), MAX_BITSLICES/8)
 148 #define free_bitslice(x) _aligned_free(x)
 149 #elif defined (__APPLE__)
 150 static void *malloc_bitslice(size_t x) {
 151         char *allocated_memory;
 152         if (posix_memalign((void**)&allocated_memory, MAX_BITSLICES/8, x)) {
 153                 return NULL;
 154         } else {
 155                 return __builtin_assume_aligned(allocated_memory, MAX_BITSLICES/8);
 156         }
 157 }
 158 #define free_bitslice(x) free(x)
 159 #else
 160 #define malloc_bitslice(x) memalign(MAX_BITSLICES/8, (x))
 161 #define free_bitslice(x) free(x)
 162 #endif
 163
 164 typedef enum {
 165         EVEN_STATE = 0,
 166         ODD_STATE = 1
 167 } odd_even_t;
 168
 169
 170 // arrays of bitsliced states with identical values in all slices
 171 static bitslice_t bitsliced_encrypted_nonces[256][KEYSTREAM_SIZE];
 172 static bitslice_t bitsliced_encrypted_parity_bits[256][4];
 173 // 1 and 0 vectors
 174 static bitslice_t bs_ones;
 175 static bitslice_t bs_zeroes;
 176
 177
 178 void BITSLICE_TEST_NONCES(uint32_t nonces_to_bruteforce, uint32_t *bf_test_nonce, uint8_t *bf_test_nonce_par) {
 179
 180         // initialize 1 and 0 vectors
 181     memset(bs_ones.bytes, 0xff, VECTOR_SIZE);
 182     memset(bs_zeroes.bytes, 0x00, VECTOR_SIZE);
 183
 184         // bitslice nonces' 2nd to 4th byte
 185         for (uint32_t i = 0; i < nonces_to_bruteforce; i++) {
 186                 for(uint32_t bit_idx = 0; bit_idx < KEYSTREAM_SIZE; bit_idx++){
 187                         bool bit = get_bit(KEYSTREAM_SIZE-1-bit_idx, rev32(bf_test_nonce[i] << 8));
 188                         if(bit){
 189                                 bitsliced_encrypted_nonces[i][bit_idx].value = bs_ones.value;
 190                         } else {
 191                                 bitsliced_encrypted_nonces[i][bit_idx].value = bs_zeroes.value;
 192                         }
 193                 }
 194         }
 195         // bitslice nonces' parity (4 bits)
 196         for (uint32_t i = 0; i < nonces_to_bruteforce; i++) {
 197                 for(uint32_t bit_idx = 0; bit_idx < 4; bit_idx++){
 198                         bool bit = get_bit(4-1-bit_idx, bf_test_nonce_par[i]);
 199                         if(bit){
 200                                 bitsliced_encrypted_parity_bits[i][bit_idx].value = bs_ones.value;
 201                         } else {
 202                                 bitsliced_encrypted_parity_bits[i][bit_idx].value = bs_zeroes.value;
 203                         }
 204                 }
 205         }
 206
 207 }
 208
 209
 210 const uint64_t CRACK_STATES_BITSLICED(uint32_t cuid, uint8_t *best_first_bytes, statelist_t *p, uint32_t *keys_found, uint64_t *num_keys_tested, uint32_t nonces_to_bruteforce, uint8_t *bf_test_nonce_2nd_byte, noncelist_t *nonces){
 211
 212     // Unlike aczid's implementation this doesn't roll back at all when performing bitsliced bruteforce.
 213         // We know that the best first byte is already shifted in. Testing with the remaining three bytes of
 214         // the nonces is sufficient to eliminate most of them. The small rest is tested with a simple unsliced
 215         // brute forcing (including roll back).
 216
 217         bitslice_t states[KEYSTREAM_SIZE+STATE_SIZE];
 218         bitslice_t * restrict state_p;
 219     uint64_t key = -1;
 220     uint64_t bucket_states_tested = 0;
 221     uint32_t bucket_size[(p->len[EVEN_STATE] - 1)/MAX_BITSLICES + 1];
 222     uint32_t bitsliced_blocks = 0;
 223     uint32_t const *restrict p_even_end = p->states[EVEN_STATE] + p->len[EVEN_STATE];
 224 #if defined (DEBUG_BRUTE_FORCE)
 225         uint32_t elimination_step = 0;
 226         #define MAX_ELIMINATION_STEP    32
 227         uint64_t keys_eliminated[MAX_ELIMINATION_STEP] = {0};
 228 #endif
 229 #ifdef DEBUG_KEY_ELIMINATION
 230         bool bucket_contains_test_key[(p->len[EVEN_STATE] - 1)/MAX_BITSLICES + 1];
 231 #endif
 232
 233         // constant ones/zeroes
 234         bitslice_t bs_ones;
 235     memset(bs_ones.bytes, 0xff, VECTOR_SIZE);
 236         bitslice_t bs_zeroes;
 237     memset(bs_zeroes.bytes, 0x00, VECTOR_SIZE);
 238
 239     // bitslice all the even states
 240     bitslice_t **restrict bitsliced_even_states = (bitslice_t **)malloc(((p->len[EVEN_STATE] - 1)/MAX_BITSLICES + 1) * sizeof(bitslice_t *));
 241         if (bitsliced_even_states == NULL) {
 242                 printf("Out of memory error in brute_force. Aborting...");
 243                 exit(4);
 244         }
 245     bitslice_value_t *restrict bitsliced_even_feedback = malloc_bitslice(((p->len[EVEN_STATE] - 1)/MAX_BITSLICES + 1) * sizeof(bitslice_value_t));
 246         if (bitsliced_even_feedback == NULL) {
 247                 printf("Out of memory error in brute_force. Aborting...");
 248                 exit(4);
 249         }
 250     for(uint32_t *restrict p_even = p->states[EVEN_STATE]; p_even < p_even_end; p_even += MAX_BITSLICES){
 251         bitslice_t *restrict lstate_p = malloc_bitslice(STATE_SIZE/2*sizeof(bitslice_t));
 252                 if (lstate_p == NULL) {
 253                         printf("Out of memory error in brute_force. Aborting... \n");
 254                         exit(4);
 255                 }
 256         memset(lstate_p, 0x00, STATE_SIZE/2*sizeof(bitslice_t)); // zero even bits
 257         // bitslice even half-states
 258         const uint32_t max_slices = (p_even_end-p_even) < MAX_BITSLICES ? p_even_end-p_even : MAX_BITSLICES;
 259         bucket_size[bitsliced_blocks] = max_slices;
 260 #ifdef DEBUG_KEY_ELIMINATION
 261                 bucket_contains_test_key[bitsliced_blocks] = false;
 262 #endif
 263                 uint32_t slice_idx;
 264         for(slice_idx = 0; slice_idx < max_slices; ++slice_idx){
 265             uint32_t e = *(p_even+slice_idx);
 266 #ifdef DEBUG_KEY_ELIMINATION
 267                         if (known_target_key != -1 && e == test_state[EVEN_STATE]) {
 268                                 bucket_contains_test_key[bitsliced_blocks] = true;
 269                                 // printf("bucket %d contains test key even state\n", bitsliced_blocks);
 270                                 // printf("in slice %d\n", slice_idx);
 271                         }
 272 #endif
 273             for(uint32_t bit_idx = 0; bit_idx < STATE_SIZE/2; bit_idx++, e >>= 1){
 274                 // set even bits
 275                 if(e&1){
 276                     lstate_p[bit_idx].bytes64[slice_idx>>6] |= 1ull << (slice_idx & 0x3f);
 277                 }
 278             }
 279         }
 280                 // padding with last even state
 281                 for ( ; slice_idx < MAX_BITSLICES; ++slice_idx) {
 282             uint32_t e = *(p_even_end-1);
 283             for(uint32_t bit_idx = 0; bit_idx < STATE_SIZE/2; bit_idx++, e >>= 1){
 284                 // set even bits
 285                 if(e&1){
 286                     lstate_p[bit_idx].bytes64[slice_idx>>6] |= 1ull << (slice_idx & 0x3f);
 287                 }
 288             }
 289                 }
 290         bitsliced_even_states[bitsliced_blocks] = lstate_p;
 291                 // bitsliced_even_feedback[bitsliced_blocks] = bs_ones;
 292                 bitsliced_even_feedback[bitsliced_blocks] = lstate_p[(47- 0)/2].value ^
 293                                                     lstate_p[(47-10)/2].value ^ lstate_p[(47-12)/2].value ^ lstate_p[(47-14)/2].value ^
 294                                                     lstate_p[(47-24)/2].value ^ lstate_p[(47-42)/2].value;
 295                 bitsliced_blocks++;
 296     }
 297     // bitslice every odd state to every block of even states
 298     for(uint32_t const *restrict p_odd = p->states[ODD_STATE]; p_odd < p->states[ODD_STATE] + p->len[ODD_STATE]; ++p_odd){
 299         // early abort
 300         if(*keys_found){
 301             goto out;
 302         }
 303
 304                 // set odd state bits and pre-compute first keystream bit vector. This is the same for all blocks of even states
 305
 306                 state_p = &states[KEYSTREAM_SIZE];
 307                 uint32_t o = *p_odd;
 308
 309         // pre-compute the odd feedback bit
 310         bool odd_feedback_bit = evenparity32(o&0x29ce5c);
 311         const bitslice_value_t odd_feedback = odd_feedback_bit ? bs_ones.value : bs_zeroes.value;
 312
 313                 // set odd state bits
 314                 for (uint32_t state_idx = 0; state_idx < STATE_SIZE; o >>= 1, state_idx += 2) {
 315                         if (o & 1){
 316                                 state_p[state_idx] = bs_ones;
 317                         } else {
 318                                 state_p[state_idx] = bs_zeroes;
 319                         }
 320                 }
 321
 322                 bitslice_value_t crypto1_bs_f20b_2[16];
 323                 bitslice_value_t crypto1_bs_f20b_3[8];
 324
 325                 crypto1_bs_f20b_2[0] = f20b(state_p[47-25].value, state_p[47-27].value, state_p[47-29].value, state_p[47-31].value);
 326                 crypto1_bs_f20b_3[0] = f20b(state_p[47-41].value, state_p[47-43].value, state_p[47-45].value, state_p[47-47].value);
 327
 328                 bitslice_value_t ksb[8];
 329                 ksb[0] = f20c(f20a(state_p[47- 9].value, state_p[47-11].value, state_p[47-13].value, state_p[47-15].value),
 330                               f20b(state_p[47-17].value, state_p[47-19].value, state_p[47-21].value, state_p[47-23].value),
 331                               crypto1_bs_f20b_2[0],
 332                               f20a(state_p[47-33].value, state_p[47-35].value, state_p[47-37].value, state_p[47-39].value),
 333                               crypto1_bs_f20b_3[0]);
 334
 335                 uint32_t *restrict p_even = p->states[EVEN_STATE];
 336         for (uint32_t block_idx = 0; block_idx < bitsliced_blocks; ++block_idx, p_even += MAX_BITSLICES) {
 337
 338 #ifdef DEBUG_KEY_ELIMINATION
 339                         // if (known_target_key != -1 && bucket_contains_test_key[block_idx] && *p_odd == test_state[ODD_STATE]) {
 340                                 // printf("Now testing known target key.\n");
 341                                 // printf("block_idx = %d/%d\n", block_idx, bitsliced_blocks);
 342                         // }
 343 #endif
 344             // add the even state bits
 345                         const bitslice_t *restrict bitsliced_even_state = bitsliced_even_states[block_idx];
 346                         for(uint32_t state_idx = 1; state_idx < STATE_SIZE; state_idx += 2) {
 347                                 state_p[state_idx] = bitsliced_even_state[state_idx/2];
 348                         }
 349
 350                         // pre-compute first feedback bit vector. This is the same for all nonces
 351                         bitslice_value_t fbb[8];
 352             fbb[0] = odd_feedback ^ bitsliced_even_feedback[block_idx];
 353
 354             // vector to contain test results (1 = passed, 0 = failed)
 355             bitslice_t results = bs_ones;
 356
 357                         // parity_bits
 358                         bitslice_value_t par[8];
 359                         par[0] = bs_zeroes.value;
 360                         uint32_t next_common_bits = 0;
 361
 362             for(uint32_t tests = 0; tests < nonces_to_bruteforce; ++tests){
 363                                 // common bits with preceding test nonce
 364                                 uint32_t common_bits = next_common_bits; //tests ? trailing_zeros(bf_test_nonce_2nd_byte[tests] ^ bf_test_nonce_2nd_byte[tests-1]) : 0;
 365                                 next_common_bits = tests < nonces_to_bruteforce - 1 ? trailing_zeros(bf_test_nonce_2nd_byte[tests] ^ bf_test_nonce_2nd_byte[tests+1]) : 0;
 366                 uint32_t parity_bit_idx = 1;                                                    // start checking with the parity of second nonce byte
 367                 bitslice_value_t fb_bits = fbb[common_bits];            // start with precomputed feedback bits from previous nonce
 368                 bitslice_value_t ks_bits = ksb[common_bits];            // dito for first keystream bits
 369                 bitslice_value_t parity_bit_vector = par[common_bits]; // dito for first parity vector
 370                                 // bitslice_value_t fb_bits = fbb[0];           // start with precomputed feedback bits from previous nonce
 371                                 // bitslice_value_t ks_bits = ksb[0];           // dito for first keystream bits
 372                                 // bitslice_value_t parity_bit_vector = par[0]; // dito for first parity vector
 373                                 state_p -= common_bits;                                                         // and reuse the already calculated state bits
 374                 // highest bit is transmitted/received first. We start with Bit 23 (highest bit of second nonce byte),
 375                                 // or the highest bit which differs from the previous nonce
 376                 for (int32_t ks_idx = KEYSTREAM_SIZE-1-common_bits; ks_idx >= 0; --ks_idx) {
 377
 378                     // decrypt nonce bits
 379                     const bitslice_value_t encrypted_nonce_bit_vector = bitsliced_encrypted_nonces[tests][ks_idx].value;
 380                     const bitslice_value_t decrypted_nonce_bit_vector = encrypted_nonce_bit_vector ^ ks_bits;
 381
 382                     // compute real parity bits on the fly
 383                     parity_bit_vector ^= decrypted_nonce_bit_vector;
 384
 385                     // update state
 386                                         state_p--;
 387                     state_p[0].value = fb_bits ^ decrypted_nonce_bit_vector;
 388
 389                                         // update crypto1 subfunctions
 390                                         bitslice_value_t f20a_1, f20b_1, f20b_2, f20a_2, f20b_3;
 391                                         f20a_2 = f20a(state_p[47-33].value, state_p[47-35].value, state_p[47-37].value, state_p[47-39].value);
 392                                         f20b_3 = f20b(state_p[47-41].value, state_p[47-43].value, state_p[47-45].value, state_p[47-47].value);
 393                                         if (ks_idx > KEYSTREAM_SIZE - 8) {
 394                                                 f20a_1 = f20a(state_p[47- 9].value, state_p[47-11].value, state_p[47-13].value, state_p[47-15].value);
 395                                                 f20b_1 = f20b(state_p[47-17].value, state_p[47-19].value, state_p[47-21].value, state_p[47-23].value);
 396                                                 f20b_2 = f20b(state_p[47-25].value, state_p[47-27].value, state_p[47-29].value, state_p[47-31].value);
 397                                                 crypto1_bs_f20b_2[KEYSTREAM_SIZE - ks_idx] = f20b_2;
 398                                                 crypto1_bs_f20b_3[KEYSTREAM_SIZE - ks_idx] = f20b_3;
 399                                         } else if (ks_idx > KEYSTREAM_SIZE - 16) {
 400                                                 f20a_1 = f20a(state_p[47- 9].value, state_p[47-11].value, state_p[47-13].value, state_p[47-15].value);
 401                                                 f20b_1 = crypto1_bs_f20b_2[KEYSTREAM_SIZE - ks_idx - 8];
 402                                                 f20b_2 = f20b(state_p[47-25].value, state_p[47-27].value, state_p[47-29].value, state_p[47-31].value);
 403                                                 crypto1_bs_f20b_2[KEYSTREAM_SIZE - ks_idx] = f20b_2;
 404                                         } else if (ks_idx > KEYSTREAM_SIZE - 24){
 405                                                 f20a_1 = f20a(state_p[47- 9].value, state_p[47-11].value, state_p[47-13].value, state_p[47-15].value);
 406                                                 f20b_1 = crypto1_bs_f20b_2[KEYSTREAM_SIZE - ks_idx - 8];
 407                                                 f20b_2 = crypto1_bs_f20b_3[KEYSTREAM_SIZE - ks_idx - 16];
 408                                         } else {
 409                                                 f20a_1 = f20a(state_p[47- 9].value, state_p[47-11].value, state_p[47-13].value, state_p[47-15].value);
 410                                                 f20b_1 = f20b(state_p[47-17].value, state_p[47-19].value, state_p[47-21].value, state_p[47-23].value);
 411                                                 f20b_2 = f20b(state_p[47-25].value, state_p[47-27].value, state_p[47-29].value, state_p[47-31].value);
 412                                         }
 413                                         // update keystream bit
 414                                         ks_bits = f20c(f20a_1, f20b_1, f20b_2, f20a_2, f20b_3);
 415
 416                     // for each completed byte:
 417                     if ((ks_idx & 0x07) == 0) {
 418                         // get encrypted parity bits
 419                         const bitslice_value_t encrypted_parity_bit_vector = bitsliced_encrypted_parity_bits[tests][parity_bit_idx++].value;
 420
 421                         // decrypt parity bits
 422                         const bitslice_value_t decrypted_parity_bit_vector = encrypted_parity_bit_vector ^ ks_bits;
 423
 424                         // compare actual parity bits with decrypted parity bits and take count in results vector
 425                         results.value &= ~parity_bit_vector ^ decrypted_parity_bit_vector;
 426
 427                         // make sure we still have a match in our set
 428                         // if(memcmp(&results, &bs_zeroes, sizeof(bitslice_t)) == 0){
 429
 430                         // this is much faster on my gcc, because somehow a memcmp needlessly spills/fills all the xmm registers to/from the stack - ???
 431                         // the short-circuiting also helps
 432                         if(results.bytes64[0] == 0
 433 #if MAX_BITSLICES > 64
 434                            && results.bytes64[1] == 0
 435 #endif
 436 #if MAX_BITSLICES > 128
 437                            && results.bytes64[2] == 0
 438                            && results.bytes64[3] == 0
 439 #endif
 440                           ) {
 441 #if defined (DEBUG_BRUTE_FORCE)
 442                                                         if (elimination_step < MAX_ELIMINATION_STEP) {
 443                                                                 keys_eliminated[elimination_step] += MAX_BITSLICES;
 444                                                         }
 445 #endif
 446 #ifdef DEBUG_KEY_ELIMINATION
 447                                                         if (known_target_key != -1 && bucket_contains_test_key[block_idx] && *p_odd == test_state[ODD_STATE]) {
 448                                                                 printf("Known target key eliminated in brute_force.\n");
 449                                                                 printf("block_idx = %d/%d, nonce = %d/%d\n", block_idx, bitsliced_blocks, tests, nonces_to_bruteforce);
 450                                                         }
 451 #endif
 452                                                         goto stop_tests;
 453                                                 }
 454                                                 // prepare for next nonce byte
 455 #if defined (DEBUG_BRUTE_FORCE)
 456                                                 elimination_step++;
 457 #endif
 458                                                 parity_bit_vector = bs_zeroes.value;
 459                                         }
 460                                         // update feedback bit vector
 461                                         if (ks_idx != 0) {
 462                                                 fb_bits =
 463                                                                   (state_p[47- 0].value ^ state_p[47- 5].value ^ state_p[47- 9].value ^
 464                                                                    state_p[47-10].value ^ state_p[47-12].value ^ state_p[47-14].value ^
 465                                                                    state_p[47-15].value ^ state_p[47-17].value ^ state_p[47-19].value ^
 466                                                                    state_p[47-24].value ^ state_p[47-25].value ^ state_p[47-27].value ^
 467                                                                    state_p[47-29].value ^ state_p[47-35].value ^ state_p[47-39].value ^
 468                                                                    state_p[47-41].value ^ state_p[47-42].value ^ state_p[47-43].value);
 469                                         }
 470                                         // remember feedback and keystream vectors for later use
 471                                         uint8_t bit = KEYSTREAM_SIZE - ks_idx;
 472                                         if (bit <= next_common_bits) {  // if needed and not yet stored
 473                                                 fbb[bit] = fb_bits;
 474                                                 ksb[bit] = ks_bits;
 475                                                 par[bit] = parity_bit_vector;
 476                                         }
 477                 }
 478                                 // prepare for next nonce. Revert to initial state
 479                                 state_p = &states[KEYSTREAM_SIZE];
 480             }
 481
 482             // all nonce tests were successful: we've found a possible key in this block!
 483                         uint32_t *p_even_test = p_even;
 484             for (uint32_t results_word = 0; results_word < MAX_BITSLICES / 64; ++results_word) {
 485                                 uint64_t results64 = results.bytes64[results_word];
 486                                 for (uint32_t results_bit = 0; results_bit < 64; results_bit++) {
 487                                         if (results64 & 0x01) {
 488                                                 if (verify_key(cuid, nonces, best_first_bytes, *p_odd, *p_even_test)) {
 489                                                         struct Crypto1State pcs;
 490                                                         pcs.odd = *p_odd;
 491                                                         pcs.even = *p_even_test;
 492                                                         lfsr_rollback_byte(&pcs, (cuid >> 24) ^ best_first_bytes[0], true);
 493                                                         crypto1_get_lfsr(&pcs, &key);
 494                                                         bucket_states_tested += 64 * results_word + results_bit;
 495                                                         goto out;
 496                                                 }
 497 #ifdef DEBUG_KEY_ELIMINATION
 498                                                 if (known_target_key != -1 && *p_even_test == test_state[EVEN_STATE] && *p_odd == test_state[ODD_STATE]) {
 499                                                         printf("Known target key eliminated in brute_force verification.\n");
 500                                                         printf("block_idx = %d/%d\n", block_idx, bitsliced_blocks);
 501                                                 }
 502 #endif
 503                                         }
 504 #ifdef DEBUG_KEY_ELIMINATION
 505                                         if (known_target_key != -1 && *p_even_test == test_state[EVEN_STATE] && *p_odd == test_state[ODD_STATE]) {
 506                                                 printf("Known target key eliminated in brute_force (results_bit == 0).\n");
 507                                                 printf("block_idx = %d/%d\n", block_idx, bitsliced_blocks);
 508                                         }
 509 #endif
 510                                         results64 >>= 1;
 511                                         p_even_test++;
 512                                         if (p_even_test == p_even_end) {
 513                                                 goto stop_tests;
 514                                         }
 515                                 }
 516             }
 517 stop_tests:
 518 #if defined (DEBUG_BRUTE_FORCE)
 519                         elimination_step = 0;
 520 #endif
 521             bucket_states_tested += bucket_size[block_idx];
 522             // prepare to set new states
 523                         state_p = &states[KEYSTREAM_SIZE];
 524             continue;
 525         }
 526     }
 527 out:
 528     for(uint32_t block_idx = 0; block_idx < bitsliced_blocks; ++block_idx){
 529         free_bitslice(bitsliced_even_states[block_idx]);
 530     }
 531         free(bitsliced_even_states);
 532         free_bitslice(bitsliced_even_feedback);
 533     __sync_fetch_and_add(num_keys_tested, bucket_states_tested);
 534
 535 #if defined (DEBUG_BRUTE_FORCE)
 536         for (uint32_t i = 0; i < MAX_ELIMINATION_STEP; i++) {
 537                 printf("Eliminated after %2u test_bytes: %5.2f%%\n", i+1, (float)keys_eliminated[i] / bucket_states_tested * 100);
 538         }
 539 #endif
 540     return key;
 541 }
 542
 543
 544
 545 #ifndef __MMX__
 546
 547 // pointers to functions:
 548 crack_states_bitsliced_t *crack_states_bitsliced_function_p = &crack_states_bitsliced_dispatch;
 549 bitslice_test_nonces_t *bitslice_test_nonces_function_p = &bitslice_test_nonces_dispatch;
 550
 551 static SIMDExecInstr intSIMDInstr = SIMD_AUTO;
 552
 553 void SetSIMDInstr(SIMDExecInstr instr) {
 554         intSIMDInstr = instr;
 555
 556         crack_states_bitsliced_function_p = &crack_states_bitsliced_dispatch;
 557         bitslice_test_nonces_function_p = &bitslice_test_nonces_dispatch;
 558 }
 559
 560 SIMDExecInstr GetSIMDInstr() {
 561         SIMDExecInstr instr = SIMD_NONE;
 562
 563 #if defined (__i386__) || defined (__x86_64__)
 564         #if !defined(__APPLE__) || (defined(__APPLE__) && (__clang_major__ > 8 || __clang_major__ == 8 && __clang_minor__ >= 1))
 565                 #if (__GNUC__ >= 5) && (__GNUC__ > 5 || __GNUC_MINOR__ > 2)
 566                 if (__builtin_cpu_supports("avx512f")) instr = SIMD_AVX512;
 567                 else if (__builtin_cpu_supports("avx2")) instr = SIMD_AVX2;
 568                 #else
 569                 if (__builtin_cpu_supports("avx2")) instr = SIMD_AVX2;
 570                 #endif
 571                 else if (__builtin_cpu_supports("avx")) instr = SIMD_AVX;
 572                 else if (__builtin_cpu_supports("sse2")) instr = SIMD_SSE2;
 573                 else if (__builtin_cpu_supports("mmx")) instr = SIMD_MMX;
 574                 else
 575         #endif
 576 #endif
 577                 instr = SIMD_NONE;
 578
 579         return instr;
 580 }
 581
 582 SIMDExecInstr GetSIMDInstrAuto() {
 583         SIMDExecInstr instr = intSIMDInstr;
 584         if (instr == SIMD_AUTO)
 585                 return GetSIMDInstr();
 586
 587         return instr;
 588 }
 589
 590 // determine the available instruction set at runtime and call the correct function
 591 const uint64_t crack_states_bitsliced_dispatch(uint32_t cuid, uint8_t *best_first_bytes, statelist_t *p, uint32_t *keys_found, uint64_t *num_keys_tested, uint32_t nonces_to_bruteforce, uint8_t *bf_test_nonce_2nd_byte, noncelist_t *nonces) {
 592         switch(GetSIMDInstrAuto()) {
 593 #if defined (__i386__) || defined (__x86_64__)
 594 #if !defined(__APPLE__) || (defined(__APPLE__) && (__clang_major__ > 8 || __clang_major__ == 8 && __clang_minor__ >= 1))
 595 #if (__GNUC__ >= 5) && (__GNUC__ > 5 || __GNUC_MINOR__ > 2)
 596                 case SIMD_AVX512:
 597                         crack_states_bitsliced_function_p = &crack_states_bitsliced_AVX512;
 598                         break;
 599 #endif
 600                 case SIMD_AVX2:
 601                         crack_states_bitsliced_function_p = &crack_states_bitsliced_AVX2;
 602                         break;
 603                 case SIMD_AVX:
 604                         crack_states_bitsliced_function_p = &crack_states_bitsliced_AVX;
 605                         break;
 606                 case SIMD_SSE2:
 607                         crack_states_bitsliced_function_p = &crack_states_bitsliced_SSE2;
 608                         break;
 609                 case SIMD_MMX:
 610                         crack_states_bitsliced_function_p = &crack_states_bitsliced_MMX;
 611                         break;
 612 #endif
 613 #endif
 614                 default:
 615                         crack_states_bitsliced_function_p = &crack_states_bitsliced_NOSIMD;
 616                         break;
 617         }
 618
 619     // call the most optimized function for this CPU
 620     return (*crack_states_bitsliced_function_p)(cuid, best_first_bytes, p, keys_found, num_keys_tested, nonces_to_bruteforce, bf_test_nonce_2nd_byte, nonces);
 621 }
 622
 623 void bitslice_test_nonces_dispatch(uint32_t nonces_to_bruteforce, uint32_t *bf_test_nonce, uint8_t *bf_test_nonce_par) {
 624         switch(GetSIMDInstrAuto()) {
 625 #if defined (__i386__) || defined (__x86_64__)
 626 #if !defined(__APPLE__) || (defined(__APPLE__) && (__clang_major__ > 8 || __clang_major__ == 8 && __clang_minor__ >= 1))
 627 #if (__GNUC__ >= 5) && (__GNUC__ > 5 || __GNUC_MINOR__ > 2)
 628                 case SIMD_AVX512:
 629                         bitslice_test_nonces_function_p = &bitslice_test_nonces_AVX512;
 630                         break;
 631 #endif
 632                 case SIMD_AVX2:
 633                         bitslice_test_nonces_function_p = &bitslice_test_nonces_AVX2;
 634                         break;
 635                 case SIMD_AVX:
 636                         bitslice_test_nonces_function_p = &bitslice_test_nonces_AVX;
 637                         break;
 638                 case SIMD_SSE2:
 639                         bitslice_test_nonces_function_p = &bitslice_test_nonces_SSE2;
 640                         break;
 641                 case SIMD_MMX:
 642                         bitslice_test_nonces_function_p = &bitslice_test_nonces_MMX;
 643                         break;
 644 #endif
 645 #endif
 646                 default:
 647                         bitslice_test_nonces_function_p = &bitslice_test_nonces_NOSIMD;
 648                         break;
 649         }
 650
 651     // call the most optimized function for this CPU
 652     (*bitslice_test_nonces_function_p)(nonces_to_bruteforce, bf_test_nonce, bf_test_nonce_par);
 653 }
 654
 655 // Entries to dispatched function calls
 656 const uint64_t crack_states_bitsliced(uint32_t cuid, uint8_t *best_first_bytes, statelist_t *p, uint32_t *keys_found, uint64_t *num_keys_tested, uint32_t nonces_to_bruteforce, uint8_t *bf_test_nonce_2nd_byte, noncelist_t *nonces) {
 657     return (*crack_states_bitsliced_function_p)(cuid, best_first_bytes, p, keys_found, num_keys_tested, nonces_to_bruteforce, bf_test_nonce_2nd_byte, nonces);
 658 }
 659
 660 void bitslice_test_nonces(uint32_t nonces_to_bruteforce, uint32_t *bf_test_nonce, uint8_t *bf_test_nonce_par) {
 661     (*bitslice_test_nonces_function_p)(nonces_to_bruteforce, bf_test_nonce, bf_test_nonce_par);
 662 }
 663
 664 #endif