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 (now expired) 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

References

  1. 1 2 Biryukov, Alex; Kushilevitz, Eyal (31 May 1998). Improved Cryptanalysis of RC5 (PDF). EUROCRYPT 1998. doi: 10.1007/BFb0054119 .
  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. ↑ "The RC5 Encryption Algorithm" (PDF). people.csail.mit.edu. Archived from the original (PDF) on September 21, 2018.
  4. 1 2 "distributed.net: Project RC5". www.distributed.net. Retrieved 14 December 2019.
  5. ↑ "stats.distributed.net - RC5-72 Overall Project Stats". stats.distributed.net.
  6. ↑ "PlayStation 3 supercomputer places UMass Dartmouth #1 in the world in code cracking challenge list" (Press release). University of Massachusetts Dartmouth. 24 September 2014. Archived from the original on 2022-06-29. Retrieved 2024-01-24.
  7. ↑ Rivest, R. L, "Block Encryption Algorithm With Data Dependent Rotation", U.S. patent 5,724,428 , issued on 3 March 1998, expired 1 November 2015.
  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.