]> git.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
CHG: syntax suger
[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
66afab80 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
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
161 if ( !bucket_malloc(bucket) ) goto out;\r
66afab80 162\r
9492e0b0 163 // initialize statelists: add all possible states which would result into the rightmost 2 bits of the keystream\r
f89c7050
M		 164 for(i = 1 << 20; i >= 0; --i) {\r
165 if(filter(i) == (oks & 1))\r
166 *++odd_tail = i;\r
167 if(filter(i) == (eks & 1))\r
168 *++even_tail = i;\r
169 }\r
170\r
9492e0b0 171 // extend the statelists. Look at the next 8 Bits of the keystream (4 Bit each odd and even):\r
f89c7050
M		 172 for(i = 0; i < 4; i++) {\r
173 extend_table_simple(odd_head, &odd_tail, (oks >>= 1) & 1);\r
174 extend_table_simple(even_head, &even_tail, (eks >>= 1) & 1);\r
175 }\r
176\r
9492e0b0 177 // the statelists now contain all states which could have generated the last 10 Bits of the keystream.\r
178 // 22 bits to go to recover 32 bits in total. From now on, we need to take the "in"\r
179 // parameter into account.\r
66afab80 180 in = (in >> 16 & 0xff) | (in << 16) | (in & 0xff00); // Byte swapping\r
089d061f 181 recover(odd_head, odd_tail, oks, even_head, even_tail, eks, 11, statelist, in << 1, bucket);\r
f89c7050
M		 182\r
183out:\r
184 free(odd_head);\r
185 free(even_head);\r
089d061f 186 bucket_free(bucket);\r
f89c7050
M		 187 return statelist;\r
188}\r
189\r
190static const uint32_t S1[] = { 0x62141, 0x310A0, 0x18850, 0x0C428, 0x06214,\r
191 0x0310A, 0x85E30, 0xC69AD, 0x634D6, 0xB5CDE, 0xDE8DA, 0x6F46D, 0xB3C83,\r
192 0x59E41, 0xA8995, 0xD027F, 0x6813F, 0x3409F, 0x9E6FA};\r
193static const uint32_t S2[] = { 0x3A557B00, 0x5D2ABD80, 0x2E955EC0, 0x174AAF60,\r
194 0x0BA557B0, 0x05D2ABD8, 0x0449DE68, 0x048464B0, 0x42423258, 0x278192A8,\r
195 0x156042D0, 0x0AB02168, 0x43F89B30, 0x61FC4D98, 0x765EAD48, 0x7D8FDD20,\r
196 0x7EC7EE90, 0x7F63F748, 0x79117020};\r
197static const uint32_t T1[] = {\r
198 0x4F37D, 0x279BE, 0x97A6A, 0x4BD35, 0x25E9A, 0x12F4D, 0x097A6, 0x80D66,\r
199 0xC4006, 0x62003, 0xB56B4, 0x5AB5A, 0xA9318, 0xD0F39, 0x6879C, 0xB057B,\r
200 0x582BD, 0x2C15E, 0x160AF, 0x8F6E2, 0xC3DC4, 0xE5857, 0x72C2B, 0x39615,\r
201 0x98DBF, 0xC806A, 0xE0680, 0x70340, 0x381A0, 0x98665, 0x4C332, 0xA272C};\r
202static const uint32_t T2[] = { 0x3C88B810, 0x5E445C08, 0x2982A580, 0x14C152C0,\r
203 0x4A60A960, 0x253054B0, 0x52982A58, 0x2FEC9EA8, 0x1156C4D0, 0x08AB6268,\r
204 0x42F53AB0, 0x217A9D58, 0x161DC528, 0x0DAE6910, 0x46D73488, 0x25CB11C0,\r
205 0x52E588E0, 0x6972C470, 0x34B96238, 0x5CFC3A98, 0x28DE96C8, 0x12CFC0E0,\r
206 0x4967E070, 0x64B3F038, 0x74F97398, 0x7CDC3248, 0x38CE92A0, 0x1C674950,\r
207 0x0E33A4A8, 0x01B959D0, 0x40DCACE8, 0x26CEDDF0};\r
208static const uint32_t C1[] = { 0x846B5, 0x4235A, 0x211AD};\r
209static const uint32_t C2[] = { 0x1A822E0, 0x21A822E0, 0x21A822E0};\r
210/** Reverse 64 bits of keystream into possible cipher states\r
211 * Variation mentioned in the paper. Somewhat optimized version\r
212 */\r
213struct Crypto1State* lfsr_recovery64(uint32_t ks2, uint32_t ks3)\r
214{\r
215 struct Crypto1State *statelist, *sl;\r
216 uint8_t oks[32], eks[32], hi[32];\r
217 uint32_t low = 0, win = 0;\r
218 uint32_t *tail, table[1 << 16];\r
219 int i, j;\r
220\r
221 sl = statelist = malloc(sizeof(struct Crypto1State) << 4);\r
222 if(!sl)\r
223 return 0;\r
224 sl->odd = sl->even = 0;\r
225\r
226 for(i = 30; i >= 0; i -= 2) {\r
a0f33b66 227 oks[i >> 1] = BEBIT(ks2, i);\r
228 oks[16 + (i >> 1)] = BEBIT(ks3, i);\r
f89c7050
M		 229 }\r
230 for(i = 31; i >= 0; i -= 2) {\r
a0f33b66 231 eks[i >> 1] = BEBIT(ks2, i);\r
232 eks[16 + (i >> 1)] = BEBIT(ks3, i);\r
f89c7050
M		 233 }\r
234\r
235 for(i = 0xfffff; i >= 0; --i) {\r
236 if (filter(i) != oks[0])\r
237 continue;\r
238\r
239 *(tail = table) = i;\r
240 for(j = 1; tail >= table && j < 29; ++j)\r
241 extend_table_simple(table, &tail, oks[j]);\r
242\r
243 if(tail < table)\r
244 continue;\r
245\r
246 for(j = 0; j < 19; ++j)\r
247 low = low << 1 | parity(i & S1[j]);\r
248 for(j = 0; j < 32; ++j)\r
249 hi[j] = parity(i & T1[j]);\r
250\r
251 for(; tail >= table; --tail) {\r
252 for(j = 0; j < 3; ++j) {\r
253 *tail = *tail << 1;\r
254 *tail |= parity((i & C1[j]) ^ (*tail & C2[j]));\r
255 if(filter(*tail) != oks[29 + j])\r
256 goto continue2;\r
257 }\r
258\r
259 for(j = 0; j < 19; ++j)\r
260 win = win << 1 | parity(*tail & S2[j]);\r
261\r
262 win ^= low;\r
263 for(j = 0; j < 32; ++j) {\r
264 win = win << 1 ^ hi[j] ^ parity(*tail & T2[j]);\r
265 if(filter(win) != eks[j])\r
266 goto continue2;\r
267 }\r
268\r
269 *tail = *tail << 1 | parity(LF_POLY_EVEN & *tail);\r
270 sl->odd = *tail ^ parity(LF_POLY_ODD & win);\r
271 sl->even = win;\r
272 ++sl;\r
273 sl->odd = sl->even = 0;\r
274 continue2:;\r
275 }\r
276 }\r
277 return statelist;\r
278}\r
279\r
280/** lfsr_rollback_bit\r
281 * Rollback the shift register in order to get previous states\r
282 */\r
a0f33b66 283uint8_t lfsr_rollback_bit(struct Crypto1State *s, uint32_t in, int fb)\r
f89c7050
M		 284{\r
285 int out;\r
a0f33b66 286 uint8_t ret;\r
287 uint32_t t;\r
f89c7050
M		 288\r
289 s->odd &= 0xffffff;\r
a0f33b66 290 t = s->odd, s->odd = s->even, s->even = t;\r
f89c7050
M		 291\r
292 out = s->even & 1;\r
293 out ^= LF_POLY_EVEN & (s->even >>= 1);\r
294 out ^= LF_POLY_ODD & s->odd;\r
295 out ^= !!in;\r
a0f33b66 296 out ^= (ret = filter(s->odd)) & !!fb;\r
f89c7050
M		 297\r
298 s->even |= parity(out) << 23;\r
a0f33b66 299 return ret;\r
f89c7050
M		 300}\r
301/** lfsr_rollback_byte\r
302 * Rollback the shift register in order to get previous states\r
303 */\r
a0f33b66 304uint8_t lfsr_rollback_byte(struct Crypto1State *s, uint32_t in, int fb)\r
f89c7050 305{\r
a0f33b66 306 /*\r
307 int i, ret = 0;\r
f89c7050 308 for (i = 7; i >= 0; --i)\r
a0f33b66 309 ret |= lfsr_rollback_bit(s, BIT(in, i), fb) << i;\r
738eeccd 310*/\r
311// unfold loop 20160112\r
a0f33b66 312 uint8_t ret = 0;\r
313 ret |= lfsr_rollback_bit(s, BIT(in, 7), fb) << 7;\r
314 ret |= lfsr_rollback_bit(s, BIT(in, 6), fb) << 6;\r
315 ret |= lfsr_rollback_bit(s, BIT(in, 5), fb) << 5;\r
316 ret |= lfsr_rollback_bit(s, BIT(in, 4), fb) << 4;\r
317 ret |= lfsr_rollback_bit(s, BIT(in, 3), fb) << 3;\r
318 ret |= lfsr_rollback_bit(s, BIT(in, 2), fb) << 2;\r
319 ret |= lfsr_rollback_bit(s, BIT(in, 1), fb) << 1;\r
320 ret |= lfsr_rollback_bit(s, BIT(in, 0), fb) << 0;\r
321 return ret;\r
f89c7050
M		 322}\r
323/** lfsr_rollback_word\r
324 * Rollback the shift register in order to get previous states\r
325 */\r
a0f33b66 326uint32_t lfsr_rollback_word(struct Crypto1State *s, uint32_t in, int fb)\r
f89c7050 327{\r
a0f33b66 328 /*\r
f89c7050 329 int i;\r
a0f33b66 330 uint32_t ret = 0;\r
f89c7050 331 for (i = 31; i >= 0; --i)\r
a0f33b66 332 ret |= lfsr_rollback_bit(s, BEBIT(in, i), fb) << (i ^ 24);\r
738eeccd 333*/\r
334// unfold loop 20160112\r
a0f33b66 335 uint32_t ret = 0;\r
336 ret |= lfsr_rollback_bit(s, BEBIT(in, 31), fb) << (31 ^ 24);\r
337 ret |= lfsr_rollback_bit(s, BEBIT(in, 30), fb) << (30 ^ 24);\r
338 ret |= lfsr_rollback_bit(s, BEBIT(in, 29), fb) << (29 ^ 24);\r
339 ret |= lfsr_rollback_bit(s, BEBIT(in, 28), fb) << (28 ^ 24);\r
340 ret |= lfsr_rollback_bit(s, BEBIT(in, 27), fb) << (27 ^ 24);\r
341 ret |= lfsr_rollback_bit(s, BEBIT(in, 26), fb) << (26 ^ 24);\r
342 ret |= lfsr_rollback_bit(s, BEBIT(in, 25), fb) << (25 ^ 24);\r
343 ret |= lfsr_rollback_bit(s, BEBIT(in, 24), fb) << (24 ^ 24);\r
344\r
345 ret |= lfsr_rollback_bit(s, BEBIT(in, 23), fb) << (23 ^ 24);\r
346 ret |= lfsr_rollback_bit(s, BEBIT(in, 22), fb) << (22 ^ 24);\r
347 ret |= lfsr_rollback_bit(s, BEBIT(in, 21), fb) << (21 ^ 24);\r
348 ret |= lfsr_rollback_bit(s, BEBIT(in, 20), fb) << (20 ^ 24);\r
349 ret |= lfsr_rollback_bit(s, BEBIT(in, 19), fb) << (19 ^ 24);\r
350 ret |= lfsr_rollback_bit(s, BEBIT(in, 18), fb) << (18 ^ 24);\r
351 ret |= lfsr_rollback_bit(s, BEBIT(in, 17), fb) << (17 ^ 24);\r
352 ret |= lfsr_rollback_bit(s, BEBIT(in, 16), fb) << (16 ^ 24);\r
353 \r
354 ret |= lfsr_rollback_bit(s, BEBIT(in, 15), fb) << (15 ^ 24);\r
355 ret |= lfsr_rollback_bit(s, BEBIT(in, 14), fb) << (14 ^ 24);\r
356 ret |= lfsr_rollback_bit(s, BEBIT(in, 13), fb) << (13 ^ 24);\r
357 ret |= lfsr_rollback_bit(s, BEBIT(in, 12), fb) << (12 ^ 24);\r
358 ret |= lfsr_rollback_bit(s, BEBIT(in, 11), fb) << (11 ^ 24);\r
359 ret |= lfsr_rollback_bit(s, BEBIT(in, 10), fb) << (10 ^ 24);\r
360 ret |= lfsr_rollback_bit(s, BEBIT(in, 9), fb) << (9 ^ 24);\r
361 ret |= lfsr_rollback_bit(s, BEBIT(in, 8), fb) << (8 ^ 24);\r
362 \r
363 ret |= lfsr_rollback_bit(s, BEBIT(in, 7), fb) << (7 ^ 24);\r
364 ret |= lfsr_rollback_bit(s, BEBIT(in, 6), fb) << (6 ^ 24);\r
365 ret |= lfsr_rollback_bit(s, BEBIT(in, 5), fb) << (5 ^ 24);\r
366 ret |= lfsr_rollback_bit(s, BEBIT(in, 4), fb) << (4 ^ 24);\r
367 ret |= lfsr_rollback_bit(s, BEBIT(in, 3), fb) << (3 ^ 24);\r
368 ret |= lfsr_rollback_bit(s, BEBIT(in, 2), fb) << (2 ^ 24);\r
369 ret |= lfsr_rollback_bit(s, BEBIT(in, 1), fb) << (1 ^ 24);\r
370 ret |= lfsr_rollback_bit(s, BEBIT(in, 0), fb) << (0 ^ 24);\r
371 return ret;\r
f89c7050
M		 372}\r
373\r
374/** nonce_distance\r
375 * x,y valid tag nonces, then prng_successor(x, nonce_distance(x, y)) = y\r
376 */\r
377static uint16_t *dist = 0;\r
378int nonce_distance(uint32_t from, uint32_t to)\r
379{\r
380 uint16_t x, i;\r
381 if(!dist) {\r
382 dist = malloc(2 << 16);\r
383 if(!dist)\r
384 return -1;\r
385 for (x = i = 1; i; ++i) {\r
386 dist[(x & 0xff) << 8 | x >> 8] = i;\r
387 x = x >> 1 | (x ^ x >> 2 ^ x >> 3 ^ x >> 5) << 15;\r
388 }\r
389 }\r
390 return (65535 + dist[to >> 16] - dist[from >> 16]) % 65535;\r
391}\r
392\r
393\r
394static uint32_t fastfwd[2][8] = {\r
395 { 0, 0x4BC53, 0xECB1, 0x450E2, 0x25E29, 0x6E27A, 0x2B298, 0x60ECB},\r
396 { 0, 0x1D962, 0x4BC53, 0x56531, 0xECB1, 0x135D3, 0x450E2, 0x58980}};\r
397\r
398\r
399/** lfsr_prefix_ks\r
400 *\r
401 * Is an exported helper function from the common prefix attack\r
402 * Described in the "dark side" paper. It returns an -1 terminated array\r
403 * of possible partial(21 bit) secret state.\r
404 * The required keystream(ks) needs to contain the keystream that was used to\r
a0f33b66 405 * encrypt the NACK which is observed when varying only the 3 last bits of Nr\r
f89c7050
M		 406 * only correct iff [NR_3] ^ NR_3 does not depend on Nr_3\r
407 */\r
408uint32_t *lfsr_prefix_ks(uint8_t ks[8], int isodd)\r
409{\r
a0f33b66 410 uint32_t *candidates = malloc(4 << 10);\r
411 if(!candidates) return 0;\r
412 \r
f89c7050 413 uint32_t c, entry;\r
a0f33b66 414 int size = 0, i, good;\r
f89c7050 415\r
a0f33b66 416 for(i = 0; i < 1 << 21; ++i) {\r
417 for(c = 0, good = 1; good && c < 8; ++c) {\r
418 entry = i ^ fastfwd[isodd][c];\r
419 good &= (BIT(ks[c], isodd) == filter(entry >> 1));\r
420 good &= (BIT(ks[c], isodd + 2) == filter(entry));\r
f89c7050 421 }\r
a0f33b66 422 if(good)\r
423 candidates[size++] = i;\r
424 }\r
f89c7050 425\r
a0f33b66 426 candidates[size] = -1;\r
f89c7050
M		 427\r
428 return candidates;\r
429}\r
430\r
a0f33b66 431/** check_pfx_parity\r
f89c7050
M		 432 * helper function which eliminates possible secret states using parity bits\r
433 */\r
a0f33b66 434static 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 435{\r
a0f33b66 436 uint32_t ks1, nr, ks2, rr, ks3, c, good = 1;\r
f89c7050 437\r
a0f33b66 438 for(c = 0; good && c < 8; ++c) {\r
439 sl->odd = odd ^ fastfwd[1][c];\r
440 sl->even = even ^ fastfwd[0][c];\r
9cefee6f 441\r
a0f33b66 442 lfsr_rollback_bit(sl, 0, 0);\r
443 lfsr_rollback_bit(sl, 0, 0);\r
9cefee6f 444\r
a0f33b66 445 ks3 = lfsr_rollback_bit(sl, 0, 0);\r
446 ks2 = lfsr_rollback_word(sl, 0, 0);\r
447 ks1 = lfsr_rollback_word(sl, prefix | c << 5, 1);\r
9cefee6f 448\r
f89c7050
M		 449 nr = ks1 ^ (prefix | c << 5);\r
450 rr = ks2 ^ rresp;\r
451\r
f89c7050
M		 452 good &= parity(nr & 0x000000ff) ^ parities[c][3] ^ BIT(ks2, 24);\r
453 good &= parity(rr & 0xff000000) ^ parities[c][4] ^ BIT(ks2, 16);\r
454 good &= parity(rr & 0x00ff0000) ^ parities[c][5] ^ BIT(ks2, 8);\r
455 good &= parity(rr & 0x0000ff00) ^ parities[c][6] ^ BIT(ks2, 0);\r
a0f33b66 456 good &= parity(rr & 0x000000ff) ^ parities[c][7] ^ ks3;\r
f89c7050
M		 457 }\r
458\r
a0f33b66 459 return sl + good;\r
9cefee6f 460}\r
f89c7050 461\r
f89c7050
M		 462/** lfsr_common_prefix\r
463 * Implentation of the common prefix attack.\r
464 * Requires the 28 bit constant prefix used as reader nonce (pfx)\r
465 * The reader response used (rr)\r
466 * The keystream used to encrypt the observed NACK's (ks)\r
467 * The parity bits (par)\r
468 * It returns a zero terminated list of possible cipher states after the\r
469 * tag nonce was fed in\r
470 */\r
a0f33b66 471\r
472struct Crypto1State* lfsr_common_prefix(uint32_t pfx, uint32_t rr, uint8_t ks[8], uint8_t par[8][8])\r
f89c7050
M		 473{\r
474 struct Crypto1State *statelist, *s;\r
475 uint32_t *odd, *even, *o, *e, top;\r
476\r
477 odd = lfsr_prefix_ks(ks, 1);\r
478 even = lfsr_prefix_ks(ks, 0);\r
479\r
8130eba4 480 s = statelist = malloc((sizeof *statelist) << 21);\r
a0f33b66 481 if(!s || !odd || !even) {\r
bcf61bd3 482 free(statelist);\r
483 free(odd);\r
484 free(even);\r
485 return 0;\r
a61b4976 486 }\r
f89c7050 487\r
a0f33b66 488 for(o = odd; *o + 1; ++o)\r
489 for(e = even; *e + 1; ++e)\r
f89c7050 490 for(top = 0; top < 64; ++top) {\r
a0f33b66 491 *o += 1 << 21;\r
492 *e += (!(top & 7) + 1) << 21;\r
493 s = check_pfx_parity(pfx, rr, par, *o, *e, s);\r
f89c7050
M		 494 }\r
495\r
a0f33b66 496 s->odd = s->even = 0;\r
f89c7050
M		 497\r
498 free(odd);\r
499 free(even);\r
f89c7050 500 return statelist;\r
a0f33b66 501}
Proxmark3 GIT tracking
Impressum, Datenschutz