RC5

Last updated
RC5
RC5 InfoBox Diagram.svg
One round (two half-rounds) of the RC5 block cipher
General
Designers Ron Rivest
First published1994
Successors RC6, Akelarre
Cipher detail
Key sizes 0 to 2040 bits (128 suggested)
Block sizes 32, 64 or 128 bits (64 suggested)
Structure Feistel-like network
Rounds 1-255 (12 suggested originally)
Best public cryptanalysis
12-round RC5 (with 64-bit blocks) is susceptible to a differential attack using 244 chosen plaintexts. [1]

In cryptography, RC5 is a symmetric-key block cipher notable for its simplicity. Designed by Ronald Rivest in 1994, [2] RC stands for "Rivest Cipher", or alternatively, "Ron's Code" (compare RC2 and RC4). The Advanced Encryption Standard (AES) candidate RC6 was based on RC5.

Contents

Description

Unlike many schemes, RC5 has a variable block size (32, 64 or 128 bits), key size (0 to 2040 bits), and number of rounds (0 to 255). The original suggested choice of parameters were a block size of 64 bits, a 128-bit key, and 12 rounds.

A key feature of RC5 is the use of data-dependent rotations; one of the goals of RC5 was to prompt the study and evaluation of such operations as a cryptographic primitive.[ citation needed ] RC5 also consists of a number of modular additions and eXclusive OR (XOR)s. The general structure of the algorithm is a Feistel-like network, similar to RC2. The encryption and decryption routines can be specified in a few lines of code. The key schedule, however, is more complex, expanding the key using an essentially one-way function with the binary expansions of both e and the golden ratio as sources of "nothing up my sleeve numbers". The tantalising simplicity of the algorithm together with the novelty of the data-dependent rotations has made RC5 an attractive object of study for cryptanalysts.[ according to whom? ] RC5 is basically denoted as RC5-w/r/b where w=word size in bits, r=number of rounds, b=number of bytes in the key.

Algorithm

RC5 encryption and decryption both expand the random key into 2(r+1) words that will be used sequentially (and only once each) during the encryption and decryption processes. All of the below comes from Rivest's revised paper on RC5. [3]

Key expansion

The key expansion algorithm is illustrated below, first in pseudocode, then example C code copied directly from the reference paper's appendix.

Following the naming scheme of the paper, the following variable names are used:

# Break K into words# u = w / 8c=ceiling(max(b,1)/u)# L is initially a c-length list of 0-valued w-length wordsfori=b-1downto0do:L[i/u]=(L[i/u]<<<8)+K[i]# Initialize key-independent pseudorandom S array# S is initially a t=2(r+1) length list of undefined w-length wordsS[0]=P_wfori=1tot-1do:S[i]=S[i-1]+Q_w# The main key scheduling loopi=j=0A=B=0do3*max(t,c)times:A=S[i]=(S[i]+A+B)<<<3B=L[j]=(L[j]+A+B)<<<(A+B)i=(i+1)%tj=(j+1)%c# return S

The example source code is provided from the appendix of Rivest's paper on RC5. The implementation is designed to work with w = 32, r = 12, and b = 16.

