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