Cryptography Reference
In-Depth Information
execution time. Shamir himself thinks that visual cryptanalysis could be most
effective when combined with suitable computer technology. Still, I felt the
basic idea behind his method was so original that I shouldn't withhold it from
you, just to show how many faces cryptanalysis can have. We will come across
more surprising methods further on in this topic.
As a sideline, you will find a remarkable note about a press release by CRAY of
March 7, 1995 in the literature referenced above. The report praises the special
production of a massive parallel bit-slice computer named CRAY-3/SSS — a
joint development by CRAY and the NSA. This computer can compute one
million bits in parallel, thus achieving a processing speed of up to 32 trillion
bits per second — with a price/performance ratio unparalleled by any other
computer. The press release says that 'the CRAY-3 system with the SSS option
will be offered as an application-specific product'. Think for a moment of who
cooperated in the development and you'll know how to interpret this sentence.
Compression
=
Compromise
Remember Section 3.6.4? It introduced the surprising fact that the prior com-
pression of data doesn't increase security, even though the plaintext is statisti-
cally distributed pretty much equally.
This argument holds for DES, too, only the attack is not as simple as against
the Vigenere method: you actually should have a DES crack machine in your
den before you can think of putting the following idea to work.
The approach against DES looks like this: assume we have a sequence of
ciphertext blocks,
C
1
,C
2
,C
3
,...
. They are the DES ciphers of a plaintext
created by
compress
(where the three fixed bytes at the beginning should be
truncated to make things a bit harder for the attacker). First, we will limit
ourselves to encrypting in simple ECB mode.
Now we have our machine try all possible DES keys. We normally decrypt only
C
1
tentatively. Since the resulting plaintext block,
P
1
, is 64 bits long, we can
already test to see whether or not
P
1
could have been created by
compress
— the
equation (*) from Section 3.6.4 will probably be sufficient for an initial test.
In most cases, (*) will
not
be true for a pair of two 9-bit blocks from
P
1
.
In about 0.8 % there is no contradiction. This figure is not hard to check: a
plaintext block contains seven 9-bit blocks of this sort. There is a probability
of about 0.5 that each of the 9-bit blocks is valid. With a plaintext created
randomly (which can be plausibly assumed when using a wrong key), relation
(*) will be true for all blocks with a probability of only 2
−
7
, i.e., 0.0078.