Cryptography Reference
In-Depth Information
of
S
[2*
i
]. A change to
B
in the remaining 27 bits has no impact on the last
five bits of
A
. With the modification, however,
K
additional bits now have an
impact. This means that the larger
K
the greater the diffusion. The value of
K
is basically limited only by the memory available.
More specifically, algorithm RC5a-32/r/* (32-bit words,
r
rounds, optional key
length) with given
K
between 1 and 27 now looks like this:
1. Set
KB
=
2
K
K
.
2. Create
(
2
r
+
2
)
∗
KB
subkeys,
S
[
i
], as shown in Figure 5.13.
3. Encrypt the half blocks,
A
and
B
, from Figure 5.13 as follows:
and
KBSH
=
32
−
A = A + S[B >> KBSH];
B = B + S[KB + (A >> KBSH)];
for i=1 to r do
A =
((A
⊕
B) <<< B) + S[2*i*KB + (B >> KBSH)];
B =
((B
⊕
A) <<< A) + S[(2*i + 1)*KB + (A >> KBSH)];
where
A
denotes the right rotation of
A
by
n
bits. In other words, the
five least significant bits of
A
or
B
, respectively, determine the rotation
of
A
or
B
, while the most significant
KB
bits determine the choice of
the key. RC5a turns back into RC5 when
K
=
4.
With 12 rounds, this corresponds to a memory requirement of well over
1.5 Kbytes for the
S
[
j
] subkeys.
=
0. I recommend
K
Cryptanalyzing RC5a
As expected, RC5a has fewer random key - plaintext pairs in which changed
bits have no influence on the rotation. Figure 5.15 shows this clearly.
This modification might not be the philosopher's stone, but the improved dif-
ferential cryptanalysis by Knudsen doesn't work on this algorithm any more,
since the probability for 'no rotation' drops considerably. Kaliski and Yin also
followed paths across the RC5 rounds, where ideally no amount of a rotation
changes due to changed bits. The point is presumably that the probabilities
of characteristics (see Section 4.4.2) for
K
=
4 are smaller by a factor of 16,
which makes differential cryptanalysis more ineffective than brute force with
less than 12 rounds. The weak keys discussed above — if there are any in RC5a
at all — are then no longer a threat either. The same applies to the linearly
weak keys of Heys and the partial differential cryptanalysis of Biryukov and
Kushilevitz.
