]> git.zerfleddert.de Git - proxmark3-svn/blame - client/nonce2key/crapto1.c
FIX: Coverity, unchecked return value, CID #121292,..
[proxmark3-svn] / client / nonce2key / crapto1.c
CommitLineData
f89c7050
M
1/* crapto1.c\r
2\r
3 This program is free software; you can redistribute it and/or\r
4 modify it under the terms of the GNU General Public License\r
5 as published by the Free Software Foundation; either version 2\r
6 of the License, or (at your option) any later version.\r
7\r
8 This program is distributed in the hope that it will be useful,\r
9 but WITHOUT ANY WARRANTY; without even the implied warranty of\r
10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the\r
11 GNU General Public License for more details.\r
12\r
13 You should have received a copy of the GNU General Public License\r
14 along with this program; if not, write to the Free Software\r
15 Foundation, Inc., 51 Franklin Street, Fifth Floor,\r
16 Boston, MA 02110-1301, US$\r
17\r
18 Copyright (C) 2008-2008 bla <blapost@gmail.com>\r
19*/\r
20#include "crapto1.h"\r
21#include <stdlib.h>\r
22\r
23#if !defined LOWMEM && defined __GNUC__\r
a531720a 24uint8_t filterlut[1 << 20];\r
f89c7050
M
25static void __attribute__((constructor)) fill_lut()\r
26{\r
a531720a 27 uint32_t x;\r
28 uint32_t f;\r
29 for(x = 0; x < 1 << 20; ++x) {\r
30 f = 0xf22c0 >> (x & 0xf) & 16;\r
31 f |= 0x6c9c0 >> (x >> 4 & 0xf) & 8;\r
32 f |= 0x3c8b0 >> (x >> 8 & 0xf) & 4;\r
33 f |= 0x1e458 >> (x >> 12 & 0xf) & 2;\r
34 f |= 0x0d938 >> (x >> 16 & 0xf) & 1;\r
35 filterlut[x] = BIT(0xEC57E80A, f);\r
36 }\r
f89c7050 37}\r
f89c7050
M
38#endif\r
39\r
9492e0b0 40\r
41\r
42typedef struct bucket {\r
43 uint32_t *head;\r
44 uint32_t *bp;\r
45} bucket_t;\r
46\r
47typedef bucket_t bucket_array_t[2][0x100];\r
48\r
49typedef struct bucket_info {\r
50 struct {\r
51 uint32_t *head, *tail;\r
52 } bucket_info[2][0x100];\r
53 uint32_t numbuckets;\r
54 } bucket_info_t;\r
9cefee6f 55\r
9492e0b0 56\r
57static void bucket_sort_intersect(uint32_t* const estart, uint32_t* const estop,\r
58 uint32_t* const ostart, uint32_t* const ostop,\r
59 bucket_info_t *bucket_info, bucket_array_t bucket)\r
60{\r
61 uint32_t *p1, *p2;\r
62 uint32_t *start[2];\r
63 uint32_t *stop[2];\r
9cefee6f 64\r
9492e0b0 65 start[0] = estart;\r
66 stop[0] = estop;\r
67 start[1] = ostart;\r
68 stop[1] = ostop;\r
9cefee6f 69\r
9492e0b0 70 // init buckets to be empty\r
71 for (uint32_t i = 0; i < 2; i++) {\r
72 for (uint32_t j = 0x00; j <= 0xff; j++) {\r
73 bucket[i][j].bp = bucket[i][j].head;\r
74 }\r
75 }\r
9cefee6f 76\r
9492e0b0 77 // sort the lists into the buckets based on the MSB (contribution bits)\r
9cefee6f 78 for (uint32_t i = 0; i < 2; i++) {\r
9492e0b0 79 for (p1 = start[i]; p1 <= stop[i]; p1++) {\r
80 uint32_t bucket_index = (*p1 & 0xff000000) >> 24;\r
81 *(bucket[i][bucket_index].bp++) = *p1;\r
82 }\r
83 }\r
84\r
9cefee6f 85\r
9492e0b0 86 // write back intersecting buckets as sorted list.\r
87 // fill in bucket_info with head and tail of the bucket contents in the list and number of non-empty buckets.\r
88 uint32_t nonempty_bucket;\r
89 for (uint32_t i = 0; i < 2; i++) {\r
90 p1 = start[i];\r
91 nonempty_bucket = 0;\r
92 for (uint32_t j = 0x00; j <= 0xff; j++) {\r
93 if (bucket[0][j].bp != bucket[0][j].head && bucket[1][j].bp != bucket[1][j].head) { // non-empty intersecting buckets only\r
94 bucket_info->bucket_info[i][nonempty_bucket].head = p1;\r
95 for (p2 = bucket[i][j].head; p2 < bucket[i][j].bp; *p1++ = *p2++);\r
96 bucket_info->bucket_info[i][nonempty_bucket].tail = p1 - 1;\r
97 nonempty_bucket++;\r
98 }\r
99 }\r
100 bucket_info->numbuckets = nonempty_bucket;\r
101 }\r
102}\r
103\r
f89c7050
M
104/** binsearch\r
105 * Binary search for the first occurence of *stop's MSB in sorted [start,stop]\r
106 */\r
107static inline uint32_t*\r
108binsearch(uint32_t *start, uint32_t *stop)\r
109{\r
110 uint32_t mid, val = *stop & 0xff000000;\r
111 while(start != stop)\r
112 if(start[mid = (stop - start) >> 1] > val)\r
113 stop = &start[mid];\r
114 else\r
115 start += mid + 1;\r
116\r
117 return start;\r
118}\r
119\r
120/** update_contribution\r
121 * helper, calculates the partial linear feedback contributions and puts in MSB\r
122 */\r
123static inline void\r
124update_contribution(uint32_t *item, const uint32_t mask1, const uint32_t mask2)\r
125{\r
126 uint32_t p = *item >> 25;\r
127\r
128 p = p << 1 | parity(*item & mask1);\r
129 p = p << 1 | parity(*item & mask2);\r
130 *item = p << 24 | (*item & 0xffffff);\r
131}\r
132\r
133/** extend_table\r
134 * using a bit of the keystream extend the table of possible lfsr states\r
135 */\r
136static inline void\r
137extend_table(uint32_t *tbl, uint32_t **end, int bit, int m1, int m2, uint32_t in)\r
138{\r
139 in <<= 24;\r
9492e0b0 140\r
141 for(uint32_t *p = tbl; p <= *end; p++) {\r
142 *p <<= 1;\r
143 if(filter(*p) != filter(*p | 1)) { // replace\r
144 *p |= filter(*p) ^ bit;\r
145 update_contribution(p, m1, m2);\r
146 *p ^= in;\r
147 } else if(filter(*p) == bit) { // insert\r
148 *++*end = p[1];\r
149 p[1] = p[0] | 1;\r
150 update_contribution(p, m1, m2);\r
151 *p++ ^= in;\r
152 update_contribution(p, m1, m2);\r
153 *p ^= in;\r
154 } else { // drop\r
155 *p-- = *(*end)--;\r
9492e0b0 156 }\r
9492e0b0 157 }\r
9cefee6f 158\r
f89c7050 159}\r
9492e0b0 160\r
161\r
f89c7050
M
162/** extend_table_simple\r
163 * using a bit of the keystream extend the table of possible lfsr states\r
164 */\r
165static inline void\r
166extend_table_simple(uint32_t *tbl, uint32_t **end, int bit)\r
167{\r
9cefee6f 168 for(*tbl <<= 1; tbl <= *end; *++tbl <<= 1)\r
9492e0b0 169 if(filter(*tbl) ^ filter(*tbl | 1)) { // replace\r
f89c7050 170 *tbl |= filter(*tbl) ^ bit;\r
9492e0b0 171 } else if(filter(*tbl) == bit) { // insert\r
f89c7050
M
172 *++*end = *++tbl;\r
173 *tbl = tbl[-1] | 1;\r
9492e0b0 174 } else // drop\r
f89c7050
M
175 *tbl-- = *(*end)--;\r
176}\r
9492e0b0 177\r
178\r
f89c7050
M
179/** recover\r
180 * recursively narrow down the search space, 4 bits of keystream at a time\r
181 */\r
182static struct Crypto1State*\r
183recover(uint32_t *o_head, uint32_t *o_tail, uint32_t oks,\r
184 uint32_t *e_head, uint32_t *e_tail, uint32_t eks, int rem,\r
9492e0b0 185 struct Crypto1State *sl, uint32_t in, bucket_array_t bucket)\r
f89c7050 186{\r
9492e0b0 187 uint32_t *o, *e;\r
188 bucket_info_t bucket_info;\r
f89c7050
M
189\r
190 if(rem == -1) {\r
191 for(e = e_head; e <= e_tail; ++e) {\r
192 *e = *e << 1 ^ parity(*e & LF_POLY_EVEN) ^ !!(in & 4);\r
193 for(o = o_head; o <= o_tail; ++o, ++sl) {\r
194 sl->even = *o;\r
195 sl->odd = *e ^ parity(*o & LF_POLY_ODD);\r
f89c7050
M
196 }\r
197 }\r
9492e0b0 198 sl->odd = sl->even = 0;\r
f89c7050
M
199 return sl;\r
200 }\r
201\r
9492e0b0 202 for(uint32_t i = 0; i < 4 && rem--; i++) {\r
f89c7050
M
203 extend_table(o_head, &o_tail, (oks >>= 1) & 1,\r
204 LF_POLY_EVEN << 1 | 1, LF_POLY_ODD << 1, 0);\r
205 if(o_head > o_tail)\r
206 return sl;\r
207\r
208 extend_table(e_head, &e_tail, (eks >>= 1) & 1,\r
209 LF_POLY_ODD, LF_POLY_EVEN << 1 | 1, (in >>= 2) & 3);\r
210 if(e_head > e_tail)\r
211 return sl;\r
212 }\r
213\r
9492e0b0 214 bucket_sort_intersect(e_head, e_tail, o_head, o_tail, &bucket_info, bucket);\r
9cefee6f 215\r
9492e0b0 216 for (int i = bucket_info.numbuckets - 1; i >= 0; i--) {\r
217 sl = recover(bucket_info.bucket_info[1][i].head, bucket_info.bucket_info[1][i].tail, oks,\r
218 bucket_info.bucket_info[0][i].head, bucket_info.bucket_info[0][i].tail, eks,\r
219 rem, sl, in, bucket);\r
220 }\r
9cefee6f 221\r
f89c7050
M
222 return sl;\r
223}\r
224/** lfsr_recovery\r
225 * recover the state of the lfsr given 32 bits of the keystream\r
226 * additionally you can use the in parameter to specify the value\r
227 * that was fed into the lfsr at the time the keystream was generated\r
228 */\r
229struct Crypto1State* lfsr_recovery32(uint32_t ks2, uint32_t in)\r
230{\r
231 struct Crypto1State *statelist;\r
232 uint32_t *odd_head = 0, *odd_tail = 0, oks = 0;\r
233 uint32_t *even_head = 0, *even_tail = 0, eks = 0;\r
234 int i;\r
235\r
9492e0b0 236 // split the keystream into an odd and even part\r
f89c7050
M
237 for(i = 31; i >= 0; i -= 2)\r
238 oks = oks << 1 | BEBIT(ks2, i);\r
239 for(i = 30; i >= 0; i -= 2)\r
240 eks = eks << 1 | BEBIT(ks2, i);\r
241\r
242 odd_head = odd_tail = malloc(sizeof(uint32_t) << 21);\r
243 even_head = even_tail = malloc(sizeof(uint32_t) << 21);\r
244 statelist = malloc(sizeof(struct Crypto1State) << 18);\r
9492e0b0 245 if(!odd_tail-- || !even_tail-- || !statelist) {\r
f89c7050 246 goto out;\r
9492e0b0 247 }\r
f89c7050
M
248 statelist->odd = statelist->even = 0;\r
249\r
9492e0b0 250 // allocate memory for out of place bucket_sort\r
251 bucket_array_t bucket;\r
252 for (uint32_t i = 0; i < 2; i++)\r
253 for (uint32_t j = 0; j <= 0xff; j++) {\r
254 bucket[i][j].head = malloc(sizeof(uint32_t)<<14);\r
255 if (!bucket[i][j].head) {\r
256 goto out;\r
257 }\r
258 }\r
259\r
9492e0b0 260 // initialize statelists: add all possible states which would result into the rightmost 2 bits of the keystream\r
f89c7050
M
261 for(i = 1 << 20; i >= 0; --i) {\r
262 if(filter(i) == (oks & 1))\r
263 *++odd_tail = i;\r
264 if(filter(i) == (eks & 1))\r
265 *++even_tail = i;\r
266 }\r
267\r
9492e0b0 268 // extend the statelists. Look at the next 8 Bits of the keystream (4 Bit each odd and even):\r
f89c7050
M
269 for(i = 0; i < 4; i++) {\r
270 extend_table_simple(odd_head, &odd_tail, (oks >>= 1) & 1);\r
271 extend_table_simple(even_head, &even_tail, (eks >>= 1) & 1);\r
272 }\r
273\r
9492e0b0 274 // the statelists now contain all states which could have generated the last 10 Bits of the keystream.\r
275 // 22 bits to go to recover 32 bits in total. From now on, we need to take the "in"\r
276 // parameter into account.\r
277\r
278 in = (in >> 16 & 0xff) | (in << 16) | (in & 0xff00); // Byte swapping\r
279\r
bcf61bd3 280 recover(odd_head, odd_tail, oks, even_head, even_tail, eks, 11, statelist, in << 1, bucket);\r
f89c7050
M
281\r
282out:\r
283 free(odd_head);\r
284 free(even_head);\r
9492e0b0 285 for (uint32_t i = 0; i < 2; i++)\r
286 for (uint32_t j = 0; j <= 0xff; j++)\r
287 free(bucket[i][j].head);\r
9cefee6f 288\r
f89c7050
M
289 return statelist;\r
290}\r
291\r
292static const uint32_t S1[] = { 0x62141, 0x310A0, 0x18850, 0x0C428, 0x06214,\r
293 0x0310A, 0x85E30, 0xC69AD, 0x634D6, 0xB5CDE, 0xDE8DA, 0x6F46D, 0xB3C83,\r
294 0x59E41, 0xA8995, 0xD027F, 0x6813F, 0x3409F, 0x9E6FA};\r
295static const uint32_t S2[] = { 0x3A557B00, 0x5D2ABD80, 0x2E955EC0, 0x174AAF60,\r
296 0x0BA557B0, 0x05D2ABD8, 0x0449DE68, 0x048464B0, 0x42423258, 0x278192A8,\r
297 0x156042D0, 0x0AB02168, 0x43F89B30, 0x61FC4D98, 0x765EAD48, 0x7D8FDD20,\r
298 0x7EC7EE90, 0x7F63F748, 0x79117020};\r
299static const uint32_t T1[] = {\r
300 0x4F37D, 0x279BE, 0x97A6A, 0x4BD35, 0x25E9A, 0x12F4D, 0x097A6, 0x80D66,\r
301 0xC4006, 0x62003, 0xB56B4, 0x5AB5A, 0xA9318, 0xD0F39, 0x6879C, 0xB057B,\r
302 0x582BD, 0x2C15E, 0x160AF, 0x8F6E2, 0xC3DC4, 0xE5857, 0x72C2B, 0x39615,\r
303 0x98DBF, 0xC806A, 0xE0680, 0x70340, 0x381A0, 0x98665, 0x4C332, 0xA272C};\r
304static const uint32_t T2[] = { 0x3C88B810, 0x5E445C08, 0x2982A580, 0x14C152C0,\r
305 0x4A60A960, 0x253054B0, 0x52982A58, 0x2FEC9EA8, 0x1156C4D0, 0x08AB6268,\r
306 0x42F53AB0, 0x217A9D58, 0x161DC528, 0x0DAE6910, 0x46D73488, 0x25CB11C0,\r
307 0x52E588E0, 0x6972C470, 0x34B96238, 0x5CFC3A98, 0x28DE96C8, 0x12CFC0E0,\r
308 0x4967E070, 0x64B3F038, 0x74F97398, 0x7CDC3248, 0x38CE92A0, 0x1C674950,\r
309 0x0E33A4A8, 0x01B959D0, 0x40DCACE8, 0x26CEDDF0};\r
310static const uint32_t C1[] = { 0x846B5, 0x4235A, 0x211AD};\r
311static const uint32_t C2[] = { 0x1A822E0, 0x21A822E0, 0x21A822E0};\r
312/** Reverse 64 bits of keystream into possible cipher states\r
313 * Variation mentioned in the paper. Somewhat optimized version\r
314 */\r
315struct Crypto1State* lfsr_recovery64(uint32_t ks2, uint32_t ks3)\r
316{\r
317 struct Crypto1State *statelist, *sl;\r
318 uint8_t oks[32], eks[32], hi[32];\r
319 uint32_t low = 0, win = 0;\r
320 uint32_t *tail, table[1 << 16];\r
321 int i, j;\r
322\r
323 sl = statelist = malloc(sizeof(struct Crypto1State) << 4);\r
324 if(!sl)\r
325 return 0;\r
326 sl->odd = sl->even = 0;\r
327\r
328 for(i = 30; i >= 0; i -= 2) {\r
329 oks[i >> 1] = BIT(ks2, i ^ 24);\r
330 oks[16 + (i >> 1)] = BIT(ks3, i ^ 24);\r
331 }\r
332 for(i = 31; i >= 0; i -= 2) {\r
333 eks[i >> 1] = BIT(ks2, i ^ 24);\r
334 eks[16 + (i >> 1)] = BIT(ks3, i ^ 24);\r
335 }\r
336\r
337 for(i = 0xfffff; i >= 0; --i) {\r
338 if (filter(i) != oks[0])\r
339 continue;\r
340\r
341 *(tail = table) = i;\r
342 for(j = 1; tail >= table && j < 29; ++j)\r
343 extend_table_simple(table, &tail, oks[j]);\r
344\r
345 if(tail < table)\r
346 continue;\r
347\r
348 for(j = 0; j < 19; ++j)\r
349 low = low << 1 | parity(i & S1[j]);\r
350 for(j = 0; j < 32; ++j)\r
351 hi[j] = parity(i & T1[j]);\r
352\r
353 for(; tail >= table; --tail) {\r
354 for(j = 0; j < 3; ++j) {\r
355 *tail = *tail << 1;\r
356 *tail |= parity((i & C1[j]) ^ (*tail & C2[j]));\r
357 if(filter(*tail) != oks[29 + j])\r
358 goto continue2;\r
359 }\r
360\r
361 for(j = 0; j < 19; ++j)\r
362 win = win << 1 | parity(*tail & S2[j]);\r
363\r
364 win ^= low;\r
365 for(j = 0; j < 32; ++j) {\r
366 win = win << 1 ^ hi[j] ^ parity(*tail & T2[j]);\r
367 if(filter(win) != eks[j])\r
368 goto continue2;\r
369 }\r
370\r
371 *tail = *tail << 1 | parity(LF_POLY_EVEN & *tail);\r
372 sl->odd = *tail ^ parity(LF_POLY_ODD & win);\r
373 sl->even = win;\r
374 ++sl;\r
375 sl->odd = sl->even = 0;\r
376 continue2:;\r
377 }\r
378 }\r
379 return statelist;\r
380}\r
381\r
382/** lfsr_rollback_bit\r
383 * Rollback the shift register in order to get previous states\r
384 */\r
385void lfsr_rollback_bit(struct Crypto1State *s, uint32_t in, int fb)\r
386{\r
387 int out;\r
9cefee6f 388 uint32_t tmp;\r
f89c7050
M
389\r
390 s->odd &= 0xffffff;\r
9cefee6f 391 tmp = s->odd;\r
392 s->odd = s->even;\r
393 s->even = tmp;\r
f89c7050
M
394\r
395 out = s->even & 1;\r
396 out ^= LF_POLY_EVEN & (s->even >>= 1);\r
397 out ^= LF_POLY_ODD & s->odd;\r
398 out ^= !!in;\r
399 out ^= filter(s->odd) & !!fb;\r
400\r
401 s->even |= parity(out) << 23;\r
402}\r
403/** lfsr_rollback_byte\r
404 * Rollback the shift register in order to get previous states\r
405 */\r
406void lfsr_rollback_byte(struct Crypto1State *s, uint32_t in, int fb)\r
407{\r
408 int i;\r
409 for (i = 7; i >= 0; --i)\r
410 lfsr_rollback_bit(s, BEBIT(in, i), fb);\r
411}\r
412/** lfsr_rollback_word\r
413 * Rollback the shift register in order to get previous states\r
414 */\r
415void lfsr_rollback_word(struct Crypto1State *s, uint32_t in, int fb)\r
416{\r
417 int i;\r
418 for (i = 31; i >= 0; --i)\r
419 lfsr_rollback_bit(s, BEBIT(in, i), fb);\r
420}\r
421\r
422/** nonce_distance\r
423 * x,y valid tag nonces, then prng_successor(x, nonce_distance(x, y)) = y\r
424 */\r
425static uint16_t *dist = 0;\r
426int nonce_distance(uint32_t from, uint32_t to)\r
427{\r
428 uint16_t x, i;\r
429 if(!dist) {\r
430 dist = malloc(2 << 16);\r
431 if(!dist)\r
432 return -1;\r
433 for (x = i = 1; i; ++i) {\r
434 dist[(x & 0xff) << 8 | x >> 8] = i;\r
435 x = x >> 1 | (x ^ x >> 2 ^ x >> 3 ^ x >> 5) << 15;\r
436 }\r
437 }\r
438 return (65535 + dist[to >> 16] - dist[from >> 16]) % 65535;\r
439}\r
440\r
441\r
442static uint32_t fastfwd[2][8] = {\r
443 { 0, 0x4BC53, 0xECB1, 0x450E2, 0x25E29, 0x6E27A, 0x2B298, 0x60ECB},\r
444 { 0, 0x1D962, 0x4BC53, 0x56531, 0xECB1, 0x135D3, 0x450E2, 0x58980}};\r
445\r
446\r
447/** lfsr_prefix_ks\r
448 *\r
449 * Is an exported helper function from the common prefix attack\r
450 * Described in the "dark side" paper. It returns an -1 terminated array\r
451 * of possible partial(21 bit) secret state.\r
452 * The required keystream(ks) needs to contain the keystream that was used to\r
453 * encrypt the NACK which is observed when varying only the 4 last bits of Nr\r
454 * only correct iff [NR_3] ^ NR_3 does not depend on Nr_3\r
455 */\r
456uint32_t *lfsr_prefix_ks(uint8_t ks[8], int isodd)\r
457{\r
458 uint32_t *candidates = malloc(4 << 21);\r
459 uint32_t c, entry;\r
460 int size, i;\r
461\r
462 if(!candidates)\r
463 return 0;\r
464\r
465 size = (1 << 21) - 1;\r
466 for(i = 0; i <= size; ++i)\r
467 candidates[i] = i;\r
468\r
469 for(c = 0; c < 8; ++c)\r
470 for(i = 0;i <= size; ++i) {\r
471 entry = candidates[i] ^ fastfwd[isodd][c];\r
472\r
473 if(filter(entry >> 1) == BIT(ks[c], isodd))\r
474 if(filter(entry) == BIT(ks[c], isodd + 2))\r
475 continue;\r
476\r
477 candidates[i--] = candidates[size--];\r
478 }\r
479\r
480 candidates[size + 1] = -1;\r
481\r
482 return candidates;\r
483}\r
484\r
485/** brute_top\r
486 * helper function which eliminates possible secret states using parity bits\r
487 */\r
488static struct Crypto1State*\r
489brute_top(uint32_t prefix, uint32_t rresp, unsigned char parities[8][8],\r
b19bd5d6 490 uint32_t odd, uint32_t even, struct Crypto1State* sl, uint8_t no_chk)\r
f89c7050
M
491{\r
492 struct Crypto1State s;\r
493 uint32_t ks1, nr, ks2, rr, ks3, good, c;\r
494\r
495 for(c = 0; c < 8; ++c) {\r
496 s.odd = odd ^ fastfwd[1][c];\r
497 s.even = even ^ fastfwd[0][c];\r
9cefee6f 498\r
f89c7050
M
499 lfsr_rollback_bit(&s, 0, 0);\r
500 lfsr_rollback_bit(&s, 0, 0);\r
501 lfsr_rollback_bit(&s, 0, 0);\r
9cefee6f 502\r
f89c7050
M
503 lfsr_rollback_word(&s, 0, 0);\r
504 lfsr_rollback_word(&s, prefix | c << 5, 1);\r
9cefee6f 505\r
f89c7050
M
506 sl->odd = s.odd;\r
507 sl->even = s.even;\r
9cefee6f 508\r
b19bd5d6 509 if (no_chk)\r
510 break;\r
9cefee6f 511\r
f89c7050
M
512 ks1 = crypto1_word(&s, prefix | c << 5, 1);\r
513 ks2 = crypto1_word(&s,0,0);\r
514 ks3 = crypto1_word(&s, 0,0);\r
515 nr = ks1 ^ (prefix | c << 5);\r
516 rr = ks2 ^ rresp;\r
517\r
518 good = 1;\r
519 good &= parity(nr & 0x000000ff) ^ parities[c][3] ^ BIT(ks2, 24);\r
520 good &= parity(rr & 0xff000000) ^ parities[c][4] ^ BIT(ks2, 16);\r
521 good &= parity(rr & 0x00ff0000) ^ parities[c][5] ^ BIT(ks2, 8);\r
522 good &= parity(rr & 0x0000ff00) ^ parities[c][6] ^ BIT(ks2, 0);\r
523 good &= parity(rr & 0x000000ff) ^ parities[c][7] ^ BIT(ks3, 24);\r
524\r
525 if(!good)\r
526 return sl;\r
527 }\r
528\r
529 return ++sl;\r
9cefee6f 530}\r
f89c7050
M
531\r
532\r
533/** lfsr_common_prefix\r
534 * Implentation of the common prefix attack.\r
535 * Requires the 28 bit constant prefix used as reader nonce (pfx)\r
536 * The reader response used (rr)\r
537 * The keystream used to encrypt the observed NACK's (ks)\r
538 * The parity bits (par)\r
539 * It returns a zero terminated list of possible cipher states after the\r
540 * tag nonce was fed in\r
541 */\r
bcf61bd3 542struct Crypto1State* lfsr_common_prefix(uint32_t pfx, uint32_t rr, uint8_t ks[8], uint8_t par[8][8], uint8_t no_par)\r
f89c7050
M
543{\r
544 struct Crypto1State *statelist, *s;\r
545 uint32_t *odd, *even, *o, *e, top;\r
546\r
547 odd = lfsr_prefix_ks(ks, 1);\r
548 even = lfsr_prefix_ks(ks, 0);\r
549\r
9cefee6f 550 statelist = malloc((sizeof *statelist) << 21); //how large should be?\r
f89c7050 551 if(!statelist || !odd || !even)\r
a61b4976 552 {\r
bcf61bd3 553 free(statelist);\r
554 free(odd);\r
555 free(even);\r
556 return 0;\r
a61b4976 557 }\r
f89c7050 558\r
f89c7050 559 s = statelist;\r
b19bd5d6 560 for(o = odd; *o != -1; ++o)\r
561 for(e = even; *e != -1; ++e)\r
f89c7050
M
562 for(top = 0; top < 64; ++top) {\r
563 *o = (*o & 0x1fffff) | (top << 21);\r
564 *e = (*e & 0x1fffff) | (top >> 3) << 21;\r
b19bd5d6 565 s = brute_top(pfx, rr, par, *o, *e, s, no_par);\r
f89c7050
M
566 }\r
567\r
9cefee6f 568 s->odd = s->even = -1;\r
b19bd5d6 569 //printf("state count = %d\n",s-statelist);\r
f89c7050
M
570\r
571 free(odd);\r
572 free(even);\r
573\r
574 return statelist;\r
575}\r
bcf61bd3 576\r
577/*\r
578struct Crypto1State* lfsr_common_prefix(uint32_t pfx, uint32_t rr, uint8_t ks[8], uint8_t par[8][8], uint8_t no_par, uint32_t nt, uint32_t uid)\r
579{\r
580 long long int amount = 0;\r
581 struct Crypto1State *statelist, *s;\r
582 uint32_t *odd, *even, *o, *e, top;\r
583\r
584 odd = lfsr_prefix_ks(ks, 1);\r
585 even = lfsr_prefix_ks(ks, 0);\r
586\r
587 s = statelist = malloc((sizeof *statelist) << 20);\r
588 if(!s || !odd || !even) {\r
589 free(odd);\r
590 free(even);\r
591 free(statelist);\r
592 return 0;\r
593 }\r
594\r
595 char filename[50] = "archivo.txt";\r
596 sprintf(filename, "logs/%x.txt", nt);\r
597 PrintAndLog("Name: %s\n", filename);\r
598 FILE *file = fopen(filename,"w+");\r
599 if ( !file ) {\r
600 s->odd = s->even = 0;\r
601 free(odd);\r
602 free(even);\r
603 PrintAndLog("Failed to create file");\r
604 return 0;\r
605 }\r
606 PrintAndLog("Creating file... ");\r
607 uint32_t xored = uid^nt;\r
608 \r
609 int lastOdd = 0;\r
610 for(o = odd; *o + 1; ++o)\r
611 for(e = even; *e + 1; ++e)\r
612 for(top = 0; top < 64; ++top) {\r
613 *o += 1 << 21;\r
614 *e += (!(top & 7) + 1) << 21;\r
615\r
616 //added by MG\r
617 if(lastOdd != statelist->odd){\r
618 // Here I create a temporal crypto1 state, \r
619 // where I load the odd and even state and work with it,\r
620 // in order not to interfere with regular mechanism, This is what I save to file\r
621 struct Crypto1State *state;\r
622 lastOdd = state->odd = statelist->odd; state->even = statelist->even;\r
623 lfsr_rollback_word(state,xored,0);\r
624 fprintf(file,"%x %x \n",state->odd,state->even);\r
625 amount++;\r
626 }\r
627 //s = check_pfx_parity(pfx, rr, par, *o, *e, s); //This is not useful at all when attacking chineese cards\r
628 s = brute_top(pfx, rr, par, *o, *e, s, no_par); \r
629 }\r
630\r
631 PrintAndLog("File created, amount %u\n",amount);\r
632 fclose(file);\r
633 s->odd = s->even = 0;\r
634 free(odd);\r
635 free(even);\r
636 return statelist;\r
637}\r
638 */\r
Impressum, Datenschutz