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


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