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
;
44 else if(*rit
> *start
)
47 *it
^= (*it
^= *rit
, *rit
^= *it
);
52 *rit
^= (*rit
^= *start
, *start
^= *rit
);
54 quicksort(start
, rit
- 1);
55 quicksort(rit
+ 1, stop
);
58 * Binary search for the first occurence of *stop's MSB in sorted [start,stop]
60 static inline uint32_t*
61 binsearch(uint32_t *start
, uint32_t *stop
)
63 uint32_t mid
, val
= *stop
& 0xff000000;
65 if(start
[mid
= (stop
- start
) >> 1] > val
)
73 /** update_contribution
74 * helper, calculates the partial linear feedback contributions and puts in MSB
77 update_contribution(uint32_t *item
, const uint32_t mask1
, const uint32_t mask2
)
79 uint32_t p
= *item
>> 25;
81 p
= p
<< 1 | parity(*item
& mask1
);
82 p
= p
<< 1 | parity(*item
& mask2
);
83 *item
= p
<< 24 | (*item
& 0xffffff);
87 * using a bit of the keystream extend the table of possible lfsr states
90 extend_table(uint32_t *tbl
, uint32_t **end
, int bit
, int m1
, int m2
, uint32_t in
)
93 for(*tbl
<<= 1; tbl
<= *end
; *++tbl
<<= 1)
94 if(filter(*tbl
) ^ filter(*tbl
| 1)) {
95 *tbl
|= filter(*tbl
) ^ bit
;
96 update_contribution(tbl
, m1
, m2
);
98 } else if(filter(*tbl
) == bit
) {
101 update_contribution(tbl
, m1
, m2
);
103 update_contribution(tbl
, m1
, m2
);
108 /** extend_table_simple
109 * using a bit of the keystream extend the table of possible lfsr states
112 extend_table_simple(uint32_t *tbl
, uint32_t **end
, int bit
)
114 for(*tbl
<<= 1; tbl
<= *end
; *++tbl
<<= 1)
115 if(filter(*tbl
) ^ filter(*tbl
| 1)) {
116 *tbl
|= filter(*tbl
) ^ bit
;
117 } else if(filter(*tbl
) == bit
) {
124 * recursively narrow down the search space, 4 bits of keystream at a time
126 static struct Crypto1State
*
127 recover(uint32_t *o_head
, uint32_t *o_tail
, uint32_t oks
,
128 uint32_t *e_head
, uint32_t *e_tail
, uint32_t eks
, int rem
,
129 struct Crypto1State
*sl
, uint32_t in
)
134 for(e
= e_head
; e
<= e_tail
; ++e
) {
135 *e
= *e
<< 1 ^ parity(*e
& LF_POLY_EVEN
) ^ !!(in
& 4);
136 for(o
= o_head
; o
<= o_tail
; ++o
, ++sl
) {
138 sl
->odd
= *e
^ parity(*o
& LF_POLY_ODD
);
139 sl
[1].odd
= sl
[1].even
= 0;
145 for(i
= 0; i
< 4 && rem
--; i
++) {
146 extend_table(o_head
, &o_tail
, (oks
>>= 1) & 1,
147 LF_POLY_EVEN
<< 1 | 1, LF_POLY_ODD
<< 1, 0);
151 extend_table(e_head
, &e_tail
, (eks
>>= 1) & 1,
152 LF_POLY_ODD
, LF_POLY_EVEN
<< 1 | 1, (in
>>= 2) & 3);
157 quicksort(o_head
, o_tail
);
158 quicksort(e_head
, e_tail
);
160 while(o_tail
>= o_head
&& e_tail
>= e_head
)
161 if(((*o_tail
^ *e_tail
) >> 24) == 0) {
162 o_tail
= binsearch(o_head
, o
= o_tail
);
163 e_tail
= binsearch(e_head
, e
= e_tail
);
164 sl
= recover(o_tail
--, o
, oks
,
165 e_tail
--, e
, eks
, rem
, sl
, in
);
167 else if(*o_tail
> *e_tail
)
168 o_tail
= binsearch(o_head
, o_tail
) - 1;
170 e_tail
= binsearch(e_head
, e_tail
) - 1;
175 * recover the state of the lfsr given 32 bits of the keystream
176 * additionally you can use the in parameter to specify the value
177 * that was fed into the lfsr at the time the keystream was generated
179 struct Crypto1State
* lfsr_recovery32(uint32_t ks2
, uint32_t in
)
181 struct Crypto1State
*statelist
;
182 uint32_t *odd_head
= 0, *odd_tail
= 0, oks
= 0;
183 uint32_t *even_head
= 0, *even_tail
= 0, eks
= 0;
186 for(i
= 31; i
>= 0; i
-= 2)
187 oks
= oks
<< 1 | BEBIT(ks2
, i
);
188 for(i
= 30; i
>= 0; i
-= 2)
189 eks
= eks
<< 1 | BEBIT(ks2
, i
);
191 odd_head
= odd_tail
= malloc(sizeof(uint32_t) << 21);
192 even_head
= even_tail
= malloc(sizeof(uint32_t) << 21);
193 statelist
= malloc(sizeof(struct Crypto1State
) << 18);
194 if(!odd_tail
-- || !even_tail
-- || !statelist
)
197 statelist
->odd
= statelist
->even
= 0;
199 for(i
= 1 << 20; i
>= 0; --i
) {
200 if(filter(i
) == (oks
& 1))
202 if(filter(i
) == (eks
& 1))
206 for(i
= 0; i
< 4; i
++) {
207 extend_table_simple(odd_head
, &odd_tail
, (oks
>>= 1) & 1);
208 extend_table_simple(even_head
, &even_tail
, (eks
>>= 1) & 1);
211 in
= (in
>> 16 & 0xff) | (in
<< 16) | (in
& 0xff00);
212 recover(odd_head
, odd_tail
, oks
,
213 even_head
, even_tail
, eks
, 11, statelist
, in
<< 1);
221 static const uint32_t S1
[] = { 0x62141, 0x310A0, 0x18850, 0x0C428, 0x06214,
222 0x0310A, 0x85E30, 0xC69AD, 0x634D6, 0xB5CDE, 0xDE8DA, 0x6F46D, 0xB3C83,
223 0x59E41, 0xA8995, 0xD027F, 0x6813F, 0x3409F, 0x9E6FA};
224 static const uint32_t S2
[] = { 0x3A557B00, 0x5D2ABD80, 0x2E955EC0, 0x174AAF60,
225 0x0BA557B0, 0x05D2ABD8, 0x0449DE68, 0x048464B0, 0x42423258, 0x278192A8,
226 0x156042D0, 0x0AB02168, 0x43F89B30, 0x61FC4D98, 0x765EAD48, 0x7D8FDD20,
227 0x7EC7EE90, 0x7F63F748, 0x79117020};
228 static const uint32_t T1
[] = {
229 0x4F37D, 0x279BE, 0x97A6A, 0x4BD35, 0x25E9A, 0x12F4D, 0x097A6, 0x80D66,
230 0xC4006, 0x62003, 0xB56B4, 0x5AB5A, 0xA9318, 0xD0F39, 0x6879C, 0xB057B,
231 0x582BD, 0x2C15E, 0x160AF, 0x8F6E2, 0xC3DC4, 0xE5857, 0x72C2B, 0x39615,
232 0x98DBF, 0xC806A, 0xE0680, 0x70340, 0x381A0, 0x98665, 0x4C332, 0xA272C};
233 static const uint32_t T2
[] = { 0x3C88B810, 0x5E445C08, 0x2982A580, 0x14C152C0,
234 0x4A60A960, 0x253054B0, 0x52982A58, 0x2FEC9EA8, 0x1156C4D0, 0x08AB6268,
235 0x42F53AB0, 0x217A9D58, 0x161DC528, 0x0DAE6910, 0x46D73488, 0x25CB11C0,
236 0x52E588E0, 0x6972C470, 0x34B96238, 0x5CFC3A98, 0x28DE96C8, 0x12CFC0E0,
237 0x4967E070, 0x64B3F038, 0x74F97398, 0x7CDC3248, 0x38CE92A0, 0x1C674950,
238 0x0E33A4A8, 0x01B959D0, 0x40DCACE8, 0x26CEDDF0};
239 static const uint32_t C1
[] = { 0x846B5, 0x4235A, 0x211AD};
240 static const uint32_t C2
[] = { 0x1A822E0, 0x21A822E0, 0x21A822E0};
241 /** Reverse 64 bits of keystream into possible cipher states
242 * Variation mentioned in the paper. Somewhat optimized version
244 struct Crypto1State
* lfsr_recovery64(uint32_t ks2
, uint32_t ks3
)
246 struct Crypto1State
*statelist
, *sl
;
247 uint8_t oks
[32], eks
[32], hi
[32];
248 uint32_t low
= 0, win
= 0;
249 uint32_t *tail
, table
[1 << 16];
252 sl
= statelist
= malloc(sizeof(struct Crypto1State
) << 4);
255 sl
->odd
= sl
->even
= 0;
257 for(i
= 30; i
>= 0; i
-= 2) {
258 oks
[i
>> 1] = BIT(ks2
, i
^ 24);
259 oks
[16 + (i
>> 1)] = BIT(ks3
, i
^ 24);
261 for(i
= 31; i
>= 0; i
-= 2) {
262 eks
[i
>> 1] = BIT(ks2
, i
^ 24);
263 eks
[16 + (i
>> 1)] = BIT(ks3
, i
^ 24);
266 for(i
= 0xfffff; i
>= 0; --i
) {
267 if (filter(i
) != oks
[0])
271 for(j
= 1; tail
>= table
&& j
< 29; ++j
)
272 extend_table_simple(table
, &tail
, oks
[j
]);
277 for(j
= 0; j
< 19; ++j
)
278 low
= low
<< 1 | parity(i
& S1
[j
]);
279 for(j
= 0; j
< 32; ++j
)
280 hi
[j
] = parity(i
& T1
[j
]);
282 for(; tail
>= table
; --tail
) {
283 for(j
= 0; j
< 3; ++j
) {
285 *tail
|= parity((i
& C1
[j
]) ^ (*tail
& C2
[j
]));
286 if(filter(*tail
) != oks
[29 + j
])
290 for(j
= 0; j
< 19; ++j
)
291 win
= win
<< 1 | parity(*tail
& S2
[j
]);
294 for(j
= 0; j
< 32; ++j
) {
295 win
= win
<< 1 ^ hi
[j
] ^ parity(*tail
& T2
[j
]);
296 if(filter(win
) != eks
[j
])
300 *tail
= *tail
<< 1 | parity(LF_POLY_EVEN
& *tail
);
301 sl
->odd
= *tail
^ parity(LF_POLY_ODD
& win
);
304 sl
->odd
= sl
->even
= 0;
311 /** lfsr_rollback_bit
312 * Rollback the shift register in order to get previous states
314 void lfsr_rollback_bit(struct Crypto1State
*s
, uint32_t in
, int fb
)
319 s
->odd
^= (s
->odd
^= s
->even
, s
->even
^= s
->odd
);
322 out
^= LF_POLY_EVEN
& (s
->even
>>= 1);
323 out
^= LF_POLY_ODD
& s
->odd
;
325 out
^= filter(s
->odd
) & !!fb
;
327 s
->even
|= parity(out
) << 23;
329 /** lfsr_rollback_byte
330 * Rollback the shift register in order to get previous states
332 void lfsr_rollback_byte(struct Crypto1State
*s
, uint32_t in
, int fb
)
335 for (i
= 7; i
>= 0; --i
)
336 lfsr_rollback_bit(s
, BEBIT(in
, i
), fb
);
338 /** lfsr_rollback_word
339 * Rollback the shift register in order to get previous states
341 void lfsr_rollback_word(struct Crypto1State
*s
, uint32_t in
, int fb
)
344 for (i
= 31; i
>= 0; --i
)
345 lfsr_rollback_bit(s
, BEBIT(in
, i
), fb
);
349 * x,y valid tag nonces, then prng_successor(x, nonce_distance(x, y)) = y
351 static uint16_t *dist
= 0;
352 int nonce_distance(uint32_t from
, uint32_t to
)
356 dist
= malloc(2 << 16);
359 for (x
= i
= 1; i
; ++i
) {
360 dist
[(x
& 0xff) << 8 | x
>> 8] = i
;
361 x
= x
>> 1 | (x
^ x
>> 2 ^ x
>> 3 ^ x
>> 5) << 15;
364 return (65535 + dist
[to
>> 16] - dist
[from
>> 16]) % 65535;
368 static uint32_t fastfwd
[2][8] = {
369 { 0, 0x4BC53, 0xECB1, 0x450E2, 0x25E29, 0x6E27A, 0x2B298, 0x60ECB},
370 { 0, 0x1D962, 0x4BC53, 0x56531, 0xECB1, 0x135D3, 0x450E2, 0x58980}};
375 * Is an exported helper function from the common prefix attack
376 * Described in the "dark side" paper. It returns an -1 terminated array
377 * of possible partial(21 bit) secret state.
378 * The required keystream(ks) needs to contain the keystream that was used to
379 * encrypt the NACK which is observed when varying only the 4 last bits of Nr
380 * only correct iff [NR_3] ^ NR_3 does not depend on Nr_3
382 uint32_t *lfsr_prefix_ks(uint8_t ks
[8], int isodd
)
384 uint32_t *candidates
= malloc(4 << 21);
391 size
= (1 << 21) - 1;
392 for(i
= 0; i
<= size
; ++i
)
395 for(c
= 0; c
< 8; ++c
)
396 for(i
= 0;i
<= size
; ++i
) {
397 entry
= candidates
[i
] ^ fastfwd
[isodd
][c
];
399 if(filter(entry
>> 1) == BIT(ks
[c
], isodd
))
400 if(filter(entry
) == BIT(ks
[c
], isodd
+ 2))
403 candidates
[i
--] = candidates
[size
--];
406 candidates
[size
+ 1] = -1;
412 * helper function which eliminates possible secret states using parity bits
414 static struct Crypto1State
*
415 brute_top(uint32_t prefix
, uint32_t rresp
, unsigned char parities
[8][8],
416 uint32_t odd
, uint32_t even
, struct Crypto1State
* sl
)
418 struct Crypto1State s
;
419 uint32_t ks1
, nr
, ks2
, rr
, ks3
, good
, c
;
421 for(c
= 0; c
< 8; ++c
) {
422 s
.odd
= odd
^ fastfwd
[1][c
];
423 s
.even
= even
^ fastfwd
[0][c
];
425 lfsr_rollback_bit(&s
, 0, 0);
426 lfsr_rollback_bit(&s
, 0, 0);
427 lfsr_rollback_bit(&s
, 0, 0);
429 lfsr_rollback_word(&s
, 0, 0);
430 lfsr_rollback_word(&s
, prefix
| c
<< 5, 1);
435 ks1
= crypto1_word(&s
, prefix
| c
<< 5, 1);
436 ks2
= crypto1_word(&s
,0,0);
437 ks3
= crypto1_word(&s
, 0,0);
438 nr
= ks1
^ (prefix
| c
<< 5);
442 good
&= parity(nr
& 0x000000ff) ^ parities
[c
][3] ^ BIT(ks2
, 24);
443 good
&= parity(rr
& 0xff000000) ^ parities
[c
][4] ^ BIT(ks2
, 16);
444 good
&= parity(rr
& 0x00ff0000) ^ parities
[c
][5] ^ BIT(ks2
, 8);
445 good
&= parity(rr
& 0x0000ff00) ^ parities
[c
][6] ^ BIT(ks2
, 0);
446 good
&= parity(rr
& 0x000000ff) ^ parities
[c
][7] ^ BIT(ks3
, 24);
456 /** lfsr_common_prefix
457 * Implentation of the common prefix attack.
458 * Requires the 28 bit constant prefix used as reader nonce (pfx)
459 * The reader response used (rr)
460 * The keystream used to encrypt the observed NACK's (ks)
461 * The parity bits (par)
462 * It returns a zero terminated list of possible cipher states after the
463 * tag nonce was fed in
466 lfsr_common_prefix(uint32_t pfx
, uint32_t rr
, uint8_t ks
[8], uint8_t par
[8][8])
468 struct Crypto1State
*statelist
, *s
;
469 uint32_t *odd
, *even
, *o
, *e
, top
;
471 odd
= lfsr_prefix_ks(ks
, 1);
472 even
= lfsr_prefix_ks(ks
, 0);
474 statelist
= malloc((sizeof *statelist
) << 20);
475 if(!statelist
|| !odd
|| !even
)
480 for(o
= odd
; *o
!= 0xffffffff; ++o
)
481 for(e
= even
; *e
!= 0xffffffff; ++e
)
482 for(top
= 0; top
< 64; ++top
) {
483 *o
= (*o
& 0x1fffff) | (top
<< 21);
484 *e
= (*e
& 0x1fffff) | (top
>> 3) << 21;
485 s
= brute_top(pfx
, rr
, par
, *o
, *e
, s
);
488 s
->odd
= s
->even
= 0;