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