]> git.zerfleddert.de Git - proxmark3-svn/blob - client/cmdhfmfhard.c
projects / proxmark3-svn / blob
? search:


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