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