]>
cvs.zerfleddert.de Git - proxmark3-svn/blob - armsrc/crapto1.c
bcd3117114147a5287eb6c0d694f21abb239d501
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.
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.
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$
18 Copyright (C) 2008-2008 bla <blapost@gmail.com>
23 #if !defined LOWMEM && defined __GNUC__
24 static uint8_t filterlut
[1 << 20];
25 static void __attribute__((constructor
)) fill_lut()
28 for(i
= 0; i
< 1 << 20; ++i
)
29 filterlut
[i
] = filter(i
);
31 #define filter(x) (filterlut[(x) & 0xfffff])
34 static void quicksort(uint32_t* const start
, uint32_t* const stop
)
36 uint32_t *it
= start
+ 1, *rit
= stop
;
45 else if(*rit
> *start
)
61 quicksort(start
, rit
- 1);
62 quicksort(rit
+ 1, stop
);
65 * Binary search for the first occurence of *stop's MSB in sorted [start,stop]
67 static inline uint32_t* binsearch(uint32_t *start
, uint32_t *stop
)
69 uint32_t mid
, val
= *stop
& 0xff000000;
71 if(start
[mid
= (stop
- start
) >> 1] > val
)
79 /** update_contribution
80 * helper, calculates the partial linear feedback contributions and puts in MSB
83 update_contribution(uint32_t *item
, const uint32_t mask1
, const uint32_t mask2
)
85 uint32_t p
= *item
>> 25;
87 p
= p
<< 1 | parity(*item
& mask1
);
88 p
= p
<< 1 | parity(*item
& mask2
);
89 *item
= p
<< 24 | (*item
& 0xffffff);
93 * using a bit of the keystream extend the table of possible lfsr states
96 extend_table(uint32_t *tbl
, uint32_t **end
, int bit
, int m1
, int m2
, uint32_t in
)
99 for(*tbl
<<= 1; tbl
<= *end
; *++tbl
<<= 1)
100 if(filter(*tbl
) ^ filter(*tbl
| 1)) {
101 *tbl
|= filter(*tbl
) ^ bit
;
102 update_contribution(tbl
, m1
, m2
);
104 } else if(filter(*tbl
) == bit
) {
107 update_contribution(tbl
, m1
, m2
);
109 update_contribution(tbl
, m1
, m2
);
114 /** extend_table_simple
115 * using a bit of the keystream extend the table of possible lfsr states
117 static inline void extend_table_simple(uint32_t *tbl
, uint32_t **end
, int bit
)
119 for(*tbl
<<= 1; tbl
<= *end
; *++tbl
<<= 1)
120 if(filter(*tbl
) ^ filter(*tbl
| 1))
121 *tbl
|= filter(*tbl
) ^ bit
;
122 else if(filter(*tbl
) == bit
) {
129 * recursively narrow down the search space, 4 bits of keystream at a time
131 static struct Crypto1State
*
132 recover(uint32_t *o_head
, uint32_t *o_tail
, uint32_t oks
,
133 uint32_t *e_head
, uint32_t *e_tail
, uint32_t eks
, int rem
,
134 struct Crypto1State
*sl
, uint32_t in
)
139 for(e
= e_head
; e
<= e_tail
; ++e
) {
140 *e
= *e
<< 1 ^ parity(*e
& LF_POLY_EVEN
) ^ !!(in
& 4);
141 for(o
= o_head
; o
<= o_tail
; ++o
, ++sl
) {
143 sl
->odd
= *e
^ parity(*o
& LF_POLY_ODD
);
144 sl
[1].odd
= sl
[1].even
= 0;
150 for(i
= 0; i
< 4 && rem
--; i
++) {
154 extend_table(o_head
, &o_tail
, oks
& 1, LF_POLY_EVEN
<< 1 | 1,
155 LF_POLY_ODD
<< 1, 0);
159 extend_table(e_head
, &e_tail
, eks
& 1, LF_POLY_ODD
,
160 LF_POLY_EVEN
<< 1 | 1, in
& 3);
165 quicksort(o_head
, o_tail
);
166 quicksort(e_head
, e_tail
);
168 while(o_tail
>= o_head
&& e_tail
>= e_head
)
169 if(((*o_tail
^ *e_tail
) >> 24) == 0) {
170 o_tail
= binsearch(o_head
, o
= o_tail
);
171 e_tail
= binsearch(e_head
, e
= e_tail
);
172 sl
= recover(o_tail
--, o
, oks
,
173 e_tail
--, e
, eks
, rem
, sl
, in
);
175 else if(*o_tail
> *e_tail
)
176 o_tail
= binsearch(o_head
, o_tail
) - 1;
178 e_tail
= binsearch(e_head
, e_tail
) - 1;
183 * recover the state of the lfsr given 32 bits of the keystream
184 * additionally you can use the in parameter to specify the value
185 * that was fed into the lfsr at the time the keystream was generated
187 struct Crypto1State
* lfsr_recovery32(uint32_t ks2
, uint32_t in
)
189 struct Crypto1State
*statelist
;
190 uint32_t *odd_head
= 0, *odd_tail
= 0, oks
= 0;
191 uint32_t *even_head
= 0, *even_tail
= 0, eks
= 0;
194 for(i
= 31; i
>= 0; i
-= 2)
195 oks
= oks
<< 1 | BEBIT(ks2
, i
);
196 for(i
= 30; i
>= 0; i
-= 2)
197 eks
= eks
<< 1 | BEBIT(ks2
, i
);
199 odd_head
= odd_tail
= malloc(sizeof(uint32_t) << 21);
200 even_head
= even_tail
= malloc(sizeof(uint32_t) << 21);
201 statelist
= malloc(sizeof(struct Crypto1State
) << 18);
202 if(!odd_tail
-- || !even_tail
-- || !statelist
) {
208 statelist
->odd
= statelist
->even
= 0;
210 for(i
= 1 << 20; i
>= 0; --i
) {
211 if(filter(i
) == (oks
& 1))
213 if(filter(i
) == (eks
& 1))
217 for(i
= 0; i
< 4; i
++) {
218 extend_table_simple(odd_head
, &odd_tail
, (oks
>>= 1) & 1);
219 extend_table_simple(even_head
, &even_tail
, (eks
>>= 1) & 1);
222 in
= (in
>> 16 & 0xff) | (in
<< 16) | (in
& 0xff00);
223 recover(odd_head
, odd_tail
, oks
,
224 even_head
, even_tail
, eks
, 11, statelist
, in
<< 1);
232 static const uint32_t S1
[] = { 0x62141, 0x310A0, 0x18850, 0x0C428, 0x06214,
233 0x0310A, 0x85E30, 0xC69AD, 0x634D6, 0xB5CDE, 0xDE8DA, 0x6F46D, 0xB3C83,
234 0x59E41, 0xA8995, 0xD027F, 0x6813F, 0x3409F, 0x9E6FA};
235 static const uint32_t S2
[] = { 0x3A557B00, 0x5D2ABD80, 0x2E955EC0, 0x174AAF60,
236 0x0BA557B0, 0x05D2ABD8, 0x0449DE68, 0x048464B0, 0x42423258, 0x278192A8,
237 0x156042D0, 0x0AB02168, 0x43F89B30, 0x61FC4D98, 0x765EAD48, 0x7D8FDD20,
238 0x7EC7EE90, 0x7F63F748, 0x79117020};
239 static const uint32_t T1
[] = {
240 0x4F37D, 0x279BE, 0x97A6A, 0x4BD35, 0x25E9A, 0x12F4D, 0x097A6, 0x80D66,
241 0xC4006, 0x62003, 0xB56B4, 0x5AB5A, 0xA9318, 0xD0F39, 0x6879C, 0xB057B,
242 0x582BD, 0x2C15E, 0x160AF, 0x8F6E2, 0xC3DC4, 0xE5857, 0x72C2B, 0x39615,
243 0x98DBF, 0xC806A, 0xE0680, 0x70340, 0x381A0, 0x98665, 0x4C332, 0xA272C};
244 static const uint32_t T2
[] = { 0x3C88B810, 0x5E445C08, 0x2982A580, 0x14C152C0,
245 0x4A60A960, 0x253054B0, 0x52982A58, 0x2FEC9EA8, 0x1156C4D0, 0x08AB6268,
246 0x42F53AB0, 0x217A9D58, 0x161DC528, 0x0DAE6910, 0x46D73488, 0x25CB11C0,
247 0x52E588E0, 0x6972C470, 0x34B96238, 0x5CFC3A98, 0x28DE96C8, 0x12CFC0E0,
248 0x4967E070, 0x64B3F038, 0x74F97398, 0x7CDC3248, 0x38CE92A0, 0x1C674950,
249 0x0E33A4A8, 0x01B959D0, 0x40DCACE8, 0x26CEDDF0};
250 static const uint32_t C1
[] = { 0x846B5, 0x4235A, 0x211AD};
251 static const uint32_t C2
[] = { 0x1A822E0, 0x21A822E0, 0x21A822E0};
252 /** Reverse 64 bits of keystream into possible cipher states
253 * Variation mentioned in the paper. Somewhat optimized version
255 struct Crypto1State
* lfsr_recovery64(uint32_t ks2
, uint32_t ks3
)
257 struct Crypto1State
*statelist
, *sl
;
258 uint8_t oks
[32], eks
[32], hi
[32];
259 uint32_t low
= 0, win
= 0;
260 uint32_t *tail
, table
[1 << 16];
263 sl
= statelist
= malloc(sizeof(struct Crypto1State
) << 4);
266 sl
->odd
= sl
->even
= 0;
268 for(i
= 30; i
>= 0; i
-= 2) {
269 oks
[i
>> 1] = BEBIT(ks2
, i
);
270 oks
[16 + (i
>> 1)] = BEBIT(ks3
, i
);
272 for(i
= 31; i
>= 0; i
-= 2) {
273 eks
[i
>> 1] = BEBIT(ks2
, i
);
274 eks
[16 + (i
>> 1)] = BEBIT(ks3
, i
);
277 for(i
= 0xfffff; i
>= 0; --i
) {
278 if (filter(i
) != oks
[0])
282 for(j
= 1; tail
>= table
&& j
< 29; ++j
)
283 extend_table_simple(table
, &tail
, oks
[j
]);
288 for(j
= 0; j
< 19; ++j
)
289 low
= low
<< 1 | parity(i
& S1
[j
]);
290 for(j
= 0; j
< 32; ++j
)
291 hi
[j
] = parity(i
& T1
[j
]);
293 for(; tail
>= table
; --tail
) {
294 for(j
= 0; j
< 3; ++j
) {
296 *tail
|= parity((i
& C1
[j
]) ^ (*tail
& C2
[j
]));
297 if(filter(*tail
) != oks
[29 + j
])
301 for(j
= 0; j
< 19; ++j
)
302 win
= win
<< 1 | parity(*tail
& S2
[j
]);
305 for(j
= 0; j
< 32; ++j
) {
306 win
= win
<< 1 ^ hi
[j
] ^ parity(*tail
& T2
[j
]);
307 if(filter(win
) != eks
[j
])
311 *tail
= *tail
<< 1 | parity(LF_POLY_EVEN
& *tail
);
312 sl
->odd
= *tail
^ parity(LF_POLY_ODD
& win
);
315 sl
->odd
= sl
->even
= 0;
322 /** lfsr_rollback_bit
323 * Rollback the shift register in order to get previous states
325 uint8_t lfsr_rollback_bit(struct Crypto1State
*s
, uint32_t in
, int fb
)
337 out
^= LF_POLY_EVEN
& (s
->even
>>= 1);
338 out
^= LF_POLY_ODD
& s
->odd
;
340 out
^= (ret
= filter(s
->odd
)) & !!fb
;
342 s
->even
|= parity(out
) << 23;
345 /** lfsr_rollback_byte
346 * Rollback the shift register in order to get previous states
348 uint8_t lfsr_rollback_byte(struct Crypto1State
*s
, uint32_t in
, int fb
)
351 for (i
= 7; i
>= 0; --i
)
352 ret
|= lfsr_rollback_bit(s
, BIT(in
, i
), fb
) << i
;
355 /** lfsr_rollback_word
356 * Rollback the shift register in order to get previous states
358 uint32_t lfsr_rollback_word(struct Crypto1State
*s
, uint32_t in
, int fb
)
362 for (i
= 31; i
>= 0; --i
)
363 ret
|= lfsr_rollback_bit(s
, BEBIT(in
, i
), fb
) << (i
^ 24);
368 * x,y valid tag nonces, then prng_successor(x, nonce_distance(x, y)) = y
370 static uint16_t *dist
= 0;
371 int nonce_distance(uint32_t from
, uint32_t to
)
375 dist
= malloc(2 << 16);
378 for (x
= i
= 1; i
; ++i
) {
379 dist
[(x
& 0xff) << 8 | x
>> 8] = i
;
380 x
= x
>> 1 | (x
^ x
>> 2 ^ x
>> 3 ^ x
>> 5) << 15;
383 return (65535 + dist
[to
>> 16] - dist
[from
>> 16]) % 65535;
387 static uint32_t fastfwd
[2][8] = {
388 { 0, 0x4BC53, 0xECB1, 0x450E2, 0x25E29, 0x6E27A, 0x2B298, 0x60ECB},
389 { 0, 0x1D962, 0x4BC53, 0x56531, 0xECB1, 0x135D3, 0x450E2, 0x58980}};
392 * Is an exported helper function from the common prefix attack
393 * Described in the "dark side" paper. It returns an -1 terminated array
394 * of possible partial(21 bit) secret state.
395 * The required keystream(ks) needs to contain the keystream that was used to
396 * encrypt the NACK which is observed when varying only the 3 last bits of Nr
397 * only correct iff [NR_3] ^ NR_3 does not depend on Nr_3
399 uint32_t *lfsr_prefix_ks(uint8_t ks
[8], int isodd
)
401 uint32_t c
, entry
, *candidates
= malloc(4 << 10);
402 int i
, size
= 0, good
;
407 for(i
= 0; i
< 1 << 21; ++i
) {
408 for(c
= 0, good
= 1; good
&& c
< 8; ++c
) {
409 entry
= i
^ fastfwd
[isodd
][c
];
410 good
&= (BIT(ks
[c
], isodd
) == filter(entry
>> 1));
411 good
&= (BIT(ks
[c
], isodd
+ 2) == filter(entry
));
414 candidates
[size
++] = i
;
417 candidates
[size
] = -1;
423 * helper function which eliminates possible secret states using parity bits
425 static struct Crypto1State
*
426 check_pfx_parity(uint32_t prefix
, uint32_t rresp
, uint8_t parities
[8][8],
427 uint32_t odd
, uint32_t even
, struct Crypto1State
* sl
)
429 uint32_t ks1
, nr
, ks2
, rr
, ks3
, c
, good
= 1;
431 for(c
= 0; good
&& c
< 8; ++c
) {
432 sl
->odd
= odd
^ fastfwd
[1][c
];
433 sl
->even
= even
^ fastfwd
[0][c
];
435 lfsr_rollback_bit(sl
, 0, 0);
436 lfsr_rollback_bit(sl
, 0, 0);
438 ks3
= lfsr_rollback_bit(sl
, 0, 0);
439 ks2
= lfsr_rollback_word(sl
, 0, 0);
440 ks1
= lfsr_rollback_word(sl
, prefix
| c
<< 5, 1);
442 nr
= ks1
^ (prefix
| c
<< 5);
445 good
&= parity(nr
& 0x000000ff) ^ parities
[c
][3] ^ BIT(ks2
, 24);
446 good
&= parity(rr
& 0xff000000) ^ parities
[c
][4] ^ BIT(ks2
, 16);
447 good
&= parity(rr
& 0x00ff0000) ^ parities
[c
][5] ^ BIT(ks2
, 8);
448 good
&= parity(rr
& 0x0000ff00) ^ parities
[c
][6] ^ BIT(ks2
, 0);
449 good
&= parity(rr
& 0x000000ff) ^ parities
[c
][7] ^ ks3
;
456 /** lfsr_common_prefix
457 * Implentation of the common prefix attack.
460 lfsr_common_prefix(uint32_t pfx
, uint32_t rr
, uint8_t ks
[8], uint8_t par
[8][8])
462 struct Crypto1State
*statelist
, *s
;
463 uint32_t *odd
, *even
, *o
, *e
, top
;
465 odd
= lfsr_prefix_ks(ks
, 1);
466 even
= lfsr_prefix_ks(ks
, 0);
468 s
= statelist
= malloc((sizeof *statelist
) << 20);
469 if(!s
|| !odd
|| !even
) {
475 for(o
= odd
; *o
+ 1; ++o
)
476 for(e
= even
; *e
+ 1; ++e
)
477 for(top
= 0; top
< 64; ++top
) {
479 *e
+= (!(top
& 7) + 1) << 21;
480 s
= check_pfx_parity(pfx
, rr
, par
, *o
, *e
, s
);
483 s
->odd
= s
->even
= 0;