]> cvs.zerfleddert.de Git - proxmark3-svn/blame - client/cmdhfmfhard.c
projects / proxmark3-svn / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
FIX: Coverity, Dereference null return, CID #212329, filehandle could be NULL
[proxmark3-svn] / client / cmdhfmfhard.c
CommitLineData
8ce3e4b4 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"
f8ada309 27#include "parity.h"
8ce3e4b4 28
29// uint32_t test_state_odd = 0;
30// uint32_t test_state_even = 0;
31
f8ada309 32#define CONFIDENCE_THRESHOLD 0.95 // Collect nonces until we are certain enough that the following brute force is successfull
fe8042f2 33#define GOOD_BYTES_REQUIRED 30
8ce3e4b4 34
35
36static 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
72typedef struct noncelistentry {
73 uint32_t nonce_enc;
74 uint8_t par_enc;
75 void *next;
76} noncelistentry_t;
77
78typedef 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;
a531720a 86 float score1, score2;
8ce3e4b4 87} noncelist_t;
88
89
90static uint32_t cuid;
91static noncelist_t nonces[256];
fe8042f2 92static uint8_t best_first_bytes[256];
8ce3e4b4 93static uint16_t first_byte_Sum = 0;
94static uint16_t first_byte_num = 0;
95static uint16_t num_good_first_bytes = 0;
f8ada309 96static uint64_t maximum_states = 0;
97static uint64_t known_target_key;
8ce3e4b4 98
8ce3e4b4 99
100
101typedef 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
109typedef 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
115typedef struct {
116 uint32_t *states[2];
117 uint32_t len[2];
118 void* next;
119} statelist_t;
120
121
f8ada309 122static partial_indexed_statelist_t partial_statelist[17];
123static partial_indexed_statelist_t statelist_bitflip;
8ce3e4b4 124
f8ada309 125static statelist_t *candidates = NULL;
8ce3e4b4 126
127
128static 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++;
f8ada309 136 first_byte_Sum += evenparity32((nonce_enc & 0xff000000) | (par_enc & 0x08));
8ce3e4b4 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,
f8ada309 141 // parity((nonce_enc & 0xff000000) | (par_enc & 0x08));
8ce3e4b4 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++;
f8ada309 171 nonces[first_byte].Sum += evenparity32((nonce_enc & 0x00ff0000) | (par_enc & 0x04));
8ce3e4b4 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
178static 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 }
f8ada309 189 part_sum ^= 1; // XOR 1 cancelled out for the other 8 bits
8ce3e4b4 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
fe8042f2 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// }
8ce3e4b4 208
209
210static 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
249static 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
a531720a 269
270
271static 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
8ce3e4b4 296static void Tests()
297{
fe8042f2 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 // }
8ce3e4b4 305
306 // #define NUM_STATISTICS 100000
8ce3e4b4 307 // uint32_t statistics_odd[17];
f8ada309 308 // uint64_t statistics[257];
8ce3e4b4 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
fe8042f2 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);
f8ada309 408 //test_state_odd = pcs->odd & 0x00ffffff;
409 //test_state_even = pcs->even & 0x00ffffff;
fe8042f2 410 // crypto1_destroy(pcs);
8ce3e4b4 411
412
fe8042f2 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));
8ce3e4b4 415
416 printf("\nTests: Actual BitFlipProperties odd/even:\n");
417 for (uint16_t i = 0; i < 256; i++) {
fe8042f2 418 printf("[%02x]:%c ", i, nonces[i].BitFlip[ODD_STATE]?'o':nonces[i].BitFlip[EVEN_STATE]?'e':' ');
8ce3e4b4 419 if (i % 8 == 7) {
420 printf("\n");
421 }
422 }
423
fe8042f2 424 printf("\nTests: Sorted First Bytes:\n");
425 for (uint16_t i = 0; i < 256; i++) {
8ce3e4b4 426 uint8_t best_byte = best_first_bytes[i];
fe8042f2 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",
a531720a 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,
fe8042f2 434 nonces[best_byte].BitFlip[ODD_STATE]?'o':nonces[best_byte].BitFlip[EVEN_STATE]?'e':' '
a531720a 435 //nonces[best_byte].score1,
436 //nonces[best_byte].score2
437 );
8ce3e4b4 438 }
f8ada309 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
8ce3e4b4 455
f8ada309 456}
457
458
459static void sort_best_first_bytes(void)
460{
fe8042f2 461 // sort based on probability for correct guess
8ce3e4b4 462 for (uint16_t i = 0; i < 256; i++ ) {
f8ada309 463 uint16_t j = 0;
8ce3e4b4 464 float prob1 = nonces[i].Sum8_prob;
f8ada309 465 float prob2 = nonces[best_first_bytes[0]].Sum8_prob;
fe8042f2 466 while (prob1 < prob2 && j < i) {
8ce3e4b4 467 prob2 = nonces[best_first_bytes[++j]].Sum8_prob;
468 }
fe8042f2 469 if (j < i) {
470 for (uint16_t k = i; k > j; k--) {
8ce3e4b4 471 best_first_bytes[k] = best_first_bytes[k-1];
472 }
fe8042f2 473 }
8ce3e4b4 474 best_first_bytes[j] = i;
475 }
f8ada309 476
fe8042f2 477 // determine how many are above the CONFIDENCE_THRESHOLD
f8ada309 478 uint16_t num_good_nonces = 0;
fe8042f2 479 for (uint16_t i = 0; i < 256; i++) {
f8ada309 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 }
a531720a 510 nonces[best_first_bytes[i]].score1 = p_K[sum8] * bitflip_prob;
f8ada309 511 if (p_K[sum8] * bitflip_prob <= min_p_K) {
512 min_p_K = p_K[sum8] * bitflip_prob;
f8ada309 513 }
514 }
515
a531720a 516
f8ada309 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++) {
a531720a 527 sum_common_bits += common_bits(best_first_bytes[i] ^ best_first_bytes[j]);
f8ada309 528 }
a531720a 529 nonces[best_first_bytes[i]].score2 = sum_common_bits;
f8ada309 530 if (sum_common_bits > max_common_bits) {
531 max_common_bits = sum_common_bits;
532 best_first_byte = i;
533 }
534 }
535 }
536
a531720a 537 // swap best possible first byte to the pole position
f8ada309 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
8ce3e4b4 542}
543
544
545static uint16_t estimate_second_byte_sum(void)
546{
8ce3e4b4 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;
fe8042f2 568 for (uint16_t i = 0; i < 256; i++) {
8ce3e4b4 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
578static 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
a531720a 620static 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
f8ada309 643static int acquire_nonces(uint8_t blockNo, uint8_t keyType, uint8_t *key, uint8_t trgBlockNo, uint8_t trgKeyType, bool nonce_file_write, bool slow)
8ce3e4b4 644{
645 clock_t time1 = clock();
646 bool initialize = true;
647 bool field_off = false;
648 bool finished = false;
a531720a 649 bool filter_flip_checked = false;
8ce3e4b4 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);
a531720a 721 if (!filter_flip_checked) {
722 Check_for_FilterFlipProperties();
723 filter_flip_checked = true;
724 }
8ce3e4b4 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
f8ada309 753 PrintAndLog("Acquired a total of %d nonces in %1.1f seconds (%0.0f nonces/minute)",
8ce3e4b4 754 total_num_nonces,
755 ((float)clock()-time1)/CLOCKS_PER_SEC,
f8ada309 756 total_num_nonces*60.0*CLOCKS_PER_SEC/((float)clock()-time1));
8ce3e4b4 757
758 return 0;
759}
760
761
762static int init_partial_statelists(void)
763{
f8ada309 764 const uint32_t sizes_odd[17] = { 126757, 0, 18387, 0, 74241, 0, 181737, 0, 248801, 0, 182033, 0, 73421, 0, 17607, 0, 125601 };
8ce3e4b4 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
813static 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
a531720a 837static inline uint32_t *find_first_state(uint32_t state, uint32_t mask, partial_indexed_statelist_t *sl, odd_even_t odd_even)
8ce3e4b4 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;
a531720a 842 while (*p < (state & mask)) p++;
8ce3e4b4 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
a531720a 849static 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)
8ce3e4b4 850{
a531720a 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
861static 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
872static 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;
8ce3e4b4 885 }
a531720a 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;
8ce3e4b4 896 }
8ce3e4b4 897 }
898
899 return true; // valid state
900}
901
902
903static 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;
a531720a 907 uint_fast8_t bytes_diff = best_first_bytes[0] ^ best_first_bytes[i];
908 uint_fast8_t j = common_bits(bytes_diff);
8ce3e4b4 909 uint32_t mask = 0xfffffff0;
910 if (odd_even == ODD_STATE) {
a531720a 911 mask >>= j/2;
8ce3e4b4 912 } else {
a531720a 913 mask >>= (j+1)/2;
8ce3e4b4 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)) {
a531720a 926 if (remaining_bits_match(j, bytes_diff, state, (state&0x00fffff0) | *p, odd_even)) {
8ce3e4b4 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
f8ada309 967static 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]) {
a531720a 971 uint_fast8_t bytes_diff = best_first_bytes[0] ^ i;
972 uint_fast8_t j = common_bits(bytes_diff);
f8ada309 973 uint32_t mask = 0xfffffff0;
974 if (odd_even == ODD_STATE) {
a531720a 975 mask >>= j/2;
f8ada309 976 } else {
a531720a 977 mask >>= (j+1)/2;
f8ada309 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)) {
a531720a 985 if (remaining_bits_match(j, bytes_diff, state, (state&0x00fffff0) | *p, odd_even)) {
f8ada309 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
a531720a 1024static struct sl_cache_entry {
1025 uint32_t *sl;
1026 uint32_t len;
1027 } sl_cache[17][17][2];
1028
1029
1030static 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
f8ada309 1043
8ce3e4b4 1044static 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
a531720a 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
8ce3e4b4 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 }
a531720a 1060 uint32_t *add_p = candidates->states[odd_even];
8ce3e4b4 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) {
a531720a 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]) {
8ce3e4b4 1068 if (all_other_first_bytes_match((*p1 << 4) | *p2, odd_even)) {
f8ada309 1069 if (all_bit_flips_match((*p1 << 4) | *p2, odd_even)) {
a531720a 1070 *add_p++ = (*p1 << 4) | *p2;
1071 }
8ce3e4b4 1072 }
f8ada309 1073 }
8ce3e4b4 1074 p2++;
1075 }
1076 }
8ce3e4b4 1077 }
f8ada309 1078
a531720a 1079 // set end of list marker and len
1080 *add_p = 0xffffffff;
1081 candidates->len[odd_even] = add_p - candidates->states[odd_even];
f8ada309 1082
8ce3e4b4 1083 candidates->states[odd_even] = realloc(candidates->states[odd_even], sizeof(uint32_t) * (candidates->len[odd_even] + 1));
1084
a531720a 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
8ce3e4b4 1088 return 0;
1089}
1090
1091
1092static 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
1112static 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;
f8ada309 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);
8ce3e4b4 1121
f8ada309 1122 uint64_t count = 0;
8ce3e4b4 1123 for (statelist_t *p = candidates; p != NULL; p = p->next) {
f8ada309 1124 bool found_odd = false;
1125 bool found_even = false;
8ce3e4b4 1126 uint32_t *p_odd = p->states[ODD_STATE];
1127 uint32_t *p_even = p->states[EVEN_STATE];
1128 while (*p_odd != 0xffffffff) {
f8ada309 1129 if ((*p_odd & 0x00ffffff) == state_odd) {
1130 found_odd = true;
1131 break;
1132 }
8ce3e4b4 1133 p_odd++;
1134 }
1135 while (*p_even != 0xffffffff) {
f8ada309 1136 if ((*p_even & 0x00ffffff) == state_even) {
1137 found_even = true;
1138 }
8ce3e4b4 1139 p_even++;
1140 }
f8ada309 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),
fe8042f2 1146 (count>>23)/60);
f8ada309 1147 crypto1_destroy(pcs);
1148 return;
1149 }
8ce3e4b4 1150 }
f8ada309 1151
1152 printf("Key NOT found!\n");
8ce3e4b4 1153 crypto1_destroy(pcs);
1154}
1155
1156
1157static 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
f8ada309 1163 maximum_states = 0;
8ce3e4b4 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
a531720a 1173 init_statelist_cache();
1174
8ce3e4b4 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);
a531720a 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])) {
8ce3e4b4 1188 add_matching_states(current_candidates, p, r, ODD_STATE);
a531720a 1189 if(current_candidates->len[ODD_STATE]) {
8ce3e4b4 1190 add_matching_states(current_candidates, q, s, EVEN_STATE);
a531720a 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));
8ce3e4b4 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
8ce3e4b4 1222}
1223
1224
f8ada309 1225static void brute_force(void)
8ce3e4b4 1226{
f8ada309 1227 if (known_target_key != -1) {
1228 PrintAndLog("Looking for known target key in remaining key space...");
1229 TestIfKeyExists(known_target_key);
f8ada309 1230 } else {
1231 PrintAndLog("Brute Force phase is not implemented.");
f8ada309 1232 }
f8ada309 1233
1234}
1235
1236
1237int 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 }
8ce3e4b4 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 }
a531720a 1265 Check_for_FilterFlipProperties();
f8ada309 1266 num_good_first_bytes = MIN(estimate_second_byte_sum(), GOOD_BYTES_REQUIRED);
8ce3e4b4 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
8ce3e4b4 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
a531720a 1292 time_t start_time = clock();
8ce3e4b4 1293 generate_candidates(first_byte_Sum, nonces[best_first_bytes[0]].Sum8_guess);
a531720a 1294 PrintAndLog("Time for generating key candidates list: %1.0f seconds", (float)(clock() - start_time)/CLOCKS_PER_SEC);
8ce3e4b4 1295
f8ada309 1296 brute_force();
8ce3e4b4 1297
1298 return 0;
1299}
1300
1301
Proxmark3 GIT tracking
Impressum, Datenschutz