Cryptography Reference
In-Depth Information
In these few cases, we decrypt
C
2
tentatively and test for (*), and so on. We
will gradually obtain all possible candidates for the plaintext, which we can
test with other means, if need be. Practically, however, (*) will be sufficient
for unambiguously revealing the key, since, with a random key, there is a
probability of
2
−
(
64
∗
8
)/
9
=2
−
56
.
8
...
that eight ciphertext blocks produce a plaintext that might have been created
by
compress
. In reality, this probability may even be smaller. In fact, it is (1
−
257
/
512) for the first 9-bit block, (1
−
258
/
512) for the second, and generally
(
N<
255) for
N
blocks:
N
(
)
256
n
512
−
n
= 1
We can use a small program to quickly verify that this product will already be
smaller than 2
−
56
for
N
=
49, i.e., due to
9*49 = 441 < 488 = 7*64
seven ciphertext blocks will suffice to recover the key on average. Though
there is really no profound mathematics behind it, the result sounds sensational
[Wobrump]:
People who compress their plaintext using
compress
before they DES-encrypt
it facilitate a ciphertext attack that requires only seven ciphertexts!
The astonishing thing about this finding is that cryptanalysts don't even dare to
dream of a ciphertext attack that might be generally mountable against DES.
We can see from the procedure that even the encryption mode plays only a
subordinate role. But the formulation is not entirely correct. It is not a pure
ciphertext attack. Though we don't know the plaintext, we do have an important
clue about it. This facilitates the test for correct decryption, as if we already
had the plaintext. What you actually want to call this type of attack doesn't
really matter. The important thing is to know that compression introduces an
additional risk!
Unfortunately, there is
no
Deep Crack in
my
den so that I won't be able to tell
you exactly how much computation time is involved. Anyway, I'm convinced
