RC5

This article explains the encryption process. For the data transfer protocol see RC-5 .

RC5
One round (two semicircles) of RC5
developer	Ronald L. Rivest
Released	1994
Key length	1 to 2040 bits
Block size	32, 64 or 128 bit
structure	Feistel cipher
Round	1 to 255 rounds, recommended at least 16 rounds
Best known cryptanalysis
RC5-32 / 12 is susceptible to differential cryptanalysis on 2 44 selected plaintext blocks.

RC5 ( R ivest C ipher 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 the same size and then encrypted or decrypted through repeated use 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 to have a simple and fast cipher. It is based on data-dependent rotations , the suitability of which as 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 plain text, key and ciphertext , which Claude Shannon called “ confusion ” in 1949 and which is important for secure operation. An S-Box creates a lot of confusion, as one can largely freely choose how an -S-Box , for example, maps the possible values ​​of the input bits to the possible output values . In practical implementation, however, S-Boxes require additional memory and a certain amount of computing effort, since a data word must first be divided into sufficiently small parts that are entered into the S-Box, because a whole word of 16 or more bits is too large for this . Then you have to put the results back together into one word. The fact that S-Boxes are not used makes RC5 very easy and quick and particularly interesting for use in areas with little resources - for example digital hardware with limited chip space. ${\displaystyle b\times b}$ ${\displaystyle 2^{b}}$ ${\displaystyle b}$ ${\displaystyle 2^{b}}$

A specific software implementation that offers different operating modes for chaining blocks - namely CBC , CBC-Pad and CTS  - is specified in the RFC 2040 standard .

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

In the United States, 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 numbers (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 the number of rounds and b 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 ${\displaystyle 2^{w}}$
• the bit-wise XOR operation 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 ${\displaystyle \log _{2}w}$

The primitives operate on words of w bits, each forming a half-block. The security of the algorithm depends largely on the use of rotation, which is the only non-linear 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 designated below with A + B for addition, A⊕B for bitwise XOR operation and A⋘B or A bzw.B for the left / right rotations of the half-block A by (B mod w) bit positions.

Key expansion

With the key expansion, the round keys S ₀ ,…, S _{2r + 1} - where S ₀ and S _{1 are used} for key whitening - are generated from the secret key . The system of round keys is also known as the extended key table. In order to achieve this, the secret key is first split into half-blocks L _i , and if necessary, it is filled with zeros. Then the round keys S _{k are} initialized to a fixed initial state using 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

${\displaystyle S_{0}\leftarrow P}$

${\displaystyle \mathbf {for} \;k\leftarrow 1\;\mathbf {to} \;2r+1\;\mathbf {do} }$:

${\displaystyle S_{k}\leftarrow S_{k-1}+Q}$

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

Ultimately, the half-blocks L _i and S _k are mixed together in three passes:

${\displaystyle k\leftarrow i\leftarrow 0}$

${\displaystyle A\leftarrow B\leftarrow 0}$

${\displaystyle \mathbf {do} \;3\cdot \max {\big (}2(r+1),\lceil b/(w/8)\rceil {\big )}\;\mathbf {times} }$:

${\displaystyle A\leftarrow S_{k}\leftarrow (S_{k}+A+B)\lll 3}$

${\displaystyle B\leftarrow L_{i}\leftarrow (L_{i}+A+B)\lll (A+B)}$

${\displaystyle k\leftarrow (k+1)\mod {{\big (}2(r+1){\big )}}}$

${\displaystyle i\leftarrow (i+1)\mod {{\big (}\lceil b/(w/8)\rceil {\big )}}}$

Encryption and decryption

A plain text block in little-endian representation is given, which consists of the half-blocks A, B and the round keys S ₀ ,…, S _{2r + 1} . The block is encrypted by:

${\displaystyle A\leftarrow A+S_{0}}$

${\displaystyle B\leftarrow B+S_{1}}$

${\displaystyle \mathbf {for} \;k\leftarrow 1\;\mathbf {to} \;r\;\mathbf {do} }$:

${\displaystyle A\leftarrow {\big (}(A\oplus B)\lll B{\big )}+S_{2k}}$

${\displaystyle B\leftarrow {\big (}(B\oplus A)\lll A{\big )}+S_{2k+1}}$

Each semicircle corresponds to a round of a Feistel cipher . The decryption of a corresponding ciphertext block from the half blocks A, B is analogous:

${\displaystyle \mathbf {for} \;k\leftarrow r\;\mathbf {downto} \;1\;\mathbf {do} }$:

${\displaystyle B\leftarrow {\big (}(B-S_{2k+1})\ggg A{\big )}\oplus A}$

${\displaystyle A\leftarrow {\big (}(A-S_{2k})\ggg B{\big )}\oplus B}$

${\displaystyle B\leftarrow B-S_{1}}$

${\displaystyle A\leftarrow A-S_{0}}$

Cryptanalysis

A variant called RC5⊕ is also used for cryptanalysis purposes, in which the modular addition of the half-blocks is completely exchanged for bit-by-bit XOR. This variant is cryptographically weaker - due to an XOR relationship between bits of the cipher texts and bits of the round key linked to the plain text - and is primarily suitable as a simplification for analyzing the data-dependent rotations.

The analog variant RC5P, which only uses additions, has also proven to be cryptographically weaker. In 1999, John Kelsey, Bruce Schneier and David Wagner showed with a new type of attack - they called "mod n" cryptanalysis - that ciphers that are based only on additions and rotations can generally be broken. The attack is based on correlations between plain text and ciphertext from the last round when viewed 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 the mixing of the operations “+” and “⊕” is essential for the security of RC5.

Chosen plaintext attacks

Kaliski and Yin from RSA Laboratories showed in 1995 that for differential cryptanalysis against RC5-32 / 9 2 ⁴⁵ pairs of selected plaintexts and associated ciphertexts are required, which corresponds approximately to the strength of 16-round DES . For RC5-32 / 12, however, 2 ⁶² such pairs are required. The attack reconstructs bits of L _2r , from which information about S _{2r + 1} can be derived. Once S _{2r + 1 is} known, a simpler analysis can be applied to RC5 with a reduced number of laps. 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. The attack by Knudsen and Meier uses the data dependency of the cyclical rotations by identifying such plain texts that do not rotate within the first few rounds. In this way the number of plain text pairs selected is reduced to 2 ³⁹ for RC5-32 / 9 and up to 2 ⁵⁴ for RC5-32 / 12. For RC5-64 - from an academic point of view - the 16 rounds with 2 ⁸³ required, selected plaintext pairs originally proposed by Rivest are not sufficiently secure against differential cryptanalysis.

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

As part of the selection of the new Advanced Encryption Standard, Takeshi Shimoyama (Fujitsu), Kiyofumi Takeuchi and Juri Hayakawa (Chuo University) submitted a modified variant of an attack on RC6 presented in 1999 by Knudsen and Meier, adapted to RC5. This correlation attack , based on the χ² test , reconstructs the last round key for RC5 with 17 semicircles using ²⁵⁴ selected plain texts with a success probability of 80%. The authors also showed that the attack for about one in 2 ²⁰ keys has the same probability of breaking RC5 with the full number of rounds.

Known plain text attacks

Kaliski and Yin showed that a reconstruction of the extended key table using linear approximations requires ^2,47 known plaintexts for five rounds and thus achieves the strength of DES compared to linear cryptanalysis. If there are more than six rounds, the attack described by these authors is pointless. According to Ali Aydın Selçuk of the University of Maryland, this attack is based on false assumptions and is therefore flawed.

In 1997 Howard M. Keys published RC5-32 / 12/16 the existence of linear weak keys. He found ²²⁸ keys for which a linear cryptanalysis can already be carried out with ²¹⁷ known plaintexts. There are also 2 ⁶⁸ keys for which the cipher can theoretically be broken with 2 ⁵⁷ plaintexts. The keys depend essentially 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 2 ^{4 + 6r} and RC5-64 / r with 2 ^{3 + 8r} known plaintexts with 90 percent Probability of success. Miyaji, Nonaka and Takii described these results in 2002 as “highly optimistic” (in German: “hochgradig optimistic”) and for their part presented a correlation attack based on the , ² test with which a 90 percent probability of success against RC5-32 / r was included 2 ^{6.14r + 2.27} known plain text is possible.

Other approaches

An attack presented by Handschuh and Heys in 1999 uses the time required for the data-dependent rotations carried out during encryption. While Rivest assumed that modern processors would rotate in time O (1), this is not necessarily the case for embedded systems, for example . The time differences occurring on such platforms allow conclusions to be drawn about the number of rotations carried out and - with complete information - enable a reconstruction of the extended key table for RC5-32 / 12/16 using 2 ²⁰ cipher texts with time requirements Ω (2 ²⁸ ) and O (2 ⁴⁰ ). However, the attack can be avoided by implementing dummy rotations.

Attacks in Practice

The company RSA Security offered as part of its Secret Key Challenge , which was carried out from 1997 to May 2007 - a public call to break specific ciphertexts - $ 10,000 for the decryption of various ciphertexts. The organization distributed.net coordinated distributed attacks on the ciphers and broke RC5-32 / 12/7 within 250 and RC5-32 / 12/8 within 1757 days. The lower endowed “Challenges” RC5-32 / 12/5 and RC5-32 / 12/6 were already broken in 3.5 and 313 hours.

literature

• Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone: Handbook of Applied Cryptography . CRC Press, Boca Raton FL et al. 1996, ISBN 0-8493-8523-7 , pp. 269-270, 280-281 .
• Bruce Schneier : Applied Cryptography. Protocols, Algorithms and Source Code in C . Addison-Wesley Publishing, Bonn et al. 1996, ISBN 3-89319-854-7 , pp. 397-399 ( information security ).

Individual evidence

1. ↑ ^{a b c d e} Ronald L. Rivest : The RC5 encryption algorithm . In: Lecture Notes in Computer Science . tape 1008/1995 . Springer, Berlin / Heidelberg 1995, ISBN 3-540-60590-8 , pp. 86-96 , doi : 10.1007 / 3-540-60590-8 .
2. ↑ Ronald Rivest, Robert W. Baldwin: RFC 2040 - The RC5, RC5-CBC, RC5-CBC-Pad, and RC5-CTS Algorithms .
3. ^ ^{A b} Johan Borst, Bart Preneel, Joos Vandewalle: Linear Cryptanalysis of RC5 and RC6 . In: Lecture Notes in Computer Science . tape 1636 , no. 1999 . Springer, 1999, ISSN  1611-3349 , p. 16 .
4. ↑ U.S. Patent 5,724,428
5. ↑ ^{a b} Alex Biryukov, Eyal Kushilevitz: Improved Cryptanalysis of RC5 . In: Lecture Notes in Computer Science . tape 1403/1998 . Springer, Berlin / Heidelberg 1998, ISBN 3-540-64518-7 , pp. 85-99 , doi : 10.1007 / BFb0054119 .
6. ^ John Kelsey, Bruce Schneier , David Wagner : Mod n Cryptanalysis, with Applications against RC5P and M6 . In: Lecture Notes in Computer Science . tape 1636/1999 . Springer, 1999, ISSN  1611-3349 , p. 139 .
7. ↑ ^{a b} Burton S. Kaliski Jr., Yiqun Lisa Yin: On Differential and Linear Cryptanalysis of the RC5 Encryption Algorithm . In: Lecture Notes in Computer Science . tape 963/1995 . Springer, 1995, ISSN  1611-3349 , p. 171 .
8. ^ ^{A b} Lars R. Knudsen, Willi Meier: Improved Differential Attacks on RC5 . In: Lecture Notes in Computer Science . tape 1109/1996 . Springer, 1996, ISSN  1611-3349 , p. 216 .
9. ↑ Takeshi Shimoyama, Kiyofumi Takeuchi, Juri Hayakawa: Correlation Attack to the Block Cipher RC5 and the Simplified Variants of RC6 . Ed .: NIST. 2000 ( csrc.nist.gov ( Memento of November 8, 2004 in the Internet Archive ) [PDF] on AES3 submitted). Correlation Attack to the Block Cipher RC5 and the Simplified Variants of RC6 ( Memento of the original dated November 8, 2004 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice.  
10. ^ Ali Aydin Selçuk: New Results in Linear Cryptanalysis of RC5 . In: Lecture Notes in Computer Science . tape 1372/1998 . Springer, 1998, ISSN  1611-3349 , p. 1 .
11. ^ Howard M. Heys: Linearly weak keys of RC5 . In: IEE Electronics Letters . tape 33 , no. 10 , May 8, 1997, ISSN  0013-5194 , pp. 836-838 ( engr.mun.ca [PDF]).
12. ^ Atsuko Miyaji, Masao Nonaka, Yoshinori Takii: Known Plaintext Correlation Attack against RC5 . In: Lecture Notes in Computer Science . tape 2271/2002 . Springer, 2002, ISSN  1611-3349 , p. 115-141 .
13. ↑ Helena Handschuh, Howard M. Heys: A Timing Attack on RC5 . In: Lecture Notes in Computer Science . tape 1556/1999 . Springer, 1999, ISSN  1611-3349 , p. 631 .
14. ^ Project RC5 from distributed.net
15. ↑ Status and Prices from RSA Laboratories

This version was added to the list of articles worth reading on August 2007 .