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
;
99 * Binary search for the first occurence of *stop's MSB in sorted [start,stop]
101 static inline uint32_t* binsearch(uint32_t *start
, uint32_t *stop
)
103 uint32_t mid
, val
= *stop
& 0xff000000;
105 if(start
[mid
= (stop
- start
) >> 1] > val
)
113 /** update_contribution
114 * helper, calculates the partial linear feedback contributions and puts in MSB
117 update_contribution(uint32_t *item
, const uint32_t mask1
, const uint32_t mask2
)
119 uint32_t p
= *item
>> 25;
121 p
= p
<< 1 | parity(*item
& mask1
);
122 p
= p
<< 1 | parity(*item
& mask2
);
123 *item
= p
<< 24 | (*item
& 0xffffff);
127 * using a bit of the keystream extend the table of possible lfsr states
130 extend_table(uint32_t *tbl
, uint32_t **end
, int bit
, int m1
, int m2
, uint32_t in
)
133 for(*tbl
<<= 1; tbl
<= *end
; *++tbl
<<= 1)
134 if(filter(*tbl
) ^ filter(*tbl
| 1)) {
135 *tbl
|= filter(*tbl
) ^ bit
;
136 update_contribution(tbl
, m1
, m2
);
138 } else if(filter(*tbl
) == bit
) {
141 update_contribution(tbl
, m1
, m2
);
143 update_contribution(tbl
, m1
, m2
);
148 /** extend_table_simple
149 * using a bit of the keystream extend the table of possible lfsr states
151 static inline void extend_table_simple(uint32_t *tbl
, uint32_t **end
, int bit
)
153 for(*tbl
<<= 1; tbl
<= *end
; *++tbl
<<= 1)
154 if(filter(*tbl
) ^ filter(*tbl
| 1)) { // replace
155 *tbl
|= filter(*tbl
) ^ bit
;
156 } else if(filter(*tbl
) == bit
) { // insert
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(uint32_t 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);
202 bucket_sort_intersect(e_head
, e_tail
, o_head
, o_tail
, &bucket_info
, bucket
);
204 for (int i
= bucket_info
.numbuckets
- 1; i
>= 0; i
--) {
205 sl
= recover(bucket_info
.bucket_info
[1][i
].head
, bucket_info
.bucket_info
[1][i
].tail
, oks
,
206 bucket_info
.bucket_info
[0][i
].head
, bucket_info
.bucket_info
[0][i
].tail
, eks
,
207 rem
, sl
, in
, bucket
);
213 * recover the state of the lfsr given 32 bits of the keystream
214 * additionally you can use the in parameter to specify the value
215 * that was fed into the lfsr at the time the keystream was generated
217 struct Crypto1State
* lfsr_recovery32(uint32_t ks2
, uint32_t in
)
219 struct Crypto1State
*statelist
;
220 uint32_t *odd_head
= 0, *odd_tail
= 0, oks
= 0;
221 uint32_t *even_head
= 0, *even_tail
= 0, eks
= 0;
224 // split the keystream into an odd and even part
225 for(i
= 31; i
>= 0; i
-= 2)
226 oks
= oks
<< 1 | BEBIT(ks2
, i
);
227 for(i
= 30; i
>= 0; i
-= 2)
228 eks
= eks
<< 1 | BEBIT(ks2
, i
);
230 odd_head
= odd_tail
= malloc(sizeof(uint32_t) << 21);
231 even_head
= even_tail
= malloc(sizeof(uint32_t) << 21);
232 statelist
= malloc(sizeof(struct Crypto1State
) << 18);
233 if(!odd_tail
-- || !even_tail
-- || !statelist
) {
239 statelist
->odd
= statelist
->even
= 0;
241 // allocate memory for out of place bucket_sort
242 bucket_array_t bucket
;
243 for (uint32_t i
= 0; i
< 2; i
++)
244 for (uint32_t j
= 0; j
<= 0xff; j
++) {
245 bucket
[i
][j
].head
= malloc(sizeof(uint32_t)<<14);
246 if (!bucket
[i
][j
].head
) {
252 // initialize statelists: add all possible states which would result into the rightmost 2 bits of the keystream
253 for(i
= 1 << 20; i
>= 0; --i
) {
254 if(filter(i
) == (oks
& 1))
256 if(filter(i
) == (eks
& 1))
260 // extend the statelists. Look at the next 8 Bits of the keystream (4 Bit each odd and even):
261 for(i
= 0; i
< 4; i
++) {
262 extend_table_simple(odd_head
, &odd_tail
, (oks
>>= 1) & 1);
263 extend_table_simple(even_head
, &even_tail
, (eks
>>= 1) & 1);
266 // the statelists now contain all states which could have generated the last 10 Bits of the keystream.
267 // 22 bits to go to recover 32 bits in total. From now on, we need to take the "in"
268 // parameter into account.
269 in
= (in
>> 16 & 0xff) | (in
<< 16) | (in
& 0xff00); // Byte swapping
270 recover(odd_head
, odd_tail
, oks
,
271 even_head
, even_tail
, eks
, 11, statelist
, in
<< 1, bucket
);
277 for (uint32_t i
= 0; i
< 2; i
++)
278 for (uint32_t j
= 0; j
<= 0xff; j
++)
279 free(bucket
[i
][j
].head
);
284 static const uint32_t S1
[] = { 0x62141, 0x310A0, 0x18850, 0x0C428, 0x06214,
285 0x0310A, 0x85E30, 0xC69AD, 0x634D6, 0xB5CDE, 0xDE8DA, 0x6F46D, 0xB3C83,
286 0x59E41, 0xA8995, 0xD027F, 0x6813F, 0x3409F, 0x9E6FA};
287 static const uint32_t S2
[] = { 0x3A557B00, 0x5D2ABD80, 0x2E955EC0, 0x174AAF60,
288 0x0BA557B0, 0x05D2ABD8, 0x0449DE68, 0x048464B0, 0x42423258, 0x278192A8,
289 0x156042D0, 0x0AB02168, 0x43F89B30, 0x61FC4D98, 0x765EAD48, 0x7D8FDD20,
290 0x7EC7EE90, 0x7F63F748, 0x79117020};
291 static const uint32_t T1
[] = {
292 0x4F37D, 0x279BE, 0x97A6A, 0x4BD35, 0x25E9A, 0x12F4D, 0x097A6, 0x80D66,
293 0xC4006, 0x62003, 0xB56B4, 0x5AB5A, 0xA9318, 0xD0F39, 0x6879C, 0xB057B,
294 0x582BD, 0x2C15E, 0x160AF, 0x8F6E2, 0xC3DC4, 0xE5857, 0x72C2B, 0x39615,
295 0x98DBF, 0xC806A, 0xE0680, 0x70340, 0x381A0, 0x98665, 0x4C332, 0xA272C};
296 static const uint32_t T2
[] = { 0x3C88B810, 0x5E445C08, 0x2982A580, 0x14C152C0,
297 0x4A60A960, 0x253054B0, 0x52982A58, 0x2FEC9EA8, 0x1156C4D0, 0x08AB6268,
298 0x42F53AB0, 0x217A9D58, 0x161DC528, 0x0DAE6910, 0x46D73488, 0x25CB11C0,
299 0x52E588E0, 0x6972C470, 0x34B96238, 0x5CFC3A98, 0x28DE96C8, 0x12CFC0E0,
300 0x4967E070, 0x64B3F038, 0x74F97398, 0x7CDC3248, 0x38CE92A0, 0x1C674950,
301 0x0E33A4A8, 0x01B959D0, 0x40DCACE8, 0x26CEDDF0};
302 static const uint32_t C1
[] = { 0x846B5, 0x4235A, 0x211AD};
303 static const uint32_t C2
[] = { 0x1A822E0, 0x21A822E0, 0x21A822E0};
304 /** Reverse 64 bits of keystream into possible cipher states
305 * Variation mentioned in the paper. Somewhat optimized version
307 struct Crypto1State
* lfsr_recovery64(uint32_t ks2
, uint32_t ks3
)
309 struct Crypto1State
*statelist
, *sl
;
310 uint8_t oks
[32], eks
[32], hi
[32];
311 uint32_t low
= 0, win
= 0;
312 uint32_t *tail
, table
[1 << 16];
315 sl
= statelist
= malloc(sizeof(struct Crypto1State
) << 4);
318 sl
->odd
= sl
->even
= 0;
320 for(i
= 30; i
>= 0; i
-= 2) {
321 oks
[i
>> 1] = BEBIT(ks2
, i
);
322 oks
[16 + (i
>> 1)] = BEBIT(ks3
, i
);
324 for(i
= 31; i
>= 0; i
-= 2) {
325 eks
[i
>> 1] = BEBIT(ks2
, i
);
326 eks
[16 + (i
>> 1)] = BEBIT(ks3
, i
);
329 for(i
= 0xfffff; i
>= 0; --i
) {
330 if (filter(i
) != oks
[0])
334 for(j
= 1; tail
>= table
&& j
< 29; ++j
)
335 extend_table_simple(table
, &tail
, oks
[j
]);
340 for(j
= 0; j
< 19; ++j
)
341 low
= low
<< 1 | parity(i
& S1
[j
]);
342 for(j
= 0; j
< 32; ++j
)
343 hi
[j
] = parity(i
& T1
[j
]);
345 for(; tail
>= table
; --tail
) {
346 for(j
= 0; j
< 3; ++j
) {
348 *tail
|= parity((i
& C1
[j
]) ^ (*tail
& C2
[j
]));
349 if(filter(*tail
) != oks
[29 + j
])
353 for(j
= 0; j
< 19; ++j
)
354 win
= win
<< 1 | parity(*tail
& S2
[j
]);
357 for(j
= 0; j
< 32; ++j
) {
358 win
= win
<< 1 ^ hi
[j
] ^ parity(*tail
& T2
[j
]);
359 if(filter(win
) != eks
[j
])
363 *tail
= *tail
<< 1 | parity(LF_POLY_EVEN
& *tail
);
364 sl
->odd
= *tail
^ parity(LF_POLY_ODD
& win
);
367 sl
->odd
= sl
->even
= 0;
374 /** lfsr_rollback_bit
375 * Rollback the shift register in order to get previous states
377 uint8_t lfsr_rollback_bit(struct Crypto1State
*s
, uint32_t in
, int fb
)
384 t
= s
->odd
, s
->odd
= s
->even
, s
->even
= t
;
387 out
^= LF_POLY_EVEN
& (s
->even
>>= 1);
388 out
^= LF_POLY_ODD
& s
->odd
;
390 out
^= (ret
= filter(s
->odd
)) & !!fb
;
392 s
->even
|= parity(out
) << 23;
395 /** lfsr_rollback_byte
396 * Rollback the shift register in order to get previous states
398 uint8_t lfsr_rollback_byte(struct Crypto1State
*s
, uint32_t in
, int fb
)
402 for (i = 7; i >= 0; --i)
403 ret |= lfsr_rollback_bit(s, BIT(in, i), fb) << i;
405 // unfold loop 20160112
407 ret
|= lfsr_rollback_bit(s
, BIT(in
, 7), fb
) << 7;
408 ret
|= lfsr_rollback_bit(s
, BIT(in
, 6), fb
) << 6;
409 ret
|= lfsr_rollback_bit(s
, BIT(in
, 5), fb
) << 5;
410 ret
|= lfsr_rollback_bit(s
, BIT(in
, 4), fb
) << 4;
411 ret
|= lfsr_rollback_bit(s
, BIT(in
, 3), fb
) << 3;
412 ret
|= lfsr_rollback_bit(s
, BIT(in
, 2), fb
) << 2;
413 ret
|= lfsr_rollback_bit(s
, BIT(in
, 1), fb
) << 1;
414 ret
|= lfsr_rollback_bit(s
, BIT(in
, 0), fb
) << 0;
417 /** lfsr_rollback_word
418 * Rollback the shift register in order to get previous states
420 uint32_t lfsr_rollback_word(struct Crypto1State
*s
, uint32_t in
, int fb
)
425 for (i = 31; i >= 0; --i)
426 ret |= lfsr_rollback_bit(s, BEBIT(in, i), fb) << (i ^ 24);
428 // unfold loop 20160112
430 ret
|= lfsr_rollback_bit(s
, BEBIT(in
, 31), fb
) << (31 ^ 24);
431 ret
|= lfsr_rollback_bit(s
, BEBIT(in
, 30), fb
) << (30 ^ 24);
432 ret
|= lfsr_rollback_bit(s
, BEBIT(in
, 29), fb
) << (29 ^ 24);
433 ret
|= lfsr_rollback_bit(s
, BEBIT(in
, 28), fb
) << (28 ^ 24);
434 ret
|= lfsr_rollback_bit(s
, BEBIT(in
, 27), fb
) << (27 ^ 24);
435 ret
|= lfsr_rollback_bit(s
, BEBIT(in
, 26), fb
) << (26 ^ 24);
436 ret
|= lfsr_rollback_bit(s
, BEBIT(in
, 25), fb
) << (25 ^ 24);
437 ret
|= lfsr_rollback_bit(s
, BEBIT(in
, 24), fb
) << (24 ^ 24);
439 ret
|= lfsr_rollback_bit(s
, BEBIT(in
, 23), fb
) << (23 ^ 24);
440 ret
|= lfsr_rollback_bit(s
, BEBIT(in
, 22), fb
) << (22 ^ 24);
441 ret
|= lfsr_rollback_bit(s
, BEBIT(in
, 21), fb
) << (21 ^ 24);
442 ret
|= lfsr_rollback_bit(s
, BEBIT(in
, 20), fb
) << (20 ^ 24);
443 ret
|= lfsr_rollback_bit(s
, BEBIT(in
, 19), fb
) << (19 ^ 24);
444 ret
|= lfsr_rollback_bit(s
, BEBIT(in
, 18), fb
) << (18 ^ 24);
445 ret
|= lfsr_rollback_bit(s
, BEBIT(in
, 17), fb
) << (17 ^ 24);
446 ret
|= lfsr_rollback_bit(s
, BEBIT(in
, 16), fb
) << (16 ^ 24);
448 ret
|= lfsr_rollback_bit(s
, BEBIT(in
, 15), fb
) << (15 ^ 24);
449 ret
|= lfsr_rollback_bit(s
, BEBIT(in
, 14), fb
) << (14 ^ 24);
450 ret
|= lfsr_rollback_bit(s
, BEBIT(in
, 13), fb
) << (13 ^ 24);
451 ret
|= lfsr_rollback_bit(s
, BEBIT(in
, 12), fb
) << (12 ^ 24);
452 ret
|= lfsr_rollback_bit(s
, BEBIT(in
, 11), fb
) << (11 ^ 24);
453 ret
|= lfsr_rollback_bit(s
, BEBIT(in
, 10), fb
) << (10 ^ 24);
454 ret
|= lfsr_rollback_bit(s
, BEBIT(in
, 9), fb
) << (9 ^ 24);
455 ret
|= lfsr_rollback_bit(s
, BEBIT(in
, 8), fb
) << (8 ^ 24);
457 ret
|= lfsr_rollback_bit(s
, BEBIT(in
, 7), fb
) << (7 ^ 24);
458 ret
|= lfsr_rollback_bit(s
, BEBIT(in
, 6), fb
) << (6 ^ 24);
459 ret
|= lfsr_rollback_bit(s
, BEBIT(in
, 5), fb
) << (5 ^ 24);
460 ret
|= lfsr_rollback_bit(s
, BEBIT(in
, 4), fb
) << (4 ^ 24);
461 ret
|= lfsr_rollback_bit(s
, BEBIT(in
, 3), fb
) << (3 ^ 24);
462 ret
|= lfsr_rollback_bit(s
, BEBIT(in
, 2), fb
) << (2 ^ 24);
463 ret
|= lfsr_rollback_bit(s
, BEBIT(in
, 1), fb
) << (1 ^ 24);
464 ret
|= lfsr_rollback_bit(s
, BEBIT(in
, 0), fb
) << (0 ^ 24);
469 * x,y valid tag nonces, then prng_successor(x, nonce_distance(x, y)) = y
471 static uint16_t *dist
= 0;
472 int nonce_distance(uint32_t from
, uint32_t to
)
476 dist
= malloc(2 << 16);
479 for (x
= i
= 1; i
; ++i
) {
480 dist
[(x
& 0xff) << 8 | x
>> 8] = i
;
481 x
= x
>> 1 | (x
^ x
>> 2 ^ x
>> 3 ^ x
>> 5) << 15;
484 return (65535 + dist
[to
>> 16] - dist
[from
>> 16]) % 65535;
488 static uint32_t fastfwd
[2][8] = {
489 { 0, 0x4BC53, 0xECB1, 0x450E2, 0x25E29, 0x6E27A, 0x2B298, 0x60ECB},
490 { 0, 0x1D962, 0x4BC53, 0x56531, 0xECB1, 0x135D3, 0x450E2, 0x58980}};
495 * Is an exported helper function from the common prefix attack
496 * Described in the "dark side" paper. It returns an -1 terminated array
497 * of possible partial(21 bit) secret state.
498 * The required keystream(ks) needs to contain the keystream that was used to
499 * encrypt the NACK which is observed when varying only the 3 last bits of Nr
500 * only correct iff [NR_3] ^ NR_3 does not depend on Nr_3
502 uint32_t *lfsr_prefix_ks(uint8_t ks
[8], int isodd
)
504 uint32_t *candidates
= malloc(4 << 10);
505 if(!candidates
) return 0;
508 int size
= 0, i
, good
;
510 for(i
= 0; i
< 1 << 21; ++i
) {
511 for(c
= 0, good
= 1; good
&& c
< 8; ++c
) {
512 entry
= i
^ fastfwd
[isodd
][c
];
513 good
&= (BIT(ks
[c
], isodd
) == filter(entry
>> 1));
514 good
&= (BIT(ks
[c
], isodd
+ 2) == filter(entry
));
517 candidates
[size
++] = i
;
520 candidates
[size
] = -1;
526 * helper function which eliminates possible secret states using parity bits
528 static struct Crypto1State
* check_pfx_parity(uint32_t prefix
, uint32_t rresp
, uint8_t parities
[8][8], uint32_t odd
, uint32_t even
, struct Crypto1State
* sl
)
530 uint32_t ks1
, nr
, ks2
, rr
, ks3
, c
, good
= 1;
532 for(c
= 0; good
&& c
< 8; ++c
) {
533 sl
->odd
= odd
^ fastfwd
[1][c
];
534 sl
->even
= even
^ fastfwd
[0][c
];
536 lfsr_rollback_bit(sl
, 0, 0);
537 lfsr_rollback_bit(sl
, 0, 0);
539 ks3
= lfsr_rollback_bit(sl
, 0, 0);
540 ks2
= lfsr_rollback_word(sl
, 0, 0);
541 ks1
= lfsr_rollback_word(sl
, prefix
| c
<< 5, 1);
543 nr
= ks1
^ (prefix
| c
<< 5);
546 good
&= parity(nr
& 0x000000ff) ^ parities
[c
][3] ^ BIT(ks2
, 24);
547 good
&= parity(rr
& 0xff000000) ^ parities
[c
][4] ^ BIT(ks2
, 16);
548 good
&= parity(rr
& 0x00ff0000) ^ parities
[c
][5] ^ BIT(ks2
, 8);
549 good
&= parity(rr
& 0x0000ff00) ^ parities
[c
][6] ^ BIT(ks2
, 0);
550 good
&= parity(rr
& 0x000000ff) ^ parities
[c
][7] ^ ks3
;
556 /** lfsr_common_prefix
557 * Implentation of the common prefix attack.
558 * Requires the 28 bit constant prefix used as reader nonce (pfx)
559 * The reader response used (rr)
560 * The keystream used to encrypt the observed NACK's (ks)
561 * The parity bits (par)
562 * It returns a zero terminated list of possible cipher states after the
563 * tag nonce was fed in
566 struct Crypto1State
* lfsr_common_prefix(uint32_t pfx
, uint32_t rr
, uint8_t ks
[8], uint8_t par
[8][8])
568 struct Crypto1State
*statelist
, *s
;
569 uint32_t *odd
, *even
, *o
, *e
, top
;
571 odd
= lfsr_prefix_ks(ks
, 1);
572 even
= lfsr_prefix_ks(ks
, 0);
574 s
= statelist
= malloc((sizeof *statelist
) << 21);
575 if(!s
|| !odd
|| !even
) {
582 for(o
= odd
; *o
+ 1; ++o
)
583 for(e
= even
; *e
+ 1; ++e
)
584 for(top
= 0; top
< 64; ++top
) {
586 *e
+= (!(top
& 7) + 1) << 21;
587 s
= check_pfx_parity(pfx
, rr
, par
, *o
, *e
, s
);
590 s
->odd
= s
->even
= 0;