Blog & News

The design of block ciphers is usually seen as a specialist topic. Consequently, knowledge is mostly preserved in academic papers and there are only few introductory tutorials. We aim to fill this gap between the IT security practitioner and the block cipher designer. In this blog series we introduce differential cryptanalysis with a hands-on approach. Our target group are IT security practitioners and programmers without a deep knowledge of math.

The following list shows the topics of all scheduled blog posts of this series. It will be updated with the corresponding links once new posts are being released.

• Part 1: Design of Modern Symmetric Ciphers
• Part 2: Differential Cryptanalysis of a Single-Round SPN
• Part 3: Differential Cryptanalysis of a Multi-Round SPN

Introduction

This first blog post in our series describes the design of symmetric block ciphers. These are encryption algorithms, where the same secret key is used for encryption and decryption.

In the first part of this post, a solid foundation is laid by discussing design requirements for block ciphers. In particular, the notions of confusion and diffusion are discussed. Next, we explain how modern encryption algorithms combine substitutions and permutations in order to achieve these requirements. Our article ends with the introduction of a full substitution permutation network which is used in modern encryption algorithms.

Design Requirements

There are various design requirements for symmetric encryption algorithms. These requirements changed over the years and have been refined in accordance with mankinds growing understanding of encryption.

Most importantly, an encryption algorithm is required to be “secure”. That means that it is not susceptible to attacks under various formalized attacker models. However, in symmetric cryptography, strict mathematical security proofs are hard to find. Instead, the requirements have a flavor of design guidelines. If these guidelines are not followed, then the encryption is probably insecure. However, the converse is not always the case.

Kerckhoffs’s Principle

One of the oldest design requirements for encryption algorithms is Kerckhoffs’s principle, named after Auguste Kerckhoffs. In 1883 he wrote La cryptographie militaire , one of the first formal treatises on military encryption. In this work, Kerckhoffs states with respect to a cryptographic system: “Il faut qu’il n’exige pas le secret, et qu’il puisse sans inconvénient tomber entre les mains de l’ennemi.” (It must not demand secrecy and it should not be a problem if it falls into the hands of the enemy.) This means that the security of an encryption algorithm should only depend on a secret key and not on a secret design.

This design philosophy means that the construction plans of the cipher are published. If the design is publicly available security has to depend only on the key. In cryptography if there are no known attacks such a system is considered more secure than a secret design, as it can be vetted by many professionals. The contrasting concept is called “Security by Obscurity”, i.e., a system is only secure as long as the attacker does not know the internals of the system. Security by obscurity is now considered a bad practice and every serious modern encryption algorithm follows Kerckhoffs’s principle.

Shannons Confusion and Diffusion

However, Kerckhoffs’s principle alone does not imply any statement about necessary statistical properties for the security of an encryption algorithm. Statements on statistical properties have only been present in design requirements from 1945 on. In that year, Shannon’s work A Mathematical Theory of Cryptography coined the notions of confusion and diffusion . Only fully declassified in 2013, this work introduces the application of statistical methods such as entropy in the field of cryptanalysis.

Confusion means that each bit of the ciphertext should depend on several parts of the key. This property obscures the connection between the key and the ciphertext.

Diffusion means that each bit of the ciphertext should depend on several parts of the plaintext. This property obscures the connection between the plaintext and the ciphertext.

More formally, both of these properties are still heavily used in cipher design under the term avalanche criterion . The avalanche criterion says that if a single bit of the key is flipped, then each bit of the ciphertext should flip with probability 1/2. Similarly, if a single bit of plaintext is flipped, then each bit of the ciphertext should flip with probability 1/2.

Building Blocks

Modern symmetric encryption algorithms use mainly two building blocks. The first building block is a substitution, the second is a permutation. In this section these two building blocks are explained in more detail.

Substitution

In a substitution, a symbol of the text is substituted by another symbol.

An example of a cipher that consists only of a substitution is the so-called Caesar cipher named after Julius Caesar. In this cipher, each letter of the alphabet is shifted left or right by a number of letters. As an example, when rotating two letters to the right, the letter “a” is exchanged by “c”, “b” is exchanged by “d”, “c” is exchanged by “e” and so on. The amount of the rotation is the secret key.

