A block cipher encrypts large blocks of data using a fixed key. A stream cipher, on the other hand, encrypts small blocks of data (typically bits or bytes) using different keys. The security of a stream cipher stems from the unpredictability of guessing the keys in the key stream. Here, we deal with stream ciphers that encrypt bit-by-bit.
A stream cipher F encrypts a plaintext m = m1m2 . . . ml to a ciphertext c = c1c2 . . . cl using a key stream k = k1k2 . . . kl, where each mi, ci, . F uses a function that yields f(mi, ki) = ci. In order to effect unique decryption, the map , μ ↦ f(μ, k), must be a bijection for each . F encrypts and decrypts bit-by-bit using the formulas ci = fki(mi) and . |
Generating a truly random key stream of arbitrary length is a difficult problem. Moreover, the same key stream is used for decryption and has to be reproduced at the recipient’s end. In view of these difficulties, Vernam’s one-time pad is used only very rarely.
A practical solution is to use a pseudorandom key stream k1, k2, k3, . . . generated from a secret key J of fixed small length. The bits in the pseudorandom stream should be sufficiently unpredictable and the length of J adequately large, so as to preclude the possibility of mounting a successful attack in feasible time.
Depending on how the key stream is generated from J, stream ciphers can be broadly classified in two categories. In a synchronous stream cipher, each key in the key stream is generated independent of any plaintext or ciphertext bit, whereas in a self-synchronizing (or asynchronous) stream cipher each key in the stream is generated based only on J and a fixed number of previous ciphertext bits. Algorithms A.16 and A.17 explain the workings of these two classes of stream ciphers.
Input: The message m = m1m2 . . . ml, the secret key J and a (not necessarily secret) initial state S of the key stream generator. Output: The ciphertext c = c1c2 . . . cl. Steps: s0 := S. /* Initialize the state of the key stream generator */ |
Input: The message m = m1m2 . . . ml, the secret key J and a (not necessarily secret) initial state (c–t+1, c–t+2, . . . , c0). Output: The ciphertext c = c1c2 . . . cl. Steps: for i = 1, . . . , l { |
A block cipher in the OFB mode works like a synchronous stream cipher, whereas a block cipher in the CFB mode like an asynchronous stream cipher.
Linear feedback shift registers (LFSRs), being suitable for hardware implementation and possessing good cryptographic properties, are widely used as basic building blocks for many stream ciphers. Figure A.2 depicts an LFSR L with d stages or delay elements D0, D1, . . . , Dd–1, each capable of storing one bit. The state of the LFSR is described by the d-tuple s := (s0, s1, . . . , sd–1), where si is the bit stored in Di. It is often convenient to treat s as the column vector (s0 s1 . . . sd–1)t.
There are d control bits a0, a1, . . . , ad–1. The working of the LFSR is governed by a clock. At every clock pulse the bits stored in the delay elements are bit-wise AND-ed with the respective control bits and the AND gate outputs are XOR-ed to obtain the bit sd. The bit s0 stored in D0 is delivered to the output. Finally, for each the delay element Di sets its stored bit to si+1, that is, the register experiences a right shift by one bit with the feedback bit sd filling up the leftmost delay element.
Thus, a clock pulse changes the state of the LFSR from s := (s0, s1, . . . , sd–1) to t := (t0, t1, . . . , td–1), where s and t are related as:
If s and t are treated as column vectors, this can be compactly represented as
Equation A.4
where the transition matrix ΔL is given by
Equation A.5
When the LFSR L is initialized to a non-zero state, the bit stream output by it can be used as a pseudorandom bit sequence. For a given set of control bits a0, . . . , ad–1, the next state of L is uniquely determined by its previous state only. Since L has only finitely many (2d – 1) non-zero states, the output bit sequence of L must be (eventually) periodic. For cryptographic use, the period of the bit sequence should be as large as possible. If the period is maximum possible, namely 2d – 1, L is called a maximum-length LFSR.
Many properties of the LFSR L can be explained in terms of its connection polynomial defined as:
Equation A.6
For example, assume that a0 = 1, so that deg CL(X) = d. Assume further that CL(X) is irreducible (over ). Consider the extension of , represented as , where . It turns out that if x is a generator of the cyclic group , then L is a maximum-length LFSR. In this case, the polynomial CL(X) is called a primitive polynomial of .[3]
[3] A primitive polynomial defined in this way has nothing to do with a primitive polynomial over a UFD, defined in Exercise 2.54. Mathematicians often go for such multiple definitions of the same terms and phrases.
The bit sequence output by an LFSR L can be used as the key stream k1k2 . . . kl in order encrypt a plaintext stream m1m2 . . . ml to the ciphertext stream c1c2 . . . cl with ci := mi ⊕ ki. The number d of stages in L should be chosen reasonably large and the control bits a0, . . . , ad–1 should be kept secret. The initial state of L may or may not be a secret. For suitable choices of a0, . . . , ad–1, the output sequences from L possess good statistical properties and hence L appears to be an efficient key stream generator.
Unfortunately, such a key stream generator is vulnerable to a known-plaintext attack as follows. Suppose that mi and ci are known for i = 1, 2, . . . , 2d. One can easily compute ki = mi⊕ci for all these i. Let si := (ki, ki+1, . . . , ki+d–1) denote the state of L while outputting ci. By Congruence (A.4), si+1 ≡ ΔLsi (mod 2) for i = 1, 2, . . . , d. Define the d × d matrices S := (s1 s2 . . . sd) and T := (s2 s3 . . . sd+1), where si are treated as column vectors as before. We then have T ≡ ΔLS (mod 2). If S is invertible modulo 2, then ΔL and hence the secret control bits can be easily computed. In order to avoid this known-plaintext attack, one should introduce some non-linearity in the LFSR outputs.
A non-linear combination generator combines the output bits u1, u2, . . . , ur from r LFSRs by a non-linear function in order to generate the key . The Geffe generator of Figure A.3 gives a well-known example. It uses the non-linear function , that is, (mod 2).
A non-linear filter generator generates the key as k = ψ(s0, s1, . . . , sd–1), where s0, . . . , sd–1 are the bits stored in the delay elements of a single LFSR and where ψ is a non-linear function.
Several other ad hoc schemes can destroy the linearity of an LFSR’s output. The shrinking generator, for example, uses two LFSRs L1 and L2. Both L1 and L2 are simultaneously clocked. If the output of L1 is 1, the output of L2 goes to the key stream, whereas if the output of L1 is 0, the output of L2 is discarded. The resulting key stream is an irregularly (and non-linearly) decimated subsequence of the output sequence of L2.
The non-linear function ( or ψ) eliminates the chance of mounting the straightforward known-plaintext attack described above. However, for polynomial non-linearities certain algebraic attacks are known, for example, see Courtois and Pieprzyk [67, 66].[4] Solving non-linear polynomial equations is usually more difficult than solving linear equations, but ample care should be taken to avoid accidental encounters with easily solvable systems. Complacency is a word ever excluded from a cryptologer’s world.
[4] Visit the Internet site http://www.cryptosystem.net/ for more papers in related areas.
A.12 | For each of the two classes of stream ciphers (Algorithms A.16, A.17) discuss the effects on decryption of
of a ciphertext bit during transmission. |
A.13 | Suppose that the LFSR L of Figure A.4 is initialized to the state (1, 0, 0, 0). Derive the sequence of state transitions of the LFSR, and hence determine the output bit sequence of L. Argue that L is a maximum-length LFSR. Verify (according to the definition) that the connection polynomial CL(X) is primitive.
Figure A.4. An LFSR with four stages
|
A.14 | Let ΔL and CL(X) be as in Equations (A.5) and (A.6). Show that:
|
A.15 | Let L be an LFSR with connection polynomial CL(X). Further let , , denote a power series[5] over . Show that L generates the (infinite) bit sequence s0, s1, s2, . . . if and only if the product CL(X)S(X) modulo 2 is a polynomial of degree < d.
|
A.16 | Let σ = s0s1 . . . sd–1 ≠ 00 . . . 0 be a bit string of length d ≥ 1. The linear complexity L(σ) of σ is defined to be the length of the shortest LFSR that generates σ as the leftmost part of its output (after it is initialized to a suitable state). Prove that:
|
A.17 | Assume that the three LFSR outputs u1, u2, u3 in the Geffe generator are uniformly distributed. Show that Pr(k = u1) = 3/4 = Pr(k = u3). Thus, partial information about the internal details of the Geffe generator is leaked out in the key stream. |
3.133.133.233