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