Cipher Block Chaining Mode

Cipher Block Chaining Mode ( CBC Mode ) is an operating mode in which block ciphers can be operated. Before a plaintext block is encrypted , it is first linked to the ciphertext block generated in the previous step using XOR (exclusive or). The mode was published in 1976 by William F. Ehrsam, Carl HW Meyer, John L. Smith, and Walter L. Tuchman.

General

The structure of the encryption in CBC mode is shown in the following figure:

This diagram can also be expressed mathematically in formulas, denote the encryption function with the key , be the associated decryption function. Designate the i-th plaintext block, the i-th ciphertext block and be the initialization vector; usually is defined. In addition, denote the logical XOR. Then the encryption in CBC mode is defined recursively as follows : ${\ displaystyle E_ {K}}$ ${\ displaystyle K}$ ${\ displaystyle D_ {K}}$ ${\ displaystyle P_ {i}}$ ${\ displaystyle C_ {i}}$ ${\ displaystyle IV}$ ${\ displaystyle C_ {0} = IV}$ ${\ displaystyle \ oplus}$

${\ displaystyle \ forall i \ in \ mathbb {N} ^ {+}: C_ {i} = E_ {K} (P_ {i} \ oplus C_ {i-1})}$

The structure of the decryption in CBC mode is shown in the following figure:

The associated decryption, however, is not recursive in CBC mode and has the same designations as above:

${\ displaystyle \ forall i \ in \ mathbb {N} ^ {+}: P_ {i} = D_ {K} (C_ {i}) \ oplus C_ {i-1}}$

Either a time stamp or a random sequence of numbers is used as the initialization vector (IV) . Some applications also use a predictable, simple ascending number, but this is not certain, because people outside an undesirably watermarking attack ( watermark attack can execute) to such data. The dm-crypt module uses the ESS process to generate the IV .

For the security of the algorithm it is not necessary to transmit the initialization vector secretly.

The CBC mode has some important advantages:

Plain text samples are destroyed.
Identical plain text blocks result in different ciphertexts.
Various attacks (time memory tradeoff and plain text attacks) are made more difficult.

Since a ciphertext block only depends on the previous block, a damaged ciphertext block, such as a bit error during data transmission, does not cause too much damage during decryption, because only the plaintext block concerned and the subsequent plaintext block are incorrectly deciphered. This can be seen directly from the definition of the decryption and the above figure, since a damaged ciphertext block only affects the plaintext blocks and and does not spread further without restriction. Nevertheless, this limited multiplication of only a single bit error in the cipher with CBC can make forward error correction of the plain text difficult or impossible. Likewise, a damaged initialization vector does not cause too much damage during decryption, since it only damages the plaintext block . ${\ displaystyle C_ {i}}$ ${\ displaystyle P_ {i}}$ ${\ displaystyle P_ {i + 1}}$ ${\ displaystyle P_ {1}}$

The CBC mode is much safer than the ECB mode, especially if you don't have any random texts. Our language and other files, such as. B. video files are by no means random, which is why the ECB mode is dangerous.

example

Plain text: 01 10
Divided into blocks: 01 = , 10 = ${\ displaystyle B_ {1}}$ ${\ displaystyle B_ {2}}$
key: 11 = k
Init. Vector (IV): 01

For simplicity, as the encryption function , the binary addition and as a decryption function uses the binary subtraction. ${\ displaystyle E}$ ${\ displaystyle D}$

Encryption

Block 1:

