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