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