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


95a6f8d7f04a6a8bf8f0d9b6708ff15d1721efdc
[proxmark3-svn] / client / cmdhfmfhard.c
1 //-----------------------------------------------------------------------------
2 // Copyright (C) 2015 piwi
3 //
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 <stdio.h>
18 #include <stdlib.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 "parity.h"
29
30 // uint32_t test_state_odd = 0;
31 // uint32_t test_state_even = 0;
32
33 #define CONFIDENCE_THRESHOLD 0.95 // Collect nonces until we are certain enough that the following brute force is successfull
34 #define GOOD_BYTES_REQUIRED 30
35
36
37 static const float p_K[257] = { // the probability that a random nonce has a Sum Property == K
38 0.0290, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
39 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
40 0.0000, 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.0083, 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.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
45 0.0006, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
46 0.0339, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
47 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
48 0.0048, 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.0934, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
51 0.0119, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
52 0.0489, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
53 0.0602, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
54 0.4180, 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.0489, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
57 0.0119, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
58 0.0934, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
59 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
60 0.0048, 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.0339, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
63 0.0006, 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.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
66 0.0083, 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.0000, 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.0290 };
71
72
73 typedef struct noncelistentry {
74 uint32_t nonce_enc;
75 uint8_t par_enc;
76 void *next;
77 } noncelistentry_t;
78
79 typedef struct noncelist {
80 uint16_t num;
81 uint16_t Sum;
82 uint16_t Sum8_guess;
83 uint8_t BitFlip[2];
84 float Sum8_prob;
85 bool updated;
86 noncelistentry_t *first;
87 float score1, score2;
88 } noncelist_t;
89
90
91 static uint32_t cuid;
92 static noncelist_t nonces[256];
93 static uint8_t best_first_bytes[256];
94 static uint16_t first_byte_Sum = 0;
95 static uint16_t first_byte_num = 0;
96 static uint16_t num_good_first_bytes = 0;
97 static uint64_t maximum_states = 0;
98 static uint64_t known_target_key;
99 static bool write_stats = false;
100 static FILE *fstats = NULL;
101
102
103 typedef enum {
104 EVEN_STATE = 0,
105 ODD_STATE = 1
106 } odd_even_t;
107
108 #define STATELIST_INDEX_WIDTH 16
109 #define STATELIST_INDEX_SIZE (1<<STATELIST_INDEX_WIDTH)
110
111 typedef struct {
112 uint32_t *states[2];
113 uint32_t len[2];
114 uint32_t *index[2][STATELIST_INDEX_SIZE];
115 } partial_indexed_statelist_t;
116
117 typedef struct {
118 uint32_t *states[2];
119 uint32_t len[2];
120 void* next;
121 } statelist_t;
122
123
124 static partial_indexed_statelist_t partial_statelist[17];
125 static partial_indexed_statelist_t statelist_bitflip;
126
127 static statelist_t *candidates = NULL;
128
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 nonces[first_byte].num++;
173 nonces[first_byte].Sum += evenparity32((nonce_enc & 0x00ff0000) | (par_enc & 0x04));
174 nonces[first_byte].updated = true; // indicates that we need to recalculate the Sum(a8) probability for this first byte
175
176 return (1); // new nonce added
177 }
178
179
180 static void init_nonce_memory(void)
181 {
182 for (uint16_t i = 0; i < 256; i++) {
183 nonces[i].num = 0;
184 nonces[i].Sum = 0;
185 nonces[i].Sum8_guess = 0;
186 nonces[i].Sum8_prob = 0.0;
187 nonces[i].updated = true;
188 nonces[i].first = NULL;
189 }
190 first_byte_num = 0;
191 first_byte_Sum = 0;
192 num_good_first_bytes = 0;
193 }
194
195
196 static void free_nonce_list(noncelistentry_t *p)
197 {
198 if (p == NULL) {
199 return;
200 } else {
201 free_nonce_list(p->next);
202 free(p);
203 }
204 }
205
206
207 static void free_nonces_memory(void)
208 {
209 for (uint16_t i = 0; i < 256; i++) {
210 free_nonce_list(nonces[i].first);
211 }
212 }
213
214
215 static uint16_t PartialSumProperty(uint32_t state, odd_even_t odd_even)
216 {
217 uint16_t sum = 0;
218 for (uint16_t j = 0; j < 16; j++) {
219 uint32_t st = state;
220 uint16_t part_sum = 0;
221 if (odd_even == ODD_STATE) {
222 for (uint16_t i = 0; i < 5; i++) {
223 part_sum ^= filter(st);
224 st = (st << 1) | ((j >> (3-i)) & 0x01) ;
225 }
226 part_sum ^= 1; // XOR 1 cancelled out for the other 8 bits
227 } else {
228 for (uint16_t i = 0; i < 4; i++) {
229 st = (st << 1) | ((j >> (3-i)) & 0x01) ;
230 part_sum ^= filter(st);
231 }
232 }
233 sum += part_sum;
234 }
235 return sum;
236 }
237
238
239 // static uint16_t SumProperty(struct Crypto1State *s)
240 // {
241 // uint16_t sum_odd = PartialSumProperty(s->odd, ODD_STATE);
242 // uint16_t sum_even = PartialSumProperty(s->even, EVEN_STATE);
243 // return (sum_odd*(16-sum_even) + (16-sum_odd)*sum_even);
244 // }
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
286 static float sum_probability(uint16_t K, uint16_t n, uint16_t k)
287 {
288 const uint16_t N = 256;
289
290 if (k > K || p_K[K] == 0.0) return 0.0;
291
292 double p_T_is_k_when_S_is_K = p_hypergeometric(N, K, n, k);
293 double p_S_is_K = p_K[K];
294 double p_T_is_k = 0;
295 for (uint16_t i = 0; i <= 256; i++) {
296 if (p_K[i] != 0.0) {
297 p_T_is_k += p_K[i] * p_hypergeometric(N, i, n, k);
298 }
299 }
300 return(p_T_is_k_when_S_is_K * p_S_is_K / p_T_is_k);
301 }
302
303
304
305
306 static inline uint_fast8_t common_bits(uint_fast8_t bytes_diff)
307 {
308 static const uint_fast8_t common_bits_LUT[256] = {
309 8, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
310 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
311 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
312 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
313 6, 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 7, 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 6, 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 };
326
327 return common_bits_LUT[bytes_diff];
328 }
329
330
331 static void Tests()
332 {
333 // printf("Tests: Partial Statelist sizes\n");
334 // for (uint16_t i = 0; i <= 16; i+=2) {
335 // printf("Partial State List Odd [%2d] has %8d entries\n", i, partial_statelist[i].len[ODD_STATE]);
336 // }
337 // for (uint16_t i = 0; i <= 16; i+=2) {
338 // printf("Partial State List Even [%2d] has %8d entries\n", i, partial_statelist[i].len[EVEN_STATE]);
339 // }
340
341 // #define NUM_STATISTICS 100000
342 // uint32_t statistics_odd[17];
343 // uint64_t statistics[257];
344 // uint32_t statistics_even[17];
345 // struct Crypto1State cs;
346 // time_t time1 = clock();
347
348 // for (uint16_t i = 0; i < 257; i++) {
349 // statistics[i] = 0;
350 // }
351 // for (uint16_t i = 0; i < 17; i++) {
352 // statistics_odd[i] = 0;
353 // statistics_even[i] = 0;
354 // }
355
356 // for (uint64_t i = 0; i < NUM_STATISTICS; i++) {
357 // cs.odd = (rand() & 0xfff) << 12 | (rand() & 0xfff);
358 // cs.even = (rand() & 0xfff) << 12 | (rand() & 0xfff);
359 // uint16_t sum_property = SumProperty(&cs);
360 // statistics[sum_property] += 1;
361 // sum_property = PartialSumProperty(cs.even, EVEN_STATE);
362 // statistics_even[sum_property]++;
363 // sum_property = PartialSumProperty(cs.odd, ODD_STATE);
364 // statistics_odd[sum_property]++;
365 // if (i%(NUM_STATISTICS/100) == 0) printf(".");
366 // }
367
368 // 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);
369 // for (uint16_t i = 0; i < 257; i++) {
370 // if (statistics[i] != 0) {
371 // printf("probability[%3d] = %0.5f\n", i, (float)statistics[i]/NUM_STATISTICS);
372 // }
373 // }
374 // for (uint16_t i = 0; i <= 16; i++) {
375 // if (statistics_odd[i] != 0) {
376 // printf("probability odd [%2d] = %0.5f\n", i, (float)statistics_odd[i]/NUM_STATISTICS);
377 // }
378 // }
379 // for (uint16_t i = 0; i <= 16; i++) {
380 // if (statistics_odd[i] != 0) {
381 // printf("probability even [%2d] = %0.5f\n", i, (float)statistics_even[i]/NUM_STATISTICS);
382 // }
383 // }
384
385 // printf("Tests: Sum Probabilities based on Partial Sums\n");
386 // for (uint16_t i = 0; i < 257; i++) {
387 // statistics[i] = 0;
388 // }
389 // uint64_t num_states = 0;
390 // for (uint16_t oddsum = 0; oddsum <= 16; oddsum += 2) {
391 // for (uint16_t evensum = 0; evensum <= 16; evensum += 2) {
392 // uint16_t sum = oddsum*(16-evensum) + (16-oddsum)*evensum;
393 // statistics[sum] += (uint64_t)partial_statelist[oddsum].len[ODD_STATE] * partial_statelist[evensum].len[EVEN_STATE] * (1<<8);
394 // num_states += (uint64_t)partial_statelist[oddsum].len[ODD_STATE] * partial_statelist[evensum].len[EVEN_STATE] * (1<<8);
395 // }
396 // }
397 // printf("num_states = %lld, expected %lld\n", num_states, (1LL<<48));
398 // for (uint16_t i = 0; i < 257; i++) {
399 // if (statistics[i] != 0) {
400 // printf("probability[%3d] = %0.5f\n", i, (float)statistics[i]/num_states);
401 // }
402 // }
403
404 // printf("\nTests: Hypergeometric Probability for selected parameters\n");
405 // printf("p_hypergeometric(256, 206, 255, 206) = %0.8f\n", p_hypergeometric(256, 206, 255, 206));
406 // printf("p_hypergeometric(256, 206, 255, 205) = %0.8f\n", p_hypergeometric(256, 206, 255, 205));
407 // printf("p_hypergeometric(256, 156, 1, 1) = %0.8f\n", p_hypergeometric(256, 156, 1, 1));
408 // printf("p_hypergeometric(256, 156, 1, 0) = %0.8f\n", p_hypergeometric(256, 156, 1, 0));
409 // printf("p_hypergeometric(256, 1, 1, 1) = %0.8f\n", p_hypergeometric(256, 1, 1, 1));
410 // printf("p_hypergeometric(256, 1, 1, 0) = %0.8f\n", p_hypergeometric(256, 1, 1, 0));
411
412 // struct Crypto1State *pcs;
413 // pcs = crypto1_create(0xffffffffffff);
414 // printf("\nTests: for key = 0xffffffffffff:\nSum(a0) = %d\nodd_state = 0x%06x\neven_state = 0x%06x\n",
415 // SumProperty(pcs), pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff);
416 // crypto1_byte(pcs, (cuid >> 24) ^ best_first_bytes[0], true);
417 // printf("After adding best first byte 0x%02x:\nSum(a8) = %d\nodd_state = 0x%06x\neven_state = 0x%06x\n",
418 // best_first_bytes[0],
419 // SumProperty(pcs),
420 // pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff);
421 // //test_state_odd = pcs->odd & 0x00ffffff;
422 // //test_state_even = pcs->even & 0x00ffffff;
423 // crypto1_destroy(pcs);
424 // pcs = crypto1_create(0xa0a1a2a3a4a5);
425 // printf("Tests: for key = 0xa0a1a2a3a4a5:\nSum(a0) = %d\nodd_state = 0x%06x\neven_state = 0x%06x\n",
426 // SumProperty(pcs), pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff);
427 // crypto1_byte(pcs, (cuid >> 24) ^ best_first_bytes[0], true);
428 // printf("After adding best first byte 0x%02x:\nSum(a8) = %d\nodd_state = 0x%06x\neven_state = 0x%06x\n",
429 // best_first_bytes[0],
430 // SumProperty(pcs),
431 // pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff);
432 // //test_state_odd = pcs->odd & 0x00ffffff;
433 // //test_state_even = pcs->even & 0x00ffffff;
434 // crypto1_destroy(pcs);
435 // pcs = crypto1_create(0xa6b9aa97b955);
436 // printf("Tests: for key = 0xa6b9aa97b955:\nSum(a0) = %d\nodd_state = 0x%06x\neven_state = 0x%06x\n",
437 // SumProperty(pcs), pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff);
438 // crypto1_byte(pcs, (cuid >> 24) ^ best_first_bytes[0], true);
439 // printf("After adding best first byte 0x%02x:\nSum(a8) = %d\nodd_state = 0x%06x\neven_state = 0x%06x\n",
440 // best_first_bytes[0],
441 // SumProperty(pcs),
442 // pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff);
443 //test_state_odd = pcs->odd & 0x00ffffff;
444 //test_state_even = pcs->even & 0x00ffffff;
445 // crypto1_destroy(pcs);
446
447
448
449 // 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));
450
451 printf("\nTests: Actual BitFlipProperties odd/even:\n");
452 for (uint16_t i = 0; i < 256; i++) {
453 printf("[%02x]:%c ", i, nonces[i].BitFlip[ODD_STATE]?'o':nonces[i].BitFlip[EVEN_STATE]?'e':' ');
454 if (i % 8 == 7) {
455 printf("\n");
456 }
457 }
458
459 printf("\nTests: Sorted First Bytes:\n");
460 for (uint16_t i = 0; i < 256; i++) {
461 uint8_t best_byte = best_first_bytes[i];
462 printf("#%03d Byte: %02x, n = %3d, k = %3d, Sum(a8): %3d, Confidence: %5.1f%%, Bitflip: %c\n",
463 //printf("#%03d Byte: %02x, n = %3d, k = %3d, Sum(a8): %3d, Confidence: %5.1f%%, Bitflip: %c, score1: %1.5f, score2: %1.0f\n",
464 i, best_byte,
465 nonces[best_byte].num,
466 nonces[best_byte].Sum,
467 nonces[best_byte].Sum8_guess,
468 nonces[best_byte].Sum8_prob * 100,
469 nonces[best_byte].BitFlip[ODD_STATE]?'o':nonces[best_byte].BitFlip[EVEN_STATE]?'e':' '
470 //nonces[best_byte].score1,
471 //nonces[best_byte].score2
472 );
473 }
474
475 // printf("\nTests: parity performance\n");
476 // time_t time1p = clock();
477 // uint32_t par_sum = 0;
478 // for (uint32_t i = 0; i < 100000000; i++) {
479 // par_sum += parity(i);
480 // }
481 // printf("parsum oldparity = %d, time = %1.5fsec\n", par_sum, (float)(clock() - time1p)/CLOCKS_PER_SEC);
482
483 // time1p = clock();
484 // par_sum = 0;
485 // for (uint32_t i = 0; i < 100000000; i++) {
486 // par_sum += evenparity32(i);
487 // }
488 // printf("parsum newparity = %d, time = %1.5fsec\n", par_sum, (float)(clock() - time1p)/CLOCKS_PER_SEC);
489
490
491 }
492
493
494 static void sort_best_first_bytes(void)
495 {
496 // sort based on probability for correct guess
497 for (uint16_t i = 0; i < 256; i++ ) {
498 uint16_t j = 0;
499 float prob1 = nonces[i].Sum8_prob;
500 float prob2 = nonces[best_first_bytes[0]].Sum8_prob;
501 while (prob1 < prob2 && j < i) {
502 prob2 = nonces[best_first_bytes[++j]].Sum8_prob;
503 }
504 if (j < i) {
505 for (uint16_t k = i; k > j; k--) {
506 best_first_bytes[k] = best_first_bytes[k-1];
507 }
508 }
509 best_first_bytes[j] = i;
510 }
511
512 // determine how many are above the CONFIDENCE_THRESHOLD
513 uint16_t num_good_nonces = 0;
514 for (uint16_t i = 0; i < 256; i++) {
515 if (nonces[best_first_bytes[i]].Sum8_prob >= CONFIDENCE_THRESHOLD) {
516 ++num_good_nonces;
517 }
518 }
519
520 uint16_t best_first_byte = 0;
521
522 // select the best possible first byte based on number of common bits with all {b'}
523 // uint16_t max_common_bits = 0;
524 // for (uint16_t i = 0; i < num_good_nonces; i++) {
525 // uint16_t sum_common_bits = 0;
526 // for (uint16_t j = 0; j < num_good_nonces; j++) {
527 // if (i != j) {
528 // sum_common_bits += common_bits(best_first_bytes[i],best_first_bytes[j]);
529 // }
530 // }
531 // if (sum_common_bits > max_common_bits) {
532 // max_common_bits = sum_common_bits;
533 // best_first_byte = i;
534 // }
535 // }
536
537 // select best possible first byte {b} based on least likely sum/bitflip property
538 float min_p_K = 1.0;
539 for (uint16_t i = 0; i < num_good_nonces; i++ ) {
540 uint16_t sum8 = nonces[best_first_bytes[i]].Sum8_guess;
541 float bitflip_prob = 1.0;
542 if (nonces[best_first_bytes[i]].BitFlip[ODD_STATE] || nonces[best_first_bytes[i]].BitFlip[EVEN_STATE]) {
543 bitflip_prob = 0.09375;
544 }
545 nonces[best_first_bytes[i]].score1 = p_K[sum8] * bitflip_prob;
546 if (p_K[sum8] * bitflip_prob <= min_p_K) {
547 min_p_K = p_K[sum8] * bitflip_prob;
548 }
549 }
550
551
552 // use number of commmon bits as a tie breaker
553 uint16_t max_common_bits = 0;
554 for (uint16_t i = 0; i < num_good_nonces; i++) {
555 float bitflip_prob = 1.0;
556 if (nonces[best_first_bytes[i]].BitFlip[ODD_STATE] || nonces[best_first_bytes[i]].BitFlip[EVEN_STATE]) {
557 bitflip_prob = 0.09375;
558 }
559 if (p_K[nonces[best_first_bytes[i]].Sum8_guess] * bitflip_prob == min_p_K) {
560 uint16_t sum_common_bits = 0;
561 for (uint16_t j = 0; j < num_good_nonces; j++) {
562 sum_common_bits += common_bits(best_first_bytes[i] ^ best_first_bytes[j]);
563 }
564 nonces[best_first_bytes[i]].score2 = sum_common_bits;
565 if (sum_common_bits > max_common_bits) {
566 max_common_bits = sum_common_bits;
567 best_first_byte = i;
568 }
569 }
570 }
571
572 // swap best possible first byte to the pole position
573 uint16_t temp = best_first_bytes[0];
574 best_first_bytes[0] = best_first_bytes[best_first_byte];
575 best_first_bytes[best_first_byte] = temp;
576
577 }
578
579
580 static uint16_t estimate_second_byte_sum(void)
581 {
582
583 for (uint16_t first_byte = 0; first_byte < 256; first_byte++) {
584 float Sum8_prob = 0.0;
585 uint16_t Sum8 = 0;
586 if (nonces[first_byte].updated) {
587 for (uint16_t sum = 0; sum <= 256; sum++) {
588 float prob = sum_probability(sum, nonces[first_byte].num, nonces[first_byte].Sum);
589 if (prob > Sum8_prob) {
590 Sum8_prob = prob;
591 Sum8 = sum;
592 }
593 }
594 nonces[first_byte].Sum8_guess = Sum8;
595 nonces[first_byte].Sum8_prob = Sum8_prob;
596 nonces[first_byte].updated = false;
597 }
598 }
599
600 sort_best_first_bytes();
601
602 uint16_t num_good_nonces = 0;
603 for (uint16_t i = 0; i < 256; i++) {
604 if (nonces[best_first_bytes[i]].Sum8_prob >= CONFIDENCE_THRESHOLD) {
605 ++num_good_nonces;
606 }
607 }
608
609 return num_good_nonces;
610 }
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
656 static void Check_for_FilterFlipProperties(void)
657 {
658 printf("Checking for Filter Flip Properties...\n");
659
660 uint16_t num_bitflips = 0;
661
662 for (uint16_t i = 0; i < 256; i++) {
663 nonces[i].BitFlip[ODD_STATE] = false;
664 nonces[i].BitFlip[EVEN_STATE] = false;
665 }
666
667 for (uint16_t i = 0; i < 256; i++) {
668 uint8_t parity1 = (nonces[i].first->par_enc) >> 3; // parity of first byte
669 uint8_t parity2_odd = (nonces[i^0x80].first->par_enc) >> 3; // XOR 0x80 = last bit flipped
670 uint8_t parity2_even = (nonces[i^0x40].first->par_enc) >> 3; // XOR 0x40 = second last bit flipped
671
672 if (parity1 == parity2_odd) { // has Bit Flip Property for odd bits
673 nonces[i].BitFlip[ODD_STATE] = true;
674 num_bitflips++;
675 } else if (parity1 == parity2_even) { // has Bit Flip Property for even bits
676 nonces[i].BitFlip[EVEN_STATE] = true;
677 num_bitflips++;
678 }
679 }
680
681 if (write_stats) {
682 fprintf(fstats, "%d;", num_bitflips);
683 }
684 }
685
686
687 static void simulate_MFplus_RNG(uint32_t test_cuid, uint64_t test_key, uint32_t *nt_enc, uint8_t *par_enc)
688 {
689 struct Crypto1State sim_cs;
690
691 // init cryptostate with key:
692 for(int8_t i = 47; i > 0; i -= 2) {
693 sim_cs.odd = sim_cs.odd << 1 | BIT(test_key, (i - 1) ^ 7);
694 sim_cs.even = sim_cs.even << 1 | BIT(test_key, i ^ 7);
695 }
696
697 *par_enc = 0;
698 uint32_t nt = (rand() & 0xff) << 24 | (rand() & 0xff) << 16 | (rand() & 0xff) << 8 | (rand() & 0xff);
699 for (int8_t byte_pos = 3; byte_pos >= 0; byte_pos--) {
700 uint8_t nt_byte_dec = (nt >> (8*byte_pos)) & 0xff;
701 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
702 *nt_enc = (*nt_enc << 8) | nt_byte_enc;
703 uint8_t ks_par = filter(sim_cs.odd); // the keystream bit to encode/decode the parity bit
704 uint8_t nt_byte_par_enc = ks_par ^ oddparity8(nt_byte_dec); // determine the nt byte's parity and encode it
705 *par_enc = (*par_enc << 1) | nt_byte_par_enc;
706 }
707
708 }
709
710
711 static void simulate_acquire_nonces()
712 {
713 clock_t time1 = clock();
714 bool filter_flip_checked = false;
715 uint32_t total_num_nonces = 0;
716 uint32_t next_fivehundred = 500;
717 uint32_t total_added_nonces = 0;
718
719 cuid = (rand() & 0xff) << 24 | (rand() & 0xff) << 16 | (rand() & 0xff) << 8 | (rand() & 0xff);
720 known_target_key = ((uint64_t)rand() & 0xfff) << 36 | ((uint64_t)rand() & 0xfff) << 24 | ((uint64_t)rand() & 0xfff) << 12 | ((uint64_t)rand() & 0xfff);
721
722 printf("Simulating nonce acquisition for target key %012"llx", cuid %08x ...\n", known_target_key, cuid);
723 fprintf(fstats, "%012"llx";%08x;", known_target_key, cuid);
724
725 do {
726 uint32_t nt_enc = 0;
727 uint8_t par_enc = 0;
728
729 simulate_MFplus_RNG(cuid, known_target_key, &nt_enc, &par_enc);
730 //printf("Simulated RNG: nt_enc1: %08x, nt_enc2: %08x, par_enc: %02x\n", nt_enc1, nt_enc2, par_enc);
731 total_added_nonces += add_nonce(nt_enc, par_enc);
732 total_num_nonces++;
733
734 if (first_byte_num == 256 ) {
735 // printf("first_byte_num = %d, first_byte_Sum = %d\n", first_byte_num, first_byte_Sum);
736 if (!filter_flip_checked) {
737 Check_for_FilterFlipProperties();
738 filter_flip_checked = true;
739 }
740 num_good_first_bytes = estimate_second_byte_sum();
741 if (total_num_nonces > next_fivehundred) {
742 next_fivehundred = (total_num_nonces/500+1) * 500;
743 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",
744 total_num_nonces,
745 total_added_nonces,
746 CONFIDENCE_THRESHOLD * 100.0,
747 num_good_first_bytes);
748 }
749 }
750
751 } while (num_good_first_bytes < GOOD_BYTES_REQUIRED);
752
753 time1 = clock() - time1;
754 if ( time1 > 0 ) {
755 PrintAndLog("Acquired a total of %d nonces in %1.1f seconds (%0.0f nonces/minute)",
756 total_num_nonces,
757 ((float)time1)/CLOCKS_PER_SEC,
758 total_num_nonces * 60.0 * CLOCKS_PER_SEC/(float)time1);
759 }
760 fprintf(fstats, "%d;%d;%d;%1.2f;", total_num_nonces, total_added_nonces, num_good_first_bytes, CONFIDENCE_THRESHOLD);
761
762 }
763
764
765 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)
766 {
767 clock_t time1 = clock();
768 bool initialize = true;
769 bool field_off = false;
770 bool finished = false;
771 bool filter_flip_checked = false;
772 uint32_t flags = 0;
773 uint8_t write_buf[9];
774 uint32_t total_num_nonces = 0;
775 uint32_t next_fivehundred = 500;
776 uint32_t total_added_nonces = 0;
777 FILE *fnonces = NULL;
778 UsbCommand resp;
779
780 printf("Acquiring nonces...\n");
781
782 clearCommandBuffer();
783
784 do {
785 flags = 0;
786 flags |= initialize ? 0x0001 : 0;
787 flags |= slow ? 0x0002 : 0;
788 flags |= field_off ? 0x0004 : 0;
789 UsbCommand c = {CMD_MIFARE_ACQUIRE_ENCRYPTED_NONCES, {blockNo + keyType * 0x100, trgBlockNo + trgKeyType * 0x100, flags}};
790 memcpy(c.d.asBytes, key, 6);
791
792 SendCommand(&c);
793
794 if (field_off) finished = true;
795
796 if (initialize) {
797 if (!WaitForResponseTimeout(CMD_ACK, &resp, 3000)) return 1;
798 if (resp.arg[0]) return resp.arg[0]; // error during nested_hard
799
800 cuid = resp.arg[1];
801 // PrintAndLog("Acquiring nonces for CUID 0x%08x", cuid);
802 if (nonce_file_write && fnonces == NULL) {
803 if ((fnonces = fopen("nonces.bin","wb")) == NULL) {
804 PrintAndLog("Could not create file nonces.bin");
805 return 3;
806 }
807 PrintAndLog("Writing acquired nonces to binary file nonces.bin");
808 num_to_bytes(cuid, 4, write_buf);
809 fwrite(write_buf, 1, 4, fnonces);
810 fwrite(&trgBlockNo, 1, 1, fnonces);
811 fwrite(&trgKeyType, 1, 1, fnonces);
812 }
813 }
814
815 if (!initialize) {
816 uint32_t nt_enc1, nt_enc2;
817 uint8_t par_enc;
818 uint16_t num_acquired_nonces = resp.arg[2];
819 uint8_t *bufp = resp.d.asBytes;
820 for (uint16_t i = 0; i < num_acquired_nonces; i+=2) {
821 nt_enc1 = bytes_to_num(bufp, 4);
822 nt_enc2 = bytes_to_num(bufp+4, 4);
823 par_enc = bytes_to_num(bufp+8, 1);
824
825 //printf("Encrypted nonce: %08x, encrypted_parity: %02x\n", nt_enc1, par_enc >> 4);
826 total_added_nonces += add_nonce(nt_enc1, par_enc >> 4);
827 //printf("Encrypted nonce: %08x, encrypted_parity: %02x\n", nt_enc2, par_enc & 0x0f);
828 total_added_nonces += add_nonce(nt_enc2, par_enc & 0x0f);
829
830
831 if (nonce_file_write) {
832 fwrite(bufp, 1, 9, fnonces);
833 }
834
835 bufp += 9;
836 }
837
838 total_num_nonces += num_acquired_nonces;
839 }
840
841 if (first_byte_num == 256 ) {
842 // printf("first_byte_num = %d, first_byte_Sum = %d\n", first_byte_num, first_byte_Sum);
843 if (!filter_flip_checked) {
844 Check_for_FilterFlipProperties();
845 filter_flip_checked = true;
846 }
847 num_good_first_bytes = estimate_second_byte_sum();
848 if (total_num_nonces > next_fivehundred) {
849 next_fivehundred = (total_num_nonces/500+1) * 500;
850 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",
851 total_num_nonces,
852 total_added_nonces,
853 CONFIDENCE_THRESHOLD * 100.0,
854 num_good_first_bytes);
855 }
856 if (num_good_first_bytes >= GOOD_BYTES_REQUIRED) {
857 field_off = true; // switch off field with next SendCommand and then finish
858 }
859 }
860
861 if (!initialize) {
862 if (!WaitForResponseTimeout(CMD_ACK, &resp, 3000)) {
863 fclose(fnonces);
864 return 1;
865 }
866 if (resp.arg[0]) {
867 fclose(fnonces);
868 return resp.arg[0]; // error during nested_hard
869 }
870 }
871
872 initialize = false;
873
874 } while (!finished);
875
876
877 if (nonce_file_write) {
878 fclose(fnonces);
879 }
880
881 time1 = clock() - time1;
882 if ( time1 > 0 ) {
883 PrintAndLog("Acquired a total of %d nonces in %1.1f seconds (%0.0f nonces/minute)",
884 total_num_nonces,
885 ((float)time1)/CLOCKS_PER_SEC,
886 total_num_nonces * 60.0 * CLOCKS_PER_SEC/(float)time1
887 );
888 }
889 return 0;
890 }
891
892
893 static int init_partial_statelists(void)
894 {
895 const uint32_t sizes_odd[17] = { 126757, 0, 18387, 0, 74241, 0, 181737, 0, 248801, 0, 182033, 0, 73421, 0, 17607, 0, 125601 };
896 const uint32_t sizes_even[17] = { 125723, 0, 17867, 0, 74305, 0, 178707, 0, 248801, 0, 185063, 0, 73356, 0, 18127, 0, 126634 };
897
898 printf("Allocating memory for partial statelists...\n");
899 for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) {
900 for (uint16_t i = 0; i <= 16; i+=2) {
901 partial_statelist[i].len[odd_even] = 0;
902 uint32_t num_of_states = odd_even == ODD_STATE ? sizes_odd[i] : sizes_even[i];
903 partial_statelist[i].states[odd_even] = malloc(sizeof(uint32_t) * num_of_states);
904 if (partial_statelist[i].states[odd_even] == NULL) {
905 PrintAndLog("Cannot allocate enough memory. Aborting");
906 return 4;
907 }
908 for (uint32_t j = 0; j < STATELIST_INDEX_SIZE; j++) {
909 partial_statelist[i].index[odd_even][j] = NULL;
910 }
911 }
912 }
913
914 printf("Generating partial statelists...\n");
915 for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) {
916 uint32_t index = -1;
917 uint32_t num_of_states = 1<<20;
918 for (uint32_t state = 0; state < num_of_states; state++) {
919 uint16_t sum_property = PartialSumProperty(state, odd_even);
920 uint32_t *p = partial_statelist[sum_property].states[odd_even];
921 p += partial_statelist[sum_property].len[odd_even];
922 *p = state;
923 partial_statelist[sum_property].len[odd_even]++;
924 uint32_t index_mask = (STATELIST_INDEX_SIZE-1) << (20-STATELIST_INDEX_WIDTH);
925 if ((state & index_mask) != index) {
926 index = state & index_mask;
927 }
928 if (partial_statelist[sum_property].index[odd_even][index >> (20-STATELIST_INDEX_WIDTH)] == NULL) {
929 partial_statelist[sum_property].index[odd_even][index >> (20-STATELIST_INDEX_WIDTH)] = p;
930 }
931 }
932 // add End Of List markers
933 for (uint16_t i = 0; i <= 16; i += 2) {
934 uint32_t *p = partial_statelist[i].states[odd_even];
935 p += partial_statelist[i].len[odd_even];
936 *p = 0xffffffff;
937 }
938 }
939
940 return 0;
941 }
942
943
944 static void init_BitFlip_statelist(void)
945 {
946 printf("Generating bitflip statelist...\n");
947 uint32_t *p = statelist_bitflip.states[0] = malloc(sizeof(uint32_t) * 1<<20);
948 uint32_t index = -1;
949 uint32_t index_mask = (STATELIST_INDEX_SIZE-1) << (20-STATELIST_INDEX_WIDTH);
950 for (uint32_t state = 0; state < (1 << 20); state++) {
951 if (filter(state) != filter(state^1)) {
952 if ((state & index_mask) != index) {
953 index = state & index_mask;
954 }
955 if (statelist_bitflip.index[0][index >> (20-STATELIST_INDEX_WIDTH)] == NULL) {
956 statelist_bitflip.index[0][index >> (20-STATELIST_INDEX_WIDTH)] = p;
957 }
958 *p++ = state;
959 }
960 }
961 // set len and add End Of List marker
962 statelist_bitflip.len[0] = p - statelist_bitflip.states[0];
963 *p = 0xffffffff;
964 statelist_bitflip.states[0] = realloc(statelist_bitflip.states[0], sizeof(uint32_t) * (statelist_bitflip.len[0] + 1));
965 }
966
967
968 static inline uint32_t *find_first_state(uint32_t state, uint32_t mask, partial_indexed_statelist_t *sl, odd_even_t odd_even)
969 {
970 uint32_t *p = sl->index[odd_even][(state & mask) >> (20-STATELIST_INDEX_WIDTH)]; // first Bits as index
971
972 if (p == NULL) return NULL;
973 while (*p < (state & mask)) p++;
974 if (*p == 0xffffffff) return NULL; // reached end of list, no match
975 if ((*p & mask) == (state & mask)) return p; // found a match.
976 return NULL; // no match
977 }
978
979
980 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)
981 {
982 uint_fast8_t j_1_bit_mask = 0x01 << (bit-1);
983 uint_fast8_t bit_diff = byte_diff & j_1_bit_mask; // difference of (j-1)th bit
984 uint_fast8_t filter_diff = filter(state1 >> (4-state_bit)) ^ filter(state2 >> (4-state_bit)); // difference in filter function
985 uint_fast8_t mask_y12_y13 = 0xc0 >> state_bit;
986 uint_fast8_t state_bits_diff = (state1 ^ state2) & mask_y12_y13; // difference in state bits 12 and 13
987 uint_fast8_t all_diff = evenparity8(bit_diff ^ state_bits_diff ^ filter_diff); // use parity function to XOR all bits
988 return !all_diff;
989 }
990
991
992 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)
993 {
994 uint_fast8_t j_bit_mask = 0x01 << bit;
995 uint_fast8_t bit_diff = byte_diff & j_bit_mask; // difference of jth bit
996 uint_fast8_t mask_y13_y16 = 0x48 >> state_bit;
997 uint_fast8_t state_bits_diff = (state1 ^ state2) & mask_y13_y16; // difference in state bits 13 and 16
998 uint_fast8_t all_diff = evenparity8(bit_diff ^ state_bits_diff); // use parity function to XOR all bits
999 return all_diff;
1000 }
1001
1002
1003 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)
1004 {
1005 if (odd_even) {
1006 // odd bits
1007 switch (num_common_bits) {
1008 case 0: if (!invariant_holds(byte_diff, state1, state2, 1, 0)) return true;
1009 case 1: if (invalid_state(byte_diff, state1, state2, 1, 0)) return false;
1010 case 2: if (!invariant_holds(byte_diff, state1, state2, 3, 1)) return true;
1011 case 3: if (invalid_state(byte_diff, state1, state2, 3, 1)) return false;
1012 case 4: if (!invariant_holds(byte_diff, state1, state2, 5, 2)) return true;
1013 case 5: if (invalid_state(byte_diff, state1, state2, 5, 2)) return false;
1014 case 6: if (!invariant_holds(byte_diff, state1, state2, 7, 3)) return true;
1015 case 7: if (invalid_state(byte_diff, state1, state2, 7, 3)) return false;
1016 }
1017 } else {
1018 // even bits
1019 switch (num_common_bits) {
1020 case 0: if (invalid_state(byte_diff, state1, state2, 0, 0)) return false;
1021 case 1: if (!invariant_holds(byte_diff, state1, state2, 2, 1)) return true;
1022 case 2: if (invalid_state(byte_diff, state1, state2, 2, 1)) return false;
1023 case 3: if (!invariant_holds(byte_diff, state1, state2, 4, 2)) return true;
1024 case 4: if (invalid_state(byte_diff, state1, state2, 4, 2)) return false;
1025 case 5: if (!invariant_holds(byte_diff, state1, state2, 6, 3)) return true;
1026 case 6: if (invalid_state(byte_diff, state1, state2, 6, 3)) return false;
1027 }
1028 }
1029
1030 return true; // valid state
1031 }
1032
1033
1034 static bool all_other_first_bytes_match(uint32_t state, odd_even_t odd_even)
1035 {
1036 for (uint16_t i = 1; i < num_good_first_bytes; i++) {
1037 uint16_t sum_a8 = nonces[best_first_bytes[i]].Sum8_guess;
1038 uint_fast8_t bytes_diff = best_first_bytes[0] ^ best_first_bytes[i];
1039 uint_fast8_t j = common_bits(bytes_diff);
1040 uint32_t mask = 0xfffffff0;
1041 if (odd_even == ODD_STATE) {
1042 mask >>= j/2;
1043 } else {
1044 mask >>= (j+1)/2;
1045 }
1046 mask &= 0x000fffff;
1047 //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);
1048 bool found_match = false;
1049 for (uint16_t r = 0; r <= 16 && !found_match; r += 2) {
1050 for (uint16_t s = 0; s <= 16 && !found_match; s += 2) {
1051 if (r*(16-s) + (16-r)*s == sum_a8) {
1052 //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);
1053 uint16_t part_sum_a8 = (odd_even == ODD_STATE) ? r : s;
1054 uint32_t *p = find_first_state(state, mask, &partial_statelist[part_sum_a8], odd_even);
1055 if (p != NULL) {
1056 while ((state & mask) == (*p & mask) && (*p != 0xffffffff)) {
1057 if (remaining_bits_match(j, bytes_diff, state, (state&0x00fffff0) | *p, odd_even)) {
1058 found_match = true;
1059 // if ((odd_even == ODD_STATE && state == test_state_odd)
1060 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1061 // 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",
1062 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1063 // }
1064 break;
1065 } else {
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: remaining bits didn't match. Bytes = %02x, %02x, Common Bits=%d, mask=0x%08x, PartSum(a8)=%d\n",
1069 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1070 // }
1071 }
1072 p++;
1073 }
1074 } else {
1075 // if ((odd_even == ODD_STATE && state == test_state_odd)
1076 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1077 // 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",
1078 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1079 // }
1080 }
1081 }
1082 }
1083 }
1084
1085 if (!found_match) {
1086 // if ((odd_even == ODD_STATE && state == test_state_odd)
1087 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1088 // 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);
1089 // }
1090 return false;
1091 }
1092 }
1093
1094 return true;
1095 }
1096
1097
1098 static bool all_bit_flips_match(uint32_t state, odd_even_t odd_even)
1099 {
1100 for (uint16_t i = 0; i < 256; i++) {
1101 if (nonces[i].BitFlip[odd_even] && i != best_first_bytes[0]) {
1102 uint_fast8_t bytes_diff = best_first_bytes[0] ^ i;
1103 uint_fast8_t j = common_bits(bytes_diff);
1104 uint32_t mask = 0xfffffff0;
1105 if (odd_even == ODD_STATE) {
1106 mask >>= j/2;
1107 } else {
1108 mask >>= (j+1)/2;
1109 }
1110 mask &= 0x000fffff;
1111 //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);
1112 bool found_match = false;
1113 uint32_t *p = find_first_state(state, mask, &statelist_bitflip, 0);
1114 if (p != NULL) {
1115 while ((state & mask) == (*p & mask) && (*p != 0xffffffff)) {
1116 if (remaining_bits_match(j, bytes_diff, state, (state&0x00fffff0) | *p, odd_even)) {
1117 found_match = true;
1118 // if ((odd_even == ODD_STATE && state == test_state_odd)
1119 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1120 // printf("all_other_first_bytes_match(): %s test state: remaining bits matched. Bytes = %02x, %02x, Common Bits=%d, mask=0x%08x, PartSum(a8)=%d\n",
1121 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1122 // }
1123 break;
1124 } else {
1125 // if ((odd_even == ODD_STATE && state == test_state_odd)
1126 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1127 // 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",
1128 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1129 // }
1130 }
1131 p++;
1132 }
1133 } else {
1134 // if ((odd_even == ODD_STATE && state == test_state_odd)
1135 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1136 // 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",
1137 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1138 // }
1139 }
1140 if (!found_match) {
1141 // if ((odd_even == ODD_STATE && state == test_state_odd)
1142 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1143 // 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);
1144 // }
1145 return false;
1146 }
1147 }
1148
1149 }
1150
1151 return true;
1152 }
1153
1154
1155 static struct sl_cache_entry {
1156 uint32_t *sl;
1157 uint32_t len;
1158 } sl_cache[17][17][2];
1159
1160
1161 static void init_statelist_cache(void)
1162 {
1163 for (uint16_t i = 0; i < 17; i+=2) {
1164 for (uint16_t j = 0; j < 17; j+=2) {
1165 for (uint16_t k = 0; k < 2; k++) {
1166 sl_cache[i][j][k].sl = NULL;
1167 sl_cache[i][j][k].len = 0;
1168 }
1169 }
1170 }
1171 }
1172
1173
1174 static int add_matching_states(statelist_t *candidates, uint16_t part_sum_a0, uint16_t part_sum_a8, odd_even_t odd_even)
1175 {
1176 uint32_t worstcase_size = 1<<20;
1177
1178 // check cache for existing results
1179 if (sl_cache[part_sum_a0][part_sum_a8][odd_even].sl != NULL) {
1180 candidates->states[odd_even] = sl_cache[part_sum_a0][part_sum_a8][odd_even].sl;
1181 candidates->len[odd_even] = sl_cache[part_sum_a0][part_sum_a8][odd_even].len;
1182 return 0;
1183 }
1184
1185 candidates->states[odd_even] = (uint32_t *)malloc(sizeof(uint32_t) * worstcase_size);
1186 if (candidates->states[odd_even] == NULL) {
1187 PrintAndLog("Out of memory error.\n");
1188 return 4;
1189 }
1190 uint32_t *add_p = candidates->states[odd_even];
1191 for (uint32_t *p1 = partial_statelist[part_sum_a0].states[odd_even]; *p1 != 0xffffffff; p1++) {
1192 uint32_t search_mask = 0x000ffff0;
1193 uint32_t *p2 = find_first_state((*p1 << 4), search_mask, &partial_statelist[part_sum_a8], odd_even);
1194 if (p2 != NULL) {
1195 while (((*p1 << 4) & search_mask) == (*p2 & search_mask) && *p2 != 0xffffffff) {
1196 if ((nonces[best_first_bytes[0]].BitFlip[odd_even] && find_first_state((*p1 << 4) | *p2, 0x000fffff, &statelist_bitflip, 0))
1197 || !nonces[best_first_bytes[0]].BitFlip[odd_even]) {
1198 if (all_other_first_bytes_match((*p1 << 4) | *p2, odd_even)) {
1199 if (all_bit_flips_match((*p1 << 4) | *p2, odd_even)) {
1200 *add_p++ = (*p1 << 4) | *p2;
1201 }
1202 }
1203 }
1204 p2++;
1205 }
1206 }
1207 }
1208
1209 // set end of list marker and len
1210 *add_p = 0xffffffff;
1211 candidates->len[odd_even] = add_p - candidates->states[odd_even];
1212
1213 candidates->states[odd_even] = realloc(candidates->states[odd_even], sizeof(uint32_t) * (candidates->len[odd_even] + 1));
1214
1215 sl_cache[part_sum_a0][part_sum_a8][odd_even].sl = candidates->states[odd_even];
1216 sl_cache[part_sum_a0][part_sum_a8][odd_even].len = candidates->len[odd_even];
1217
1218 return 0;
1219 }
1220
1221
1222 static statelist_t *add_more_candidates(statelist_t *current_candidates)
1223 {
1224 statelist_t *new_candidates = NULL;
1225 if (current_candidates == NULL) {
1226 if (candidates == NULL) {
1227 candidates = (statelist_t *)malloc(sizeof(statelist_t));
1228 }
1229 new_candidates = candidates;
1230 } else {
1231 new_candidates = current_candidates->next = (statelist_t *)malloc(sizeof(statelist_t));
1232 }
1233 new_candidates->next = NULL;
1234 new_candidates->len[ODD_STATE] = 0;
1235 new_candidates->len[EVEN_STATE] = 0;
1236 new_candidates->states[ODD_STATE] = NULL;
1237 new_candidates->states[EVEN_STATE] = NULL;
1238 return new_candidates;
1239 }
1240
1241
1242 static void TestIfKeyExists(uint64_t key)
1243 {
1244 struct Crypto1State *pcs;
1245 pcs = crypto1_create(key);
1246 crypto1_byte(pcs, (cuid >> 24) ^ best_first_bytes[0], true);
1247
1248 uint32_t state_odd = pcs->odd & 0x00ffffff;
1249 uint32_t state_even = pcs->even & 0x00ffffff;
1250 //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);
1251
1252 uint64_t count = 0;
1253 for (statelist_t *p = candidates; p != NULL; p = p->next) {
1254 bool found_odd = false;
1255 bool found_even = false;
1256 uint32_t *p_odd = p->states[ODD_STATE];
1257 uint32_t *p_even = p->states[EVEN_STATE];
1258 while (*p_odd != 0xffffffff) {
1259 if ((*p_odd & 0x00ffffff) == state_odd) {
1260 found_odd = true;
1261 break;
1262 }
1263 p_odd++;
1264 }
1265 while (*p_even != 0xffffffff) {
1266 if ((*p_even & 0x00ffffff) == state_even) {
1267 found_even = true;
1268 }
1269 p_even++;
1270 }
1271 count += (p_odd - p->states[ODD_STATE]) * (p_even - p->states[EVEN_STATE]);
1272 if (found_odd && found_even) {
1273 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.",
1274 count, log(count)/log(2),
1275 maximum_states, log(maximum_states)/log(2),
1276 (count>>23)/60);
1277 if (write_stats) {
1278 fprintf(fstats, "1\n");
1279 }
1280 crypto1_destroy(pcs);
1281 return;
1282 }
1283 }
1284
1285 printf("Key NOT found!\n");
1286 if (write_stats) {
1287 fprintf(fstats, "0\n");
1288 }
1289 crypto1_destroy(pcs);
1290 }
1291
1292
1293 static void generate_candidates(uint16_t sum_a0, uint16_t sum_a8)
1294 {
1295 printf("Generating crypto1 state candidates... \n");
1296
1297 statelist_t *current_candidates = NULL;
1298 // estimate maximum candidate states
1299 maximum_states = 0;
1300 for (uint16_t sum_odd = 0; sum_odd <= 16; sum_odd += 2) {
1301 for (uint16_t sum_even = 0; sum_even <= 16; sum_even += 2) {
1302 if (sum_odd*(16-sum_even) + (16-sum_odd)*sum_even == sum_a0) {
1303 maximum_states += (uint64_t)partial_statelist[sum_odd].len[ODD_STATE] * partial_statelist[sum_even].len[EVEN_STATE] * (1<<8);
1304 }
1305 }
1306 }
1307 printf("Number of possible keys with Sum(a0) = %d: %"PRIu64" (2^%1.1f)\n", sum_a0, maximum_states, log(maximum_states)/log(2.0));
1308
1309 init_statelist_cache();
1310
1311 for (uint16_t p = 0; p <= 16; p += 2) {
1312 for (uint16_t q = 0; q <= 16; q += 2) {
1313 if (p*(16-q) + (16-p)*q == sum_a0) {
1314 printf("Reducing Partial Statelists (p,q) = (%d,%d) with lengths %d, %d\n",
1315 p, q, partial_statelist[p].len[ODD_STATE], partial_statelist[q].len[EVEN_STATE]);
1316 for (uint16_t r = 0; r <= 16; r += 2) {
1317 for (uint16_t s = 0; s <= 16; s += 2) {
1318 if (r*(16-s) + (16-r)*s == sum_a8) {
1319 current_candidates = add_more_candidates(current_candidates);
1320 // check for the smallest partial statelist. Try this first - it might give 0 candidates
1321 // and eliminate the need to calculate the other part
1322 if (MIN(partial_statelist[p].len[ODD_STATE], partial_statelist[r].len[ODD_STATE])
1323 < MIN(partial_statelist[q].len[EVEN_STATE], partial_statelist[s].len[EVEN_STATE])) {
1324 add_matching_states(current_candidates, p, r, ODD_STATE);
1325 if(current_candidates->len[ODD_STATE]) {
1326 add_matching_states(current_candidates, q, s, EVEN_STATE);
1327 } else {
1328 current_candidates->len[EVEN_STATE] = 0;
1329 uint32_t *p = current_candidates->states[EVEN_STATE] = malloc(sizeof(uint32_t));
1330 *p = 0xffffffff;
1331 }
1332 } else {
1333 add_matching_states(current_candidates, q, s, EVEN_STATE);
1334 if(current_candidates->len[EVEN_STATE]) {
1335 add_matching_states(current_candidates, p, r, ODD_STATE);
1336 } else {
1337 current_candidates->len[ODD_STATE] = 0;
1338 uint32_t *p = current_candidates->states[ODD_STATE] = malloc(sizeof(uint32_t));
1339 *p = 0xffffffff;
1340 }
1341 }
1342 printf("Odd state candidates: %6d (2^%0.1f)\n", current_candidates->len[ODD_STATE], log(current_candidates->len[ODD_STATE])/log(2));
1343 printf("Even state candidates: %6d (2^%0.1f)\n", current_candidates->len[EVEN_STATE], log(current_candidates->len[EVEN_STATE])/log(2));
1344 }
1345 }
1346 }
1347 }
1348 }
1349 }
1350
1351
1352 maximum_states = 0;
1353 for (statelist_t *sl = candidates; sl != NULL; sl = sl->next) {
1354 maximum_states += (uint64_t)sl->len[ODD_STATE] * sl->len[EVEN_STATE];
1355 }
1356 printf("Number of remaining possible keys: %"PRIu64" (2^%1.1f)\n", maximum_states, log(maximum_states)/log(2.0));
1357 if (write_stats) {
1358 if (maximum_states != 0) {
1359 fprintf(fstats, "%1.1f;", log(maximum_states)/log(2.0));
1360 } else {
1361 fprintf(fstats, "%1.1f;", 0.0);
1362 }
1363 }
1364 }
1365
1366
1367 static void free_candidates_memory(statelist_t *sl)
1368 {
1369 if (sl == NULL) {
1370 return;
1371 } else {
1372 free_candidates_memory(sl->next);
1373 free(sl);
1374 }
1375 }
1376
1377
1378 static void free_statelist_cache(void)
1379 {
1380 for (uint16_t i = 0; i < 17; i+=2) {
1381 for (uint16_t j = 0; j < 17; j+=2) {
1382 for (uint16_t k = 0; k < 2; k++) {
1383 free(sl_cache[i][j][k].sl);
1384 }
1385 }
1386 }
1387 }
1388
1389
1390 static void brute_force(void)
1391 {
1392 if (known_target_key != -1) {
1393 PrintAndLog("Looking for known target key in remaining key space...");
1394 TestIfKeyExists(known_target_key);
1395 } else {
1396 PrintAndLog("Brute Force phase is not implemented.");
1397 }
1398
1399 }
1400
1401
1402 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)
1403 {
1404 // initialize Random number generator
1405 time_t t;
1406 srand((unsigned) time(&t));
1407
1408 if (trgkey != NULL) {
1409 known_target_key = bytes_to_num(trgkey, 6);
1410 } else {
1411 known_target_key = -1;
1412 }
1413
1414 init_partial_statelists();
1415 init_BitFlip_statelist();
1416 write_stats = false;
1417
1418 if (tests) {
1419 // set the correct locale for the stats printing
1420 setlocale(LC_ALL, "");
1421 write_stats = true;
1422 if ((fstats = fopen("hardnested_stats.txt","a")) == NULL) {
1423 PrintAndLog("Could not create/open file hardnested_stats.txt");
1424 return 3;
1425 }
1426 for (uint32_t i = 0; i < tests; i++) {
1427 init_nonce_memory();
1428 simulate_acquire_nonces();
1429 Tests();
1430 printf("Sum(a0) = %d\n", first_byte_Sum);
1431 fprintf(fstats, "%d;", first_byte_Sum);
1432 generate_candidates(first_byte_Sum, nonces[best_first_bytes[0]].Sum8_guess);
1433 brute_force();
1434 free_nonces_memory();
1435 free_statelist_cache();
1436 free_candidates_memory(candidates);
1437 candidates = NULL;
1438 }
1439 fclose(fstats);
1440 } else {
1441 init_nonce_memory();
1442 if (nonce_file_read) { // use pre-acquired data from file nonces.bin
1443 if (read_nonce_file() != 0) {
1444 return 3;
1445 }
1446 Check_for_FilterFlipProperties();
1447 num_good_first_bytes = MIN(estimate_second_byte_sum(), GOOD_BYTES_REQUIRED);
1448 } else { // acquire nonces.
1449 uint16_t is_OK = acquire_nonces(blockNo, keyType, key, trgBlockNo, trgKeyType, nonce_file_write, slow);
1450 if (is_OK != 0) {
1451 return is_OK;
1452 }
1453 }
1454
1455 Tests();
1456
1457 PrintAndLog("");
1458 PrintAndLog("Sum(a0) = %d", first_byte_Sum);
1459 // PrintAndLog("Best 10 first bytes: %02x, %02x, %02x, %02x, %02x, %02x, %02x, %02x, %02x, %02x",
1460 // best_first_bytes[0],
1461 // best_first_bytes[1],
1462 // best_first_bytes[2],
1463 // best_first_bytes[3],
1464 // best_first_bytes[4],
1465 // best_first_bytes[5],
1466 // best_first_bytes[6],
1467 // best_first_bytes[7],
1468 // best_first_bytes[8],
1469 // best_first_bytes[9] );
1470 PrintAndLog("Number of first bytes with confidence > %2.1f%%: %d", CONFIDENCE_THRESHOLD*100.0, num_good_first_bytes);
1471
1472 clock_t time1 = clock();
1473 generate_candidates(first_byte_Sum, nonces[best_first_bytes[0]].Sum8_guess);
1474 time1 = clock() - time1;
1475 if ( time1 > 0 )
1476 PrintAndLog("Time for generating key candidates list: %1.0f seconds", ((float)time1)/CLOCKS_PER_SEC);
1477
1478 brute_force();
1479 free_nonces_memory();
1480 free_statelist_cache();
1481 free_candidates_memory(candidates);
1482 candidates = NULL;
1483 }
1484 return 0;
1485 }
1486
1487
Proxmark3 GIT tracking
Impressum, Datenschutz