Unlike many schemes, RC5 has a variable block size, key size and number of rounds. The original suggested choice of parameters were a block size of 64 bits, a 128-bit key and 12 rounds. A key feature of RC5 is the use of data-dependent rotations; one of the goals of RC5 was to prompt the study and evaluation of such operations as a cryptographic primitive. RC5 also consists of a number of modular additions and eXclusive OR s. The general structure of the algorithm is a Feistel-like network. The encryption and decryption routines can be specified in a few lines of code. The key schedule, however, is more complex, expanding the key using an essentially one-way function with the binary expansions of both e and the golden ratio as sources of "nothing up my sleeve numbers". The tantalising simplicity of the algorithm together with the novelty of the data-dependent rotations has made RC5 an attractive object of study for cryptanalysts. The RC5 is basically denoted as RC5-w/r/b where w=word size in bits, r=number of rounds, b=number of 8-bit bytes in the key.
Algorithm
RC5 encryption and decryption both expand the random key into 2 words that will be used sequentially during the encryption and decryption processes. All of the below comes from Rivest's revised paper on RC5.
Key expansion
The key expansion algorithm is illustrated below, first in pseudocode, then example C code copied directly from the reference paper's appendix. Following the naming scheme of the paper, the following variable names are used:
w - The length of a word in bits, typically 16, 32 or 64. Encryption is done in 2-word blocks.
u = w/8 - The length of a word in bytes.
b - The length of the key in bytes.
K - The key, considered as an array of bytes.
c - The length of the key in words.
L - A temporary working array used during key scheduling. initialized to the key in words.
r - The number of rounds to use when encrypting data.
t = 2 - the number of round subkeys required.
S - The round subkey words.
Pw - The first magic constant, defined as, where Odd is the nearest odd integer to the given input, e is the base of the natural logarithm, and w is defined above. For common values of w, the associated values of Pw are given here in hexadecimal:
* For w = 16: 0xB7E1
* For w = 32: 0xB7E15163
* For w = 64: 0xB7E151628AED2A6B
Qw - The second magic constant, defined as, where Odd is the nearest odd integer to the given input, where is the golden ratio, and w is defined above. For common values of w, the associated values of Qw are given here in hexadecimal:
* For w = 16: 0x9E37
* For w = 32: 0x9E3779B9
* For w = 64: 0x9E3779B97F4A7C15
Break K into words
u = w / 8
c = ceiling
L is initially a c-length list of 0-valued w-length words
for i = b-1 down to 0 do: L = + K
Initialize key-independent pseudorandom S array
S is initially a t=2 length list of undefined w-length words
S = P_w for i = 1 to t-1 do: S = S + Q_w
The main key scheduling loop
i = j = 0 A = B = 0 do 3 * max times: A = S = <<< 3 B = L = <<< i = % t j = % c
return S
The example source code is provided from the appendix of Rivest's paper on RC5. The implementation is designed to work with w = 32, r = 12, and b = 16. void RC5_SETUP
Encryption
Encryption involved several rounds of a simple function. 12 or 20 rounds seem to be recommended, depending on security needs and time considerations. Beyond the variables used above, the following variables are used in this algorithm:
A, B - The two words composing the block of plaintext to be encrypted.
A = A + S B = B + S for i = 1 to r do: A = + S B = + S
The ciphertext block consists of the two-word wide block composed of A and B, in that order.
return A, B
The example C code given by Rivest is this. void RC5_ENCRYPT
Decryption
Decryption is a fairly straightforward reversal of the encryption process. The below pseudocode shows the process. for i = r down to 1 do: B = ^ A A = ^ B B = B - S A = A - S return A, B
The example C code given by Rivest is this. void RC5_DECRYPT
Cryptanalysis
12-round RC5 is susceptible to a differential attack using 244 chosen plaintexts. 18-20 rounds are suggested as sufficient protection. A number of these challenge problems have been tackled using distributed computing, organised by Distributed.net. Distributed.net has brute-forced RC5 messages encrypted with 56-bit and 64-bit keys and has been working on cracking a 72-bit key since November 3, 2002. As of December 13, 2019, 6.222% of the keyspace has been searched and based on the rate recorded that day, it would take 102 years to complete 100% of the keyspace. The task has inspired many new and novel developments in the field of cluster computing. RSA Security, which had a patent on the algorithm, offered a series of US$10,000 prizes for breaking ciphertexts encrypted with RC5, but these contests have been discontinued as of May 2007. As a result, distributed.net decided to fund the monetary prize. The individual who discovers the winning key will receive US$1,000, their team will receive US$1,000 and the Free Software Foundation will receive US$2,000.
