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