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