voidRC5_SETUP(unsignedchar*K){// w = 32, r = 12, b = 16// c = max(1, ceil(8 * b/w))// t = 2 * (r+1)WORDi,j,k,u=w/8,A,B,L[c];for(i=b-1,L[c-1]=0;i!=-1;i--)L[i/u]=(L[i/u]<<8)+K[i];for(S[0]=P,i=1;i<t;i++)S[i]=S[i-1]+Q;for(A=B=i=j=k=0;k<3*t;k++,i=(i+1)%t,j=(j+1)%c){A=S[i]=ROTL(S[i]+(A+B),3);B=L[j]=ROTL(L[j]+(A+B),(A+B));}}

Encryption

Encryption involved several rounds of a simple function, with 12 or 20 rounds seemingly recommended, depending on security needs and time considerations. Beyond the variables used above, the following variables are used in this algorithm:

A=A+S[0]B=B+S[1]fori=1tordo:A=((A^B)<<<B)+S[2*i]B=((B^A)<<<A)+S[2*i+1]# The ciphertext block consists of the two-word wide block composed of A and B, in that order.returnA,B

The example C code given by Rivest is this.

voidRC5_ENCRYPT(WORD*pt,WORD*ct){WORDi,A=pt[0]+S[0],B=pt[1]+S[1];for(i=1;i<=r;i++){A=ROTL(A^B,B)+S[2*i];B=ROTL(B^A,A)+S[2*i+1];}ct[0]=A;ct[1]=B;}

Decryption

Decryption is a fairly straightforward reversal of the encryption process. The below pseudocode shows the process.

fori=rdownto1do:B=((B-S[2*i+1])>>>A)^AA=((A-S[2*i])>>>B)^BB=B-S[1]A=A-S[0]returnA,B

The example C code given by Rivest is this.

voidRC5_DECRYPT(WORD*ct,WORD*pt){WORDi,B=ct[1],A=ct[0];for(i=r;i>0;i--){B=ROTR(B-S[2*i+1],A)^A;A=ROTR(A-S[2*i],B)^B;}pt[1]=B-S[1];pt[0]=A-S[0];}

Cryptanalysis

Twelve-round RC5 (with 64-bit blocks) is susceptible to a differential attack using 244 chosen plaintexts. [1] 18–20 rounds are suggested as sufficient protection.

A number of these challenge problems have been tackled using distributed computing, organised by Distributed.net. Distributed.net has brute-forced RC5 messages encrypted with 56-bit and 64-bit keys and has been working on cracking a 72-bit key since November 3, 2002. [4] As of July 26, 2023, 10.409% of the keyspace has been searched and based on the rate recorded that day, it would take a little more than 59 years to complete 100% of the keyspace. [5] The task has inspired many new and novel developments in the field of cluster computing. [6]

RSA Security, which had a patent on the algorithm, [7] offered a series of US$10,000 prizes for breaking ciphertexts encrypted with RC5, but these contests were discontinued as of May 2007. [4] As a result, distributed.net decided to fund the monetary prize. The individual who discovers the winning key will receive US$1,000, their team (if applicable) will receive US$1,000, and the Free Software Foundation will receive US$2,000. [8]

See also

Related Research Articles

<span class="mw-page-title-main">Advanced Encryption Standard</span> Standard for the encryption of electronic data

The Advanced Encryption Standard (AES), also known by its original name Rijndael, is a specification for the encryption of electronic data established by the U.S. National Institute of Standards and Technology (NIST) in 2001.

Blowfish is a symmetric-key block cipher, designed in 1993 by Bruce Schneier and included in many cipher suites and encryption products. Blowfish provides a good encryption rate in software, and no effective cryptanalysis of it has been found to date. However, the Advanced Encryption Standard (AES) now receives more attention, and Schneier recommends Twofish for modern applications.

In cryptography, a block cipher is a deterministic algorithm that operates on fixed-length groups of bits, called blocks. Block ciphers are the elementary building blocks of many cryptographic protocols. They are ubiquitous in the storage and exchange of data, where such data is secured and authenticated via encryption.

<span class="mw-page-title-main">Data Encryption Standard</span> Early unclassified symmetric-key block cipher

The Data Encryption Standard is a symmetric-key algorithm for the encryption of digital data. Although its short key length of 56 bits makes it too insecure for modern applications, it has been highly influential in the advancement of cryptography.

<span class="mw-page-title-main">International Data Encryption Algorithm</span>

In cryptography, the International Data Encryption Algorithm (IDEA), originally called Improved Proposed Encryption Standard (IPES), is a symmetric-key block cipher designed by James Massey of ETH Zurich and Xuejia Lai and was first described in 1991. The algorithm was intended as a replacement for the Data Encryption Standard (DES). IDEA is a minor revision of an earlier cipher Proposed Encryption Standard (PES).

In cryptography, RC4 is a stream cipher. While it is remarkable for its simplicity and speed in software, multiple vulnerabilities have been discovered in RC4, rendering it insecure. It is especially vulnerable when the beginning of the output keystream is not discarded, or when nonrandom or related keys are used. Particularly problematic uses of RC4 have led to very insecure protocols such as WEP.

In cryptography, a block cipher mode of operation is an algorithm that uses a block cipher to provide information security such as confidentiality or authenticity. A block cipher by itself is only suitable for the secure cryptographic transformation of one fixed-length group of bits called a block. A mode of operation describes how to repeatedly apply a cipher's single-block operation to securely transform amounts of data larger than a block.

<span class="mw-page-title-main">RC6</span> Block cipher

In cryptography, RC6 is a symmetric key block cipher derived from RC5. It was designed by Ron Rivest, Matt Robshaw, Ray Sidney, and Yiqun Lisa Yin to meet the requirements of the Advanced Encryption Standard (AES) competition. The algorithm was one of the five finalists, and also was submitted to the NESSIE and CRYPTREC projects. It was a proprietary algorithm, patented by RSA Security.

<span class="mw-page-title-main">Serpent (cipher)</span>

Serpent is a symmetric key block cipher that was a finalist in the Advanced Encryption Standard (AES) contest, in which it ranked second to Rijndael. Serpent was designed by Ross Anderson, Eli Biham, and Lars Knudsen.

Red Pike is a classified United Kingdom government encryption algorithm, proposed for use by the National Health Service by GCHQ, but designed for a "broad range of applications in the British government" Archived 2004-04-23 at the Wayback Machine. Little is publicly known about Red Pike, except that it is a block cipher with a 64-bit block size and 64-bit key length. According to the academic study of the cipher cited below and quoted in a paper by Ross Anderson and Markus Kuhn, it "uses the same basic operations as RC5" and "has no look-up tables, virtually no key schedule and requires only five lines of code"; "the influence of each key bit quickly cascades" and "each encryption involves of the order of 100 operations".

<span class="mw-page-title-main">RC2</span> Block cipher

In cryptography, RC2 is a symmetric-key block cipher designed by Ron Rivest in 1987. "RC" stands for "Ron's Code" or "Rivest Cipher"; other ciphers designed by Rivest include RC4, RC5, and RC6.

In cryptography, ciphertext stealing (CTS) is a general method of using a block cipher mode of operation that allows for processing of messages that are not evenly divisible into blocks without resulting in any expansion of the ciphertext, at the cost of slightly increased complexity.

The RSA Secret-Key Challenge was a series of cryptographic contests organised by RSA Laboratories with the intent of helping to demonstrate the relative security of different encryption algorithms. The challenge ran from 28 January 1997 until May 2007.

<span class="mw-page-title-main">Salsa20</span> Stream ciphers

Salsa20 and the closely related ChaCha are stream ciphers developed by Daniel J. Bernstein. Salsa20, the original cipher, was designed in 2005, then later submitted to the eSTREAM European Union cryptographic validation process by Bernstein. ChaCha is a modification of Salsa20 published in 2008. It uses a new round function that increases diffusion and increases performance on some architectures.

The Blum–Goldwasser (BG) cryptosystem is an asymmetric key encryption algorithm proposed by Manuel Blum and Shafi Goldwasser in 1984. Blum–Goldwasser is a probabilistic, semantically secure cryptosystem with a constant-size ciphertext expansion. The encryption algorithm implements an XOR-based stream cipher using the Blum-Blum-Shub (BBS) pseudo-random number generator to generate the keystream. Decryption is accomplished by manipulating the final state of the BBS generator using the private key, in order to find the initial seed and reconstruct the keystream.

<span class="mw-page-title-main">SM4 (cipher)</span> Block cipher used in Chinese wireless standards

ShāngMì 4 is a block cipher used in the Chinese National Standard for Wireless LAN WAPI and also used with Transport Layer Security.

In cryptography, Galois/Counter Mode (GCM) is a mode of operation for symmetric-key cryptographic block ciphers which is widely adopted for its performance. GCM throughput rates for state-of-the-art, high-speed communication channels can be achieved with inexpensive hardware resources.

In cryptography, M8 is a block cipher designed by Hitachi in 1999. It is a modification of Hitachi's earlier M6 algorithm, designed for greater security and high performance in both hardware and 32-bit software implementations. M8 was registered by Hitachi in March 1999 as ISO/IEC 9979-0020.

ACE is the collection of units, implementing both a public key encryption scheme and a digital signature scheme. Corresponding names for these schemes — «ACE Encrypt» and «ACE Sign». Schemes are based on Cramer-Shoup public key encryption scheme and Cramer-Shoup signature scheme. Introduced variants of these schemes are intended to achieve a good balance between performance and security of the whole encryption system.

<span class="mw-page-title-main">Speck (cipher)</span> Family of block ciphers

Speck is a family of lightweight block ciphers publicly released by the National Security Agency (NSA) in June 2013. Speck has been optimized for performance in software implementations, while its sister algorithm, Simon, has been optimized for hardware implementations. Speck is an add–rotate–xor (ARX) cipher.

References

  1. 1 2 Biryukov A. and Kushilevitz E. (1998). Improved Cryptanalysis of RC5. EUROCRYPT 1998.
  2. ↑ Rivest, R. L. (1994). "The RC5 Encryption Algorithm" (PDF). Proceedings of the Second International Workshop on Fast Software Encryption (FSE) 1994e. pp. 86–96. Archived from the original (PDF) on 2007-04-17. Retrieved 2004-12-18.
  3. ↑ http://people.csail.mit.edu/rivest/Rivest-rc5rev.pdf Archived 2018-09-21 at the Wayback Machine [ bare URL PDF ]
  4. 1 2 "distributed.net: Project RC5". www.distributed.net. Retrieved 14 December 2019.
  5. ↑ RC5-72 / Overall Project Stats
  6. ↑ "Press Release: PlayStation 3 supercomputer places UMass Dartmouth #1 in the world in code cracking challenge list - UMass Dartmouth". Archived from the original on 2014-10-28. Retrieved 2014-10-28.
  7. ↑ Rivest, R. L, "Block Encryption Algorithm With Data Dependent Rotation", U.S. Patent 5,724,428 , issued on 3 March 1998.
  8. ↑ "distributed.net: staff blogs – 2008 – September – 08" . Retrieved 15 December 2019.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.