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-2014 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])
36 typedef struct bucket
{
41 typedef bucket_t bucket_array_t
[2][0x100];
43 typedef struct bucket_info
{
45 uint32_t *head
, *tail
;
46 } bucket_info
[2][0x100];
51 static void bucket_sort_intersect(uint32_t* const estart
, uint32_t* const estop
,
52 uint32_t* const ostart
, uint32_t* const ostop
,
53 bucket_info_t
*bucket_info
, bucket_array_t bucket
)
64 // init buckets to be empty
65 for (uint32_t i
= 0; i
< 2; i
++) {
66 for (uint32_t j
= 0x00; j
<= 0xff; j
++) {
67 bucket
[i
][j
].bp
= bucket
[i
][j
].head
;
71 // sort the lists into the buckets based on the MSB (contribution bits)
72 for (uint32_t i
= 0; i
< 2; i
++) {
73 for (p1
= start
[i
]; p1
<= stop
[i
]; p1
++) {
74 uint32_t bucket_index
= (*p1
& 0xff000000) >> 24;
75 *(bucket
[i
][bucket_index
].bp
++) = *p1
;
80 // write back intersecting buckets as sorted list.
81 // fill in bucket_info with head and tail of the bucket contents in the list and number of non-empty buckets.
82 uint32_t nonempty_bucket
;
83 for (uint32_t i
= 0; i
< 2; i
++) {
86 for (uint32_t j
= 0x00; j
<= 0xff; j
++) {
87 if (bucket
[0][j
].bp
!= bucket
[0][j
].head
&& bucket
[1][j
].bp
!= bucket
[1][j
].head
) { // non-empty intersecting buckets only
88 bucket_info
->bucket_info
[i
][nonempty_bucket
].head
= p1
;
89 for (p2
= bucket
[i
][j
].head
; p2
< bucket
[i
][j
].bp
; *p1
++ = *p2
++);
90 bucket_info
->bucket_info
[i
][nonempty_bucket
].tail
= p1
- 1;
94 bucket_info
->numbuckets
= nonempty_bucket
;
98 * Binary search for the first occurence of *stop's MSB in sorted [start,stop]
100 static inline uint32_t* binsearch(uint32_t *start
, uint32_t *stop
)
102 uint32_t mid
, val
= *stop
& 0xff000000;
104 if(start
[mid
= (stop
- start
) >> 1] > val
)
112 /** update_contribution
113 * helper, calculates the partial linear feedback contributions and puts in MSB
116 update_contribution(uint32_t *item
, const uint32_t mask1
, const uint32_t mask2
)
118 uint32_t p
= *item
>> 25;
120 p
= p
<< 1 | parity(*item
& mask1
);
121 p
= p
<< 1 | parity(*item
& mask2
);
122 *item
= p
<< 24 | (*item
& 0xffffff);
126 * using a bit of the keystream extend the table of possible lfsr states
129 extend_table(uint32_t *tbl
, uint32_t **end
, int bit
, int m1
, int m2
, uint32_t in
)
132 for(*tbl
<<= 1; tbl
<= *end
; *++tbl
<<= 1)
133 if(filter(*tbl
) ^ filter(*tbl
| 1)) {
134 *tbl
|= filter(*tbl
) ^ bit
;
135 update_contribution(tbl
, m1
, m2
);
137 } else if(filter(*tbl
) == bit
) {
140 update_contribution(tbl
, m1
, m2
);
142 update_contribution(tbl
, m1
, m2
);
147 /** extend_table_simple
148 * using a bit of the keystream extend the table of possible lfsr states
150 static inline void extend_table_simple(uint32_t *tbl
, uint32_t **end
, int bit
)
152 for(*tbl
<<= 1; tbl
<= *end
; *++tbl
<<= 1)
153 if(filter(*tbl
) ^ filter(*tbl
| 1))
154 *tbl
|= filter(*tbl
) ^ bit
;
155 else if(filter(*tbl
) == bit
) {
165 * recursively narrow down the search space, 4 bits of keystream at a time
167 static struct Crypto1State
*
168 recover(uint32_t *o_head
, uint32_t *o_tail
, uint32_t oks
,
169 uint32_t *e_head
, uint32_t *e_tail
, uint32_t eks
, int rem
,
170 struct Crypto1State
*sl
, uint32_t in
, bucket_array_t bucket
)
173 bucket_info_t bucket_info
;
176 for(e
= e_head
; e
<= e_tail
; ++e
) {
177 *e
= *e
<< 1 ^ parity(*e
& LF_POLY_EVEN
) ^ !!(in
& 4);
178 for(o
= o_head
; o
<= o_tail
; ++o
, ++sl
) {
180 sl
->odd
= *e
^ parity(*o
& LF_POLY_ODD
);
181 sl
[1].odd
= sl
[1].even
= 0;
187 for(i
= 0; i
< 4 && rem
--; i
++) {
191 extend_table(o_head
, &o_tail
, oks
& 1, LF_POLY_EVEN
<< 1 | 1,
192 LF_POLY_ODD
<< 1, 0);
196 extend_table(e_head
, &e_tail
, eks
& 1, LF_POLY_ODD
,
197 LF_POLY_EVEN
<< 1 | 1, in
& 3);
201 bucket_sort_intersect(e_head
, e_tail
, o_head
, o_tail
, &bucket_info
, bucket
);
203 for (int i
= bucket_info
.numbuckets
- 1; i
>= 0; i
--) {
204 sl
= recover(bucket_info
.bucket_info
[1][i
].head
, bucket_info
.bucket_info
[1][i
].tail
, oks
,
205 bucket_info
.bucket_info
[0][i
].head
, bucket_info
.bucket_info
[0][i
].tail
, eks
,
206 rem
, sl
, in
, bucket
);
212 * recover the state of the lfsr given 32 bits of the keystream
213 * additionally you can use the in parameter to specify the value
214 * that was fed into the lfsr at the time the keystream was generated
216 struct Crypto1State
* lfsr_recovery32(uint32_t ks2
, uint32_t in
)
218 struct Crypto1State
*statelist
;
219 uint32_t *odd_head
= 0, *odd_tail
= 0, oks
= 0;
220 uint32_t *even_head
= 0, *even_tail
= 0, eks
= 0;
223 for(i
= 31; i
>= 0; i
-= 2)
224 oks
= oks
<< 1 | BEBIT(ks2
, i
);
225 for(i
= 30; i
>= 0; i
-= 2)
226 eks
= eks
<< 1 | BEBIT(ks2
, i
);
228 odd_head
= odd_tail
= malloc(sizeof(uint32_t) << 21);
229 even_head
= even_tail
= malloc(sizeof(uint32_t) << 21);
230 statelist
= malloc(sizeof(struct Crypto1State
) << 18);
231 if(!odd_tail
-- || !even_tail
-- || !statelist
) {
236 statelist
->odd
= statelist
->even
= 0;
238 // allocate memory for out of place bucket_sort
239 bucket_array_t bucket
;
240 for (uint32_t i
= 0; i
< 2; i
++)
241 for (uint32_t j
= 0; j
<= 0xff; j
++) {
242 bucket
[i
][j
].head
= malloc(sizeof(uint32_t)<<14);
243 if (!bucket
[i
][j
].head
) {
249 for(i
= 1 << 20; i
>= 0; --i
) {
250 if(filter(i
) == (oks
& 1))
252 if(filter(i
) == (eks
& 1))
256 for(i
= 0; i
< 4; i
++) {
257 extend_table_simple(odd_head
, &odd_tail
, (oks
>>= 1) & 1);
258 extend_table_simple(even_head
, &even_tail
, (eks
>>= 1) & 1);
261 in
= (in
>> 16 & 0xff) | (in
<< 16) | (in
& 0xff00);
262 recover(odd_head
, odd_tail
, oks
,
263 even_head
, even_tail
, eks
, 11, statelist
, in
<< 1, bucket
);
268 for (uint32_t i
= 0; i
< 2; i
++)
269 for (uint32_t j
= 0; j
<= 0xff; j
++)
270 free(bucket
[i
][j
].head
);
275 static const uint32_t S1
[] = { 0x62141, 0x310A0, 0x18850, 0x0C428, 0x06214,
276 0x0310A, 0x85E30, 0xC69AD, 0x634D6, 0xB5CDE, 0xDE8DA, 0x6F46D, 0xB3C83,
277 0x59E41, 0xA8995, 0xD027F, 0x6813F, 0x3409F, 0x9E6FA};
278 static const uint32_t S2
[] = { 0x3A557B00, 0x5D2ABD80, 0x2E955EC0, 0x174AAF60,
279 0x0BA557B0, 0x05D2ABD8, 0x0449DE68, 0x048464B0, 0x42423258, 0x278192A8,
280 0x156042D0, 0x0AB02168, 0x43F89B30, 0x61FC4D98, 0x765EAD48, 0x7D8FDD20,
281 0x7EC7EE90, 0x7F63F748, 0x79117020};
282 static const uint32_t T1
[] = {
283 0x4F37D, 0x279BE, 0x97A6A, 0x4BD35, 0x25E9A, 0x12F4D, 0x097A6, 0x80D66,
284 0xC4006, 0x62003, 0xB56B4, 0x5AB5A, 0xA9318, 0xD0F39, 0x6879C, 0xB057B,
285 0x582BD, 0x2C15E, 0x160AF, 0x8F6E2, 0xC3DC4, 0xE5857, 0x72C2B, 0x39615,
286 0x98DBF, 0xC806A, 0xE0680, 0x70340, 0x381A0, 0x98665, 0x4C332, 0xA272C};
287 static const uint32_t T2
[] = { 0x3C88B810, 0x5E445C08, 0x2982A580, 0x14C152C0,
288 0x4A60A960, 0x253054B0, 0x52982A58, 0x2FEC9EA8, 0x1156C4D0, 0x08AB6268,
289 0x42F53AB0, 0x217A9D58, 0x161DC528, 0x0DAE6910, 0x46D73488, 0x25CB11C0,
290 0x52E588E0, 0x6972C470, 0x34B96238, 0x5CFC3A98, 0x28DE96C8, 0x12CFC0E0,
291 0x4967E070, 0x64B3F038, 0x74F97398, 0x7CDC3248, 0x38CE92A0, 0x1C674950,
292 0x0E33A4A8, 0x01B959D0, 0x40DCACE8, 0x26CEDDF0};
293 static const uint32_t C1
[] = { 0x846B5, 0x4235A, 0x211AD};
294 static const uint32_t C2
[] = { 0x1A822E0, 0x21A822E0, 0x21A822E0};
295 /** Reverse 64 bits of keystream into possible cipher states
296 * Variation mentioned in the paper. Somewhat optimized version
298 struct Crypto1State
* lfsr_recovery64(uint32_t ks2
, uint32_t ks3
)
300 struct Crypto1State
*statelist
, *sl
;
301 uint8_t oks
[32], eks
[32], hi
[32];
302 uint32_t low
= 0, win
= 0;
303 uint32_t *tail
, table
[1 << 16];
306 sl
= statelist
= malloc(sizeof(struct Crypto1State
) << 4);
309 sl
->odd
= sl
->even
= 0;
311 for(i
= 30; i
>= 0; i
-= 2) {
312 oks
[i
>> 1] = BEBIT(ks2
, i
);
313 oks
[16 + (i
>> 1)] = BEBIT(ks3
, i
);
315 for(i
= 31; i
>= 0; i
-= 2) {
316 eks
[i
>> 1] = BEBIT(ks2
, i
);
317 eks
[16 + (i
>> 1)] = BEBIT(ks3
, i
);
320 for(i
= 0xfffff; i
>= 0; --i
) {
321 if (filter(i
) != oks
[0])
325 for(j
= 1; tail
>= table
&& j
< 29; ++j
)
326 extend_table_simple(table
, &tail
, oks
[j
]);
331 for(j
= 0; j
< 19; ++j
)
332 low
= low
<< 1 | parity(i
& S1
[j
]);
333 for(j
= 0; j
< 32; ++j
)
334 hi
[j
] = parity(i
& T1
[j
]);
336 for(; tail
>= table
; --tail
) {
337 for(j
= 0; j
< 3; ++j
) {
339 *tail
|= parity((i
& C1
[j
]) ^ (*tail
& C2
[j
]));
340 if(filter(*tail
) != oks
[29 + j
])
344 for(j
= 0; j
< 19; ++j
)
345 win
= win
<< 1 | parity(*tail
& S2
[j
]);
348 for(j
= 0; j
< 32; ++j
) {
349 win
= win
<< 1 ^ hi
[j
] ^ parity(*tail
& T2
[j
]);
350 if(filter(win
) != eks
[j
])
354 *tail
= *tail
<< 1 | parity(LF_POLY_EVEN
& *tail
);
355 sl
->odd
= *tail
^ parity(LF_POLY_ODD
& win
);
358 sl
->odd
= sl
->even
= 0;
365 /** lfsr_rollback_bit
366 * Rollback the shift register in order to get previous states
368 uint8_t lfsr_rollback_bit(struct Crypto1State
*s
, uint32_t in
, int fb
)
375 t
= s
->odd
, s
->odd
= s
->even
, s
->even
= t
;
378 out
^= LF_POLY_EVEN
& (s
->even
>>= 1);
379 out
^= LF_POLY_ODD
& s
->odd
;
381 out
^= (ret
= filter(s
->odd
)) & !!fb
;
383 s
->even
|= parity(out
) << 23;
386 /** lfsr_rollback_byte
387 * Rollback the shift register in order to get previous states
389 uint8_t lfsr_rollback_byte(struct Crypto1State
*s
, uint32_t in
, int fb
)
392 for (i
= 7; i
>= 0; --i
)
393 ret
|= lfsr_rollback_bit(s
, BIT(in
, i
), fb
) << i
;
396 /** lfsr_rollback_word
397 * Rollback the shift register in order to get previous states
399 uint32_t lfsr_rollback_word(struct Crypto1State
*s
, uint32_t in
, int fb
)
403 for (i
= 31; i
>= 0; --i
)
404 ret
|= lfsr_rollback_bit(s
, BEBIT(in
, i
), fb
) << (i
^ 24);
409 * x,y valid tag nonces, then prng_successor(x, nonce_distance(x, y)) = y
411 static uint16_t *dist
= 0;
412 int nonce_distance(uint32_t from
, uint32_t to
)
416 dist
= malloc(2 << 16);
419 for (x
= i
= 1; i
; ++i
) {
420 dist
[(x
& 0xff) << 8 | x
>> 8] = i
;
421 x
= x
>> 1 | (x
^ x
>> 2 ^ x
>> 3 ^ x
>> 5) << 15;
424 return (65535 + dist
[to
>> 16] - dist
[from
>> 16]) % 65535;
428 static uint32_t fastfwd
[2][8] = {
429 { 0, 0x4BC53, 0xECB1, 0x450E2, 0x25E29, 0x6E27A, 0x2B298, 0x60ECB},
430 { 0, 0x1D962, 0x4BC53, 0x56531, 0xECB1, 0x135D3, 0x450E2, 0x58980}};
433 * Is an exported helper function from the common prefix attack
434 * Described in the "dark side" paper. It returns an -1 terminated array
435 * of possible partial(21 bit) secret state.
436 * The required keystream(ks) needs to contain the keystream that was used to
437 * encrypt the NACK which is observed when varying only the 3 last bits of Nr
438 * only correct iff [NR_3] ^ NR_3 does not depend on Nr_3
440 uint32_t *lfsr_prefix_ks(uint8_t ks
[8], int isodd
)
442 uint32_t c
, entry
, *candidates
= malloc(4 << 10);
443 int i
, size
= 0, good
;
448 for(i
= 0; i
< 1 << 21; ++i
) {
449 for(c
= 0, good
= 1; good
&& c
< 8; ++c
) {
450 entry
= i
^ fastfwd
[isodd
][c
];
451 good
&= (BIT(ks
[c
], isodd
) == filter(entry
>> 1));
452 good
&= (BIT(ks
[c
], isodd
+ 2) == filter(entry
));
455 candidates
[size
++] = i
;
458 candidates
[size
] = -1;
464 * helper function which eliminates possible secret states using parity bits
466 static struct Crypto1State
*
467 check_pfx_parity(uint32_t prefix
, uint32_t rresp
, uint8_t parities
[8][8],
468 uint32_t odd
, uint32_t even
, struct Crypto1State
* sl
, uint32_t no_par
)
470 uint32_t ks1
, nr
, ks2
, rr
, ks3
, c
, good
= 1;
472 for(c
= 0; good
&& c
< 8; ++c
) {
473 sl
->odd
= odd
^ fastfwd
[1][c
];
474 sl
->even
= even
^ fastfwd
[0][c
];
476 lfsr_rollback_bit(sl
, 0, 0);
477 lfsr_rollback_bit(sl
, 0, 0);
479 ks3
= lfsr_rollback_bit(sl
, 0, 0);
480 ks2
= lfsr_rollback_word(sl
, 0, 0);
481 ks1
= lfsr_rollback_word(sl
, prefix
| c
<< 5, 1);
486 nr
= ks1
^ (prefix
| c
<< 5);
489 good
&= parity(nr
& 0x000000ff) ^ parities
[c
][3] ^ BIT(ks2
, 24);
490 good
&= parity(rr
& 0xff000000) ^ parities
[c
][4] ^ BIT(ks2
, 16);
491 good
&= parity(rr
& 0x00ff0000) ^ parities
[c
][5] ^ BIT(ks2
, 8);
492 good
&= parity(rr
& 0x0000ff00) ^ parities
[c
][6] ^ BIT(ks2
, 0);
493 good
&= parity(rr
& 0x000000ff) ^ parities
[c
][7] ^ ks3
;
500 /** lfsr_common_prefix
501 * Implentation of the common prefix attack.
504 lfsr_common_prefix(uint32_t pfx
, uint32_t rr
, uint8_t ks
[8], uint8_t par
[8][8], uint32_t no_par
)
506 struct Crypto1State
*statelist
, *s
;
507 uint32_t *odd
, *even
, *o
, *e
, top
;
509 odd
= lfsr_prefix_ks(ks
, 1);
510 even
= lfsr_prefix_ks(ks
, 0);
512 s
= statelist
= malloc((sizeof *statelist
) << 21); // need more for no_par special attack. Enough???
513 if(!s
|| !odd
|| !even
) {
519 for(o
= odd
; *o
+ 1; ++o
)
520 for(e
= even
; *e
+ 1; ++e
)
521 for(top
= 0; top
< 64; ++top
) {
523 *e
+= (!(top
& 7) + 1) << 21;
524 s
= check_pfx_parity(pfx
, rr
, par
, *o
, *e
, s
, no_par
);
527 s
->odd
= s
->even
= 0;