| Previous | Table of Contents | Next |
There are many ways to combine block algorithms to get new algorithms. The impetus behind these schemes is to try to increase security without going through the trouble of designing a new algorithm. DES is a secure algorithm; it has been cryptanalyzed for a good 20 years and the most practical way to break it is still brute force. However, the key is too short. Wouldn’t it be nice to use DES as a building block for another algorithm with a longer key? We’d have the best of both worlds: the assurance of two decades of cryptanalysis plus a long key.
Multiple encryption is one combination technique: using an algorithm to encrypt the same plaintext block multiple times with multiple keys. Cascading is like multiple encryption, but uses different algorithms. There are other techniques.
Encrypting a plaintext block twice with the same key, whether with the same algorithm or a different one, is not smart. For the same algorithm, it does not affect the complexity of a brute-force search. (Remember, you assume a cryptanalyst knows the algorithm including the number of encryptions used.) For different algorithms, it may or may not. If you are going to use any of the techniques in this chapter, make sure the multiple keys are different and independent.
A naìve way of improving the security of a block algorithm is to encrypt a block twice with two different keys. First encrypt a block with the first key, then encrypt the resulting ciphertext with the second key. Decryption is the reverse process.
If the block algorithm is a group (see Section 11.3), then there is always a K3 such that
If this is not the case, the resultant doubly-encrypted ciphertext block should be much harder to break using an exhaustive search. Instead of 2n attempts (where n is the bit length of the key), it would require 22n attempts. If the algorithm is a 64-bit algorithm, the doubly-encrypted ciphertext would require 2128 attempts to find the key.
This turns out not to be true for a known-plaintext attack. Merkle and Hellman [1075] developed a time-memory trade-off that could break this double-encryption scheme in 2n + 1 encryptions, not in 22n encryptions. (They showed this for DES, but the result can be generalized to any block algorithm.) The attack is called a meet-in-the-middle attack; it works by encrypting from one end, decrypting from the other, and matching the results in the middle.
In this attack, the cryptanalyst knows P1, C1, P2, and C2, such that
For each possible K, he computes EK(P1) and stores the result in memory. After collecting them all, he computes DK(C1) for each K and looks for the same result in memory. If he finds it, it is possible that the current key is K2 and the key in memory is K1. He tries encrypting P2 with K1 and K2; if he gets C2 he can be pretty sure (with a probability of success of 1 in 22m – 2n, where m is the block size) that he has both K1 and K2. If not, he keeps looking. The maximum number of encryption trials he will probably have to run is 2*2n, or 2n + 1. If the probability of error is too large, he can use a third ciphertext block to get a probability of success of 1 in 23m – 2n. There are still other optimizations [912].
This attack requires a lot of memory: 2n blocks. For a 56-bit algorithm, this translates to 256 64-bit blocks, or 1017 bytes. This is still considerably more memory storage than one could comfortably comprehend, but it’s enough to convince the most paranoid of cryptographers that double encryption is not worth anything.
For a 128-bit key, the amount of memory required is an enormous 1039 bytes. If we assume that a way exists to store a bit of information on a single atom of aluminum, the memory device required to launch this attack would be a cube of solid aluminum over a kilometer on a side. And then you need some place to put it! The meet-in-the middle attack seems infeasible for keys this size.
Another double-encryption method, sometimes called Davies-Price, is a variant of CBC [435].
They claim “no special virtue of this mode,” but it seems to be vulnerable to the same meet-in-the-middle attacks as other double-encryption modes.
Triple Encryption with Two Keys
A better idea, proposed by Tuchman in [1551], operates on a block three times with two keys: with the first key, then with the second key, and finally with the first key again. He suggested that the sender first encrypt with the first key, then decrypt with the second key, and finally encrypt with the first key. The receiver decrypts with the first key, then encrypts with the second key, and finally decrypts with the first key.
| Previous | Table of Contents | Next |