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