]> git.zerfleddert.de Git - proxmark3-svn/blame - tools/mfkey/crapto1.c
projects / proxmark3-svn / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
ADD: added some time debug statements to be able to measure execution time.
[proxmark3-svn] / tools / mfkey / crapto1.c
CommitLineData
7847961b 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
72109f82 18 Copyright (C) 2008-2014 bla <blapost@gmail.com>\r
7847961b 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
685d366c 34\r
35\r
36typedef struct bucket {\r
37 uint32_t *head;\r
38 uint32_t *bp;\r
39} bucket_t;\r
40\r
41typedef bucket_t bucket_array_t[2][0x100];\r
42\r
43typedef struct bucket_info {\r
44 struct {\r
45 uint32_t *head, *tail;\r
46 } bucket_info[2][0x100];\r
47 uint32_t numbuckets;\r
48 } bucket_info_t;\r
49\r
50\r
51static void bucket_sort_intersect(uint32_t* const estart, uint32_t* const estop,\r
52 uint32_t* const ostart, uint32_t* const ostop,\r
53 bucket_info_t *bucket_info, bucket_array_t bucket)\r
7847961b 54{\r
685d366c 55 uint32_t *p1, *p2;\r
56 uint32_t *start[2];\r
57 uint32_t *stop[2];\r
7847961b 58\r
685d366c 59 start[0] = estart;\r
60 stop[0] = estop;\r
61 start[1] = ostart;\r
62 stop[1] = ostop;\r
7847961b 63\r
685d366c 64 // init buckets to be empty\r
65 for (uint32_t i = 0; i < 2; i++) {\r
66 for (uint32_t j = 0x00; j <= 0xff; j++) {\r
67 bucket[i][j].bp = bucket[i][j].head;\r
68 }\r
69 }\r
70\r
71 // sort the lists into the buckets based on the MSB (contribution bits)\r
72 for (uint32_t i = 0; i < 2; i++) {\r
73 for (p1 = start[i]; p1 <= stop[i]; p1++) {\r
74 uint32_t bucket_index = (*p1 & 0xff000000) >> 24;\r
75 *(bucket[i][bucket_index].bp++) = *p1;\r
76 }\r
77 }\r
7847961b 78\r
7847961b 79\r
685d366c 80 // write back intersecting buckets as sorted list.\r
81 // fill in bucket_info with head and tail of the bucket contents in the list and number of non-empty buckets.\r
82 uint32_t nonempty_bucket;\r
83 for (uint32_t i = 0; i < 2; i++) {\r
84 p1 = start[i];\r
85 nonempty_bucket = 0;\r
86 for (uint32_t j = 0x00; j <= 0xff; j++) {\r
87 if (bucket[0][j].bp != bucket[0][j].head && bucket[1][j].bp != bucket[1][j].head) { // non-empty intersecting buckets only\r
88 bucket_info->bucket_info[i][nonempty_bucket].head = p1;\r
89 for (p2 = bucket[i][j].head; p2 < bucket[i][j].bp; *p1++ = *p2++);\r
90 bucket_info->bucket_info[i][nonempty_bucket].tail = p1 - 1;\r
91 nonempty_bucket++;\r
92 }\r
93 }\r
94 bucket_info->numbuckets = nonempty_bucket;\r
95 }\r
7847961b 96}\r
685d366c 97\r
7847961b 98\r
99/** update_contribution\r
100 * helper, calculates the partial linear feedback contributions and puts in MSB\r
101 */\r
838c15a6 102static inline void update_contribution(uint32_t *item, const uint32_t mask1, const uint32_t mask2)\r
7847961b 103{\r
104 uint32_t p = *item >> 25;\r
105\r
106 p = p << 1 | parity(*item & mask1);\r
107 p = p << 1 | parity(*item & mask2);\r
108 *item = p << 24 | (*item & 0xffffff);\r
109}\r
110\r
111/** extend_table\r
112 * using a bit of the keystream extend the table of possible lfsr states\r
113 */\r
838c15a6 114static inline void extend_table(uint32_t *tbl, uint32_t **end, int bit, int m1, int m2, uint32_t in)\r
7847961b 115{\r
116 in <<= 24;\r
117 for(*tbl <<= 1; tbl <= *end; *++tbl <<= 1)\r
118 if(filter(*tbl) ^ filter(*tbl | 1)) {\r
119 *tbl |= filter(*tbl) ^ bit;\r
120 update_contribution(tbl, m1, m2);\r
121 *tbl ^= in;\r
122 } else if(filter(*tbl) == bit) {\r
123 *++*end = tbl[1];\r
124 tbl[1] = tbl[0] | 1;\r
125 update_contribution(tbl, m1, m2);\r
126 *tbl++ ^= in;\r
127 update_contribution(tbl, m1, m2);\r
128 *tbl ^= in;\r
129 } else\r
130 *tbl-- = *(*end)--;\r
131}\r
132/** extend_table_simple\r
133 * using a bit of the keystream extend the table of possible lfsr states\r
134 */\r
135static inline void extend_table_simple(uint32_t *tbl, uint32_t **end, int bit)\r
136{\r
838c15a6 137 for(*tbl <<= 1; tbl <= *end; *++tbl <<= 1) {\r
685d366c 138 if(filter(*tbl) ^ filter(*tbl | 1)) { // replace\r
7847961b 139 *tbl |= filter(*tbl) ^ bit;\r
685d366c 140 } else if(filter(*tbl) == bit) { // insert\r
7847961b 141 *++*end = *++tbl;\r
142 *tbl = tbl[-1] | 1;\r
838c15a6 143 } else { // drop\r
7847961b 144 *tbl-- = *(*end)--;\r
838c15a6 145 }\r
146 }\r
7847961b 147}\r
148/** recover\r
149 * recursively narrow down the search space, 4 bits of keystream at a time\r
150 */\r
151static struct Crypto1State*\r
152recover(uint32_t *o_head, uint32_t *o_tail, uint32_t oks,\r
153 uint32_t *e_head, uint32_t *e_tail, uint32_t eks, int rem,\r
685d366c 154 struct Crypto1State *sl, uint32_t in, bucket_array_t bucket)\r
7847961b 155{\r
685d366c 156 uint32_t *o, *e;\r
157 bucket_info_t bucket_info;\r
7847961b 158\r
159 if(rem == -1) {\r
160 for(e = e_head; e <= e_tail; ++e) {\r
161 *e = *e << 1 ^ parity(*e & LF_POLY_EVEN) ^ !!(in & 4);\r
162 for(o = o_head; o <= o_tail; ++o, ++sl) {\r
163 sl->even = *o;\r
164 sl->odd = *e ^ parity(*o & LF_POLY_ODD);\r
165 sl[1].odd = sl[1].even = 0;\r
166 }\r
167 }\r
168 return sl;\r
169 }\r
170\r
685d366c 171 for(uint32_t i = 0; i < 4 && rem--; i++) {\r
7847961b 172 oks >>= 1;\r
173 eks >>= 1;\r
174 in >>= 2;\r
838c15a6 175 extend_table(o_head, &o_tail, oks & 1, LF_POLY_EVEN << 1 | 1, LF_POLY_ODD << 1, 0);\r
7847961b 176 if(o_head > o_tail)\r
177 return sl;\r
178\r
838c15a6 179 extend_table(e_head, &e_tail, eks & 1, LF_POLY_ODD, LF_POLY_EVEN << 1 | 1, in & 3);\r
7847961b 180 if(e_head > e_tail)\r
181 return sl;\r
182 }\r
183\r
685d366c 184 bucket_sort_intersect(e_head, e_tail, o_head, o_tail, &bucket_info, bucket);\r
7847961b 185\r
685d366c 186 for (int i = bucket_info.numbuckets - 1; i >= 0; i--) {\r
187 sl = recover(bucket_info.bucket_info[1][i].head, bucket_info.bucket_info[1][i].tail, oks,\r
188 bucket_info.bucket_info[0][i].head, bucket_info.bucket_info[0][i].tail, eks,\r
189 rem, sl, in, bucket);\r
7847961b 190 }\r
7847961b 191\r
192 return sl;\r
193}\r
194/** lfsr_recovery\r
195 * recover the state of the lfsr given 32 bits of the keystream\r
196 * additionally you can use the in parameter to specify the value\r
197 * that was fed into the lfsr at the time the keystream was generated\r
198 */\r
199struct Crypto1State* lfsr_recovery32(uint32_t ks2, uint32_t in)\r
200{\r
201 struct Crypto1State *statelist;\r
202 uint32_t *odd_head = 0, *odd_tail = 0, oks = 0;\r
203 uint32_t *even_head = 0, *even_tail = 0, eks = 0;\r
204 int i;\r
205\r
a1afa550 206 // split the keystream into an odd and even part\r
7847961b 207 for(i = 31; i >= 0; i -= 2)\r
208 oks = oks << 1 | BEBIT(ks2, i);\r
209 for(i = 30; i >= 0; i -= 2)\r
210 eks = eks << 1 | BEBIT(ks2, i);\r
211\r
212 odd_head = odd_tail = malloc(sizeof(uint32_t) << 21);\r
213 even_head = even_tail = malloc(sizeof(uint32_t) << 21);\r
214 statelist = malloc(sizeof(struct Crypto1State) << 18);\r
215 if(!odd_tail-- || !even_tail-- || !statelist) {\r
216 free(statelist);\r
217 statelist = 0;\r
218 goto out;\r
219 }\r
220\r
221 statelist->odd = statelist->even = 0;\r
222\r
685d366c 223 // allocate memory for out of place bucket_sort\r
224 bucket_array_t bucket;\r
838c15a6 225 \r
226 for (uint32_t i = 0; i < 2; i++) {\r
685d366c 227 for (uint32_t j = 0; j <= 0xff; j++) {\r
228 bucket[i][j].head = malloc(sizeof(uint32_t)<<14);\r
229 if (!bucket[i][j].head) {\r
230 goto out;\r
231 }\r
232 }\r
838c15a6 233 }\r
685d366c 234\r
a1afa550 235 // initialize statelists: add all possible states which would result into the rightmost 2 bits of the keystream\r
7847961b 236 for(i = 1 << 20; i >= 0; --i) {\r
237 if(filter(i) == (oks & 1))\r
238 *++odd_tail = i;\r
239 if(filter(i) == (eks & 1))\r
240 *++even_tail = i;\r
241 }\r
242\r
a1afa550 243 // extend the statelists. Look at the next 8 Bits of the keystream (4 Bit each odd and even):\r
7847961b 244 for(i = 0; i < 4; i++) {\r
245 extend_table_simple(odd_head, &odd_tail, (oks >>= 1) & 1);\r
246 extend_table_simple(even_head, &even_tail, (eks >>= 1) & 1);\r
247 }\r
248\r
a1afa550 249 // the statelists now contain all states which could have generated the last 10 Bits of the keystream.\r
250 // 22 bits to go to recover 32 bits in total. From now on, we need to take the "in"\r
251 // parameter into account.\r
685d366c 252 in = (in >> 16 & 0xff) | (in << 16) | (in & 0xff00); // Byte swapping\r
838c15a6 253 recover(odd_head, odd_tail, oks, even_head, even_tail, eks, 11, statelist, in << 1, bucket);\r
7847961b 254\r
255out:\r
685d366c 256 for (uint32_t i = 0; i < 2; i++)\r
257 for (uint32_t j = 0; j <= 0xff; j++)\r
258 free(bucket[i][j].head);\r
838c15a6 259 free(odd_head);\r
260 free(even_head);\r
7847961b 261 return statelist;\r
262}\r
263\r
264static const uint32_t S1[] = { 0x62141, 0x310A0, 0x18850, 0x0C428, 0x06214,\r
265 0x0310A, 0x85E30, 0xC69AD, 0x634D6, 0xB5CDE, 0xDE8DA, 0x6F46D, 0xB3C83,\r
266 0x59E41, 0xA8995, 0xD027F, 0x6813F, 0x3409F, 0x9E6FA};\r
267static const uint32_t S2[] = { 0x3A557B00, 0x5D2ABD80, 0x2E955EC0, 0x174AAF60,\r
268 0x0BA557B0, 0x05D2ABD8, 0x0449DE68, 0x048464B0, 0x42423258, 0x278192A8,\r
269 0x156042D0, 0x0AB02168, 0x43F89B30, 0x61FC4D98, 0x765EAD48, 0x7D8FDD20,\r
270 0x7EC7EE90, 0x7F63F748, 0x79117020};\r
271static const uint32_t T1[] = {\r
272 0x4F37D, 0x279BE, 0x97A6A, 0x4BD35, 0x25E9A, 0x12F4D, 0x097A6, 0x80D66,\r
273 0xC4006, 0x62003, 0xB56B4, 0x5AB5A, 0xA9318, 0xD0F39, 0x6879C, 0xB057B,\r
274 0x582BD, 0x2C15E, 0x160AF, 0x8F6E2, 0xC3DC4, 0xE5857, 0x72C2B, 0x39615,\r
275 0x98DBF, 0xC806A, 0xE0680, 0x70340, 0x381A0, 0x98665, 0x4C332, 0xA272C};\r
276static const uint32_t T2[] = { 0x3C88B810, 0x5E445C08, 0x2982A580, 0x14C152C0,\r
277 0x4A60A960, 0x253054B0, 0x52982A58, 0x2FEC9EA8, 0x1156C4D0, 0x08AB6268,\r
278 0x42F53AB0, 0x217A9D58, 0x161DC528, 0x0DAE6910, 0x46D73488, 0x25CB11C0,\r
279 0x52E588E0, 0x6972C470, 0x34B96238, 0x5CFC3A98, 0x28DE96C8, 0x12CFC0E0,\r
280 0x4967E070, 0x64B3F038, 0x74F97398, 0x7CDC3248, 0x38CE92A0, 0x1C674950,\r
281 0x0E33A4A8, 0x01B959D0, 0x40DCACE8, 0x26CEDDF0};\r
282static const uint32_t C1[] = { 0x846B5, 0x4235A, 0x211AD};\r
283static const uint32_t C2[] = { 0x1A822E0, 0x21A822E0, 0x21A822E0};\r
284/** Reverse 64 bits of keystream into possible cipher states\r
285 * Variation mentioned in the paper. Somewhat optimized version\r
286 */\r
287struct Crypto1State* lfsr_recovery64(uint32_t ks2, uint32_t ks3)\r
288{\r
289 struct Crypto1State *statelist, *sl;\r
290 uint8_t oks[32], eks[32], hi[32];\r
291 uint32_t low = 0, win = 0;\r
292 uint32_t *tail, table[1 << 16];\r
293 int i, j;\r
294\r
295 sl = statelist = malloc(sizeof(struct Crypto1State) << 4);\r
296 if(!sl)\r
297 return 0;\r
298 sl->odd = sl->even = 0;\r
299\r
300 for(i = 30; i >= 0; i -= 2) {\r
301 oks[i >> 1] = BEBIT(ks2, i);\r
302 oks[16 + (i >> 1)] = BEBIT(ks3, i);\r
303 }\r
304 for(i = 31; i >= 0; i -= 2) {\r
305 eks[i >> 1] = BEBIT(ks2, i);\r
306 eks[16 + (i >> 1)] = BEBIT(ks3, i);\r
307 }\r
308\r
309 for(i = 0xfffff; i >= 0; --i) {\r
310 if (filter(i) != oks[0])\r
311 continue;\r
312\r
313 *(tail = table) = i;\r
314 for(j = 1; tail >= table && j < 29; ++j)\r
315 extend_table_simple(table, &tail, oks[j]);\r
316\r
317 if(tail < table)\r
318 continue;\r
319\r
320 for(j = 0; j < 19; ++j)\r
321 low = low << 1 | parity(i & S1[j]);\r
322 for(j = 0; j < 32; ++j)\r
323 hi[j] = parity(i & T1[j]);\r
324\r
325 for(; tail >= table; --tail) {\r
326 for(j = 0; j < 3; ++j) {\r
327 *tail = *tail << 1;\r
328 *tail |= parity((i & C1[j]) ^ (*tail & C2[j]));\r
329 if(filter(*tail) != oks[29 + j])\r
330 goto continue2;\r
331 }\r
332\r
333 for(j = 0; j < 19; ++j)\r
334 win = win << 1 | parity(*tail & S2[j]);\r
335\r
336 win ^= low;\r
337 for(j = 0; j < 32; ++j) {\r
338 win = win << 1 ^ hi[j] ^ parity(*tail & T2[j]);\r
339 if(filter(win) != eks[j])\r
340 goto continue2;\r
341 }\r
342\r
343 *tail = *tail << 1 | parity(LF_POLY_EVEN & *tail);\r
344 sl->odd = *tail ^ parity(LF_POLY_ODD & win);\r
345 sl->even = win;\r
346 ++sl;\r
347 sl->odd = sl->even = 0;\r
348 continue2:;\r
349 }\r
350 }\r
351 return statelist;\r
352}\r
353\r
354/** lfsr_rollback_bit\r
355 * Rollback the shift register in order to get previous states\r
356 */\r
357uint8_t lfsr_rollback_bit(struct Crypto1State *s, uint32_t in, int fb)\r
358{\r
359 int out;\r
360 uint8_t ret;\r
72109f82 361 uint32_t t;\r
7847961b 362\r
363 s->odd &= 0xffffff;\r
72109f82 364 t = s->odd, s->odd = s->even, s->even = t;\r
7847961b 365\r
366 out = s->even & 1;\r
367 out ^= LF_POLY_EVEN & (s->even >>= 1);\r
368 out ^= LF_POLY_ODD & s->odd;\r
369 out ^= !!in;\r
370 out ^= (ret = filter(s->odd)) & !!fb;\r
371\r
372 s->even |= parity(out) << 23;\r
373 return ret;\r
374}\r
375/** lfsr_rollback_byte\r
376 * Rollback the shift register in order to get previous states\r
377 */\r
378uint8_t lfsr_rollback_byte(struct Crypto1State *s, uint32_t in, int fb)\r
379{\r
a1afa550 380 /*\r
7847961b 381 int i, ret = 0;\r
382 for (i = 7; i >= 0; --i)\r
383 ret |= lfsr_rollback_bit(s, BIT(in, i), fb) << i;\r
a1afa550 384*/\r
8130eba4 385// unfold loop 20160112\r
a1afa550 386 uint8_t ret = 0;\r
387 ret |= lfsr_rollback_bit(s, BIT(in, 7), fb) << 7;\r
388 ret |= lfsr_rollback_bit(s, BIT(in, 6), fb) << 6;\r
389 ret |= lfsr_rollback_bit(s, BIT(in, 5), fb) << 5;\r
390 ret |= lfsr_rollback_bit(s, BIT(in, 4), fb) << 4;\r
391 ret |= lfsr_rollback_bit(s, BIT(in, 3), fb) << 3;\r
392 ret |= lfsr_rollback_bit(s, BIT(in, 2), fb) << 2;\r
393 ret |= lfsr_rollback_bit(s, BIT(in, 1), fb) << 1;\r
394 ret |= lfsr_rollback_bit(s, BIT(in, 0), fb) << 0;\r
7847961b 395 return ret;\r
396}\r
397/** lfsr_rollback_word\r
398 * Rollback the shift register in order to get previous states\r
399 */\r
400uint32_t lfsr_rollback_word(struct Crypto1State *s, uint32_t in, int fb)\r
401{\r
a1afa550 402 /*\r
7847961b 403 int i;\r
404 uint32_t ret = 0;\r
405 for (i = 31; i >= 0; --i)\r
406 ret |= lfsr_rollback_bit(s, BEBIT(in, i), fb) << (i ^ 24);\r
a1afa550 407*/\r
8130eba4 408// unfold loop 20160112\r
a1afa550 409 uint32_t ret = 0;\r
410 ret |= lfsr_rollback_bit(s, BEBIT(in, 31), fb) << (31 ^ 24);\r
411 ret |= lfsr_rollback_bit(s, BEBIT(in, 30), fb) << (30 ^ 24);\r
412 ret |= lfsr_rollback_bit(s, BEBIT(in, 29), fb) << (29 ^ 24);\r
413 ret |= lfsr_rollback_bit(s, BEBIT(in, 28), fb) << (28 ^ 24);\r
414 ret |= lfsr_rollback_bit(s, BEBIT(in, 27), fb) << (27 ^ 24);\r
415 ret |= lfsr_rollback_bit(s, BEBIT(in, 26), fb) << (26 ^ 24);\r
416 ret |= lfsr_rollback_bit(s, BEBIT(in, 25), fb) << (25 ^ 24);\r
417 ret |= lfsr_rollback_bit(s, BEBIT(in, 24), fb) << (24 ^ 24);\r
418\r
419 ret |= lfsr_rollback_bit(s, BEBIT(in, 23), fb) << (23 ^ 24);\r
420 ret |= lfsr_rollback_bit(s, BEBIT(in, 22), fb) << (22 ^ 24);\r
421 ret |= lfsr_rollback_bit(s, BEBIT(in, 21), fb) << (21 ^ 24);\r
422 ret |= lfsr_rollback_bit(s, BEBIT(in, 20), fb) << (20 ^ 24);\r
423 ret |= lfsr_rollback_bit(s, BEBIT(in, 19), fb) << (19 ^ 24);\r
424 ret |= lfsr_rollback_bit(s, BEBIT(in, 18), fb) << (18 ^ 24);\r
425 ret |= lfsr_rollback_bit(s, BEBIT(in, 17), fb) << (17 ^ 24);\r
426 ret |= lfsr_rollback_bit(s, BEBIT(in, 16), fb) << (16 ^ 24);\r
427 \r
428 ret |= lfsr_rollback_bit(s, BEBIT(in, 15), fb) << (15 ^ 24);\r
429 ret |= lfsr_rollback_bit(s, BEBIT(in, 14), fb) << (14 ^ 24);\r
430 ret |= lfsr_rollback_bit(s, BEBIT(in, 13), fb) << (13 ^ 24);\r
431 ret |= lfsr_rollback_bit(s, BEBIT(in, 12), fb) << (12 ^ 24);\r
432 ret |= lfsr_rollback_bit(s, BEBIT(in, 11), fb) << (11 ^ 24);\r
433 ret |= lfsr_rollback_bit(s, BEBIT(in, 10), fb) << (10 ^ 24);\r
434 ret |= lfsr_rollback_bit(s, BEBIT(in, 9), fb) << (9 ^ 24);\r
435 ret |= lfsr_rollback_bit(s, BEBIT(in, 8), fb) << (8 ^ 24);\r
436 \r
437 ret |= lfsr_rollback_bit(s, BEBIT(in, 7), fb) << (7 ^ 24);\r
438 ret |= lfsr_rollback_bit(s, BEBIT(in, 6), fb) << (6 ^ 24);\r
439 ret |= lfsr_rollback_bit(s, BEBIT(in, 5), fb) << (5 ^ 24);\r
440 ret |= lfsr_rollback_bit(s, BEBIT(in, 4), fb) << (4 ^ 24);\r
441 ret |= lfsr_rollback_bit(s, BEBIT(in, 3), fb) << (3 ^ 24);\r
442 ret |= lfsr_rollback_bit(s, BEBIT(in, 2), fb) << (2 ^ 24);\r
443 ret |= lfsr_rollback_bit(s, BEBIT(in, 1), fb) << (1 ^ 24);\r
444 ret |= lfsr_rollback_bit(s, BEBIT(in, 0), fb) << (0 ^ 24);\r
7847961b 445 return ret;\r
446}\r
447\r
448/** nonce_distance\r
449 * x,y valid tag nonces, then prng_successor(x, nonce_distance(x, y)) = y\r
450 */\r
451static uint16_t *dist = 0;\r
452int nonce_distance(uint32_t from, uint32_t to)\r
453{\r
454 uint16_t x, i;\r
455 if(!dist) {\r
456 dist = malloc(2 << 16);\r
457 if(!dist)\r
458 return -1;\r
459 for (x = i = 1; i; ++i) {\r
460 dist[(x & 0xff) << 8 | x >> 8] = i;\r
461 x = x >> 1 | (x ^ x >> 2 ^ x >> 3 ^ x >> 5) << 15;\r
462 }\r
463 }\r
464 return (65535 + dist[to >> 16] - dist[from >> 16]) % 65535;\r
465}\r
466\r
467\r
468static uint32_t fastfwd[2][8] = {\r
469 { 0, 0x4BC53, 0xECB1, 0x450E2, 0x25E29, 0x6E27A, 0x2B298, 0x60ECB},\r
470 { 0, 0x1D962, 0x4BC53, 0x56531, 0xECB1, 0x135D3, 0x450E2, 0x58980}};\r
93b0bbd2 471\r
472\r
7847961b 473/** lfsr_prefix_ks\r
474 *\r
475 * Is an exported helper function from the common prefix attack\r
476 * Described in the "dark side" paper. It returns an -1 terminated array\r
477 * of possible partial(21 bit) secret state.\r
478 * The required keystream(ks) needs to contain the keystream that was used to\r
479 * encrypt the NACK which is observed when varying only the 3 last bits of Nr\r
480 * only correct iff [NR_3] ^ NR_3 does not depend on Nr_3\r
481 */\r
482uint32_t *lfsr_prefix_ks(uint8_t ks[8], int isodd)\r
483{\r
a1afa550 484 uint32_t *candidates = malloc(4 << 10);\r
8130eba4 485 if(!candidates) return 0;\r
486 \r
a1afa550 487 uint32_t c, entry;\r
488 int size = 0, i, good;\r
7847961b 489\r
7847961b 490 for(i = 0; i < 1 << 21; ++i) {\r
491 for(c = 0, good = 1; good && c < 8; ++c) {\r
492 entry = i ^ fastfwd[isodd][c];\r
493 good &= (BIT(ks[c], isodd) == filter(entry >> 1));\r
494 good &= (BIT(ks[c], isodd + 2) == filter(entry));\r
495 }\r
496 if(good)\r
497 candidates[size++] = i;\r
498 }\r
499\r
500 candidates[size] = -1;\r
501\r
502 return candidates;\r
503}\r
504\r
505/** check_pfx_parity\r
506 * helper function which eliminates possible secret states using parity bits\r
507 */\r
93b0bbd2 508static 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
7847961b 509{\r
510 uint32_t ks1, nr, ks2, rr, ks3, c, good = 1;\r
511\r
512 for(c = 0; good && c < 8; ++c) {\r
513 sl->odd = odd ^ fastfwd[1][c];\r
514 sl->even = even ^ fastfwd[0][c];\r
515\r
516 lfsr_rollback_bit(sl, 0, 0);\r
517 lfsr_rollback_bit(sl, 0, 0);\r
518\r
519 ks3 = lfsr_rollback_bit(sl, 0, 0);\r
520 ks2 = lfsr_rollback_word(sl, 0, 0);\r
521 ks1 = lfsr_rollback_word(sl, prefix | c << 5, 1);\r
522\r
523 nr = ks1 ^ (prefix | c << 5);\r
524 rr = ks2 ^ rresp;\r
525\r
526 good &= parity(nr & 0x000000ff) ^ parities[c][3] ^ BIT(ks2, 24);\r
527 good &= parity(rr & 0xff000000) ^ parities[c][4] ^ BIT(ks2, 16);\r
528 good &= parity(rr & 0x00ff0000) ^ parities[c][5] ^ BIT(ks2, 8);\r
529 good &= parity(rr & 0x0000ff00) ^ parities[c][6] ^ BIT(ks2, 0);\r
530 good &= parity(rr & 0x000000ff) ^ parities[c][7] ^ ks3;\r
531 }\r
532\r
533 return sl + good;\r
534} \r
535\r
7847961b 536/** lfsr_common_prefix\r
537 * Implentation of the common prefix attack.\r
93b0bbd2 538 * Requires the 28 bit constant prefix used as reader nonce (pfx)\r
539 * The reader response used (rr)\r
540 * The keystream used to encrypt the observed NACK's (ks)\r
541 * The parity bits (par)\r
542 * It returns a zero terminated list of possible cipher states after the\r
543 * tag nonce was fed in\r
7847961b 544 */\r
8130eba4 545\r
93b0bbd2 546struct Crypto1State* lfsr_common_prefix(uint32_t pfx, uint32_t rr, uint8_t ks[8], uint8_t par[8][8])\r
7847961b 547{\r
548 struct Crypto1State *statelist, *s;\r
549 uint32_t *odd, *even, *o, *e, top;\r
550\r
551 odd = lfsr_prefix_ks(ks, 1);\r
552 even = lfsr_prefix_ks(ks, 0);\r
553\r
838c15a6 554 s = statelist = malloc((sizeof *statelist) << 20);\r
7847961b 555 if(!s || !odd || !even) {\r
556 free(statelist);\r
838c15a6 557 statelist = 0;\r
558 goto out;\r
7847961b 559 }\r
560\r
561 for(o = odd; *o + 1; ++o)\r
562 for(e = even; *e + 1; ++e)\r
563 for(top = 0; top < 64; ++top) {\r
564 *o += 1 << 21;\r
565 *e += (!(top & 7) + 1) << 21;\r
566 s = check_pfx_parity(pfx, rr, par, *o, *e, s);\r
567 }\r
568\r
569 s->odd = s->even = 0;\r
838c15a6 570out:\r
a1afa550 571 free(odd);\r
572 free(even);\r
7847961b 573 return statelist;\r
838c15a6 574}\r
Proxmark3 GIT tracking
Impressum, Datenschutz