]> git.zerfleddert.de Git - proxmark3-svn/blame - tools/nonce2key/crapto1.c
projects / proxmark3-svn / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
Merge pull request #230 from zhovner/master
[proxmark3-svn] / tools / nonce2key / crapto1.c
CommitLineData
93f57590 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
24static uint8_t filterlut[1 << 20];\r
25static void __attribute__((constructor)) fill_lut()\r
26{\r
27 uint32_t i;\r
28 for(i = 0; i < 1 << 20; ++i)\r
29 filterlut[i] = filter(i);\r
30}\r
31#define filter(x) (filterlut[(x) & 0xfffff])\r
32#endif\r
33\r
34static void quicksort(uint32_t* const start, uint32_t* const stop)\r
35{\r
36 uint32_t *it = start + 1, *rit = stop;\r
37\r
38 if(it > rit)\r
39 return;\r
40\r
41 while(it < rit)\r
42 if(*it <= *start)\r
43 ++it;\r
44 else if(*rit > *start)\r
45 --rit;\r
46 else\r
47 *it ^= (*it ^= *rit, *rit ^= *it);\r
48\r
49 if(*rit >= *start)\r
50 --rit;\r
51 if(rit != start)\r
52 *rit ^= (*rit ^= *start, *start ^= *rit);\r
53\r
54 quicksort(start, rit - 1);\r
55 quicksort(rit + 1, stop);\r
56}\r
57/** binsearch\r
58 * Binary search for the first occurence of *stop's MSB in sorted [start,stop]\r
59 */\r
60static inline uint32_t*\r
61binsearch(uint32_t *start, uint32_t *stop)\r
62{\r
63 uint32_t mid, val = *stop & 0xff000000;\r
64 while(start != stop)\r
65 if(start[mid = (stop - start) >> 1] > val)\r
66 stop = &start[mid];\r
67 else\r
68 start += mid + 1;\r
69\r
70 return start;\r
71}\r
72\r
73/** update_contribution\r
74 * helper, calculates the partial linear feedback contributions and puts in MSB\r
75 */\r
76static inline void\r
77update_contribution(uint32_t *item, const uint32_t mask1, const uint32_t mask2)\r
78{\r
79 uint32_t p = *item >> 25;\r
80\r
81 p = p << 1 | parity(*item & mask1);\r
82 p = p << 1 | parity(*item & mask2);\r
83 *item = p << 24 | (*item & 0xffffff);\r
84}\r
85\r
86/** extend_table\r
87 * using a bit of the keystream extend the table of possible lfsr states\r
88 */\r
89static inline void\r
90extend_table(uint32_t *tbl, uint32_t **end, int bit, int m1, int m2, uint32_t in)\r
91{\r
92 in <<= 24;\r
93 for(*tbl <<= 1; tbl <= *end; *++tbl <<= 1)\r
94 if(filter(*tbl) ^ filter(*tbl | 1)) {\r
95 *tbl |= filter(*tbl) ^ bit;\r
96 update_contribution(tbl, m1, m2);\r
97 *tbl ^= in;\r
98 } else if(filter(*tbl) == bit) {\r
99 *++*end = tbl[1];\r
100 tbl[1] = tbl[0] | 1;\r
101 update_contribution(tbl, m1, m2);\r
102 *tbl++ ^= in;\r
103 update_contribution(tbl, m1, m2);\r
104 *tbl ^= in;\r
105 } else\r
106 *tbl-- = *(*end)--;\r
107}\r
108/** extend_table_simple\r
109 * using a bit of the keystream extend the table of possible lfsr states\r
110 */\r
111static inline void\r
112extend_table_simple(uint32_t *tbl, uint32_t **end, int bit)\r
113{\r
114 for(*tbl <<= 1; tbl <= *end; *++tbl <<= 1)\r
115 if(filter(*tbl) ^ filter(*tbl | 1)) {\r
116 *tbl |= filter(*tbl) ^ bit;\r
117 } else if(filter(*tbl) == bit) {\r
118 *++*end = *++tbl;\r
119 *tbl = tbl[-1] | 1;\r
120 } else\r
121 *tbl-- = *(*end)--;\r
122}\r
123/** recover\r
124 * recursively narrow down the search space, 4 bits of keystream at a time\r
125 */\r
126static struct Crypto1State*\r
127recover(uint32_t *o_head, uint32_t *o_tail, uint32_t oks,\r
128 uint32_t *e_head, uint32_t *e_tail, uint32_t eks, int rem,\r
129 struct Crypto1State *sl, uint32_t in)\r
130{\r
131 uint32_t *o, *e, i;\r
132\r
133 if(rem == -1) {\r
134 for(e = e_head; e <= e_tail; ++e) {\r
135 *e = *e << 1 ^ parity(*e & LF_POLY_EVEN) ^ !!(in & 4);\r
136 for(o = o_head; o <= o_tail; ++o, ++sl) {\r
137 sl->even = *o;\r
138 sl->odd = *e ^ parity(*o & LF_POLY_ODD);\r
139 sl[1].odd = sl[1].even = 0;\r
140 }\r
141 }\r
142 return sl;\r
143 }\r
144\r
145 for(i = 0; i < 4 && rem--; i++) {\r
146 extend_table(o_head, &o_tail, (oks >>= 1) & 1,\r
147 LF_POLY_EVEN << 1 | 1, LF_POLY_ODD << 1, 0);\r
148 if(o_head > o_tail)\r
149 return sl;\r
150\r
151 extend_table(e_head, &e_tail, (eks >>= 1) & 1,\r
152 LF_POLY_ODD, LF_POLY_EVEN << 1 | 1, (in >>= 2) & 3);\r
153 if(e_head > e_tail)\r
154 return sl;\r
155 }\r
156\r
157 quicksort(o_head, o_tail);\r
158 quicksort(e_head, e_tail);\r
159\r
160 while(o_tail >= o_head && e_tail >= e_head)\r
161 if(((*o_tail ^ *e_tail) >> 24) == 0) {\r
162 o_tail = binsearch(o_head, o = o_tail);\r
163 e_tail = binsearch(e_head, e = e_tail);\r
164 sl = recover(o_tail--, o, oks,\r
165 e_tail--, e, eks, rem, sl, in);\r
166 }\r
167 else if(*o_tail > *e_tail)\r
168 o_tail = binsearch(o_head, o_tail) - 1;\r
169 else\r
170 e_tail = binsearch(e_head, e_tail) - 1;\r
171\r
172 return sl;\r
173}\r
174/** lfsr_recovery\r
175 * recover the state of the lfsr given 32 bits of the keystream\r
176 * additionally you can use the in parameter to specify the value\r
177 * that was fed into the lfsr at the time the keystream was generated\r
178 */\r
179struct Crypto1State* lfsr_recovery32(uint32_t ks2, uint32_t in)\r
180{\r
181 struct Crypto1State *statelist;\r
182 uint32_t *odd_head = 0, *odd_tail = 0, oks = 0;\r
183 uint32_t *even_head = 0, *even_tail = 0, eks = 0;\r
184 int i;\r
185\r
186 for(i = 31; i >= 0; i -= 2)\r
187 oks = oks << 1 | BEBIT(ks2, i);\r
188 for(i = 30; i >= 0; i -= 2)\r
189 eks = eks << 1 | BEBIT(ks2, i);\r
190\r
191 odd_head = odd_tail = malloc(sizeof(uint32_t) << 21);\r
192 even_head = even_tail = malloc(sizeof(uint32_t) << 21);\r
193 statelist = malloc(sizeof(struct Crypto1State) << 18);\r
194 if(!odd_tail-- || !even_tail-- || !statelist)\r
195 goto out;\r
196\r
197 statelist->odd = statelist->even = 0;\r
198\r
199 for(i = 1 << 20; i >= 0; --i) {\r
200 if(filter(i) == (oks & 1))\r
201 *++odd_tail = i;\r
202 if(filter(i) == (eks & 1))\r
203 *++even_tail = i;\r
204 }\r
205\r
206 for(i = 0; i < 4; i++) {\r
207 extend_table_simple(odd_head, &odd_tail, (oks >>= 1) & 1);\r
208 extend_table_simple(even_head, &even_tail, (eks >>= 1) & 1);\r
209 }\r
210\r
211 in = (in >> 16 & 0xff) | (in << 16) | (in & 0xff00);\r
212 recover(odd_head, odd_tail, oks,\r
213 even_head, even_tail, eks, 11, statelist, in << 1);\r
214\r
215out:\r
216 free(odd_head);\r
217 free(even_head);\r
218 return statelist;\r
219}\r
220\r
221static const uint32_t S1[] = { 0x62141, 0x310A0, 0x18850, 0x0C428, 0x06214,\r
222 0x0310A, 0x85E30, 0xC69AD, 0x634D6, 0xB5CDE, 0xDE8DA, 0x6F46D, 0xB3C83,\r
223 0x59E41, 0xA8995, 0xD027F, 0x6813F, 0x3409F, 0x9E6FA};\r
224static const uint32_t S2[] = { 0x3A557B00, 0x5D2ABD80, 0x2E955EC0, 0x174AAF60,\r
225 0x0BA557B0, 0x05D2ABD8, 0x0449DE68, 0x048464B0, 0x42423258, 0x278192A8,\r
226 0x156042D0, 0x0AB02168, 0x43F89B30, 0x61FC4D98, 0x765EAD48, 0x7D8FDD20,\r
227 0x7EC7EE90, 0x7F63F748, 0x79117020};\r
228static const uint32_t T1[] = {\r
229 0x4F37D, 0x279BE, 0x97A6A, 0x4BD35, 0x25E9A, 0x12F4D, 0x097A6, 0x80D66,\r
230 0xC4006, 0x62003, 0xB56B4, 0x5AB5A, 0xA9318, 0xD0F39, 0x6879C, 0xB057B,\r
231 0x582BD, 0x2C15E, 0x160AF, 0x8F6E2, 0xC3DC4, 0xE5857, 0x72C2B, 0x39615,\r
232 0x98DBF, 0xC806A, 0xE0680, 0x70340, 0x381A0, 0x98665, 0x4C332, 0xA272C};\r
233static const uint32_t T2[] = { 0x3C88B810, 0x5E445C08, 0x2982A580, 0x14C152C0,\r
234 0x4A60A960, 0x253054B0, 0x52982A58, 0x2FEC9EA8, 0x1156C4D0, 0x08AB6268,\r
235 0x42F53AB0, 0x217A9D58, 0x161DC528, 0x0DAE6910, 0x46D73488, 0x25CB11C0,\r
236 0x52E588E0, 0x6972C470, 0x34B96238, 0x5CFC3A98, 0x28DE96C8, 0x12CFC0E0,\r
237 0x4967E070, 0x64B3F038, 0x74F97398, 0x7CDC3248, 0x38CE92A0, 0x1C674950,\r
238 0x0E33A4A8, 0x01B959D0, 0x40DCACE8, 0x26CEDDF0};\r
239static const uint32_t C1[] = { 0x846B5, 0x4235A, 0x211AD};\r
240static const uint32_t C2[] = { 0x1A822E0, 0x21A822E0, 0x21A822E0};\r
241/** Reverse 64 bits of keystream into possible cipher states\r
242 * Variation mentioned in the paper. Somewhat optimized version\r
243 */\r
244struct Crypto1State* lfsr_recovery64(uint32_t ks2, uint32_t ks3)\r
245{\r
246 struct Crypto1State *statelist, *sl;\r
247 uint8_t oks[32], eks[32], hi[32];\r
248 uint32_t low = 0, win = 0;\r
249 uint32_t *tail, table[1 << 16];\r
250 int i, j;\r
251\r
252 sl = statelist = malloc(sizeof(struct Crypto1State) << 4);\r
253 if(!sl)\r
254 return 0;\r
255 sl->odd = sl->even = 0;\r
256\r
257 for(i = 30; i >= 0; i -= 2) {\r
258 oks[i >> 1] = BIT(ks2, i ^ 24);\r
259 oks[16 + (i >> 1)] = BIT(ks3, i ^ 24);\r
260 }\r
261 for(i = 31; i >= 0; i -= 2) {\r
262 eks[i >> 1] = BIT(ks2, i ^ 24);\r
263 eks[16 + (i >> 1)] = BIT(ks3, i ^ 24);\r
264 }\r
265\r
266 for(i = 0xfffff; i >= 0; --i) {\r
267 if (filter(i) != oks[0])\r
268 continue;\r
269\r
270 *(tail = table) = i;\r
271 for(j = 1; tail >= table && j < 29; ++j)\r
272 extend_table_simple(table, &tail, oks[j]);\r
273\r
274 if(tail < table)\r
275 continue;\r
276\r
277 for(j = 0; j < 19; ++j)\r
278 low = low << 1 | parity(i & S1[j]);\r
279 for(j = 0; j < 32; ++j)\r
280 hi[j] = parity(i & T1[j]);\r
281\r
282 for(; tail >= table; --tail) {\r
283 for(j = 0; j < 3; ++j) {\r
284 *tail = *tail << 1;\r
285 *tail |= parity((i & C1[j]) ^ (*tail & C2[j]));\r
286 if(filter(*tail) != oks[29 + j])\r
287 goto continue2;\r
288 }\r
289\r
290 for(j = 0; j < 19; ++j)\r
291 win = win << 1 | parity(*tail & S2[j]);\r
292\r
293 win ^= low;\r
294 for(j = 0; j < 32; ++j) {\r
295 win = win << 1 ^ hi[j] ^ parity(*tail & T2[j]);\r
296 if(filter(win) != eks[j])\r
297 goto continue2;\r
298 }\r
299\r
300 *tail = *tail << 1 | parity(LF_POLY_EVEN & *tail);\r
301 sl->odd = *tail ^ parity(LF_POLY_ODD & win);\r
302 sl->even = win;\r
303 ++sl;\r
304 sl->odd = sl->even = 0;\r
305 continue2:;\r
306 }\r
307 }\r
308 return statelist;\r
309}\r
310\r
311/** lfsr_rollback_bit\r
312 * Rollback the shift register in order to get previous states\r
313 */\r
314void lfsr_rollback_bit(struct Crypto1State *s, uint32_t in, int fb)\r
315{\r
316 int out;\r
317\r
318 s->odd &= 0xffffff;\r
319 s->odd ^= (s->odd ^= s->even, s->even ^= s->odd);\r
320\r
321 out = s->even & 1;\r
322 out ^= LF_POLY_EVEN & (s->even >>= 1);\r
323 out ^= LF_POLY_ODD & s->odd;\r
324 out ^= !!in;\r
325 out ^= filter(s->odd) & !!fb;\r
326\r
327 s->even |= parity(out) << 23;\r
328}\r
329/** lfsr_rollback_byte\r
330 * Rollback the shift register in order to get previous states\r
331 */\r
332void lfsr_rollback_byte(struct Crypto1State *s, uint32_t in, int fb)\r
333{\r
334 int i;\r
335 for (i = 7; i >= 0; --i)\r
336 lfsr_rollback_bit(s, BEBIT(in, i), fb);\r
337}\r
338/** lfsr_rollback_word\r
339 * Rollback the shift register in order to get previous states\r
340 */\r
341void lfsr_rollback_word(struct Crypto1State *s, uint32_t in, int fb)\r
342{\r
343 int i;\r
344 for (i = 31; i >= 0; --i)\r
345 lfsr_rollback_bit(s, BEBIT(in, i), fb);\r
346}\r
347\r
348/** nonce_distance\r
349 * x,y valid tag nonces, then prng_successor(x, nonce_distance(x, y)) = y\r
350 */\r
351static uint16_t *dist = 0;\r
352int nonce_distance(uint32_t from, uint32_t to)\r
353{\r
354 uint16_t x, i;\r
355 if(!dist) {\r
356 dist = malloc(2 << 16);\r
357 if(!dist)\r
358 return -1;\r
359 for (x = i = 1; i; ++i) {\r
360 dist[(x & 0xff) << 8 | x >> 8] = i;\r
361 x = x >> 1 | (x ^ x >> 2 ^ x >> 3 ^ x >> 5) << 15;\r
362 }\r
363 }\r
364 return (65535 + dist[to >> 16] - dist[from >> 16]) % 65535;\r
365}\r
366\r
367\r
368static uint32_t fastfwd[2][8] = {\r
369 { 0, 0x4BC53, 0xECB1, 0x450E2, 0x25E29, 0x6E27A, 0x2B298, 0x60ECB},\r
370 { 0, 0x1D962, 0x4BC53, 0x56531, 0xECB1, 0x135D3, 0x450E2, 0x58980}};\r
371\r
372\r
373/** lfsr_prefix_ks\r
374 *\r
375 * Is an exported helper function from the common prefix attack\r
376 * Described in the "dark side" paper. It returns an -1 terminated array\r
377 * of possible partial(21 bit) secret state.\r
378 * The required keystream(ks) needs to contain the keystream that was used to\r
379 * encrypt the NACK which is observed when varying only the 4 last bits of Nr\r
380 * only correct iff [NR_3] ^ NR_3 does not depend on Nr_3\r
381 */\r
382uint32_t *lfsr_prefix_ks(uint8_t ks[8], int isodd)\r
383{\r
384 uint32_t *candidates = malloc(4 << 21);\r
385 uint32_t c, entry;\r
386 int size, i;\r
387\r
388 if(!candidates)\r
389 return 0;\r
390\r
391 size = (1 << 21) - 1;\r
392 for(i = 0; i <= size; ++i)\r
393 candidates[i] = i;\r
394\r
395 for(c = 0; c < 8; ++c)\r
396 for(i = 0;i <= size; ++i) {\r
397 entry = candidates[i] ^ fastfwd[isodd][c];\r
398\r
399 if(filter(entry >> 1) == BIT(ks[c], isodd))\r
400 if(filter(entry) == BIT(ks[c], isodd + 2))\r
401 continue;\r
402\r
403 candidates[i--] = candidates[size--];\r
404 }\r
405\r
406 candidates[size + 1] = -1;\r
407\r
408 return candidates;\r
409}\r
410\r
411/** brute_top\r
412 * helper function which eliminates possible secret states using parity bits\r
413 */\r
414static struct Crypto1State*\r
415brute_top(uint32_t prefix, uint32_t rresp, unsigned char parities[8][8],\r
416 uint32_t odd, uint32_t even, struct Crypto1State* sl)\r
417{\r
418 struct Crypto1State s;\r
419 uint32_t ks1, nr, ks2, rr, ks3, good, c;\r
420\r
421 for(c = 0; c < 8; ++c) {\r
422 s.odd = odd ^ fastfwd[1][c];\r
423 s.even = even ^ fastfwd[0][c];\r
424 \r
425 lfsr_rollback_bit(&s, 0, 0);\r
426 lfsr_rollback_bit(&s, 0, 0);\r
427 lfsr_rollback_bit(&s, 0, 0);\r
428 \r
429 lfsr_rollback_word(&s, 0, 0);\r
430 lfsr_rollback_word(&s, prefix | c << 5, 1);\r
431 \r
432 sl->odd = s.odd;\r
433 sl->even = s.even;\r
434 \r
435 ks1 = crypto1_word(&s, prefix | c << 5, 1);\r
436 ks2 = crypto1_word(&s,0,0);\r
437 ks3 = crypto1_word(&s, 0,0);\r
438 nr = ks1 ^ (prefix | c << 5);\r
439 rr = ks2 ^ rresp;\r
440\r
441 good = 1;\r
442 good &= parity(nr & 0x000000ff) ^ parities[c][3] ^ BIT(ks2, 24);\r
443 good &= parity(rr & 0xff000000) ^ parities[c][4] ^ BIT(ks2, 16);\r
444 good &= parity(rr & 0x00ff0000) ^ parities[c][5] ^ BIT(ks2, 8);\r
445 good &= parity(rr & 0x0000ff00) ^ parities[c][6] ^ BIT(ks2, 0);\r
446 good &= parity(rr & 0x000000ff) ^ parities[c][7] ^ BIT(ks3, 24);\r
447\r
448 if(!good)\r
449 return sl;\r
450 }\r
451\r
452 return ++sl;\r
453} \r
454\r
455\r
456/** lfsr_common_prefix\r
457 * Implentation of the common prefix attack.\r
458 * Requires the 28 bit constant prefix used as reader nonce (pfx)\r
459 * The reader response used (rr)\r
460 * The keystream used to encrypt the observed NACK's (ks)\r
461 * The parity bits (par)\r
462 * It returns a zero terminated list of possible cipher states after the\r
463 * tag nonce was fed in\r
464 */\r
465struct Crypto1State*\r
466lfsr_common_prefix(uint32_t pfx, uint32_t rr, uint8_t ks[8], uint8_t par[8][8])\r
467{\r
468 struct Crypto1State *statelist, *s;\r
469 uint32_t *odd, *even, *o, *e, top;\r
470\r
471 odd = lfsr_prefix_ks(ks, 1);\r
472 even = lfsr_prefix_ks(ks, 0);\r
473\r
474 statelist = malloc((sizeof *statelist) << 20);\r
475 if(!statelist || !odd || !even)\r
476 return 0;\r
477\r
478\r
479 s = statelist;\r
480 for(o = odd; *o != 0xffffffff; ++o)\r
481 for(e = even; *e != 0xffffffff; ++e)\r
482 for(top = 0; top < 64; ++top) {\r
483 *o = (*o & 0x1fffff) | (top << 21);\r
484 *e = (*e & 0x1fffff) | (top >> 3) << 21;\r
485 s = brute_top(pfx, rr, par, *o, *e, s);\r
486 }\r
487\r
488 s->odd = s->even = 0;\r
489\r
490 free(odd);\r
491 free(even);\r
492\r
493 return statelist;\r
494}\r
Proxmark3 GIT tracking
Impressum, Datenschutz