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