]> cvs.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" - fixes and additions.
[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 void free_candidates_memory(statelist_t *sl)
766 {
767 if (sl == NULL) {
768 return;
769 } else {
770 free_candidates_memory(sl->next);
771 free(sl);
772 }
773 }
774
775 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)
776 {
777 uint8_t three_in_row = 0;
778 uint8_t prev_best = 0;
779 clock_t time1 = clock();
780 bool initialize = true;
781 bool finished = false;
782 bool filter_flip_checked = false;
783 uint32_t flags = 0;
784 uint8_t write_buf[9];
785 uint32_t total_num_nonces = 0;
786 uint32_t next_fivehundred = 500;
787 uint32_t total_added_nonces = 0;
788 uint32_t idx = 1;
789 FILE *fnonces = NULL;
790 field_off = false;
791 UsbCommand resp;
792 UsbCommand c = {CMD_MIFARE_ACQUIRE_ENCRYPTED_NONCES, {0,0,0} };
793 memcpy(c.d.asBytes, key, 6);
794 c.arg[0] = blockNo + (keyType * 0x100);
795 c.arg[1] = trgBlockNo + (trgKeyType * 0x100);
796
797 printf("Acquiring nonces...\n");
798 do {
799
800 flags = 0;
801 //flags |= initialize ? 0x0001 : 0;
802 flags |= 0x0001;
803 flags |= slow ? 0x0002 : 0;
804 flags |= field_off ? 0x0004 : 0;
805 c.arg[2] = flags;
806
807 clearCommandBuffer();
808 SendCommand(&c);
809
810 if (field_off) break;
811
812 if (!WaitForResponseTimeout(CMD_ACK, &resp, 6000)) {
813 if (fnonces) fclose(fnonces);
814 return 1;
815 }
816
817 if (resp.arg[0]) {
818 if (fnonces) fclose(fnonces);
819 return resp.arg[0]; // error during nested_hard
820 }
821
822 if (initialize) {
823 // global var CUID
824 cuid = resp.arg[1];
825 if (nonce_file_write && fnonces == NULL) {
826 if ((fnonces = fopen("nonces.bin","wb")) == NULL) {
827 PrintAndLog("Could not create file nonces.bin");
828 return 3;
829 }
830 PrintAndLog("Writing acquired nonces to binary file nonces.bin");
831 memset (write_buf, 0, sizeof (write_buf));
832 num_to_bytes(cuid, 4, write_buf);
833 fwrite(write_buf, 1, 4, fnonces);
834 fwrite(&trgBlockNo, 1, 1, fnonces);
835 fwrite(&trgKeyType, 1, 1, fnonces);
836 fflush(fnonces);
837 }
838 initialize = false;
839 }
840
841 uint32_t nt_enc1, nt_enc2;
842 uint8_t par_enc;
843 uint16_t num_acquired_nonces = resp.arg[2];
844 uint8_t *bufp = resp.d.asBytes;
845 for (uint16_t i = 0; i < num_acquired_nonces; i += 2) {
846 nt_enc1 = bytes_to_num(bufp, 4);
847 nt_enc2 = bytes_to_num(bufp+4, 4);
848 par_enc = bytes_to_num(bufp+8, 1);
849
850 total_added_nonces += add_nonce(nt_enc1, par_enc >> 4);
851 total_added_nonces += add_nonce(nt_enc2, par_enc & 0x0f);
852
853 if (nonce_file_write && fnonces) {
854 fwrite(bufp, 1, 9, fnonces);
855 fflush(fnonces);
856 }
857 bufp += 9;
858 }
859 total_num_nonces += num_acquired_nonces;
860
861 if (first_byte_num == 256) {
862
863 if (!filter_flip_checked) {
864 Check_for_FilterFlipProperties();
865 filter_flip_checked = true;
866 }
867
868 num_good_first_bytes = estimate_second_byte_sum();
869 if ( prev_best == best_first_bytes[0] ){
870 ++three_in_row;
871 } else {
872 three_in_row = 0;
873 }
874 prev_best = best_first_bytes[0];
875
876 if (total_num_nonces > next_fivehundred) {
877 next_fivehundred = (total_num_nonces/500+1) * 500;
878 printf("Acquired %5d nonces (%5d/%5d with distinct bytes 0,1). Bytes with probability for correctly guessed Sum(a8) > %1.1f%%: %d\n",
879 total_num_nonces,
880 total_added_nonces,
881 NONCES_THRESHOLD * idx,
882 CONFIDENCE_THRESHOLD * 100.0,
883 num_good_first_bytes
884 );
885 }
886
887 if ( num_good_first_bytes > 0 ) {
888 //printf("GOOD BYTES: %s \n", sprint_hex(best_first_bytes, num_good_first_bytes) );
889 if ( total_added_nonces >= (NONCES_THRESHOLD * idx) || three_in_row >= 3) {
890
891 bool cracking = generate_candidates(first_byte_Sum, nonces[best_first_bytes[0]].Sum8_guess);
892 if (cracking || known_target_key != -1) {
893
894 UsbCommand cOff = {CMD_FPGA_MAJOR_MODE_OFF, {0,0,0} };
895 SendCommand(&cOff);
896 field_off = brute_force();
897 }
898 free_candidates_memory(candidates);
899 }
900 }
901
902 if ( total_added_nonces >= (NONCES_THRESHOLD * idx))
903 ++idx;
904 }
905 } while (!finished);
906
907 if (nonce_file_write && fnonces)
908 fclose(fnonces);
909
910 time1 = clock() - time1;
911 if ( time1 > 0 ) {
912 PrintAndLog("Acquired a total of %d nonces in %1.1f seconds (%0.0f nonces/minute)",
913 total_num_nonces,
914 ((float)time1)/CLOCKS_PER_SEC,
915 total_num_nonces * 60.0 * CLOCKS_PER_SEC/(float)time1
916 );
917 }
918 return 0;
919 }
920
921 static int init_partial_statelists(void)
922 {
923 const uint32_t sizes_odd[17] = { 126757, 0, 18387, 0, 74241, 0, 181737, 0, 248801, 0, 182033, 0, 73421, 0, 17607, 0, 125601 };
924 // const uint32_t sizes_even[17] = { 125723, 0, 17867, 0, 74305, 0, 178707, 0, 248801, 0, 185063, 0, 73356, 0, 18127, 0, 126634 };
925 const uint32_t sizes_even[17] = { 125723, 0, 17867, 0, 74305, 0, 178707, 0, 248801, 0, 185063, 0, 73357, 0, 18127, 0, 126635 };
926
927 printf("Allocating memory for partial statelists...\n");
928 for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) {
929 for (uint16_t i = 0; i <= 16; i+=2) {
930 partial_statelist[i].len[odd_even] = 0;
931 uint32_t num_of_states = odd_even == ODD_STATE ? sizes_odd[i] : sizes_even[i];
932 partial_statelist[i].states[odd_even] = malloc(sizeof(uint32_t) * num_of_states);
933 if (partial_statelist[i].states[odd_even] == NULL) {
934 PrintAndLog("Cannot allocate enough memory. Aborting");
935 return 4;
936 }
937 for (uint32_t j = 0; j < STATELIST_INDEX_SIZE; j++) {
938 partial_statelist[i].index[odd_even][j] = NULL;
939 }
940 }
941 }
942
943 printf("Generating partial statelists...\n");
944 for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) {
945 uint32_t index = -1;
946 uint32_t num_of_states = 1<<20;
947 for (uint32_t state = 0; state < num_of_states; state++) {
948 uint16_t sum_property = PartialSumProperty(state, odd_even);
949 uint32_t *p = partial_statelist[sum_property].states[odd_even];
950 p += partial_statelist[sum_property].len[odd_even];
951 *p = state;
952 partial_statelist[sum_property].len[odd_even]++;
953 uint32_t index_mask = (STATELIST_INDEX_SIZE-1) << (20-STATELIST_INDEX_WIDTH);
954 if ((state & index_mask) != index) {
955 index = state & index_mask;
956 }
957 if (partial_statelist[sum_property].index[odd_even][index >> (20-STATELIST_INDEX_WIDTH)] == NULL) {
958 partial_statelist[sum_property].index[odd_even][index >> (20-STATELIST_INDEX_WIDTH)] = p;
959 }
960 }
961 // add End Of List markers
962 for (uint16_t i = 0; i <= 16; i += 2) {
963 uint32_t *p = partial_statelist[i].states[odd_even];
964 p += partial_statelist[i].len[odd_even];
965 *p = END_OF_LIST_MARKER;
966 }
967 }
968
969 return 0;
970 }
971
972 static void init_BitFlip_statelist(void)
973 {
974 printf("Generating bitflip statelist...\n");
975 uint32_t *p = statelist_bitflip.states[0] = malloc(sizeof(uint32_t) * 1<<20);
976 uint32_t index = -1;
977 uint32_t index_mask = (STATELIST_INDEX_SIZE-1) << (20-STATELIST_INDEX_WIDTH);
978 for (uint32_t state = 0; state < (1 << 20); state++) {
979 if (filter(state) != filter(state^1)) {
980 if ((state & index_mask) != index) {
981 index = state & index_mask;
982 }
983 if (statelist_bitflip.index[0][index >> (20-STATELIST_INDEX_WIDTH)] == NULL) {
984 statelist_bitflip.index[0][index >> (20-STATELIST_INDEX_WIDTH)] = p;
985 }
986 *p++ = state;
987 }
988 }
989 // set len and add End Of List marker
990 statelist_bitflip.len[0] = p - statelist_bitflip.states[0];
991 *p = END_OF_LIST_MARKER;
992 //statelist_bitflip.states[0] = realloc(statelist_bitflip.states[0], sizeof(uint32_t) * (statelist_bitflip.len[0] + 1));
993 }
994
995 static inline uint32_t *find_first_state(uint32_t state, uint32_t mask, partial_indexed_statelist_t *sl, odd_even_t odd_even)
996 {
997 uint32_t *p = sl->index[odd_even][(state & mask) >> (20-STATELIST_INDEX_WIDTH)]; // first Bits as index
998
999 if (p == NULL) return NULL;
1000 while (*p < (state & mask)) p++;
1001 if (*p == END_OF_LIST_MARKER) return NULL; // reached end of list, no match
1002 if ((*p & mask) == (state & mask)) return p; // found a match.
1003 return NULL; // no match
1004 }
1005
1006 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)
1007 {
1008 uint_fast8_t j_1_bit_mask = 0x01 << (bit-1);
1009 uint_fast8_t bit_diff = byte_diff & j_1_bit_mask; // difference of (j-1)th bit
1010 uint_fast8_t filter_diff = filter(state1 >> (4-state_bit)) ^ filter(state2 >> (4-state_bit)); // difference in filter function
1011 uint_fast8_t mask_y12_y13 = 0xc0 >> state_bit;
1012 uint_fast8_t state_bits_diff = (state1 ^ state2) & mask_y12_y13; // difference in state bits 12 and 13
1013 uint_fast8_t all_diff = evenparity8(bit_diff ^ state_bits_diff ^ filter_diff); // use parity function to XOR all bits
1014 return !all_diff;
1015 }
1016
1017 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)
1018 {
1019 uint_fast8_t j_bit_mask = 0x01 << bit;
1020 uint_fast8_t bit_diff = byte_diff & j_bit_mask; // difference of jth bit
1021 uint_fast8_t mask_y13_y16 = 0x48 >> state_bit;
1022 uint_fast8_t state_bits_diff = (state1 ^ state2) & mask_y13_y16; // difference in state bits 13 and 16
1023 uint_fast8_t all_diff = evenparity8(bit_diff ^ state_bits_diff); // use parity function to XOR all bits
1024 return all_diff;
1025 }
1026
1027 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)
1028 {
1029 if (odd_even) {
1030 // odd bits
1031 switch (num_common_bits) {
1032 case 0: if (!invariant_holds(byte_diff, state1, state2, 1, 0)) return true;
1033 case 1: if (invalid_state(byte_diff, state1, state2, 1, 0)) return false;
1034 case 2: if (!invariant_holds(byte_diff, state1, state2, 3, 1)) return true;
1035 case 3: if (invalid_state(byte_diff, state1, state2, 3, 1)) return false;
1036 case 4: if (!invariant_holds(byte_diff, state1, state2, 5, 2)) return true;
1037 case 5: if (invalid_state(byte_diff, state1, state2, 5, 2)) return false;
1038 case 6: if (!invariant_holds(byte_diff, state1, state2, 7, 3)) return true;
1039 case 7: if (invalid_state(byte_diff, state1, state2, 7, 3)) return false;
1040 }
1041 } else {
1042 // even bits
1043 switch (num_common_bits) {
1044 case 0: if (invalid_state(byte_diff, state1, state2, 0, 0)) return false;
1045 case 1: if (!invariant_holds(byte_diff, state1, state2, 2, 1)) return true;
1046 case 2: if (invalid_state(byte_diff, state1, state2, 2, 1)) return false;
1047 case 3: if (!invariant_holds(byte_diff, state1, state2, 4, 2)) return true;
1048 case 4: if (invalid_state(byte_diff, state1, state2, 4, 2)) return false;
1049 case 5: if (!invariant_holds(byte_diff, state1, state2, 6, 3)) return true;
1050 case 6: if (invalid_state(byte_diff, state1, state2, 6, 3)) return false;
1051 }
1052 }
1053
1054 return true; // valid state
1055 }
1056
1057 static bool all_other_first_bytes_match(uint32_t state, odd_even_t odd_even)
1058 {
1059 for (uint16_t i = 1; i < num_good_first_bytes; i++) {
1060 uint16_t sum_a8 = nonces[best_first_bytes[i]].Sum8_guess;
1061 uint_fast8_t bytes_diff = best_first_bytes[0] ^ best_first_bytes[i];
1062 uint_fast8_t j = common_bits(bytes_diff);
1063 uint32_t mask = 0xfffffff0;
1064 if (odd_even == ODD_STATE) {
1065 mask >>= j/2;
1066 } else {
1067 mask >>= (j+1)/2;
1068 }
1069 mask &= 0x000fffff;
1070 //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);
1071 bool found_match = false;
1072 for (uint16_t r = 0; r <= 16 && !found_match; r += 2) {
1073 for (uint16_t s = 0; s <= 16 && !found_match; s += 2) {
1074 if (r*(16-s) + (16-r)*s == sum_a8) {
1075 //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);
1076 uint16_t part_sum_a8 = (odd_even == ODD_STATE) ? r : s;
1077 uint32_t *p = find_first_state(state, mask, &partial_statelist[part_sum_a8], odd_even);
1078 if (p != NULL) {
1079 while ((state & mask) == (*p & mask) && (*p != END_OF_LIST_MARKER)) {
1080 if (remaining_bits_match(j, bytes_diff, state, (state&0x00fffff0) | *p, odd_even)) {
1081 found_match = true;
1082 // if ((odd_even == ODD_STATE && state == test_state_odd)
1083 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1084 // 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",
1085 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1086 // }
1087 break;
1088 } else {
1089 // if ((odd_even == ODD_STATE && state == test_state_odd)
1090 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1091 // 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",
1092 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1093 // }
1094 }
1095 p++;
1096 }
1097 } else {
1098 // if ((odd_even == ODD_STATE && state == test_state_odd)
1099 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1100 // 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",
1101 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1102 // }
1103 }
1104 }
1105 }
1106 }
1107
1108 if (!found_match) {
1109 // if ((odd_even == ODD_STATE && state == test_state_odd)
1110 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1111 // 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);
1112 // }
1113 return false;
1114 }
1115 }
1116
1117 return true;
1118 }
1119
1120 static bool all_bit_flips_match(uint32_t state, odd_even_t odd_even)
1121 {
1122 for (uint16_t i = 0; i < 256; i++) {
1123 if (nonces[i].BitFlip[odd_even] && i != best_first_bytes[0]) {
1124 uint_fast8_t bytes_diff = best_first_bytes[0] ^ i;
1125 uint_fast8_t j = common_bits(bytes_diff);
1126 uint32_t mask = 0xfffffff0;
1127 if (odd_even == ODD_STATE) {
1128 mask >>= j/2;
1129 } else {
1130 mask >>= (j+1)/2;
1131 }
1132 mask &= 0x000fffff;
1133 //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);
1134 bool found_match = false;
1135 uint32_t *p = find_first_state(state, mask, &statelist_bitflip, 0);
1136 if (p != NULL) {
1137 while ((state & mask) == (*p & mask) && (*p != END_OF_LIST_MARKER)) {
1138 if (remaining_bits_match(j, bytes_diff, state, (state&0x00fffff0) | *p, odd_even)) {
1139 found_match = true;
1140 // if ((odd_even == ODD_STATE && state == test_state_odd)
1141 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1142 // 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",
1143 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1144 // }
1145 break;
1146 } else {
1147 // if ((odd_even == ODD_STATE && state == test_state_odd)
1148 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1149 // 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",
1150 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1151 // }
1152 }
1153 p++;
1154 }
1155 } else {
1156 // if ((odd_even == ODD_STATE && state == test_state_odd)
1157 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1158 // 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",
1159 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1160 // }
1161 }
1162 if (!found_match) {
1163 // if ((odd_even == ODD_STATE && state == test_state_odd)
1164 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1165 // 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);
1166 // }
1167 return false;
1168 }
1169 }
1170
1171 }
1172
1173 return true;
1174 }
1175
1176 static struct sl_cache_entry {
1177 uint32_t *sl;
1178 uint32_t len;
1179 } sl_cache[17][17][2];
1180
1181 static void init_statelist_cache(void)
1182 {
1183 for (uint16_t i = 0; i < 17; i+=2) {
1184 for (uint16_t j = 0; j < 17; j+=2) {
1185 for (uint16_t k = 0; k < 2; k++) {
1186 sl_cache[i][j][k].sl = NULL;
1187 sl_cache[i][j][k].len = 0;
1188 }
1189 }
1190 }
1191 }
1192
1193 static int add_matching_states(statelist_t *candidates, uint16_t part_sum_a0, uint16_t part_sum_a8, odd_even_t odd_even)
1194 {
1195 uint32_t worstcase_size = 1<<20;
1196
1197 // check cache for existing results
1198 if (sl_cache[part_sum_a0][part_sum_a8][odd_even].sl != NULL) {
1199 candidates->states[odd_even] = sl_cache[part_sum_a0][part_sum_a8][odd_even].sl;
1200 candidates->len[odd_even] = sl_cache[part_sum_a0][part_sum_a8][odd_even].len;
1201 return 0;
1202 }
1203
1204 candidates->states[odd_even] = (uint32_t *)malloc(sizeof(uint32_t) * worstcase_size);
1205 if (candidates->states[odd_even] == NULL) {
1206 PrintAndLog("Out of memory error.\n");
1207 return 4;
1208 }
1209 uint32_t *add_p = candidates->states[odd_even];
1210 for (uint32_t *p1 = partial_statelist[part_sum_a0].states[odd_even]; *p1 != END_OF_LIST_MARKER; p1++) {
1211 uint32_t search_mask = 0x000ffff0;
1212 uint32_t *p2 = find_first_state((*p1 << 4), search_mask, &partial_statelist[part_sum_a8], odd_even);
1213 if (p1 != NULL && p2 != NULL) {
1214 while (((*p1 << 4) & search_mask) == (*p2 & search_mask) && *p2 != END_OF_LIST_MARKER) {
1215 if ((nonces[best_first_bytes[0]].BitFlip[odd_even] && find_first_state((*p1 << 4) | *p2, 0x000fffff, &statelist_bitflip, 0))
1216 || !nonces[best_first_bytes[0]].BitFlip[odd_even]) {
1217 if (all_other_first_bytes_match((*p1 << 4) | *p2, odd_even)) {
1218 if (all_bit_flips_match((*p1 << 4) | *p2, odd_even)) {
1219 *add_p++ = (*p1 << 4) | *p2;
1220 }
1221 }
1222 }
1223 p2++;
1224 }
1225 }
1226 }
1227
1228 // set end of list marker and len
1229 *add_p = END_OF_LIST_MARKER;
1230 candidates->len[odd_even] = add_p - candidates->states[odd_even];
1231
1232 candidates->states[odd_even] = realloc(candidates->states[odd_even], sizeof(uint32_t) * (candidates->len[odd_even] + 1));
1233
1234 sl_cache[part_sum_a0][part_sum_a8][odd_even].sl = candidates->states[odd_even];
1235 sl_cache[part_sum_a0][part_sum_a8][odd_even].len = candidates->len[odd_even];
1236
1237 return 0;
1238 }
1239
1240 static statelist_t *add_more_candidates(statelist_t *current_candidates)
1241 {
1242 statelist_t *new_candidates = NULL;
1243 if (current_candidates == NULL) {
1244 if (candidates == NULL) {
1245 candidates = (statelist_t *)malloc(sizeof(statelist_t));
1246 }
1247 new_candidates = candidates;
1248 } else {
1249 new_candidates = current_candidates->next = (statelist_t *)malloc(sizeof(statelist_t));
1250 }
1251 if (!new_candidates) return NULL;
1252
1253 new_candidates->next = NULL;
1254 new_candidates->len[ODD_STATE] = 0;
1255 new_candidates->len[EVEN_STATE] = 0;
1256 new_candidates->states[ODD_STATE] = NULL;
1257 new_candidates->states[EVEN_STATE] = NULL;
1258 return new_candidates;
1259 }
1260
1261 static bool TestIfKeyExists(uint64_t key)
1262 {
1263 struct Crypto1State *pcs;
1264 pcs = crypto1_create(key);
1265 crypto1_byte(pcs, (cuid >> 24) ^ best_first_bytes[0], true);
1266
1267 uint32_t state_odd = pcs->odd & 0x00ffffff;
1268 uint32_t state_even = pcs->even & 0x00ffffff;
1269 //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);
1270 printf("Validating keysearch space\n");
1271 if ( candidates == NULL ) {
1272 printf("candidates list is NULL\n");
1273 return false;
1274 }
1275 uint64_t count = 0;
1276 for (statelist_t *p = candidates; p != NULL; p = p->next) {
1277 bool found_odd = false;
1278 bool found_even = false;
1279 uint32_t *p_odd = p->states[ODD_STATE];
1280 uint32_t *p_even = p->states[EVEN_STATE];
1281 while (*p_odd != END_OF_LIST_MARKER) {
1282 if ((*p_odd & 0x00ffffff) == state_odd) {
1283 found_odd = true;
1284 break;
1285 }
1286 p_odd++;
1287 }
1288 while (*p_even != END_OF_LIST_MARKER) {
1289 if ((*p_even & 0x00ffffff) == state_even)
1290 found_even = true;
1291
1292 p_even++;
1293 }
1294 count += (p_odd - p->states[ODD_STATE]) * (p_even - p->states[EVEN_STATE]);
1295 if (found_odd && found_even) {
1296 if (known_target_key != -1) {
1297 PrintAndLog("Key Found after testing %llu (2^%1.1f) out of %lld (2^%1.1f) keys.",
1298 count,
1299 log(count)/log(2),
1300 maximum_states,
1301 log(maximum_states)/log(2)
1302 );
1303 if (write_stats)
1304 fprintf(fstats, "1\n");
1305 }
1306 crypto1_destroy(pcs);
1307 return true;
1308 }
1309 }
1310
1311 if (known_target_key != -1) {
1312 printf("Key NOT found!\n");
1313 if (write_stats)
1314 fprintf(fstats, "0\n");
1315 }
1316 crypto1_destroy(pcs);
1317 return false;
1318 }
1319
1320 static bool generate_candidates(uint16_t sum_a0, uint16_t sum_a8)
1321 {
1322 printf("Generating crypto1 state candidates... \n");
1323
1324 statelist_t *current_candidates = NULL;
1325 // estimate maximum candidate states
1326 maximum_states = 0;
1327 for (uint16_t sum_odd = 0; sum_odd <= 16; sum_odd += 2) {
1328 for (uint16_t sum_even = 0; sum_even <= 16; sum_even += 2) {
1329 if (sum_odd*(16-sum_even) + (16-sum_odd)*sum_even == sum_a0) {
1330 maximum_states += (uint64_t)partial_statelist[sum_odd].len[ODD_STATE] * partial_statelist[sum_even].len[EVEN_STATE] * (1<<8);
1331 }
1332 }
1333 }
1334
1335 if (maximum_states == 0) return false; // prevent keyspace reduction error (2^-inf)
1336
1337 printf("Number of possible keys with Sum(a0) = %d: %"PRIu64" (2^%1.1f)\n", sum_a0, maximum_states, log(maximum_states)/log(2));
1338
1339 init_statelist_cache();
1340
1341 for (uint16_t p = 0; p <= 16; p += 2) {
1342 for (uint16_t q = 0; q <= 16; q += 2) {
1343 if (p*(16-q) + (16-p)*q == sum_a0) {
1344 // printf("Reducing Partial Statelists (p,q) = (%d,%d) with lengths %d, %d\n",
1345 // p, q, partial_statelist[p].len[ODD_STATE], partial_statelist[q].len[EVEN_STATE]);
1346 for (uint16_t r = 0; r <= 16; r += 2) {
1347 for (uint16_t s = 0; s <= 16; s += 2) {
1348 if (r*(16-s) + (16-r)*s == sum_a8) {
1349 current_candidates = add_more_candidates(current_candidates);
1350 if (current_candidates != NULL) {
1351 // check for the smallest partial statelist. Try this first - it might give 0 candidates
1352 // and eliminate the need to calculate the other part
1353 if (MIN(partial_statelist[p].len[ODD_STATE], partial_statelist[r].len[ODD_STATE])
1354 < MIN(partial_statelist[q].len[EVEN_STATE], partial_statelist[s].len[EVEN_STATE])) {
1355 add_matching_states(current_candidates, p, r, ODD_STATE);
1356 if(current_candidates->len[ODD_STATE]) {
1357 add_matching_states(current_candidates, q, s, EVEN_STATE);
1358 } else {
1359 current_candidates->len[EVEN_STATE] = 0;
1360 uint32_t *p = current_candidates->states[EVEN_STATE] = malloc(sizeof(uint32_t));
1361 *p = END_OF_LIST_MARKER;
1362 }
1363 } else {
1364 add_matching_states(current_candidates, q, s, EVEN_STATE);
1365 if(current_candidates->len[EVEN_STATE]) {
1366 add_matching_states(current_candidates, p, r, ODD_STATE);
1367 } else {
1368 current_candidates->len[ODD_STATE] = 0;
1369 uint32_t *p = current_candidates->states[ODD_STATE] = malloc(sizeof(uint32_t));
1370 *p = END_OF_LIST_MARKER;
1371 }
1372 }
1373 //printf("Odd state candidates: %6d (2^%0.1f)\n", current_candidates->len[ODD_STATE], log(current_candidates->len[ODD_STATE])/log(2));
1374 //printf("Even state candidates: %6d (2^%0.1f)\n", current_candidates->len[EVEN_STATE], log(current_candidates->len[EVEN_STATE])/log(2));
1375 }
1376 }
1377 }
1378 }
1379 }
1380 }
1381 }
1382
1383 maximum_states = 0;
1384 unsigned int n = 0;
1385 for (statelist_t *sl = candidates; sl != NULL && n < MAX_BUCKETS; sl = sl->next, n++) {
1386 maximum_states += (uint64_t)sl->len[ODD_STATE] * sl->len[EVEN_STATE];
1387 }
1388
1389 if (maximum_states == 0) return false; // prevent keyspace reduction error (2^-inf)
1390
1391 float kcalc = log(maximum_states)/log(2);
1392 printf("Number of remaining possible keys: %"PRIu64" (2^%1.1f)\n", maximum_states, kcalc);
1393 if (write_stats) {
1394 fprintf(fstats, "%1.1f;", (kcalc != 0) ? kcalc : 0.0);
1395 }
1396 if (kcalc < CRACKING_THRESHOLD) return true;
1397
1398 return false;
1399 }
1400
1401 static void free_statelist_cache(void)
1402 {
1403 for (uint16_t i = 0; i < 17; i+=2) {
1404 for (uint16_t j = 0; j < 17; j+=2) {
1405 for (uint16_t k = 0; k < 2; k++) {
1406 free(sl_cache[i][j][k].sl);
1407 }
1408 }
1409 }
1410 }
1411
1412 static const uint64_t crack_states_bitsliced(statelist_t *p){
1413 // the idea to roll back the half-states before combining them was suggested/explained to me by bla
1414 // 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
1415 uint64_t key = -1;
1416 uint8_t bSize = sizeof(bitslice_t);
1417
1418 #ifdef EXACT_COUNT
1419 size_t bucket_states_tested = 0;
1420 size_t bucket_size[p->len[EVEN_STATE]/MAX_BITSLICES];
1421 #else
1422 const size_t bucket_states_tested = (p->len[EVEN_STATE])*(p->len[ODD_STATE]);
1423 #endif
1424
1425 bitslice_t *bitsliced_even_states[p->len[EVEN_STATE]/MAX_BITSLICES];
1426 size_t bitsliced_blocks = 0;
1427 uint32_t const * restrict even_end = p->states[EVEN_STATE]+p->len[EVEN_STATE];
1428
1429 // bitslice all the even states
1430 for(uint32_t * restrict p_even = p->states[EVEN_STATE]; p_even < even_end; p_even += MAX_BITSLICES){
1431
1432 #ifdef __WIN32
1433 #ifdef __MINGW32__
1434 bitslice_t * restrict lstate_p = __mingw_aligned_malloc((STATE_SIZE+ROLLBACK_SIZE) * bSize, bSize);
1435 #else
1436 bitslice_t * restrict lstate_p = _aligned_malloc((STATE_SIZE+ROLLBACK_SIZE) * bSize, bSize);
1437 #endif
1438 #else
1439 #ifdef __APPLE__
1440 bitslice_t * restrict lstate_p = malloc((STATE_SIZE+ROLLBACK_SIZE) * bSize);
1441 #else
1442 bitslice_t * restrict lstate_p = memalign(bSize, (STATE_SIZE+ROLLBACK_SIZE) * bSize);
1443 #endif
1444 #endif
1445
1446 if ( !lstate_p ) {
1447 __sync_fetch_and_add(&total_states_tested, bucket_states_tested);
1448 return key;
1449 }
1450
1451 memset(lstate_p+1, 0x0, (STATE_SIZE-1)*sizeof(bitslice_t)); // zero even bits
1452
1453 // bitslice even half-states
1454 const size_t max_slices = (even_end-p_even) < MAX_BITSLICES ? even_end-p_even : MAX_BITSLICES;
1455 #ifdef EXACT_COUNT
1456 bucket_size[bitsliced_blocks] = max_slices;
1457 #endif
1458 for(size_t slice_idx = 0; slice_idx < max_slices; ++slice_idx){
1459 uint32_t e = *(p_even+slice_idx);
1460 for(size_t bit_idx = 1; bit_idx < STATE_SIZE; bit_idx+=2, e >>= 1){
1461 // set even bits
1462 if(e&1){
1463 lstate_p[bit_idx].bytes64[slice_idx>>6] |= 1ull << (slice_idx&63);
1464 }
1465 }
1466 }
1467 // compute the rollback bits
1468 for(size_t rollback = 0; rollback < ROLLBACK_SIZE; ++rollback){
1469 // inlined crypto1_bs_lfsr_rollback
1470 const bitslice_value_t feedout = lstate_p[0].value;
1471 ++lstate_p;
1472 const bitslice_value_t ks_bits = crypto1_bs_f20(lstate_p);
1473 const bitslice_value_t feedback = (feedout ^ ks_bits ^ lstate_p[47- 5].value ^ lstate_p[47- 9].value ^
1474 lstate_p[47-10].value ^ lstate_p[47-12].value ^ lstate_p[47-14].value ^
1475 lstate_p[47-15].value ^ lstate_p[47-17].value ^ lstate_p[47-19].value ^
1476 lstate_p[47-24].value ^ lstate_p[47-25].value ^ lstate_p[47-27].value ^
1477 lstate_p[47-29].value ^ lstate_p[47-35].value ^ lstate_p[47-39].value ^
1478 lstate_p[47-41].value ^ lstate_p[47-42].value ^ lstate_p[47-43].value);
1479 lstate_p[47].value = feedback ^ bitsliced_rollback_byte[rollback].value;
1480 }
1481 bitsliced_even_states[bitsliced_blocks++] = lstate_p;
1482 }
1483
1484 // bitslice every odd state to every block of even half-states with half-finished rollback
1485 for(uint32_t const * restrict p_odd = p->states[ODD_STATE]; p_odd < p->states[ODD_STATE]+p->len[ODD_STATE]; ++p_odd){
1486 // early abort
1487 if(keys_found){
1488 goto out;
1489 }
1490
1491 // set the odd bits and compute rollback
1492 uint64_t o = (uint64_t) *p_odd;
1493 lfsr_rollback_byte((struct Crypto1State*) &o, 0, 1);
1494 // pre-compute part of the odd feedback bits (minus rollback)
1495 bool odd_feedback_bit = parity(o&0x9ce5c);
1496
1497 crypto1_bs_rewind_a0();
1498 // set odd bits
1499 for(size_t state_idx = 0; state_idx < STATE_SIZE-ROLLBACK_SIZE; o >>= 1, state_idx+=2){
1500 state_p[state_idx] = (o & 1) ? bs_ones : bs_zeroes;
1501 }
1502 const bitslice_value_t odd_feedback = odd_feedback_bit ? bs_ones.value : bs_zeroes.value;
1503
1504 for(size_t block_idx = 0; block_idx < bitsliced_blocks; ++block_idx){
1505 const bitslice_t * const restrict bitsliced_even_state = bitsliced_even_states[block_idx];
1506 size_t state_idx;
1507 // set even bits
1508 for(state_idx = 0; state_idx < STATE_SIZE-ROLLBACK_SIZE; state_idx+=2){
1509 state_p[1+state_idx] = bitsliced_even_state[1+state_idx];
1510 }
1511 // set rollback bits
1512 uint64_t lo = o;
1513 for(; state_idx < STATE_SIZE; lo >>= 1, state_idx+=2){
1514 // set the odd bits and take in the odd rollback bits from the even states
1515 if(lo & 1){
1516 state_p[state_idx].value = ~bitsliced_even_state[state_idx].value;
1517 } else {
1518 state_p[state_idx] = bitsliced_even_state[state_idx];
1519 }
1520
1521 // set the even bits and take in the even rollback bits from the odd states
1522 if((lo >> 32) & 1){
1523 state_p[1+state_idx].value = ~bitsliced_even_state[1+state_idx].value;
1524 } else {
1525 state_p[1+state_idx] = bitsliced_even_state[1+state_idx];
1526 }
1527 }
1528
1529 #ifdef EXACT_COUNT
1530 bucket_states_tested += (bucket_size[block_idx] > MAX_BITSLICES) ? MAX_BITSLICES : bucket_size[block_idx];
1531 #endif
1532 // pre-compute first keystream and feedback bit vectors
1533 const bitslice_value_t ksb = crypto1_bs_f20(state_p);
1534 const bitslice_value_t fbb = (odd_feedback ^ state_p[47- 0].value ^ state_p[47- 5].value ^ // take in the even and rollback bits
1535 state_p[47-10].value ^ state_p[47-12].value ^ state_p[47-14].value ^
1536 state_p[47-24].value ^ state_p[47-42].value);
1537
1538 // vector to contain test results (1 = passed, 0 = failed)
1539 bitslice_t results = bs_ones;
1540
1541 for(size_t tests = 0; tests < NONCE_TESTS; ++tests){
1542 size_t parity_bit_idx = 0;
1543 bitslice_value_t fb_bits = fbb;
1544 bitslice_value_t ks_bits = ksb;
1545 state_p = &states[KEYSTREAM_SIZE-1];
1546 bitslice_value_t parity_bit_vector = bs_zeroes.value;
1547
1548 // highest bit is transmitted/received first
1549 for(int32_t ks_idx = KEYSTREAM_SIZE-1; ks_idx >= 0; --ks_idx, --state_p){
1550 // decrypt nonce bits
1551 const bitslice_value_t encrypted_nonce_bit_vector = bitsliced_encrypted_nonces[tests][ks_idx].value;
1552 const bitslice_value_t decrypted_nonce_bit_vector = (encrypted_nonce_bit_vector ^ ks_bits);
1553
1554 // compute real parity bits on the fly
1555 parity_bit_vector ^= decrypted_nonce_bit_vector;
1556
1557 // update state
1558 state_p[0].value = (fb_bits ^ decrypted_nonce_bit_vector);
1559
1560 // compute next keystream bit
1561 ks_bits = crypto1_bs_f20(state_p);
1562
1563 // for each byte:
1564 if((ks_idx&7) == 0){
1565 // get encrypted parity bits
1566 const bitslice_value_t encrypted_parity_bit_vector = bitsliced_encrypted_parity_bits[tests][parity_bit_idx++].value;
1567
1568 // decrypt parity bits
1569 const bitslice_value_t decrypted_parity_bit_vector = (encrypted_parity_bit_vector ^ ks_bits);
1570
1571 // compare actual parity bits with decrypted parity bits and take count in results vector
1572 results.value &= (parity_bit_vector ^ decrypted_parity_bit_vector);
1573
1574 // make sure we still have a match in our set
1575 // if(memcmp(&results, &bs_zeroes, sizeof(bitslice_t)) == 0){
1576
1577 // this is much faster on my gcc, because somehow a memcmp needlessly spills/fills all the xmm registers to/from the stack - ???
1578 // the short-circuiting also helps
1579 if(results.bytes64[0] == 0
1580 #if MAX_BITSLICES > 64
1581 && results.bytes64[1] == 0
1582 #endif
1583 #if MAX_BITSLICES > 128
1584 && results.bytes64[2] == 0
1585 && results.bytes64[3] == 0
1586 #endif
1587 ){
1588 goto stop_tests;
1589 }
1590 // this is about as fast but less portable (requires -std=gnu99)
1591 // asm goto ("ptest %1, %0\n\t"
1592 // "jz %l2" :: "xm" (results.value), "xm" (bs_ones.value) : "cc" : stop_tests);
1593 parity_bit_vector = bs_zeroes.value;
1594 }
1595 // compute next feedback bit vector
1596 fb_bits = (state_p[47- 0].value ^ state_p[47- 5].value ^ state_p[47- 9].value ^
1597 state_p[47-10].value ^ state_p[47-12].value ^ state_p[47-14].value ^
1598 state_p[47-15].value ^ state_p[47-17].value ^ state_p[47-19].value ^
1599 state_p[47-24].value ^ state_p[47-25].value ^ state_p[47-27].value ^
1600 state_p[47-29].value ^ state_p[47-35].value ^ state_p[47-39].value ^
1601 state_p[47-41].value ^ state_p[47-42].value ^ state_p[47-43].value);
1602 }
1603 }
1604 // all nonce tests were successful: we've found the key in this block!
1605 state_t keys[MAX_BITSLICES];
1606 crypto1_bs_convert_states(&states[KEYSTREAM_SIZE], keys);
1607 for(size_t results_idx = 0; results_idx < MAX_BITSLICES; ++results_idx){
1608 if(get_vector_bit(results_idx, results)){
1609 key = keys[results_idx].value;
1610 goto out;
1611 }
1612 }
1613 stop_tests:
1614 // prepare to set new states
1615 crypto1_bs_rewind_a0();
1616 continue;
1617 }
1618 }
1619
1620 out:
1621 for(size_t block_idx = 0; block_idx < bitsliced_blocks; ++block_idx){
1622
1623 #ifdef __WIN32
1624 #ifdef __MINGW32__
1625 __mingw_aligned_free(bitsliced_even_states[block_idx]-ROLLBACK_SIZE);
1626 #else
1627 _aligned_free(bitsliced_even_states[block_idx]-ROLLBACK_SIZE);
1628 #endif
1629 #else
1630 free(bitsliced_even_states[block_idx]-ROLLBACK_SIZE);
1631 #endif
1632
1633 }
1634 __sync_fetch_and_add(&total_states_tested, bucket_states_tested);
1635 return key;
1636 }
1637
1638 static void* crack_states_thread(void* x){
1639 const size_t thread_id = (size_t)x;
1640 size_t current_bucket = thread_id;
1641 statelist_t *bucket = NULL;
1642
1643 while(current_bucket < bucket_count){
1644 if (keys_found) break;
1645
1646 if ((bucket = buckets[current_bucket])) {
1647 const uint64_t key = crack_states_bitsliced(bucket);
1648
1649 if (keys_found) break;
1650 else if(key != -1 && TestIfKeyExists(key)) {
1651 __sync_fetch_and_add(&keys_found, 1);
1652 __sync_fetch_and_add(&foundkey, key);
1653 break;
1654 } else {
1655 printf(".");
1656 fflush(stdout);
1657 }
1658 }
1659
1660 current_bucket += thread_count;
1661 }
1662
1663 return NULL;
1664 }
1665
1666 static bool brute_force(void) {
1667 bool ret = false;
1668 if (known_target_key != -1) {
1669 PrintAndLog("Looking for known target key in remaining key space...");
1670 ret = TestIfKeyExists(known_target_key);
1671 } else {
1672 if (maximum_states == 0) return false; // prevent keyspace reduction error (2^-inf)
1673
1674 PrintAndLog("Brute force phase starting.");
1675
1676 clock_t time1 = clock();
1677 keys_found = 0;
1678 foundkey = 0;
1679
1680 crypto1_bs_init();
1681 memset (bitsliced_rollback_byte, 0, sizeof (bitsliced_rollback_byte));
1682 memset (bitsliced_encrypted_nonces, 0, sizeof (bitsliced_encrypted_nonces));
1683 memset (bitsliced_encrypted_parity_bits, 0, sizeof (bitsliced_encrypted_parity_bits));
1684
1685 PrintAndLog("Using %u-bit bitslices", MAX_BITSLICES);
1686 PrintAndLog("Bitslicing best_first_byte^uid[3] (rollback byte): %02X ...", best_first_bytes[0]^(cuid>>24));
1687 // convert to 32 bit little-endian
1688 crypto1_bs_bitslice_value32((best_first_bytes[0]<<24)^cuid, bitsliced_rollback_byte, 8);
1689
1690 PrintAndLog("Bitslicing nonces...");
1691 for(size_t tests = 0; tests < NONCE_TESTS; tests++){
1692 uint32_t test_nonce = brute_force_nonces[tests]->nonce_enc;
1693 uint8_t test_parity = brute_force_nonces[tests]->par_enc;
1694 // 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
1695 crypto1_bs_bitslice_value32(cuid^test_nonce, bitsliced_encrypted_nonces[tests], 32);
1696 // convert to 32 bit little-endian
1697 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);
1698 }
1699 total_states_tested = 0;
1700
1701 // count number of states to go
1702 bucket_count = 0;
1703 buckets[MAX_BUCKETS-1] = NULL;
1704 for (statelist_t *p = candidates; p != NULL && bucket_count < MAX_BUCKETS; p = p->next) {
1705 buckets[bucket_count] = p;
1706 bucket_count++;
1707 }
1708 if (bucket_count < MAX_BUCKETS) buckets[bucket_count] = NULL;
1709
1710 #ifndef __WIN32
1711 thread_count = sysconf(_SC_NPROCESSORS_CONF);
1712 if ( thread_count < 1)
1713 thread_count = 1;
1714 #endif /* _WIN32 */
1715
1716 pthread_t threads[thread_count];
1717
1718 // enumerate states using all hardware threads, each thread handles one bucket
1719 PrintAndLog("Starting %u cracking threads to search %u buckets containing a total of %"PRIu64" states...", thread_count, bucket_count, maximum_states);
1720
1721 for(size_t i = 0; i < thread_count; i++){
1722 pthread_create(&threads[i], NULL, crack_states_thread, (void*) i);
1723 }
1724 for(size_t i = 0; i < thread_count; i++){
1725 pthread_join(threads[i], 0);
1726 }
1727
1728 time1 = clock() - time1;
1729 PrintAndLog("\nTime for bruteforce %0.1f seconds.",((float)time1)/CLOCKS_PER_SEC);
1730
1731 if (keys_found) {
1732 PrintAndLog("\nFound key: %012"PRIx64"\n", foundkey);
1733 ret = true;
1734 }
1735 // reset this counter for the next call
1736 nonces_to_bruteforce = 0;
1737 }
1738 return ret;
1739 }
1740
1741 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)
1742 {
1743 // initialize Random number generator
1744 time_t t;
1745 srand((unsigned) time(&t));
1746
1747 if (trgkey != NULL) {
1748 known_target_key = bytes_to_num(trgkey, 6);
1749 } else {
1750 known_target_key = -1;
1751 }
1752
1753 init_partial_statelists();
1754 init_BitFlip_statelist();
1755 write_stats = false;
1756
1757 if (tests) {
1758 // set the correct locale for the stats printing
1759 setlocale(LC_ALL, "");
1760 write_stats = true;
1761 if ((fstats = fopen("hardnested_stats.txt","a")) == NULL) {
1762 PrintAndLog("Could not create/open file hardnested_stats.txt");
1763 return 3;
1764 }
1765 for (uint32_t i = 0; i < tests; i++) {
1766 init_nonce_memory();
1767 simulate_acquire_nonces();
1768 Tests();
1769 printf("Sum(a0) = %d\n", first_byte_Sum);
1770 fprintf(fstats, "%d;", first_byte_Sum);
1771 generate_candidates(first_byte_Sum, nonces[best_first_bytes[0]].Sum8_guess);
1772 brute_force();
1773 free_nonces_memory();
1774 free_statelist_cache();
1775 free_candidates_memory(candidates);
1776 candidates = NULL;
1777 }
1778 fclose(fstats);
1779 fstats = NULL;
1780 } else {
1781 init_nonce_memory();
1782 if (nonce_file_read) { // use pre-acquired data from file nonces.bin
1783 if (read_nonce_file() != 0) {
1784 return 3;
1785 }
1786 Check_for_FilterFlipProperties();
1787 num_good_first_bytes = MIN(estimate_second_byte_sum(), GOOD_BYTES_REQUIRED);
1788 PrintAndLog("Number of first bytes with confidence > %2.1f%%: %d", CONFIDENCE_THRESHOLD*100.0, num_good_first_bytes);
1789
1790 bool cracking = generate_candidates(first_byte_Sum, nonces[best_first_bytes[0]].Sum8_guess);
1791 if (cracking || known_target_key != -1) {
1792 brute_force();
1793 }
1794
1795 } else { // acquire nonces.
1796 uint16_t is_OK = acquire_nonces(blockNo, keyType, key, trgBlockNo, trgKeyType, nonce_file_write, slow);
1797 if (is_OK != 0) {
1798 return is_OK;
1799 }
1800 }
1801
1802 //Tests();
1803 free_nonces_memory();
1804 free_statelist_cache();
1805 free_candidates_memory(candidates);
1806 candidates = NULL;
1807 }
1808 return 0;
1809 }
Proxmark3 GIT tracking
Impressum, Datenschutz