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