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