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