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


956da8e8473893ed2edc06a042e233222f23b109
[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
42 #define END_OF_LIST_MARKER 0xFFFFFFFF
43
44 static const float p_K[257] = { // the probability that a random nonce has a Sum Property == K
45 0.0290, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
46 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
47 0.0000, 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.0083, 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.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
52 0.0006, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
53 0.0339, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
54 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
55 0.0048, 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.0934, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
58 0.0119, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
59 0.0489, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
60 0.0602, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
61 0.4180, 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.0489, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
64 0.0119, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
65 0.0934, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
66 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
67 0.0048, 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.0339, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
70 0.0006, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
71 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
72 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
73 0.0083, 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.0000, 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.0290 };
78
79 typedef struct noncelistentry {
80 uint32_t nonce_enc;
81 uint8_t par_enc;
82 void *next;
83 } noncelistentry_t;
84
85 typedef struct noncelist {
86 uint16_t num;
87 uint16_t Sum;
88 uint16_t Sum8_guess;
89 uint8_t BitFlip[2];
90 float Sum8_prob;
91 bool updated;
92 noncelistentry_t *first;
93 float score1, score2;
94 } noncelist_t;
95
96 typedef struct check_args {
97 uint32_t next_fivehundred;
98 uint32_t total_num_nonces;
99 uint32_t total_added_nonces;
100 uint32_t idx;
101 } check_args_t;
102
103 static size_t nonces_to_bruteforce = 0;
104 static noncelistentry_t *brute_force_nonces[256];
105 static uint32_t cuid = 0;
106 static noncelist_t nonces[256];
107 static uint8_t best_first_bytes[256];
108 static uint16_t first_byte_Sum = 0;
109 static uint16_t first_byte_num = 0;
110 static uint16_t num_good_first_bytes = 0;
111 static uint64_t maximum_states = 0;
112 static uint64_t known_target_key;
113 static bool write_stats = false;
114 static FILE *fstats = NULL;
115
116
117 typedef enum {
118 EVEN_STATE = 0,
119 ODD_STATE = 1
120 } odd_even_t;
121
122 #define STATELIST_INDEX_WIDTH 16
123 #define STATELIST_INDEX_SIZE (1<<STATELIST_INDEX_WIDTH)
124
125 typedef struct {
126 uint32_t *states[2];
127 uint32_t len[2];
128 uint32_t *index[2][STATELIST_INDEX_SIZE];
129 } partial_indexed_statelist_t;
130
131 typedef struct {
132 uint32_t *states[2];
133 uint32_t len[2];
134 void* next;
135 } statelist_t;
136
137
138 static partial_indexed_statelist_t partial_statelist[17];
139 static partial_indexed_statelist_t statelist_bitflip;
140 static statelist_t *candidates = NULL;
141
142 bool thread_check_started = false;
143 bool thread_check_done = false;
144 bool cracking = false;
145 bool field_off = false;
146
147 pthread_t thread_check;
148 check_args_t cargs;
149
150 static void* check_thread(void*);
151 static bool generate_candidates(uint16_t, uint16_t);
152 static bool brute_force(void);
153
154 static int add_nonce(uint32_t nonce_enc, uint8_t par_enc)
155 {
156 uint8_t first_byte = nonce_enc >> 24;
157 noncelistentry_t *p1 = nonces[first_byte].first;
158 noncelistentry_t *p2 = NULL;
159
160 if (p1 == NULL) { // first nonce with this 1st byte
161 first_byte_num++;
162 first_byte_Sum += evenparity32((nonce_enc & 0xff000000) | (par_enc & 0x08));
163 // printf("Adding nonce 0x%08x, par_enc 0x%02x, parity(0x%08x) = %d\n",
164 // nonce_enc,
165 // par_enc,
166 // (nonce_enc & 0xff000000) | (par_enc & 0x08) |0x01,
167 // parity((nonce_enc & 0xff000000) | (par_enc & 0x08));
168 }
169
170 while (p1 != NULL && (p1->nonce_enc & 0x00ff0000) < (nonce_enc & 0x00ff0000)) {
171 p2 = p1;
172 p1 = p1->next;
173 }
174
175 if (p1 == NULL) { // need to add at the end of the list
176 if (p2 == NULL) { // list is empty yet. Add first entry.
177 p2 = nonces[first_byte].first = malloc(sizeof(noncelistentry_t));
178 } else { // add new entry at end of existing list.
179 p2 = p2->next = malloc(sizeof(noncelistentry_t));
180 }
181 } else if ((p1->nonce_enc & 0x00ff0000) != (nonce_enc & 0x00ff0000)) { // found distinct 2nd byte. Need to insert.
182 if (p2 == NULL) { // need to insert at start of list
183 p2 = nonces[first_byte].first = malloc(sizeof(noncelistentry_t));
184 } else {
185 p2 = p2->next = malloc(sizeof(noncelistentry_t));
186 }
187 } else { // we have seen this 2nd byte before. Nothing to add or insert.
188 return (0);
189 }
190
191 // add or insert new data
192 p2->next = p1;
193 p2->nonce_enc = nonce_enc;
194 p2->par_enc = par_enc;
195
196 if(nonces_to_bruteforce < 256){
197 brute_force_nonces[nonces_to_bruteforce] = p2;
198 nonces_to_bruteforce++;
199 }
200
201 nonces[first_byte].num++;
202 nonces[first_byte].Sum += evenparity32((nonce_enc & 0x00ff0000) | (par_enc & 0x04));
203 nonces[first_byte].updated = true; // indicates that we need to recalculate the Sum(a8) probability for this first byte
204
205 return (1); // new nonce added
206 }
207
208 static void init_nonce_memory(void)
209 {
210 for (uint16_t i = 0; i < 256; i++) {
211 nonces[i].num = 0;
212 nonces[i].Sum = 0;
213 nonces[i].Sum8_guess = 0;
214 nonces[i].Sum8_prob = 0.0;
215 nonces[i].updated = true;
216 nonces[i].first = NULL;
217 }
218 first_byte_num = 0;
219 first_byte_Sum = 0;
220 num_good_first_bytes = 0;
221 }
222
223 static void free_nonce_list(noncelistentry_t *p)
224 {
225 if (p == NULL) {
226 return;
227 } else {
228 free_nonce_list(p->next);
229 free(p);
230 }
231 }
232
233 static void free_nonces_memory(void)
234 {
235 for (uint16_t i = 0; i < 256; i++) {
236 free_nonce_list(nonces[i].first);
237 }
238 }
239
240 static uint16_t PartialSumProperty(uint32_t state, odd_even_t odd_even)
241 {
242 uint16_t sum = 0;
243 for (uint16_t j = 0; j < 16; j++) {
244 uint32_t st = state;
245 uint16_t part_sum = 0;
246 if (odd_even == ODD_STATE) {
247 for (uint16_t i = 0; i < 5; i++) {
248 part_sum ^= filter(st);
249 st = (st << 1) | ((j >> (3-i)) & 0x01) ;
250 }
251 part_sum ^= 1; // XOR 1 cancelled out for the other 8 bits
252 } else {
253 for (uint16_t i = 0; i < 4; i++) {
254 st = (st << 1) | ((j >> (3-i)) & 0x01) ;
255 part_sum ^= filter(st);
256 }
257 }
258 sum += part_sum;
259 }
260 return sum;
261 }
262
263 // static uint16_t SumProperty(struct Crypto1State *s)
264 // {
265 // uint16_t sum_odd = PartialSumProperty(s->odd, ODD_STATE);
266 // uint16_t sum_even = PartialSumProperty(s->even, EVEN_STATE);
267 // return (sum_odd*(16-sum_even) + (16-sum_odd)*sum_even);
268 // }
269
270 static double p_hypergeometric(uint16_t N, uint16_t K, uint16_t n, uint16_t k)
271 {
272 // for efficient computation we are using the recursive definition
273 // (K-k+1) * (n-k+1)
274 // P(X=k) = P(X=k-1) * --------------------
275 // k * (N-K-n+k)
276 // and
277 // (N-K)*(N-K-1)*...*(N-K-n+1)
278 // P(X=0) = -----------------------------
279 // N*(N-1)*...*(N-n+1)
280
281 if (n-k > N-K || k > K) return 0.0; // avoids log(x<=0) in calculation below
282 if (k == 0) {
283 // use logarithms to avoid overflow with huge factorials (double type can only hold 170!)
284 double log_result = 0.0;
285 for (int16_t i = N-K; i >= N-K-n+1; i--) {
286 log_result += log(i);
287 }
288 for (int16_t i = N; i >= N-n+1; i--) {
289 log_result -= log(i);
290 }
291 return exp(log_result);
292 } else {
293 if (n-k == N-K) { // special case. The published recursion below would fail with a divide by zero exception
294 double log_result = 0.0;
295 for (int16_t i = k+1; i <= n; i++) {
296 log_result += log(i);
297 }
298 for (int16_t i = K+1; i <= N; i++) {
299 log_result -= log(i);
300 }
301 return exp(log_result);
302 } else { // recursion
303 return (p_hypergeometric(N, K, n, k-1) * (K-k+1) * (n-k+1) / (k * (N-K-n+k)));
304 }
305 }
306 }
307
308 static float sum_probability(uint16_t K, uint16_t n, uint16_t k)
309 {
310 const uint16_t N = 256;
311
312 if (k > K || p_K[K] == 0.0) return 0.0;
313
314 double p_T_is_k_when_S_is_K = p_hypergeometric(N, K, n, k);
315 double p_S_is_K = p_K[K];
316 double p_T_is_k = 0;
317 for (uint16_t i = 0; i <= 256; i++) {
318 if (p_K[i] != 0.0) {
319 p_T_is_k += p_K[i] * p_hypergeometric(N, i, n, k);
320 }
321 }
322 return(p_T_is_k_when_S_is_K * p_S_is_K / p_T_is_k);
323 }
324
325
326 static inline uint_fast8_t common_bits(uint_fast8_t bytes_diff)
327 {
328 static const uint_fast8_t common_bits_LUT[256] = {
329 8, 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 5, 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 6, 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 5, 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 7, 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 5, 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 6, 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 5, 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 };
346
347 return common_bits_LUT[bytes_diff];
348 }
349
350 static void Tests()
351 {
352 // printf("Tests: Partial Statelist sizes\n");
353 // for (uint16_t i = 0; i <= 16; i+=2) {
354 // printf("Partial State List Odd [%2d] has %8d entries\n", i, partial_statelist[i].len[ODD_STATE]);
355 // }
356 // for (uint16_t i = 0; i <= 16; i+=2) {
357 // printf("Partial State List Even [%2d] has %8d entries\n", i, partial_statelist[i].len[EVEN_STATE]);
358 // }
359
360 // #define NUM_STATISTICS 100000
361 // uint32_t statistics_odd[17];
362 // uint64_t statistics[257];
363 // uint32_t statistics_even[17];
364 // struct Crypto1State cs;
365 // time_t time1 = clock();
366
367 // for (uint16_t i = 0; i < 257; i++) {
368 // statistics[i] = 0;
369 // }
370 // for (uint16_t i = 0; i < 17; i++) {
371 // statistics_odd[i] = 0;
372 // statistics_even[i] = 0;
373 // }
374
375 // for (uint64_t i = 0; i < NUM_STATISTICS; i++) {
376 // cs.odd = (rand() & 0xfff) << 12 | (rand() & 0xfff);
377 // cs.even = (rand() & 0xfff) << 12 | (rand() & 0xfff);
378 // uint16_t sum_property = SumProperty(&cs);
379 // statistics[sum_property] += 1;
380 // sum_property = PartialSumProperty(cs.even, EVEN_STATE);
381 // statistics_even[sum_property]++;
382 // sum_property = PartialSumProperty(cs.odd, ODD_STATE);
383 // statistics_odd[sum_property]++;
384 // if (i%(NUM_STATISTICS/100) == 0) printf(".");
385 // }
386
387 // 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);
388 // for (uint16_t i = 0; i < 257; i++) {
389 // if (statistics[i] != 0) {
390 // printf("probability[%3d] = %0.5f\n", i, (float)statistics[i]/NUM_STATISTICS);
391 // }
392 // }
393 // for (uint16_t i = 0; i <= 16; i++) {
394 // if (statistics_odd[i] != 0) {
395 // printf("probability odd [%2d] = %0.5f\n", i, (float)statistics_odd[i]/NUM_STATISTICS);
396 // }
397 // }
398 // for (uint16_t i = 0; i <= 16; i++) {
399 // if (statistics_odd[i] != 0) {
400 // printf("probability even [%2d] = %0.5f\n", i, (float)statistics_even[i]/NUM_STATISTICS);
401 // }
402 // }
403
404 // printf("Tests: Sum Probabilities based on Partial Sums\n");
405 // for (uint16_t i = 0; i < 257; i++) {
406 // statistics[i] = 0;
407 // }
408 // uint64_t num_states = 0;
409 // for (uint16_t oddsum = 0; oddsum <= 16; oddsum += 2) {
410 // for (uint16_t evensum = 0; evensum <= 16; evensum += 2) {
411 // uint16_t sum = oddsum*(16-evensum) + (16-oddsum)*evensum;
412 // statistics[sum] += (uint64_t)partial_statelist[oddsum].len[ODD_STATE] * partial_statelist[evensum].len[EVEN_STATE] * (1<<8);
413 // num_states += (uint64_t)partial_statelist[oddsum].len[ODD_STATE] * partial_statelist[evensum].len[EVEN_STATE] * (1<<8);
414 // }
415 // }
416 // printf("num_states = %lld, expected %lld\n", num_states, (1LL<<48));
417 // for (uint16_t i = 0; i < 257; i++) {
418 // if (statistics[i] != 0) {
419 // printf("probability[%3d] = %0.5f\n", i, (float)statistics[i]/num_states);
420 // }
421 // }
422
423 // printf("\nTests: Hypergeometric Probability for selected parameters\n");
424 // printf("p_hypergeometric(256, 206, 255, 206) = %0.8f\n", p_hypergeometric(256, 206, 255, 206));
425 // printf("p_hypergeometric(256, 206, 255, 205) = %0.8f\n", p_hypergeometric(256, 206, 255, 205));
426 // printf("p_hypergeometric(256, 156, 1, 1) = %0.8f\n", p_hypergeometric(256, 156, 1, 1));
427 // printf("p_hypergeometric(256, 156, 1, 0) = %0.8f\n", p_hypergeometric(256, 156, 1, 0));
428 // printf("p_hypergeometric(256, 1, 1, 1) = %0.8f\n", p_hypergeometric(256, 1, 1, 1));
429 // printf("p_hypergeometric(256, 1, 1, 0) = %0.8f\n", p_hypergeometric(256, 1, 1, 0));
430
431 // struct Crypto1State *pcs;
432 // pcs = crypto1_create(0xffffffffffff);
433 // printf("\nTests: for key = 0xffffffffffff:\nSum(a0) = %d\nodd_state = 0x%06x\neven_state = 0x%06x\n",
434 // SumProperty(pcs), pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff);
435 // crypto1_byte(pcs, (cuid >> 24) ^ best_first_bytes[0], true);
436 // printf("After adding best first byte 0x%02x:\nSum(a8) = %d\nodd_state = 0x%06x\neven_state = 0x%06x\n",
437 // best_first_bytes[0],
438 // SumProperty(pcs),
439 // pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff);
440 // //test_state_odd = pcs->odd & 0x00ffffff;
441 // //test_state_even = pcs->even & 0x00ffffff;
442 // crypto1_destroy(pcs);
443 // pcs = crypto1_create(0xa0a1a2a3a4a5);
444 // printf("Tests: for key = 0xa0a1a2a3a4a5:\nSum(a0) = %d\nodd_state = 0x%06x\neven_state = 0x%06x\n",
445 // SumProperty(pcs), pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff);
446 // crypto1_byte(pcs, (cuid >> 24) ^ best_first_bytes[0], true);
447 // printf("After adding best first byte 0x%02x:\nSum(a8) = %d\nodd_state = 0x%06x\neven_state = 0x%06x\n",
448 // best_first_bytes[0],
449 // SumProperty(pcs),
450 // pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff);
451 // //test_state_odd = pcs->odd & 0x00ffffff;
452 // //test_state_even = pcs->even & 0x00ffffff;
453 // crypto1_destroy(pcs);
454 // pcs = crypto1_create(0xa6b9aa97b955);
455 // printf("Tests: for key = 0xa6b9aa97b955:\nSum(a0) = %d\nodd_state = 0x%06x\neven_state = 0x%06x\n",
456 // SumProperty(pcs), pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff);
457 // crypto1_byte(pcs, (cuid >> 24) ^ best_first_bytes[0], true);
458 // printf("After adding best first byte 0x%02x:\nSum(a8) = %d\nodd_state = 0x%06x\neven_state = 0x%06x\n",
459 // best_first_bytes[0],
460 // SumProperty(pcs),
461 // pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff);
462 //test_state_odd = pcs->odd & 0x00ffffff;
463 //test_state_even = pcs->even & 0x00ffffff;
464 // crypto1_destroy(pcs);
465
466
467 // 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));
468
469 // printf("\nTests: Actual BitFlipProperties odd/even:\n");
470 // for (uint16_t i = 0; i < 256; i++) {
471 // printf("[%02x]:%c ", i, nonces[i].BitFlip[ODD_STATE]?'o':nonces[i].BitFlip[EVEN_STATE]?'e':' ');
472 // if (i % 8 == 7) {
473 // printf("\n");
474 // }
475 // }
476
477 // printf("\nTests: Sorted First Bytes:\n");
478 // for (uint16_t i = 0; i < 256; i++) {
479 // uint8_t best_byte = best_first_bytes[i];
480 // printf("#%03d Byte: %02x, n = %3d, k = %3d, Sum(a8): %3d, Confidence: %5.1f%%, Bitflip: %c\n",
481 // //printf("#%03d Byte: %02x, n = %3d, k = %3d, Sum(a8): %3d, Confidence: %5.1f%%, Bitflip: %c, score1: %1.5f, score2: %1.0f\n",
482 // i, best_byte,
483 // nonces[best_byte].num,
484 // nonces[best_byte].Sum,
485 // nonces[best_byte].Sum8_guess,
486 // nonces[best_byte].Sum8_prob * 100,
487 // nonces[best_byte].BitFlip[ODD_STATE]?'o':nonces[best_byte].BitFlip[EVEN_STATE]?'e':' '
488 // //nonces[best_byte].score1,
489 // //nonces[best_byte].score2
490 // );
491 // }
492
493 // printf("\nTests: parity performance\n");
494 // time_t time1p = clock();
495 // uint32_t par_sum = 0;
496 // for (uint32_t i = 0; i < 100000000; i++) {
497 // par_sum += parity(i);
498 // }
499 // printf("parsum oldparity = %d, time = %1.5fsec\n", par_sum, (float)(clock() - time1p)/CLOCKS_PER_SEC);
500
501 // time1p = clock();
502 // par_sum = 0;
503 // for (uint32_t i = 0; i < 100000000; i++) {
504 // par_sum += evenparity32(i);
505 // }
506 // printf("parsum newparity = %d, time = %1.5fsec\n", par_sum, (float)(clock() - time1p)/CLOCKS_PER_SEC);
507
508
509 }
510
511 static void sort_best_first_bytes(void)
512 {
513 // sort based on probability for correct guess
514 for (uint16_t i = 0; i < 256; i++ ) {
515 uint16_t j = 0;
516 float prob1 = nonces[i].Sum8_prob;
517 float prob2 = nonces[best_first_bytes[0]].Sum8_prob;
518 while (prob1 < prob2 && j < i) {
519 prob2 = nonces[best_first_bytes[++j]].Sum8_prob;
520 }
521 if (j < i) {
522 for (uint16_t k = i; k > j; k--) {
523 best_first_bytes[k] = best_first_bytes[k-1];
524 }
525 }
526 best_first_bytes[j] = i;
527 }
528
529 // determine how many are above the CONFIDENCE_THRESHOLD
530 uint16_t num_good_nonces = 0;
531 for (uint16_t i = 0; i < 256; i++) {
532 if (nonces[best_first_bytes[i]].Sum8_prob >= CONFIDENCE_THRESHOLD) {
533 ++num_good_nonces;
534 }
535 }
536
537 uint16_t best_first_byte = 0;
538
539 // select the best possible first byte based on number of common bits with all {b'}
540 // uint16_t max_common_bits = 0;
541 // for (uint16_t i = 0; i < num_good_nonces; i++) {
542 // uint16_t sum_common_bits = 0;
543 // for (uint16_t j = 0; j < num_good_nonces; j++) {
544 // if (i != j) {
545 // sum_common_bits += common_bits(best_first_bytes[i],best_first_bytes[j]);
546 // }
547 // }
548 // if (sum_common_bits > max_common_bits) {
549 // max_common_bits = sum_common_bits;
550 // best_first_byte = i;
551 // }
552 // }
553
554 // select best possible first byte {b} based on least likely sum/bitflip property
555 float min_p_K = 1.0;
556 for (uint16_t i = 0; i < num_good_nonces; i++ ) {
557 uint16_t sum8 = nonces[best_first_bytes[i]].Sum8_guess;
558 float bitflip_prob = 1.0;
559 if (nonces[best_first_bytes[i]].BitFlip[ODD_STATE] || nonces[best_first_bytes[i]].BitFlip[EVEN_STATE]) {
560 bitflip_prob = 0.09375;
561 }
562 nonces[best_first_bytes[i]].score1 = p_K[sum8] * bitflip_prob;
563 if (p_K[sum8] * bitflip_prob <= min_p_K) {
564 min_p_K = p_K[sum8] * bitflip_prob;
565 }
566 }
567
568
569 // use number of commmon bits as a tie breaker
570 uint16_t max_common_bits = 0;
571 for (uint16_t i = 0; i < num_good_nonces; i++) {
572 float bitflip_prob = 1.0;
573 if (nonces[best_first_bytes[i]].BitFlip[ODD_STATE] || nonces[best_first_bytes[i]].BitFlip[EVEN_STATE]) {
574 bitflip_prob = 0.09375;
575 }
576 if (p_K[nonces[best_first_bytes[i]].Sum8_guess] * bitflip_prob == min_p_K) {
577 uint16_t sum_common_bits = 0;
578 for (uint16_t j = 0; j < num_good_nonces; j++) {
579 sum_common_bits += common_bits(best_first_bytes[i] ^ best_first_bytes[j]);
580 }
581 nonces[best_first_bytes[i]].score2 = sum_common_bits;
582 if (sum_common_bits > max_common_bits) {
583 max_common_bits = sum_common_bits;
584 best_first_byte = i;
585 }
586 }
587 }
588
589 // swap best possible first byte to the pole position
590 uint16_t temp = best_first_bytes[0];
591 best_first_bytes[0] = best_first_bytes[best_first_byte];
592 best_first_bytes[best_first_byte] = temp;
593
594 }
595
596 static uint16_t estimate_second_byte_sum(void)
597 {
598
599 for (uint16_t first_byte = 0; first_byte < 256; first_byte++) {
600 float Sum8_prob = 0.0;
601 uint16_t Sum8 = 0;
602 if (nonces[first_byte].updated) {
603 for (uint16_t sum = 0; sum <= 256; sum++) {
604 float prob = sum_probability(sum, nonces[first_byte].num, nonces[first_byte].Sum);
605 if (prob > Sum8_prob) {
606 Sum8_prob = prob;
607 Sum8 = sum;
608 }
609 }
610 nonces[first_byte].Sum8_guess = Sum8;
611 nonces[first_byte].Sum8_prob = Sum8_prob;
612 nonces[first_byte].updated = false;
613 }
614 }
615
616 sort_best_first_bytes();
617
618 uint16_t num_good_nonces = 0;
619 for (uint16_t i = 0; i < 256; i++) {
620 if (nonces[best_first_bytes[i]].Sum8_prob >= CONFIDENCE_THRESHOLD) {
621 ++num_good_nonces;
622 }
623 }
624
625 return num_good_nonces;
626 }
627
628 static int read_nonce_file(void)
629 {
630 FILE *fnonces = NULL;
631 uint8_t trgBlockNo = 0;
632 uint8_t trgKeyType = 0;
633 uint8_t read_buf[9];
634 uint32_t nt_enc1 = 0, nt_enc2 = 0;
635 uint8_t par_enc = 0;
636 int total_num_nonces = 0;
637
638 if ((fnonces = fopen("nonces.bin","rb")) == NULL) {
639 PrintAndLog("Could not open file nonces.bin");
640 return 1;
641 }
642
643 PrintAndLog("Reading nonces from file nonces.bin...");
644 size_t bytes_read = fread(read_buf, 1, 6, fnonces);
645 if ( bytes_read == 0) {
646 PrintAndLog("File reading error.");
647 fclose(fnonces);
648 return 1;
649 }
650 cuid = bytes_to_num(read_buf, 4);
651 trgBlockNo = bytes_to_num(read_buf+4, 1);
652 trgKeyType = bytes_to_num(read_buf+5, 1);
653
654 while (fread(read_buf, 1, 9, fnonces) == 9) {
655 nt_enc1 = bytes_to_num(read_buf, 4);
656 nt_enc2 = bytes_to_num(read_buf+4, 4);
657 par_enc = bytes_to_num(read_buf+8, 1);
658 //printf("Encrypted nonce: %08x, encrypted_parity: %02x\n", nt_enc1, par_enc >> 4);
659 //printf("Encrypted nonce: %08x, encrypted_parity: %02x\n", nt_enc2, par_enc & 0x0f);
660 add_nonce(nt_enc1, par_enc >> 4);
661 add_nonce(nt_enc2, par_enc & 0x0f);
662 total_num_nonces += 2;
663 }
664 fclose(fnonces);
665 PrintAndLog("Read %d nonces from file. cuid=%08x, Block=%d, Keytype=%c", total_num_nonces, cuid, trgBlockNo, trgKeyType==0?'A':'B');
666 return 0;
667 }
668
669 static void Check_for_FilterFlipProperties(void)
670 {
671 printf("Checking for Filter Flip Properties...\n");
672
673 uint16_t num_bitflips = 0;
674
675 for (uint16_t i = 0; i < 256; i++) {
676 nonces[i].BitFlip[ODD_STATE] = false;
677 nonces[i].BitFlip[EVEN_STATE] = false;
678 }
679
680 for (uint16_t i = 0; i < 256; i++) {
681 uint8_t parity1 = (nonces[i].first->par_enc) >> 3; // parity of first byte
682 uint8_t parity2_odd = (nonces[i^0x80].first->par_enc) >> 3; // XOR 0x80 = last bit flipped
683 uint8_t parity2_even = (nonces[i^0x40].first->par_enc) >> 3; // XOR 0x40 = second last bit flipped
684
685 if (parity1 == parity2_odd) { // has Bit Flip Property for odd bits
686 nonces[i].BitFlip[ODD_STATE] = true;
687 num_bitflips++;
688 } else if (parity1 == parity2_even) { // has Bit Flip Property for even bits
689 nonces[i].BitFlip[EVEN_STATE] = true;
690 num_bitflips++;
691 }
692 }
693
694 if (write_stats) {
695 fprintf(fstats, "%d;", num_bitflips);
696 }
697 }
698
699 static void simulate_MFplus_RNG(uint32_t test_cuid, uint64_t test_key, uint32_t *nt_enc, uint8_t *par_enc)
700 {
701 struct Crypto1State sim_cs = {0, 0};
702 // init cryptostate with key:
703 for(int8_t i = 47; i > 0; i -= 2) {
704 sim_cs.odd = sim_cs.odd << 1 | BIT(test_key, (i - 1) ^ 7);
705 sim_cs.even = sim_cs.even << 1 | BIT(test_key, i ^ 7);
706 }
707
708 *par_enc = 0;
709 uint32_t nt = (rand() & 0xff) << 24 | (rand() & 0xff) << 16 | (rand() & 0xff) << 8 | (rand() & 0xff);
710 for (int8_t byte_pos = 3; byte_pos >= 0; byte_pos--) {
711 uint8_t nt_byte_dec = (nt >> (8*byte_pos)) & 0xff;
712 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
713 *nt_enc = (*nt_enc << 8) | nt_byte_enc;
714 uint8_t ks_par = filter(sim_cs.odd); // the keystream bit to encode/decode the parity bit
715 uint8_t nt_byte_par_enc = ks_par ^ oddparity8(nt_byte_dec); // determine the nt byte's parity and encode it
716 *par_enc = (*par_enc << 1) | nt_byte_par_enc;
717 }
718
719 }
720
721 static void simulate_acquire_nonces()
722 {
723 clock_t time1 = clock();
724 bool filter_flip_checked = false;
725 uint32_t total_num_nonces = 0;
726 uint32_t next_fivehundred = 500;
727 uint32_t total_added_nonces = 0;
728
729 cuid = (rand() & 0xff) << 24 | (rand() & 0xff) << 16 | (rand() & 0xff) << 8 | (rand() & 0xff);
730 known_target_key = ((uint64_t)rand() & 0xfff) << 36 | ((uint64_t)rand() & 0xfff) << 24 | ((uint64_t)rand() & 0xfff) << 12 | ((uint64_t)rand() & 0xfff);
731
732 printf("Simulating nonce acquisition for target key %012"llx", cuid %08x ...\n", known_target_key, cuid);
733 fprintf(fstats, "%012"llx";%08x;", known_target_key, cuid);
734
735 do {
736 uint32_t nt_enc = 0;
737 uint8_t par_enc = 0;
738
739 simulate_MFplus_RNG(cuid, known_target_key, &nt_enc, &par_enc);
740 //printf("Simulated RNG: nt_enc1: %08x, nt_enc2: %08x, par_enc: %02x\n", nt_enc1, nt_enc2, par_enc);
741 total_added_nonces += add_nonce(nt_enc, par_enc);
742 total_num_nonces++;
743
744 if (first_byte_num == 256 ) {
745 // printf("first_byte_num = %d, first_byte_Sum = %d\n", first_byte_num, first_byte_Sum);
746 if (!filter_flip_checked) {
747 Check_for_FilterFlipProperties();
748 filter_flip_checked = true;
749 }
750 num_good_first_bytes = estimate_second_byte_sum();
751 if (total_num_nonces > next_fivehundred) {
752 next_fivehundred = (total_num_nonces/500+1) * 500;
753 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",
754 total_num_nonces,
755 total_added_nonces,
756 CONFIDENCE_THRESHOLD * 100.0,
757 num_good_first_bytes);
758 }
759 }
760
761 } while (num_good_first_bytes < GOOD_BYTES_REQUIRED);
762
763 time1 = clock() - time1;
764 if ( time1 > 0 ) {
765 PrintAndLog("Acquired a total of %d nonces in %1.1f seconds (%0.0f nonces/minute)",
766 total_num_nonces,
767 ((float)time1)/CLOCKS_PER_SEC,
768 total_num_nonces * 60.0 * CLOCKS_PER_SEC/(float)time1);
769 }
770 fprintf(fstats, "%d;%d;%d;%1.2f;", total_num_nonces, total_added_nonces, num_good_first_bytes, CONFIDENCE_THRESHOLD);
771
772 }
773
774 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)
775 {
776 clock_t time1 = clock();
777 bool initialize = true;
778 bool finished = false;
779 bool filter_flip_checked = false;
780 uint32_t flags = 0;
781 uint8_t write_buf[9];
782 uint32_t total_num_nonces = 0;
783 uint32_t next_fivehundred = 500;
784 uint32_t total_added_nonces = 0;
785 uint32_t idx = 1;
786 FILE *fnonces = NULL;
787 UsbCommand resp;
788
789 field_off = false;
790 cracking = false;
791
792 printf("Acquiring nonces...\n");
793
794 clearCommandBuffer();
795
796 do {
797 if (cracking) {
798 sleep(3);
799 continue;
800 }
801
802 flags = 0;
803 flags |= initialize ? 0x0001 : 0;
804 flags |= slow ? 0x0002 : 0;
805 flags |= field_off ? 0x0004 : 0;
806 UsbCommand c = {CMD_MIFARE_ACQUIRE_ENCRYPTED_NONCES, {blockNo + keyType * 0x100, trgBlockNo + trgKeyType * 0x100, flags}};
807 memcpy(c.d.asBytes, key, 6);
808
809 SendCommand(&c);
810
811 if (field_off) finished = true;
812
813 if (initialize) {
814 if (!WaitForResponseTimeout(CMD_ACK, &resp, 3000)) return 1;
815 if (resp.arg[0]) return resp.arg[0]; // error during nested_hard
816
817 cuid = resp.arg[1];
818 // PrintAndLog("Acquiring nonces for CUID 0x%08x", cuid);
819 if (nonce_file_write && fnonces == NULL) {
820 if ((fnonces = fopen("nonces.bin","wb")) == NULL) {
821 PrintAndLog("Could not create file nonces.bin");
822 return 3;
823 }
824 PrintAndLog("Writing acquired nonces to binary file nonces.bin");
825 num_to_bytes(cuid, 4, write_buf);
826 fwrite(write_buf, 1, 4, fnonces);
827 fwrite(&trgBlockNo, 1, 1, fnonces);
828 fwrite(&trgKeyType, 1, 1, fnonces);
829 }
830 }
831
832 if (!initialize) {
833 uint32_t nt_enc1, nt_enc2;
834 uint8_t par_enc;
835 uint16_t num_acquired_nonces = resp.arg[2];
836 uint8_t *bufp = resp.d.asBytes;
837 for (uint16_t i = 0; i < num_acquired_nonces; i+=2) {
838 nt_enc1 = bytes_to_num(bufp, 4);
839 nt_enc2 = bytes_to_num(bufp+4, 4);
840 par_enc = bytes_to_num(bufp+8, 1);
841
842 //printf("Encrypted nonce: %08x, encrypted_parity: %02x\n", nt_enc1, par_enc >> 4);
843 total_added_nonces += add_nonce(nt_enc1, par_enc >> 4);
844 //printf("Encrypted nonce: %08x, encrypted_parity: %02x\n", nt_enc2, par_enc & 0x0f);
845 total_added_nonces += add_nonce(nt_enc2, par_enc & 0x0f);
846
847 if (nonce_file_write) {
848 fwrite(bufp, 1, 9, fnonces);
849 }
850
851 bufp += 9;
852 }
853
854 total_num_nonces += num_acquired_nonces;
855 }
856
857 if (first_byte_num == 256 && !field_off) {
858 // printf("first_byte_num = %d, first_byte_Sum = %d\n", first_byte_num, first_byte_Sum);
859 if (!filter_flip_checked) {
860 Check_for_FilterFlipProperties();
861 filter_flip_checked = true;
862 }
863
864 num_good_first_bytes = estimate_second_byte_sum();
865 if (total_num_nonces > next_fivehundred) {
866 next_fivehundred = (total_num_nonces/500+1) * 500;
867 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",
868 total_num_nonces,
869 total_added_nonces,
870 CONFIDENCE_THRESHOLD * 100.0,
871 num_good_first_bytes);
872 }
873
874 if (thread_check_started) {
875 if (thread_check_done) {
876 //printf ("Detect check thread end ..\n");
877 pthread_join (thread_check, 0);
878 idx = cargs.idx;
879 thread_check_started = thread_check_done = false;
880 }
881 } else {
882 //printf ("Starting check thread ...\n");
883 memset (&cargs, 0, sizeof (cargs));
884
885 // set arguments
886 cargs.next_fivehundred = next_fivehundred;
887 cargs.total_num_nonces = total_num_nonces;
888 cargs.total_added_nonces = total_added_nonces;
889 cargs.idx = idx;
890
891 pthread_create (&thread_check, NULL, check_thread, (void *)&cargs);
892 thread_check_started = true;
893 }
894 }
895
896 if (!initialize) {
897 if (!WaitForResponseTimeout(CMD_ACK, &resp, 3000)) {
898 fclose(fnonces);
899 return 1;
900 }
901
902 if (resp.arg[0]) {
903 fclose(fnonces);
904 return resp.arg[0]; // error during nested_hard
905 }
906 }
907
908 initialize = false;
909
910 } while (!finished);
911
912 if (nonce_file_write) {
913 fclose(fnonces);
914 }
915
916 time1 = clock() - time1;
917 if ( time1 > 0 ) {
918 PrintAndLog("Acquired a total of %d nonces in %1.1f seconds (%0.0f nonces/minute)",
919 total_num_nonces,
920 ((float)time1)/CLOCKS_PER_SEC,
921 total_num_nonces * 60.0 * CLOCKS_PER_SEC/(float)time1
922 );
923 }
924 return 0;
925 }
926
927 static int init_partial_statelists(void)
928 {
929 const uint32_t sizes_odd[17] = { 126757, 0, 18387, 0, 74241, 0, 181737, 0, 248801, 0, 182033, 0, 73421, 0, 17607, 0, 125601 };
930 const uint32_t sizes_even[17] = { 125723, 0, 17867, 0, 74305, 0, 178707, 0, 248801, 0, 185063, 0, 73356, 0, 18127, 0, 126634 };
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;
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 float kcalc = log(maximum_states)/log(2.0);
1384 printf("Number of remaining possible keys: %"PRIu64" (2^%1.1f)\n", maximum_states, kcalc);
1385 if (write_stats) {
1386 if (maximum_states != 0) {
1387 fprintf(fstats, "%1.1f;", kcalc);
1388 } else {
1389 fprintf(fstats, "%1.1f;", 0.0);
1390 }
1391 }
1392 if (kcalc < 39.00f) return true;
1393
1394 return false;
1395 }
1396
1397 static void free_candidates_memory(statelist_t *sl)
1398 {
1399 if (sl == NULL) {
1400 return;
1401 } else {
1402 free_candidates_memory(sl->next);
1403 free(sl);
1404 }
1405 }
1406
1407 static void free_statelist_cache(void)
1408 {
1409 for (uint16_t i = 0; i < 17; i+=2) {
1410 for (uint16_t j = 0; j < 17; j+=2) {
1411 for (uint16_t k = 0; k < 2; k++) {
1412 free(sl_cache[i][j][k].sl);
1413 }
1414 }
1415 }
1416 }
1417
1418 uint64_t foundkey = 0;
1419 size_t keys_found = 0;
1420 size_t bucket_count = 0;
1421 statelist_t* buckets[128];
1422 size_t total_states_tested = 0;
1423 size_t thread_count = 4;
1424
1425 // these bitsliced states will hold identical states in all slices
1426 bitslice_t bitsliced_rollback_byte[ROLLBACK_SIZE];
1427
1428 // arrays of bitsliced states with identical values in all slices
1429 bitslice_t bitsliced_encrypted_nonces[NONCE_TESTS][STATE_SIZE];
1430 bitslice_t bitsliced_encrypted_parity_bits[NONCE_TESTS][ROLLBACK_SIZE];
1431
1432 #define EXACT_COUNT
1433
1434 static const uint64_t crack_states_bitsliced(statelist_t *p){
1435 // the idea to roll back the half-states before combining them was suggested/explained to me by bla
1436 // 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
1437 uint64_t key = -1;
1438 uint8_t bSize = sizeof(bitslice_t);
1439
1440 #ifdef EXACT_COUNT
1441 size_t bucket_states_tested = 0;
1442 size_t bucket_size[p->len[EVEN_STATE]/MAX_BITSLICES];
1443 #else
1444 const size_t bucket_states_tested = (p->len[EVEN_STATE])*(p->len[ODD_STATE]);
1445 #endif
1446
1447 bitslice_t *bitsliced_even_states[p->len[EVEN_STATE]/MAX_BITSLICES];
1448 size_t bitsliced_blocks = 0;
1449 uint32_t const * restrict even_end = p->states[EVEN_STATE]+p->len[EVEN_STATE];
1450
1451 // bitslice all the even states
1452 for(uint32_t * restrict p_even = p->states[EVEN_STATE]; p_even < even_end; p_even += MAX_BITSLICES){
1453
1454 #ifdef __WIN32
1455 #ifdef __MINGW32__
1456 bitslice_t * restrict lstate_p = __mingw_aligned_malloc((STATE_SIZE+ROLLBACK_SIZE) * bSize, bSize);
1457 #else
1458 bitslice_t * restrict lstate_p = _aligned_malloc((STATE_SIZE+ROLLBACK_SIZE) * bSize, bSize);
1459 #endif
1460 #else
1461 #ifdef __APPLE__
1462 bitslice_t * restrict lstate_p = malloc((STATE_SIZE+ROLLBACK_SIZE) * bSize);
1463 #else
1464 bitslice_t * restrict lstate_p = memalign(bSize, (STATE_SIZE+ROLLBACK_SIZE) * bSize);
1465 #endif
1466 #endif
1467
1468 if ( !lstate_p ) {
1469 __sync_fetch_and_add(&total_states_tested, bucket_states_tested);
1470 return key;
1471 }
1472
1473 memset(lstate_p+1, 0x0, (STATE_SIZE-1)*sizeof(bitslice_t)); // zero even bits
1474
1475 // bitslice even half-states
1476 const size_t max_slices = (even_end-p_even) < MAX_BITSLICES ? even_end-p_even : MAX_BITSLICES;
1477 #ifdef EXACT_COUNT
1478 bucket_size[bitsliced_blocks] = max_slices;
1479 #endif
1480 for(size_t slice_idx = 0; slice_idx < max_slices; ++slice_idx){
1481 uint32_t e = *(p_even+slice_idx);
1482 for(size_t bit_idx = 1; bit_idx < STATE_SIZE; bit_idx+=2, e >>= 1){
1483 // set even bits
1484 if(e&1){
1485 lstate_p[bit_idx].bytes64[slice_idx>>6] |= 1ull << (slice_idx&63);
1486 }
1487 }
1488 }
1489 // compute the rollback bits
1490 for(size_t rollback = 0; rollback < ROLLBACK_SIZE; ++rollback){
1491 // inlined crypto1_bs_lfsr_rollback
1492 const bitslice_value_t feedout = lstate_p[0].value;
1493 ++lstate_p;
1494 const bitslice_value_t ks_bits = crypto1_bs_f20(lstate_p);
1495 const bitslice_value_t feedback = (feedout ^ ks_bits ^ lstate_p[47- 5].value ^ lstate_p[47- 9].value ^
1496 lstate_p[47-10].value ^ lstate_p[47-12].value ^ lstate_p[47-14].value ^
1497 lstate_p[47-15].value ^ lstate_p[47-17].value ^ lstate_p[47-19].value ^
1498 lstate_p[47-24].value ^ lstate_p[47-25].value ^ lstate_p[47-27].value ^
1499 lstate_p[47-29].value ^ lstate_p[47-35].value ^ lstate_p[47-39].value ^
1500 lstate_p[47-41].value ^ lstate_p[47-42].value ^ lstate_p[47-43].value);
1501 lstate_p[47].value = feedback ^ bitsliced_rollback_byte[rollback].value;
1502 }
1503 bitsliced_even_states[bitsliced_blocks++] = lstate_p;
1504 }
1505
1506 // bitslice every odd state to every block of even half-states with half-finished rollback
1507 for(uint32_t const * restrict p_odd = p->states[ODD_STATE]; p_odd < p->states[ODD_STATE]+p->len[ODD_STATE]; ++p_odd){
1508 // early abort
1509 if(keys_found){
1510 goto out;
1511 }
1512
1513 // set the odd bits and compute rollback
1514 uint64_t o = (uint64_t) *p_odd;
1515 lfsr_rollback_byte((struct Crypto1State*) &o, 0, 1);
1516 // pre-compute part of the odd feedback bits (minus rollback)
1517 bool odd_feedback_bit = parity(o&0x9ce5c);
1518
1519 crypto1_bs_rewind_a0();
1520 // set odd bits
1521 for(size_t state_idx = 0; state_idx < STATE_SIZE-ROLLBACK_SIZE; o >>= 1, state_idx+=2){
1522 if(o & 1){
1523 state_p[state_idx] = bs_ones;
1524 } else {
1525 state_p[state_idx] = bs_zeroes;
1526 }
1527 }
1528 const bitslice_value_t odd_feedback = odd_feedback_bit ? bs_ones.value : bs_zeroes.value;
1529
1530 for(size_t block_idx = 0; block_idx < bitsliced_blocks; ++block_idx){
1531 const bitslice_t * const restrict bitsliced_even_state = bitsliced_even_states[block_idx];
1532 size_t state_idx;
1533 // set even bits
1534 for(state_idx = 0; state_idx < STATE_SIZE-ROLLBACK_SIZE; state_idx+=2){
1535 state_p[1+state_idx] = bitsliced_even_state[1+state_idx];
1536 }
1537 // set rollback bits
1538 uint64_t lo = o;
1539 for(; state_idx < STATE_SIZE; lo >>= 1, state_idx+=2){
1540 // set the odd bits and take in the odd rollback bits from the even states
1541 if(lo & 1){
1542 state_p[state_idx].value = ~bitsliced_even_state[state_idx].value;
1543 } else {
1544 state_p[state_idx] = bitsliced_even_state[state_idx];
1545 }
1546
1547 // set the even bits and take in the even rollback bits from the odd states
1548 if((lo >> 32) & 1){
1549 state_p[1+state_idx].value = ~bitsliced_even_state[1+state_idx].value;
1550 } else {
1551 state_p[1+state_idx] = bitsliced_even_state[1+state_idx];
1552 }
1553 }
1554
1555 #ifdef EXACT_COUNT
1556 bucket_states_tested += bucket_size[block_idx];
1557 #endif
1558 // pre-compute first keystream and feedback bit vectors
1559 const bitslice_value_t ksb = crypto1_bs_f20(state_p);
1560 const bitslice_value_t fbb = (odd_feedback ^ state_p[47- 0].value ^ state_p[47- 5].value ^ // take in the even and rollback bits
1561 state_p[47-10].value ^ state_p[47-12].value ^ state_p[47-14].value ^
1562 state_p[47-24].value ^ state_p[47-42].value);
1563
1564 // vector to contain test results (1 = passed, 0 = failed)
1565 bitslice_t results = bs_ones;
1566
1567 for(size_t tests = 0; tests < NONCE_TESTS; ++tests){
1568 size_t parity_bit_idx = 0;
1569 bitslice_value_t fb_bits = fbb;
1570 bitslice_value_t ks_bits = ksb;
1571 state_p = &states[KEYSTREAM_SIZE-1];
1572 bitslice_value_t parity_bit_vector = bs_zeroes.value;
1573
1574 // highest bit is transmitted/received first
1575 for(int32_t ks_idx = KEYSTREAM_SIZE-1; ks_idx >= 0; --ks_idx, --state_p){
1576 // decrypt nonce bits
1577 const bitslice_value_t encrypted_nonce_bit_vector = bitsliced_encrypted_nonces[tests][ks_idx].value;
1578 const bitslice_value_t decrypted_nonce_bit_vector = (encrypted_nonce_bit_vector ^ ks_bits);
1579
1580 // compute real parity bits on the fly
1581 parity_bit_vector ^= decrypted_nonce_bit_vector;
1582
1583 // update state
1584 state_p[0].value = (fb_bits ^ decrypted_nonce_bit_vector);
1585
1586 // compute next keystream bit
1587 ks_bits = crypto1_bs_f20(state_p);
1588
1589 // for each byte:
1590 if((ks_idx&7) == 0){
1591 // get encrypted parity bits
1592 const bitslice_value_t encrypted_parity_bit_vector = bitsliced_encrypted_parity_bits[tests][parity_bit_idx++].value;
1593
1594 // decrypt parity bits
1595 const bitslice_value_t decrypted_parity_bit_vector = (encrypted_parity_bit_vector ^ ks_bits);
1596
1597 // compare actual parity bits with decrypted parity bits and take count in results vector
1598 results.value &= (parity_bit_vector ^ decrypted_parity_bit_vector);
1599
1600 // make sure we still have a match in our set
1601 // if(memcmp(&results, &bs_zeroes, sizeof(bitslice_t)) == 0){
1602
1603 // this is much faster on my gcc, because somehow a memcmp needlessly spills/fills all the xmm registers to/from the stack - ???
1604 // the short-circuiting also helps
1605 if(results.bytes64[0] == 0
1606 #if MAX_BITSLICES > 64
1607 && results.bytes64[1] == 0
1608 #endif
1609 #if MAX_BITSLICES > 128
1610 && results.bytes64[2] == 0
1611 && results.bytes64[3] == 0
1612 #endif
1613 ){
1614 goto stop_tests;
1615 }
1616 // this is about as fast but less portable (requires -std=gnu99)
1617 // asm goto ("ptest %1, %0\n\t"
1618 // "jz %l2" :: "xm" (results.value), "xm" (bs_ones.value) : "cc" : stop_tests);
1619 parity_bit_vector = bs_zeroes.value;
1620 }
1621 // compute next feedback bit vector
1622 fb_bits = (state_p[47- 0].value ^ state_p[47- 5].value ^ state_p[47- 9].value ^
1623 state_p[47-10].value ^ state_p[47-12].value ^ state_p[47-14].value ^
1624 state_p[47-15].value ^ state_p[47-17].value ^ state_p[47-19].value ^
1625 state_p[47-24].value ^ state_p[47-25].value ^ state_p[47-27].value ^
1626 state_p[47-29].value ^ state_p[47-35].value ^ state_p[47-39].value ^
1627 state_p[47-41].value ^ state_p[47-42].value ^ state_p[47-43].value);
1628 }
1629 }
1630 // all nonce tests were successful: we've found the key in this block!
1631 state_t keys[MAX_BITSLICES];
1632 crypto1_bs_convert_states(&states[KEYSTREAM_SIZE], keys);
1633 for(size_t results_idx = 0; results_idx < MAX_BITSLICES; ++results_idx){
1634 if(get_vector_bit(results_idx, results)){
1635 key = keys[results_idx].value;
1636 goto out;
1637 }
1638 }
1639 stop_tests:
1640 // prepare to set new states
1641 crypto1_bs_rewind_a0();
1642 continue;
1643 }
1644 }
1645
1646 out:
1647 for(size_t block_idx = 0; block_idx < bitsliced_blocks; ++block_idx){
1648
1649 #ifdef __WIN32
1650 #ifdef __MINGW32__
1651 __mingw_aligned_free(bitsliced_even_states[block_idx]-ROLLBACK_SIZE);
1652 #else
1653 _aligned_free(bitsliced_even_states[block_idx]-ROLLBACK_SIZE);
1654 #endif
1655 #else
1656 free(bitsliced_even_states[block_idx]-ROLLBACK_SIZE);
1657 #endif
1658
1659 }
1660 __sync_fetch_and_add(&total_states_tested, bucket_states_tested);
1661 return key;
1662 }
1663
1664 static void* check_thread(void* x)
1665 {
1666 check_args_t *cargs = (check_args_t *)x;
1667
1668 // printf("first_byte_num = %d, first_byte_Sum = %d\n", first_byte_num, first_byte_Sum);
1669 num_good_first_bytes = estimate_second_byte_sum();
1670 if (cargs->total_added_nonces > (2500*cargs->idx)) {
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 cargs->idx++;
1677 }
1678
1679 if (cracking || num_good_first_bytes >= GOOD_BYTES_REQUIRED) {
1680 if (cargs->total_added_nonces > 2500+1000) {
1681 field_off = brute_force(); // switch off field with next SendCommand and then finish
1682 }
1683 cracking = false;
1684 }
1685
1686 thread_check_done = true;
1687
1688 return (void *) NULL;
1689 }
1690
1691 static void* crack_states_thread(void* x){
1692 const size_t thread_id = (size_t)x;
1693 size_t current_bucket = thread_id;
1694 while(current_bucket < bucket_count){
1695 statelist_t * bucket = buckets[current_bucket];
1696 if(bucket){
1697 const uint64_t key = crack_states_bitsliced(bucket);
1698 if(key != -1){
1699 __sync_fetch_and_add(&keys_found, 1);
1700 __sync_fetch_and_add(&foundkey, key);
1701 break;
1702 } else if(keys_found){
1703 break;
1704 } else {
1705 printf(".");
1706 fflush(stdout);
1707 }
1708 }
1709 current_bucket += thread_count;
1710 }
1711 return NULL;
1712 }
1713
1714 static bool brute_force(void)
1715 {
1716 bool ret = false;
1717 if (known_target_key != -1) {
1718 PrintAndLog("Looking for known target key in remaining key space...");
1719 ret = TestIfKeyExists(known_target_key);
1720 } else {
1721 if (maximum_states == 0) return false;
1722
1723 PrintAndLog("Brute force phase starting.");
1724 time_t start, end;
1725 time(&start);
1726 keys_found = 0;
1727 foundkey = 0;
1728
1729 crypto1_bs_init();
1730
1731 PrintAndLog("Using %u-bit bitslices", MAX_BITSLICES);
1732 PrintAndLog("Bitslicing best_first_byte^uid[3] (rollback byte): %02x...", best_first_bytes[0]^(cuid>>24));
1733 // convert to 32 bit little-endian
1734 crypto1_bs_bitslice_value32((best_first_bytes[0]<<24)^cuid, bitsliced_rollback_byte, 8);
1735
1736 PrintAndLog("Bitslicing nonces...");
1737 for(size_t tests = 0; tests < NONCE_TESTS; tests++){
1738 uint32_t test_nonce = brute_force_nonces[tests]->nonce_enc;
1739 uint8_t test_parity = brute_force_nonces[tests]->par_enc;
1740 // 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
1741 crypto1_bs_bitslice_value32(cuid^test_nonce, bitsliced_encrypted_nonces[tests], 32);
1742 // convert to 32 bit little-endian
1743 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);
1744 }
1745 total_states_tested = 0;
1746
1747 // count number of states to go
1748 bucket_count = 0;
1749 for (statelist_t *p = candidates; p != NULL; p = p->next) {
1750 buckets[bucket_count] = p;
1751 bucket_count++;
1752 }
1753
1754 #ifndef __WIN32
1755 thread_count = sysconf(_SC_NPROCESSORS_CONF);
1756 if ( thread_count < 1)
1757 thread_count = 1;
1758 #endif /* _WIN32 */
1759
1760 pthread_t threads[thread_count];
1761
1762 // enumerate states using all hardware threads, each thread handles one bucket
1763 PrintAndLog("Starting %u cracking threads to search %u buckets containing a total of %"PRIu64" states...", thread_count, bucket_count, maximum_states);
1764
1765 for(size_t i = 0; i < thread_count; i++){
1766 pthread_create(&threads[i], NULL, crack_states_thread, (void*) i);
1767 }
1768 for(size_t i = 0; i < thread_count; i++){
1769 pthread_join(threads[i], 0);
1770 }
1771
1772 time(&end);
1773 double elapsed_time = difftime(end, start);
1774
1775 if (keys_found && TestIfKeyExists(foundkey)) {
1776 PrintAndLog("Success! Tested %"PRIu32" states, found %u keys after %.f seconds", total_states_tested, keys_found, elapsed_time);
1777 PrintAndLog("\nFound key: %012"PRIx64"\n", foundkey);
1778 ret = true;
1779 } else {
1780 PrintAndLog("Fail! Tested %"PRIu32" states, in %.f seconds", total_states_tested, elapsed_time);
1781 }
1782
1783 // reset this counter for the next call
1784 nonces_to_bruteforce = 0;
1785 }
1786
1787 return ret;
1788 }
1789
1790 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)
1791 {
1792 // initialize Random number generator
1793 time_t t;
1794 srand((unsigned) time(&t));
1795
1796 if (trgkey != NULL) {
1797 known_target_key = bytes_to_num(trgkey, 6);
1798 } else {
1799 known_target_key = -1;
1800 }
1801
1802 init_partial_statelists();
1803 init_BitFlip_statelist();
1804 write_stats = false;
1805
1806 if (tests) {
1807 // set the correct locale for the stats printing
1808 setlocale(LC_ALL, "");
1809 write_stats = true;
1810 if ((fstats = fopen("hardnested_stats.txt","a")) == NULL) {
1811 PrintAndLog("Could not create/open file hardnested_stats.txt");
1812 return 3;
1813 }
1814 for (uint32_t i = 0; i < tests; i++) {
1815 init_nonce_memory();
1816 simulate_acquire_nonces();
1817 Tests();
1818 printf("Sum(a0) = %d\n", first_byte_Sum);
1819 fprintf(fstats, "%d;", first_byte_Sum);
1820 generate_candidates(first_byte_Sum, nonces[best_first_bytes[0]].Sum8_guess);
1821 brute_force();
1822 free_nonces_memory();
1823 free_statelist_cache();
1824 free_candidates_memory(candidates);
1825 candidates = NULL;
1826 }
1827 fclose(fstats);
1828 } else {
1829 init_nonce_memory();
1830 if (nonce_file_read) { // use pre-acquired data from file nonces.bin
1831 if (read_nonce_file() != 0) {
1832 return 3;
1833 }
1834 Check_for_FilterFlipProperties();
1835 num_good_first_bytes = MIN(estimate_second_byte_sum(), GOOD_BYTES_REQUIRED);
1836 } else { // acquire nonces.
1837 uint16_t is_OK = acquire_nonces(blockNo, keyType, key, trgBlockNo, trgKeyType, nonce_file_write, slow);
1838 if (is_OK != 0) {
1839 return is_OK;
1840 }
1841 }
1842
1843 //Tests();
1844
1845 //PrintAndLog("");
1846 //PrintAndLog("Sum(a0) = %d", first_byte_Sum);
1847 // PrintAndLog("Best 10 first bytes: %02x, %02x, %02x, %02x, %02x, %02x, %02x, %02x, %02x, %02x",
1848 // best_first_bytes[0],
1849 // best_first_bytes[1],
1850 // best_first_bytes[2],
1851 // best_first_bytes[3],
1852 // best_first_bytes[4],
1853 // best_first_bytes[5],
1854 // best_first_bytes[6],
1855 // best_first_bytes[7],
1856 // best_first_bytes[8],
1857 // best_first_bytes[9] );
1858
1859 //PrintAndLog("Number of first bytes with confidence > %2.1f%%: %d", CONFIDENCE_THRESHOLD*100.0, num_good_first_bytes);
1860
1861 //clock_t time1 = clock();
1862 //generate_candidates(first_byte_Sum, nonces[best_first_bytes[0]].Sum8_guess);
1863 //time1 = clock() - time1;
1864 //if ( time1 > 0 )
1865 //PrintAndLog("Time for generating key candidates list: %1.0f seconds", ((float)time1)/CLOCKS_PER_SEC);
1866
1867 //brute_force();
1868
1869 free_nonces_memory();
1870 free_statelist_cache();
1871 free_candidates_memory(candidates);
1872 candidates = NULL;
1873 }
1874 return 0;
1875 }
1876
1877
Proxmark3 GIT tracking
Impressum, Datenschutz