]> cvs.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
CHG: syntax suger
[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
8130eba4 18 Copyright (C) 2008-2014 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
da198be4 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
417f4ae1 36 uint32_t *it = start + 1, *rit = stop, t;\r
20f9a2a1
M		 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
417f4ae1 46 else\r
47 t = *it, *it = *rit, *rit = t;\r
20f9a2a1
M		 48\r
49 if(*rit >= *start)\r
50 --rit;\r
417f4ae1 51 if(rit != start)\r
52 t = *rit, *rit = *start, *start = t;\r
20f9a2a1
M		 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
8130eba4 88static inline void\r
89extend_table(uint32_t *tbl, uint32_t **end, int bit, int m1, int m2, uint32_t in)\r
20f9a2a1
M		 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
8130eba4 187 // split the keystream into an odd and even part\r
20f9a2a1
M		 188 for(i = 31; i >= 0; i -= 2)\r
189 oks = oks << 1 | BEBIT(ks2, i);\r
190 for(i = 30; i >= 0; i -= 2)\r
191 eks = eks << 1 | BEBIT(ks2, i);\r
192\r
193 odd_head = odd_tail = malloc(sizeof(uint32_t) << 21);\r
194 even_head = even_tail = malloc(sizeof(uint32_t) << 21);\r
195 statelist = malloc(sizeof(struct Crypto1State) << 18);\r
196 if(!odd_tail-- || !even_tail-- || !statelist) {\r
197 free(statelist);\r
198 statelist = 0;\r
199 goto out;\r
200 }\r
201\r
202 statelist->odd = statelist->even = 0;\r
203\r
8130eba4 204 // initialize statelists: add all possible states which would result into the rightmost 2 bits of the keystream\r
20f9a2a1
M		 205 for(i = 1 << 20; i >= 0; --i) {\r
206 if(filter(i) == (oks & 1))\r
207 *++odd_tail = i;\r
208 if(filter(i) == (eks & 1))\r
209 *++even_tail = i;\r
210 }\r
211\r
8130eba4 212 // extend the statelists. Look at the next 8 Bits of the keystream (4 Bit each odd and even):\r
20f9a2a1
M		 213 for(i = 0; i < 4; i++) {\r
214 extend_table_simple(odd_head, &odd_tail, (oks >>= 1) & 1);\r
215 extend_table_simple(even_head, &even_tail, (eks >>= 1) & 1);\r
216 }\r
217\r
8130eba4 218 // the statelists now contain all states which could have generated the last 10 Bits of the keystream.\r
219 // 22 bits to go to recover 32 bits in total. From now on, we need to take the "in"\r
220 // parameter into account.\r
20f9a2a1
M		 221 in = (in >> 16 & 0xff) | (in << 16) | (in & 0xff00);\r
222 recover(odd_head, odd_tail, oks,\r
223 even_head, even_tail, eks, 11, statelist, in << 1);\r
224\r
225out:\r
226 free(odd_head);\r
227 free(even_head);\r
228 return statelist;\r
229}\r
230\r
231static const uint32_t S1[] = { 0x62141, 0x310A0, 0x18850, 0x0C428, 0x06214,\r
232 0x0310A, 0x85E30, 0xC69AD, 0x634D6, 0xB5CDE, 0xDE8DA, 0x6F46D, 0xB3C83,\r
233 0x59E41, 0xA8995, 0xD027F, 0x6813F, 0x3409F, 0x9E6FA};\r
234static const uint32_t S2[] = { 0x3A557B00, 0x5D2ABD80, 0x2E955EC0, 0x174AAF60,\r
235 0x0BA557B0, 0x05D2ABD8, 0x0449DE68, 0x048464B0, 0x42423258, 0x278192A8,\r
236 0x156042D0, 0x0AB02168, 0x43F89B30, 0x61FC4D98, 0x765EAD48, 0x7D8FDD20,\r
237 0x7EC7EE90, 0x7F63F748, 0x79117020};\r
238static const uint32_t T1[] = {\r
239 0x4F37D, 0x279BE, 0x97A6A, 0x4BD35, 0x25E9A, 0x12F4D, 0x097A6, 0x80D66,\r
240 0xC4006, 0x62003, 0xB56B4, 0x5AB5A, 0xA9318, 0xD0F39, 0x6879C, 0xB057B,\r
241 0x582BD, 0x2C15E, 0x160AF, 0x8F6E2, 0xC3DC4, 0xE5857, 0x72C2B, 0x39615,\r
242 0x98DBF, 0xC806A, 0xE0680, 0x70340, 0x381A0, 0x98665, 0x4C332, 0xA272C};\r
243static const uint32_t T2[] = { 0x3C88B810, 0x5E445C08, 0x2982A580, 0x14C152C0,\r
244 0x4A60A960, 0x253054B0, 0x52982A58, 0x2FEC9EA8, 0x1156C4D0, 0x08AB6268,\r
245 0x42F53AB0, 0x217A9D58, 0x161DC528, 0x0DAE6910, 0x46D73488, 0x25CB11C0,\r
246 0x52E588E0, 0x6972C470, 0x34B96238, 0x5CFC3A98, 0x28DE96C8, 0x12CFC0E0,\r
247 0x4967E070, 0x64B3F038, 0x74F97398, 0x7CDC3248, 0x38CE92A0, 0x1C674950,\r
248 0x0E33A4A8, 0x01B959D0, 0x40DCACE8, 0x26CEDDF0};\r
249static const uint32_t C1[] = { 0x846B5, 0x4235A, 0x211AD};\r
250static const uint32_t C2[] = { 0x1A822E0, 0x21A822E0, 0x21A822E0};\r
251/** Reverse 64 bits of keystream into possible cipher states\r
252 * Variation mentioned in the paper. Somewhat optimized version\r
253 */\r
254struct Crypto1State* lfsr_recovery64(uint32_t ks2, uint32_t ks3)\r
255{\r
256 struct Crypto1State *statelist, *sl;\r
257 uint8_t oks[32], eks[32], hi[32];\r
258 uint32_t low = 0, win = 0;\r
259 uint32_t *tail, table[1 << 16];\r
260 int i, j;\r
261\r
262 sl = statelist = malloc(sizeof(struct Crypto1State) << 4);\r
263 if(!sl)\r
264 return 0;\r
265 sl->odd = sl->even = 0;\r
266\r
267 for(i = 30; i >= 0; i -= 2) {\r
268 oks[i >> 1] = BEBIT(ks2, i);\r
269 oks[16 + (i >> 1)] = BEBIT(ks3, i);\r
270 }\r
271 for(i = 31; i >= 0; i -= 2) {\r
272 eks[i >> 1] = BEBIT(ks2, i);\r
273 eks[16 + (i >> 1)] = BEBIT(ks3, i);\r
274 }\r
275\r
276 for(i = 0xfffff; i >= 0; --i) {\r
277 if (filter(i) != oks[0])\r
278 continue;\r
279\r
280 *(tail = table) = i;\r
281 for(j = 1; tail >= table && j < 29; ++j)\r
282 extend_table_simple(table, &tail, oks[j]);\r
283\r
284 if(tail < table)\r
285 continue;\r
286\r
287 for(j = 0; j < 19; ++j)\r
288 low = low << 1 | parity(i & S1[j]);\r
289 for(j = 0; j < 32; ++j)\r
290 hi[j] = parity(i & T1[j]);\r
291\r
292 for(; tail >= table; --tail) {\r
293 for(j = 0; j < 3; ++j) {\r
294 *tail = *tail << 1;\r
295 *tail |= parity((i & C1[j]) ^ (*tail & C2[j]));\r
296 if(filter(*tail) != oks[29 + j])\r
297 goto continue2;\r
298 }\r
299\r
300 for(j = 0; j < 19; ++j)\r
301 win = win << 1 | parity(*tail & S2[j]);\r
302\r
303 win ^= low;\r
304 for(j = 0; j < 32; ++j) {\r
305 win = win << 1 ^ hi[j] ^ parity(*tail & T2[j]);\r
306 if(filter(win) != eks[j])\r
307 goto continue2;\r
308 }\r
309\r
310 *tail = *tail << 1 | parity(LF_POLY_EVEN & *tail);\r
311 sl->odd = *tail ^ parity(LF_POLY_ODD & win);\r
312 sl->even = win;\r
313 ++sl;\r
314 sl->odd = sl->even = 0;\r
315 continue2:;\r
316 }\r
317 }\r
318 return statelist;\r
319}\r
320\r
321/** lfsr_rollback_bit\r
322 * Rollback the shift register in order to get previous states\r
323 */\r
324uint8_t lfsr_rollback_bit(struct Crypto1State *s, uint32_t in, int fb)\r
325{\r
326 int out;\r
327 uint8_t ret;\r
417f4ae1 328 uint32_t t;\r
20f9a2a1
M		 329\r
330 s->odd &= 0xffffff;\r
417f4ae1 331 t = s->odd, s->odd = s->even, s->even = t;\r
20f9a2a1
M		 332\r
333 out = s->even & 1;\r
334 out ^= LF_POLY_EVEN & (s->even >>= 1);\r
335 out ^= LF_POLY_ODD & s->odd;\r
336 out ^= !!in;\r
337 out ^= (ret = filter(s->odd)) & !!fb;\r
338\r
339 s->even |= parity(out) << 23;\r
340 return ret;\r
341}\r
342/** lfsr_rollback_byte\r
343 * Rollback the shift register in order to get previous states\r
344 */\r
345uint8_t lfsr_rollback_byte(struct Crypto1State *s, uint32_t in, int fb)\r
346{\r
417f4ae1 347 /*\r
348 int i, ret = 0;\r
20f9a2a1
M		 349 for (i = 7; i >= 0; --i)\r
350 ret |= lfsr_rollback_bit(s, BIT(in, i), fb) << i;\r
c2d2a5a6 351*/\r
352// unfold loop 20160112\r
353 uint8_t ret = 0;\r
354 ret |= lfsr_rollback_bit(s, BIT(in, 7), fb) << 7;\r
355 ret |= lfsr_rollback_bit(s, BIT(in, 6), fb) << 6;\r
356 ret |= lfsr_rollback_bit(s, BIT(in, 5), fb) << 5;\r
357 ret |= lfsr_rollback_bit(s, BIT(in, 4), fb) << 4;\r
358 ret |= lfsr_rollback_bit(s, BIT(in, 3), fb) << 3;\r
359 ret |= lfsr_rollback_bit(s, BIT(in, 2), fb) << 2;\r
360 ret |= lfsr_rollback_bit(s, BIT(in, 1), fb) << 1;\r
361 ret |= lfsr_rollback_bit(s, BIT(in, 0), fb) << 0;\r
20f9a2a1
M		 362 return ret;\r
363}\r
364/** lfsr_rollback_word\r
365 * Rollback the shift register in order to get previous states\r
366 */\r
367uint32_t lfsr_rollback_word(struct Crypto1State *s, uint32_t in, int fb)\r
368{\r
417f4ae1 369 /*\r
370 int i;\r
20f9a2a1
M		 371 uint32_t ret = 0;\r
372 for (i = 31; i >= 0; --i)\r
373 ret |= lfsr_rollback_bit(s, BEBIT(in, i), fb) << (i ^ 24);\r
c2d2a5a6 374*/\r
375// unfold loop 20160112\r
376 uint32_t ret = 0;\r
377 ret |= lfsr_rollback_bit(s, BEBIT(in, 31), fb) << (31 ^ 24);\r
378 ret |= lfsr_rollback_bit(s, BEBIT(in, 30), fb) << (30 ^ 24);\r
379 ret |= lfsr_rollback_bit(s, BEBIT(in, 29), fb) << (29 ^ 24);\r
380 ret |= lfsr_rollback_bit(s, BEBIT(in, 28), fb) << (28 ^ 24);\r
381 ret |= lfsr_rollback_bit(s, BEBIT(in, 27), fb) << (27 ^ 24);\r
382 ret |= lfsr_rollback_bit(s, BEBIT(in, 26), fb) << (26 ^ 24);\r
383 ret |= lfsr_rollback_bit(s, BEBIT(in, 25), fb) << (25 ^ 24);\r
384 ret |= lfsr_rollback_bit(s, BEBIT(in, 24), fb) << (24 ^ 24);\r
385\r
386 ret |= lfsr_rollback_bit(s, BEBIT(in, 23), fb) << (23 ^ 24);\r
387 ret |= lfsr_rollback_bit(s, BEBIT(in, 22), fb) << (22 ^ 24);\r
388 ret |= lfsr_rollback_bit(s, BEBIT(in, 21), fb) << (21 ^ 24);\r
389 ret |= lfsr_rollback_bit(s, BEBIT(in, 20), fb) << (20 ^ 24);\r
390 ret |= lfsr_rollback_bit(s, BEBIT(in, 19), fb) << (19 ^ 24);\r
391 ret |= lfsr_rollback_bit(s, BEBIT(in, 18), fb) << (18 ^ 24);\r
392 ret |= lfsr_rollback_bit(s, BEBIT(in, 17), fb) << (17 ^ 24);\r
393 ret |= lfsr_rollback_bit(s, BEBIT(in, 16), fb) << (16 ^ 24);\r
394\r
395 ret |= lfsr_rollback_bit(s, BEBIT(in, 15), fb) << (15 ^ 24);\r
396 ret |= lfsr_rollback_bit(s, BEBIT(in, 14), fb) << (14 ^ 24);\r
397 ret |= lfsr_rollback_bit(s, BEBIT(in, 13), fb) << (13 ^ 24);\r
398 ret |= lfsr_rollback_bit(s, BEBIT(in, 12), fb) << (12 ^ 24);\r
399 ret |= lfsr_rollback_bit(s, BEBIT(in, 11), fb) << (11 ^ 24);\r
400 ret |= lfsr_rollback_bit(s, BEBIT(in, 10), fb) << (10 ^ 24);\r
401 ret |= lfsr_rollback_bit(s, BEBIT(in, 9), fb) << (9 ^ 24);\r
402 ret |= lfsr_rollback_bit(s, BEBIT(in, 8), fb) << (8 ^ 24);\r
403\r
404 ret |= lfsr_rollback_bit(s, BEBIT(in, 7), fb) << (7 ^ 24);\r
405 ret |= lfsr_rollback_bit(s, BEBIT(in, 6), fb) << (6 ^ 24);\r
406 ret |= lfsr_rollback_bit(s, BEBIT(in, 5), fb) << (5 ^ 24);\r
407 ret |= lfsr_rollback_bit(s, BEBIT(in, 4), fb) << (4 ^ 24);\r
408 ret |= lfsr_rollback_bit(s, BEBIT(in, 3), fb) << (3 ^ 24);\r
409 ret |= lfsr_rollback_bit(s, BEBIT(in, 2), fb) << (2 ^ 24);\r
410 ret |= lfsr_rollback_bit(s, BEBIT(in, 1), fb) << (1 ^ 24);\r
411 ret |= lfsr_rollback_bit(s, BEBIT(in, 0), fb) << (0 ^ 24);\r
20f9a2a1
M		 412 return ret;\r
413}\r
414\r
415/** nonce_distance\r
416 * x,y valid tag nonces, then prng_successor(x, nonce_distance(x, y)) = y\r
417 */\r
418static uint16_t *dist = 0;\r
419int nonce_distance(uint32_t from, uint32_t to)\r
420{\r
421 uint16_t x, i;\r
422 if(!dist) {\r
423 dist = malloc(2 << 16);\r
424 if(!dist)\r
425 return -1;\r
426 for (x = i = 1; i; ++i) {\r
427 dist[(x & 0xff) << 8 | x >> 8] = i;\r
428 x = x >> 1 | (x ^ x >> 2 ^ x >> 3 ^ x >> 5) << 15;\r
429 }\r
430 }\r
431 return (65535 + dist[to >> 16] - dist[from >> 16]) % 65535;\r
432}\r
433\r
434\r
435static uint32_t fastfwd[2][8] = {\r
436 { 0, 0x4BC53, 0xECB1, 0x450E2, 0x25E29, 0x6E27A, 0x2B298, 0x60ECB},\r
437 { 0, 0x1D962, 0x4BC53, 0x56531, 0xECB1, 0x135D3, 0x450E2, 0x58980}};\r
417f4ae1 438\r
439\r
20f9a2a1
M		 440/** lfsr_prefix_ks\r
441 *\r
442 * Is an exported helper function from the common prefix attack\r
443 * Described in the "dark side" paper. It returns an -1 terminated array\r
444 * of possible partial(21 bit) secret state.\r
445 * The required keystream(ks) needs to contain the keystream that was used to\r
446 * encrypt the NACK which is observed when varying only the 3 last bits of Nr\r
447 * only correct iff [NR_3] ^ NR_3 does not depend on Nr_3\r
448 */\r
449uint32_t *lfsr_prefix_ks(uint8_t ks[8], int isodd)\r
450{\r
417f4ae1 451 uint32_t *candidates = malloc(4 << 10);\r
8130eba4 452 if(!candidates) return 0;\r
453 \r
417f4ae1 454 uint32_t c, entry;\r
455 int size = 0, i, good;\r
20f9a2a1 456\r
20f9a2a1
M		 457 for(i = 0; i < 1 << 21; ++i) {\r
458 for(c = 0, good = 1; good && c < 8; ++c) {\r
459 entry = i ^ fastfwd[isodd][c];\r
460 good &= (BIT(ks[c], isodd) == filter(entry >> 1));\r
461 good &= (BIT(ks[c], isodd + 2) == filter(entry));\r
462 }\r
463 if(good)\r
464 candidates[size++] = i;\r
465 }\r
466\r
467 candidates[size] = -1;\r
468\r
469 return candidates;\r
470}\r
471\r
472/** check_pfx_parity\r
473 * helper function which eliminates possible secret states using parity bits\r
474 */\r
8130eba4 475static struct Crypto1State* check_pfx_parity(uint32_t prefix, uint32_t rresp, uint8_t parities[8][8], uint32_t odd, uint32_t even, struct Crypto1State* sl)\r
20f9a2a1
M		 476{\r
477 uint32_t ks1, nr, ks2, rr, ks3, c, good = 1;\r
478\r
479 for(c = 0; good && c < 8; ++c) {\r
480 sl->odd = odd ^ fastfwd[1][c];\r
481 sl->even = even ^ fastfwd[0][c];\r
482\r
483 lfsr_rollback_bit(sl, 0, 0);\r
484 lfsr_rollback_bit(sl, 0, 0);\r
485\r
486 ks3 = lfsr_rollback_bit(sl, 0, 0);\r
487 ks2 = lfsr_rollback_word(sl, 0, 0);\r
488 ks1 = lfsr_rollback_word(sl, prefix | c << 5, 1);\r
489\r
490 nr = ks1 ^ (prefix | c << 5);\r
491 rr = ks2 ^ rresp;\r
492\r
493 good &= parity(nr & 0x000000ff) ^ parities[c][3] ^ BIT(ks2, 24);\r
494 good &= parity(rr & 0xff000000) ^ parities[c][4] ^ BIT(ks2, 16);\r
495 good &= parity(rr & 0x00ff0000) ^ parities[c][5] ^ BIT(ks2, 8);\r
496 good &= parity(rr & 0x0000ff00) ^ parities[c][6] ^ BIT(ks2, 0);\r
497 good &= parity(rr & 0x000000ff) ^ parities[c][7] ^ ks3;\r
498 }\r
499\r
500 return sl + good;\r
9cefee6f 501}\r
20f9a2a1 502\r
20f9a2a1
M		 503/** lfsr_common_prefix\r
504 * Implentation of the common prefix attack.\r
417f4ae1 505 * Requires the 28 bit constant prefix used as reader nonce (pfx)\r
506 * The reader response used (rr)\r
507 * The keystream used to encrypt the observed NACK's (ks)\r
508 * The parity bits (par)\r
509 * It returns a zero terminated list of possible cipher states after the\r
510 * tag nonce was fed in\r
20f9a2a1 511 */\r
8130eba4 512struct Crypto1State* lfsr_common_prefix(uint32_t pfx, uint32_t rr, uint8_t ks[8], uint8_t par[8][8])\r
20f9a2a1
M		 513{\r
514 struct Crypto1State *statelist, *s;\r
515 uint32_t *odd, *even, *o, *e, top;\r
516\r
517 odd = lfsr_prefix_ks(ks, 1);\r
518 even = lfsr_prefix_ks(ks, 0);\r
f6c18637 519 \r
8130eba4 520 s = statelist = malloc((sizeof *statelist) << 21);\r
20f9a2a1
M		 521 if(!s || !odd || !even) {\r
522 free(statelist);\r
5eceba29 523 statelist = 0;\r
524 goto out;\r
20f9a2a1
M		 525 }\r
526\r
527 for(o = odd; *o + 1; ++o)\r
528 for(e = even; *e + 1; ++e)\r
529 for(top = 0; top < 64; ++top) {\r
530 *o += 1 << 21;\r
531 *e += (!(top & 7) + 1) << 21;\r
532 s = check_pfx_parity(pfx, rr, par, *o, *e, s);\r
533 }\r
534\r
535 s->odd = s->even = 0;\r
5eceba29 536out:\r
20f9a2a1
M		 537 free(odd);\r
538 free(even);\r
539 return statelist;\r
8130eba4 540}
Proxmark3 GIT tracking
Impressum, Datenschutz