Cryptography Reference
In-Depth Information
Figure 5.13, and not the original key,
K
— have three subkeys,
S
i
,S
i
+
1
, and
S
i
+
2
, with special values in their last five bits. This increases the probability
of special differences over three half rounds by a factor of 4.7. However, a
special test with chosen plaintexts is required here, too, to detect the use of
such a key.
These weak keys have different 'risk classes'. The higher the risk class, the
easier the attack, but also the fewer weak keys of that class there are. More
specifically, only 2
45
chosen plaintexts (270 Tbytes of text) are required to find
the key to be weak with RC5-32/12/16 for a key group with frequency 2
−
32
.
2
(approximately one key out of five billion random keys). For these keys, differ-
ential cryptanalysis can make do with 'only' 2
40
chosen plaintexts (8.2 Tbytes).
For other keys with frequency 2
−
10
.
7
(one key out of 1663 random keys), you
would need 2
53
plaintexts for the key and 2
49
plaintexts for the attack.
This doesn't represent a particular risk for practical purposes. But there might
be faster methods to find weak keys, and there might also be other types of
weak keys.
As you can see, the result is not as alarming as the Abstract in Knudsen's
article may suggest: 'We also show that RC5 has many weak keys with regard
to differential cryptanalysis. This weakness is in the structure of the algorithm
and not in its key generation.' However, we should follow up closely on the
development. It's certainly no mistake to use RC5-32/16/16, i.e., to work with
16 rounds rather than 12. This algorithm is still very fast. And, by the way,
this cryptanalysis doesn't work for RC5a (see Section 5.4.3).
Linear Cryptanalysis and Linearly Weak Keys
The first known linear cryptanalysis on RC5 was done by Kaliski and Yin
[KalisRC5]. They required 2
47
plaintexts for a 5-round method (i.e., like with
the differential cryptanalysis on DES!), but as many as 2
57
with 6 rounds.
Consequently, the 12-round method is secure in this respect. However, similarly
to Knudsen and Meier, Heys [HeysRC5] showed that there are weak keys here,
too, which facilitate linear cryptanalysis: using the 12-round method with a
128-bit key, there are 2
28
(about one quarter of a billion) such weak (sub)keys,
and only about 2
17
plaintext blocks (corresponding to 1 Mbyte of plaintext) are
required to recover the subkeys. This sounds more worrying than the result
from differential cryptanalysis. Though the probability of catching such a key
