HOW TO CRACK 1-ROUND-RC5 IN A KNOWN PLAINTEXT ATTACK

The 1-round RC5 can be cracked directly if you know at least some plain-
text-ciphertext word pairs. rc5_1_crack is a program  to demonstrate how
fast such a cracking can be.

In theory, the method works as follows:

The  RC5(32,1,*) encoding can  be described as  follows (cf. rc5.txt for
notations):

A0 = A + S0			(1)
B0 = B + S1			(2)

A1 = ((A0^B0)<<<B0) + S2	(3)
B1 = ((B0^A1)<<<A1) + S3	(4)

Here A,B is a  plaintext word pair,  A1,B1 the corresponding ciphertext.
We transform (4) and (2) to

S1 = ((B1-S3)>>>A1)^A1 - B

We  subtract two such  equations  for different  values  of A1&31 (i.e.,
different rotation amounts) and get an equation of the form

(X>>>K)^P - ((X+D)>>>L)^Q = R	(5)

with known K,  L, P, Q, R  and unknown X =  B1-S3. This equation  can be
solved for L >  K (this is  done in solve_X()),  maybe not unique. So we
get  S3, then B0,  and then S1. The other part of the key - S0  and S2 -
can be obtained analogously from (1) and (3).

How to use rc5_1_crack is  described in the source. Equation (5) will be
solved the faster the smaller L-K is.  BOUND, defined in  rc5_1_crack.c,
is  a  reasonable upper  bound  for  this difference.  In  practice, the
solution (tested against the given pairs) was always unique. Maybe, this
can be proved but I have not enough time and motivation to do this.

More  interesting is the  practical  result: The  computation  time on a
Pentium-133 under UNIX V.4.2 (ESIX)  with a Pentium-optimizied  compiler
was  in all tested  cases about 2ms  (!) with only 24 bytes of plaintext
needed.                         ****************************************

With other words: If somebody uses RC5(32,1,*) in  ECB mode (i.e., iden-
tical plaintext  pairs give identical results), and we know only 3 (or a
bit more) plaintext word  pairs together  with the corresponding cipher-
text pairs, his  whole message is expected to be decoded within millise-
conds.

The amount of about 3 ARBITRARY pairs is  interesting since the investi-
gation of Kalinski and Yin showed that 128 CHOSEN PAIRS suffice to crack
RC5(32,1,*).  Nevertheless,  such  a  result  could  be  expected  since
RC5(32,1,*) is simple and special, whereas the paper of Kalinski and Yin
treates the general, much more complicated case. I think, rc5_1_crack is
useful to show outsiders how fast and simple-to-use the cracking of such
a simple method can be.

Reinhard Wobst
wobst@ifw-dresden.de