]> cvs.zerfleddert.de Git - proxmark3-svn/blob - client/cmdhfmfhard.c
projects / proxmark3-svn / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
REM: removed a print. The printing is done in the calling function.
[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 if (fread(read_buf, 1, 6, fnonces) == 0) {
630 PrintAndLog("File reading error.");
631 fclose(fnonces);
632 return 1;
633 }
634 cuid = bytes_to_num(read_buf, 4);
635 trgBlockNo = bytes_to_num(read_buf+4, 1);
636 trgKeyType = bytes_to_num(read_buf+5, 1);
637
638 while (fread(read_buf, 1, 9, fnonces) == 9) {
639 nt_enc1 = bytes_to_num(read_buf, 4);
640 nt_enc2 = bytes_to_num(read_buf+4, 4);
641 par_enc = bytes_to_num(read_buf+8, 1);
642 //printf("Encrypted nonce: %08x, encrypted_parity: %02x\n", nt_enc1, par_enc >> 4);
643 //printf("Encrypted nonce: %08x, encrypted_parity: %02x\n", nt_enc2, par_enc & 0x0f);
644 add_nonce(nt_enc1, par_enc >> 4);
645 add_nonce(nt_enc2, par_enc & 0x0f);
646 total_num_nonces += 2;
647 }
648 fclose(fnonces);
649 PrintAndLog("Read %d nonces from file. cuid=%08x, Block=%d, Keytype=%c", total_num_nonces, cuid, trgBlockNo, trgKeyType==0?'A':'B');
650
651 return 0;
652 }
653
654
655 static void Check_for_FilterFlipProperties(void)
656 {
657 printf("Checking for Filter Flip Properties...\n");
658
659 uint16_t num_bitflips = 0;
660
661 for (uint16_t i = 0; i < 256; i++) {
662 nonces[i].BitFlip[ODD_STATE] = false;
663 nonces[i].BitFlip[EVEN_STATE] = false;
664 }
665
666 for (uint16_t i = 0; i < 256; i++) {
667 uint8_t parity1 = (nonces[i].first->par_enc) >> 3; // parity of first byte
668 uint8_t parity2_odd = (nonces[i^0x80].first->par_enc) >> 3; // XOR 0x80 = last bit flipped
669 uint8_t parity2_even = (nonces[i^0x40].first->par_enc) >> 3; // XOR 0x40 = second last bit flipped
670
671 if (parity1 == parity2_odd) { // has Bit Flip Property for odd bits
672 nonces[i].BitFlip[ODD_STATE] = true;
673 num_bitflips++;
674 } else if (parity1 == parity2_even) { // has Bit Flip Property for even bits
675 nonces[i].BitFlip[EVEN_STATE] = true;
676 num_bitflips++;
677 }
678 }
679
680 if (write_stats) {
681 fprintf(fstats, "%d;", num_bitflips);
682 }
683 }
684
685
686 static void simulate_MFplus_RNG(uint32_t test_cuid, uint64_t test_key, uint32_t *nt_enc, uint8_t *par_enc)
687 {
688 struct Crypto1State sim_cs;
689
690 // init cryptostate with key:
691 for(int8_t i = 47; i > 0; i -= 2) {
692 sim_cs.odd = sim_cs.odd << 1 | BIT(test_key, (i - 1) ^ 7);
693 sim_cs.even = sim_cs.even << 1 | BIT(test_key, i ^ 7);
694 }
695
696 *par_enc = 0;
697 uint32_t nt = (rand() & 0xff) << 24 | (rand() & 0xff) << 16 | (rand() & 0xff) << 8 | (rand() & 0xff);
698 for (int8_t byte_pos = 3; byte_pos >= 0; byte_pos--) {
699 uint8_t nt_byte_dec = (nt >> (8*byte_pos)) & 0xff;
700 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
701 *nt_enc = (*nt_enc << 8) | nt_byte_enc;
702 uint8_t ks_par = filter(sim_cs.odd); // the keystream bit to encode/decode the parity bit
703 uint8_t nt_byte_par_enc = ks_par ^ oddparity8(nt_byte_dec); // determine the nt byte's parity and encode it
704 *par_enc = (*par_enc << 1) | nt_byte_par_enc;
705 }
706
707 }
708
709
710 static void simulate_acquire_nonces()
711 {
712 clock_t time1 = clock();
713 bool filter_flip_checked = false;
714 uint32_t total_num_nonces = 0;
715 uint32_t next_fivehundred = 500;
716 uint32_t total_added_nonces = 0;
717
718 cuid = (rand() & 0xff) << 24 | (rand() & 0xff) << 16 | (rand() & 0xff) << 8 | (rand() & 0xff);
719 known_target_key = ((uint64_t)rand() & 0xfff) << 36 | ((uint64_t)rand() & 0xfff) << 24 | ((uint64_t)rand() & 0xfff) << 12 | ((uint64_t)rand() & 0xfff);
720
721 printf("Simulating nonce acquisition for target key %012"llx", cuid %08x ...\n", known_target_key, cuid);
722 fprintf(fstats, "%012"llx";%08x;", known_target_key, cuid);
723
724 do {
725 uint32_t nt_enc = 0;
726 uint8_t par_enc = 0;
727
728 simulate_MFplus_RNG(cuid, known_target_key, &nt_enc, &par_enc);
729 //printf("Simulated RNG: nt_enc1: %08x, nt_enc2: %08x, par_enc: %02x\n", nt_enc1, nt_enc2, par_enc);
730 total_added_nonces += add_nonce(nt_enc, par_enc);
731 total_num_nonces++;
732
733 if (first_byte_num == 256 ) {
734 // printf("first_byte_num = %d, first_byte_Sum = %d\n", first_byte_num, first_byte_Sum);
735 if (!filter_flip_checked) {
736 Check_for_FilterFlipProperties();
737 filter_flip_checked = true;
738 }
739 num_good_first_bytes = estimate_second_byte_sum();
740 if (total_num_nonces > next_fivehundred) {
741 next_fivehundred = (total_num_nonces/500+1) * 500;
742 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",
743 total_num_nonces,
744 total_added_nonces,
745 CONFIDENCE_THRESHOLD * 100.0,
746 num_good_first_bytes);
747 }
748 }
749
750 } while (num_good_first_bytes < GOOD_BYTES_REQUIRED);
751
752 PrintAndLog("Acquired a total of %d nonces in %1.1f seconds (%0.0f nonces/minute)",
753 total_num_nonces,
754 ((float)clock()-time1)/CLOCKS_PER_SEC,
755 total_num_nonces*60.0*CLOCKS_PER_SEC/((float)clock()-time1));
756
757 fprintf(fstats, "%d;%d;%d;%1.2f;", total_num_nonces, total_added_nonces, num_good_first_bytes, CONFIDENCE_THRESHOLD);
758
759 }
760
761
762 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)
763 {
764 clock_t time1 = clock();
765 bool initialize = true;
766 bool field_off = false;
767 bool finished = false;
768 bool filter_flip_checked = false;
769 uint32_t flags = 0;
770 uint8_t write_buf[9];
771 uint32_t total_num_nonces = 0;
772 uint32_t next_fivehundred = 500;
773 uint32_t total_added_nonces = 0;
774 FILE *fnonces = NULL;
775 UsbCommand resp;
776
777 printf("Acquiring nonces...\n");
778
779 clearCommandBuffer();
780
781 do {
782 flags = 0;
783 flags |= initialize ? 0x0001 : 0;
784 flags |= slow ? 0x0002 : 0;
785 flags |= field_off ? 0x0004 : 0;
786 UsbCommand c = {CMD_MIFARE_ACQUIRE_ENCRYPTED_NONCES, {blockNo + keyType * 0x100, trgBlockNo + trgKeyType * 0x100, flags}};
787 memcpy(c.d.asBytes, key, 6);
788
789 SendCommand(&c);
790
791 if (field_off) finished = true;
792
793 if (initialize) {
794 if (!WaitForResponseTimeout(CMD_ACK, &resp, 3000)) return 1;
795 if (resp.arg[0]) return resp.arg[0]; // error during nested_hard
796
797 cuid = resp.arg[1];
798 // PrintAndLog("Acquiring nonces for CUID 0x%08x", cuid);
799 if (nonce_file_write && fnonces == NULL) {
800 if ((fnonces = fopen("nonces.bin","wb")) == NULL) {
801 PrintAndLog("Could not create file nonces.bin");
802 return 3;
803 }
804 PrintAndLog("Writing acquired nonces to binary file nonces.bin");
805 num_to_bytes(cuid, 4, write_buf);
806 fwrite(write_buf, 1, 4, fnonces);
807 fwrite(&trgBlockNo, 1, 1, fnonces);
808 fwrite(&trgKeyType, 1, 1, fnonces);
809 }
810 }
811
812 if (!initialize) {
813 uint32_t nt_enc1, nt_enc2;
814 uint8_t par_enc;
815 uint16_t num_acquired_nonces = resp.arg[2];
816 uint8_t *bufp = resp.d.asBytes;
817 for (uint16_t i = 0; i < num_acquired_nonces; i+=2) {
818 nt_enc1 = bytes_to_num(bufp, 4);
819 nt_enc2 = bytes_to_num(bufp+4, 4);
820 par_enc = bytes_to_num(bufp+8, 1);
821
822 //printf("Encrypted nonce: %08x, encrypted_parity: %02x\n", nt_enc1, par_enc >> 4);
823 total_added_nonces += add_nonce(nt_enc1, par_enc >> 4);
824 //printf("Encrypted nonce: %08x, encrypted_parity: %02x\n", nt_enc2, par_enc & 0x0f);
825 total_added_nonces += add_nonce(nt_enc2, par_enc & 0x0f);
826
827
828 if (nonce_file_write) {
829 fwrite(bufp, 1, 9, fnonces);
830 }
831
832 bufp += 9;
833 }
834
835 total_num_nonces += num_acquired_nonces;
836 }
837
838 if (first_byte_num == 256 ) {
839 // printf("first_byte_num = %d, first_byte_Sum = %d\n", first_byte_num, first_byte_Sum);
840 if (!filter_flip_checked) {
841 Check_for_FilterFlipProperties();
842 filter_flip_checked = true;
843 }
844 num_good_first_bytes = estimate_second_byte_sum();
845 if (total_num_nonces > next_fivehundred) {
846 next_fivehundred = (total_num_nonces/500+1) * 500;
847 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",
848 total_num_nonces,
849 total_added_nonces,
850 CONFIDENCE_THRESHOLD * 100.0,
851 num_good_first_bytes);
852 }
853 if (num_good_first_bytes >= GOOD_BYTES_REQUIRED) {
854 field_off = true; // switch off field with next SendCommand and then finish
855 }
856 }
857
858 if (!initialize) {
859 if (!WaitForResponseTimeout(CMD_ACK, &resp, 3000)) {
860 fclose(fnonces);
861 return 1;
862 }
863 if (resp.arg[0]) {
864 fclose(fnonces);
865 return resp.arg[0]; // error during nested_hard
866 }
867 }
868
869 initialize = false;
870
871 } while (!finished);
872
873
874 if (nonce_file_write) {
875 fclose(fnonces);
876 }
877
878 PrintAndLog("Acquired a total of %d nonces in %1.1f seconds (%0.0f nonces/minute)",
879 total_num_nonces,
880 ((float)clock()-time1)/CLOCKS_PER_SEC,
881 total_num_nonces*60.0*CLOCKS_PER_SEC/((float)clock()-time1));
882
883 return 0;
884 }
885
886
887 static int init_partial_statelists(void)
888 {
889 const uint32_t sizes_odd[17] = { 126757, 0, 18387, 0, 74241, 0, 181737, 0, 248801, 0, 182033, 0, 73421, 0, 17607, 0, 125601 };
890 const uint32_t sizes_even[17] = { 125723, 0, 17867, 0, 74305, 0, 178707, 0, 248801, 0, 185063, 0, 73356, 0, 18127, 0, 126634 };
891
892 printf("Allocating memory for partial statelists...\n");
893 for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) {
894 for (uint16_t i = 0; i <= 16; i+=2) {
895 partial_statelist[i].len[odd_even] = 0;
896 uint32_t num_of_states = odd_even == ODD_STATE ? sizes_odd[i] : sizes_even[i];
897 partial_statelist[i].states[odd_even] = malloc(sizeof(uint32_t) * num_of_states);
898 if (partial_statelist[i].states[odd_even] == NULL) {
899 PrintAndLog("Cannot allocate enough memory. Aborting");
900 return 4;
901 }
902 for (uint32_t j = 0; j < STATELIST_INDEX_SIZE; j++) {
903 partial_statelist[i].index[odd_even][j] = NULL;
904 }
905 }
906 }
907
908 printf("Generating partial statelists...\n");
909 for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) {
910 uint32_t index = -1;
911 uint32_t num_of_states = 1<<20;
912 for (uint32_t state = 0; state < num_of_states; state++) {
913 uint16_t sum_property = PartialSumProperty(state, odd_even);
914 uint32_t *p = partial_statelist[sum_property].states[odd_even];
915 p += partial_statelist[sum_property].len[odd_even];
916 *p = state;
917 partial_statelist[sum_property].len[odd_even]++;
918 uint32_t index_mask = (STATELIST_INDEX_SIZE-1) << (20-STATELIST_INDEX_WIDTH);
919 if ((state & index_mask) != index) {
920 index = state & index_mask;
921 }
922 if (partial_statelist[sum_property].index[odd_even][index >> (20-STATELIST_INDEX_WIDTH)] == NULL) {
923 partial_statelist[sum_property].index[odd_even][index >> (20-STATELIST_INDEX_WIDTH)] = p;
924 }
925 }
926 // add End Of List markers
927 for (uint16_t i = 0; i <= 16; i += 2) {
928 uint32_t *p = partial_statelist[i].states[odd_even];
929 p += partial_statelist[i].len[odd_even];
930 *p = 0xffffffff;
931 }
932 }
933
934 return 0;
935 }
936
937
938 static void init_BitFlip_statelist(void)
939 {
940 printf("Generating bitflip statelist...\n");
941 uint32_t *p = statelist_bitflip.states[0] = malloc(sizeof(uint32_t) * 1<<20);
942 uint32_t index = -1;
943 uint32_t index_mask = (STATELIST_INDEX_SIZE-1) << (20-STATELIST_INDEX_WIDTH);
944 for (uint32_t state = 0; state < (1 << 20); state++) {
945 if (filter(state) != filter(state^1)) {
946 if ((state & index_mask) != index) {
947 index = state & index_mask;
948 }
949 if (statelist_bitflip.index[0][index >> (20-STATELIST_INDEX_WIDTH)] == NULL) {
950 statelist_bitflip.index[0][index >> (20-STATELIST_INDEX_WIDTH)] = p;
951 }
952 *p++ = state;
953 }
954 }
955 // set len and add End Of List marker
956 statelist_bitflip.len[0] = p - statelist_bitflip.states[0];
957 *p = 0xffffffff;
958 statelist_bitflip.states[0] = realloc(statelist_bitflip.states[0], sizeof(uint32_t) * (statelist_bitflip.len[0] + 1));
959 }
960
961
962 static inline uint32_t *find_first_state(uint32_t state, uint32_t mask, partial_indexed_statelist_t *sl, odd_even_t odd_even)
963 {
964 uint32_t *p = sl->index[odd_even][(state & mask) >> (20-STATELIST_INDEX_WIDTH)]; // first Bits as index
965
966 if (p == NULL) return NULL;
967 while (*p < (state & mask)) p++;
968 if (*p == 0xffffffff) return NULL; // reached end of list, no match
969 if ((*p & mask) == (state & mask)) return p; // found a match.
970 return NULL; // no match
971 }
972
973
974 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)
975 {
976 uint_fast8_t j_1_bit_mask = 0x01 << (bit-1);
977 uint_fast8_t bit_diff = byte_diff & j_1_bit_mask; // difference of (j-1)th bit
978 uint_fast8_t filter_diff = filter(state1 >> (4-state_bit)) ^ filter(state2 >> (4-state_bit)); // difference in filter function
979 uint_fast8_t mask_y12_y13 = 0xc0 >> state_bit;
980 uint_fast8_t state_bits_diff = (state1 ^ state2) & mask_y12_y13; // difference in state bits 12 and 13
981 uint_fast8_t all_diff = evenparity8(bit_diff ^ state_bits_diff ^ filter_diff); // use parity function to XOR all bits
982 return !all_diff;
983 }
984
985
986 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)
987 {
988 uint_fast8_t j_bit_mask = 0x01 << bit;
989 uint_fast8_t bit_diff = byte_diff & j_bit_mask; // difference of jth bit
990 uint_fast8_t mask_y13_y16 = 0x48 >> state_bit;
991 uint_fast8_t state_bits_diff = (state1 ^ state2) & mask_y13_y16; // difference in state bits 13 and 16
992 uint_fast8_t all_diff = evenparity8(bit_diff ^ state_bits_diff); // use parity function to XOR all bits
993 return all_diff;
994 }
995
996
997 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)
998 {
999 if (odd_even) {
1000 // odd bits
1001 switch (num_common_bits) {
1002 case 0: if (!invariant_holds(byte_diff, state1, state2, 1, 0)) return true;
1003 case 1: if (invalid_state(byte_diff, state1, state2, 1, 0)) return false;
1004 case 2: if (!invariant_holds(byte_diff, state1, state2, 3, 1)) return true;
1005 case 3: if (invalid_state(byte_diff, state1, state2, 3, 1)) return false;
1006 case 4: if (!invariant_holds(byte_diff, state1, state2, 5, 2)) return true;
1007 case 5: if (invalid_state(byte_diff, state1, state2, 5, 2)) return false;
1008 case 6: if (!invariant_holds(byte_diff, state1, state2, 7, 3)) return true;
1009 case 7: if (invalid_state(byte_diff, state1, state2, 7, 3)) return false;
1010 }
1011 } else {
1012 // even bits
1013 switch (num_common_bits) {
1014 case 0: if (invalid_state(byte_diff, state1, state2, 0, 0)) return false;
1015 case 1: if (!invariant_holds(byte_diff, state1, state2, 2, 1)) return true;
1016 case 2: if (invalid_state(byte_diff, state1, state2, 2, 1)) return false;
1017 case 3: if (!invariant_holds(byte_diff, state1, state2, 4, 2)) return true;
1018 case 4: if (invalid_state(byte_diff, state1, state2, 4, 2)) return false;
1019 case 5: if (!invariant_holds(byte_diff, state1, state2, 6, 3)) return true;
1020 case 6: if (invalid_state(byte_diff, state1, state2, 6, 3)) return false;
1021 }
1022 }
1023
1024 return true; // valid state
1025 }
1026
1027
1028 static bool all_other_first_bytes_match(uint32_t state, odd_even_t odd_even)
1029 {
1030 for (uint16_t i = 1; i < num_good_first_bytes; i++) {
1031 uint16_t sum_a8 = nonces[best_first_bytes[i]].Sum8_guess;
1032 uint_fast8_t bytes_diff = best_first_bytes[0] ^ best_first_bytes[i];
1033 uint_fast8_t j = common_bits(bytes_diff);
1034 uint32_t mask = 0xfffffff0;
1035 if (odd_even == ODD_STATE) {
1036 mask >>= j/2;
1037 } else {
1038 mask >>= (j+1)/2;
1039 }
1040 mask &= 0x000fffff;
1041 //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);
1042 bool found_match = false;
1043 for (uint16_t r = 0; r <= 16 && !found_match; r += 2) {
1044 for (uint16_t s = 0; s <= 16 && !found_match; s += 2) {
1045 if (r*(16-s) + (16-r)*s == sum_a8) {
1046 //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);
1047 uint16_t part_sum_a8 = (odd_even == ODD_STATE) ? r : s;
1048 uint32_t *p = find_first_state(state, mask, &partial_statelist[part_sum_a8], odd_even);
1049 if (p != NULL) {
1050 while ((state & mask) == (*p & mask) && (*p != 0xffffffff)) {
1051 if (remaining_bits_match(j, bytes_diff, state, (state&0x00fffff0) | *p, odd_even)) {
1052 found_match = true;
1053 // if ((odd_even == ODD_STATE && state == test_state_odd)
1054 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1055 // printf("all_other_first_bytes_match(): %s test state: remaining bits matched. Bytes = %02x, %02x, Common Bits=%d, mask=0x%08x, PartSum(a8)=%d\n",
1056 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1057 // }
1058 break;
1059 } else {
1060 // if ((odd_even == ODD_STATE && state == test_state_odd)
1061 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1062 // 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",
1063 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1064 // }
1065 }
1066 p++;
1067 }
1068 } else {
1069 // if ((odd_even == ODD_STATE && state == test_state_odd)
1070 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1071 // 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",
1072 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1073 // }
1074 }
1075 }
1076 }
1077 }
1078
1079 if (!found_match) {
1080 // if ((odd_even == ODD_STATE && state == test_state_odd)
1081 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1082 // 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);
1083 // }
1084 return false;
1085 }
1086 }
1087
1088 return true;
1089 }
1090
1091
1092 static bool all_bit_flips_match(uint32_t state, odd_even_t odd_even)
1093 {
1094 for (uint16_t i = 0; i < 256; i++) {
1095 if (nonces[i].BitFlip[odd_even] && i != best_first_bytes[0]) {
1096 uint_fast8_t bytes_diff = best_first_bytes[0] ^ i;
1097 uint_fast8_t j = common_bits(bytes_diff);
1098 uint32_t mask = 0xfffffff0;
1099 if (odd_even == ODD_STATE) {
1100 mask >>= j/2;
1101 } else {
1102 mask >>= (j+1)/2;
1103 }
1104 mask &= 0x000fffff;
1105 //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);
1106 bool found_match = false;
1107 uint32_t *p = find_first_state(state, mask, &statelist_bitflip, 0);
1108 if (p != NULL) {
1109 while ((state & mask) == (*p & mask) && (*p != 0xffffffff)) {
1110 if (remaining_bits_match(j, bytes_diff, state, (state&0x00fffff0) | *p, odd_even)) {
1111 found_match = true;
1112 // if ((odd_even == ODD_STATE && state == test_state_odd)
1113 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1114 // printf("all_other_first_bytes_match(): %s test state: remaining bits matched. Bytes = %02x, %02x, Common Bits=%d, mask=0x%08x, PartSum(a8)=%d\n",
1115 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1116 // }
1117 break;
1118 } else {
1119 // if ((odd_even == ODD_STATE && state == test_state_odd)
1120 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1121 // 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",
1122 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1123 // }
1124 }
1125 p++;
1126 }
1127 } else {
1128 // if ((odd_even == ODD_STATE && state == test_state_odd)
1129 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1130 // printf("all_other_first_bytes_match(): %s test state: couldn't find a matching state. Bytes = %02x, %02x, Common Bits=%d, mask=0x%08x, PartSum(a8)=%d\n",
1131 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1132 // }
1133 }
1134 if (!found_match) {
1135 // if ((odd_even == ODD_STATE && state == test_state_odd)
1136 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1137 // 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);
1138 // }
1139 return false;
1140 }
1141 }
1142
1143 }
1144
1145 return true;
1146 }
1147
1148
1149 static struct sl_cache_entry {
1150 uint32_t *sl;
1151 uint32_t len;
1152 } sl_cache[17][17][2];
1153
1154
1155 static void init_statelist_cache(void)
1156 {
1157 for (uint16_t i = 0; i < 17; i+=2) {
1158 for (uint16_t j = 0; j < 17; j+=2) {
1159 for (uint16_t k = 0; k < 2; k++) {
1160 sl_cache[i][j][k].sl = NULL;
1161 sl_cache[i][j][k].len = 0;
1162 }
1163 }
1164 }
1165 }
1166
1167
1168 static int add_matching_states(statelist_t *candidates, uint16_t part_sum_a0, uint16_t part_sum_a8, odd_even_t odd_even)
1169 {
1170 uint32_t worstcase_size = 1<<20;
1171
1172 // check cache for existing results
1173 if (sl_cache[part_sum_a0][part_sum_a8][odd_even].sl != NULL) {
1174 candidates->states[odd_even] = sl_cache[part_sum_a0][part_sum_a8][odd_even].sl;
1175 candidates->len[odd_even] = sl_cache[part_sum_a0][part_sum_a8][odd_even].len;
1176 return 0;
1177 }
1178
1179 candidates->states[odd_even] = (uint32_t *)malloc(sizeof(uint32_t) * worstcase_size);
1180 if (candidates->states[odd_even] == NULL) {
1181 PrintAndLog("Out of memory error.\n");
1182 return 4;
1183 }
1184 uint32_t *add_p = candidates->states[odd_even];
1185 for (uint32_t *p1 = partial_statelist[part_sum_a0].states[odd_even]; *p1 != 0xffffffff; p1++) {
1186 uint32_t search_mask = 0x000ffff0;
1187 uint32_t *p2 = find_first_state((*p1 << 4), search_mask, &partial_statelist[part_sum_a8], odd_even);
1188 if (p2 != NULL) {
1189 while (((*p1 << 4) & search_mask) == (*p2 & search_mask) && *p2 != 0xffffffff) {
1190 if ((nonces[best_first_bytes[0]].BitFlip[odd_even] && find_first_state((*p1 << 4) | *p2, 0x000fffff, &statelist_bitflip, 0))
1191 || !nonces[best_first_bytes[0]].BitFlip[odd_even]) {
1192 if (all_other_first_bytes_match((*p1 << 4) | *p2, odd_even)) {
1193 if (all_bit_flips_match((*p1 << 4) | *p2, odd_even)) {
1194 *add_p++ = (*p1 << 4) | *p2;
1195 }
1196 }
1197 }
1198 p2++;
1199 }
1200 }
1201 }
1202
1203 // set end of list marker and len
1204 *add_p = 0xffffffff;
1205 candidates->len[odd_even] = add_p - candidates->states[odd_even];
1206
1207 candidates->states[odd_even] = realloc(candidates->states[odd_even], sizeof(uint32_t) * (candidates->len[odd_even] + 1));
1208
1209 sl_cache[part_sum_a0][part_sum_a8][odd_even].sl = candidates->states[odd_even];
1210 sl_cache[part_sum_a0][part_sum_a8][odd_even].len = candidates->len[odd_even];
1211
1212 return 0;
1213 }
1214
1215
1216 static statelist_t *add_more_candidates(statelist_t *current_candidates)
1217 {
1218 statelist_t *new_candidates = NULL;
1219 if (current_candidates == NULL) {
1220 if (candidates == NULL) {
1221 candidates = (statelist_t *)malloc(sizeof(statelist_t));
1222 }
1223 new_candidates = candidates;
1224 } else {
1225 new_candidates = current_candidates->next = (statelist_t *)malloc(sizeof(statelist_t));
1226 }
1227 new_candidates->next = NULL;
1228 new_candidates->len[ODD_STATE] = 0;
1229 new_candidates->len[EVEN_STATE] = 0;
1230 new_candidates->states[ODD_STATE] = NULL;
1231 new_candidates->states[EVEN_STATE] = NULL;
1232 return new_candidates;
1233 }
1234
1235
1236 static void TestIfKeyExists(uint64_t key)
1237 {
1238 struct Crypto1State *pcs;
1239 pcs = crypto1_create(key);
1240 crypto1_byte(pcs, (cuid >> 24) ^ best_first_bytes[0], true);
1241
1242 uint32_t state_odd = pcs->odd & 0x00ffffff;
1243 uint32_t state_even = pcs->even & 0x00ffffff;
1244 //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);
1245
1246 uint64_t count = 0;
1247 for (statelist_t *p = candidates; p != NULL; p = p->next) {
1248 bool found_odd = false;
1249 bool found_even = false;
1250 uint32_t *p_odd = p->states[ODD_STATE];
1251 uint32_t *p_even = p->states[EVEN_STATE];
1252 while (*p_odd != 0xffffffff) {
1253 if ((*p_odd & 0x00ffffff) == state_odd) {
1254 found_odd = true;
1255 break;
1256 }
1257 p_odd++;
1258 }
1259 while (*p_even != 0xffffffff) {
1260 if ((*p_even & 0x00ffffff) == state_even) {
1261 found_even = true;
1262 }
1263 p_even++;
1264 }
1265 count += (p_odd - p->states[ODD_STATE]) * (p_even - p->states[EVEN_STATE]);
1266 if (found_odd && found_even) {
1267 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.",
1268 count, log(count)/log(2),
1269 maximum_states, log(maximum_states)/log(2),
1270 (count>>23)/60);
1271 if (write_stats) {
1272 fprintf(fstats, "1\n");
1273 }
1274 crypto1_destroy(pcs);
1275 return;
1276 }
1277 }
1278
1279 printf("Key NOT found!\n");
1280 if (write_stats) {
1281 fprintf(fstats, "0\n");
1282 }
1283 crypto1_destroy(pcs);
1284 }
1285
1286
1287 static void generate_candidates(uint16_t sum_a0, uint16_t sum_a8)
1288 {
1289 printf("Generating crypto1 state candidates... \n");
1290
1291 statelist_t *current_candidates = NULL;
1292 // estimate maximum candidate states
1293 maximum_states = 0;
1294 for (uint16_t sum_odd = 0; sum_odd <= 16; sum_odd += 2) {
1295 for (uint16_t sum_even = 0; sum_even <= 16; sum_even += 2) {
1296 if (sum_odd*(16-sum_even) + (16-sum_odd)*sum_even == sum_a0) {
1297 maximum_states += (uint64_t)partial_statelist[sum_odd].len[ODD_STATE] * partial_statelist[sum_even].len[EVEN_STATE] * (1<<8);
1298 }
1299 }
1300 }
1301 printf("Number of possible keys with Sum(a0) = %d: %lld (2^%1.1f)\n", sum_a0, maximum_states, log(maximum_states)/log(2.0));
1302
1303 init_statelist_cache();
1304
1305 for (uint16_t p = 0; p <= 16; p += 2) {
1306 for (uint16_t q = 0; q <= 16; q += 2) {
1307 if (p*(16-q) + (16-p)*q == sum_a0) {
1308 printf("Reducing Partial Statelists (p,q) = (%d,%d) with lengths %d, %d\n",
1309 p, q, partial_statelist[p].len[ODD_STATE], partial_statelist[q].len[EVEN_STATE]);
1310 for (uint16_t r = 0; r <= 16; r += 2) {
1311 for (uint16_t s = 0; s <= 16; s += 2) {
1312 if (r*(16-s) + (16-r)*s == sum_a8) {
1313 current_candidates = add_more_candidates(current_candidates);
1314 // check for the smallest partial statelist. Try this first - it might give 0 candidates
1315 // and eliminate the need to calculate the other part
1316 if (MIN(partial_statelist[p].len[ODD_STATE], partial_statelist[r].len[ODD_STATE])
1317 < MIN(partial_statelist[q].len[EVEN_STATE], partial_statelist[s].len[EVEN_STATE])) {
1318 add_matching_states(current_candidates, p, r, ODD_STATE);
1319 if(current_candidates->len[ODD_STATE]) {
1320 add_matching_states(current_candidates, q, s, EVEN_STATE);
1321 } else {
1322 current_candidates->len[EVEN_STATE] = 0;
1323 uint32_t *p = current_candidates->states[EVEN_STATE] = malloc(sizeof(uint32_t));
1324 *p = 0xffffffff;
1325 }
1326 } else {
1327 add_matching_states(current_candidates, q, s, EVEN_STATE);
1328 if(current_candidates->len[EVEN_STATE]) {
1329 add_matching_states(current_candidates, p, r, ODD_STATE);
1330 } else {
1331 current_candidates->len[ODD_STATE] = 0;
1332 uint32_t *p = current_candidates->states[ODD_STATE] = malloc(sizeof(uint32_t));
1333 *p = 0xffffffff;
1334 }
1335 }
1336 printf("Odd state candidates: %6d (2^%0.1f)\n", current_candidates->len[ODD_STATE], log(current_candidates->len[ODD_STATE])/log(2));
1337 printf("Even state candidates: %6d (2^%0.1f)\n", current_candidates->len[EVEN_STATE], log(current_candidates->len[EVEN_STATE])/log(2));
1338 }
1339 }
1340 }
1341 }
1342 }
1343 }
1344
1345
1346 maximum_states = 0;
1347 for (statelist_t *sl = candidates; sl != NULL; sl = sl->next) {
1348 maximum_states += (uint64_t)sl->len[ODD_STATE] * sl->len[EVEN_STATE];
1349 }
1350 printf("Number of remaining possible keys: %lld (2^%1.1f)\n", maximum_states, log(maximum_states)/log(2.0));
1351 if (write_stats) {
1352 if (maximum_states != 0) {
1353 fprintf(fstats, "%1.1f;", log(maximum_states)/log(2.0));
1354 } else {
1355 fprintf(fstats, "%1.1f;", 0.0);
1356 }
1357 }
1358 }
1359
1360
1361 static void free_candidates_memory(statelist_t *sl)
1362 {
1363 if (sl == NULL) {
1364 return;
1365 } else {
1366 free_candidates_memory(sl->next);
1367 free(sl);
1368 }
1369 }
1370
1371
1372 static void free_statelist_cache(void)
1373 {
1374 for (uint16_t i = 0; i < 17; i+=2) {
1375 for (uint16_t j = 0; j < 17; j+=2) {
1376 for (uint16_t k = 0; k < 2; k++) {
1377 free(sl_cache[i][j][k].sl);
1378 }
1379 }
1380 }
1381 }
1382
1383
1384 static void brute_force(void)
1385 {
1386 if (known_target_key != -1) {
1387 PrintAndLog("Looking for known target key in remaining key space...");
1388 TestIfKeyExists(known_target_key);
1389 } else {
1390 PrintAndLog("Brute Force phase is not implemented.");
1391 }
1392
1393 }
1394
1395
1396 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)
1397 {
1398 // initialize Random number generator
1399 time_t t;
1400 srand((unsigned) time(&t));
1401
1402 if (trgkey != NULL) {
1403 known_target_key = bytes_to_num(trgkey, 6);
1404 } else {
1405 known_target_key = -1;
1406 }
1407
1408 init_partial_statelists();
1409 init_BitFlip_statelist();
1410 write_stats = false;
1411
1412 if (tests) {
1413 // set the correct locale for the stats printing
1414 setlocale(LC_ALL, "");
1415 write_stats = true;
1416 if ((fstats = fopen("hardnested_stats.txt","a")) == NULL) {
1417 PrintAndLog("Could not create/open file hardnested_stats.txt");
1418 return 3;
1419 }
1420 for (uint32_t i = 0; i < tests; i++) {
1421 init_nonce_memory();
1422 simulate_acquire_nonces();
1423 Tests();
1424 printf("Sum(a0) = %d\n", first_byte_Sum);
1425 fprintf(fstats, "%d;", first_byte_Sum);
1426 generate_candidates(first_byte_Sum, nonces[best_first_bytes[0]].Sum8_guess);
1427 brute_force();
1428 free_nonces_memory();
1429 free_statelist_cache();
1430 free_candidates_memory(candidates);
1431 candidates = NULL;
1432 }
1433 fclose(fstats);
1434 } else {
1435 init_nonce_memory();
1436 if (nonce_file_read) { // use pre-acquired data from file nonces.bin
1437 if (read_nonce_file() != 0) {
1438 return 3;
1439 }
1440 Check_for_FilterFlipProperties();
1441 num_good_first_bytes = MIN(estimate_second_byte_sum(), GOOD_BYTES_REQUIRED);
1442 } else { // acquire nonces.
1443 uint16_t is_OK = acquire_nonces(blockNo, keyType, key, trgBlockNo, trgKeyType, nonce_file_write, slow);
1444 if (is_OK != 0) {
1445 return is_OK;
1446 }
1447 }
1448
1449 Tests();
1450
1451 PrintAndLog("");
1452 PrintAndLog("Sum(a0) = %d", first_byte_Sum);
1453 // PrintAndLog("Best 10 first bytes: %02x, %02x, %02x, %02x, %02x, %02x, %02x, %02x, %02x, %02x",
1454 // best_first_bytes[0],
1455 // best_first_bytes[1],
1456 // best_first_bytes[2],
1457 // best_first_bytes[3],
1458 // best_first_bytes[4],
1459 // best_first_bytes[5],
1460 // best_first_bytes[6],
1461 // best_first_bytes[7],
1462 // best_first_bytes[8],
1463 // best_first_bytes[9] );
1464 PrintAndLog("Number of first bytes with confidence > %2.1f%%: %d", CONFIDENCE_THRESHOLD*100.0, num_good_first_bytes);
1465
1466 clock_t start_time = clock();
1467 generate_candidates(first_byte_Sum, nonces[best_first_bytes[0]].Sum8_guess);
1468 PrintAndLog("Time for generating key candidates list: %1.0f seconds", (float)(clock() - start_time)/CLOCKS_PER_SEC);
1469
1470 brute_force();
1471 free_nonces_memory();
1472 free_statelist_cache();
1473 free_candidates_memory(candidates);
1474 candidates = NULL;
1475 }
1476
1477 return 0;
1478 }
1479
1480
Proxmark3 GIT tracking
Impressum, Datenschutz