RC5 (block cipher): design, parameters, and cryptographic role

RC5 has variable block sizes (32, 64, or 128 bits), key lengths (0-2040 bits), and round counts (0-255). A specific choice of these parameters is usually referred to as "RC5-w/r/b" - w is the length of a word in bits (a block consists of two words), r is the number of rounds, and b is the length of the key in bytes. Rivest originally recommended RC5-32/12/16 and RC5-64/16/16 for 64-bit architectures.

RC5 consists of three components: Encryption, Decryption and Key Expansion. The cryptographic primitives of the method used in encryption and decryption are:

• the addition of two words modulo
• the bitwise XORing of two words
• the rotation of a word by b bit positions, where b is given by the least significant bits of the other word

The primitives operate on words of w bits, each forming a half-block. The security of the algorithm depends significantly on the use of rotation, which is the only nonlinear operation of the method. The successor algorithm RC6 and in parts the AES candidate MARS are also based on data-dependent rotations.

The primitives are denoted hereafter by A+B for addition, A⊕B for bitwise XOR operation, and A⋘B and A⋙B, respectively, for the left/right rotations of the half-block A by (B mod w) bit locations.

Key expansion

With key expansion, the round keys S0, ..., _S2r+1 - where S0 and _S1 are used for key whitening - are generated from the secret key. The system of round keys is also called an expanded key table. To achieve this, the secret key is first split into half-blocks _Li, padded with zeros if necessary. Then the round keys _Sk are initialized to a fixed initial state by means of constants:

:

Here, P and Q are odd integers generated using Euler's number e and the golden ratio Φ depending on the block size used.

Finally, the half-blocks _Li and _{Sk are} mixed together in three passes:

:

encryption and decryption

Given a plaintext block in little-endian representation consisting of the half-blocks A, B and the round keys S0,..., _S2r+1. The block is encrypted by:

:

Here, each half-round corresponds to one round of a feistel cipher. The decryption of a corresponding ciphertext block from the half blocks A, B proceeds analogously:

:

For cryptanalysis purposes, a variant called RC5⊕ is also used, in which the modular addition of the half blocks is completely replaced by bitwise XOR. This variant is - due to a connection existing under XOR between bits of the ciphertexts and bits of the round keys associated with the plaintext - cryptographically weaker and is predominantly suitable as a simplification for the analysis of the data-dependent rotations.

The analogous variant RC5P, which uses only additions, has also been shown to be cryptographically weaker. In 1999, John Kelsey, Bruce Schneier and David Wagner showed with a novel attack - called "mod n" cryptanalysis by them - that ciphers based only on additions and rotations can generally be broken. Here, the attack is based on correlations between plaintext and ciphertext of the last round when considered modulo n. By choosing n appropriately, an attacker can obtain information about the last round key in this way. The authors concluded from their results that mixing the operations "+" and "⊕" is essential for the security of RC5.

Chosen-Plaintext Attacks

Kaliski and Yin of RSA Laboratories showed in 1995 that differential cryptanalysis against RC5-32/9 requires ²⁴⁵ pairs of chosen plaintexts and associated ciphertexts, which is about the strength of 16-round DES. RC5-32/12, on the other hand, requires ²⁶² such pairs. The attack here reconstructs bits of L2r, from which information about _S2r+1 can be inferred. Once _S2r+1 is known, a simpler analysis can be applied to RC5 with a reduced number of rounds. The chosen key length is meaningless for this attack.

In 1996 Knudsen and Meier improved the differential attack and also showed the existence of a large number of weak keys. These arise from the structure of the cipher and are independent of the choice of expansion algorithm. Knudsen and Meier's attack exploits data dependence of cyclic rotations by identifying such plaintexts where no rotation occurs within the first rounds. In this way, the number of chosen plaintext pairs is reduced to ²³⁹ for RC5-32/9 and up to ²⁵⁴ for RC5-32/12. For RC5-64 - from an academic point of view - the 16 rounds originally proposed by Rivest with ²⁸³ required chosen plaintext pairs are not sufficiently secure against differential cryptanalysis.

Another improvement of differential cryptanalysis was published in 1998 by Buryukov and Kushilevitz of the Israeli Institute of Technology in Haifa. This attack, in which so-called "good" pairs of chosen plaintexts and ciphertexts are chosen via Hamming weights of round differences, reduces the number of required chosen plaintext pairs for RC5-32/12 to ²⁴⁴. The authors concluded that differential attacks against RC5-32/12/16 were possible with ²³⁸ and against RC5-64/16/16 with ²⁶³ chosen plaintext pairs.

In the course of the election of the new Advanced Encryption Standard in 2000, Takeshi Shimoyama (Fujitsu), Kiyofumi Takeuchi, and Juri Hayakawa (Chuo University) submitted a modified variant of an attack on RC6 presented by Knudsen and Meier in 1999, adapted to RC5. This correlation attack, based on the χ²-test, reconstructs the last round key for RC5 with 17 half-rounds using ²⁵⁴ chosen plaintexts with a success probability of 80%. Similarly, the authors showed that the attack for about one in ²²⁰ keys also breaks RC5 with full rounds with the same probability.

Known-Plaintext Attacks

Kaliski and Yin showed that a reconstruction of the extended key table using linear approximations already requires ²⁴⁷ known plaintexts for five rounds and thus reaches the strength of DES against linear cryptanalysis. For more than six rounds, the attack described by these authors is meaningless. However, according to Ali Aydın Selçuk of the University of Maryland, this attack is based on false assumptions and is thus flawed.

In 1997 Howard M. Keys RC5-32/12/16 published the existence of linear weak keys. He found ^{228 keys for which a} linear cryptanalysis can already be performed with ²¹⁷ known plaintexts. Furthermore, ²⁶⁸ keys exist for which the cipher can theoretically be broken with ²⁵⁷ plaintexts. The keys essentially depend on the expansion algorithm used.

An attack published in 1999 by Borst, Preneel and Vandewalle, based on linear approximations and practically implementable due to its low memory requirements, breaks RC5-32/r with ^24+6r and RC5-64/r with ^23+8r known plaintexts with 90% probability of success. Miyaji, Nonaka, and Takii called these results "highly optimistic" in 2002, and in turn presented a correlation attack based on the χ²-test that could achieve a 90 percent probability of success against RC5-32/r with ^26.14r+2.27 known plaintexts.

Other approaches

An attack presented in 1999 by Handschuh and Heys exploits the time required for the data-dependent rotations performed during encryption. While Rivest assumed modern processors would perform a rotation in time O(1), this is not necessarily the case for embedded systems, for example. The timing differences that occur on such platforms allow inferences about the number of rotations performed and, given complete information, allow reconstruction of the extended key table for RC5-32/12/16 using ²²⁰ ciphertexts with time requirements Ω(²²⁸) and O(²⁴⁰). However, the attack can be avoided implementation-based by dummy rotations.

Attacks in practice

The company RSA Security offered $10,000 to decipher various ciphertexts as part of its Secret-Key Challenge - a public call to break specific ciphertexts - which ran from 1997 to May 2007. The distributed.net organization coordinated distributed attacks on the ciphertext and broke RC5-32/12/7 within 250 days and RC5-32/12/8 within 1757 days. The lower-priced "challenges" RC5-32/12/5 and RC5-32/12/6 were previously broken in 3.5 and 313 hours, respectively.