Cryptography Reference
In-Depth Information
The background of this attack is interesting. The IDEA developers introduced
so-called
Markov ciphers
[LMM.IDEA]. These are product algorithms where
the probability for an arbitrary difference of two ciphertexts depends only on
the difference in the pertaining plaintexts, and not on that difference's value, in
every round. Such methods are resistant to differential cryptanalysis, because
every ciphertext difference has about the same probability after a sufficient
number of rounds with a fixed plaintext difference.
RC5 is not a Markov cipher. But every fixed plaintext difference creates a large
number of possible ciphertext differences with about the same probability across
several rounds, mainly thanks to rotation.
This attack was improved by Knudsen and Meier by a factor of up to 512,
i.e., 2
9
[KnudRC5], at the CRYPTO '96. Their idea was to search for such
plaintexts where no rotation occurs at the beginning in several rounds, i.e.,
where there is only a weak diffusion. They found these plaintexts by use of a
special
key-detection
algorithm. Against a 12-round RC5, they 'only' needed
2
53
chosen plaintexts to find special plaintexts where no rotation occurred in the
first few rounds. Subsequently, they would need another 2
54
chosen plaintexts
to recover the key. As a sideline, 2
54
plaintexts correspond to a data volume
of 128 000 terabytes
...
Another improvement was introduced by Biryukov and Kushilevitz at the
EUROCRYPT '98 [BirKush]. They defined a pair of plaintexts where the rota-
tion amounts coincided in all rounds to serve as a
right pair
(see Section 4.4.2)
for differential cryptanalysis. (The exceptions found in Figure 5.15 may in this
sense also be considered to be right pairs that differ only in one bit.) Rather
than looking at the differences of 32-bit words, they studied only the five least
significant bits. This is why they also call their method
partial differential crypt-
analysis
. Its result is more dangerous by a factor of about 1000: 2
44
chosen
plaintexts suffice to recover the subkeys. So, the only thing left for the attacker
is to foist 128 Gbytes of chosen plaintext on the code writer (or the chip card).
That kind of volume is transmitted over a 34-Mbit data line within a little over
one hour. As a sideline, RC5a, my modification introduced in Section 5.4.3, is
resistant to this attack, just as well as to the attack by Knudsen and Meier.
Weak Keys
Knudsen and Meier additionally found weak keys in the sense that using
such a key facilitates differential cryptanalysis. These keys — the
S
i
words in
