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