Multiple encryption
We can encrypt a message more than once, for example, given an encryption function 𝐸, keys 𝑘1, 𝑘2, and plaintext 𝑥, produce ciphertext 𝑦 as follows:
𝑦=𝐸 (𝐸 (𝑥)) 𝑘2 𝑘1
But is this always more secure?
Think of a substitution cipher as using a permuted alphabet. For example, if our alphabet contains 6 letters, we might use the permutation [𝑏, 𝑐, 𝑓, 𝑒, 𝑎, 𝑑]. The meaning is that the plaintext characters in alphabetic order map to cipher characters as follows:
– 𝑎→𝑏 – 𝑏→𝑐 – 𝑐→𝑓 – 𝑑→𝑒 – 𝑒→𝑎 – 𝑓→𝑑
Let’s try double encryption with the permutation [𝑓, 𝑐, 𝑏, 𝑎, 𝑑, 𝑒]:
– 𝑎→𝑏→𝑐 – 𝑏→𝑐→𝑏 -𝑐→𝑓→𝑒 – 𝑑→𝑒→𝑑 – 𝑒→𝑎→𝑓 – 𝑓→𝑑→𝑎
But we could have achieved that with the single permutation [𝑐, 𝑏, 𝑒, 𝑑, 𝑓, 𝑎].
In other words, encrypting twice with permutations is equivalent to encrypting once. Double encryption adds no security. Another example: double encrypting with two shifts 𝑠1, 𝑠2 is the same as single encrypting with the shift 𝑠1 + 𝑠2, for example.
Vigenère suffers from the same weakness. Double encrypting with two different keywords one after another is equivalent to encrypting with a single keyword whose length is the least common multiple of the lengths of the original keywords.
But there cipher systems for which this is not true. DES and AES are two such systems. But even these can be attacked using a known plaintext attack.
Meet-in-the-middle attack
For concreteness, we’ll look at this attack used against
DES, where the keys are 56 bits long, that is, there
are 256 possible keys: 𝑘1, 𝑘2, 𝑘3, … , 𝑘256 . We denote the
encryption and decryption functions as 𝐸 , 𝐷 where 𝑘 is 𝑘𝑘
the key. We have plaintext/ciphertext pair 𝑚, 𝑐 encrypted first with key 𝑘𝑎 and then re-encrypted with key 𝑘𝑏:
𝑐=𝐸 (𝐸 (𝑚)) 𝑘𝑏 𝑘𝑎
It would seem that Eve would have try all possible keys
values for 𝑘𝑎 and all possible keys values for 𝑘𝑏. In
effect, the two 56-bit keys can be thought of as a single
112-bit key. This is equivalent to a brute-force search
112
through 2 different keys. But she has a better way!
She can use a known plaintext attack, which means she knows 𝑚 and 𝑐 but doesn’t know 𝑘𝑎 , 𝑘𝑏 .
She first creates a list of all possible encryptions of 𝑚: 𝐸 (𝑚)=𝑧
𝑘1 1
𝐸 (𝑚)=𝑧 𝑘2 2
𝐸 (𝑚)=𝑧 𝑘3 3
…
𝐸 (𝑚) = 𝑧 56 𝑘256 2
Then she creates a list of all possible decryptions of 𝑐: 𝐷 (𝑐)=𝑧′
𝑘1 1
𝐷 (𝑐)=𝑧′ 𝑘2 2
𝐷 (𝑐)=𝑧′ 𝑘3 3
…
𝐷 (𝑐) = 𝑧′56 𝑘256 2
It must be true that 𝐸 (𝑚) = 𝑧 for some 𝑖 and 𝑘𝑎 𝑖
that 𝐷 (𝑐) = 𝑧′ for some 𝑗, which means that 𝑧 = 𝑧′. 𝑘𝑏𝑗 𝑖𝑗
And this means that the encryption was done
by 𝐸 (𝐸 (𝑚)) = 𝐸 (𝑧 ) = 𝑐. Eve’s task now becomes
𝑘𝑗 𝑘𝑖 𝑘𝑗 𝑖
finding a match between the two lists.
How much work does she have to do? She creates two
lists of length 256 and that requires 256 + 256 = 257
112
steps, not the 2 steps needed for brute-force.