]> 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' into topaz
[proxmark3-svn] / armsrc / crapto1.c
CommitLineData
20f9a2a1
M		 1/* crapto1.c\r
2\r
9cefee6f 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
20f9a2a1
M		 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
9cefee6f 27 uint32_t i;\r
28 for(i = 0; i < 1 << 20; ++i)\r
29 filterlut[i] = filter(i);\r
20f9a2a1
M		 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
9cefee6f 37 uint32_t tmp;\r
20f9a2a1
M		 38\r
39 if(it > rit)\r
40 return;\r
41\r
42 while(it < rit)\r
43 if(*it <= *start)\r
44 ++it;\r
45 else if(*rit > *start)\r
46 --rit;\r
9cefee6f 47 else {\r
48 tmp = *it;\r
49 *it = *rit;\r
50 *rit = tmp;\r
51 }\r
20f9a2a1
M		 52\r
53 if(*rit >= *start)\r
54 --rit;\r
9cefee6f 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
9cefee6f 155 LF_POLY_ODD << 1, 0);\r
20f9a2a1
M		 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
9cefee6f 160 LF_POLY_EVEN << 1 | 1, in & 3);\r
20f9a2a1
M		 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
9cefee6f 173 e_tail--, e, eks, rem, sl, in);\r
20f9a2a1
M		 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
9cefee6f 329 uint32_t tmp;\r
20f9a2a1
M		 330\r
331 s->odd &= 0xffffff;\r
9cefee6f 332 tmp = s->odd;\r
333 s->odd = s->even;\r
334 s->even = tmp;\r
20f9a2a1
M		 335\r
336 out = s->even & 1;\r
337 out ^= LF_POLY_EVEN & (s->even >>= 1);\r
338 out ^= LF_POLY_ODD & s->odd;\r
339 out ^= !!in;\r
340 out ^= (ret = filter(s->odd)) & !!fb;\r
341\r
342 s->even |= parity(out) << 23;\r
343 return ret;\r
344}\r
345/** lfsr_rollback_byte\r
346 * Rollback the shift register in order to get previous states\r
347 */\r
348uint8_t lfsr_rollback_byte(struct Crypto1State *s, uint32_t in, int fb)\r
349{\r
350 int i, ret = 0;\r
351 for (i = 7; i >= 0; --i)\r
352 ret |= lfsr_rollback_bit(s, BIT(in, i), fb) << i;\r
353 return ret;\r
354}\r
355/** lfsr_rollback_word\r
356 * Rollback the shift register in order to get previous states\r
357 */\r
358uint32_t lfsr_rollback_word(struct Crypto1State *s, uint32_t in, int fb)\r
359{\r
360 int i;\r
361 uint32_t ret = 0;\r
362 for (i = 31; i >= 0; --i)\r
363 ret |= lfsr_rollback_bit(s, BEBIT(in, i), fb) << (i ^ 24);\r
364 return ret;\r
365}\r
366\r
367/** nonce_distance\r
368 * x,y valid tag nonces, then prng_successor(x, nonce_distance(x, y)) = y\r
369 */\r
370static uint16_t *dist = 0;\r
371int nonce_distance(uint32_t from, uint32_t to)\r
372{\r
373 uint16_t x, i;\r
374 if(!dist) {\r
375 dist = malloc(2 << 16);\r
376 if(!dist)\r
377 return -1;\r
378 for (x = i = 1; i; ++i) {\r
379 dist[(x & 0xff) << 8 | x >> 8] = i;\r
380 x = x >> 1 | (x ^ x >> 2 ^ x >> 3 ^ x >> 5) << 15;\r
381 }\r
382 }\r
383 return (65535 + dist[to >> 16] - dist[from >> 16]) % 65535;\r
384}\r
385\r
386\r
387static uint32_t fastfwd[2][8] = {\r
388 { 0, 0x4BC53, 0xECB1, 0x450E2, 0x25E29, 0x6E27A, 0x2B298, 0x60ECB},\r
389 { 0, 0x1D962, 0x4BC53, 0x56531, 0xECB1, 0x135D3, 0x450E2, 0x58980}};\r
390/** lfsr_prefix_ks\r
391 *\r
392 * Is an exported helper function from the common prefix attack\r
393 * Described in the "dark side" paper. It returns an -1 terminated array\r
394 * of possible partial(21 bit) secret state.\r
395 * The required keystream(ks) needs to contain the keystream that was used to\r
396 * encrypt the NACK which is observed when varying only the 3 last bits of Nr\r
397 * only correct iff [NR_3] ^ NR_3 does not depend on Nr_3\r
398 */\r
399uint32_t *lfsr_prefix_ks(uint8_t ks[8], int isodd)\r
400{\r
401 uint32_t c, entry, *candidates = malloc(4 << 10);\r
402 int i, size = 0, good;\r
403\r
404 if(!candidates)\r
405 return 0;\r
406\r
407 for(i = 0; i < 1 << 21; ++i) {\r
408 for(c = 0, good = 1; good && c < 8; ++c) {\r
409 entry = i ^ fastfwd[isodd][c];\r
410 good &= (BIT(ks[c], isodd) == filter(entry >> 1));\r
411 good &= (BIT(ks[c], isodd + 2) == filter(entry));\r
412 }\r
413 if(good)\r
414 candidates[size++] = i;\r
415 }\r
416\r
417 candidates[size] = -1;\r
418\r
419 return candidates;\r
420}\r
421\r
422/** check_pfx_parity\r
423 * helper function which eliminates possible secret states using parity bits\r
424 */\r
425static struct Crypto1State*\r
426check_pfx_parity(uint32_t prefix, uint32_t rresp, uint8_t parities[8][8],\r
9cefee6f 427 uint32_t odd, uint32_t even, struct Crypto1State* sl)\r
20f9a2a1
M		 428{\r
429 uint32_t ks1, nr, ks2, rr, ks3, c, good = 1;\r
430\r
431 for(c = 0; good && c < 8; ++c) {\r
432 sl->odd = odd ^ fastfwd[1][c];\r
433 sl->even = even ^ fastfwd[0][c];\r
434\r
435 lfsr_rollback_bit(sl, 0, 0);\r
436 lfsr_rollback_bit(sl, 0, 0);\r
437\r
438 ks3 = lfsr_rollback_bit(sl, 0, 0);\r
439 ks2 = lfsr_rollback_word(sl, 0, 0);\r
440 ks1 = lfsr_rollback_word(sl, prefix | c << 5, 1);\r
441\r
442 nr = ks1 ^ (prefix | c << 5);\r
443 rr = ks2 ^ rresp;\r
444\r
445 good &= parity(nr & 0x000000ff) ^ parities[c][3] ^ BIT(ks2, 24);\r
446 good &= parity(rr & 0xff000000) ^ parities[c][4] ^ BIT(ks2, 16);\r
447 good &= parity(rr & 0x00ff0000) ^ parities[c][5] ^ BIT(ks2, 8);\r
448 good &= parity(rr & 0x0000ff00) ^ parities[c][6] ^ BIT(ks2, 0);\r
449 good &= parity(rr & 0x000000ff) ^ parities[c][7] ^ ks3;\r
450 }\r
451\r
452 return sl + good;\r
9cefee6f 453}\r
20f9a2a1
M		 454\r
455\r
456/** lfsr_common_prefix\r
457 * Implentation of the common prefix attack.\r
458 */\r
459struct Crypto1State*\r
460lfsr_common_prefix(uint32_t pfx, uint32_t rr, uint8_t ks[8], uint8_t par[8][8])\r
461{\r
462 struct Crypto1State *statelist, *s;\r
463 uint32_t *odd, *even, *o, *e, top;\r
464\r
465 odd = lfsr_prefix_ks(ks, 1);\r
466 even = lfsr_prefix_ks(ks, 0);\r
467\r
468 s = statelist = malloc((sizeof *statelist) << 20);\r
469 if(!s || !odd || !even) {\r
470 free(statelist);\r
471 statelist = 0;\r
9cefee6f 472 goto out;\r
20f9a2a1
M		 473 }\r
474\r
475 for(o = odd; *o + 1; ++o)\r
476 for(e = even; *e + 1; ++e)\r
477 for(top = 0; top < 64; ++top) {\r
478 *o += 1 << 21;\r
479 *e += (!(top & 7) + 1) << 21;\r
480 s = check_pfx_parity(pfx, rr, par, *o, *e, s);\r
481 }\r
482\r
483 s->odd = s->even = 0;\r
484out:\r
485 free(odd);\r
486 free(even);\r
487 return statelist;\r
488}\r
Proxmark3 GIT tracking
Impressum, Datenschutz