RC5: Rivest Cipher 5

CS 463 Lecture, Dr. Lawlor

A series of curiously simple Feistel-type ciphers were developed in the 1990's by Ronald Rivest (of RSA fame).  RC5 is basically a Feistel structure, where each round function consists of:
Here's the code.  A and B are incoming plaintext; the S table is derived from the key (carefully, to avoid meet-in-the-middle).

    A = A + S[0];
    B = B + S[1];
    for (i = 1 ; i <= R ; i++) {
        A = A ^ B;
        A = rotateLeft(A, B) + S[2*i];

        B = B ^ A;
        B = rotateLeft(B, A) + S[(2*i)+1];
    }

That's it!

A decent description interspersed with the C implementation is in RFC 2040.  Steve Burnett wrote up a readable design intro and some technical discussion here.

Cryptanalysis

On paper, the simplest 12-round version is vulnerable to a differential cryptanalysis attack requiring 244 chosen plaintexts (thus, if somebody asks you to encrypt 16 trillion plaintexts, be careful!).  The higher round count versions are secure, as far as anyone knows, despite the very simple structure.  Evidently the data-dependent variable bit shifts are the key feature to resist attack, since XOR and add are very weak alone.

RC5 with a short 56-bit key was brute forced in 250 days (in 1997), mostly as a PR stunt to show DES's key was too short.
RC5 with a 64-bit key was brute forced in 1,757 days using way more computers (in 2002).
They've been trying for a 72-bit key since 2002.
Typical minimum today is a 128 bit key and 20 rounds, which seems to be secure.

One reason RC5 isn't more widely used?  It's patented, although the patent does run out in November 2015.

Testing

Here's a simplified version, without a key schedule, for differential cryptanalysis testing.

/* A cipher similar to RC5: */

typedef unsigned long var;

/* Bit rotate rightwards */
var ror(var v,unsigned int bits) {
	return (v>>bits)|(v<<(8*sizeof(var)-bits));
}
/* Bit rotate left */
var rol(var v,unsigned int bits) {
	return (v<<bits)|(v>>(8*sizeof(var)-bits));
}

/* This class is used to encrypt or decrypt a block of data. */
class cipherblock {
public:
	var L,R; // current state, Left and Right halves
	
	// Perform one forward round, using this key.
	//   Modifies L depending on both R and the round key.
	void round_fw(var &L,const var &R,var key,unsigned int stage) {
		L=L^R;
		L=rol(L,R);
		L=L+key+stage;
	}

	// Perform one reverse round, using this key.
	//   Modifies L depending on both R and the round key.
	void round_bw(var &L,const var &R,var key,unsigned int stage) {
		L=L-key-stage;
		L=ror(L,R);
		L=L^R;
	}

	// Print the current state of this block
	void print(const char *description,int stage) {
		printf("%s %d: %016lx %016lx\n",description,stage,L,R);
	}
};



int foo(void) {
for (int diff=0;diff<100;diff++) {
	var plain=0xabcdef0000000+diff; // plaintext
	var key=0xf0f0f0f; // encryption key
	int r; // round count
	cipherblock b; b.L=plain; b.R=plain>>32;
	if (diff==0) b.print(" P",0);
	
	// Take several rounds to scramble the data
	// FIXME: real RC5 uses more rounds, and a real key schedule.
	for (r=0;r<10;r++) {
		b.round_fw(b.L,b.R,key,r); 
		if (diff==0) b.print("L",r);
		b.round_fw(b.R,b.L,key,r); 
		if (diff==0) b.print("R",r);
	}

	b.print("                   C",0);

	// Walk rounds backwards to unscramble the data
	for (r--;r>=0;r--) {
		if (diff==0) b.print("R",r); 
		b.round_bw(b.R,b.L,key,r);
		if (diff==0) b.print("L",r); 
		b.round_bw(b.L,b.R,key,r); 
	}
	
	if (diff==0) b.print(" P",0);
}
	return 0;
}

(Try this in NetRun now!)