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