Table of contents
Open Table of contents
What it is
If you’ve studied Cryptography there’s no doubt you stumbled upon historical ciphers such as the Caesar Cipher or the Vigenère Cipher which were considered secure back in the day they were invented.
Both, the Caesar- as well as the Vigenère Cipher encrypt the plaintext into a ciphertext by shifting the plaintext’s characters right (or left) while decryption applies the same steps in reverse to the ciphertext. Such shift ciphers are a subset of a broader class of ciphers called Substitution Ciphers since characters from the plaintext are substituted (replaced) with other characters from the same alphabet.
As it turns out, substitution alone isn’t enough to build a secure (symmetric) cipher. Per Claude Shannon’s analysis there are two properties a cipher needs to have in order to be secure: Confusion and Diffusion.
So how can we introduce confusion and diffusion to a cipher and how are both properties related to substitution and permutation?
Substitution
With substitution, characters from the plaintext are replaced with other characters from the same alphabet while retaining the plaintext’s structure.
A common way to implement substitution is through a so-called Substitution Box also known as “S-Box”. An S-Box is a lookup table which can be indexed into to get the value to use for substitution.
Let’s take a look at the following, fabricated example in which a 4-bit value is substituted with another 4-bit value. To find the corresponding row in our example table, one needs to take the first two leftmost bits from the plaintext value while the column lookup is dictated through the last two bits. The intersection of row and column tells us which value our substitution value is.
So if we have the value 1011 we find the row by looking for the bit pattern 10 (the first two bits). The column can be identified by checking for the bit pattern 11 (the last two bits). The value 1011 will be replaced with is thus 1101.
| - | 00 | 01 | 10 | 11 |
| 00 | 0000 | 1101 | 0110 | 1111 |
| 01 | 1010 | 1011 | 0010 | 1010 |
| 10 | 0100 | 1011 | 1110 | 1101 |
| 11 | 1100 | 0101 | 0010 | 1001 |
Again, this is just an example and other S-Box implementations might work differently.
Substitutions implemented via S-Boxes, for example introduce the very important property of non-linearity which ensures that there are no linear relationships that can be exploited during an attack.
It’s important to reiterate that the structure (i.e. the “meaning”) of the plaintext stays the same which means that statistical analysis (e.g. looking for letter frequencies) still allow for simple breakage of ciphers relying only on substitution.
Permutation / Transposition
Permutation (sometimes also called transposition) takes the characters from the plaintext and re-arranges them according to a pre-defined function. In this case the plaintext’s structure isn’t retained anymore as characters are reordered.
Permutations are often implemented through a Permutation Box also known as “P-Box”. A P-Box is a lookup table that can be used to find the corresponding permutation value.
The following, fabricated example shows how the value 1101 will be permuted using the following table.
| 4 | 3 | 1 | 2 |
The table should be read as follows:
- The output’s 1st bit is the 4th bit of the input (which is
1) - The output’s 2nd bit is the 3rd bit of the input (which is
0) - The output’s 3rd bit is the 1st bit of the input (which is
1) - The output’s 4th bit is the 2nd bit of the input (which is
1)
So in conclusion our input 1101 will be permuted into 1011.
Again, this is just an example and other P-Box implementations might work differently.
Using permutation alone doesn’t help in building a secure cipher as a Chosen Plaintext Attack in which the attacker asks for an encryption of the whole, ordered alphabet reveals the mappings of the permutation.
Substitution-Permutation Network
To build a secure cipher both, substitution and permutation are necessary. In fact, most of the modern symmetric ciphers such as AES make heavy use of both techniques.
Ciphers using substitution and permutation are called Substitution-Permutation Networks as they chain multiple blocks of substitution followed by permutation together.
The relationship to Confusion and Diffusion
So how does all this relate to Confusion and Diffusion, the properties Shannon identified as being both necessary to create secure ciphers?
The goal of confusion is to hide the relationship between the key and the resulting ciphertext. So ideally one bit of the ciphertext is linked to multiple bits of the key. As it turns out, confusion can be implemented via substitution and S-Boxes.
With diffusion, a change in one bit of the plaintext should result in multiple ciphertext bit changes (and vice versa). To implement diffusion, Permutation Boxes (P-Boxes) can be used.
References
The following resources have been invaluable for me to learn the concepts discussed in this article.
You should definitely give them a read if you want to dive deeper into the topic.