Further notes on RC6
Ronald L. Rivest
Last updated 6/20/98
http://theory.lcs.mit.edu/~rivest/rc6-notes.txt
Here are some notes on RC6, based on comments or questions from others.
[1] The introductory paragraph of section 6 ("Security") conjectures that
the best approach is exhaustive search for the encryption key. When
the user-supplied key is longer than the table of round keys, it is
of course easier to do a brute-force search for the table of round
keys. The paper thus provides the formula
min(2^(8b),2^1408)
as an estimate of the difficulty of breaking RC6, where b is the number
of user-supplied key bytes.
However, as pointed out by Don Coppersmith, there is a meet-in-the-middle
attack on the table of round keys. So the formula should instead have read
min(2^(8b),2^704)
if you can assume enough memory to mount such an attack (!).
[2] The RC6 paper asserts that the function
f(x) = x (2x+1) mod 2^w
is one-to-one, but doesn't give a proof. Here is one.
Theorem: The function
f(x) = x (rx+s) mod 2^w
is one-to-one over {0,1,...,2^w-1}
whenever r is even and s is odd, for any integer w >= 0.
Proof: By contradiction.
Assume that f(x) = f(y) for x != y.
Then x(rx+s) = y(ry+s) mod 2^w.
So r(x^2-y^2) = s(y-x) mod 2^w.
Thus r(x+y)(x-y) = -s(x-y) mod 2^w.
But 2 divides the left side more times than the right side. QED
[3] The paper claims an encrypt/decrypt time of 254 clock cycles (in
assembler). Ted Krovetz (krovetz@theory.cs.ucdavis.ed), a PhD student
at UCSD working with Phil Rogaway, has an assembler implementation which
runs in 243 cycles per block (equivalent to 823,000 blocks/sec at 200MHz,
or equivalent to 13.17 Mbytes/second at 200MHz).
---