RC5

RC5 ( Rivest Cipher 5) is designed in 1994 by Ronald Rivest symmetric block cipher, which means that both the encrypting as decrypting, the same key is used. It belongs to the class of Feistelchiffren. The data is first divided into blocks of equal size and on repeated application of simple operations - encrypted or decrypted - so-called " primitives ." The block size, the length of the key and the number of repetitions - the " rounds " - are not determined by the algorithm, and be set as a parameter prior to encryption.

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

Unlike many other block ciphers RC5 uses no S-boxes to the by Claude Shannon in 1949 as a " confusion " referred to and to achieve important blurring statistical relationships between plaintext, key and ciphertext for safe operation. An S- Box provides strong confusion, since one can freely choose largely, such as an S- box maps the possible values ​​of the input bits to the possible output values ​​. S-boxes require in the practical implementation but additional memory and also a certain amount of computational effort because you have to share the one data word only into sufficiently small parts that are input to the S-box, for a whole word of 16 bits or more is it too big. Then you have the results again together to make one word. The absence of S-boxes makes RC5 very easy and fast, and in particular for use in resource-poor areas - about digital hardware with limited chip area - interesting.

A concrete software implementation, the different modes of operation to concatenate blocks offers - namely CBC, CBC -Pad and CTS - is specified in RFC 2040.

RC5 served as the base for encryption RC6, which ran for election of the Advanced Encryption Standard.

In the United States, the company RSA Security holds up to 2015 a patent on RC5.

• 2.1 Chosen -plaintext attacks
• 2.2 Known -plaintext attacks
• 2.3 Other approaches
• 2.4 attacks in practice

Description

RC5 has a variable block size (32, 64, or 128 bits ), key lengths ( 0-2040 bits) and round numbers (0-255). A specific choice of these parameters is commonly referred to as " RC5-w/r/b " - w is the length of a word in bits (one block consists of two words ), the number of rounds r and b the length of the key in bytes. Rivest suggested originally 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 used in encryption and decryption of the method are:

• The addition of two words modulo
• The bitwise XOR operation of two words
• The rotation of a word to bit positions b, 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 largely on the use of rotation, which is the only non -linear operation of the process. Also, the successor algorithm RC6 and in parts of the AES candidate MARS are based on data-dependent rotations.

The primitives are designated below by A and B for the addition, A ⊕ B bitwise XOR operation and ⋘ A B and A B ⋙ for Links-/Rechtsrotationen of half block A to ( B mod w) bits.

Key Expansion

With the key expansion are from the secret key, the round keys S0, ..., S2r 1 - being used S0 and S1 for Key Whitening - generated. The system of round keys is referred to as an extended key table. In order to achieve this, the secret key first split into half-blocks Li, if necessary is filled with zeros. Then the round key Sk are initialized by constants on a fixed initial state:

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

Finally, the half-blocks Li and Sk are mixed in three runs with each other:

Encrypting and decrypting

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:

This corresponds to each half round one round of Feistelchiffre. The decryption of a corresponding ciphertext block from the half- blocks A, B is analogous:

Cryptanalysis

To Kryptanalysezwecken also as RC5 ⊕ designated variant is used, in which the modular addition of half-blocks will be completely replaced with bitwise XOR. This variant is - by an existing under XOR relationship between bits of the ciphertext and the bits associated with the plaintext round key - cryptographically weaker and is mainly suitable as a simplification for the analysis of data-dependent rotations.

The analog version RC5P intended to be used additions, has been shown to be cryptographically weak. John Kelsey, Bruce Schneier and David Wagner showed in 1999 with a new type of attack - of them as "mod n" Cryptanalysis referred - that ciphers that are based only on additions and rotations, can generally be broken. The attack is based on correlations between plaintext and ciphertext of the last round when viewed modulo n By a suitable choice of n can be obtained in this way information about the last round key, an attacker. The authors concluded from their results that the mixing of the operations " " and " ⊕ " for the security of RC5 is essential.

Chosen -plaintext attacks

