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