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