10.2. Stream and Block Ciphers

Definition 101. Let E be an encipherment algorithm, and let E_k(b) be the encipherment of message b with key k. Let a message m = b₁b₂ …, where each b_i is of a fixed length. Then a block cipher is a cipher for which E_k(m) = E_k(b₁)E_k(b₂) ….

EXAMPLE: The DES is a block cipher. It breaks the message into 64-bit blocks and uses the same 56-bit key to encipher each block.

Other ciphers use a nonrepeating stream of key elements to encipher characters of a message.

Definition 102. Let E be an encipherment algorithm, and let E_k(b) be the encipherment of message b with key k. Let a message m = b₁b₂ …, where each b_i is of a fixed length, and let k = k₁k₂…. Then a stream cipher is a cipher for which E_k(m) = E_k1(b₁)E_k2(b₂) ….

If the key stream k of a stream cipher repeats itself, it is a periodic cipher.

EXAMPLE: The Vigenère cipher (see Section 8.2.2.1) is a stream cipher. Take bi to be a character of the message and ki to be a character of the key. This cipher is periodic, because the key is of finite length, and should the key be shorter than the message, the key is repeated. The one-time pad is also a stream cipher but is not periodic, because the key stream never repeats.

10.2.1. Stream Ciphers

The one-time pad is a cipher that can be proven secure (see Section 8.2.2.2, "One-Time Pad"). Bit-oriented ciphers implement the one-time pad by exclusive-oring each bit of the key with one bit of the message. For example, if the message is 00101 and the key is 10010, the ciphertext is 01||00||10||01||10 or 10111. But how can one generate a random, infinitely long key?

10.2.1.1 Synchronous Stream Ciphers

To simulate a random, infinitely long key, synchronous stream ciphers generate bits from a source other than the message itself. The simplest such cipher extracts bits from a register to use as the key. The contents of the register change on the basis of the current contents of the register.

Definition 103. An n-stage linear feedback shift register (LFSR) consists of an n-bit register r = r₀…r_n1 and an n-bit tap sequence t = t₀…t_n1. To obtain a key bit, r_n1 is used, the register is shifted one bit to the right, and the new bit r₀t_0…r_n1t_n1 is inserted.

EXAMPLE: Let the tap sequence for a four-stage LFSR be 1001, and let the initial value of the register be 0010. The key bits extracted, and the values in the register, are and the cycle repeats. The key stream that this LFSR produces has a period of 15 and is 010001111010110. Current register Key New bit New register 0010 0 01001001 = 0000 = 0 0001 0001 1 01000011 = 0001 = 1 1000 1000 0 11000001 = 1000 = 1 1100 1100 0 11100001 = 1000 = 1 1110 1110 0 11101001 = 1000 = 1 1111 1111 1 11101011 = 1001 = 0 0111 0111 1 01101011 = 0001 = 1 1011 1011 1 11001011 = 1001 = 0 0101 0101 1 01100011 = 0001 = 1 1010 1010 0 11001001 = 1000 = 1 1101 1101 1 11100011 = 1001 = 0 0110 0110 0 01101001 = 0000 = 0 0011 0011 1 01001011 = 0001 = 1 1001 1001 1 11000011 = 1001 = 0 0100 0100 0 01100001 = 0000 = 0 0010 0010 0 01001001 = 0000 = 0 0001

The LFSR method is an attempt to simulate a one-time pad by generating a long key sequence from a little information. As with any such attempt, if the key is shorter than the message, breaking part of the ciphertext gives the cryptanalyst information about other parts of the ciphertext. For an LFSR, a known plaintext attack can reveal parts of the key sequence. If the known plaintext is of length 2n, the tap sequence for an n-stage LFSR can be determined completely.

Nonlinear feedback shift registers do not use tap sequences; instead, the new bit is any function of the current register bits.

Definition 104. An n-stage nonlinear feedback shift register (NLFSR) consists of an n-bit register r = r₀…r_n1. To obtain a key bit, r_n1 is used, the register is shifted one bit to the right, and the new bit is set to f(r₀…r_n1), where f is any function of n inputs.

