 One round (two half-rounds) of the RC5 block cipher | |
| General | |
|---|---|
| Designers | Ron Rivest |
| First published | 1994 |
| 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 publiccryptanalysis | |
| 12-round RC5 (with 64-bit blocks) is susceptible to adifferential attack using 244 chosen plaintexts.[1] | |
Incryptography,RC5 is asymmetric-keyblock cipher notable for its simplicity. Designed byRonald Rivest in 1994,[2]RC stands for "Rivest Cipher", or alternatively, "Ron's Code" (compareRC2 andRC4). TheAdvanced Encryption Standard (AES) candidateRC6 was based on RC5.
Unlike many schemes, RC5 has a variableblock size (32, 64 or 128bits),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 acryptographic primitive.[citation needed] RC5 also consists of a number ofmodular additions andeXclusive OR (XOR)s. The general structure of the algorithm is aFeistel-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 essentiallyone-way function with the binary expansions of bothe and thegolden 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.
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]
The key expansion algorithm is illustrated below, first inpseudocode, then exampleC 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 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 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];}
Twelve-round RC5 (with 64-bit blocks) is susceptible to adifferential attack using 244 chosen plaintexts.[1] 18–20 rounds are suggested as sufficient protection.
A number of these challenge problems have been tackled usingdistributed computing, organised byDistributed.net. Distributed.net hasbrute-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 breakingciphertexts 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 theFree Software Foundation will receive US$2,000.[8]
