Cryptography Reference
In-Depth Information
Consequently, this equation also holds for all
X <<< n
rotations with uneven
n
. When
n
is even, the remainder of
X
modulo 3 does not change in the
rotation. In particular, the divisibility by 3 is not lost in any rotation. If
X
and
n
are random, then the following holds with a probability of 2/3:
X <<< n = X mod 3.
In other words, the data-dependent rotation doesn't 'blur' information on
X
(namely the remainder from dividing by 3) sufficiently, and the confusion is
'weak' in this respect. The results of intermediate rounds differ from random-
ness in a definable way. That's the point where the authors mount their attack.
I will just discuss two details below (you can find the full article in
txt/cryptana/
mod3.ps
on our Web site):
1. In order for the 'beautiful number theory' to remain applicable, RC5P
is analyzed rather than RC5. The RC5P modification emerges from the
original RC5 when replacing the XOR operations by additions in every
round. Kaliski and Yin studied RC5P back in 1998 (so the algorithm
was not 'invented' especially for the mod-3 cryptanalysis) and assumed
that the method was just as secure as RC5 itself. They were wrong as it
turned out.
It is easy to see without further explanation that additions are 'friendlier'
towards residual classes than XOR operations.
2. The authors didn't initially succeed in providing a clean theoretical
substantiation for their cryptanalysis, i.e., estimating statistical shifts
mathematically. They replaced the theory by computer experiments and
constructed their attack on this basis.
Something like this is generally disapproved of among theoreticians, but jus-
tified from the cryptanalytic point of view: the end justifies the means. If the
attack works in practice, then it is irrelevant whether or not it was theoretically
substantiated.
Nevertheless, the authors endeavor to close this gap. For cryptographs, i.e.,
from the algorithm development perspective, the current state is somewhat
unsatisfactory: only when the background is fully understood can one start
building algorithms that cannot be cryptanalyzed by such methods.