]> git.zerfleddert.de Git - proxmark3-svn/blob - tools/mfkey/crapto1.c
Merge remote-tracking branch 'upstream/master'
[proxmark3-svn] / tools / mfkey / crapto1.c
1 /* crapto1.c
2
3 This program is free software; you can redistribute it and/or
4 modify it under the terms of the GNU General Public License
5 as published by the Free Software Foundation; either version 2
6 of the License, or (at your option) any later version.
7
8 This program is distributed in the hope that it will be useful,
9 but WITHOUT ANY WARRANTY; without even the implied warranty of
10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 GNU General Public License for more details.
12
13 You should have received a copy of the GNU General Public License
14 along with this program; if not, write to the Free Software
15 Foundation, Inc., 51 Franklin Street, Fifth Floor,
16 Boston, MA 02110-1301, US$
17
18 Copyright (C) 2008-2008 bla <blapost@gmail.com>
19 */
20 #include "crapto1.h"
21 #include <stdlib.h>
22
23 #if !defined LOWMEM && defined __GNUC__
24 static uint8_t filterlut[1 << 20];
25 static void __attribute__((constructor)) fill_lut()
26 {
27 uint32_t i;
28 for(i = 0; i < 1 << 20; ++i)
29 filterlut[i] = filter(i);
30 }
31 #define filter(x) (filterlut[(x) & 0xfffff])
32 #endif
33
34 static void quicksort(uint32_t* const start, uint32_t* const stop)
35 {
36 uint32_t *it = start + 1, *rit = stop;
37
38 if(it > rit)
39 return;
40
41 while(it < rit)
42 if(*it <= *start)
43 ++it;
44 else if(*rit > *start)
45 --rit;
46 else
47 *it ^= (*it ^= *rit, *rit ^= *it);
48
49 if(*rit >= *start)
50 --rit;
51 if(rit != start)
52 *rit ^= (*rit ^= *start, *start ^= *rit);
53
54 quicksort(start, rit - 1);
55 quicksort(rit + 1, stop);
56 }
57 /** binsearch
58 * Binary search for the first occurence of *stop's MSB in sorted [start,stop]
59 */
60 static inline uint32_t* binsearch(uint32_t *start, uint32_t *stop)
61 {
62 uint32_t mid, val = *stop & 0xff000000;
63 while(start != stop)
64 if(start[mid = (stop - start) >> 1] > val)
65 stop = &start[mid];
66 else
67 start += mid + 1;
68
69 return start;
70 }
71
72 /** update_contribution
73 * helper, calculates the partial linear feedback contributions and puts in MSB
74 */
75 static inline void
76 update_contribution(uint32_t *item, const uint32_t mask1, const uint32_t mask2)
77 {
78 uint32_t p = *item >> 25;
79
80 p = p << 1 | parity(*item & mask1);
81 p = p << 1 | parity(*item & mask2);
82 *item = p << 24 | (*item & 0xffffff);
83 }
84
85 /** extend_table
86 * using a bit of the keystream extend the table of possible lfsr states
87 */
88 static inline void
89 extend_table(uint32_t *tbl, uint32_t **end, int bit, int m1, int m2, uint32_t in)
90 {
91 in <<= 24;
92 for(*tbl <<= 1; tbl <= *end; *++tbl <<= 1)
93 if(filter(*tbl) ^ filter(*tbl | 1)) {
94 *tbl |= filter(*tbl) ^ bit;
95 update_contribution(tbl, m1, m2);
96 *tbl ^= in;
97 } else if(filter(*tbl) == bit) {
98 *++*end = tbl[1];
99 tbl[1] = tbl[0] | 1;
100 update_contribution(tbl, m1, m2);
101 *tbl++ ^= in;
102 update_contribution(tbl, m1, m2);
103 *tbl ^= in;
104 } else
105 *tbl-- = *(*end)--;
106 }
107 /** extend_table_simple
108 * using a bit of the keystream extend the table of possible lfsr states
109 */
110 static inline void extend_table_simple(uint32_t *tbl, uint32_t **end, int bit)
111 {
112 for(*tbl <<= 1; tbl <= *end; *++tbl <<= 1)
113 if(filter(*tbl) ^ filter(*tbl | 1))
114 *tbl |= filter(*tbl) ^ bit;
115 else if(filter(*tbl) == bit) {
116 *++*end = *++tbl;
117 *tbl = tbl[-1] | 1;
118 } else
119 *tbl-- = *(*end)--;
120 }
121 /** recover
122 * recursively narrow down the search space, 4 bits of keystream at a time
123 */
124 static struct Crypto1State*
125 recover(uint32_t *o_head, uint32_t *o_tail, uint32_t oks,
126 uint32_t *e_head, uint32_t *e_tail, uint32_t eks, int rem,
127 struct Crypto1State *sl, uint32_t in)
128 {
129 uint32_t *o, *e, i;
130
131 if(rem == -1) {
132 for(e = e_head; e <= e_tail; ++e) {
133 *e = *e << 1 ^ parity(*e & LF_POLY_EVEN) ^ !!(in & 4);
134 for(o = o_head; o <= o_tail; ++o, ++sl) {
135 sl->even = *o;
136 sl->odd = *e ^ parity(*o & LF_POLY_ODD);
137 sl[1].odd = sl[1].even = 0;
138 }
139 }
140 return sl;
141 }
142
143 for(i = 0; i < 4 && rem--; i++) {
144 oks >>= 1;
145 eks >>= 1;
146 in >>= 2;
147 extend_table(o_head, &o_tail, oks & 1, LF_POLY_EVEN << 1 | 1,
148 LF_POLY_ODD << 1, 0);
149 if(o_head > o_tail)
150 return sl;
151
152 extend_table(e_head, &e_tail, eks & 1, LF_POLY_ODD,
153 LF_POLY_EVEN << 1 | 1, in & 3);
154 if(e_head > e_tail)
155 return sl;
156 }
157
158 quicksort(o_head, o_tail);
159 quicksort(e_head, e_tail);
160
161 while(o_tail >= o_head && e_tail >= e_head)
162 if(((*o_tail ^ *e_tail) >> 24) == 0) {
163 o_tail = binsearch(o_head, o = o_tail);
164 e_tail = binsearch(e_head, e = e_tail);
165 sl = recover(o_tail--, o, oks,
166 e_tail--, e, eks, rem, sl, in);
167 }
168 else if(*o_tail > *e_tail)
169 o_tail = binsearch(o_head, o_tail) - 1;
170 else
171 e_tail = binsearch(e_head, e_tail) - 1;
172
173 return sl;
174 }
175 /** lfsr_recovery
176 * recover the state of the lfsr given 32 bits of the keystream
177 * additionally you can use the in parameter to specify the value
178 * that was fed into the lfsr at the time the keystream was generated
179 */
180 struct Crypto1State* lfsr_recovery32(uint32_t ks2, uint32_t in)
181 {
182 struct Crypto1State *statelist;
183 uint32_t *odd_head = 0, *odd_tail = 0, oks = 0;
184 uint32_t *even_head = 0, *even_tail = 0, eks = 0;
185 int i;
186
187 for(i = 31; i >= 0; i -= 2)
188 oks = oks << 1 | BEBIT(ks2, i);
189 for(i = 30; i >= 0; i -= 2)
190 eks = eks << 1 | BEBIT(ks2, i);
191
192 odd_head = odd_tail = malloc(sizeof(uint32_t) << 21);
193 even_head = even_tail = malloc(sizeof(uint32_t) << 21);
194 statelist = malloc(sizeof(struct Crypto1State) << 18);
195 if(!odd_tail-- || !even_tail-- || !statelist) {
196 free(statelist);
197 statelist = 0;
198 goto out;
199 }
200
201 statelist->odd = statelist->even = 0;
202
203 for(i = 1 << 20; i >= 0; --i) {
204 if(filter(i) == (oks & 1))
205 *++odd_tail = i;
206 if(filter(i) == (eks & 1))
207 *++even_tail = i;
208 }
209
210 for(i = 0; i < 4; i++) {
211 extend_table_simple(odd_head, &odd_tail, (oks >>= 1) & 1);
212 extend_table_simple(even_head, &even_tail, (eks >>= 1) & 1);
213 }
214
215 in = (in >> 16 & 0xff) | (in << 16) | (in & 0xff00);
216 recover(odd_head, odd_tail, oks,
217 even_head, even_tail, eks, 11, statelist, in << 1);
218
219 out:
220 free(odd_head);
221 free(even_head);
222 return statelist;
223 }
224
225 static const uint32_t S1[] = { 0x62141, 0x310A0, 0x18850, 0x0C428, 0x06214,
226 0x0310A, 0x85E30, 0xC69AD, 0x634D6, 0xB5CDE, 0xDE8DA, 0x6F46D, 0xB3C83,
227 0x59E41, 0xA8995, 0xD027F, 0x6813F, 0x3409F, 0x9E6FA};
228 static const uint32_t S2[] = { 0x3A557B00, 0x5D2ABD80, 0x2E955EC0, 0x174AAF60,
229 0x0BA557B0, 0x05D2ABD8, 0x0449DE68, 0x048464B0, 0x42423258, 0x278192A8,
230 0x156042D0, 0x0AB02168, 0x43F89B30, 0x61FC4D98, 0x765EAD48, 0x7D8FDD20,
231 0x7EC7EE90, 0x7F63F748, 0x79117020};
232 static const uint32_t T1[] = {
233 0x4F37D, 0x279BE, 0x97A6A, 0x4BD35, 0x25E9A, 0x12F4D, 0x097A6, 0x80D66,
234 0xC4006, 0x62003, 0xB56B4, 0x5AB5A, 0xA9318, 0xD0F39, 0x6879C, 0xB057B,
235 0x582BD, 0x2C15E, 0x160AF, 0x8F6E2, 0xC3DC4, 0xE5857, 0x72C2B, 0x39615,
236 0x98DBF, 0xC806A, 0xE0680, 0x70340, 0x381A0, 0x98665, 0x4C332, 0xA272C};
237 static const uint32_t T2[] = { 0x3C88B810, 0x5E445C08, 0x2982A580, 0x14C152C0,
238 0x4A60A960, 0x253054B0, 0x52982A58, 0x2FEC9EA8, 0x1156C4D0, 0x08AB6268,
239 0x42F53AB0, 0x217A9D58, 0x161DC528, 0x0DAE6910, 0x46D73488, 0x25CB11C0,
240 0x52E588E0, 0x6972C470, 0x34B96238, 0x5CFC3A98, 0x28DE96C8, 0x12CFC0E0,
241 0x4967E070, 0x64B3F038, 0x74F97398, 0x7CDC3248, 0x38CE92A0, 0x1C674950,
242 0x0E33A4A8, 0x01B959D0, 0x40DCACE8, 0x26CEDDF0};
243 static const uint32_t C1[] = { 0x846B5, 0x4235A, 0x211AD};
244 static const uint32_t C2[] = { 0x1A822E0, 0x21A822E0, 0x21A822E0};
245 /** Reverse 64 bits of keystream into possible cipher states
246 * Variation mentioned in the paper. Somewhat optimized version
247 */
248 struct Crypto1State* lfsr_recovery64(uint32_t ks2, uint32_t ks3)
249 {
250 struct Crypto1State *statelist, *sl;
251 uint8_t oks[32], eks[32], hi[32];
252 uint32_t low = 0, win = 0;
253 uint32_t *tail, table[1 << 16];
254 int i, j;
255
256 sl = statelist = malloc(sizeof(struct Crypto1State) << 4);
257 if(!sl)
258 return 0;
259 sl->odd = sl->even = 0;
260
261 for(i = 30; i >= 0; i -= 2) {
262 oks[i >> 1] = BEBIT(ks2, i);
263 oks[16 + (i >> 1)] = BEBIT(ks3, i);
264 }
265 for(i = 31; i >= 0; i -= 2) {
266 eks[i >> 1] = BEBIT(ks2, i);
267 eks[16 + (i >> 1)] = BEBIT(ks3, i);
268 }
269
270 for(i = 0xfffff; i >= 0; --i) {
271 if (filter(i) != oks[0])
272 continue;
273
274 *(tail = table) = i;
275 for(j = 1; tail >= table && j < 29; ++j)
276 extend_table_simple(table, &tail, oks[j]);
277
278 if(tail < table)
279 continue;
280
281 for(j = 0; j < 19; ++j)
282 low = low << 1 | parity(i & S1[j]);
283 for(j = 0; j < 32; ++j)
284 hi[j] = parity(i & T1[j]);
285
286 for(; tail >= table; --tail) {
287 for(j = 0; j < 3; ++j) {
288 *tail = *tail << 1;
289 *tail |= parity((i & C1[j]) ^ (*tail & C2[j]));
290 if(filter(*tail) != oks[29 + j])
291 goto continue2;
292 }
293
294 for(j = 0; j < 19; ++j)
295 win = win << 1 | parity(*tail & S2[j]);
296
297 win ^= low;
298 for(j = 0; j < 32; ++j) {
299 win = win << 1 ^ hi[j] ^ parity(*tail & T2[j]);
300 if(filter(win) != eks[j])
301 goto continue2;
302 }
303
304 *tail = *tail << 1 | parity(LF_POLY_EVEN & *tail);
305 sl->odd = *tail ^ parity(LF_POLY_ODD & win);
306 sl->even = win;
307 ++sl;
308 sl->odd = sl->even = 0;
309 continue2:;
310 }
311 }
312 return statelist;
313 }
314
315 /** lfsr_rollback_bit
316 * Rollback the shift register in order to get previous states
317 */
318 uint8_t lfsr_rollback_bit(struct Crypto1State *s, uint32_t in, int fb)
319 {
320 int out;
321 uint8_t ret;
322
323 s->odd &= 0xffffff;
324 s->odd ^= (s->odd ^= s->even, s->even ^= s->odd);
325
326 out = s->even & 1;
327 out ^= LF_POLY_EVEN & (s->even >>= 1);
328 out ^= LF_POLY_ODD & s->odd;
329 out ^= !!in;
330 out ^= (ret = filter(s->odd)) & !!fb;
331
332 s->even |= parity(out) << 23;
333 return ret;
334 }
335 /** lfsr_rollback_byte
336 * Rollback the shift register in order to get previous states
337 */
338 uint8_t lfsr_rollback_byte(struct Crypto1State *s, uint32_t in, int fb)
339 {
340 int i, ret = 0;
341 for (i = 7; i >= 0; --i)
342 ret |= lfsr_rollback_bit(s, BIT(in, i), fb) << i;
343 return ret;
344 }
345 /** lfsr_rollback_word
346 * Rollback the shift register in order to get previous states
347 */
348 uint32_t lfsr_rollback_word(struct Crypto1State *s, uint32_t in, int fb)
349 {
350 int i;
351 uint32_t ret = 0;
352 for (i = 31; i >= 0; --i)
353 ret |= lfsr_rollback_bit(s, BEBIT(in, i), fb) << (i ^ 24);
354 return ret;
355 }
356
357 /** nonce_distance
358 * x,y valid tag nonces, then prng_successor(x, nonce_distance(x, y)) = y
359 */
360 static uint16_t *dist = 0;
361 int nonce_distance(uint32_t from, uint32_t to)
362 {
363 uint16_t x, i;
364 if(!dist) {
365 dist = malloc(2 << 16);
366 if(!dist)
367 return -1;
368 for (x = i = 1; i; ++i) {
369 dist[(x & 0xff) << 8 | x >> 8] = i;
370 x = x >> 1 | (x ^ x >> 2 ^ x >> 3 ^ x >> 5) << 15;
371 }
372 }
373 return (65535 + dist[to >> 16] - dist[from >> 16]) % 65535;
374 }
375
376
377 static uint32_t fastfwd[2][8] = {
378 { 0, 0x4BC53, 0xECB1, 0x450E2, 0x25E29, 0x6E27A, 0x2B298, 0x60ECB},
379 { 0, 0x1D962, 0x4BC53, 0x56531, 0xECB1, 0x135D3, 0x450E2, 0x58980}};
380 /** lfsr_prefix_ks
381 *
382 * Is an exported helper function from the common prefix attack
383 * Described in the "dark side" paper. It returns an -1 terminated array
384 * of possible partial(21 bit) secret state.
385 * The required keystream(ks) needs to contain the keystream that was used to
386 * encrypt the NACK which is observed when varying only the 3 last bits of Nr
387 * only correct iff [NR_3] ^ NR_3 does not depend on Nr_3
388 */
389 uint32_t *lfsr_prefix_ks(uint8_t ks[8], int isodd)
390 {
391 uint32_t c, entry, *candidates = malloc(4 << 10);
392 int i, size = 0, good;
393
394 if(!candidates)
395 return 0;
396
397 for(i = 0; i < 1 << 21; ++i) {
398 for(c = 0, good = 1; good && c < 8; ++c) {
399 entry = i ^ fastfwd[isodd][c];
400 good &= (BIT(ks[c], isodd) == filter(entry >> 1));
401 good &= (BIT(ks[c], isodd + 2) == filter(entry));
402 }
403 if(good)
404 candidates[size++] = i;
405 }
406
407 candidates[size] = -1;
408
409 return candidates;
410 }
411
412 /** check_pfx_parity
413 * helper function which eliminates possible secret states using parity bits
414 */
415 static struct Crypto1State*
416 check_pfx_parity(uint32_t prefix, uint32_t rresp, uint8_t parities[8][8],
417 uint32_t odd, uint32_t even, struct Crypto1State* sl)
418 {
419 uint32_t ks1, nr, ks2, rr, ks3, c, good = 1;
420
421 for(c = 0; good && c < 8; ++c) {
422 sl->odd = odd ^ fastfwd[1][c];
423 sl->even = even ^ fastfwd[0][c];
424
425 lfsr_rollback_bit(sl, 0, 0);
426 lfsr_rollback_bit(sl, 0, 0);
427
428 ks3 = lfsr_rollback_bit(sl, 0, 0);
429 ks2 = lfsr_rollback_word(sl, 0, 0);
430 ks1 = lfsr_rollback_word(sl, prefix | c << 5, 1);
431
432 nr = ks1 ^ (prefix | c << 5);
433 rr = ks2 ^ rresp;
434
435 good &= parity(nr & 0x000000ff) ^ parities[c][3] ^ BIT(ks2, 24);
436 good &= parity(rr & 0xff000000) ^ parities[c][4] ^ BIT(ks2, 16);
437 good &= parity(rr & 0x00ff0000) ^ parities[c][5] ^ BIT(ks2, 8);
438 good &= parity(rr & 0x0000ff00) ^ parities[c][6] ^ BIT(ks2, 0);
439 good &= parity(rr & 0x000000ff) ^ parities[c][7] ^ ks3;
440 }
441
442 return sl + good;
443 }
444
445
446 /** lfsr_common_prefix
447 * Implentation of the common prefix attack.
448 */
449 struct Crypto1State*
450 lfsr_common_prefix(uint32_t pfx, uint32_t rr, uint8_t ks[8], uint8_t par[8][8])
451 {
452 struct Crypto1State *statelist, *s;
453 uint32_t *odd, *even, *o, *e, top;
454
455 odd = lfsr_prefix_ks(ks, 1);
456 even = lfsr_prefix_ks(ks, 0);
457
458 s = statelist = malloc((sizeof *statelist) << 20);
459 if(!s || !odd || !even) {
460 free(statelist);
461 statelist = 0;
462 goto out;
463 }
464
465 for(o = odd; *o + 1; ++o)
466 for(e = even; *e + 1; ++e)
467 for(top = 0; top < 64; ++top) {
468 *o += 1 << 21;
469 *e += (!(top & 7) + 1) << 21;
470 s = check_pfx_parity(pfx, rr, par, *o, *e, s);
471 }
472
473 s->odd = s->even = 0;
474 out:
475 free(odd);
476 free(even);
477 return statelist;
478 }
Impressum, Datenschutz