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