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* binsearch(uint32_t *start
, uint32_t *stop
)
62 uint32_t mid
, val
= *stop
& 0xff000000;
64 if(start
[mid
= (stop
- start
) >> 1] > val
)
72 /** update_contribution
73 * helper, calculates the partial linear feedback contributions and puts in MSB
76 update_contribution(uint32_t *item
, const uint32_t mask1
, const uint32_t mask2
)
78 uint32_t p
= *item
>> 25;
80 p
= p
<< 1 | parity(*item
& mask1
);
81 p
= p
<< 1 | parity(*item
& mask2
);
82 *item
= p
<< 24 | (*item
& 0xffffff);
86 * using a bit of the keystream extend the table of possible lfsr states
89 extend_table(uint32_t *tbl
, uint32_t **end
, int bit
, int m1
, int m2
, uint32_t in
)
92 for(*tbl
<<= 1; tbl
<= *end
; *++tbl
<<= 1)
93 if(filter(*tbl
) ^ filter(*tbl
| 1)) {
94 *tbl
|= filter(*tbl
) ^ bit
;
95 update_contribution(tbl
, m1
, m2
);
97 } else if(filter(*tbl
) == bit
) {
100 update_contribution(tbl
, m1
, m2
);
102 update_contribution(tbl
, m1
, m2
);
107 /** extend_table_simple
108 * using a bit of the keystream extend the table of possible lfsr states
110 static inline void extend_table_simple(uint32_t *tbl
, uint32_t **end
, int bit
)
112 for(*tbl
<<= 1; tbl
<= *end
; *++tbl
<<= 1)
113 if(filter(*tbl
) ^ filter(*tbl
| 1))
114 *tbl
|= filter(*tbl
) ^ bit
;
115 else if(filter(*tbl
) == bit
) {
122 * recursively narrow down the search space, 4 bits of keystream at a time
124 static struct Crypto1State
*
125 recover(uint32_t *o_head
, uint32_t *o_tail
, uint32_t oks
,
126 uint32_t *e_head
, uint32_t *e_tail
, uint32_t eks
, int rem
,
127 struct Crypto1State
*sl
, uint32_t in
)
132 for(e
= e_head
; e
<= e_tail
; ++e
) {
133 *e
= *e
<< 1 ^ parity(*e
& LF_POLY_EVEN
) ^ !!(in
& 4);
134 for(o
= o_head
; o
<= o_tail
; ++o
, ++sl
) {
136 sl
->odd
= *e
^ parity(*o
& LF_POLY_ODD
);
137 sl
[1].odd
= sl
[1].even
= 0;
143 for(i
= 0; i
< 4 && rem
--; i
++) {
147 extend_table(o_head
, &o_tail
, oks
& 1, LF_POLY_EVEN
<< 1 | 1,
148 LF_POLY_ODD
<< 1, 0);
152 extend_table(e_head
, &e_tail
, eks
& 1, LF_POLY_ODD
,
153 LF_POLY_EVEN
<< 1 | 1, in
& 3);
158 quicksort(o_head
, o_tail
);
159 quicksort(e_head
, e_tail
);
161 while(o_tail
>= o_head
&& e_tail
>= e_head
)
162 if(((*o_tail
^ *e_tail
) >> 24) == 0) {
163 o_tail
= binsearch(o_head
, o
= o_tail
);
164 e_tail
= binsearch(e_head
, e
= e_tail
);
165 sl
= recover(o_tail
--, o
, oks
,
166 e_tail
--, e
, eks
, rem
, sl
, in
);
168 else if(*o_tail
> *e_tail
)
169 o_tail
= binsearch(o_head
, o_tail
) - 1;
171 e_tail
= binsearch(e_head
, e_tail
) - 1;
176 * recover the state of the lfsr given 32 bits of the keystream
177 * additionally you can use the in parameter to specify the value
178 * that was fed into the lfsr at the time the keystream was generated
180 struct Crypto1State
* lfsr_recovery32(uint32_t ks2
, uint32_t in
)
182 struct Crypto1State
*statelist
;
183 uint32_t *odd_head
= 0, *odd_tail
= 0, oks
= 0;
184 uint32_t *even_head
= 0, *even_tail
= 0, eks
= 0;
187 for(i
= 31; i
>= 0; i
-= 2)
188 oks
= oks
<< 1 | BEBIT(ks2
, i
);
189 for(i
= 30; i
>= 0; i
-= 2)
190 eks
= eks
<< 1 | BEBIT(ks2
, i
);
192 odd_head
= odd_tail
= malloc(sizeof(uint32_t) << 21);
193 even_head
= even_tail
= malloc(sizeof(uint32_t) << 21);
194 statelist
= malloc(sizeof(struct Crypto1State
) << 18);
195 if(!odd_tail
-- || !even_tail
-- || !statelist
) {
201 statelist
->odd
= statelist
->even
= 0;
203 for(i
= 1 << 20; i
>= 0; --i
) {
204 if(filter(i
) == (oks
& 1))
206 if(filter(i
) == (eks
& 1))
210 for(i
= 0; i
< 4; i
++) {
211 extend_table_simple(odd_head
, &odd_tail
, (oks
>>= 1) & 1);
212 extend_table_simple(even_head
, &even_tail
, (eks
>>= 1) & 1);
215 in
= (in
>> 16 & 0xff) | (in
<< 16) | (in
& 0xff00);
216 recover(odd_head
, odd_tail
, oks
,
217 even_head
, even_tail
, eks
, 11, statelist
, in
<< 1);
225 static const uint32_t S1
[] = { 0x62141, 0x310A0, 0x18850, 0x0C428, 0x06214,
226 0x0310A, 0x85E30, 0xC69AD, 0x634D6, 0xB5CDE, 0xDE8DA, 0x6F46D, 0xB3C83,
227 0x59E41, 0xA8995, 0xD027F, 0x6813F, 0x3409F, 0x9E6FA};
228 static const uint32_t S2
[] = { 0x3A557B00, 0x5D2ABD80, 0x2E955EC0, 0x174AAF60,
229 0x0BA557B0, 0x05D2ABD8, 0x0449DE68, 0x048464B0, 0x42423258, 0x278192A8,
230 0x156042D0, 0x0AB02168, 0x43F89B30, 0x61FC4D98, 0x765EAD48, 0x7D8FDD20,
231 0x7EC7EE90, 0x7F63F748, 0x79117020};
232 static const uint32_t T1
[] = {
233 0x4F37D, 0x279BE, 0x97A6A, 0x4BD35, 0x25E9A, 0x12F4D, 0x097A6, 0x80D66,
234 0xC4006, 0x62003, 0xB56B4, 0x5AB5A, 0xA9318, 0xD0F39, 0x6879C, 0xB057B,
235 0x582BD, 0x2C15E, 0x160AF, 0x8F6E2, 0xC3DC4, 0xE5857, 0x72C2B, 0x39615,
236 0x98DBF, 0xC806A, 0xE0680, 0x70340, 0x381A0, 0x98665, 0x4C332, 0xA272C};
237 static const uint32_t T2
[] = { 0x3C88B810, 0x5E445C08, 0x2982A580, 0x14C152C0,
238 0x4A60A960, 0x253054B0, 0x52982A58, 0x2FEC9EA8, 0x1156C4D0, 0x08AB6268,
239 0x42F53AB0, 0x217A9D58, 0x161DC528, 0x0DAE6910, 0x46D73488, 0x25CB11C0,
240 0x52E588E0, 0x6972C470, 0x34B96238, 0x5CFC3A98, 0x28DE96C8, 0x12CFC0E0,
241 0x4967E070, 0x64B3F038, 0x74F97398, 0x7CDC3248, 0x38CE92A0, 0x1C674950,
242 0x0E33A4A8, 0x01B959D0, 0x40DCACE8, 0x26CEDDF0};
243 static const uint32_t C1
[] = { 0x846B5, 0x4235A, 0x211AD};
244 static const uint32_t C2
[] = { 0x1A822E0, 0x21A822E0, 0x21A822E0};
245 /** Reverse 64 bits of keystream into possible cipher states
246 * Variation mentioned in the paper. Somewhat optimized version
248 struct Crypto1State
* lfsr_recovery64(uint32_t ks2
, uint32_t ks3
)
250 struct Crypto1State
*statelist
, *sl
;
251 uint8_t oks
[32], eks
[32], hi
[32];
252 uint32_t low
= 0, win
= 0;
253 uint32_t *tail
, table
[1 << 16];
256 sl
= statelist
= malloc(sizeof(struct Crypto1State
) << 4);
259 sl
->odd
= sl
->even
= 0;
261 for(i
= 30; i
>= 0; i
-= 2) {
262 oks
[i
>> 1] = BEBIT(ks2
, i
);
263 oks
[16 + (i
>> 1)] = BEBIT(ks3
, i
);
265 for(i
= 31; i
>= 0; i
-= 2) {
266 eks
[i
>> 1] = BEBIT(ks2
, i
);
267 eks
[16 + (i
>> 1)] = BEBIT(ks3
, i
);
270 for(i
= 0xfffff; i
>= 0; --i
) {
271 if (filter(i
) != oks
[0])
275 for(j
= 1; tail
>= table
&& j
< 29; ++j
)
276 extend_table_simple(table
, &tail
, oks
[j
]);
281 for(j
= 0; j
< 19; ++j
)
282 low
= low
<< 1 | parity(i
& S1
[j
]);
283 for(j
= 0; j
< 32; ++j
)
284 hi
[j
] = parity(i
& T1
[j
]);
286 for(; tail
>= table
; --tail
) {
287 for(j
= 0; j
< 3; ++j
) {
289 *tail
|= parity((i
& C1
[j
]) ^ (*tail
& C2
[j
]));
290 if(filter(*tail
) != oks
[29 + j
])
294 for(j
= 0; j
< 19; ++j
)
295 win
= win
<< 1 | parity(*tail
& S2
[j
]);
298 for(j
= 0; j
< 32; ++j
) {
299 win
= win
<< 1 ^ hi
[j
] ^ parity(*tail
& T2
[j
]);
300 if(filter(win
) != eks
[j
])
304 *tail
= *tail
<< 1 | parity(LF_POLY_EVEN
& *tail
);
305 sl
->odd
= *tail
^ parity(LF_POLY_ODD
& win
);
308 sl
->odd
= sl
->even
= 0;
315 /** lfsr_rollback_bit
316 * Rollback the shift register in order to get previous states
318 uint8_t lfsr_rollback_bit(struct Crypto1State
*s
, uint32_t in
, int fb
)
324 s
->odd
^= (s
->odd
^= s
->even
, s
->even
^= s
->odd
);
327 out
^= LF_POLY_EVEN
& (s
->even
>>= 1);
328 out
^= LF_POLY_ODD
& s
->odd
;
330 out
^= (ret
= filter(s
->odd
)) & !!fb
;
332 s
->even
|= parity(out
) << 23;
335 /** lfsr_rollback_byte
336 * Rollback the shift register in order to get previous states
338 uint8_t lfsr_rollback_byte(struct Crypto1State
*s
, uint32_t in
, int fb
)
341 for (i
= 7; i
>= 0; --i
)
342 ret
|= lfsr_rollback_bit(s
, BIT(in
, i
), fb
) << i
;
345 /** lfsr_rollback_word
346 * Rollback the shift register in order to get previous states
348 uint32_t lfsr_rollback_word(struct Crypto1State
*s
, uint32_t in
, int fb
)
352 for (i
= 31; i
>= 0; --i
)
353 ret
|= lfsr_rollback_bit(s
, BEBIT(in
, i
), fb
) << (i
^ 24);
358 * x,y valid tag nonces, then prng_successor(x, nonce_distance(x, y)) = y
360 static uint16_t *dist
= 0;
361 int nonce_distance(uint32_t from
, uint32_t to
)
365 dist
= malloc(2 << 16);
368 for (x
= i
= 1; i
; ++i
) {
369 dist
[(x
& 0xff) << 8 | x
>> 8] = i
;
370 x
= x
>> 1 | (x
^ x
>> 2 ^ x
>> 3 ^ x
>> 5) << 15;
373 return (65535 + dist
[to
>> 16] - dist
[from
>> 16]) % 65535;
377 static uint32_t fastfwd
[2][8] = {
378 { 0, 0x4BC53, 0xECB1, 0x450E2, 0x25E29, 0x6E27A, 0x2B298, 0x60ECB},
379 { 0, 0x1D962, 0x4BC53, 0x56531, 0xECB1, 0x135D3, 0x450E2, 0x58980}};
382 * Is an exported helper function from the common prefix attack
383 * Described in the "dark side" paper. It returns an -1 terminated array
384 * of possible partial(21 bit) secret state.
385 * The required keystream(ks) needs to contain the keystream that was used to
386 * encrypt the NACK which is observed when varying only the 3 last bits of Nr
387 * only correct iff [NR_3] ^ NR_3 does not depend on Nr_3
389 uint32_t *lfsr_prefix_ks(uint8_t ks
[8], int isodd
)
391 uint32_t c
, entry
, *candidates
= malloc(4 << 10);
392 int i
, size
= 0, good
;
397 for(i
= 0; i
< 1 << 21; ++i
) {
398 for(c
= 0, good
= 1; good
&& c
< 8; ++c
) {
399 entry
= i
^ fastfwd
[isodd
][c
];
400 good
&= (BIT(ks
[c
], isodd
) == filter(entry
>> 1));
401 good
&= (BIT(ks
[c
], isodd
+ 2) == filter(entry
));
404 candidates
[size
++] = i
;
407 candidates
[size
] = -1;
413 * helper function which eliminates possible secret states using parity bits
415 static struct Crypto1State
*
416 check_pfx_parity(uint32_t prefix
, uint32_t rresp
, uint8_t parities
[8][8],
417 uint32_t odd
, uint32_t even
, struct Crypto1State
* sl
)
419 uint32_t ks1
, nr
, ks2
, rr
, ks3
, c
, good
= 1;
421 for(c
= 0; good
&& c
< 8; ++c
) {
422 sl
->odd
= odd
^ fastfwd
[1][c
];
423 sl
->even
= even
^ fastfwd
[0][c
];
425 lfsr_rollback_bit(sl
, 0, 0);
426 lfsr_rollback_bit(sl
, 0, 0);
428 ks3
= lfsr_rollback_bit(sl
, 0, 0);
429 ks2
= lfsr_rollback_word(sl
, 0, 0);
430 ks1
= lfsr_rollback_word(sl
, prefix
| c
<< 5, 1);
432 nr
= ks1
^ (prefix
| c
<< 5);
435 good
&= parity(nr
& 0x000000ff) ^ parities
[c
][3] ^ BIT(ks2
, 24);
436 good
&= parity(rr
& 0xff000000) ^ parities
[c
][4] ^ BIT(ks2
, 16);
437 good
&= parity(rr
& 0x00ff0000) ^ parities
[c
][5] ^ BIT(ks2
, 8);
438 good
&= parity(rr
& 0x0000ff00) ^ parities
[c
][6] ^ BIT(ks2
, 0);
439 good
&= parity(rr
& 0x000000ff) ^ parities
[c
][7] ^ ks3
;
446 /** lfsr_common_prefix
447 * Implentation of the common prefix attack.
450 lfsr_common_prefix(uint32_t pfx
, uint32_t rr
, uint8_t ks
[8], uint8_t par
[8][8])
452 struct Crypto1State
*statelist
, *s
;
453 uint32_t *odd
, *even
, *o
, *e
, top
;
455 odd
= lfsr_prefix_ks(ks
, 1);
456 even
= lfsr_prefix_ks(ks
, 0);
458 s
= statelist
= malloc((sizeof *statelist
) << 20);
459 if(!s
|| !odd
|| !even
) {
465 for(o
= odd
; *o
+ 1; ++o
)
466 for(e
= even
; *e
+ 1; ++e
)
467 for(top
= 0; top
< 64; ++top
) {
469 *e
+= (!(top
& 7) + 1) << 21;
470 s
= check_pfx_parity(pfx
, rr
, par
, *o
, *e
, s
);
473 s
->odd
= s
->even
= 0;