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