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