Regarding confusion, if the key changes then each of the ciphertext symbols changes. This change is not only with a probability, but is always performed. Regarding diffusion, if a single letter of the plaintext changes then the single corresponding letter in the ciphertext changes as well. The other letters in the ciphertext are not affected.

Even though a single substitution offers practically no security as the key space is small and the frequency of letters symbols is not hidden, it is used as a building block for more complex ciphers. In modern times, this building block is called a substitution box or simply S-box. These are lookup tables that map an input to an output.

Permutation

The second major building block for modern symmetric ciphers are permutations.

The historical predecessor of permutations in cryptography is the so-called skytale . The skytale is a historical device for encrypting messages. It is a cylinder on which a strip of parchment is wrapped around as shwon below. The message is then written on the parchment. When the strip is unwound again, the message cannot be read as the order of the letters has changed. Decryption is performed by wrapping the strip of parchment around a cylinder of equal diameter as the first skytale. Consequently, the diameter of the skytale serves as the secret key for the encryption.

Regarding confusion, if the key changes, then the ciphertext symbols stay the same, but their position changes. Regarding diffusion, if a single letter of the plaintext changes then the single corresponding letter in the ciphertext changes.

In our modern age of computers, such a simple permutation offers practically no security. However, as with the substitution, it is used as a building block for more complex encryption algorithms.

Modern Cryptography

Modern symmetric ciphers are not based on letters anymore. Instead, they use blocks of bits as the symbols of their alphabet. In block ciphers, a plaintext of fixed size is mapped to a ciphertext of fixed size using a key. The size of the plaintext and ciphertext blocks is usually fixed in the design of the cipher. For encrypting longer messages consisting of multiple blocks, the encrypted single blocks are chained using a so-called operation mode of the cipher.

Confusion and diffusion is achieved by combining substitution and permutation in a clever way. Further, in contrast to the Caesar cipher and the skytale, the parameters of the permutation and substitution are public. The key is applied separately onto the message by usage of the boolean xor operation.

Combining Substitutions and Permutations

Let us first establish some observations which will lead us closer to the goal of introducing a full substitution permutation network.

Combining multiple substitutions one after the other is the same as applying a single substitution on the plaintext. Substituting the plaintext using an S-box, and then substituting it again using a different S-box can be combined into a single step. In the combined step, a lookup table is created by first looking up the entry in the first S-box and then looking up the result as an entry in the second S-box. This combined lookup table describes the result of applying the two S-boxes sequentially. Consequently, combining multiple substitutions in a series does not increase their complexity.

The same is true for permutations. Intuitively speaking, first applying a permutation and then another permutation is the same as applying a permutation that is the combination of the two permutations. Mathematically, this follows from the fact that permutations form a group – the so-called permutation group – where the group operation is sequential composition of the permutations.

Consequently, applying multiple permutations or multiple substitutions directly in sequence does not increase the security of the encryption algorithm. Instead they need to be applied alternately.

Interleaving Substitutions and Permutations

As we have established in the last paragraph, applying multiple substitutions or multiple permutations directly in sequence does not yield any benefit. However, When the substitutions and permutations are interleaved their operation cannot be replaced by a simpler step. Further, note that substitutions and permutations do not commute, i.e., their order cannot be exchanged. Consequently, we examine the alternate application of substitutions and permutations. More specifically, we use multiple S-boxes for substitution, and use the permutation to spread the outputs of an S-box over the inputs of the next S-boxes. This way, the S-boxes stay small and thus easy to analyze.

The following figure shows a typical notation of such a network consisting of substitutions and permutations.

The data flow in this figure is from top to bottom. The input to the whole schematic consists of 16 bits; each wire holds a single bit. The S-box is a box where a substitution is applied to four bits each. That means that an input of four bits is substituted by four bits using a table lookup. In this schematic we use the same S-box for all substitutions. There may be cases though, where multiple different S-boxes are used. The part where the wires cross is the permutation. This permutation spreads the bits of the input over multiple parts of the output.

