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