Stream Ciphers - Understanding Cryptography - page 45

Eq. (2.1) is a description of the relationship of the unknown key bits p i and the
key stream output. We repeat the equation here for convenience:

m − 1
j =0 p j · s i + j mod 2;

s i + m ≡ s i , p j ∈{ 0 , 1 } ; i = 0 , 1 , 2 ,...

Note that we get a different equation for every value of i . Moreover, the equations
are linearly independent. With this knowledge, Oscar can generate m equations for
the first m values of i :

i = 0 , s m ≡ p m − 1 s m − 1 + ... + p 1 s 1 + p 0 s 0 mod 2

i = 1 , s m +1 ≡ p m − 1 s m + ... + p 1 s 2 + p 0 s 1 mod 2

(2.2)

. . . . .

i = m − 1 , s 2 m − 1 ≡ p m − 1 s 2 m − 2 + ... + p 1 s m + p 0 s m − 1 mod 2

He has now m linear equations in m unknowns p 0 , p 1 ,..., p m − 1 . This system can
easily be solved by Oscar using Gaussian elimination, matrix inversion or any other
algorithm for solving systems of linear equations. Even for large values of m ,this
can be done easily with a standard PC.
This situation has major consequences: as soon as Oscar knows 2 m output bits
of an LFSR of degree m ,the p i coefficients can exactly be constructed by merely
solving a system of linear equations . Once he has computed these feedback coef-
ficients, he can “build” the LFSR and load it with any m consecutive output bits
that he already knows. Oscar can now clock the LFSR and produce the entire output
sequence. Because of this powerful attack, LFSRs by themselves are extremely inse-
cure! They are a good example of a PRNG with good statistical properties but with
terrible cryptographical ones. Nevertheless, all is not lost. There are many stream
ciphers which use combinations of several LFSRs to build strong cryptosystems.
The cipher Trivium in the next section is an example.

2.3.3 Trivium

Trivium is a relatively new stream cipher which uses an 80-bit key. It is based on a
combination of three shift registers. Even though these are feedback shift registers,
there are nonlinear components used to derive the output of each register, unlike the
LFSRs that we studied in the previous section.

Description of Trivium

As shown in Fig. 2.8, at the heart of Trivium are three shift registers, A , B and C .
The lengths of the registers are 93, 84 and 111, respectively. The XOR-sum of all
three register outputs forms the key stream s i . A specific feature of the cipher is that