RC5
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  
RC532 / 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  socalled " 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 datadependent 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 Sboxes 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 SBox creates a lot of confusion, as one can largely freely choose how an SBox , for example, maps the possible values of the input bits to the possible output values . In practical implementation, however, SBoxes 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 SBox, 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 SBoxes 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.
A specific software implementation that offers different operating modes for chaining blocks  namely CBC , CBCPad 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 RC532 / 12/16 and RC564 / 16/16 for 64bit 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 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
The primitives operate on words of w bits, each forming a halfblock. The security of the algorithm depends largely 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 datadependent 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 halfblock A by (B mod w) bit positions.
Key expansion
With the key expansion, the round keys S _{0} ,…, S _{2r + 1}  where S _{0} 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 halfblocks 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) 

32  B7E1  9E37 
64  B7E1 5163  9E37 79B9 
128  B7E1 5162 8AED 2A6B  9E37 79B9 7F4A 7C15 

:
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 halfblocks L _{i} and S _{k} are mixed together in three passes:

:
Encryption and decryption
A plain text block in littleendian representation is given, which consists of the halfblocks A, B and the round keys S _{0} ,…, S _{2r + 1} . The block is encrypted by:

:
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:

:
Cryptanalysis
A variant called RC5⊕ is also used for cryptanalysis purposes, in which the modular addition of the halfblocks is completely exchanged for bitbybit 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 datadependent 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 RC532 / 9 2 ^{45} pairs of selected plaintexts and associated ciphertexts are required, which corresponds approximately to the strength of 16round DES . For RC532 / 12, however, 2 ^{62} 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 ^{39} for RC532 / 9 and up to 2 ^{54} for RC532 / 12. For RC564  from an academic point of view  the 16 rounds with 2 ^{83} 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 socalled "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 RC532 / 12 to 2 ^{44} . The authors concluded that differential attacks against RC532 / 12/16 with 2 ^{38} and against RC564 / 16/16 with 2 ^{63} 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 ^{254} selected plain texts with a success probability of 80%. The authors also showed that the attack for about one in 2 ^{20} 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 RC532 / 12/16 the existence of linear weak keys. He found ^{228} keys for which a linear cryptanalysis can already be carried out with ^{217} known plaintexts. There are also 2 ^{68} keys for which the cipher can theoretically be broken with 2 ^{57} 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 RC532 / r with 2 ^{4 + 6r} and RC564 / 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 RC532 / 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 datadependent 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 RC532 / 12/16 using 2 ^{20} cipher texts with time requirements Ω (2 ^{28} ) and O (2 ^{40} ). 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 RC532 / 12/7 within 250 and RC532 / 12/8 within 1757 days. The lower endowed “Challenges” RC532 / 12/5 and RC532 / 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 0849385237 , pp. 269270, 280281 .
 Bruce Schneier : Applied Cryptography. Protocols, Algorithms and Source Code in C . AddisonWesley Publishing, Bonn et al. 1996, ISBN 3893198547 , pp. 397399 ( information security ).
Individual evidence
 ↑ ^{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 3540605908 , pp. 8696 , doi : 10.1007 / 3540605908 .
 ↑ Ronald Rivest, Robert W. Baldwin: RFC 2040  The RC5, RC5CBC, RC5CBCPad, and RC5CTS Algorithms .
 ^ ^{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 16113349 , p. 16 .
 ↑ U.S. Patent 5,724,428
 ↑ ^{a } ^{b} Alex Biryukov, Eyal Kushilevitz: Improved Cryptanalysis of RC5 . In: Lecture Notes in Computer Science . tape 1403/1998 . Springer, Berlin / Heidelberg 1998, ISBN 3540645187 , pp. 8599 , doi : 10.1007 / BFb0054119 .
 ^ 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 16113349 , p. 139 .
 ↑ ^{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 16113349 , p. 171 .
 ^ ^{A } ^{b} Lars R. Knudsen, Willi Meier: Improved Differential Attacks on RC5 . In: Lecture Notes in Computer Science . tape 1109/1996 . Springer, 1996, ISSN 16113349 , p. 216 .
 ↑ 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.
 ^ Ali Aydin Selçuk: New Results in Linear Cryptanalysis of RC5 . In: Lecture Notes in Computer Science . tape 1372/1998 . Springer, 1998, ISSN 16113349 , p. 1 .
 ^ Howard M. Heys: Linearly weak keys of RC5 . In: IEE Electronics Letters . tape 33 , no. 10 , May 8, 1997, ISSN 00135194 , pp. 836838 ( engr.mun.ca [PDF]).
 ^ Atsuko Miyaji, Masao Nonaka, Yoshinori Takii: Known Plaintext Correlation Attack against RC5 . In: Lecture Notes in Computer Science . tape 2271/2002 . Springer, 2002, ISSN 16113349 , p. 115141 .
 ↑ Helena Handschuh, Howard M. Heys: A Timing Attack on RC5 . In: Lecture Notes in Computer Science . tape 1556/1999 . Springer, 1999, ISSN 16113349 , p. 631 .
 ^ Project RC5 from distributed.net
 ↑ Status and Prices from RSA Laboratories