]> git.zerfleddert.de Git - proxmark3-svn/blame - tools/nonce2key/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 / nonce2key / crapto1.c
CommitLineData
93f57590 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
93b0bbd2 18 Copyright (C) 2008-2014 bla <blapost@gmail.com>\r
93f57590 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
93f57590 54{\r
685d366c 55 uint32_t *p1, *p2;\r
56 uint32_t *start[2];\r
57 uint32_t *stop[2];\r
93f57590 58\r
685d366c 59 start[0] = estart;\r
60 stop[0] = estop;\r
61 start[1] = ostart;\r
62 stop[1] = ostop;\r
93f57590 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
93f57590 78\r
93f57590 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
93f57590 96}\r
685d366c 97\r
93f57590 98/** binsearch\r
99 * Binary search for the first occurence of *stop's MSB in sorted [start,stop]\r
100 */\r
72109f82 101static inline uint32_t* binsearch(uint32_t *start, uint32_t *stop)\r
93f57590 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
93b0bbd2 151static inline void extend_table_simple(uint32_t *tbl, uint32_t **end, int bit)\r
93f57590 152{\r
153 for(*tbl <<= 1; tbl <= *end; *++tbl <<= 1)\r
685d366c 154 if(filter(*tbl) ^ filter(*tbl | 1)) { // replace\r
93f57590 155 *tbl |= filter(*tbl) ^ bit;\r
685d366c 156 } else if(filter(*tbl) == bit) { // insert\r
93f57590 157 *++*end = *++tbl;\r
158 *tbl = tbl[-1] | 1;\r
685d366c 159 } else // drop\r
93f57590 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
93f57590 169{\r
685d366c 170 uint32_t *o, *e;\r
171 bucket_info_t bucket_info;\r
93f57590 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
72109f82 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
93f57590 191 if(o_head > o_tail)\r
192 return sl;\r
193\r
72109f82 194 extend_table(e_head, &e_tail, eks & 1, LF_POLY_ODD,\r
195 LF_POLY_EVEN << 1 | 1, in & 3);\r
93f57590 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
93f57590 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
93f57590 206 }\r
93f57590 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
93f57590 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
72109f82 231 if(!odd_tail-- || !even_tail-- || !statelist) {\r
232 free(statelist);\r
233 statelist = 0;\r
93f57590 234 goto out;\r
72109f82 235 }\r
93f57590 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
93f57590 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
93f57590 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
93f57590 268 recover(odd_head, odd_tail, oks,\r
685d366c 269 even_head, even_tail, eks, 11, statelist, in << 1, bucket);\r
270\r
93f57590 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
93f57590 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
72109f82 319 oks[i >> 1] = BEBIT(ks2, i);\r
320 oks[16 + (i >> 1)] = BEBIT(ks3, i);\r
93f57590 321 }\r
322 for(i = 31; i >= 0; i -= 2) {\r
72109f82 323 eks[i >> 1] = BEBIT(ks2, i);\r
324 eks[16 + (i >> 1)] = BEBIT(ks3, i);\r
93f57590 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
72109f82 375uint8_t lfsr_rollback_bit(struct Crypto1State *s, uint32_t in, int fb)\r
93f57590 376{\r
377 int out;\r
72109f82 378 uint8_t ret;\r
379 uint32_t t;\r
93f57590 380\r
381 s->odd &= 0xffffff;\r
72109f82 382 t = s->odd, s->odd = s->even, s->even = t;\r
93f57590 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
72109f82 388 out ^= (ret = filter(s->odd)) & !!fb;\r
93f57590 389\r
390 s->even |= parity(out) << 23;\r
72109f82 391 return ret;\r
93f57590 392}\r
393/** lfsr_rollback_byte\r
394 * Rollback the shift register in order to get previous states\r
395 */\r
72109f82 396uint8_t lfsr_rollback_byte(struct Crypto1State *s, uint32_t in, int fb)\r
93f57590 397{\r
a1afa550 398 /*\r
72109f82 399 int i, ret = 0;\r
93f57590 400 for (i = 7; i >= 0; --i)\r
72109f82 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
72109f82 413 return ret;\r
93f57590 414}\r
415/** lfsr_rollback_word\r
416 * Rollback the shift register in order to get previous states\r
417 */\r
72109f82 418uint32_t lfsr_rollback_word(struct Crypto1State *s, uint32_t in, int fb)\r
93f57590 419{\r
a1afa550 420 /*\r
93f57590 421 int i;\r
72109f82 422 uint32_t ret = 0;\r
93f57590 423 for (i = 31; i >= 0; --i)\r
72109f82 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
72109f82 463 return ret;\r
93f57590 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
489\r
490\r
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
72109f82 497 * encrypt the NACK which is observed when varying only the 3 last bits of Nr\r
93f57590 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
93f57590 507\r
72109f82 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
93f57590 513 }\r
72109f82 514 if(good)\r
515 candidates[size++] = i;\r
516 }\r
93f57590 517\r
72109f82 518 candidates[size] = -1;\r
93f57590 519\r
520 return candidates;\r
521}\r
522\r
72109f82 523/** check_pfx_parity\r
93f57590 524 * helper function which eliminates possible secret states using parity bits\r
525 */\r
9d1eaa28 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
93f57590 527{\r
72109f82 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
93f57590 541 nr = ks1 ^ (prefix | c << 5);\r
542 rr = ks2 ^ rresp;\r
543\r
93f57590 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
72109f82 548 good &= parity(rr & 0x000000ff) ^ parities[c][7] ^ ks3;\r
93f57590 549 }\r
550\r
72109f82 551 return sl + good;\r
93f57590 552} \r
553\r
93f57590 554/** lfsr_common_prefix\r
555 * Implentation of the common prefix attack.\r
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
562 */\r
8130eba4 563\r
9d1eaa28 564struct Crypto1State* lfsr_common_prefix(uint32_t pfx, uint32_t rr, uint8_t ks[8], uint8_t par[8][8])\r
93f57590 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
72109f82 573 if(!s || !odd || !even) {\r
574 free(statelist);\r
9d1eaa28 575 free(odd);\r
576 free(even);\r
577 return 0;\r
72109f82 578 }\r
93f57590 579\r
72109f82 580 for(o = odd; *o + 1; ++o)\r
581 for(e = even; *e + 1; ++e)\r
93f57590 582 for(top = 0; top < 64; ++top) {\r
72109f82 583 *o += 1 << 21;\r
584 *e += (!(top & 7) + 1) << 21;\r
585 s = check_pfx_parity(pfx, rr, par, *o, *e, s);\r
93f57590 586 }\r
587\r
588 s->odd = s->even = 0;\r
9d1eaa28 589\r
a1afa550 590 free(odd);\r
591 free(even);\r
93f57590 592 return statelist;\r
8130eba4 593}
Proxmark3 GIT tracking
Impressum, Datenschutz