EXAMPLE: Let the function f for a four-stage NLFSR be f(r0…rn1) = (r0 and r2) or r3, and let the initial value of the register be 1100. The key bits extracted, and the values in the register, are Current register Key New bit New register 1100 0 f(1, 1, 0, 0) = (1 and 0) or 0 = 0 0110 0110 0 f(0, 1, 1, 0) = (0 and 1) or 0 = 0 0011 0011 1 f(0, 0, 1, 1) = (0 and 1) or 1 = 1 1001 1001 1 f(1, 0, 0, 1) = (1 and 0) or 1 = 1 1100 1100 0 f(1, 1, 0, 0) = (1 and 0) or 0 = 0 0110 0110 0 f(0, 1, 1, 0) = (0 and 1) or 0 = 0 0011 0011 1 f(0, 0, 1, 1) = (0 and 1) or 1 = 1 1001 1001 1 f(1, 0, 0, 1) = (1 and 0) or 1 = 1 1100 1100 0 f(1, 1, 0, 0) = (1 and 0) or 0 = 0 0110 0110 0 f(0, 1, 1, 0) = (0 and 1) or 0 = 0 0011 and the cycle repeats. The key stream that this NLFSR produces has a period of 4 and is 0011.

NLFSRs are not common because there is no body of theory about how to build NLFSRs with long periods. By contrast, it is known how to design n-stage LFSRs with a period of 2ⁿ 1, and that period is maximal.

A second technique for eliminating linearity is called output feedback mode. Let E be an encipherment function. Define k as a cryptographic key, and define r as a register. To obtain a bit for the key, compute E_k(r) and put that value into the register. The rightmost bit of the result is exclusive-or'ed with one bit of the message. The process is repeated until the message is enciphered. The key k and the initial value in r are the keys for this method. This method differs from the NLFSR in that the register is never shifted. It is repeatedly enciphered.

A variant of output feedback mode is called the counter method. Instead of using a register r, simply use a counter that is incremented for every encipherment. The initial value of the counter replaces r as part of the key. This method enables one to generate the ith bit of the key without generating the bits 0…i 1. If the initial counter value is i₀, set the register to i + i₀. In output feedback mode, one must generate all the preceding key bits.

10.2.1.2 Self-Synchronous Stream Ciphers

Self-synchronous ciphers obtain the key from the message itself. The simplest self-synchronous cipher is called an autokey cipher and uses the message itself for the key.

EXAMPLE: The following is an autokey version of the Vigen•re cipher, with the key drawn from the plaintext. key XTHEBOYHASTHEBA plaintext THEBOYHASTHEBAG ciphertext QALFPNFHSLALFCT Contrast this with the example on page 103. The key there is VIG, and the resulting ciphertext contains two three-character repetitions.

The problem with this cipher is the selection of the key. Unlike a one-time pad, any statistical regularities in the plaintext show up in the key. For example, the last two letters of the ciphertext associated with the plaintext word THE are always AL, because H is enciphered with the key letter T and E is enciphered with the key letter H. Furthermore, if the analyst can guess any letter of the plaintext, she can determine all successive plaintext letters.

An alternative is to use the ciphertext as the key stream. A good cipher will produce pseudorandom ciphertext, which approximates a random one-time pad better than a message with nonrandom characteristics (such as a meaningful English sentence).

EXAMPLE: The following is an autokey version of the Vigenére cipher, with the key drawn from the ciphertext. key XQXBCQOVVNGNRTT plaintext THEBOYHASTHECAT ciphertext QXBCQOVVNGNRTTM This eliminates the repetition (ALF) in the preceding example.

This type of autokey cipher is weak, because plaintext can be deduced from the ciphertext. For example, consider the first two characters of the ciphertext, QX. The X is the ciphertext resulting from enciphering some letter with the key Q. Deciphering, the unknown letter is H. Continuing in this fashion, the analyst can reconstruct all of the plaintext except for the first letter.