${\ displaystyle B_ {1} \ oplus IV = 01 \ oplus 01 = 00 = C_ {1} '}$
${\ displaystyle E_ {k} (C_ {1} ') = C_ {1}' + k = 00 + 11 = 11 = C_ {1}}$

Block 2:

${\ displaystyle B_ {2} \ oplus C_ {1} = 10 \ oplus 11 = 01 = C_ {2} '}$
${\ displaystyle E_ {k} (C_ {2} ') = C_ {2}' + k = 01 + 11 = 00 = C_ {2}}$

Encrypted text:

${\ displaystyle C_ {1} C_ {2} = 1100}$

If you look at the encryption of , you can see that this is required. In general, this means that the cipher block is required for encryption . A parallelization of the encryption process is therefore not possible. ${\ displaystyle B_ {2}}$ ${\ displaystyle C_ {1}}$ ${\ displaystyle B_ {i}}$ ${\ displaystyle C_ {i-1}}$

Decryption

Block 1:

${\ displaystyle D_ {k} (C_ {1}) = C_ {1} -k = 11-11 = 00 = C_ {1} '}$
${\ displaystyle C_ {1} '\ oplus IV = 00 \ oplus 01 = 01 = B_ {1}}$

Block 2:

${\ displaystyle D_ {k} (C_ {2}) = C_ {2} -k = 00-11 = 01 = C_ {2} '}$
${\ displaystyle C_ {2} '\ oplus C1 = 01 \ oplus 11 = 10 = B_ {2}}$

Plain text:

${\ displaystyle B_ {1} B_ {2} = 0110}$

If you look at the decryption of , you can see that it is not required for this, only . In general, this means that only is required for decryption . This enables the decryption process to be carried out in parallel. ${\ displaystyle C_ {2}}$ ${\ displaystyle B_ {1}}$ ${\ displaystyle C_ {1}}$ ${\ displaystyle C_ {i}}$ ${\ displaystyle C_ {i-1}}$

Integrity assurance with CBC, CBC-MAC

Structure for the CBC-MAC calculation

CBC can also be used to ensure integrity by setting the initialization vector to zero and appending the last block encrypted with CBC as a MAC (the so-called CBC-MAC or CBC residual value) to the original unencrypted message and sending it together with this MAC. With the help of the CBC algorithm, the recipient can calculate the CBC-MAC of the received message and now compare whether the value that has just been calculated agrees with the one attached to the message. If a message encrypted with CBC is to be secured with a CBC-MAC, the same key must not be used for the generation of the CBC-MAC as for the encryption. If the same key were used, the MAC block would be the same as the last cipher block and an attacker could undetected change the entire message with the exception of the last block.

CBC-MAC is only secure for messages of fixed length. If the message length varies , the method can be attacked by length extension . An attacker can generate a valid MAC for a new message (the concatenation of the two messages) from two valid message-MAC pairs. Two modifications can prevent this attack: Each message can be preceded by the message length or the MAC block is additionally encrypted with a second key.

literature

Reinhard Wobst: Adventure cryptology. Methods, risks and benefits of data encryption. 2nd, revised edition. Addison-Wesley Longman, Bonn et al. 1998, ISBN 3-8273-1413-5 .

Individual evidence

^ William F. Ehrsam, Carl HW Meyer, John L. Smith, Walter L. Tuchman, "Message verification and transmission error detection by block chaining", US Patent 4074066, 1976
↑ Mihir Bellare , Joe Kiliany, Phillip Rogaway: The Security of the Cipher Block Chaining Message Authentication Code . In: Journal of Computer and System Science . tape 61 , no. 3 , 2000, pp. 362–399 ( digitized version ( PDF; 466 kB) ( memento from February 5, 2012 in the Internet Archive )). The Security of the Cipher Block Chaining Message Authentication Code ( Memento of the original dated February 5, 2012 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. @1@ 2

[1] William F. Ehrsam, Carl HW Meyer, John L. Smith, Walter L. Tuchman, "Message verification and transmission error detection by block chaining", US Patent 4074066, 1976

[BKR-2] Mihir Bellare , Joe Kiliany, Phillip Rogaway: The Security of the Cipher Block Chaining Message Authentication Code . In: Journal of Computer and System Science . tape 61 , no. 3 , 2000, pp. 362–399 ( digitized version ( PDF; 466 kB) ( memento from February 5, 2012 in the Internet Archive )). The Security of the Cipher Block Chaining Message Authentication Code ( Memento of the original dated February 5, 2012 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. @1@ 2