Cryptography Reference
In-Depth Information
is only 2
−
100
(approximately 10
−
30
), what if Rivest's algorithm were to create
preferably weak subkeys for generation? The counter-proof may not be easy.
There are no such worries rationally, but being careful has never hurt. RC5a,
my modification introduced in Section 5.4.3, should not have differentially or
linearly weak keys (Heys thinks so, too). The reason is that the probability that
no rotation occurs in successive rounds is much smaller with RC5a (it can even
be arbitrarily reduced if there is enough memory available). All attacks against
RC5 discussed so far are based on the assumption that there is no rotation in
several rounds.
The mod-3 Cryptanalysis of RC5P
Kelsey, Schneier, and Wagner introduced a new type of attack against a modi-
fication of RC5 in [Schnmod3]. I find this attack worth noting here since it was
the first direct attack against data-dependent rotations. In fact, all cryptanalyses
I know of try to find chosen plaintexts where nothing or little is rotated, and
attack the algorithm, for example, by differential cryptanalysis. The underlying
idea outlined in [Schnmod3] is different and so simple you once again have to
ask yourself why nobody thought of it earlier.
We look at the remainders of 32-bit numbers,
X
, when dividing them by 3.
If
X
is smaller than 2
31
, then the cyclic left rotation by 1 is nothing but a
multiplication by 2:
X<<<1=2X(X<2
31
)
Conversely, the following holds in the other case:
X<<<1=2X+1-2
32
(X
2
32
).
•
But the following holds in general since 2
32
leaves a remainder of 1 when
divided by 3:
X <<< 1 = 2X mod 3.