A variant of the autokey method, cipher feedback mode, uses a shift register. Let E be an encipherment function. Define k as a cryptographic key and r as a register. To obtain a bit for the key, compute E_k(r). The rightmost bit of the result is exclusive-or'ed with one bit of the message, and the other bits of the result are discarded. The resulting ciphertext is fed back into the leftmost bit of the register, which is right shifted one bit. (See Figure 10-1.)

Cipher feedback mode has a self-healing property. If a bit is corrupted in transmission of the ciphertext, the next n bits will be deciphered incorrectly. But after n uncorrupted bits have been received, the shift register will be reinitialized to the value used for encipherment and the ciphertext will decipher properly from that point on.

As in the counter method, one can decipher parts of messages enciphered in cipher feedback mode without deciphering the entire message. Let the shift register contain n bits. The analyst obtains the previous n bits of ciphertext. This is the value in the shift register before the bit under consideration was enciphered. The decipherment can then continue from that bit on.

10.2.2. Block Ciphers

Block ciphers encipher and decipher multiple bits at once, rather than one bit at a time. For this reason, software implementations of block ciphers run faster than software implementations of stream ciphers. Errors in transmitting one block generally do not affect other blocks, but as each block is enciphered independently, using the same key, identical plaintext blocks produce identical ciphertext blocks. This allows the analyst to search for data by determining what the encipherment of a specific plaintext block is. For example, if the word INCOME is enciphered as one block, all occurrences of the word produce the same ciphertext.

EXAMPLE: Consider a banking database with two records: MEMBER: HOLLY INCOME $100,000 MEMBER: HEIDI INCOME $100,000 Suppose the encipherment of this data under a block cipher is ABCQZRME GHQMRSIB CTXUVYSS RMGRPFQN ABCQZRME ORMPABRZ CTXUVYSS RMGRPFQN If an attacker determines who these records refer to, and that CTXUVYSS is the encipherment of the INCOME keyword, he will know that Holly and Heidi have the same income.

To prevent this type of attack, some information related to the block's position is inserted into the plaintext block before it is enciphered. The information can be bits from the preceding ciphertext block [311] or a sequence number [502]. The disadvantage is that the effective block size is reduced, because fewer message bits are present in a block.

Cipher block chaining does not require the extra information to occupy bit spaces, so every bit in the block is part of the message. Before a plaintext block is enciphered, that block is exclusive-or'ed with the preceding ciphertext block. In addition to the key, this technique requires an initialization vector with which to exclusive-or the initial plaintext block. Taking E_k to be the encipherment algorithm with key k, and I to be the initialization vector, the cipher block chaining technique is

c₀ = E_k(m₀ I)

c_i = E_k(m_i c_i1) for i > 0

10.2.2.1 Multiple Encryption

Other approaches involve multiple encryption. Using two keys k and k' to encipher a message as c = E_k' (E_k(m)) looks attractive because it has an effective key length of 2n, whereas the keys to E are of length n. However, Merkle and Hellman [624] have shown that this encryption technique can be broken using 2ⁿ⁺¹ encryptions, rather than the expected 2²ⁿ (see Exercise 3).

Using three encipherments improves the strength of the cipher. There are several ways to do this. Tuchman [908] suggested using two keys k and k':

c = E_k(D_k' (E_k(m)))

This mode, called Encrypt-Decrypt-Encrypt (EDE) mode, collapses to a single encipherment when k = k'. The DES in EDE mode is widely used in the financial community and is a standard (ANSI X9.17 and ISO 8732). It is not vulnerable to the attack outlined earlier. However, it is vulnerable to a chosen plaintext and a known plaintext attack. If b is the block size in bits, and n is the key length, the chosen plaintext attack takes O(2ⁿ) time, O(2ⁿ) space, and requires 2ⁿ chosen plaintexts. The known plaintext attack requires p known plaintexts, and takes O(2^n+b/p) time and O(p) memory.

A second version of triple encipherment is the triple encryption mode [624]. In this mode, three keys are used in a chain of encipherments.

c = E_k(E_k' (E_{k' '} (m)))

The best attack against this scheme is similar to the attack on double encipherment, but requires O(2²ⁿ) time and O(2ⁿ) memory. If the key length is 56 bits, this attack is computationally infeasible.