Cryptography Reference
In-Depth Information
encryptions, this set, together with this operation, does not form a mathematical
group. It is quite possible that this algebraic structure offers vulnerabilities for
cryptanalysis. To my knowledge, no such vulnerabilities are known; one doesn't
probably even know whether or not consecutive encryptions can produce an
identity (i.e., the original plaintext again) — except for the six pairs of semiweak
keys from Section 4.4.3.
Let's not stumble about in the gray zone and instead look at a more substantial
theory in the following section.
Man Meets in the Middle
There is a method to cryptanalyze double encryption. It is a brute-force attack
combined with a known-plaintext attack. The cryptanalyst meets virtually in the
middle between the two encryptions. On the one side, he encrypts the known
plaintext with all keys; on the other side, he decrypts the ciphertext. The two
results should coincide in the middle. This is the reason why this method is
referred to as a
meet-in-the-middle attack
, not to be confused with the
man-
in-the-middle attack
, where public keys are exchanged (see Section 4.5.2).
Two plaintext - ciphertext block pairs are basically sufficient for this attack. The
idea is very simple:
Suppose a plaintext block,
P
, and the corresponding ciphertext,
C
, produced
from a double encryption, are known:
C = DES
K
(DES
K
(P))
We encrypt
P
with all possible keys,
K
, and save the results. We then decrypt
C
with all possible keys,
K
, and see whether or not the deciphered product
occurs in the ciphers created. If it does, then we test the two keys,
K
and
K
,
on a second (
C, P )
pair. If
K
and
K
pass this test, then it is very likely that
they are the correct keys. We can now run other, more elaborate tests.
Rather than trial-and-error testing all
K
for every
K
, i.e., working our way
though 2
56
∗
2
56
possibilities like the wise men of Gotham, we save the results
for all possible 2
56
K
keys and test for possible
K
supto2
56
times, so that the
time required is now only 2
56
+
2
56
.
