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