Page 141 - Ellingham, Mark, Mariusz Meszka, Primož Moravec, Enes Pasalic, 2014. 2014 PhD Summer School in Discrete Mathematics. Koper: University of Primorska Press. Famnit Lectures, 3.
P. 141
s Pasalic: Symmetric Key Cryptography and its Relation to Graph Theory 129
The sequence is of maximum length 15 = 24 − 1 and contains exactly 2k −1 = 8 ones and
2k −1 − 1 zeros, why ? Check what happens if we use irreducible polynomial C (x ) = x 4 +
x3+x2+x +1 !
However, any sequence generated by a finite-state machine has a finite linear complexity.
Moreover, due to Elwyn R. Berlekamp and James L. Massey [5], there exists an efficient
polynomial-time synthesis algorithm, which computes the linear complexity of a given
binary sequence. When the length L of LFSR is known then a sequence of length 2L
is required to compute the connection polynomial, either using the Berlekamp-Massey
algorithm or a direct matrix equation. If L is not known, then the Berlekamp-Massey
algorithm can be used to determine L and the connection polynomial. In either case the
adversary must obtain a subsequence of length 2L.
In reference to Figure 4.2, we assume that an adversary mounts a known or chosen-
plaintext attack on additive binary stream cipher where the running-key generator is im-
plemented by using an LFSR. Then the adversary can obtain the subsequence of z of
length L, by computing z i = mi ⊕ ci , i = 0, . . . , L − 1 (since mi are known). Then, an LFSR
of length L, with the connection polynomial computed with the Berlekamp-Massey al-
gorithm, can be initialized with this subsequence to generate the remainder of the se-
quence z.
Thus, a necessary but not sufficient condition for any keystream generator is the re-
quirement for a large linear complexity. This cannot be achieved using a single LFSR,
and general methods for destroying the linear properties of LFSRs are:
• using a nonlinear combining function at the outputs of several LFSRs;
• using a nonlinear filtering function on the contents of a single LFSR;and
• using the output of one/several LFSRs to control clocking of one/several LFSRs.
As mentioned earlier the first two methods take advantage of a Boolean function to
introduce the nonlinearity to the keystream. A general construction of a nonlinear com-
bination generator is illustrated in Figure 4.6, where for the sake of generality we consider
F: n → m , for m ≥ 1.
2 2
In this set up the outputs of n LFSRs, x (1), . . . , x (n) are used as the inputs to a nonlinear
vectorial Boolean function, denoted F , and the keystream sequence is then generated by
this function. More formally, zi = fi (x (1) , . . . , x (n ) ), and the function F : n → m (actually
i i 2 2
an S-box) is a collection of m Boolean functions F = ( f 1, . . . , f m ). A Boolean function
f (x1, . . . , xn ) can be represented as the output column of its truth table f , i.e., a binary
string of length 2n , f = [f (0, 0, · · · , 0), f (1, 0, · · · , 0), f (0, 1, · · · , 0), . . . , f (1, 1, · · · , 1)].
The truth table representation may be suitable for Boolean function in small number
of variables. Thus, for moderate to large values of n , f ∈ n is usually represented by its
The sequence is of maximum length 15 = 24 − 1 and contains exactly 2k −1 = 8 ones and
2k −1 − 1 zeros, why ? Check what happens if we use irreducible polynomial C (x ) = x 4 +
x3+x2+x +1 !
However, any sequence generated by a finite-state machine has a finite linear complexity.
Moreover, due to Elwyn R. Berlekamp and James L. Massey [5], there exists an efficient
polynomial-time synthesis algorithm, which computes the linear complexity of a given
binary sequence. When the length L of LFSR is known then a sequence of length 2L
is required to compute the connection polynomial, either using the Berlekamp-Massey
algorithm or a direct matrix equation. If L is not known, then the Berlekamp-Massey
algorithm can be used to determine L and the connection polynomial. In either case the
adversary must obtain a subsequence of length 2L.
In reference to Figure 4.2, we assume that an adversary mounts a known or chosen-
plaintext attack on additive binary stream cipher where the running-key generator is im-
plemented by using an LFSR. Then the adversary can obtain the subsequence of z of
length L, by computing z i = mi ⊕ ci , i = 0, . . . , L − 1 (since mi are known). Then, an LFSR
of length L, with the connection polynomial computed with the Berlekamp-Massey al-
gorithm, can be initialized with this subsequence to generate the remainder of the se-
quence z.
Thus, a necessary but not sufficient condition for any keystream generator is the re-
quirement for a large linear complexity. This cannot be achieved using a single LFSR,
and general methods for destroying the linear properties of LFSRs are:
• using a nonlinear combining function at the outputs of several LFSRs;
• using a nonlinear filtering function on the contents of a single LFSR;and
• using the output of one/several LFSRs to control clocking of one/several LFSRs.
As mentioned earlier the first two methods take advantage of a Boolean function to
introduce the nonlinearity to the keystream. A general construction of a nonlinear com-
bination generator is illustrated in Figure 4.6, where for the sake of generality we consider
F: n → m , for m ≥ 1.
2 2
In this set up the outputs of n LFSRs, x (1), . . . , x (n) are used as the inputs to a nonlinear
vectorial Boolean function, denoted F , and the keystream sequence is then generated by
this function. More formally, zi = fi (x (1) , . . . , x (n ) ), and the function F : n → m (actually
i i 2 2
an S-box) is a collection of m Boolean functions F = ( f 1, . . . , f m ). A Boolean function
f (x1, . . . , xn ) can be represented as the output column of its truth table f , i.e., a binary
string of length 2n , f = [f (0, 0, · · · , 0), f (1, 0, · · · , 0), f (0, 1, · · · , 0), . . . , f (1, 1, · · · , 1)].
The truth table representation may be suitable for Boolean function in small number
of variables. Thus, for moderate to large values of n , f ∈ n is usually represented by its
