RC5

RC5 (Rivest Cipher 5) is a symmetric block cipher designed by Ronald Rivest in 1994. This means that the same key is used for both encryption and decryption. It belongs to the class of Feistel ciphers. The data is first divided into blocks of equal size and encrypted or decrypted by repeated application of simple operations - so-called "primitives". The block size, the length of the key and the number of repetitions - the "rounds" - are not specified by the algorithm and are set as parameters before encryption.

The goal in designing RC5 was a simple and fast cipher. It is based on data-dependent rotations, whose suitability as a primitive was still largely unexplored at the time of development.

Unlike many other block ciphers, RC5 does not use S-boxes to achieve the blurring of statistical relationships between plaintext, key, and ciphertext that Claude Shannon called "confusion" in 1949 and that is important for secure operation. An S-box provides strong confusion, since one is largely free to choose how, for example, a -S-box maps the possible values of the input bits to the possible output values. However, S-boxes in practical implementation require additional memory and also some computational effort, since one must first divide a data word into sufficiently small parts to be input to the S-box, since a whole word of 16 or more bits is too large for this. After that, you also have to reassemble the results into a word. The lack of S-boxes makes RC5 very simple and fast and especially interesting for use in resource-poor areas - such as digital hardware with limited chip area.

A concrete software implementation that provides different modes of operation for chaining blocks - namely CBC, CBC pad, and CTS - is specified in the RFC 2040 standard.

RC5 served as the basis for RC6 encryption, which was a candidate for the Advanced Encryption Standard.

In the United States, the company RSA Security held a patent on RC5 until 2015.

Description

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:

Block size (bits)	P (hexadecimal)	Q (hexadecimal)
032	B7E1	9E37
064	B7E1 5163	9E37 79B9
128	B7E1 5162 8AED 2A6B	9E37 79B9 7F4A 7C15

:

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:

:

Cryptanalysis

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.