1 //-----------------------------------------------------------------------------
2 // Copyright (C) 2015 piwi
3 // fiddled with 2016 Azcid (hardnested bitsliced Bruteforce imp)
4 // fiddled with 2016 Matrix ( sub testing of nonces while collecting )
5 // This code is licensed to you under the terms of the GNU GPL, version 2 or,
6 // at your option, any later version. See the LICENSE.txt file for the text of
8 //-----------------------------------------------------------------------------
9 // Implements a card only attack based on crypto text (encrypted nonces
10 // received during a nested authentication) only. Unlike other card only
11 // attacks this doesn't rely on implementation errors but only on the
12 // inherent weaknesses of the crypto1 cypher. Described in
13 // Carlo Meijer, Roel Verdult, "Ciphertext-only Cryptanalysis on Hardened
14 // Mifare Classic Cards" in Proceedings of the 22nd ACM SIGSAC Conference on
15 // Computer and Communications Security, 2015
16 //-----------------------------------------------------------------------------
17 #include "cmdhfmfhard.h"
19 #define CONFIDENCE_THRESHOLD 0.95 // Collect nonces until we are certain enough that the following brute force is successfull
20 #define GOOD_BYTES_REQUIRED 13 // default 28, could be smaller == faster
21 #define NONCES_THRESHOLD 5000 // every N nonces check if we can crack the key
22 #define CRACKING_THRESHOLD 39.00f // as 2^39
24 #define END_OF_LIST_MARKER 0xFFFFFFFF
26 static const float p_K
[257] = { // the probability that a random nonce has a Sum Property == K
27 0.0290, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
28 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
29 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
30 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
31 0.0083, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
32 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
33 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
34 0.0006, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
35 0.0339, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
36 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
37 0.0048, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
38 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
39 0.0934, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
40 0.0119, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
41 0.0489, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
42 0.0602, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
43 0.4180, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
44 0.0602, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
45 0.0489, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
46 0.0119, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
47 0.0934, 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.0048, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
50 0.0000, 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.0006, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
53 0.0000, 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.0083, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
56 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
57 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
58 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
61 typedef struct noncelistentry
{
67 typedef struct noncelist
{
74 noncelistentry_t
*first
;
78 static size_t nonces_to_bruteforce
= 0;
79 static noncelistentry_t
*brute_force_nonces
[256];
80 static uint32_t cuid
= 0;
81 static noncelist_t nonces
[256];
82 static uint8_t best_first_bytes
[256];
83 static uint16_t first_byte_Sum
= 0;
84 static uint16_t first_byte_num
= 0;
85 static uint16_t num_good_first_bytes
= 0;
86 static uint64_t maximum_states
= 0;
87 static uint64_t known_target_key
;
88 static bool write_stats
= false;
89 static FILE *fstats
= NULL
;
97 #define STATELIST_INDEX_WIDTH 16
98 #define STATELIST_INDEX_SIZE (1<<STATELIST_INDEX_WIDTH)
103 uint32_t *index
[2][STATELIST_INDEX_SIZE
];
104 } partial_indexed_statelist_t
;
113 static partial_indexed_statelist_t partial_statelist
[17];
114 static partial_indexed_statelist_t statelist_bitflip
;
115 static statelist_t
*candidates
= NULL
;
117 bool field_off
= false;
119 static bool generate_candidates(uint16_t, uint16_t);
120 static bool brute_force(void);
122 static int add_nonce(uint32_t nonce_enc
, uint8_t par_enc
)
124 uint8_t first_byte
= nonce_enc
>> 24;
125 noncelistentry_t
*p1
= nonces
[first_byte
].first
;
126 noncelistentry_t
*p2
= NULL
;
128 if (p1
== NULL
) { // first nonce with this 1st byte
130 first_byte_Sum
+= evenparity32((nonce_enc
& 0xff000000) | (par_enc
& 0x08));
131 // printf("Adding nonce 0x%08x, par_enc 0x%02x, parity(0x%08x) = %d\n",
134 // (nonce_enc & 0xff000000) | (par_enc & 0x08) |0x01,
135 // parity((nonce_enc & 0xff000000) | (par_enc & 0x08));
138 while (p1
!= NULL
&& (p1
->nonce_enc
& 0x00ff0000) < (nonce_enc
& 0x00ff0000)) {
143 if (p1
== NULL
) { // need to add at the end of the list
144 if (p2
== NULL
) { // list is empty yet. Add first entry.
145 p2
= nonces
[first_byte
].first
= malloc(sizeof(noncelistentry_t
));
146 } else { // add new entry at end of existing list.
147 p2
= p2
->next
= malloc(sizeof(noncelistentry_t
));
149 } else if ((p1
->nonce_enc
& 0x00ff0000) != (nonce_enc
& 0x00ff0000)) { // found distinct 2nd byte. Need to insert.
150 if (p2
== NULL
) { // need to insert at start of list
151 p2
= nonces
[first_byte
].first
= malloc(sizeof(noncelistentry_t
));
153 p2
= p2
->next
= malloc(sizeof(noncelistentry_t
));
155 } else { // we have seen this 2nd byte before. Nothing to add or insert.
159 // add or insert new data
161 p2
->nonce_enc
= nonce_enc
;
162 p2
->par_enc
= par_enc
;
164 if(nonces_to_bruteforce
< 256){
165 brute_force_nonces
[nonces_to_bruteforce
] = p2
;
166 nonces_to_bruteforce
++;
169 nonces
[first_byte
].num
++;
170 nonces
[first_byte
].Sum
+= evenparity32((nonce_enc
& 0x00ff0000) | (par_enc
& 0x04));
171 nonces
[first_byte
].updated
= true; // indicates that we need to recalculate the Sum(a8) probability for this first byte
173 return (1); // new nonce added
176 static void init_nonce_memory(void)
178 for (uint16_t i
= 0; i
< 256; i
++) {
181 nonces
[i
].Sum8_guess
= 0;
182 nonces
[i
].Sum8_prob
= 0.0;
183 nonces
[i
].updated
= true;
184 nonces
[i
].first
= NULL
;
188 num_good_first_bytes
= 0;
191 static void free_nonce_list(noncelistentry_t
*p
)
196 free_nonce_list(p
->next
);
201 static void free_nonces_memory(void)
203 for (uint16_t i
= 0; i
< 256; i
++) {
204 free_nonce_list(nonces
[i
].first
);
208 static uint16_t PartialSumProperty(uint32_t state
, odd_even_t odd_even
)
211 for (uint16_t j
= 0; j
< 16; j
++) {
213 uint16_t part_sum
= 0;
214 if (odd_even
== ODD_STATE
) {
215 for (uint16_t i
= 0; i
< 5; i
++) {
216 part_sum
^= filter(st
);
217 st
= (st
<< 1) | ((j
>> (3-i
)) & 0x01) ;
219 part_sum
^= 1; // XOR 1 cancelled out for the other 8 bits
221 for (uint16_t i
= 0; i
< 4; i
++) {
222 st
= (st
<< 1) | ((j
>> (3-i
)) & 0x01) ;
223 part_sum
^= filter(st
);
231 // static uint16_t SumProperty(struct Crypto1State *s)
233 // uint16_t sum_odd = PartialSumProperty(s->odd, ODD_STATE);
234 // uint16_t sum_even = PartialSumProperty(s->even, EVEN_STATE);
235 // return (sum_odd*(16-sum_even) + (16-sum_odd)*sum_even);
238 static double p_hypergeometric(uint16_t N
, uint16_t K
, uint16_t n
, uint16_t k
)
240 // for efficient computation we are using the recursive definition
242 // P(X=k) = P(X=k-1) * --------------------
245 // (N-K)*(N-K-1)*...*(N-K-n+1)
246 // P(X=0) = -----------------------------
247 // N*(N-1)*...*(N-n+1)
249 if (n
-k
> N
-K
|| k
> K
) return 0.0; // avoids log(x<=0) in calculation below
251 // use logarithms to avoid overflow with huge factorials (double type can only hold 170!)
252 double log_result
= 0.0;
253 for (int16_t i
= N
-K
; i
>= N
-K
-n
+1; i
--) {
254 log_result
+= log(i
);
256 for (int16_t i
= N
; i
>= N
-n
+1; i
--) {
257 log_result
-= log(i
);
259 return exp(log_result
);
261 if (n
-k
== N
-K
) { // special case. The published recursion below would fail with a divide by zero exception
262 double log_result
= 0.0;
263 for (int16_t i
= k
+1; i
<= n
; i
++) {
264 log_result
+= log(i
);
266 for (int16_t i
= K
+1; i
<= N
; i
++) {
267 log_result
-= log(i
);
269 return exp(log_result
);
270 } else { // recursion
271 return (p_hypergeometric(N
, K
, n
, k
-1) * (K
-k
+1) * (n
-k
+1) / (k
* (N
-K
-n
+k
)));
276 static float sum_probability(uint16_t K
, uint16_t n
, uint16_t k
)
278 const uint16_t N
= 256;
280 if (k
> K
|| p_K
[K
] == 0.0) return 0.0;
282 double p_T_is_k_when_S_is_K
= p_hypergeometric(N
, K
, n
, k
);
283 double p_S_is_K
= p_K
[K
];
285 for (uint16_t i
= 0; i
<= 256; i
++) {
287 double tmp
= p_hypergeometric(N
, i
, n
, k
);
289 p_T_is_k
+= p_K
[i
] * tmp
;
292 return(p_T_is_k_when_S_is_K
* p_S_is_K
/ p_T_is_k
);
296 static inline uint_fast8_t common_bits(uint_fast8_t bytes_diff
)
298 static const uint_fast8_t common_bits_LUT
[256] = {
299 8, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
300 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
301 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
302 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
303 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
304 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
305 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
306 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
307 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
308 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
309 5, 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 6, 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 5, 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
317 return common_bits_LUT
[bytes_diff
];
322 // printf("Tests: Partial Statelist sizes\n");
323 // for (uint16_t i = 0; i <= 16; i+=2) {
324 // printf("Partial State List Odd [%2d] has %8d entries\n", i, partial_statelist[i].len[ODD_STATE]);
326 // for (uint16_t i = 0; i <= 16; i+=2) {
327 // printf("Partial State List Even [%2d] has %8d entries\n", i, partial_statelist[i].len[EVEN_STATE]);
330 // #define NUM_STATISTICS 100000
331 // uint32_t statistics_odd[17];
332 // uint64_t statistics[257];
333 // uint32_t statistics_even[17];
334 // struct Crypto1State cs;
335 // time_t time1 = clock();
337 // for (uint16_t i = 0; i < 257; i++) {
338 // statistics[i] = 0;
340 // for (uint16_t i = 0; i < 17; i++) {
341 // statistics_odd[i] = 0;
342 // statistics_even[i] = 0;
345 // for (uint64_t i = 0; i < NUM_STATISTICS; i++) {
346 // cs.odd = (rand() & 0xfff) << 12 | (rand() & 0xfff);
347 // cs.even = (rand() & 0xfff) << 12 | (rand() & 0xfff);
348 // uint16_t sum_property = SumProperty(&cs);
349 // statistics[sum_property] += 1;
350 // sum_property = PartialSumProperty(cs.even, EVEN_STATE);
351 // statistics_even[sum_property]++;
352 // sum_property = PartialSumProperty(cs.odd, ODD_STATE);
353 // statistics_odd[sum_property]++;
354 // if (i%(NUM_STATISTICS/100) == 0) printf(".");
357 // 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);
358 // for (uint16_t i = 0; i < 257; i++) {
359 // if (statistics[i] != 0) {
360 // printf("probability[%3d] = %0.5f\n", i, (float)statistics[i]/NUM_STATISTICS);
363 // for (uint16_t i = 0; i <= 16; i++) {
364 // if (statistics_odd[i] != 0) {
365 // printf("probability odd [%2d] = %0.5f\n", i, (float)statistics_odd[i]/NUM_STATISTICS);
368 // for (uint16_t i = 0; i <= 16; i++) {
369 // if (statistics_odd[i] != 0) {
370 // printf("probability even [%2d] = %0.5f\n", i, (float)statistics_even[i]/NUM_STATISTICS);
374 // printf("Tests: Sum Probabilities based on Partial Sums\n");
375 // for (uint16_t i = 0; i < 257; i++) {
376 // statistics[i] = 0;
378 // uint64_t num_states = 0;
379 // for (uint16_t oddsum = 0; oddsum <= 16; oddsum += 2) {
380 // for (uint16_t evensum = 0; evensum <= 16; evensum += 2) {
381 // uint16_t sum = oddsum*(16-evensum) + (16-oddsum)*evensum;
382 // statistics[sum] += (uint64_t)partial_statelist[oddsum].len[ODD_STATE] * partial_statelist[evensum].len[EVEN_STATE] * (1<<8);
383 // num_states += (uint64_t)partial_statelist[oddsum].len[ODD_STATE] * partial_statelist[evensum].len[EVEN_STATE] * (1<<8);
386 // printf("num_states = %lld, expected %lld\n", num_states, (1LL<<48));
387 // for (uint16_t i = 0; i < 257; i++) {
388 // if (statistics[i] != 0) {
389 // printf("probability[%3d] = %0.5f\n", i, (float)statistics[i]/num_states);
393 // printf("\nTests: Hypergeometric Probability for selected parameters\n");
394 // printf("p_hypergeometric(256, 206, 255, 206) = %0.8f\n", p_hypergeometric(256, 206, 255, 206));
395 // printf("p_hypergeometric(256, 206, 255, 205) = %0.8f\n", p_hypergeometric(256, 206, 255, 205));
396 // printf("p_hypergeometric(256, 156, 1, 1) = %0.8f\n", p_hypergeometric(256, 156, 1, 1));
397 // printf("p_hypergeometric(256, 156, 1, 0) = %0.8f\n", p_hypergeometric(256, 156, 1, 0));
398 // printf("p_hypergeometric(256, 1, 1, 1) = %0.8f\n", p_hypergeometric(256, 1, 1, 1));
399 // printf("p_hypergeometric(256, 1, 1, 0) = %0.8f\n", p_hypergeometric(256, 1, 1, 0));
401 // struct Crypto1State *pcs;
402 // pcs = crypto1_create(0xffffffffffff);
403 // printf("\nTests: for key = 0xffffffffffff:\nSum(a0) = %d\nodd_state = 0x%06x\neven_state = 0x%06x\n",
404 // SumProperty(pcs), pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff);
405 // crypto1_byte(pcs, (cuid >> 24) ^ best_first_bytes[0], true);
406 // printf("After adding best first byte 0x%02x:\nSum(a8) = %d\nodd_state = 0x%06x\neven_state = 0x%06x\n",
407 // best_first_bytes[0],
409 // pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff);
410 // //test_state_odd = pcs->odd & 0x00ffffff;
411 // //test_state_even = pcs->even & 0x00ffffff;
412 // crypto1_destroy(pcs);
413 // pcs = crypto1_create(0xa0a1a2a3a4a5);
414 // printf("Tests: for key = 0xa0a1a2a3a4a5:\nSum(a0) = %d\nodd_state = 0x%06x\neven_state = 0x%06x\n",
415 // SumProperty(pcs), pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff);
416 // crypto1_byte(pcs, (cuid >> 24) ^ best_first_bytes[0], true);
417 // printf("After adding best first byte 0x%02x:\nSum(a8) = %d\nodd_state = 0x%06x\neven_state = 0x%06x\n",
418 // best_first_bytes[0],
420 // pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff);
421 // //test_state_odd = pcs->odd & 0x00ffffff;
422 // //test_state_even = pcs->even & 0x00ffffff;
423 // crypto1_destroy(pcs);
424 // pcs = crypto1_create(0xa6b9aa97b955);
425 // printf("Tests: for key = 0xa6b9aa97b955:\nSum(a0) = %d\nodd_state = 0x%06x\neven_state = 0x%06x\n",
426 // SumProperty(pcs), pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff);
427 // crypto1_byte(pcs, (cuid >> 24) ^ best_first_bytes[0], true);
428 // printf("After adding best first byte 0x%02x:\nSum(a8) = %d\nodd_state = 0x%06x\neven_state = 0x%06x\n",
429 // best_first_bytes[0],
431 // pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff);
432 //test_state_odd = pcs->odd & 0x00ffffff;
433 //test_state_even = pcs->even & 0x00ffffff;
434 // crypto1_destroy(pcs);
437 // 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));
439 // printf("\nTests: Actual BitFlipProperties odd/even:\n");
440 // for (uint16_t i = 0; i < 256; i++) {
441 // printf("[%02x]:%c ", i, nonces[i].BitFlip[ODD_STATE]?'o':nonces[i].BitFlip[EVEN_STATE]?'e':' ');
447 // printf("\nTests: Sorted First Bytes:\n");
448 // for (uint16_t i = 0; i < 256; i++) {
449 // uint8_t best_byte = best_first_bytes[i];
450 // printf("#%03d Byte: %02x, n = %3d, k = %3d, Sum(a8): %3d, Confidence: %5.1f%%, Bitflip: %c\n",
451 // //printf("#%03d Byte: %02x, n = %3d, k = %3d, Sum(a8): %3d, Confidence: %5.1f%%, Bitflip: %c, score1: %1.5f, score2: %1.0f\n",
453 // nonces[best_byte].num,
454 // nonces[best_byte].Sum,
455 // nonces[best_byte].Sum8_guess,
456 // nonces[best_byte].Sum8_prob * 100,
457 // nonces[best_byte].BitFlip[ODD_STATE]?'o':nonces[best_byte].BitFlip[EVEN_STATE]?'e':' '
458 // //nonces[best_byte].score1,
459 // //nonces[best_byte].score2
463 // printf("\nTests: parity performance\n");
464 // time_t time1p = clock();
465 // uint32_t par_sum = 0;
466 // for (uint32_t i = 0; i < 100000000; i++) {
467 // par_sum += parity(i);
469 // printf("parsum oldparity = %d, time = %1.5fsec\n", par_sum, (float)(clock() - time1p)/CLOCKS_PER_SEC);
473 // for (uint32_t i = 0; i < 100000000; i++) {
474 // par_sum += evenparity32(i);
476 // printf("parsum newparity = %d, time = %1.5fsec\n", par_sum, (float)(clock() - time1p)/CLOCKS_PER_SEC);
481 static void sort_best_first_bytes(void)
483 // sort based on probability for correct guess
484 for (uint16_t i
= 0; i
< 256; i
++ ) {
486 float prob1
= nonces
[i
].Sum8_prob
;
487 float prob2
= nonces
[best_first_bytes
[0]].Sum8_prob
;
488 while (prob1
< prob2
&& j
< i
) {
489 prob2
= nonces
[best_first_bytes
[++j
]].Sum8_prob
;
492 for (uint16_t k
= i
; k
> j
; k
--) {
493 best_first_bytes
[k
] = best_first_bytes
[k
-1];
496 best_first_bytes
[j
] = i
;
499 // determine how many are above the CONFIDENCE_THRESHOLD
500 uint16_t num_good_nonces
= 0;
501 for (uint16_t i
= 0; i
< 256; i
++) {
502 if (nonces
[best_first_bytes
[i
]].Sum8_prob
>= CONFIDENCE_THRESHOLD
) {
507 uint16_t best_first_byte
= 0;
509 // select the best possible first byte based on number of common bits with all {b'}
510 // uint16_t max_common_bits = 0;
511 // for (uint16_t i = 0; i < num_good_nonces; i++) {
512 // uint16_t sum_common_bits = 0;
513 // for (uint16_t j = 0; j < num_good_nonces; j++) {
515 // sum_common_bits += common_bits(best_first_bytes[i],best_first_bytes[j]);
518 // if (sum_common_bits > max_common_bits) {
519 // max_common_bits = sum_common_bits;
520 // best_first_byte = i;
524 // select best possible first byte {b} based on least likely sum/bitflip property
526 for (uint16_t i
= 0; i
< num_good_nonces
; i
++ ) {
527 uint16_t sum8
= nonces
[best_first_bytes
[i
]].Sum8_guess
;
528 float bitflip_prob
= 1.0;
529 if (nonces
[best_first_bytes
[i
]].BitFlip
[ODD_STATE
] || nonces
[best_first_bytes
[i
]].BitFlip
[EVEN_STATE
]) {
530 bitflip_prob
= 0.09375;
532 nonces
[best_first_bytes
[i
]].score1
= p_K
[sum8
] * bitflip_prob
;
533 if (p_K
[sum8
] * bitflip_prob
<= min_p_K
) {
534 min_p_K
= p_K
[sum8
] * bitflip_prob
;
539 // use number of commmon bits as a tie breaker
540 uint16_t max_common_bits
= 0;
541 for (uint16_t i
= 0; i
< num_good_nonces
; i
++) {
542 float bitflip_prob
= 1.0;
543 if (nonces
[best_first_bytes
[i
]].BitFlip
[ODD_STATE
] || nonces
[best_first_bytes
[i
]].BitFlip
[EVEN_STATE
]) {
544 bitflip_prob
= 0.09375;
546 if (p_K
[nonces
[best_first_bytes
[i
]].Sum8_guess
] * bitflip_prob
== min_p_K
) {
547 uint16_t sum_common_bits
= 0;
548 for (uint16_t j
= 0; j
< num_good_nonces
; j
++) {
549 sum_common_bits
+= common_bits(best_first_bytes
[i
] ^ best_first_bytes
[j
]);
551 nonces
[best_first_bytes
[i
]].score2
= sum_common_bits
;
552 if (sum_common_bits
> max_common_bits
) {
553 max_common_bits
= sum_common_bits
;
559 // swap best possible first byte to the pole position
560 if (best_first_byte
!= 0) {
561 uint16_t temp
= best_first_bytes
[0];
562 best_first_bytes
[0] = best_first_bytes
[best_first_byte
];
563 best_first_bytes
[best_first_byte
] = temp
;
568 static uint16_t estimate_second_byte_sum(void)
571 for (uint16_t first_byte
= 0; first_byte
< 256; first_byte
++) {
572 float Sum8_prob
= 0.0;
574 if (nonces
[first_byte
].updated
) {
575 for (uint16_t sum
= 0; sum
<= 256; sum
++) {
576 float prob
= sum_probability(sum
, nonces
[first_byte
].num
, nonces
[first_byte
].Sum
);
577 if (prob
> Sum8_prob
) {
582 nonces
[first_byte
].Sum8_guess
= Sum8
;
583 nonces
[first_byte
].Sum8_prob
= Sum8_prob
;
584 nonces
[first_byte
].updated
= false;
588 sort_best_first_bytes();
590 uint16_t num_good_nonces
= 0;
591 for (uint16_t i
= 0; i
< 256; i
++) {
592 if (nonces
[best_first_bytes
[i
]].Sum8_prob
>= CONFIDENCE_THRESHOLD
) {
597 return num_good_nonces
;
600 static int read_nonce_file(void)
602 FILE *fnonces
= NULL
;
603 uint8_t trgBlockNo
= 0;
604 uint8_t trgKeyType
= 0;
606 uint32_t nt_enc1
= 0, nt_enc2
= 0;
608 int total_num_nonces
= 0;
610 if ((fnonces
= fopen("nonces.bin","rb")) == NULL
) {
611 PrintAndLog("Could not open file nonces.bin");
615 PrintAndLog("Reading nonces from file nonces.bin...");
616 size_t bytes_read
= fread(read_buf
, 1, 6, fnonces
);
617 if ( bytes_read
== 0) {
618 PrintAndLog("File reading error.");
622 cuid
= bytes_to_num(read_buf
, 4);
623 trgBlockNo
= bytes_to_num(read_buf
+4, 1);
624 trgKeyType
= bytes_to_num(read_buf
+5, 1);
626 while (fread(read_buf
, 1, 9, fnonces
) == 9) {
627 nt_enc1
= bytes_to_num(read_buf
, 4);
628 nt_enc2
= bytes_to_num(read_buf
+4, 4);
629 par_enc
= bytes_to_num(read_buf
+8, 1);
630 //printf("Encrypted nonce: %08x, encrypted_parity: %02x\n", nt_enc1, par_enc >> 4);
631 //printf("Encrypted nonce: %08x, encrypted_parity: %02x\n", nt_enc2, par_enc & 0x0f);
632 add_nonce(nt_enc1
, par_enc
>> 4);
633 add_nonce(nt_enc2
, par_enc
& 0x0f);
634 total_num_nonces
+= 2;
637 PrintAndLog("Read %d nonces from file. cuid=%08x, Block=%d, Keytype=%c", total_num_nonces
, cuid
, trgBlockNo
, trgKeyType
==0?'A':'B');
641 static void Check_for_FilterFlipProperties(void)
643 printf("Checking for Filter Flip Properties...\n");
645 uint16_t num_bitflips
= 0;
647 for (uint16_t i
= 0; i
< 256; i
++) {
648 nonces
[i
].BitFlip
[ODD_STATE
] = false;
649 nonces
[i
].BitFlip
[EVEN_STATE
] = false;
652 for (uint16_t i
= 0; i
< 256; i
++) {
653 uint8_t parity1
= (nonces
[i
].first
->par_enc
) >> 3; // parity of first byte
654 uint8_t parity2_odd
= (nonces
[i
^0x80].first
->par_enc
) >> 3; // XOR 0x80 = last bit flipped
655 uint8_t parity2_even
= (nonces
[i
^0x40].first
->par_enc
) >> 3; // XOR 0x40 = second last bit flipped
657 if (parity1
== parity2_odd
) { // has Bit Flip Property for odd bits
658 nonces
[i
].BitFlip
[ODD_STATE
] = true;
660 } else if (parity1
== parity2_even
) { // has Bit Flip Property for even bits
661 nonces
[i
].BitFlip
[EVEN_STATE
] = true;
667 fprintf(fstats
, "%d;", num_bitflips
);
671 static void simulate_MFplus_RNG(uint32_t test_cuid
, uint64_t test_key
, uint32_t *nt_enc
, uint8_t *par_enc
)
673 struct Crypto1State sim_cs
= {0, 0};
674 // init cryptostate with key:
675 for(int8_t i
= 47; i
> 0; i
-= 2) {
676 sim_cs
.odd
= sim_cs
.odd
<< 1 | BIT(test_key
, (i
- 1) ^ 7);
677 sim_cs
.even
= sim_cs
.even
<< 1 | BIT(test_key
, i
^ 7);
681 uint32_t nt
= (rand() & 0xff) << 24 | (rand() & 0xff) << 16 | (rand() & 0xff) << 8 | (rand() & 0xff);
682 for (int8_t byte_pos
= 3; byte_pos
>= 0; byte_pos
--) {
683 uint8_t nt_byte_dec
= (nt
>> (8*byte_pos
)) & 0xff;
684 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
685 *nt_enc
= (*nt_enc
<< 8) | nt_byte_enc
;
686 uint8_t ks_par
= filter(sim_cs
.odd
); // the keystream bit to encode/decode the parity bit
687 uint8_t nt_byte_par_enc
= ks_par
^ oddparity8(nt_byte_dec
); // determine the nt byte's parity and encode it
688 *par_enc
= (*par_enc
<< 1) | nt_byte_par_enc
;
693 static void simulate_acquire_nonces()
695 clock_t time1
= clock();
696 bool filter_flip_checked
= false;
697 uint32_t total_num_nonces
= 0;
698 uint32_t next_fivehundred
= 500;
699 uint32_t total_added_nonces
= 0;
701 cuid
= (rand() & 0xff) << 24 | (rand() & 0xff) << 16 | (rand() & 0xff) << 8 | (rand() & 0xff);
702 known_target_key
= ((uint64_t)rand() & 0xfff) << 36 | ((uint64_t)rand() & 0xfff) << 24 | ((uint64_t)rand() & 0xfff) << 12 | ((uint64_t)rand() & 0xfff);
704 printf("Simulating nonce acquisition for target key %012"llx
", cuid %08x ...\n", known_target_key
, cuid
);
705 fprintf(fstats
, "%012"llx
";%08x;", known_target_key
, cuid
);
711 simulate_MFplus_RNG(cuid
, known_target_key
, &nt_enc
, &par_enc
);
712 //printf("Simulated RNG: nt_enc1: %08x, nt_enc2: %08x, par_enc: %02x\n", nt_enc1, nt_enc2, par_enc);
713 total_added_nonces
+= add_nonce(nt_enc
, par_enc
);
716 if (first_byte_num
== 256 ) {
717 // printf("first_byte_num = %d, first_byte_Sum = %d\n", first_byte_num, first_byte_Sum);
718 if (!filter_flip_checked
) {
719 Check_for_FilterFlipProperties();
720 filter_flip_checked
= true;
722 num_good_first_bytes
= estimate_second_byte_sum();
723 if (total_num_nonces
> next_fivehundred
) {
724 next_fivehundred
= (total_num_nonces
/500+1) * 500;
725 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",
728 CONFIDENCE_THRESHOLD
* 100.0,
729 num_good_first_bytes
);
733 } while (num_good_first_bytes
< GOOD_BYTES_REQUIRED
);
735 time1
= clock() - time1
;
737 PrintAndLog("Acquired a total of %d nonces in %1.1f seconds (%0.0f nonces/minute)",
739 ((float)time1
)/CLOCKS_PER_SEC
,
740 total_num_nonces
* 60.0 * CLOCKS_PER_SEC
/(float)time1
);
742 fprintf(fstats
, "%d;%d;%d;%1.2f;", total_num_nonces
, total_added_nonces
, num_good_first_bytes
, CONFIDENCE_THRESHOLD
);
746 static int acquire_nonces(uint8_t blockNo
, uint8_t keyType
, uint8_t *key
, uint8_t trgBlockNo
, uint8_t trgKeyType
, bool nonce_file_write
, bool slow
)
748 clock_t time1
= clock();
749 bool initialize
= true;
750 bool finished
= false;
751 bool filter_flip_checked
= false;
753 uint8_t write_buf
[9];
754 uint32_t total_num_nonces
= 0;
755 uint32_t next_fivehundred
= 500;
756 uint32_t total_added_nonces
= 0;
758 FILE *fnonces
= NULL
;
763 printf("Acquiring nonces...\n");
767 flags
|= initialize
? 0x0001 : 0;
768 flags
|= slow
? 0x0002 : 0;
769 flags
|= field_off
? 0x0004 : 0;
770 UsbCommand c
= {CMD_MIFARE_ACQUIRE_ENCRYPTED_NONCES
, {blockNo
+ keyType
* 0x100, trgBlockNo
+ trgKeyType
* 0x100, flags
}};
771 memcpy(c
.d
.asBytes
, key
, 6);
773 clearCommandBuffer();
776 if (field_off
) break;
779 if (!WaitForResponseTimeout(CMD_ACK
, &resp
, 3000)) return 1;
780 if (resp
.arg
[0]) return resp
.arg
[0]; // error during nested_hard
783 // PrintAndLog("Acquiring nonces for CUID 0x%08x", cuid);
784 if (nonce_file_write
&& fnonces
== NULL
) {
785 if ((fnonces
= fopen("nonces.bin","wb")) == NULL
) {
786 PrintAndLog("Could not create file nonces.bin");
789 PrintAndLog("Writing acquired nonces to binary file nonces.bin");
790 num_to_bytes(cuid
, 4, write_buf
);
791 fwrite(write_buf
, 1, 4, fnonces
);
792 fwrite(&trgBlockNo
, 1, 1, fnonces
);
793 fwrite(&trgKeyType
, 1, 1, fnonces
);
799 uint32_t nt_enc1
, nt_enc2
;
801 uint16_t num_acquired_nonces
= resp
.arg
[2];
802 uint8_t *bufp
= resp
.d
.asBytes
;
803 for (uint16_t i
= 0; i
< num_acquired_nonces
; i
+=2) {
804 nt_enc1
= bytes_to_num(bufp
, 4);
805 nt_enc2
= bytes_to_num(bufp
+4, 4);
806 par_enc
= bytes_to_num(bufp
+8, 1);
808 //printf("Encrypted nonce: %08x, encrypted_parity: %02x\n", nt_enc1, par_enc >> 4);
809 total_added_nonces
+= add_nonce(nt_enc1
, par_enc
>> 4);
810 //printf("Encrypted nonce: %08x, encrypted_parity: %02x\n", nt_enc2, par_enc & 0x0f);
811 total_added_nonces
+= add_nonce(nt_enc2
, par_enc
& 0x0f);
813 if (nonce_file_write
&& fnonces
) {
814 fwrite(bufp
, 1, 9, fnonces
);
821 total_num_nonces
+= num_acquired_nonces
;
824 if (first_byte_num
== 256 && !field_off
) {
825 // printf("first_byte_num = %d, first_byte_Sum = %d\n", first_byte_num, first_byte_Sum);
826 if (!filter_flip_checked
) {
827 Check_for_FilterFlipProperties();
828 filter_flip_checked
= true;
831 num_good_first_bytes
= estimate_second_byte_sum();
832 if (total_num_nonces
> next_fivehundred
) {
833 next_fivehundred
= (total_num_nonces
/500+1) * 500;
834 printf("Acquired %5d nonces (%5d / %5d with distinct bytes 0 and 1). Number of bytes with probability for correctly guessed Sum(a8) > %1.1f%%: %d\n",
837 NONCES_THRESHOLD
* idx
,
838 CONFIDENCE_THRESHOLD
* 100.0,
839 num_good_first_bytes
);
842 if (total_added_nonces
>= (NONCES_THRESHOLD
* idx
))
844 num_good_first_bytes
= estimate_second_byte_sum();
845 clock_t time1
= clock();
846 bool cracking
= generate_candidates(first_byte_Sum
, nonces
[best_first_bytes
[0]].Sum8_guess
);
847 time1
= clock() - time1
;
848 if (time1
> 0) PrintAndLog("Time for generating key candidates list: %1.0f seconds", ((float)time1
)/CLOCKS_PER_SEC
);
850 if (cracking
|| known_target_key
!= -1) {
851 field_off
= brute_force(); // switch off field with next SendCommand and then finish
859 if (!WaitForResponseTimeout(CMD_ACK
, &resp
, 3000)) {
860 if (fnonces
) fclose(fnonces
);
865 if (fnonces
) fclose(fnonces
);
866 return resp
.arg
[0]; // error during nested_hard
874 if (nonce_file_write
&& fnonces
)
877 time1
= clock() - time1
;
879 PrintAndLog("Acquired a total of %d nonces in %1.1f seconds (%0.0f nonces/minute)",
881 ((float)time1
)/CLOCKS_PER_SEC
,
882 total_num_nonces
* 60.0 * CLOCKS_PER_SEC
/(float)time1
888 static int init_partial_statelists(void)
890 const uint32_t sizes_odd
[17] = { 126757, 0, 18387, 0, 74241, 0, 181737, 0, 248801, 0, 182033, 0, 73421, 0, 17607, 0, 125601 };
891 // const uint32_t sizes_even[17] = { 125723, 0, 17867, 0, 74305, 0, 178707, 0, 248801, 0, 185063, 0, 73356, 0, 18127, 0, 126634 };
892 const uint32_t sizes_even
[17] = { 125723, 0, 17867, 0, 74305, 0, 178707, 0, 248801, 0, 185063, 0, 73357, 0, 18127, 0, 126635 };
894 printf("Allocating memory for partial statelists...\n");
895 for (odd_even_t odd_even
= EVEN_STATE
; odd_even
<= ODD_STATE
; odd_even
++) {
896 for (uint16_t i
= 0; i
<= 16; i
+=2) {
897 partial_statelist
[i
].len
[odd_even
] = 0;
898 uint32_t num_of_states
= odd_even
== ODD_STATE
? sizes_odd
[i
] : sizes_even
[i
];
899 partial_statelist
[i
].states
[odd_even
] = malloc(sizeof(uint32_t) * num_of_states
);
900 if (partial_statelist
[i
].states
[odd_even
] == NULL
) {
901 PrintAndLog("Cannot allocate enough memory. Aborting");
904 for (uint32_t j
= 0; j
< STATELIST_INDEX_SIZE
; j
++) {
905 partial_statelist
[i
].index
[odd_even
][j
] = NULL
;
910 printf("Generating partial statelists...\n");
911 for (odd_even_t odd_even
= EVEN_STATE
; odd_even
<= ODD_STATE
; odd_even
++) {
913 uint32_t num_of_states
= 1<<20;
914 for (uint32_t state
= 0; state
< num_of_states
; state
++) {
915 uint16_t sum_property
= PartialSumProperty(state
, odd_even
);
916 uint32_t *p
= partial_statelist
[sum_property
].states
[odd_even
];
917 p
+= partial_statelist
[sum_property
].len
[odd_even
];
919 partial_statelist
[sum_property
].len
[odd_even
]++;
920 uint32_t index_mask
= (STATELIST_INDEX_SIZE
-1) << (20-STATELIST_INDEX_WIDTH
);
921 if ((state
& index_mask
) != index
) {
922 index
= state
& index_mask
;
924 if (partial_statelist
[sum_property
].index
[odd_even
][index
>> (20-STATELIST_INDEX_WIDTH
)] == NULL
) {
925 partial_statelist
[sum_property
].index
[odd_even
][index
>> (20-STATELIST_INDEX_WIDTH
)] = p
;
928 // add End Of List markers
929 for (uint16_t i
= 0; i
<= 16; i
+= 2) {
930 uint32_t *p
= partial_statelist
[i
].states
[odd_even
];
931 p
+= partial_statelist
[i
].len
[odd_even
];
932 *p
= END_OF_LIST_MARKER
;
939 static void init_BitFlip_statelist(void)
941 printf("Generating bitflip statelist...\n");
942 uint32_t *p
= statelist_bitflip
.states
[0] = malloc(sizeof(uint32_t) * 1<<20);
944 uint32_t index_mask
= (STATELIST_INDEX_SIZE
-1) << (20-STATELIST_INDEX_WIDTH
);
945 for (uint32_t state
= 0; state
< (1 << 20); state
++) {
946 if (filter(state
) != filter(state
^1)) {
947 if ((state
& index_mask
) != index
) {
948 index
= state
& index_mask
;
950 if (statelist_bitflip
.index
[0][index
>> (20-STATELIST_INDEX_WIDTH
)] == NULL
) {
951 statelist_bitflip
.index
[0][index
>> (20-STATELIST_INDEX_WIDTH
)] = p
;
956 // set len and add End Of List marker
957 statelist_bitflip
.len
[0] = p
- statelist_bitflip
.states
[0];
958 *p
= END_OF_LIST_MARKER
;
959 statelist_bitflip
.states
[0] = realloc(statelist_bitflip
.states
[0], sizeof(uint32_t) * (statelist_bitflip
.len
[0] + 1));
962 static inline uint32_t *find_first_state(uint32_t state
, uint32_t mask
, partial_indexed_statelist_t
*sl
, odd_even_t odd_even
)
964 uint32_t *p
= sl
->index
[odd_even
][(state
& mask
) >> (20-STATELIST_INDEX_WIDTH
)]; // first Bits as index
966 if (p
== NULL
) return NULL
;
967 while (*p
< (state
& mask
)) p
++;
968 if (*p
== END_OF_LIST_MARKER
) return NULL
; // reached end of list, no match
969 if ((*p
& mask
) == (state
& mask
)) return p
; // found a match.
970 return NULL
; // no match
973 static 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
)
975 uint_fast8_t j_1_bit_mask
= 0x01 << (bit
-1);
976 uint_fast8_t bit_diff
= byte_diff
& j_1_bit_mask
; // difference of (j-1)th bit
977 uint_fast8_t filter_diff
= filter(state1
>> (4-state_bit
)) ^ filter(state2
>> (4-state_bit
)); // difference in filter function
978 uint_fast8_t mask_y12_y13
= 0xc0 >> state_bit
;
979 uint_fast8_t state_bits_diff
= (state1
^ state2
) & mask_y12_y13
; // difference in state bits 12 and 13
980 uint_fast8_t all_diff
= evenparity8(bit_diff
^ state_bits_diff
^ filter_diff
); // use parity function to XOR all bits
984 static 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
)
986 uint_fast8_t j_bit_mask
= 0x01 << bit
;
987 uint_fast8_t bit_diff
= byte_diff
& j_bit_mask
; // difference of jth bit
988 uint_fast8_t mask_y13_y16
= 0x48 >> state_bit
;
989 uint_fast8_t state_bits_diff
= (state1
^ state2
) & mask_y13_y16
; // difference in state bits 13 and 16
990 uint_fast8_t all_diff
= evenparity8(bit_diff
^ state_bits_diff
); // use parity function to XOR all bits
994 static 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
)
998 switch (num_common_bits
) {
999 case 0: if (!invariant_holds(byte_diff
, state1
, state2
, 1, 0)) return true;
1000 case 1: if (invalid_state(byte_diff
, state1
, state2
, 1, 0)) return false;
1001 case 2: if (!invariant_holds(byte_diff
, state1
, state2
, 3, 1)) return true;
1002 case 3: if (invalid_state(byte_diff
, state1
, state2
, 3, 1)) return false;
1003 case 4: if (!invariant_holds(byte_diff
, state1
, state2
, 5, 2)) return true;
1004 case 5: if (invalid_state(byte_diff
, state1
, state2
, 5, 2)) return false;
1005 case 6: if (!invariant_holds(byte_diff
, state1
, state2
, 7, 3)) return true;
1006 case 7: if (invalid_state(byte_diff
, state1
, state2
, 7, 3)) return false;
1010 switch (num_common_bits
) {
1011 case 0: if (invalid_state(byte_diff
, state1
, state2
, 0, 0)) return false;
1012 case 1: if (!invariant_holds(byte_diff
, state1
, state2
, 2, 1)) return true;
1013 case 2: if (invalid_state(byte_diff
, state1
, state2
, 2, 1)) return false;
1014 case 3: if (!invariant_holds(byte_diff
, state1
, state2
, 4, 2)) return true;
1015 case 4: if (invalid_state(byte_diff
, state1
, state2
, 4, 2)) return false;
1016 case 5: if (!invariant_holds(byte_diff
, state1
, state2
, 6, 3)) return true;
1017 case 6: if (invalid_state(byte_diff
, state1
, state2
, 6, 3)) return false;
1021 return true; // valid state
1024 static bool all_other_first_bytes_match(uint32_t state
, odd_even_t odd_even
)
1026 for (uint16_t i
= 1; i
< num_good_first_bytes
; i
++) {
1027 uint16_t sum_a8
= nonces
[best_first_bytes
[i
]].Sum8_guess
;
1028 uint_fast8_t bytes_diff
= best_first_bytes
[0] ^ best_first_bytes
[i
];
1029 uint_fast8_t j
= common_bits(bytes_diff
);
1030 uint32_t mask
= 0xfffffff0;
1031 if (odd_even
== ODD_STATE
) {
1037 //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);
1038 bool found_match
= false;
1039 for (uint16_t r
= 0; r
<= 16 && !found_match
; r
+= 2) {
1040 for (uint16_t s
= 0; s
<= 16 && !found_match
; s
+= 2) {
1041 if (r
*(16-s
) + (16-r
)*s
== sum_a8
) {
1042 //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);
1043 uint16_t part_sum_a8
= (odd_even
== ODD_STATE
) ? r
: s
;
1044 uint32_t *p
= find_first_state(state
, mask
, &partial_statelist
[part_sum_a8
], odd_even
);
1046 while ((state
& mask
) == (*p
& mask
) && (*p
!= END_OF_LIST_MARKER
)) {
1047 if (remaining_bits_match(j
, bytes_diff
, state
, (state
&0x00fffff0) | *p
, odd_even
)) {
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 matched. 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);
1056 // if ((odd_even == ODD_STATE && state == test_state_odd)
1057 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1058 // 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",
1059 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1065 // if ((odd_even == ODD_STATE && state == test_state_odd)
1066 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1067 // 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",
1068 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1076 // if ((odd_even == ODD_STATE && state == test_state_odd)
1077 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1078 // 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);
1087 static bool all_bit_flips_match(uint32_t state
, odd_even_t odd_even
)
1089 for (uint16_t i
= 0; i
< 256; i
++) {
1090 if (nonces
[i
].BitFlip
[odd_even
] && i
!= best_first_bytes
[0]) {
1091 uint_fast8_t bytes_diff
= best_first_bytes
[0] ^ i
;
1092 uint_fast8_t j
= common_bits(bytes_diff
);
1093 uint32_t mask
= 0xfffffff0;
1094 if (odd_even
== ODD_STATE
) {
1100 //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);
1101 bool found_match
= false;
1102 uint32_t *p
= find_first_state(state
, mask
, &statelist_bitflip
, 0);
1104 while ((state
& mask
) == (*p
& mask
) && (*p
!= END_OF_LIST_MARKER
)) {
1105 if (remaining_bits_match(j
, bytes_diff
, state
, (state
&0x00fffff0) | *p
, odd_even
)) {
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 matched. 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);
1114 // if ((odd_even == ODD_STATE && state == test_state_odd)
1115 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1116 // 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",
1117 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
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: couldn't find a matching state. Bytes = %02x, %02x, Common Bits=%d, mask=0x%08x, PartSum(a8)=%d\n",
1126 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1130 // if ((odd_even == ODD_STATE && state == test_state_odd)
1131 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1132 // 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);
1143 static struct sl_cache_entry
{
1146 } sl_cache
[17][17][2];
1148 static void init_statelist_cache(void)
1150 for (uint16_t i
= 0; i
< 17; i
+=2) {
1151 for (uint16_t j
= 0; j
< 17; j
+=2) {
1152 for (uint16_t k
= 0; k
< 2; k
++) {
1153 sl_cache
[i
][j
][k
].sl
= NULL
;
1154 sl_cache
[i
][j
][k
].len
= 0;
1160 static int add_matching_states(statelist_t
*candidates
, uint16_t part_sum_a0
, uint16_t part_sum_a8
, odd_even_t odd_even
)
1162 uint32_t worstcase_size
= 1<<20;
1164 // check cache for existing results
1165 if (sl_cache
[part_sum_a0
][part_sum_a8
][odd_even
].sl
!= NULL
) {
1166 candidates
->states
[odd_even
] = sl_cache
[part_sum_a0
][part_sum_a8
][odd_even
].sl
;
1167 candidates
->len
[odd_even
] = sl_cache
[part_sum_a0
][part_sum_a8
][odd_even
].len
;
1171 candidates
->states
[odd_even
] = (uint32_t *)malloc(sizeof(uint32_t) * worstcase_size
);
1172 if (candidates
->states
[odd_even
] == NULL
) {
1173 PrintAndLog("Out of memory error.\n");
1176 uint32_t *add_p
= candidates
->states
[odd_even
];
1177 for (uint32_t *p1
= partial_statelist
[part_sum_a0
].states
[odd_even
]; *p1
!= END_OF_LIST_MARKER
; p1
++) {
1178 uint32_t search_mask
= 0x000ffff0;
1179 uint32_t *p2
= find_first_state((*p1
<< 4), search_mask
, &partial_statelist
[part_sum_a8
], odd_even
);
1181 while (((*p1
<< 4) & search_mask
) == (*p2
& search_mask
) && *p2
!= END_OF_LIST_MARKER
) {
1182 if ((nonces
[best_first_bytes
[0]].BitFlip
[odd_even
] && find_first_state((*p1
<< 4) | *p2
, 0x000fffff, &statelist_bitflip
, 0))
1183 || !nonces
[best_first_bytes
[0]].BitFlip
[odd_even
]) {
1184 if (all_other_first_bytes_match((*p1
<< 4) | *p2
, odd_even
)) {
1185 if (all_bit_flips_match((*p1
<< 4) | *p2
, odd_even
)) {
1186 *add_p
++ = (*p1
<< 4) | *p2
;
1195 // set end of list marker and len
1196 *add_p
= END_OF_LIST_MARKER
;
1197 candidates
->len
[odd_even
] = add_p
- candidates
->states
[odd_even
];
1199 candidates
->states
[odd_even
] = realloc(candidates
->states
[odd_even
], sizeof(uint32_t) * (candidates
->len
[odd_even
] + 1));
1201 sl_cache
[part_sum_a0
][part_sum_a8
][odd_even
].sl
= candidates
->states
[odd_even
];
1202 sl_cache
[part_sum_a0
][part_sum_a8
][odd_even
].len
= candidates
->len
[odd_even
];
1207 static statelist_t
*add_more_candidates(statelist_t
*current_candidates
)
1209 statelist_t
*new_candidates
= NULL
;
1210 if (current_candidates
== NULL
) {
1211 if (candidates
== NULL
) {
1212 candidates
= (statelist_t
*)malloc(sizeof(statelist_t
));
1214 new_candidates
= candidates
;
1216 new_candidates
= current_candidates
->next
= (statelist_t
*)malloc(sizeof(statelist_t
));
1218 new_candidates
->next
= NULL
;
1219 new_candidates
->len
[ODD_STATE
] = 0;
1220 new_candidates
->len
[EVEN_STATE
] = 0;
1221 new_candidates
->states
[ODD_STATE
] = NULL
;
1222 new_candidates
->states
[EVEN_STATE
] = NULL
;
1223 return new_candidates
;
1226 static bool TestIfKeyExists(uint64_t key
)
1228 struct Crypto1State
*pcs
;
1229 pcs
= crypto1_create(key
);
1230 crypto1_byte(pcs
, (cuid
>> 24) ^ best_first_bytes
[0], true);
1232 uint32_t state_odd
= pcs
->odd
& 0x00ffffff;
1233 uint32_t state_even
= pcs
->even
& 0x00ffffff;
1234 //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);
1237 for (statelist_t
*p
= candidates
; p
!= NULL
; p
= p
->next
) {
1238 bool found_odd
= false;
1239 bool found_even
= false;
1240 uint32_t *p_odd
= p
->states
[ODD_STATE
];
1241 uint32_t *p_even
= p
->states
[EVEN_STATE
];
1242 while (*p_odd
!= END_OF_LIST_MARKER
) {
1243 if ((*p_odd
& 0x00ffffff) == state_odd
) {
1249 while (*p_even
!= END_OF_LIST_MARKER
) {
1250 if ((*p_even
& 0x00ffffff) == state_even
) {
1255 count
+= (p_odd
- p
->states
[ODD_STATE
]) * (p_even
- p
->states
[EVEN_STATE
]);
1256 if (found_odd
&& found_even
) {
1257 PrintAndLog("\nKey Found after testing %lld (2^%1.1f) out of %lld (2^%1.1f) keys. ",
1261 log(maximum_states
)/log(2)
1264 fprintf(fstats
, "1\n");
1266 crypto1_destroy(pcs
);
1271 printf("Key NOT found!\n");
1273 fprintf(fstats
, "0\n");
1275 crypto1_destroy(pcs
);
1280 static bool generate_candidates(uint16_t sum_a0
, uint16_t sum_a8
)
1282 printf("Generating crypto1 state candidates... \n");
1284 statelist_t
*current_candidates
= NULL
;
1285 // estimate maximum candidate states
1287 for (uint16_t sum_odd
= 0; sum_odd
<= 16; sum_odd
+= 2) {
1288 for (uint16_t sum_even
= 0; sum_even
<= 16; sum_even
+= 2) {
1289 if (sum_odd
*(16-sum_even
) + (16-sum_odd
)*sum_even
== sum_a0
) {
1290 maximum_states
+= (uint64_t)partial_statelist
[sum_odd
].len
[ODD_STATE
] * partial_statelist
[sum_even
].len
[EVEN_STATE
] * (1<<8);
1295 if (maximum_states
== 0) return false; // prevent keyspace reduction error (2^-inf)
1297 printf("Number of possible keys with Sum(a0) = %d: %"PRIu64
" (2^%1.1f)\n", sum_a0
, maximum_states
, log(maximum_states
)/log(2));
1299 init_statelist_cache();
1301 for (uint16_t p
= 0; p
<= 16; p
+= 2) {
1302 for (uint16_t q
= 0; q
<= 16; q
+= 2) {
1303 if (p
*(16-q
) + (16-p
)*q
== sum_a0
) {
1304 // printf("Reducing Partial Statelists (p,q) = (%d,%d) with lengths %d, %d\n",
1305 // p, q, partial_statelist[p].len[ODD_STATE], partial_statelist[q].len[EVEN_STATE]);
1306 for (uint16_t r
= 0; r
<= 16; r
+= 2) {
1307 for (uint16_t s
= 0; s
<= 16; s
+= 2) {
1308 if (r
*(16-s
) + (16-r
)*s
== sum_a8
) {
1309 current_candidates
= add_more_candidates(current_candidates
);
1310 if (current_candidates
) {
1311 // check for the smallest partial statelist. Try this first - it might give 0 candidates
1312 // and eliminate the need to calculate the other part
1313 if (MIN(partial_statelist
[p
].len
[ODD_STATE
], partial_statelist
[r
].len
[ODD_STATE
])
1314 < MIN(partial_statelist
[q
].len
[EVEN_STATE
], partial_statelist
[s
].len
[EVEN_STATE
])) {
1315 add_matching_states(current_candidates
, p
, r
, ODD_STATE
);
1316 if(current_candidates
->len
[ODD_STATE
]) {
1317 add_matching_states(current_candidates
, q
, s
, EVEN_STATE
);
1319 current_candidates
->len
[EVEN_STATE
] = 0;
1320 uint32_t *p
= current_candidates
->states
[EVEN_STATE
] = malloc(sizeof(uint32_t));
1321 *p
= END_OF_LIST_MARKER
;
1324 add_matching_states(current_candidates
, q
, s
, EVEN_STATE
);
1325 if(current_candidates
->len
[EVEN_STATE
]) {
1326 add_matching_states(current_candidates
, p
, r
, ODD_STATE
);
1328 current_candidates
->len
[ODD_STATE
] = 0;
1329 uint32_t *p
= current_candidates
->states
[ODD_STATE
] = malloc(sizeof(uint32_t));
1330 *p
= END_OF_LIST_MARKER
;
1333 //printf("Odd state candidates: %6d (2^%0.1f)\n", current_candidates->len[ODD_STATE], log(current_candidates->len[ODD_STATE])/log(2));
1334 //printf("Even state candidates: %6d (2^%0.1f)\n", current_candidates->len[EVEN_STATE], log(current_candidates->len[EVEN_STATE])/log(2));
1345 for (statelist_t
*sl
= candidates
; sl
!= NULL
&& n
< 128; sl
= sl
->next
, n
++) {
1346 maximum_states
+= (uint64_t)sl
->len
[ODD_STATE
] * sl
->len
[EVEN_STATE
];
1349 if (maximum_states
== 0) return false; // prevent keyspace reduction error (2^-inf)
1351 float kcalc
= log(maximum_states
)/log(2);
1352 printf("Number of remaining possible keys: %"PRIu64
" (2^%1.1f)\n", maximum_states
, kcalc
);
1354 if (maximum_states
!= 0) {
1355 fprintf(fstats
, "%1.1f;", kcalc
);
1357 fprintf(fstats
, "%1.1f;", 0.0);
1360 if (kcalc
< CRACKING_THRESHOLD
) return true;
1365 static void free_candidates_memory(statelist_t
*sl
)
1370 free_candidates_memory(sl
->next
);
1375 static void free_statelist_cache(void)
1377 for (uint16_t i
= 0; i
< 17; i
+=2) {
1378 for (uint16_t j
= 0; j
< 17; j
+=2) {
1379 for (uint16_t k
= 0; k
< 2; k
++) {
1380 free(sl_cache
[i
][j
][k
].sl
);
1386 #define MAX_BUCKETS 128
1387 uint64_t foundkey
= 0;
1388 size_t keys_found
= 0;
1389 size_t bucket_count
= 0;
1390 statelist_t
* buckets
[MAX_BUCKETS
];
1391 size_t total_states_tested
= 0;
1392 size_t thread_count
= 4;
1394 // these bitsliced states will hold identical states in all slices
1395 bitslice_t bitsliced_rollback_byte
[ROLLBACK_SIZE
];
1397 // arrays of bitsliced states with identical values in all slices
1398 bitslice_t bitsliced_encrypted_nonces
[NONCE_TESTS
][STATE_SIZE
];
1399 bitslice_t bitsliced_encrypted_parity_bits
[NONCE_TESTS
][ROLLBACK_SIZE
];
1403 static const uint64_t crack_states_bitsliced(statelist_t
*p
){
1404 // the idea to roll back the half-states before combining them was suggested/explained to me by bla
1405 // 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
1407 uint8_t bSize
= sizeof(bitslice_t
);
1410 size_t bucket_states_tested
= 0;
1411 size_t bucket_size
[p
->len
[EVEN_STATE
]/MAX_BITSLICES
];
1413 const size_t bucket_states_tested
= (p
->len
[EVEN_STATE
])*(p
->len
[ODD_STATE
]);
1416 bitslice_t
*bitsliced_even_states
[p
->len
[EVEN_STATE
]/MAX_BITSLICES
];
1417 size_t bitsliced_blocks
= 0;
1418 uint32_t const * restrict even_end
= p
->states
[EVEN_STATE
]+p
->len
[EVEN_STATE
];
1420 // bitslice all the even states
1421 for(uint32_t * restrict p_even
= p
->states
[EVEN_STATE
]; p_even
< even_end
; p_even
+= MAX_BITSLICES
){
1425 bitslice_t
* restrict lstate_p
= __mingw_aligned_malloc((STATE_SIZE
+ROLLBACK_SIZE
) * bSize
, bSize
);
1427 bitslice_t
* restrict lstate_p
= _aligned_malloc((STATE_SIZE
+ROLLBACK_SIZE
) * bSize
, bSize
);
1431 bitslice_t
* restrict lstate_p
= malloc((STATE_SIZE
+ROLLBACK_SIZE
) * bSize
);
1433 bitslice_t
* restrict lstate_p
= memalign(bSize
, (STATE_SIZE
+ROLLBACK_SIZE
) * bSize
);
1438 __sync_fetch_and_add(&total_states_tested
, bucket_states_tested
);
1442 memset(lstate_p
+1, 0x0, (STATE_SIZE
-1)*sizeof(bitslice_t
)); // zero even bits
1444 // bitslice even half-states
1445 const size_t max_slices
= (even_end
-p_even
) < MAX_BITSLICES
? even_end
-p_even
: MAX_BITSLICES
;
1447 bucket_size
[bitsliced_blocks
] = max_slices
;
1449 for(size_t slice_idx
= 0; slice_idx
< max_slices
; ++slice_idx
){
1450 uint32_t e
= *(p_even
+slice_idx
);
1451 for(size_t bit_idx
= 1; bit_idx
< STATE_SIZE
; bit_idx
+=2, e
>>= 1){
1454 lstate_p
[bit_idx
].bytes64
[slice_idx
>>6] |= 1ull << (slice_idx
&63);
1458 // compute the rollback bits
1459 for(size_t rollback
= 0; rollback
< ROLLBACK_SIZE
; ++rollback
){
1460 // inlined crypto1_bs_lfsr_rollback
1461 const bitslice_value_t feedout
= lstate_p
[0].value
;
1463 const bitslice_value_t ks_bits
= crypto1_bs_f20(lstate_p
);
1464 const bitslice_value_t feedback
= (feedout
^ ks_bits
^ lstate_p
[47- 5].value
^ lstate_p
[47- 9].value
^
1465 lstate_p
[47-10].value
^ lstate_p
[47-12].value
^ lstate_p
[47-14].value
^
1466 lstate_p
[47-15].value
^ lstate_p
[47-17].value
^ lstate_p
[47-19].value
^
1467 lstate_p
[47-24].value
^ lstate_p
[47-25].value
^ lstate_p
[47-27].value
^
1468 lstate_p
[47-29].value
^ lstate_p
[47-35].value
^ lstate_p
[47-39].value
^
1469 lstate_p
[47-41].value
^ lstate_p
[47-42].value
^ lstate_p
[47-43].value
);
1470 lstate_p
[47].value
= feedback
^ bitsliced_rollback_byte
[rollback
].value
;
1472 bitsliced_even_states
[bitsliced_blocks
++] = lstate_p
;
1475 // bitslice every odd state to every block of even half-states with half-finished rollback
1476 for(uint32_t const * restrict p_odd
= p
->states
[ODD_STATE
]; p_odd
< p
->states
[ODD_STATE
]+p
->len
[ODD_STATE
]; ++p_odd
){
1482 // set the odd bits and compute rollback
1483 uint64_t o
= (uint64_t) *p_odd
;
1484 lfsr_rollback_byte((struct Crypto1State
*) &o
, 0, 1);
1485 // pre-compute part of the odd feedback bits (minus rollback)
1486 bool odd_feedback_bit
= parity(o
&0x9ce5c);
1488 crypto1_bs_rewind_a0();
1490 for(size_t state_idx
= 0; state_idx
< STATE_SIZE
-ROLLBACK_SIZE
; o
>>= 1, state_idx
+=2){
1492 state_p
[state_idx
] = bs_ones
;
1494 state_p
[state_idx
] = bs_zeroes
;
1497 const bitslice_value_t odd_feedback
= odd_feedback_bit
? bs_ones
.value
: bs_zeroes
.value
;
1499 for(size_t block_idx
= 0; block_idx
< bitsliced_blocks
; ++block_idx
){
1500 const bitslice_t
* const restrict bitsliced_even_state
= bitsliced_even_states
[block_idx
];
1503 for(state_idx
= 0; state_idx
< STATE_SIZE
-ROLLBACK_SIZE
; state_idx
+=2){
1504 state_p
[1+state_idx
] = bitsliced_even_state
[1+state_idx
];
1506 // set rollback bits
1508 for(; state_idx
< STATE_SIZE
; lo
>>= 1, state_idx
+=2){
1509 // set the odd bits and take in the odd rollback bits from the even states
1511 state_p
[state_idx
].value
= ~bitsliced_even_state
[state_idx
].value
;
1513 state_p
[state_idx
] = bitsliced_even_state
[state_idx
];
1516 // set the even bits and take in the even rollback bits from the odd states
1518 state_p
[1+state_idx
].value
= ~bitsliced_even_state
[1+state_idx
].value
;
1520 state_p
[1+state_idx
] = bitsliced_even_state
[1+state_idx
];
1525 bucket_states_tested
+= bucket_size
[block_idx
];
1527 // pre-compute first keystream and feedback bit vectors
1528 const bitslice_value_t ksb
= crypto1_bs_f20(state_p
);
1529 const bitslice_value_t fbb
= (odd_feedback
^ state_p
[47- 0].value
^ state_p
[47- 5].value
^ // take in the even and rollback bits
1530 state_p
[47-10].value
^ state_p
[47-12].value
^ state_p
[47-14].value
^
1531 state_p
[47-24].value
^ state_p
[47-42].value
);
1533 // vector to contain test results (1 = passed, 0 = failed)
1534 bitslice_t results
= bs_ones
;
1536 for(size_t tests
= 0; tests
< NONCE_TESTS
; ++tests
){
1537 size_t parity_bit_idx
= 0;
1538 bitslice_value_t fb_bits
= fbb
;
1539 bitslice_value_t ks_bits
= ksb
;
1540 state_p
= &states
[KEYSTREAM_SIZE
-1];
1541 bitslice_value_t parity_bit_vector
= bs_zeroes
.value
;
1543 // highest bit is transmitted/received first
1544 for(int32_t ks_idx
= KEYSTREAM_SIZE
-1; ks_idx
>= 0; --ks_idx
, --state_p
){
1545 // decrypt nonce bits
1546 const bitslice_value_t encrypted_nonce_bit_vector
= bitsliced_encrypted_nonces
[tests
][ks_idx
].value
;
1547 const bitslice_value_t decrypted_nonce_bit_vector
= (encrypted_nonce_bit_vector
^ ks_bits
);
1549 // compute real parity bits on the fly
1550 parity_bit_vector
^= decrypted_nonce_bit_vector
;
1553 state_p
[0].value
= (fb_bits
^ decrypted_nonce_bit_vector
);
1555 // compute next keystream bit
1556 ks_bits
= crypto1_bs_f20(state_p
);
1559 if((ks_idx
&7) == 0){
1560 // get encrypted parity bits
1561 const bitslice_value_t encrypted_parity_bit_vector
= bitsliced_encrypted_parity_bits
[tests
][parity_bit_idx
++].value
;
1563 // decrypt parity bits
1564 const bitslice_value_t decrypted_parity_bit_vector
= (encrypted_parity_bit_vector
^ ks_bits
);
1566 // compare actual parity bits with decrypted parity bits and take count in results vector
1567 results
.value
&= (parity_bit_vector
^ decrypted_parity_bit_vector
);
1569 // make sure we still have a match in our set
1570 // if(memcmp(&results, &bs_zeroes, sizeof(bitslice_t)) == 0){
1572 // this is much faster on my gcc, because somehow a memcmp needlessly spills/fills all the xmm registers to/from the stack - ???
1573 // the short-circuiting also helps
1574 if(results
.bytes64
[0] == 0
1575 #if MAX_BITSLICES > 64
1576 && results
.bytes64
[1] == 0
1578 #if MAX_BITSLICES > 128
1579 && results
.bytes64
[2] == 0
1580 && results
.bytes64
[3] == 0
1585 // this is about as fast but less portable (requires -std=gnu99)
1586 // asm goto ("ptest %1, %0\n\t"
1587 // "jz %l2" :: "xm" (results.value), "xm" (bs_ones.value) : "cc" : stop_tests);
1588 parity_bit_vector
= bs_zeroes
.value
;
1590 // compute next feedback bit vector
1591 fb_bits
= (state_p
[47- 0].value
^ state_p
[47- 5].value
^ state_p
[47- 9].value
^
1592 state_p
[47-10].value
^ state_p
[47-12].value
^ state_p
[47-14].value
^
1593 state_p
[47-15].value
^ state_p
[47-17].value
^ state_p
[47-19].value
^
1594 state_p
[47-24].value
^ state_p
[47-25].value
^ state_p
[47-27].value
^
1595 state_p
[47-29].value
^ state_p
[47-35].value
^ state_p
[47-39].value
^
1596 state_p
[47-41].value
^ state_p
[47-42].value
^ state_p
[47-43].value
);
1599 // all nonce tests were successful: we've found the key in this block!
1600 state_t keys
[MAX_BITSLICES
];
1601 crypto1_bs_convert_states(&states
[KEYSTREAM_SIZE
], keys
);
1602 for(size_t results_idx
= 0; results_idx
< MAX_BITSLICES
; ++results_idx
){
1603 if(get_vector_bit(results_idx
, results
)){
1604 key
= keys
[results_idx
].value
;
1609 // prepare to set new states
1610 crypto1_bs_rewind_a0();
1616 for(size_t block_idx
= 0; block_idx
< bitsliced_blocks
; ++block_idx
){
1620 __mingw_aligned_free(bitsliced_even_states
[block_idx
]-ROLLBACK_SIZE
);
1622 _aligned_free(bitsliced_even_states
[block_idx
]-ROLLBACK_SIZE
);
1625 free(bitsliced_even_states
[block_idx
]-ROLLBACK_SIZE
);
1629 __sync_fetch_and_add(&total_states_tested
, bucket_states_tested
);
1633 static void* crack_states_thread(void* x
){
1634 const size_t thread_id
= (size_t)x
;
1635 size_t current_bucket
= thread_id
;
1636 while(current_bucket
< bucket_count
){
1637 statelist_t
* bucket
= buckets
[current_bucket
];
1639 const uint64_t key
= crack_states_bitsliced(bucket
);
1641 __sync_fetch_and_add(&keys_found
, 1);
1642 __sync_fetch_and_add(&foundkey
, key
);
1644 } else if(keys_found
){
1651 current_bucket
+= thread_count
;
1656 static bool brute_force(void)
1659 if (known_target_key
!= -1) {
1660 PrintAndLog("Looking for known target key in remaining key space...");
1661 ret
= TestIfKeyExists(known_target_key
);
1663 if (maximum_states
== 0) return false; // prevent keyspace reduction error (2^-inf)
1665 PrintAndLog("Brute force phase starting.");
1667 clock_t time1
= clock();
1673 PrintAndLog("Using %u-bit bitslices", MAX_BITSLICES
);
1674 PrintAndLog("Bitslicing best_first_byte^uid[3] (rollback byte): %02X ...", best_first_bytes
[0]^(cuid
>>24));
1675 // convert to 32 bit little-endian
1676 crypto1_bs_bitslice_value32((best_first_bytes
[0]<<24)^cuid
, bitsliced_rollback_byte
, 8);
1678 PrintAndLog("Bitslicing nonces...");
1679 for(size_t tests
= 0; tests
< NONCE_TESTS
; tests
++){
1680 uint32_t test_nonce
= brute_force_nonces
[tests
]->nonce_enc
;
1681 uint8_t test_parity
= brute_force_nonces
[tests
]->par_enc
;
1682 // 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
1683 crypto1_bs_bitslice_value32(cuid
^test_nonce
, bitsliced_encrypted_nonces
[tests
], 32);
1684 // convert to 32 bit little-endian
1685 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);
1687 total_states_tested
= 0;
1689 // count number of states to go
1691 for (statelist_t
*p
= candidates
; p
!= NULL
&& bucket_count
< MAX_BUCKETS
; p
= p
->next
) {
1692 buckets
[bucket_count
] = p
;
1695 buckets
[bucket_count
] = NULL
;
1698 thread_count
= sysconf(_SC_NPROCESSORS_CONF
);
1699 if ( thread_count
< 1)
1703 pthread_t threads
[thread_count
];
1705 // enumerate states using all hardware threads, each thread handles one bucket
1706 PrintAndLog("Starting %u cracking threads to search %u buckets containing a total of %"PRIu64
" states...", thread_count
, bucket_count
, maximum_states
);
1708 for(size_t i
= 0; i
< thread_count
; i
++){
1709 pthread_create(&threads
[i
], NULL
, crack_states_thread
, (void*) i
);
1711 for(size_t i
= 0; i
< thread_count
; i
++){
1712 pthread_join(threads
[i
], 0);
1715 time1
= clock() - time1
;
1716 if ( time1
< 0 ) time1
= -1;
1718 if (keys_found
&& TestIfKeyExists(foundkey
)) {
1719 PrintAndLog("Success! Found %u keys after %0.0f seconds", keys_found
, ((float)time1
)/CLOCKS_PER_SEC
);
1720 PrintAndLog("\nFound key: %012"PRIx64
"\n", foundkey
);
1723 PrintAndLog("Fail! Tested %"PRIu32
" states, in %0.0f seconds", total_states_tested
, ((float)time1
)/CLOCKS_PER_SEC
);
1726 // reset this counter for the next call
1727 nonces_to_bruteforce
= 0;
1733 int 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
)
1735 // initialize Random number generator
1737 srand((unsigned) time(&t
));
1739 if (trgkey
!= NULL
) {
1740 known_target_key
= bytes_to_num(trgkey
, 6);
1742 known_target_key
= -1;
1745 init_partial_statelists();
1746 init_BitFlip_statelist();
1747 write_stats
= false;
1750 // set the correct locale for the stats printing
1751 setlocale(LC_ALL
, "");
1753 if ((fstats
= fopen("hardnested_stats.txt","a")) == NULL
) {
1754 PrintAndLog("Could not create/open file hardnested_stats.txt");
1757 for (uint32_t i
= 0; i
< tests
; i
++) {
1758 init_nonce_memory();
1759 simulate_acquire_nonces();
1761 printf("Sum(a0) = %d\n", first_byte_Sum
);
1762 fprintf(fstats
, "%d;", first_byte_Sum
);
1763 generate_candidates(first_byte_Sum
, nonces
[best_first_bytes
[0]].Sum8_guess
);
1765 free_nonces_memory();
1766 free_statelist_cache();
1767 free_candidates_memory(candidates
);
1773 init_nonce_memory();
1774 if (nonce_file_read
) { // use pre-acquired data from file nonces.bin
1775 if (read_nonce_file() != 0) {
1778 Check_for_FilterFlipProperties();
1779 num_good_first_bytes
= MIN(estimate_second_byte_sum(), GOOD_BYTES_REQUIRED
);
1780 PrintAndLog("Number of first bytes with confidence > %2.1f%%: %d", CONFIDENCE_THRESHOLD
*100.0, num_good_first_bytes
);
1782 clock_t time1
= clock();
1783 bool cracking
= generate_candidates(first_byte_Sum
, nonces
[best_first_bytes
[0]].Sum8_guess
);
1784 time1
= clock() - time1
;
1786 PrintAndLog("Time for generating key candidates list: %1.0f seconds", ((float)time1
)/CLOCKS_PER_SEC
);
1788 if (cracking
|| known_target_key
!= -1) {
1792 } else { // acquire nonces.
1793 uint16_t is_OK
= acquire_nonces(blockNo
, keyType
, key
, trgBlockNo
, trgKeyType
, nonce_file_write
, slow
);
1802 //PrintAndLog("Sum(a0) = %d", first_byte_Sum);
1803 // PrintAndLog("Best 10 first bytes: %02x, %02x, %02x, %02x, %02x, %02x, %02x, %02x, %02x, %02x",
1804 // best_first_bytes[0],
1805 // best_first_bytes[1],
1806 // best_first_bytes[2],
1807 // best_first_bytes[3],
1808 // best_first_bytes[4],
1809 // best_first_bytes[5],
1810 // best_first_bytes[6],
1811 // best_first_bytes[7],
1812 // best_first_bytes[8],
1813 // best_first_bytes[9] );
1815 free_nonces_memory();
1816 free_statelist_cache();
1817 free_candidates_memory(candidates
);