Cryptography Reference
In-Depth Information
5.2.1 Meet-in-the-Middle Attack
A lingering question we have yet to answer is, why use 3DES? Why not just use two DES keys back to back
(i.e., 2DES)? In other words, just calculate, for two keys,
K
and
L
The reason this isn't as secure as we might wish to believe is due to Diffie and Hellman's
meet-in-the-
middle attack
[6]. Although we would naturally assume that by encrypting a plaintext with one DES key and
then immediately with another, we would have a theoretical security of using a 56 + 56 = 112-bit key.
However, we can actually trade space for time very well in this particular case, using the birthday paradox,
by “meeting in the middle.” To explain this, let's break out the cipher into two steps:
The intermediate ciphertext,
D
, is what we are going to use to break the cipher.
The essence of the attack is to keep a large store of encrypts of the plaintext and decrypts of the ciphertext
(using only a
single
encryption and decryption, and not two). We then, for a new key (
J
) that we want to try,
will use it to encrypt the plaintext and decrypt the ciphertext (again, using only the single encryption and de-
cryption).
We then compare the results of the encryption with the table of previously decrypted blocks, and decryption
with the table of previously encrypted blocks we have stored. If we get a match with either result, then we have
found the two keys. For example, if the decryption with
J
matched some encryption for a key
I,
then we know
that
and therefore,
Thus, we have found
J = L
and
I = K
— our two keys. The technique works vice versa if we found an en-
cryption with
J
that matched a decryption for
I.
How long will it take for this time-space trade-off to work? To brute-force and calculate for all possible keys
(which are pairs of keys of size
n,
for a total size of
2n
) would take
2
2n
time. However, since we are storing
every value and checking it against the table, looking for a repeat, then we can use the birthday paradox to find
that it is only going to take about the square root of that time, or 2
n
. However, we have to do twice as much
work as normal brute-force, since we have to perform an encryption and decryption each time, which gives us
2
n
+1
. In other words, it takes only about twice as long as normal brute-forcing of a single
n
-bit key (instead of
exponentially longer).
Of course, the trade-off comes at the cost of storage. We must store the entire table in order to accomplish
this, which grows by two entries each time. We can expect success after about 2
n
attempts, each time storing
two items, giving us a total of about 2
n
+1
space (times the size of the key).
This attack is a good reason why 3DES uses a process of three encryptions and decryptions, even when using
two keys. The order of the keys' use in 3DES is geared so that no meet-in-the-middle attack is possible. Since
the intermediate ciphertexts depend on alternating keys, there is no way to coordinate them to induce the above
attack.
Search WWH ::
Custom Search