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