Kaliski and Yin by RSA Laboratories in 1995 showed that for differential cryptanalysis against RC5 -32/ 9245 pairs chosen plaintexts and corresponding ciphertexts are needed, which corresponds approximately to the thickness of 16 - round DES. For RC5-32/12 contrast, 262 such pairs are needed. The attack reconstructed here bits of L2R, from which information about S2r 1 can be derived. 1 When S2r is known a simpler analysis can be applied to RC5 with reduced number of rounds. The selected key length is meaningless for this attack.

Knudsen and Meier 1996 improved the differential attack, and also showed the existence of a large number of weak keys. These are caused by the structure of the cipher and are independent of the choice of the expansion algorithm. The attack of Knudsen and Meier uses data dependency of the cyclic rotations by such plaintexts can be identified, which does not rotate within the first few laps. In this way, the number of chosen plaintext pairs is reduced to 239 for RC5 -32/ 9 and up to 254 for RC5-32/12. For RC5 -64 - from an academic point of view - which was originally proposed by Rivest 16 laps required with 283 chosen plaintext pairs is not sufficiently secure against differential cryptanalysis.

A further improvement of differential cryptanalysis has been published by Buryukov Kushilevitz and the Israel Institute of Technology in Haifa in 1998. This attack may apply when the so-called "good" pairs of chosen plaintexts and ciphertexts over Hamming weights of the round differences, reduces the number of required chosen plaintext pairs for RC5-32/12 to 244 The authors concluded that differential attacks against RC5-32/12/16 with 238 and against RC5-64/16/16 with 263 chosen plaintext pairs are possible.

In the wake of the election of the new Advanced Encryption Standard 2000 ranged Takeshi Shimoyama (Fujitsu ), Kiyofumi Takeuchi and Yuri Hayakawa ( Chuo University) a modified and adapted to RC5 variant of a presented by Knudsen and Meier 1999 attack on RC6. This, building on the χ ² - test correlation attack reconstructs the last round key for RC5 with 17/2 rounds using 254 chosen plaintexts with a success probability of 80 %. Likewise, the authors showed that the attack for about a break in 220 keys with equal probability and RC5 with full number of rounds.

Known-plaintext attacks

Kaliski and Yin showed that a reconstruction of the expanded key table using linear approximations already for five rounds requires 247 known plaintexts and thus achieved against linear cryptanalysis of DES strength. If more than six rounds of the attack described by these authors is meaningless. After Ali Aydın Selçuk University of Maryland this attack however, is based on false assumptions and is therefore erroneous.

Published in 1997 Howard M. Keys RC5-32/12/16 the existence of a linear weak key. He found 228 keys for which a linear cryptanalysis can be carried out already with 217 known plaintexts. Furthermore, there are 268 keys for which the cipher can theoretically be broken with 257 plaintexts. The key depend largely on the expansion algorithm used.

A 1999 published by Borst, Preneel, and Vandewalle, building on linear approximations and because of its low memory requirements, practically implementable attack break RC5 -32 / r with 24 6 r and RC5 -64 / r with 23 8 r known plaintexts, with 90 percent probability of success. Miyaji, Nonaka and Takii designated these results in 2002 as "highly optimistic " ( in German: "highly optimistic" ) and presented in turn a building on the χ ² - test correlation attack before, with a 90 percent probability of success against RC5 -32 / r with was 26.14 2.27 r known plaintexts possible.

Other approaches

A glove and Heys imagined 1999 attack exploits the time needed for the tasks performed in the encryption data-dependent rotations. While Rivest assumed modern processors would perform a rotation in time O (1 ), this is not necessary as embedded systems for the case. The time differences arising on such platforms allow conclusions about the number of rotations performed and allow - with complete information - a reconstruction of the expanded key table for RC5-32/12/16 by 220 cipher texts with time needs Ω (228 ) and O ( 240). The attack, however, can be avoided by implementation- based dummy rotations.

Attacks in practice

The RSA Security offered as part of their 1997 conducted up with May 2007, Secret -Key Challenge - a public call for breaking concrete ciphertexts - 10,000 U.S. dollars for the decryption of different 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 doped " Challenges" RC5-32/12/5 and RC5-32/12/6 have been previously broken in 3.5 and 313 hours.