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