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


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