Cryptography Reference
In-Depth Information
(not to be confused with the faster
fcrypt
DES implementation). To cryptanalyze
it, we will use a method totally different from those discussed so far, namely
differential cryptanalysis
. This method was first introduced by the Israeli
mathematicians Biham and Shamir in 1990 [Bih.diff] and used for an attack
against DES; we will discuss this issue in more detail in Section 4.4.2.
Though my
fcrypt
method should no longer be used for encryption, it is quite
interesting for cryptanalysis. As mentioned in the previous section that dealt
with compressed files, we won't worry about the probability theory as we
mount our attack, because
fcrypt
is immune to statistical methods. We will
reach our goal with a particularly simple type of differential cryptanalysis.
The
fcrypt
Method
How does
fcrypt
work? The basic idea is pretty simple: we divide the plaintext
in blocks of 256 bytes each (appropriately padding the last block). We take
each block and split it into 16 groups of 16 bytes each in a secret way. There
are 256!/(16!)
2
or approximately 10
192
different ways (so we don't need to
consider brute force from the outset). We encrypt each group separately by the
following rule:
Replace each byte by the sum of the other 15 bytes of that group.
Let the plaintext bytes of a group be
p
1
,...,p
16
, then the formula for creating
the ciphertext bytes,
c
1
,...,c
16
, is as follows:
c
1
=p
2
+p
3
+ ... + p
16
(mod 256)
c
2
=p
1
+p
3
+ ... + p
16
(mod 256)
...
c
16
=p
1
+p
2
+ ... + p
15
(mod 256)
(The decryption is just as easy, but we are not interested in it here.) This method
has a remarkable property: if the plaintext bytes are sufficiently random, we
might be lucky enough to get equally distributed ciphertext bytes. Even sharp
tests didn't show any more statistical dependencies between the ciphertext
bytes. However, I found in the first design that the method has a conceptual
weakness:
If two plaintexts differ only in one byte, then the ciphertexts (created with the
same key) differ in 15 bytes. These 15 bytes all belong to the same group.
