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