Limited Entropy Dot Com Not so random thoughts on security featured by Eloi Sanfèlix

Crypto Series: Block ciphers

In this entry we introduce block ciphers in a general way, as well as its modes of operation. Further, we'll see how to generate message authentication codes (MAC) using block ciphers.

Block ciphers

As we already said in the previous entry, block ciphers are symmetric ciphers which encrypt fixed length blocks. Therefore, a block cipher generally applies a series of operations combining the input block and the secret key (which isn't necessarily the same length) to obtain the output block (ciphertext).

Since they are symmetric, the decryption primitive uses the same key as the encryption primitive, and applies the operations needed to get back the plaintext at its output:

Most block ciphers can be classified as product ciphers or iterative block ciphers, based on a series of basic operations (rounds) which are repeated a number of times. These rounds provide confusion and difusion to the cipher, two concepts identified by Shannon in his famous treaty about communication theory.

Confusion refers to breaking the relationship between ciphertext and key as much as possible, while diffusion refers to destroying the statistical characteristics of the message source. Shannon identified these concepts and established the need for a secure cipher to provide them.

These kind of ciphers are generally Substitution-Permutation Networks (SPN), where several permutations (scrambling) and substitutions (changing values for others) take place one after the other, using a key, trying to achieve the goal: destroy the statistical properties of the source and obtain a secure cipher.

In subsequent entries we'll see how DES and AES, two well-known symmetric encryption standards, work. The remaining of this article treats block cipher modes of operation and how to authenticate messages using these ciphers.

Modes of operation

We'll see now some constructions that allow the use of a block cipher to encrypt texts larger than the block length. Some of them can be viewed as stream ciphers in which a key stream is generated and gets mixed with the plaintext.

First, we'll see the most simple way of using a block cipher. The construction that would come to every mind would be dividing the plaintext in blocks of the suitable length and encrypt each of them. This is what we call Electronic Codebook Mode (ECB), and as can easily be observed, it mantains the structure of the plaintext at the block level (not inside blocks): two identical blocks produce the same ciphertext under the same key.

After ECB, one of the most famous modes is the Cipher Block Chaining (CBC). In this case, the plaintext is also divided into several blocks, but before encrypting them with the secret key, they are XORed with the previous ciphertext block:

Where would be the so called Intialization Vector (IV), which can be different each time but doesn't need to be secret. Actually, it's usually known, either being a fixed value defined in the concrete protocol's specifications or sent together with the message as a header.

In this way, each encrypted block depends on each one of the previous blocks. A simple bit change in one of the blocks would produce a cascade effect and make the remaining blocks completely different. Clearly, message structure at the block level is not revealed. This is well illustrated in the following image from Wikipedia:

But not only CBC exists. For instance, the Output Feedback Mode (OFB) generates a bit stream to be used as a key, in the most pure stream cipher style. The cipher is initialized with an IV in the same way as CBC, but it is encrypted using the secret key. The resulting block has the k initial bits of key stream, which are XORed with the plaintext to produce the ciphertext.

To generate the next keystream bits, the previous block is used. Using the usual notation:

Obviously, decryption will be performed calculating the same keystream and XORing it with the ciphertext. This construction creates a stream cipher, and as other stream ciphers, if one bit is flipped in the plaintext, it will also be flipped in the ciphertext (and the other way around) due to the usage of XOR.

Another quite common mode is the counter mode (CTR), in which a counter is used at the input of the block cipher, and the output is used in the same mode as in OFB mode.

These are not all the existing modes, but the intention is simply to provide an overview of the options and to refer the interested reader to other sources. See for instance the famous Applied Cryptography from Bruce Schneier, or the Handbook of Applied Cryptography.

Message Authentication Codes

One of the problems that Cryptography's tried to solve, is the authentication of the data origin. This is, trying to assure that a message has been actually created by a certain person, machine or, more in general, entity. The solution to this problem based using symmetric crypto is known as Message Authentication Codes, or MACs.

These codes are just a block of groups generated by some alrogithm using a secret key and a plaintext message. The most common construction for generating these codes is based on using a block cipher in CBC mode, but taking just the last block as the MAC.

As we've seen previously, this last block depends on all the previous blocks, as well as on the key. Therefore, this code is binded to the complete message (provides message integrity) as well as to the entity with whom the secret key is shared (provides data origin authentication).

Thus, the receiver of the message, who shares a secret key with the source, is able to check whether the message was actually generated by the expected entity and that it has not been altered.