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). ---