4
$\begingroup$

Suppose I have access to an LFSR generator output used in a radio communications system, with the LFSR being used to authenticate devices. The system cycles an internal unknown length LFSR (greater than 32 bits) an unknown but constant number of times and returns the truncated upper 32 bits, with the lower bits being unknown.

I do not know the starting condition or the polynomial, but I can read the truncated output from this system as it transmits. Using this data alone, can I predict the next output using an algorithm such as Berlekamp-Massey algorithm?

I know that Berlekamp-Massey can solve given 2n captured bits, but do these have to be completely consecutive, or can they be a scattered "picture" of the output? Do I need to know the size of the generator to use Berlekamp-Massey?

I'm thinking of implementing this in a communications system: power consumption and complexity is key here, and an LFSR uses considerably less power and flash memory than a full AES or SHA authentication system, but I'm not sure if it will be easy to predict. (The idea is the receiver will refuse to acknowledge packets an incorrect LFSR, preventing the device being "impersonated".)

$\endgroup$
4
$\begingroup$

It is very easy to predict and should not be used as a main cryptographic component on its own.

Firstly, many $k-$decimations $s_{kt}$ of LFSR sequences (those with $gcd(k,2^n-1)=1$) are shifted LFSR sequences themselves so this can be used for prediction.

If you can find a template $T=\{0,t_1,\ldots,t_{n-1}\}$ (with $0<t_1<t_2<\cdots<t_{n-1}$ such that the samples you have of the LFSR sequence $(s_t)$ cover $n+1$ shifts of this template you can set up a linear system and solve for the recurrence. In fact assuming $n=3$ one can (Berlekamp Massey is more efficient of course, this would need Gaussian elimination) set up the system

$$c_0 x_t + c_1 x_{t+1} + c_2 x_{t+2}=x_{t+3}\\ c_0 x_{t+1} + c_1 x_{t+2} + c_2 x_{t+3}=x_{t+4}\\ c_0 x_{t+2} + c_1 x_{t+3} + c_2 x_{t+4}=x_{t+5}$$

and solve for the LFSR coefficients $c_i$. For the template I mentioned, a similar system needs to be solved. This case is the template $T=\{0,1,2\}$ with shifts also $\{0,1,2\}.$

$\endgroup$
  • $\begingroup$ Thanks for the information. I can't pretend to have a strong mathematical background here. Given the low processing capability are there any algorithms you would suggest as a way of authenticating the devices? The idea here is to make it hard to impersonate another device, though absolute security isn't critical, I would like to make it as hard to break as practically possible. There's a delay of about 30 minutes between packets so currently it would take 3(?) iterations or 90 minutes to gather enough information to break the protocol. I'd like to extend that to 10+ iters. Thanks $\endgroup$ – Thomas O Aug 30 '15 at 12:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.