]> git.zerfleddert.de Git - proxmark3-svn/blame - common/crapto1/crapto1.c
Split data askgproxiidemod to own file
[proxmark3-svn] / common / crapto1 / crapto1.c
CommitLineData
33443e7c 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
0ca9bc0e 18 Copyright (C) 2008-2014 bla <blapost@gmail.com>
33443e7c 19*/
20#include "crapto1.h"
21#include <stdlib.h>
33443e7c 22
23#if !defined LOWMEM && defined __GNUC__
24static uint8_t filterlut[1 << 20];
25static 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
36typedef struct bucket {
37 uint32_t *head;
38 uint32_t *bp;
39} bucket_t;
40
41typedef bucket_t bucket_array_t[2][0x100];
42
43typedef 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
51static 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}
33443e7c 97/** binsearch
98 * Binary search for the first occurence of *stop's MSB in sorted [start,stop]
99 */
0ca9bc0e 100static inline uint32_t* binsearch(uint32_t *start, uint32_t *stop)
33443e7c 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 */
115static inline void
116update_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 */
128static inline void
129extend_table(uint32_t *tbl, uint32_t **end, int bit, int m1, int m2, uint32_t in)
130{
131 in <<= 24;
0ca9bc0e 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)--;
33443e7c 146}
33443e7c 147/** extend_table_simple
148 * using a bit of the keystream extend the table of possible lfsr states
149 */
0ca9bc0e 150static inline void extend_table_simple(uint32_t *tbl, uint32_t **end, int bit)
33443e7c 151{
152 for(*tbl <<= 1; tbl <= *end; *++tbl <<= 1)
0ca9bc0e 153 if(filter(*tbl) ^ filter(*tbl | 1))
33443e7c 154 *tbl |= filter(*tbl) ^ bit;
0ca9bc0e 155 else if(filter(*tbl) == bit) {
33443e7c 156 *++*end = *++tbl;
157 *tbl = tbl[-1] | 1;
0ca9bc0e 158
159 } else
33443e7c 160 *tbl-- = *(*end)--;
161}
162
163
164/** recover
165 * recursively narrow down the search space, 4 bits of keystream at a time
166 */
167static struct Crypto1State*
168recover(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{
0ca9bc0e 172 uint32_t *o, *e, i;
33443e7c 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);
0ca9bc0e 181 sl[1].odd = sl[1].even = 0;
33443e7c 182 }
183 }
33443e7c 184 return sl;
185 }
186
0ca9bc0e 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);
33443e7c 193 if(o_head > o_tail)
194 return sl;
195
0ca9bc0e 196 extend_table(e_head, &e_tail, eks & 1, LF_POLY_ODD,
197 LF_POLY_EVEN << 1 | 1, in & 3);
33443e7c 198 if(e_head > e_tail)
199 return sl;
200 }
33443e7c 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 */
216struct 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
33443e7c 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) {
0ca9bc0e 232 free(statelist);
233 statelist = 0;
33443e7c 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
33443e7c 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
33443e7c 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
0ca9bc0e 261 in = (in >> 16 & 0xff) | (in << 16) | (in & 0xff00);
33443e7c 262 recover(odd_head, odd_tail, oks,
263 even_head, even_tail, eks, 11, statelist, in << 1, bucket);
264
33443e7c 265out:
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
275static 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};
278static 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};
282static 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};
287static 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};
293static const uint32_t C1[] = { 0x846B5, 0x4235A, 0x211AD};
294static 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 */
298struct 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) {
0ca9bc0e 312 oks[i >> 1] = BEBIT(ks2, i);
313 oks[16 + (i >> 1)] = BEBIT(ks3, i);
33443e7c 314 }
315 for(i = 31; i >= 0; i -= 2) {
0ca9bc0e 316 eks[i >> 1] = BEBIT(ks2, i);
317 eks[16 + (i >> 1)] = BEBIT(ks3, i);
33443e7c 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 */
0ca9bc0e 368uint8_t lfsr_rollback_bit(struct Crypto1State *s, uint32_t in, int fb)
33443e7c 369{
370 int out;
0ca9bc0e 371 uint8_t ret;
372 uint32_t t;
373
33443e7c 374 s->odd &= 0xffffff;
0ca9bc0e 375 t = s->odd, s->odd = s->even, s->even = t;
33443e7c 376
377 out = s->even & 1;
378 out ^= LF_POLY_EVEN & (s->even >>= 1);
379 out ^= LF_POLY_ODD & s->odd;
380 out ^= !!in;
0ca9bc0e 381 out ^= (ret = filter(s->odd)) & !!fb;
33443e7c 382
383 s->even |= parity(out) << 23;
0ca9bc0e 384 return ret;
33443e7c 385}
386/** lfsr_rollback_byte
387 * Rollback the shift register in order to get previous states
388 */
0ca9bc0e 389uint8_t lfsr_rollback_byte(struct Crypto1State *s, uint32_t in, int fb)
33443e7c 390{
0ca9bc0e 391 int i, ret=0;
33443e7c 392 for (i = 7; i >= 0; --i)
0ca9bc0e 393 ret |= lfsr_rollback_bit(s, BIT(in, i), fb) << i;
394 return ret;
33443e7c 395}
396/** lfsr_rollback_word
397 * Rollback the shift register in order to get previous states
398 */
0ca9bc0e 399uint32_t lfsr_rollback_word(struct Crypto1State *s, uint32_t in, int fb)
33443e7c 400{
401 int i;
0ca9bc0e 402 uint32_t ret = 0;
33443e7c 403 for (i = 31; i >= 0; --i)
0ca9bc0e 404 ret |= lfsr_rollback_bit(s, BEBIT(in, i), fb) << (i ^ 24);
405 return ret;
33443e7c 406}
407
408/** nonce_distance
409 * x,y valid tag nonces, then prng_successor(x, nonce_distance(x, y)) = y
410 */
411static uint16_t *dist = 0;
412int 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
428static uint32_t fastfwd[2][8] = {
429 { 0, 0x4BC53, 0xECB1, 0x450E2, 0x25E29, 0x6E27A, 0x2B298, 0x60ECB},
430 { 0, 0x1D962, 0x4BC53, 0x56531, 0xECB1, 0x135D3, 0x450E2, 0x58980}};
33443e7c 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
0ca9bc0e 437 * encrypt the NACK which is observed when varying only the 3 last bits of Nr
33443e7c 438 * only correct iff [NR_3] ^ NR_3 does not depend on Nr_3
439 */
440uint32_t *lfsr_prefix_ks(uint8_t ks[8], int isodd)
441{
0ca9bc0e 442 uint32_t c, entry, *candidates = malloc(4 << 10);
443 int i, size = 0, good;
444
33443e7c 445 if(!candidates)
446 return 0;
447
0ca9bc0e 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));
33443e7c 453 }
0ca9bc0e 454 if(good)
455 candidates[size++] = i;
456 }
457
458 candidates[size] = -1;
33443e7c 459
460 return candidates;
461}
462
0ca9bc0e 463/** check_pfx_parity
33443e7c 464 * helper function which eliminates possible secret states using parity bits
465 */
466static struct Crypto1State*
0ca9bc0e 467check_pfx_parity(uint32_t prefix, uint32_t rresp, uint8_t parities[8][8],
de867f50 468 uint32_t odd, uint32_t even, struct Crypto1State* sl, uint32_t no_par)
33443e7c 469{
de867f50 470 uint32_t ks1, nr, ks2, rr, ks3, c, good = 1;
33443e7c 471
0ca9bc0e 472 for(c = 0; good && c < 8; ++c) {
473 sl->odd = odd ^ fastfwd[1][c];
474 sl->even = even ^ fastfwd[0][c];
33443e7c 475
0ca9bc0e 476 lfsr_rollback_bit(sl, 0, 0);
477 lfsr_rollback_bit(sl, 0, 0);
33443e7c 478
0ca9bc0e 479 ks3 = lfsr_rollback_bit(sl, 0, 0);
480 ks2 = lfsr_rollback_word(sl, 0, 0);
481 ks1 = lfsr_rollback_word(sl, prefix | c << 5, 1);
33443e7c 482
483 if (no_par)
484 break;
485
33443e7c 486 nr = ks1 ^ (prefix | c << 5);
487 rr = ks2 ^ rresp;
488
33443e7c 489 good &= parity(nr & 0x000000ff) ^ parities[c][3] ^ BIT(ks2, 24);
490 good &= parity(rr & 0xff000000) ^ parities[c][4] ^ BIT(ks2, 16);
491 good &= parity(rr & 0x00ff0000) ^ parities[c][5] ^ BIT(ks2, 8);
492 good &= parity(rr & 0x0000ff00) ^ parities[c][6] ^ BIT(ks2, 0);
0ca9bc0e 493 good &= parity(rr & 0x000000ff) ^ parities[c][7] ^ ks3;
33443e7c 494 }
495
0ca9bc0e 496 return sl + good;
33443e7c 497}
498
499
500/** lfsr_common_prefix
501 * Implentation of the common prefix attack.
33443e7c 502 */
503struct Crypto1State*
de867f50 504lfsr_common_prefix(uint32_t pfx, uint32_t rr, uint8_t ks[8], uint8_t par[8][8], uint32_t no_par)
33443e7c 505{
506 struct Crypto1State *statelist, *s;
507 uint32_t *odd, *even, *o, *e, top;
508
509 odd = lfsr_prefix_ks(ks, 1);
510 even = lfsr_prefix_ks(ks, 0);
511
7779d73c 512 s = statelist = malloc((sizeof *statelist) << 22); // was << 20. Need more for no_par special attack. Enough???
0ca9bc0e 513 if(!s || !odd || !even) {
514 free(statelist);
515 statelist = 0;
516 goto out;
33443e7c 517 }
518
0ca9bc0e 519 for(o = odd; *o + 1; ++o)
520 for(e = even; *e + 1; ++e)
33443e7c 521 for(top = 0; top < 64; ++top) {
0ca9bc0e 522 *o += 1 << 21;
523 *e += (!(top & 7) + 1) << 21;
de867f50 524 s = check_pfx_parity(pfx, rr, par, *o, *e, s, no_par);
33443e7c 525 }
526
0ca9bc0e 527 s->odd = s->even = 0;
528out:
33443e7c 529 free(odd);
530 free(even);
33443e7c 531 return statelist;
532}
Impressum, Datenschutz