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


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