]> git.zerfleddert.de Git - proxmark3-svn/blame - client/cmdhfmfhard.c
FIX: Some Coverity Scan warnings. fread, not initialised etc etc
[proxmark3-svn] / client / cmdhfmfhard.c
CommitLineData
8ce3e4b4 1//-----------------------------------------------------------------------------
2// Copyright (C) 2015 piwi
3130ba4b 3// fiddled with 2016 Azcid (hardnested bitsliced Bruteforce imp)
8ce3e4b4 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
8ce3e4b4 17#include <stdlib.h>
3130ba4b 18#include <stdio.h>
8ce3e4b4 19#include <string.h>
20#include <pthread.h>
0d5ee8e2 21#include <locale.h>
8ce3e4b4 22#include <math.h>
23#include "proxmark3.h"
24#include "cmdmain.h"
25#include "ui.h"
26#include "util.h"
27#include "nonce2key/crapto1.h"
3130ba4b 28#include "nonce2key/crypto1_bs.h"
f8ada309 29#include "parity.h"
3130ba4b 30#ifdef __WIN32
31 #include <windows.h>
32#endif
33#include <malloc.h>
34#include <assert.h>
8ce3e4b4 35
36// uint32_t test_state_odd = 0;
37// uint32_t test_state_even = 0;
38
f8ada309 39#define CONFIDENCE_THRESHOLD 0.95 // Collect nonces until we are certain enough that the following brute force is successfull
3130ba4b 40#define GOOD_BYTES_REQUIRED 28
8ce3e4b4 41
42static const float p_K[257] = { // the probability that a random nonce has a Sum Property == K
43 0.0290, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
44 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
45 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
46 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
47 0.0083, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
48 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
49 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
50 0.0006, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
51 0.0339, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
52 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
53 0.0048, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
54 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
55 0.0934, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
56 0.0119, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
57 0.0489, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
58 0.0602, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
59 0.4180, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
60 0.0602, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
61 0.0489, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
62 0.0119, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
63 0.0934, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
64 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
65 0.0048, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
66 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
67 0.0339, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
68 0.0006, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
69 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
70 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
71 0.0083, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
72 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
73 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
74 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
75 0.0290 };
8ce3e4b4 76
77typedef struct noncelistentry {
78 uint32_t nonce_enc;
79 uint8_t par_enc;
80 void *next;
81} noncelistentry_t;
82
83typedef struct noncelist {
84 uint16_t num;
85 uint16_t Sum;
86 uint16_t Sum8_guess;
87 uint8_t BitFlip[2];
88 float Sum8_prob;
89 bool updated;
90 noncelistentry_t *first;
a531720a 91 float score1, score2;
8ce3e4b4 92} noncelist_t;
93
3130ba4b 94static size_t nonces_to_bruteforce = 0;
95static noncelistentry_t *brute_force_nonces[256];
810f5379 96static uint32_t cuid = 0;
8ce3e4b4 97static noncelist_t nonces[256];
fe8042f2 98static uint8_t best_first_bytes[256];
8ce3e4b4 99static uint16_t first_byte_Sum = 0;
100static uint16_t first_byte_num = 0;
101static uint16_t num_good_first_bytes = 0;
f8ada309 102static uint64_t maximum_states = 0;
103static uint64_t known_target_key;
0d5ee8e2 104static bool write_stats = false;
105static FILE *fstats = NULL;
8ce3e4b4 106
107
108typedef enum {
109 EVEN_STATE = 0,
110 ODD_STATE = 1
111} odd_even_t;
112
113#define STATELIST_INDEX_WIDTH 16
114#define STATELIST_INDEX_SIZE (1<<STATELIST_INDEX_WIDTH)
115
116typedef struct {
117 uint32_t *states[2];
118 uint32_t len[2];
119 uint32_t *index[2][STATELIST_INDEX_SIZE];
120} partial_indexed_statelist_t;
121
122typedef struct {
123 uint32_t *states[2];
124 uint32_t len[2];
125 void* next;
126} statelist_t;
127
128
f8ada309 129static partial_indexed_statelist_t partial_statelist[17];
130static partial_indexed_statelist_t statelist_bitflip;
f8ada309 131static statelist_t *candidates = NULL;
8ce3e4b4 132
8ce3e4b4 133static int add_nonce(uint32_t nonce_enc, uint8_t par_enc)
134{
135 uint8_t first_byte = nonce_enc >> 24;
136 noncelistentry_t *p1 = nonces[first_byte].first;
137 noncelistentry_t *p2 = NULL;
138
139 if (p1 == NULL) { // first nonce with this 1st byte
140 first_byte_num++;
f8ada309 141 first_byte_Sum += evenparity32((nonce_enc & 0xff000000) | (par_enc & 0x08));
8ce3e4b4 142 // printf("Adding nonce 0x%08x, par_enc 0x%02x, parity(0x%08x) = %d\n",
143 // nonce_enc,
144 // par_enc,
145 // (nonce_enc & 0xff000000) | (par_enc & 0x08) |0x01,
f8ada309 146 // parity((nonce_enc & 0xff000000) | (par_enc & 0x08));
8ce3e4b4 147 }
148
149 while (p1 != NULL && (p1->nonce_enc & 0x00ff0000) < (nonce_enc & 0x00ff0000)) {
150 p2 = p1;
151 p1 = p1->next;
152 }
153
154 if (p1 == NULL) { // need to add at the end of the list
155 if (p2 == NULL) { // list is empty yet. Add first entry.
156 p2 = nonces[first_byte].first = malloc(sizeof(noncelistentry_t));
157 } else { // add new entry at end of existing list.
158 p2 = p2->next = malloc(sizeof(noncelistentry_t));
159 }
160 } else if ((p1->nonce_enc & 0x00ff0000) != (nonce_enc & 0x00ff0000)) { // found distinct 2nd byte. Need to insert.
161 if (p2 == NULL) { // need to insert at start of list
162 p2 = nonces[first_byte].first = malloc(sizeof(noncelistentry_t));
163 } else {
164 p2 = p2->next = malloc(sizeof(noncelistentry_t));
165 }
166 } else { // we have seen this 2nd byte before. Nothing to add or insert.
167 return (0);
168 }
169
170 // add or insert new data
171 p2->next = p1;
172 p2->nonce_enc = nonce_enc;
173 p2->par_enc = par_enc;
174
3130ba4b 175 if(nonces_to_bruteforce < 256){
176 brute_force_nonces[nonces_to_bruteforce] = p2;
177 nonces_to_bruteforce++;
178 }
179
8ce3e4b4 180 nonces[first_byte].num++;
f8ada309 181 nonces[first_byte].Sum += evenparity32((nonce_enc & 0x00ff0000) | (par_enc & 0x04));
8ce3e4b4 182 nonces[first_byte].updated = true; // indicates that we need to recalculate the Sum(a8) probability for this first byte
183
184 return (1); // new nonce added
185}
186
0d5ee8e2 187static void init_nonce_memory(void)
188{
189 for (uint16_t i = 0; i < 256; i++) {
190 nonces[i].num = 0;
191 nonces[i].Sum = 0;
192 nonces[i].Sum8_guess = 0;
193 nonces[i].Sum8_prob = 0.0;
194 nonces[i].updated = true;
195 nonces[i].first = NULL;
196 }
197 first_byte_num = 0;
198 first_byte_Sum = 0;
199 num_good_first_bytes = 0;
200}
201
202
203static void free_nonce_list(noncelistentry_t *p)
204{
205 if (p == NULL) {
206 return;
207 } else {
208 free_nonce_list(p->next);
209 free(p);
210 }
211}
212
0d5ee8e2 213static void free_nonces_memory(void)
214{
215 for (uint16_t i = 0; i < 256; i++) {
216 free_nonce_list(nonces[i].first);
217 }
218}
219
8ce3e4b4 220static uint16_t PartialSumProperty(uint32_t state, odd_even_t odd_even)
221{
222 uint16_t sum = 0;
223 for (uint16_t j = 0; j < 16; j++) {
224 uint32_t st = state;
225 uint16_t part_sum = 0;
226 if (odd_even == ODD_STATE) {
227 for (uint16_t i = 0; i < 5; i++) {
228 part_sum ^= filter(st);
229 st = (st << 1) | ((j >> (3-i)) & 0x01) ;
230 }
f8ada309 231 part_sum ^= 1; // XOR 1 cancelled out for the other 8 bits
8ce3e4b4 232 } else {
233 for (uint16_t i = 0; i < 4; i++) {
234 st = (st << 1) | ((j >> (3-i)) & 0x01) ;
235 part_sum ^= filter(st);
236 }
237 }
238 sum += part_sum;
239 }
240 return sum;
241}
242
fe8042f2 243// static uint16_t SumProperty(struct Crypto1State *s)
244// {
245 // uint16_t sum_odd = PartialSumProperty(s->odd, ODD_STATE);
246 // uint16_t sum_even = PartialSumProperty(s->even, EVEN_STATE);
247 // return (sum_odd*(16-sum_even) + (16-sum_odd)*sum_even);
248// }
8ce3e4b4 249
8ce3e4b4 250static double p_hypergeometric(uint16_t N, uint16_t K, uint16_t n, uint16_t k)
251{
252 // for efficient computation we are using the recursive definition
253 // (K-k+1) * (n-k+1)
254 // P(X=k) = P(X=k-1) * --------------------
255 // k * (N-K-n+k)
256 // and
257 // (N-K)*(N-K-1)*...*(N-K-n+1)
258 // P(X=0) = -----------------------------
259 // N*(N-1)*...*(N-n+1)
260
261 if (n-k > N-K || k > K) return 0.0; // avoids log(x<=0) in calculation below
262 if (k == 0) {
263 // use logarithms to avoid overflow with huge factorials (double type can only hold 170!)
264 double log_result = 0.0;
265 for (int16_t i = N-K; i >= N-K-n+1; i--) {
266 log_result += log(i);
267 }
268 for (int16_t i = N; i >= N-n+1; i--) {
269 log_result -= log(i);
270 }
271 return exp(log_result);
272 } else {
273 if (n-k == N-K) { // special case. The published recursion below would fail with a divide by zero exception
274 double log_result = 0.0;
275 for (int16_t i = k+1; i <= n; i++) {
276 log_result += log(i);
277 }
278 for (int16_t i = K+1; i <= N; i++) {
279 log_result -= log(i);
280 }
281 return exp(log_result);
282 } else { // recursion
283 return (p_hypergeometric(N, K, n, k-1) * (K-k+1) * (n-k+1) / (k * (N-K-n+k)));
284 }
285 }
286}
3130ba4b 287
8ce3e4b4 288static float sum_probability(uint16_t K, uint16_t n, uint16_t k)
289{
290 const uint16_t N = 256;
8ce3e4b4 291
4b2e63be 292 if (k > K || p_K[K] == 0.0) return 0.0;
8ce3e4b4 293
4b2e63be 294 double p_T_is_k_when_S_is_K = p_hypergeometric(N, K, n, k);
295 double p_S_is_K = p_K[K];
296 double p_T_is_k = 0;
297 for (uint16_t i = 0; i <= 256; i++) {
298 if (p_K[i] != 0.0) {
299 p_T_is_k += p_K[i] * p_hypergeometric(N, i, n, k);
8ce3e4b4 300 }
4b2e63be 301 }
302 return(p_T_is_k_when_S_is_K * p_S_is_K / p_T_is_k);
8ce3e4b4 303}
304
a531720a 305
306static inline uint_fast8_t common_bits(uint_fast8_t bytes_diff)
307{
308 static const uint_fast8_t common_bits_LUT[256] = {
309 8, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
310 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
311 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
312 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
313 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
314 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
315 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
316 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
317 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
318 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
319 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
320 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
321 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
322 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
323 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
324 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
325 };
326
327 return common_bits_LUT[bytes_diff];
328}
329
8ce3e4b4 330static void Tests()
331{
fe8042f2 332 // printf("Tests: Partial Statelist sizes\n");
333 // for (uint16_t i = 0; i <= 16; i+=2) {
334 // printf("Partial State List Odd [%2d] has %8d entries\n", i, partial_statelist[i].len[ODD_STATE]);
335 // }
336 // for (uint16_t i = 0; i <= 16; i+=2) {
337 // printf("Partial State List Even [%2d] has %8d entries\n", i, partial_statelist[i].len[EVEN_STATE]);
338 // }
8ce3e4b4 339
340 // #define NUM_STATISTICS 100000
8ce3e4b4 341 // uint32_t statistics_odd[17];
f8ada309 342 // uint64_t statistics[257];
8ce3e4b4 343 // uint32_t statistics_even[17];
344 // struct Crypto1State cs;
345 // time_t time1 = clock();
346
347 // for (uint16_t i = 0; i < 257; i++) {
348 // statistics[i] = 0;
349 // }
350 // for (uint16_t i = 0; i < 17; i++) {
351 // statistics_odd[i] = 0;
352 // statistics_even[i] = 0;
353 // }
354
355 // for (uint64_t i = 0; i < NUM_STATISTICS; i++) {
356 // cs.odd = (rand() & 0xfff) << 12 | (rand() & 0xfff);
357 // cs.even = (rand() & 0xfff) << 12 | (rand() & 0xfff);
358 // uint16_t sum_property = SumProperty(&cs);
359 // statistics[sum_property] += 1;
360 // sum_property = PartialSumProperty(cs.even, EVEN_STATE);
361 // statistics_even[sum_property]++;
362 // sum_property = PartialSumProperty(cs.odd, ODD_STATE);
363 // statistics_odd[sum_property]++;
364 // if (i%(NUM_STATISTICS/100) == 0) printf(".");
365 // }
366
367 // printf("\nTests: Calculated %d Sum properties in %0.3f seconds (%0.0f calcs/second)\n", NUM_STATISTICS, ((float)clock() - time1)/CLOCKS_PER_SEC, NUM_STATISTICS/((float)clock() - time1)*CLOCKS_PER_SEC);
368 // for (uint16_t i = 0; i < 257; i++) {
369 // if (statistics[i] != 0) {
370 // printf("probability[%3d] = %0.5f\n", i, (float)statistics[i]/NUM_STATISTICS);
371 // }
372 // }
373 // for (uint16_t i = 0; i <= 16; i++) {
374 // if (statistics_odd[i] != 0) {
375 // printf("probability odd [%2d] = %0.5f\n", i, (float)statistics_odd[i]/NUM_STATISTICS);
376 // }
377 // }
378 // for (uint16_t i = 0; i <= 16; i++) {
379 // if (statistics_odd[i] != 0) {
380 // printf("probability even [%2d] = %0.5f\n", i, (float)statistics_even[i]/NUM_STATISTICS);
381 // }
382 // }
383
384 // printf("Tests: Sum Probabilities based on Partial Sums\n");
385 // for (uint16_t i = 0; i < 257; i++) {
386 // statistics[i] = 0;
387 // }
388 // uint64_t num_states = 0;
389 // for (uint16_t oddsum = 0; oddsum <= 16; oddsum += 2) {
390 // for (uint16_t evensum = 0; evensum <= 16; evensum += 2) {
391 // uint16_t sum = oddsum*(16-evensum) + (16-oddsum)*evensum;
392 // statistics[sum] += (uint64_t)partial_statelist[oddsum].len[ODD_STATE] * partial_statelist[evensum].len[EVEN_STATE] * (1<<8);
393 // num_states += (uint64_t)partial_statelist[oddsum].len[ODD_STATE] * partial_statelist[evensum].len[EVEN_STATE] * (1<<8);
394 // }
395 // }
396 // printf("num_states = %lld, expected %lld\n", num_states, (1LL<<48));
397 // for (uint16_t i = 0; i < 257; i++) {
398 // if (statistics[i] != 0) {
399 // printf("probability[%3d] = %0.5f\n", i, (float)statistics[i]/num_states);
400 // }
401 // }
402
403 // printf("\nTests: Hypergeometric Probability for selected parameters\n");
404 // printf("p_hypergeometric(256, 206, 255, 206) = %0.8f\n", p_hypergeometric(256, 206, 255, 206));
405 // printf("p_hypergeometric(256, 206, 255, 205) = %0.8f\n", p_hypergeometric(256, 206, 255, 205));
406 // printf("p_hypergeometric(256, 156, 1, 1) = %0.8f\n", p_hypergeometric(256, 156, 1, 1));
407 // printf("p_hypergeometric(256, 156, 1, 0) = %0.8f\n", p_hypergeometric(256, 156, 1, 0));
408 // printf("p_hypergeometric(256, 1, 1, 1) = %0.8f\n", p_hypergeometric(256, 1, 1, 1));
409 // printf("p_hypergeometric(256, 1, 1, 0) = %0.8f\n", p_hypergeometric(256, 1, 1, 0));
410
fe8042f2 411 // struct Crypto1State *pcs;
412 // pcs = crypto1_create(0xffffffffffff);
413 // printf("\nTests: for key = 0xffffffffffff:\nSum(a0) = %d\nodd_state = 0x%06x\neven_state = 0x%06x\n",
414 // SumProperty(pcs), pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff);
415 // crypto1_byte(pcs, (cuid >> 24) ^ best_first_bytes[0], true);
416 // printf("After adding best first byte 0x%02x:\nSum(a8) = %d\nodd_state = 0x%06x\neven_state = 0x%06x\n",
417 // best_first_bytes[0],
418 // SumProperty(pcs),
419 // pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff);
420 // //test_state_odd = pcs->odd & 0x00ffffff;
421 // //test_state_even = pcs->even & 0x00ffffff;
422 // crypto1_destroy(pcs);
423 // pcs = crypto1_create(0xa0a1a2a3a4a5);
424 // printf("Tests: for key = 0xa0a1a2a3a4a5:\nSum(a0) = %d\nodd_state = 0x%06x\neven_state = 0x%06x\n",
425 // SumProperty(pcs), pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff);
426 // crypto1_byte(pcs, (cuid >> 24) ^ best_first_bytes[0], true);
427 // printf("After adding best first byte 0x%02x:\nSum(a8) = %d\nodd_state = 0x%06x\neven_state = 0x%06x\n",
428 // best_first_bytes[0],
429 // SumProperty(pcs),
430 // pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff);
431 // //test_state_odd = pcs->odd & 0x00ffffff;
432 // //test_state_even = pcs->even & 0x00ffffff;
433 // crypto1_destroy(pcs);
434 // pcs = crypto1_create(0xa6b9aa97b955);
435 // printf("Tests: for key = 0xa6b9aa97b955:\nSum(a0) = %d\nodd_state = 0x%06x\neven_state = 0x%06x\n",
436 // SumProperty(pcs), pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff);
437 // crypto1_byte(pcs, (cuid >> 24) ^ best_first_bytes[0], true);
438 // printf("After adding best first byte 0x%02x:\nSum(a8) = %d\nodd_state = 0x%06x\neven_state = 0x%06x\n",
439 // best_first_bytes[0],
440 // SumProperty(pcs),
441 // pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff);
f8ada309 442 //test_state_odd = pcs->odd & 0x00ffffff;
443 //test_state_even = pcs->even & 0x00ffffff;
fe8042f2 444 // crypto1_destroy(pcs);
8ce3e4b4 445
446
fe8042f2 447 // printf("\nTests: number of states with BitFlipProperty: %d, (= %1.3f%% of total states)\n", statelist_bitflip.len[0], 100.0 * statelist_bitflip.len[0] / (1<<20));
8ce3e4b4 448
cd777a05 449 // printf("\nTests: Actual BitFlipProperties odd/even:\n");
450 // for (uint16_t i = 0; i < 256; i++) {
451 // printf("[%02x]:%c ", i, nonces[i].BitFlip[ODD_STATE]?'o':nonces[i].BitFlip[EVEN_STATE]?'e':' ');
452 // if (i % 8 == 7) {
453 // printf("\n");
454 // }
455 // }
8ce3e4b4 456
cd777a05 457 // printf("\nTests: Sorted First Bytes:\n");
458 // for (uint16_t i = 0; i < 256; i++) {
459 // uint8_t best_byte = best_first_bytes[i];
460 // printf("#%03d Byte: %02x, n = %3d, k = %3d, Sum(a8): %3d, Confidence: %5.1f%%, Bitflip: %c\n",
461 // //printf("#%03d Byte: %02x, n = %3d, k = %3d, Sum(a8): %3d, Confidence: %5.1f%%, Bitflip: %c, score1: %1.5f, score2: %1.0f\n",
462 // i, best_byte,
463 // nonces[best_byte].num,
464 // nonces[best_byte].Sum,
465 // nonces[best_byte].Sum8_guess,
466 // nonces[best_byte].Sum8_prob * 100,
467 // nonces[best_byte].BitFlip[ODD_STATE]?'o':nonces[best_byte].BitFlip[EVEN_STATE]?'e':' '
468 // //nonces[best_byte].score1,
469 // //nonces[best_byte].score2
470 // );
471 // }
f8ada309 472
473 // printf("\nTests: parity performance\n");
474 // time_t time1p = clock();
475 // uint32_t par_sum = 0;
476 // for (uint32_t i = 0; i < 100000000; i++) {
477 // par_sum += parity(i);
478 // }
479 // printf("parsum oldparity = %d, time = %1.5fsec\n", par_sum, (float)(clock() - time1p)/CLOCKS_PER_SEC);
480
481 // time1p = clock();
482 // par_sum = 0;
483 // for (uint32_t i = 0; i < 100000000; i++) {
484 // par_sum += evenparity32(i);
485 // }
486 // printf("parsum newparity = %d, time = %1.5fsec\n", par_sum, (float)(clock() - time1p)/CLOCKS_PER_SEC);
487
8ce3e4b4 488
f8ada309 489}
490
f8ada309 491static void sort_best_first_bytes(void)
492{
fe8042f2 493 // sort based on probability for correct guess
8ce3e4b4 494 for (uint16_t i = 0; i < 256; i++ ) {
f8ada309 495 uint16_t j = 0;
8ce3e4b4 496 float prob1 = nonces[i].Sum8_prob;
f8ada309 497 float prob2 = nonces[best_first_bytes[0]].Sum8_prob;
fe8042f2 498 while (prob1 < prob2 && j < i) {
8ce3e4b4 499 prob2 = nonces[best_first_bytes[++j]].Sum8_prob;
500 }
fe8042f2 501 if (j < i) {
502 for (uint16_t k = i; k > j; k--) {
8ce3e4b4 503 best_first_bytes[k] = best_first_bytes[k-1];
504 }
fe8042f2 505 }
8ce3e4b4 506 best_first_bytes[j] = i;
507 }
f8ada309 508
fe8042f2 509 // determine how many are above the CONFIDENCE_THRESHOLD
f8ada309 510 uint16_t num_good_nonces = 0;
fe8042f2 511 for (uint16_t i = 0; i < 256; i++) {
4b2e63be 512 if (nonces[best_first_bytes[i]].Sum8_prob >= CONFIDENCE_THRESHOLD) {
f8ada309 513 ++num_good_nonces;
514 }
515 }
516
517 uint16_t best_first_byte = 0;
518
519 // select the best possible first byte based on number of common bits with all {b'}
520 // uint16_t max_common_bits = 0;
521 // for (uint16_t i = 0; i < num_good_nonces; i++) {
522 // uint16_t sum_common_bits = 0;
523 // for (uint16_t j = 0; j < num_good_nonces; j++) {
524 // if (i != j) {
525 // sum_common_bits += common_bits(best_first_bytes[i],best_first_bytes[j]);
526 // }
527 // }
528 // if (sum_common_bits > max_common_bits) {
529 // max_common_bits = sum_common_bits;
530 // best_first_byte = i;
531 // }
532 // }
533
534 // select best possible first byte {b} based on least likely sum/bitflip property
535 float min_p_K = 1.0;
536 for (uint16_t i = 0; i < num_good_nonces; i++ ) {
537 uint16_t sum8 = nonces[best_first_bytes[i]].Sum8_guess;
538 float bitflip_prob = 1.0;
539 if (nonces[best_first_bytes[i]].BitFlip[ODD_STATE] || nonces[best_first_bytes[i]].BitFlip[EVEN_STATE]) {
540 bitflip_prob = 0.09375;
541 }
a531720a 542 nonces[best_first_bytes[i]].score1 = p_K[sum8] * bitflip_prob;
f8ada309 543 if (p_K[sum8] * bitflip_prob <= min_p_K) {
544 min_p_K = p_K[sum8] * bitflip_prob;
f8ada309 545 }
546 }
547
a531720a 548
f8ada309 549 // use number of commmon bits as a tie breaker
550 uint16_t max_common_bits = 0;
551 for (uint16_t i = 0; i < num_good_nonces; i++) {
552 float bitflip_prob = 1.0;
553 if (nonces[best_first_bytes[i]].BitFlip[ODD_STATE] || nonces[best_first_bytes[i]].BitFlip[EVEN_STATE]) {
554 bitflip_prob = 0.09375;
555 }
556 if (p_K[nonces[best_first_bytes[i]].Sum8_guess] * bitflip_prob == min_p_K) {
557 uint16_t sum_common_bits = 0;
558 for (uint16_t j = 0; j < num_good_nonces; j++) {
a531720a 559 sum_common_bits += common_bits(best_first_bytes[i] ^ best_first_bytes[j]);
f8ada309 560 }
a531720a 561 nonces[best_first_bytes[i]].score2 = sum_common_bits;
f8ada309 562 if (sum_common_bits > max_common_bits) {
563 max_common_bits = sum_common_bits;
564 best_first_byte = i;
565 }
566 }
567 }
568
a531720a 569 // swap best possible first byte to the pole position
f8ada309 570 uint16_t temp = best_first_bytes[0];
571 best_first_bytes[0] = best_first_bytes[best_first_byte];
572 best_first_bytes[best_first_byte] = temp;
573
8ce3e4b4 574}
575
8ce3e4b4 576static uint16_t estimate_second_byte_sum(void)
577{
8ce3e4b4 578
579 for (uint16_t first_byte = 0; first_byte < 256; first_byte++) {
580 float Sum8_prob = 0.0;
581 uint16_t Sum8 = 0;
582 if (nonces[first_byte].updated) {
583 for (uint16_t sum = 0; sum <= 256; sum++) {
584 float prob = sum_probability(sum, nonces[first_byte].num, nonces[first_byte].Sum);
585 if (prob > Sum8_prob) {
586 Sum8_prob = prob;
587 Sum8 = sum;
588 }
589 }
590 nonces[first_byte].Sum8_guess = Sum8;
591 nonces[first_byte].Sum8_prob = Sum8_prob;
592 nonces[first_byte].updated = false;
593 }
594 }
595
596 sort_best_first_bytes();
597
598 uint16_t num_good_nonces = 0;
fe8042f2 599 for (uint16_t i = 0; i < 256; i++) {
4b2e63be 600 if (nonces[best_first_bytes[i]].Sum8_prob >= CONFIDENCE_THRESHOLD) {
8ce3e4b4 601 ++num_good_nonces;
602 }
603 }
604
605 return num_good_nonces;
606}
607
8ce3e4b4 608static int read_nonce_file(void)
609{
610 FILE *fnonces = NULL;
611 uint8_t trgBlockNo;
612 uint8_t trgKeyType;
613 uint8_t read_buf[9];
614 uint32_t nt_enc1, nt_enc2;
615 uint8_t par_enc;
616 int total_num_nonces = 0;
617
618 if ((fnonces = fopen("nonces.bin","rb")) == NULL) {
619 PrintAndLog("Could not open file nonces.bin");
620 return 1;
621 }
622
623 PrintAndLog("Reading nonces from file nonces.bin...");
841d7af0 624 size_t bytes_read = fread(read_buf, 1, 6, fnonces);
625 if ( bytes_read == 0) {
8ce3e4b4 626 PrintAndLog("File reading error.");
627 fclose(fnonces);
628 return 1;
629 }
630 cuid = bytes_to_num(read_buf, 4);
631 trgBlockNo = bytes_to_num(read_buf+4, 1);
632 trgKeyType = bytes_to_num(read_buf+5, 1);
633
634 while (fread(read_buf, 1, 9, fnonces) == 9) {
635 nt_enc1 = bytes_to_num(read_buf, 4);
636 nt_enc2 = bytes_to_num(read_buf+4, 4);
637 par_enc = bytes_to_num(read_buf+8, 1);
638 //printf("Encrypted nonce: %08x, encrypted_parity: %02x\n", nt_enc1, par_enc >> 4);
639 //printf("Encrypted nonce: %08x, encrypted_parity: %02x\n", nt_enc2, par_enc & 0x0f);
640 add_nonce(nt_enc1, par_enc >> 4);
641 add_nonce(nt_enc2, par_enc & 0x0f);
642 total_num_nonces += 2;
643 }
644 fclose(fnonces);
645 PrintAndLog("Read %d nonces from file. cuid=%08x, Block=%d, Keytype=%c", total_num_nonces, cuid, trgBlockNo, trgKeyType==0?'A':'B');
646
647 return 0;
648}
649
a531720a 650static void Check_for_FilterFlipProperties(void)
651{
652 printf("Checking for Filter Flip Properties...\n");
653
0d5ee8e2 654 uint16_t num_bitflips = 0;
655
a531720a 656 for (uint16_t i = 0; i < 256; i++) {
657 nonces[i].BitFlip[ODD_STATE] = false;
658 nonces[i].BitFlip[EVEN_STATE] = false;
659 }
660
661 for (uint16_t i = 0; i < 256; i++) {
662 uint8_t parity1 = (nonces[i].first->par_enc) >> 3; // parity of first byte
663 uint8_t parity2_odd = (nonces[i^0x80].first->par_enc) >> 3; // XOR 0x80 = last bit flipped
664 uint8_t parity2_even = (nonces[i^0x40].first->par_enc) >> 3; // XOR 0x40 = second last bit flipped
665
666 if (parity1 == parity2_odd) { // has Bit Flip Property for odd bits
667 nonces[i].BitFlip[ODD_STATE] = true;
0d5ee8e2 668 num_bitflips++;
a531720a 669 } else if (parity1 == parity2_even) { // has Bit Flip Property for even bits
670 nonces[i].BitFlip[EVEN_STATE] = true;
0d5ee8e2 671 num_bitflips++;
a531720a 672 }
673 }
0d5ee8e2 674
675 if (write_stats) {
676 fprintf(fstats, "%d;", num_bitflips);
677 }
678}
679
0d5ee8e2 680static void simulate_MFplus_RNG(uint32_t test_cuid, uint64_t test_key, uint32_t *nt_enc, uint8_t *par_enc)
681{
1f1929a4 682 struct Crypto1State sim_cs = {0, 0};
0d5ee8e2 683 // init cryptostate with key:
684 for(int8_t i = 47; i > 0; i -= 2) {
685 sim_cs.odd = sim_cs.odd << 1 | BIT(test_key, (i - 1) ^ 7);
686 sim_cs.even = sim_cs.even << 1 | BIT(test_key, i ^ 7);
687 }
688
689 *par_enc = 0;
690 uint32_t nt = (rand() & 0xff) << 24 | (rand() & 0xff) << 16 | (rand() & 0xff) << 8 | (rand() & 0xff);
691 for (int8_t byte_pos = 3; byte_pos >= 0; byte_pos--) {
692 uint8_t nt_byte_dec = (nt >> (8*byte_pos)) & 0xff;
693 uint8_t nt_byte_enc = crypto1_byte(&sim_cs, nt_byte_dec ^ (test_cuid >> (8*byte_pos)), false) ^ nt_byte_dec; // encode the nonce byte
694 *nt_enc = (*nt_enc << 8) | nt_byte_enc;
695 uint8_t ks_par = filter(sim_cs.odd); // the keystream bit to encode/decode the parity bit
696 uint8_t nt_byte_par_enc = ks_par ^ oddparity8(nt_byte_dec); // determine the nt byte's parity and encode it
697 *par_enc = (*par_enc << 1) | nt_byte_par_enc;
698 }
699
700}
701
0d5ee8e2 702static void simulate_acquire_nonces()
703{
704 clock_t time1 = clock();
705 bool filter_flip_checked = false;
706 uint32_t total_num_nonces = 0;
707 uint32_t next_fivehundred = 500;
708 uint32_t total_added_nonces = 0;
709
710 cuid = (rand() & 0xff) << 24 | (rand() & 0xff) << 16 | (rand() & 0xff) << 8 | (rand() & 0xff);
711 known_target_key = ((uint64_t)rand() & 0xfff) << 36 | ((uint64_t)rand() & 0xfff) << 24 | ((uint64_t)rand() & 0xfff) << 12 | ((uint64_t)rand() & 0xfff);
712
713 printf("Simulating nonce acquisition for target key %012"llx", cuid %08x ...\n", known_target_key, cuid);
714 fprintf(fstats, "%012"llx";%08x;", known_target_key, cuid);
715
716 do {
717 uint32_t nt_enc = 0;
718 uint8_t par_enc = 0;
719
720 simulate_MFplus_RNG(cuid, known_target_key, &nt_enc, &par_enc);
721 //printf("Simulated RNG: nt_enc1: %08x, nt_enc2: %08x, par_enc: %02x\n", nt_enc1, nt_enc2, par_enc);
722 total_added_nonces += add_nonce(nt_enc, par_enc);
723 total_num_nonces++;
724
725 if (first_byte_num == 256 ) {
726 // printf("first_byte_num = %d, first_byte_Sum = %d\n", first_byte_num, first_byte_Sum);
727 if (!filter_flip_checked) {
728 Check_for_FilterFlipProperties();
729 filter_flip_checked = true;
730 }
731 num_good_first_bytes = estimate_second_byte_sum();
732 if (total_num_nonces > next_fivehundred) {
733 next_fivehundred = (total_num_nonces/500+1) * 500;
734 printf("Acquired %5d nonces (%5d with distinct bytes 0 and 1). Number of bytes with probability for correctly guessed Sum(a8) > %1.1f%%: %d\n",
735 total_num_nonces,
736 total_added_nonces,
737 CONFIDENCE_THRESHOLD * 100.0,
738 num_good_first_bytes);
739 }
740 }
741
742 } while (num_good_first_bytes < GOOD_BYTES_REQUIRED);
743
b112787d 744 time1 = clock() - time1;
745 if ( time1 > 0 ) {
0d5ee8e2 746 PrintAndLog("Acquired a total of %d nonces in %1.1f seconds (%0.0f nonces/minute)",
747 total_num_nonces,
b112787d 748 ((float)time1)/CLOCKS_PER_SEC,
749 total_num_nonces * 60.0 * CLOCKS_PER_SEC/(float)time1);
750 }
0d5ee8e2 751 fprintf(fstats, "%d;%d;%d;%1.2f;", total_num_nonces, total_added_nonces, num_good_first_bytes, CONFIDENCE_THRESHOLD);
752
a531720a 753}
754
f8ada309 755static int acquire_nonces(uint8_t blockNo, uint8_t keyType, uint8_t *key, uint8_t trgBlockNo, uint8_t trgKeyType, bool nonce_file_write, bool slow)
8ce3e4b4 756{
757 clock_t time1 = clock();
758 bool initialize = true;
759 bool field_off = false;
760 bool finished = false;
a531720a 761 bool filter_flip_checked = false;
8ce3e4b4 762 uint32_t flags = 0;
763 uint8_t write_buf[9];
764 uint32_t total_num_nonces = 0;
765 uint32_t next_fivehundred = 500;
766 uint32_t total_added_nonces = 0;
767 FILE *fnonces = NULL;
768 UsbCommand resp;
769
770 printf("Acquiring nonces...\n");
771
772 clearCommandBuffer();
773
774 do {
775 flags = 0;
776 flags |= initialize ? 0x0001 : 0;
777 flags |= slow ? 0x0002 : 0;
778 flags |= field_off ? 0x0004 : 0;
779 UsbCommand c = {CMD_MIFARE_ACQUIRE_ENCRYPTED_NONCES, {blockNo + keyType * 0x100, trgBlockNo + trgKeyType * 0x100, flags}};
780 memcpy(c.d.asBytes, key, 6);
781
782 SendCommand(&c);
783
784 if (field_off) finished = true;
785
786 if (initialize) {
787 if (!WaitForResponseTimeout(CMD_ACK, &resp, 3000)) return 1;
788 if (resp.arg[0]) return resp.arg[0]; // error during nested_hard
789
790 cuid = resp.arg[1];
791 // PrintAndLog("Acquiring nonces for CUID 0x%08x", cuid);
792 if (nonce_file_write && fnonces == NULL) {
793 if ((fnonces = fopen("nonces.bin","wb")) == NULL) {
794 PrintAndLog("Could not create file nonces.bin");
795 return 3;
796 }
797 PrintAndLog("Writing acquired nonces to binary file nonces.bin");
798 num_to_bytes(cuid, 4, write_buf);
799 fwrite(write_buf, 1, 4, fnonces);
800 fwrite(&trgBlockNo, 1, 1, fnonces);
801 fwrite(&trgKeyType, 1, 1, fnonces);
802 }
803 }
804
805 if (!initialize) {
806 uint32_t nt_enc1, nt_enc2;
807 uint8_t par_enc;
808 uint16_t num_acquired_nonces = resp.arg[2];
809 uint8_t *bufp = resp.d.asBytes;
810 for (uint16_t i = 0; i < num_acquired_nonces; i+=2) {
811 nt_enc1 = bytes_to_num(bufp, 4);
812 nt_enc2 = bytes_to_num(bufp+4, 4);
813 par_enc = bytes_to_num(bufp+8, 1);
814
815 //printf("Encrypted nonce: %08x, encrypted_parity: %02x\n", nt_enc1, par_enc >> 4);
816 total_added_nonces += add_nonce(nt_enc1, par_enc >> 4);
817 //printf("Encrypted nonce: %08x, encrypted_parity: %02x\n", nt_enc2, par_enc & 0x0f);
818 total_added_nonces += add_nonce(nt_enc2, par_enc & 0x0f);
819
820
821 if (nonce_file_write) {
822 fwrite(bufp, 1, 9, fnonces);
823 }
824
825 bufp += 9;
826 }
827
828 total_num_nonces += num_acquired_nonces;
829 }
830
831 if (first_byte_num == 256 ) {
832 // printf("first_byte_num = %d, first_byte_Sum = %d\n", first_byte_num, first_byte_Sum);
a531720a 833 if (!filter_flip_checked) {
834 Check_for_FilterFlipProperties();
835 filter_flip_checked = true;
836 }
8ce3e4b4 837 num_good_first_bytes = estimate_second_byte_sum();
838 if (total_num_nonces > next_fivehundred) {
839 next_fivehundred = (total_num_nonces/500+1) * 500;
840 printf("Acquired %5d nonces (%5d with distinct bytes 0 and 1). Number of bytes with probability for correctly guessed Sum(a8) > %1.1f%%: %d\n",
841 total_num_nonces,
842 total_added_nonces,
843 CONFIDENCE_THRESHOLD * 100.0,
844 num_good_first_bytes);
845 }
846 if (num_good_first_bytes >= GOOD_BYTES_REQUIRED) {
847 field_off = true; // switch off field with next SendCommand and then finish
848 }
849 }
850
851 if (!initialize) {
1a4b6738 852 if (!WaitForResponseTimeout(CMD_ACK, &resp, 3000)) {
853 fclose(fnonces);
854 return 1;
855 }
856 if (resp.arg[0]) {
857 fclose(fnonces);
858 return resp.arg[0]; // error during nested_hard
859 }
8ce3e4b4 860 }
861
862 initialize = false;
863
864 } while (!finished);
865
866
867 if (nonce_file_write) {
868 fclose(fnonces);
869 }
870
b112787d 871 time1 = clock() - time1;
872 if ( time1 > 0 ) {
f8ada309 873 PrintAndLog("Acquired a total of %d nonces in %1.1f seconds (%0.0f nonces/minute)",
8ce3e4b4 874 total_num_nonces,
b112787d 875 ((float)time1)/CLOCKS_PER_SEC,
876 total_num_nonces * 60.0 * CLOCKS_PER_SEC/(float)time1
877 );
878 }
8ce3e4b4 879 return 0;
880}
881
8ce3e4b4 882static int init_partial_statelists(void)
883{
f8ada309 884 const uint32_t sizes_odd[17] = { 126757, 0, 18387, 0, 74241, 0, 181737, 0, 248801, 0, 182033, 0, 73421, 0, 17607, 0, 125601 };
8ce3e4b4 885 const uint32_t sizes_even[17] = { 125723, 0, 17867, 0, 74305, 0, 178707, 0, 248801, 0, 185063, 0, 73356, 0, 18127, 0, 126634 };
886
887 printf("Allocating memory for partial statelists...\n");
888 for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) {
889 for (uint16_t i = 0; i <= 16; i+=2) {
890 partial_statelist[i].len[odd_even] = 0;
891 uint32_t num_of_states = odd_even == ODD_STATE ? sizes_odd[i] : sizes_even[i];
892 partial_statelist[i].states[odd_even] = malloc(sizeof(uint32_t) * num_of_states);
893 if (partial_statelist[i].states[odd_even] == NULL) {
894 PrintAndLog("Cannot allocate enough memory. Aborting");
895 return 4;
896 }
897 for (uint32_t j = 0; j < STATELIST_INDEX_SIZE; j++) {
898 partial_statelist[i].index[odd_even][j] = NULL;
899 }
900 }
901 }
902
903 printf("Generating partial statelists...\n");
904 for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) {
905 uint32_t index = -1;
906 uint32_t num_of_states = 1<<20;
907 for (uint32_t state = 0; state < num_of_states; state++) {
908 uint16_t sum_property = PartialSumProperty(state, odd_even);
909 uint32_t *p = partial_statelist[sum_property].states[odd_even];
910 p += partial_statelist[sum_property].len[odd_even];
911 *p = state;
912 partial_statelist[sum_property].len[odd_even]++;
913 uint32_t index_mask = (STATELIST_INDEX_SIZE-1) << (20-STATELIST_INDEX_WIDTH);
914 if ((state & index_mask) != index) {
915 index = state & index_mask;
916 }
917 if (partial_statelist[sum_property].index[odd_even][index >> (20-STATELIST_INDEX_WIDTH)] == NULL) {
918 partial_statelist[sum_property].index[odd_even][index >> (20-STATELIST_INDEX_WIDTH)] = p;
919 }
920 }
921 // add End Of List markers
922 for (uint16_t i = 0; i <= 16; i += 2) {
923 uint32_t *p = partial_statelist[i].states[odd_even];
924 p += partial_statelist[i].len[odd_even];
925 *p = 0xffffffff;
926 }
927 }
928
929 return 0;
930}
8ce3e4b4 931
932static void init_BitFlip_statelist(void)
933{
934 printf("Generating bitflip statelist...\n");
935 uint32_t *p = statelist_bitflip.states[0] = malloc(sizeof(uint32_t) * 1<<20);
936 uint32_t index = -1;
937 uint32_t index_mask = (STATELIST_INDEX_SIZE-1) << (20-STATELIST_INDEX_WIDTH);
938 for (uint32_t state = 0; state < (1 << 20); state++) {
939 if (filter(state) != filter(state^1)) {
940 if ((state & index_mask) != index) {
941 index = state & index_mask;
942 }
943 if (statelist_bitflip.index[0][index >> (20-STATELIST_INDEX_WIDTH)] == NULL) {
944 statelist_bitflip.index[0][index >> (20-STATELIST_INDEX_WIDTH)] = p;
945 }
946 *p++ = state;
947 }
948 }
949 // set len and add End Of List marker
950 statelist_bitflip.len[0] = p - statelist_bitflip.states[0];
951 *p = 0xffffffff;
952 statelist_bitflip.states[0] = realloc(statelist_bitflip.states[0], sizeof(uint32_t) * (statelist_bitflip.len[0] + 1));
953}
8ce3e4b4 954
a531720a 955static inline uint32_t *find_first_state(uint32_t state, uint32_t mask, partial_indexed_statelist_t *sl, odd_even_t odd_even)
8ce3e4b4 956{
957 uint32_t *p = sl->index[odd_even][(state & mask) >> (20-STATELIST_INDEX_WIDTH)]; // first Bits as index
958
959 if (p == NULL) return NULL;
a531720a 960 while (*p < (state & mask)) p++;
8ce3e4b4 961 if (*p == 0xffffffff) return NULL; // reached end of list, no match
962 if ((*p & mask) == (state & mask)) return p; // found a match.
963 return NULL; // no match
964}
965
a531720a 966static inline bool /*__attribute__((always_inline))*/ invariant_holds(uint_fast8_t byte_diff, uint_fast32_t state1, uint_fast32_t state2, uint_fast8_t bit, uint_fast8_t state_bit)
8ce3e4b4 967{
a531720a 968 uint_fast8_t j_1_bit_mask = 0x01 << (bit-1);
969 uint_fast8_t bit_diff = byte_diff & j_1_bit_mask; // difference of (j-1)th bit
970 uint_fast8_t filter_diff = filter(state1 >> (4-state_bit)) ^ filter(state2 >> (4-state_bit)); // difference in filter function
971 uint_fast8_t mask_y12_y13 = 0xc0 >> state_bit;
972 uint_fast8_t state_bits_diff = (state1 ^ state2) & mask_y12_y13; // difference in state bits 12 and 13
973 uint_fast8_t all_diff = evenparity8(bit_diff ^ state_bits_diff ^ filter_diff); // use parity function to XOR all bits
974 return !all_diff;
975}
976
a531720a 977static inline bool /*__attribute__((always_inline))*/ invalid_state(uint_fast8_t byte_diff, uint_fast32_t state1, uint_fast32_t state2, uint_fast8_t bit, uint_fast8_t state_bit)
978{
979 uint_fast8_t j_bit_mask = 0x01 << bit;
980 uint_fast8_t bit_diff = byte_diff & j_bit_mask; // difference of jth bit
981 uint_fast8_t mask_y13_y16 = 0x48 >> state_bit;
982 uint_fast8_t state_bits_diff = (state1 ^ state2) & mask_y13_y16; // difference in state bits 13 and 16
983 uint_fast8_t all_diff = evenparity8(bit_diff ^ state_bits_diff); // use parity function to XOR all bits
984 return all_diff;
985}
986
a531720a 987static inline bool remaining_bits_match(uint_fast8_t num_common_bits, uint_fast8_t byte_diff, uint_fast32_t state1, uint_fast32_t state2, odd_even_t odd_even)
988{
989 if (odd_even) {
990 // odd bits
991 switch (num_common_bits) {
992 case 0: if (!invariant_holds(byte_diff, state1, state2, 1, 0)) return true;
993 case 1: if (invalid_state(byte_diff, state1, state2, 1, 0)) return false;
994 case 2: if (!invariant_holds(byte_diff, state1, state2, 3, 1)) return true;
995 case 3: if (invalid_state(byte_diff, state1, state2, 3, 1)) return false;
996 case 4: if (!invariant_holds(byte_diff, state1, state2, 5, 2)) return true;
997 case 5: if (invalid_state(byte_diff, state1, state2, 5, 2)) return false;
998 case 6: if (!invariant_holds(byte_diff, state1, state2, 7, 3)) return true;
999 case 7: if (invalid_state(byte_diff, state1, state2, 7, 3)) return false;
8ce3e4b4 1000 }
a531720a 1001 } else {
1002 // even bits
1003 switch (num_common_bits) {
1004 case 0: if (invalid_state(byte_diff, state1, state2, 0, 0)) return false;
1005 case 1: if (!invariant_holds(byte_diff, state1, state2, 2, 1)) return true;
1006 case 2: if (invalid_state(byte_diff, state1, state2, 2, 1)) return false;
1007 case 3: if (!invariant_holds(byte_diff, state1, state2, 4, 2)) return true;
1008 case 4: if (invalid_state(byte_diff, state1, state2, 4, 2)) return false;
1009 case 5: if (!invariant_holds(byte_diff, state1, state2, 6, 3)) return true;
1010 case 6: if (invalid_state(byte_diff, state1, state2, 6, 3)) return false;
8ce3e4b4 1011 }
8ce3e4b4 1012 }
1013
1014 return true; // valid state
1015}
1016
8ce3e4b4 1017static bool all_other_first_bytes_match(uint32_t state, odd_even_t odd_even)
1018{
1019 for (uint16_t i = 1; i < num_good_first_bytes; i++) {
1020 uint16_t sum_a8 = nonces[best_first_bytes[i]].Sum8_guess;
a531720a 1021 uint_fast8_t bytes_diff = best_first_bytes[0] ^ best_first_bytes[i];
1022 uint_fast8_t j = common_bits(bytes_diff);
8ce3e4b4 1023 uint32_t mask = 0xfffffff0;
1024 if (odd_even == ODD_STATE) {
a531720a 1025 mask >>= j/2;
8ce3e4b4 1026 } else {
a531720a 1027 mask >>= (j+1)/2;
8ce3e4b4 1028 }
1029 mask &= 0x000fffff;
1030 //printf("bytes 0x%02x and 0x%02x: %d common bits, mask = 0x%08x, state = 0x%08x, sum_a8 = %d", best_first_bytes[0], best_first_bytes[i], j, mask, state, sum_a8);
1031 bool found_match = false;
1032 for (uint16_t r = 0; r <= 16 && !found_match; r += 2) {
1033 for (uint16_t s = 0; s <= 16 && !found_match; s += 2) {
1034 if (r*(16-s) + (16-r)*s == sum_a8) {
1035 //printf("Checking byte 0x%02x for partial sum (%s) %d\n", best_first_bytes[i], odd_even==ODD_STATE?"odd":"even", odd_even==ODD_STATE?r:s);
1036 uint16_t part_sum_a8 = (odd_even == ODD_STATE) ? r : s;
1037 uint32_t *p = find_first_state(state, mask, &partial_statelist[part_sum_a8], odd_even);
1038 if (p != NULL) {
1039 while ((state & mask) == (*p & mask) && (*p != 0xffffffff)) {
a531720a 1040 if (remaining_bits_match(j, bytes_diff, state, (state&0x00fffff0) | *p, odd_even)) {
8ce3e4b4 1041 found_match = true;
1042 // if ((odd_even == ODD_STATE && state == test_state_odd)
1043 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1044 // printf("all_other_first_bytes_match(): %s test state: remaining bits matched. Bytes = %02x, %02x, Common Bits=%d, mask=0x%08x, PartSum(a8)=%d\n",
1045 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1046 // }
1047 break;
1048 } else {
1049 // if ((odd_even == ODD_STATE && state == test_state_odd)
1050 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1051 // printf("all_other_first_bytes_match(): %s test state: remaining bits didn't match. Bytes = %02x, %02x, Common Bits=%d, mask=0x%08x, PartSum(a8)=%d\n",
1052 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1053 // }
1054 }
1055 p++;
1056 }
1057 } else {
1058 // if ((odd_even == ODD_STATE && state == test_state_odd)
1059 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1060 // printf("all_other_first_bytes_match(): %s test state: couldn't find a matching state. Bytes = %02x, %02x, Common Bits=%d, mask=0x%08x, PartSum(a8)=%d\n",
1061 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1062 // }
1063 }
1064 }
1065 }
1066 }
1067
1068 if (!found_match) {
1069 // if ((odd_even == ODD_STATE && state == test_state_odd)
1070 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1071 // printf("all_other_first_bytes_match(): %s test state: Eliminated. Bytes = %02x, %02x, Common Bits = %d\n", odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j);
1072 // }
1073 return false;
1074 }
1075 }
1076
1077 return true;
1078}
1079
f8ada309 1080static bool all_bit_flips_match(uint32_t state, odd_even_t odd_even)
1081{
1082 for (uint16_t i = 0; i < 256; i++) {
1083 if (nonces[i].BitFlip[odd_even] && i != best_first_bytes[0]) {
a531720a 1084 uint_fast8_t bytes_diff = best_first_bytes[0] ^ i;
1085 uint_fast8_t j = common_bits(bytes_diff);
f8ada309 1086 uint32_t mask = 0xfffffff0;
1087 if (odd_even == ODD_STATE) {
a531720a 1088 mask >>= j/2;
f8ada309 1089 } else {
a531720a 1090 mask >>= (j+1)/2;
f8ada309 1091 }
1092 mask &= 0x000fffff;
1093 //printf("bytes 0x%02x and 0x%02x: %d common bits, mask = 0x%08x, state = 0x%08x, sum_a8 = %d", best_first_bytes[0], best_first_bytes[i], j, mask, state, sum_a8);
1094 bool found_match = false;
1095 uint32_t *p = find_first_state(state, mask, &statelist_bitflip, 0);
1096 if (p != NULL) {
1097 while ((state & mask) == (*p & mask) && (*p != 0xffffffff)) {
a531720a 1098 if (remaining_bits_match(j, bytes_diff, state, (state&0x00fffff0) | *p, odd_even)) {
f8ada309 1099 found_match = true;
1100 // if ((odd_even == ODD_STATE && state == test_state_odd)
1101 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1102 // printf("all_other_first_bytes_match(): %s test state: remaining bits matched. Bytes = %02x, %02x, Common Bits=%d, mask=0x%08x, PartSum(a8)=%d\n",
1103 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1104 // }
1105 break;
1106 } else {
1107 // if ((odd_even == ODD_STATE && state == test_state_odd)
1108 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1109 // printf("all_other_first_bytes_match(): %s test state: remaining bits didn't match. Bytes = %02x, %02x, Common Bits=%d, mask=0x%08x, PartSum(a8)=%d\n",
1110 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1111 // }
1112 }
1113 p++;
1114 }
1115 } else {
1116 // if ((odd_even == ODD_STATE && state == test_state_odd)
1117 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1118 // printf("all_other_first_bytes_match(): %s test state: couldn't find a matching state. Bytes = %02x, %02x, Common Bits=%d, mask=0x%08x, PartSum(a8)=%d\n",
1119 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1120 // }
1121 }
1122 if (!found_match) {
1123 // if ((odd_even == ODD_STATE && state == test_state_odd)
1124 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1125 // printf("all_other_first_bytes_match(): %s test state: Eliminated. Bytes = %02x, %02x, Common Bits = %d\n", odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j);
1126 // }
1127 return false;
1128 }
1129 }
1130
1131 }
1132
1133 return true;
1134}
1135
a531720a 1136static struct sl_cache_entry {
1137 uint32_t *sl;
1138 uint32_t len;
1139 } sl_cache[17][17][2];
1140
a531720a 1141static void init_statelist_cache(void)
1142{
a531720a 1143 for (uint16_t i = 0; i < 17; i+=2) {
1144 for (uint16_t j = 0; j < 17; j+=2) {
1145 for (uint16_t k = 0; k < 2; k++) {
1146 sl_cache[i][j][k].sl = NULL;
1147 sl_cache[i][j][k].len = 0;
1148 }
1149 }
1150 }
1151}
1152
8ce3e4b4 1153static int add_matching_states(statelist_t *candidates, uint16_t part_sum_a0, uint16_t part_sum_a8, odd_even_t odd_even)
1154{
1155 uint32_t worstcase_size = 1<<20;
1156
a531720a 1157 // check cache for existing results
1158 if (sl_cache[part_sum_a0][part_sum_a8][odd_even].sl != NULL) {
1159 candidates->states[odd_even] = sl_cache[part_sum_a0][part_sum_a8][odd_even].sl;
1160 candidates->len[odd_even] = sl_cache[part_sum_a0][part_sum_a8][odd_even].len;
1161 return 0;
1162 }
1163
8ce3e4b4 1164 candidates->states[odd_even] = (uint32_t *)malloc(sizeof(uint32_t) * worstcase_size);
1165 if (candidates->states[odd_even] == NULL) {
1166 PrintAndLog("Out of memory error.\n");
1167 return 4;
1168 }
a531720a 1169 uint32_t *add_p = candidates->states[odd_even];
8ce3e4b4 1170 for (uint32_t *p1 = partial_statelist[part_sum_a0].states[odd_even]; *p1 != 0xffffffff; p1++) {
1171 uint32_t search_mask = 0x000ffff0;
1172 uint32_t *p2 = find_first_state((*p1 << 4), search_mask, &partial_statelist[part_sum_a8], odd_even);
1173 if (p2 != NULL) {
1174 while (((*p1 << 4) & search_mask) == (*p2 & search_mask) && *p2 != 0xffffffff) {
a531720a 1175 if ((nonces[best_first_bytes[0]].BitFlip[odd_even] && find_first_state((*p1 << 4) | *p2, 0x000fffff, &statelist_bitflip, 0))
1176 || !nonces[best_first_bytes[0]].BitFlip[odd_even]) {
8ce3e4b4 1177 if (all_other_first_bytes_match((*p1 << 4) | *p2, odd_even)) {
f8ada309 1178 if (all_bit_flips_match((*p1 << 4) | *p2, odd_even)) {
a531720a 1179 *add_p++ = (*p1 << 4) | *p2;
1180 }
8ce3e4b4 1181 }
f8ada309 1182 }
8ce3e4b4 1183 p2++;
1184 }
1185 }
8ce3e4b4 1186 }
f8ada309 1187
a531720a 1188 // set end of list marker and len
1189 *add_p = 0xffffffff;
1190 candidates->len[odd_even] = add_p - candidates->states[odd_even];
f8ada309 1191
8ce3e4b4 1192 candidates->states[odd_even] = realloc(candidates->states[odd_even], sizeof(uint32_t) * (candidates->len[odd_even] + 1));
1193
a531720a 1194 sl_cache[part_sum_a0][part_sum_a8][odd_even].sl = candidates->states[odd_even];
1195 sl_cache[part_sum_a0][part_sum_a8][odd_even].len = candidates->len[odd_even];
1196
8ce3e4b4 1197 return 0;
1198}
1199
8ce3e4b4 1200static statelist_t *add_more_candidates(statelist_t *current_candidates)
1201{
1202 statelist_t *new_candidates = NULL;
1203 if (current_candidates == NULL) {
1204 if (candidates == NULL) {
1205 candidates = (statelist_t *)malloc(sizeof(statelist_t));
1206 }
1207 new_candidates = candidates;
1208 } else {
1209 new_candidates = current_candidates->next = (statelist_t *)malloc(sizeof(statelist_t));
1210 }
1211 new_candidates->next = NULL;
1212 new_candidates->len[ODD_STATE] = 0;
1213 new_candidates->len[EVEN_STATE] = 0;
1214 new_candidates->states[ODD_STATE] = NULL;
1215 new_candidates->states[EVEN_STATE] = NULL;
1216 return new_candidates;
1217}
1218
8ce3e4b4 1219static void TestIfKeyExists(uint64_t key)
1220{
1221 struct Crypto1State *pcs;
1222 pcs = crypto1_create(key);
1223 crypto1_byte(pcs, (cuid >> 24) ^ best_first_bytes[0], true);
1224
1225 uint32_t state_odd = pcs->odd & 0x00ffffff;
1226 uint32_t state_even = pcs->even & 0x00ffffff;
f8ada309 1227 //printf("Tests: searching for key %llx after first byte 0x%02x (state_odd = 0x%06x, state_even = 0x%06x) ...\n", key, best_first_bytes[0], state_odd, state_even);
8ce3e4b4 1228
f8ada309 1229 uint64_t count = 0;
8ce3e4b4 1230 for (statelist_t *p = candidates; p != NULL; p = p->next) {
f8ada309 1231 bool found_odd = false;
1232 bool found_even = false;
8ce3e4b4 1233 uint32_t *p_odd = p->states[ODD_STATE];
1234 uint32_t *p_even = p->states[EVEN_STATE];
1235 while (*p_odd != 0xffffffff) {
f8ada309 1236 if ((*p_odd & 0x00ffffff) == state_odd) {
1237 found_odd = true;
1238 break;
1239 }
8ce3e4b4 1240 p_odd++;
1241 }
1242 while (*p_even != 0xffffffff) {
f8ada309 1243 if ((*p_even & 0x00ffffff) == state_even) {
1244 found_even = true;
1245 }
8ce3e4b4 1246 p_even++;
1247 }
f8ada309 1248 count += (p_odd - p->states[ODD_STATE]) * (p_even - p->states[EVEN_STATE]);
1249 if (found_odd && found_even) {
1250 PrintAndLog("Key Found after testing %lld (2^%1.1f) out of %lld (2^%1.1f) keys. A brute force would have taken approx %lld minutes.",
1251 count, log(count)/log(2),
1252 maximum_states, log(maximum_states)/log(2),
fe8042f2 1253 (count>>23)/60);
0d5ee8e2 1254 if (write_stats) {
1255 fprintf(fstats, "1\n");
1256 }
f8ada309 1257 crypto1_destroy(pcs);
1258 return;
1259 }
8ce3e4b4 1260 }
f8ada309 1261
1262 printf("Key NOT found!\n");
0d5ee8e2 1263 if (write_stats) {
1264 fprintf(fstats, "0\n");
1265 }
8ce3e4b4 1266 crypto1_destroy(pcs);
1267}
1268
8ce3e4b4 1269static void generate_candidates(uint16_t sum_a0, uint16_t sum_a8)
1270{
1271 printf("Generating crypto1 state candidates... \n");
1272
1273 statelist_t *current_candidates = NULL;
1274 // estimate maximum candidate states
f8ada309 1275 maximum_states = 0;
8ce3e4b4 1276 for (uint16_t sum_odd = 0; sum_odd <= 16; sum_odd += 2) {
1277 for (uint16_t sum_even = 0; sum_even <= 16; sum_even += 2) {
1278 if (sum_odd*(16-sum_even) + (16-sum_odd)*sum_even == sum_a0) {
1279 maximum_states += (uint64_t)partial_statelist[sum_odd].len[ODD_STATE] * partial_statelist[sum_even].len[EVEN_STATE] * (1<<8);
1280 }
1281 }
1282 }
5e32cf75 1283 printf("Number of possible keys with Sum(a0) = %d: %"PRIu64" (2^%1.1f)\n", sum_a0, maximum_states, log(maximum_states)/log(2.0));
8ce3e4b4 1284
a531720a 1285 init_statelist_cache();
1286
8ce3e4b4 1287 for (uint16_t p = 0; p <= 16; p += 2) {
1288 for (uint16_t q = 0; q <= 16; q += 2) {
1289 if (p*(16-q) + (16-p)*q == sum_a0) {
1290 printf("Reducing Partial Statelists (p,q) = (%d,%d) with lengths %d, %d\n",
1291 p, q, partial_statelist[p].len[ODD_STATE], partial_statelist[q].len[EVEN_STATE]);
1292 for (uint16_t r = 0; r <= 16; r += 2) {
1293 for (uint16_t s = 0; s <= 16; s += 2) {
1294 if (r*(16-s) + (16-r)*s == sum_a8) {
1295 current_candidates = add_more_candidates(current_candidates);
a531720a 1296 // check for the smallest partial statelist. Try this first - it might give 0 candidates
1297 // and eliminate the need to calculate the other part
1298 if (MIN(partial_statelist[p].len[ODD_STATE], partial_statelist[r].len[ODD_STATE])
1299 < MIN(partial_statelist[q].len[EVEN_STATE], partial_statelist[s].len[EVEN_STATE])) {
8ce3e4b4 1300 add_matching_states(current_candidates, p, r, ODD_STATE);
a531720a 1301 if(current_candidates->len[ODD_STATE]) {
8ce3e4b4 1302 add_matching_states(current_candidates, q, s, EVEN_STATE);
a531720a 1303 } else {
1304 current_candidates->len[EVEN_STATE] = 0;
1305 uint32_t *p = current_candidates->states[EVEN_STATE] = malloc(sizeof(uint32_t));
1306 *p = 0xffffffff;
1307 }
1308 } else {
1309 add_matching_states(current_candidates, q, s, EVEN_STATE);
1310 if(current_candidates->len[EVEN_STATE]) {
1311 add_matching_states(current_candidates, p, r, ODD_STATE);
1312 } else {
1313 current_candidates->len[ODD_STATE] = 0;
1314 uint32_t *p = current_candidates->states[ODD_STATE] = malloc(sizeof(uint32_t));
1315 *p = 0xffffffff;
1316 }
1317 }
1318 printf("Odd state candidates: %6d (2^%0.1f)\n", current_candidates->len[ODD_STATE], log(current_candidates->len[ODD_STATE])/log(2));
1319 printf("Even state candidates: %6d (2^%0.1f)\n", current_candidates->len[EVEN_STATE], log(current_candidates->len[EVEN_STATE])/log(2));
8ce3e4b4 1320 }
1321 }
1322 }
1323 }
1324 }
1325 }
1326
1327
1328 maximum_states = 0;
1329 for (statelist_t *sl = candidates; sl != NULL; sl = sl->next) {
1330 maximum_states += (uint64_t)sl->len[ODD_STATE] * sl->len[EVEN_STATE];
1331 }
5e32cf75 1332 printf("Number of remaining possible keys: %"PRIu64" (2^%1.1f)\n", maximum_states, log(maximum_states)/log(2.0));
0d5ee8e2 1333 if (write_stats) {
1334 if (maximum_states != 0) {
1335 fprintf(fstats, "%1.1f;", log(maximum_states)/log(2.0));
1336 } else {
1337 fprintf(fstats, "%1.1f;", 0.0);
1338 }
1339 }
1340}
1341
0d5ee8e2 1342static void free_candidates_memory(statelist_t *sl)
1343{
1344 if (sl == NULL) {
1345 return;
1346 } else {
1347 free_candidates_memory(sl->next);
1348 free(sl);
1349 }
1350}
1351
0d5ee8e2 1352static void free_statelist_cache(void)
1353{
1354 for (uint16_t i = 0; i < 17; i+=2) {
1355 for (uint16_t j = 0; j < 17; j+=2) {
1356 for (uint16_t k = 0; k < 2; k++) {
1357 free(sl_cache[i][j][k].sl);
1358 }
1359 }
1360 }
8ce3e4b4 1361}
1362
3130ba4b 1363size_t keys_found = 0;
1364size_t bucket_count = 0;
1365statelist_t* buckets[128];
1366size_t total_states_tested = 0;
1367size_t thread_count = 4;
1368
1369// these bitsliced states will hold identical states in all slices
1370bitslice_t bitsliced_rollback_byte[ROLLBACK_SIZE];
1371
1372// arrays of bitsliced states with identical values in all slices
1373bitslice_t bitsliced_encrypted_nonces[NONCE_TESTS][STATE_SIZE];
1374bitslice_t bitsliced_encrypted_parity_bits[NONCE_TESTS][ROLLBACK_SIZE];
1375
1376#define EXACT_COUNT
1377
1378static const uint64_t crack_states_bitsliced(statelist_t *p){
1379 // the idea to roll back the half-states before combining them was suggested/explained to me by bla
1380 // first we pre-bitslice all the even state bits and roll them back, then bitslice the odd bits and combine the two in the inner loop
1381 uint64_t key = -1;
1382 uint8_t bSize = sizeof(bitslice_t);
1383
1384#ifdef EXACT_COUNT
1385 size_t bucket_states_tested = 0;
1386 size_t bucket_size[p->len[EVEN_STATE]/MAX_BITSLICES];
1387#else
1388 const size_t bucket_states_tested = (p->len[EVEN_STATE])*(p->len[ODD_STATE]);
1389#endif
1390
1391 bitslice_t *bitsliced_even_states[p->len[EVEN_STATE]/MAX_BITSLICES];
1392 size_t bitsliced_blocks = 0;
1393 uint32_t const * restrict even_end = p->states[EVEN_STATE]+p->len[EVEN_STATE];
1394
1395 // bitslice all the even states
1396 for(uint32_t * restrict p_even = p->states[EVEN_STATE]; p_even < even_end; p_even += MAX_BITSLICES){
1397
1398#ifdef __WIN32
1399 #ifdef __MINGW32__
1400 bitslice_t * restrict lstate_p = __mingw_aligned_malloc((STATE_SIZE+ROLLBACK_SIZE) * bSize, bSize);
1401 #else
1402 bitslice_t * restrict lstate_p = _aligned_malloc((STATE_SIZE+ROLLBACK_SIZE) * bSize, bSize);
1403 #endif
1404#else
1405 bitslice_t * restrict lstate_p = memalign(bSize, (STATE_SIZE+ROLLBACK_SIZE) * bSize);
1406#endif
1407
1408 if ( !lstate_p ) {
1409 __sync_fetch_and_add(&total_states_tested, bucket_states_tested);
1410 return key;
1411 }
1412
1413 memset(lstate_p+1, 0x0, (STATE_SIZE-1)*sizeof(bitslice_t)); // zero even bits
1414
1415 // bitslice even half-states
1416 const size_t max_slices = (even_end-p_even) < MAX_BITSLICES ? even_end-p_even : MAX_BITSLICES;
1417#ifdef EXACT_COUNT
1418 bucket_size[bitsliced_blocks] = max_slices;
1419#endif
1420 for(size_t slice_idx = 0; slice_idx < max_slices; ++slice_idx){
1421 uint32_t e = *(p_even+slice_idx);
1422 for(size_t bit_idx = 1; bit_idx < STATE_SIZE; bit_idx+=2, e >>= 1){
1423 // set even bits
1424 if(e&1){
1425 lstate_p[bit_idx].bytes64[slice_idx>>6] |= 1ull << (slice_idx&63);
1426 }
1427 }
1428 }
1429 // compute the rollback bits
1430 for(size_t rollback = 0; rollback < ROLLBACK_SIZE; ++rollback){
1431 // inlined crypto1_bs_lfsr_rollback
1432 const bitslice_value_t feedout = lstate_p[0].value;
1433 ++lstate_p;
1434 const bitslice_value_t ks_bits = crypto1_bs_f20(lstate_p);
1435 const bitslice_value_t feedback = (feedout ^ ks_bits ^ lstate_p[47- 5].value ^ lstate_p[47- 9].value ^
1436 lstate_p[47-10].value ^ lstate_p[47-12].value ^ lstate_p[47-14].value ^
1437 lstate_p[47-15].value ^ lstate_p[47-17].value ^ lstate_p[47-19].value ^
1438 lstate_p[47-24].value ^ lstate_p[47-25].value ^ lstate_p[47-27].value ^
1439 lstate_p[47-29].value ^ lstate_p[47-35].value ^ lstate_p[47-39].value ^
1440 lstate_p[47-41].value ^ lstate_p[47-42].value ^ lstate_p[47-43].value);
1441 lstate_p[47].value = feedback ^ bitsliced_rollback_byte[rollback].value;
1442 }
1443 bitsliced_even_states[bitsliced_blocks++] = lstate_p;
1444 }
1445
1446 // bitslice every odd state to every block of even half-states with half-finished rollback
1447 for(uint32_t const * restrict p_odd = p->states[ODD_STATE]; p_odd < p->states[ODD_STATE]+p->len[ODD_STATE]; ++p_odd){
1448 // early abort
1449 if(keys_found){
1450 goto out;
1451 }
1452
1453 // set the odd bits and compute rollback
1454 uint64_t o = (uint64_t) *p_odd;
1455 lfsr_rollback_byte((struct Crypto1State*) &o, 0, 1);
1456 // pre-compute part of the odd feedback bits (minus rollback)
1457 bool odd_feedback_bit = parity(o&0x9ce5c);
1458
1459 crypto1_bs_rewind_a0();
1460 // set odd bits
1461 for(size_t state_idx = 0; state_idx < STATE_SIZE-ROLLBACK_SIZE; o >>= 1, state_idx+=2){
1462 if(o & 1){
1463 state_p[state_idx] = bs_ones;
1464 } else {
1465 state_p[state_idx] = bs_zeroes;
1466 }
1467 }
1468 const bitslice_value_t odd_feedback = odd_feedback_bit ? bs_ones.value : bs_zeroes.value;
1469
1470 for(size_t block_idx = 0; block_idx < bitsliced_blocks; ++block_idx){
1471 const bitslice_t const * restrict bitsliced_even_state = bitsliced_even_states[block_idx];
1472 size_t state_idx;
1473 // set even bits
1474 for(state_idx = 0; state_idx < STATE_SIZE-ROLLBACK_SIZE; state_idx+=2){
1475 state_p[1+state_idx] = bitsliced_even_state[1+state_idx];
1476 }
1477 // set rollback bits
1478 uint64_t lo = o;
1479 for(; state_idx < STATE_SIZE; lo >>= 1, state_idx+=2){
1480 // set the odd bits and take in the odd rollback bits from the even states
1481 if(lo & 1){
1482 state_p[state_idx].value = ~bitsliced_even_state[state_idx].value;
1483 } else {
1484 state_p[state_idx] = bitsliced_even_state[state_idx];
1485 }
1486
1487 // set the even bits and take in the even rollback bits from the odd states
1488 if((lo >> 32) & 1){
1489 state_p[1+state_idx].value = ~bitsliced_even_state[1+state_idx].value;
1490 } else {
1491 state_p[1+state_idx] = bitsliced_even_state[1+state_idx];
1492 }
1493 }
1494
1495#ifdef EXACT_COUNT
1496 bucket_states_tested += bucket_size[block_idx];
1497#endif
1498 // pre-compute first keystream and feedback bit vectors
1499 const bitslice_value_t ksb = crypto1_bs_f20(state_p);
1500 const bitslice_value_t fbb = (odd_feedback ^ state_p[47- 0].value ^ state_p[47- 5].value ^ // take in the even and rollback bits
1501 state_p[47-10].value ^ state_p[47-12].value ^ state_p[47-14].value ^
1502 state_p[47-24].value ^ state_p[47-42].value);
1503
1504 // vector to contain test results (1 = passed, 0 = failed)
1505 bitslice_t results = bs_ones;
1506
1507 for(size_t tests = 0; tests < NONCE_TESTS; ++tests){
1508 size_t parity_bit_idx = 0;
1509 bitslice_value_t fb_bits = fbb;
1510 bitslice_value_t ks_bits = ksb;
1511 state_p = &states[KEYSTREAM_SIZE-1];
1512 bitslice_value_t parity_bit_vector = bs_zeroes.value;
1513
1514 // highest bit is transmitted/received first
1515 for(int32_t ks_idx = KEYSTREAM_SIZE-1; ks_idx >= 0; --ks_idx, --state_p){
1516 // decrypt nonce bits
1517 const bitslice_value_t encrypted_nonce_bit_vector = bitsliced_encrypted_nonces[tests][ks_idx].value;
1518 const bitslice_value_t decrypted_nonce_bit_vector = (encrypted_nonce_bit_vector ^ ks_bits);
1519
1520 // compute real parity bits on the fly
1521 parity_bit_vector ^= decrypted_nonce_bit_vector;
1522
1523 // update state
1524 state_p[0].value = (fb_bits ^ decrypted_nonce_bit_vector);
1525
1526 // compute next keystream bit
1527 ks_bits = crypto1_bs_f20(state_p);
1528
1529 // for each byte:
1530 if((ks_idx&7) == 0){
1531 // get encrypted parity bits
1532 const bitslice_value_t encrypted_parity_bit_vector = bitsliced_encrypted_parity_bits[tests][parity_bit_idx++].value;
1533
1534 // decrypt parity bits
1535 const bitslice_value_t decrypted_parity_bit_vector = (encrypted_parity_bit_vector ^ ks_bits);
1536
1537 // compare actual parity bits with decrypted parity bits and take count in results vector
1538 results.value &= (parity_bit_vector ^ decrypted_parity_bit_vector);
1539
1540 // make sure we still have a match in our set
1541 // if(memcmp(&results, &bs_zeroes, sizeof(bitslice_t)) == 0){
1542
1543 // this is much faster on my gcc, because somehow a memcmp needlessly spills/fills all the xmm registers to/from the stack - ???
1544 // the short-circuiting also helps
1545 if(results.bytes64[0] == 0
1546#if MAX_BITSLICES > 64
1547 && results.bytes64[1] == 0
1548#endif
1549#if MAX_BITSLICES > 128
1550 && results.bytes64[2] == 0
1551 && results.bytes64[3] == 0
1552#endif
1553 ){
1554 goto stop_tests;
1555 }
1556 // this is about as fast but less portable (requires -std=gnu99)
1557 // asm goto ("ptest %1, %0\n\t"
1558 // "jz %l2" :: "xm" (results.value), "xm" (bs_ones.value) : "cc" : stop_tests);
1559 parity_bit_vector = bs_zeroes.value;
1560 }
1561 // compute next feedback bit vector
1562 fb_bits = (state_p[47- 0].value ^ state_p[47- 5].value ^ state_p[47- 9].value ^
1563 state_p[47-10].value ^ state_p[47-12].value ^ state_p[47-14].value ^
1564 state_p[47-15].value ^ state_p[47-17].value ^ state_p[47-19].value ^
1565 state_p[47-24].value ^ state_p[47-25].value ^ state_p[47-27].value ^
1566 state_p[47-29].value ^ state_p[47-35].value ^ state_p[47-39].value ^
1567 state_p[47-41].value ^ state_p[47-42].value ^ state_p[47-43].value);
1568 }
1569 }
1570 // all nonce tests were successful: we've found the key in this block!
1571 state_t keys[MAX_BITSLICES];
1572 crypto1_bs_convert_states(&states[KEYSTREAM_SIZE], keys);
1573 for(size_t results_idx = 0; results_idx < MAX_BITSLICES; ++results_idx){
1574 if(get_vector_bit(results_idx, results)){
1575 key = keys[results_idx].value;
1576 goto out;
1577 }
1578 }
1579stop_tests:
1580 // prepare to set new states
1581 crypto1_bs_rewind_a0();
1582 continue;
1583 }
1584 }
1585
1586out:
1587 for(size_t block_idx = 0; block_idx < bitsliced_blocks; ++block_idx){
1588
1589#ifdef __WIN32
1590 #ifdef __MINGW32__
1591 __mingw_aligned_free(bitsliced_even_states[block_idx]-ROLLBACK_SIZE);
1592 #else
1593 _aligned_free(bitsliced_even_states[block_idx]-ROLLBACK_SIZE);
1594 #endif
1595#else
2e350b19 1596 free(bitsliced_even_states[block_idx]-ROLLBACK_SIZE);
3130ba4b 1597#endif
1598
1599 }
1600 __sync_fetch_and_add(&total_states_tested, bucket_states_tested);
1601 return key;
1602}
8ce3e4b4 1603
3130ba4b 1604static void* crack_states_thread(void* x){
1605 const size_t thread_id = (size_t)x;
1606 size_t current_bucket = thread_id;
1607 while(current_bucket < bucket_count){
1608 statelist_t * bucket = buckets[current_bucket];
1609 if(bucket){
1610 const uint64_t key = crack_states_bitsliced(bucket);
1611 if(key != -1){
1612 printf("\nFound key: %012"PRIx64"\n", key);
1613 __sync_fetch_and_add(&keys_found, 1);
1614 break;
1615 } else if(keys_found){
1616 break;
1617 } else {
1618 printf(".");
1619 fflush(stdout);
1620 }
1621 }
1622 current_bucket += thread_count;
1623 }
1624 return NULL;
1625}
cd777a05 1626
f8ada309 1627static void brute_force(void)
8ce3e4b4 1628{
f8ada309 1629 if (known_target_key != -1) {
1630 PrintAndLog("Looking for known target key in remaining key space...");
1631 TestIfKeyExists(known_target_key);
f8ada309 1632 } else {
3130ba4b 1633 PrintAndLog("Brute force phase starting.");
1634 time_t start, end;
1635 time(&start);
1636 keys_found = 0;
1637
1638 crypto1_bs_init();
1639
1640 PrintAndLog("Using %u-bit bitslices", MAX_BITSLICES);
1641 PrintAndLog("Bitslicing best_first_byte^uid[3] (rollback byte): %02x...", best_first_bytes[0]^(cuid>>24));
1642 // convert to 32 bit little-endian
1643 crypto1_bs_bitslice_value32(rev32((best_first_bytes[0]^(cuid>>24))), bitsliced_rollback_byte, 8);
1644
1645 PrintAndLog("Bitslicing nonces...");
1646 for(size_t tests = 0; tests < NONCE_TESTS; tests++){
1647 uint32_t test_nonce = brute_force_nonces[tests]->nonce_enc;
1648 uint8_t test_parity = brute_force_nonces[tests]->par_enc;
1649 // pre-xor the uid into the decrypted nonces, and also pre-xor the cuid parity into the encrypted parity bits - otherwise an exta xor is required in the decryption routine
1650 crypto1_bs_bitslice_value32(cuid^test_nonce, bitsliced_encrypted_nonces[tests], 32);
1651 // convert to 32 bit little-endian
1652 crypto1_bs_bitslice_value32(rev32( ~(test_parity ^ ~(parity(cuid>>24 & 0xff)<<3 | parity(cuid>>16 & 0xff)<<2 | parity(cuid>>8 & 0xff)<<1 | parity(cuid&0xff)))), bitsliced_encrypted_parity_bits[tests], 4);
1653 }
1654 total_states_tested = 0;
1655
1656 // count number of states to go
1657 bucket_count = 0;
1658 for (statelist_t *p = candidates; p != NULL; p = p->next) {
1659 buckets[bucket_count] = p;
1660 bucket_count++;
1661 }
1662
1663#ifndef __WIN32
1664 thread_count = sysconf(_SC_NPROCESSORS_CONF);
cd777a05 1665 if ( thread_count < 1)
1666 thread_count = 1;
3130ba4b 1667#endif /* _WIN32 */
1668 pthread_t threads[thread_count];
1669
1670 // enumerate states using all hardware threads, each thread handles one bucket
1671 PrintAndLog("Starting %u cracking threads to search %u buckets containing a total of %"PRIu32" states...", thread_count, bucket_count, maximum_states);
1672
1673 for(size_t i = 0; i < thread_count; i++){
1674 pthread_create(&threads[i], NULL, crack_states_thread, (void*) i);
1675 }
1676 for(size_t i = 0; i < thread_count; i++){
1677 pthread_join(threads[i], 0);
1678 }
1679
1680 time(&end);
1681 unsigned long elapsed_time = difftime(end, start);
1682 PrintAndLog("Tested %"PRIu32" states, found %u keys after %u seconds", total_states_tested, keys_found, elapsed_time);
1683 if(!keys_found){
1684 assert(total_states_tested == maximum_states);
1685 }
1686 // reset this counter for the next call
1687 nonces_to_bruteforce = 0;
f8ada309 1688 }
f8ada309 1689}
1690
0d5ee8e2 1691int mfnestedhard(uint8_t blockNo, uint8_t keyType, uint8_t *key, uint8_t trgBlockNo, uint8_t trgKeyType, uint8_t *trgkey, bool nonce_file_read, bool nonce_file_write, bool slow, int tests)
f8ada309 1692{
0d5ee8e2 1693 // initialize Random number generator
1694 time_t t;
1695 srand((unsigned) time(&t));
1696
f8ada309 1697 if (trgkey != NULL) {
1698 known_target_key = bytes_to_num(trgkey, 6);
1699 } else {
1700 known_target_key = -1;
1701 }
8ce3e4b4 1702
8ce3e4b4 1703 init_partial_statelists();
1704 init_BitFlip_statelist();
0d5ee8e2 1705 write_stats = false;
8ce3e4b4 1706
0d5ee8e2 1707 if (tests) {
1708 // set the correct locale for the stats printing
1709 setlocale(LC_ALL, "");
1710 write_stats = true;
1711 if ((fstats = fopen("hardnested_stats.txt","a")) == NULL) {
1712 PrintAndLog("Could not create/open file hardnested_stats.txt");
1713 return 3;
1714 }
1715 for (uint32_t i = 0; i < tests; i++) {
1716 init_nonce_memory();
1717 simulate_acquire_nonces();
1718 Tests();
1719 printf("Sum(a0) = %d\n", first_byte_Sum);
1720 fprintf(fstats, "%d;", first_byte_Sum);
1721 generate_candidates(first_byte_Sum, nonces[best_first_bytes[0]].Sum8_guess);
1722 brute_force();
1723 free_nonces_memory();
1724 free_statelist_cache();
1725 free_candidates_memory(candidates);
1726 candidates = NULL;
1727 }
1728 fclose(fstats);
1729 } else {
1730 init_nonce_memory();
b112787d 1731 if (nonce_file_read) { // use pre-acquired data from file nonces.bin
1732 if (read_nonce_file() != 0) {
1733 return 3;
1734 }
1735 Check_for_FilterFlipProperties();
1736 num_good_first_bytes = MIN(estimate_second_byte_sum(), GOOD_BYTES_REQUIRED);
1737 } else { // acquire nonces.
1738 uint16_t is_OK = acquire_nonces(blockNo, keyType, key, trgBlockNo, trgKeyType, nonce_file_write, slow);
1739 if (is_OK != 0) {
1740 return is_OK;
1741 }
8ce3e4b4 1742 }
8ce3e4b4 1743
b112787d 1744 Tests();
1745
1746 PrintAndLog("");
1747 PrintAndLog("Sum(a0) = %d", first_byte_Sum);
1748 // PrintAndLog("Best 10 first bytes: %02x, %02x, %02x, %02x, %02x, %02x, %02x, %02x, %02x, %02x",
1749 // best_first_bytes[0],
1750 // best_first_bytes[1],
1751 // best_first_bytes[2],
1752 // best_first_bytes[3],
1753 // best_first_bytes[4],
1754 // best_first_bytes[5],
1755 // best_first_bytes[6],
1756 // best_first_bytes[7],
1757 // best_first_bytes[8],
1758 // best_first_bytes[9] );
1759 PrintAndLog("Number of first bytes with confidence > %2.1f%%: %d", CONFIDENCE_THRESHOLD*100.0, num_good_first_bytes);
1760
1761 clock_t time1 = clock();
1762 generate_candidates(first_byte_Sum, nonces[best_first_bytes[0]].Sum8_guess);
1763 time1 = clock() - time1;
1764 if ( time1 > 0 )
1765 PrintAndLog("Time for generating key candidates list: %1.0f seconds", ((float)time1)/CLOCKS_PER_SEC);
8ce3e4b4 1766
b112787d 1767 brute_force();
1768 free_nonces_memory();
1769 free_statelist_cache();
1770 free_candidates_memory(candidates);
1771 candidates = NULL;
1772 }
8ce3e4b4 1773 return 0;
1774}
1775
1776
Impressum, Datenschutz