Let us now take a look at the property of diffusion. Recall, that diffusion means that each bit of the output should depend on several parts of the plaintext. If one bit is flipped in the input, say the first one, then the first S-box has a different output. The first permutation spreads the new output of the first S-box over the first, second and third S-box of the next round. Consequently, their outputs change as well. In the next permutation, the changes are spread over all four S-boxes. In summary, by flipping a single bit in the input, every bit of the output is affected.

Regarding the property of confusion, i.e., the relationship between the key and the ciphertext, first the key needs to be defined. As the permutations and substitutions affect the overall properties of the cipher heavily, these are usually kept public and the key is processed separately. If the key would be integrated in the substitutions or the permutations, different keys would offer different security levels. As an example, a key may correspond to the identity substitution, i.e., no substitution at all, and thus offer only marginal security.

Integrating the Secret Key

Let us take a step back and try to integrate the secret key into a simpler network.

If an encryption routine is defined by simply xoring the key onto the plaintext the resulting algorithm is vulnerable. If a single plaintext/ciphertext pair is given to the attacker the key can be recovered. More specifically, the key is the plaintext block xor the ciphertext block.

Consequently, we need to add more components to achieve a secure cipher. As our network above consists of multiple rounds, it seems natural to split the secret key and process each partial key in each round. These partial keys are usually called round keys, as they are used in the different rounds of the encryption algorithm. In modern proposals round keys are not parts of the main key, but are derived using more complex operations.

For our purposes, define the key as consisting of two parts: k0 and k1. These partial keys are used as round keys. Next, we evaluate the two possibilities of creating a more complex cipher: xor k0, permute, xor k1, and xor k0, substitute, xor k1.

xor k0, permute, xor k1

Define an encryption algorithm by xoring the plaintext with k0, then applying a publicly known permutation, and xoring again with k1. The resulting data is the ciphertext. A schematic of these operations can be found below.

Note that all of these operations commute and are not dependent on the plaintext. This sequence of operations can be exchanged by permuting the plaintext first and then xoring by the xor of the permuted k0 and k1. The result is one permutation and only one xor operation with a modified key derived from k0 and k1. Consequently, this combination of operations does not offer more security, as it can be computed using simpler operations.

xor k0, substitute, xor k1

Define an encryption algorithm by xoring the plaintext with k0, then applying a publicly known substitution, and xoring again with k1. The schematic of this procedure can be found below.

Note that the xor operation and the substitution does not commute, i.e., the order of operations cannot be changed. There is no way to substitute this construction with simpler operations. And in fact, this minimalist cipher known as the Even-Mansour scheme is one of the smallest ciphers for which a security guarantee can be proven in a formal sense.

With a single S-box this construction already offers confusion. If a bit of the key k0 is flipped, then the input to the S-box changes and consequently all output bits of the S-box are affected by this bit flip in the key. The same holds true for flipping an input bit of the plaintext.

Consequently, this way of integrating a secret key is what we will be using in order to build a full substitution permutation network, as it is used in modern cipher design.

A Full Substitution Permutation Network

Summarizing our points from above, an xor of the round key together with a substitution is used to achieve confusion. The permutations are used for the diffusion. The parameters for the substitution, as well as for the permutation are publicly known. The only secret ingredient are the round keys. Therefore, Kerckhoffs’s principle is satisfied.

The full construction of a substitution permutation network (SPN) is given in the figure below.

This figure shows a construction with three rounds and four round keys. In the last round the permutation is omitted as it is easy to undo without knowledge of the key and thus does not add security. The subkey mixing is usually done by xoring the round key with the wires, but there may be other options. In order to be more general the term “subkey mixing” is used in the schematic.

A modern encryption algorithm has many more rounds. In the advanced encryption standard AES the number of rounds is 10, 12, or 14 depending on the key length.

The round keys (k0, k1, k2, and k3 in our case) are usually derived from the main key using a key schedule. However, this is beyond the scope of our introduction.

Resources

• For further reading on the design of a modern cipher, we suggest the Stick Figure Guide to AES for a nontechnical introduction.
• Regarding the graphics, we are grateful for Tikz for Cryptographers which saved us a lot of time.
• The image of the Skytale is from Wikimedia Commons .
• And finally, the title image is from Pexels .

~ Dr. Henning Kopp