RC5 - Misplaced Pages

(Redirected from RC5 encryption algorithm) Block cipher This article is about the block cipher. For the infrared remote control protocol, see RC-5.

RC5
General
One round (two half-rounds) of the RC5 block cipher
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 public cryptanalysis
12-round RC5 (with 64-bit blocks) is susceptible to a differential attack using 2 chosen plaintexts.

In cryptography, RC5 is a symmetric-key block cipher notable for its simplicity. Designed by Ronald Rivest in 1994, 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.

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

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:

w – The length of a word in bits, typically 16, 32 or 64. Encryption is done in 2-word blocks.
u = w/8 – The length of a word in bytes.
b – The length of the key in bytes.
K – The key, considered as an array of bytes (using 0-based indexing).
c – The length of the key in words (or 1, if b = 0).
L – A temporary working array used during key scheduling, initialized to the key in words.
r – The number of rounds to use when encrypting data.
t = 2(r+1) – the number of round subkeys required.
S – The round subkey words.
P_w – The first magic constant, defined as Odd((e − 2) × 2), where Odd is the nearest odd integer to the given input, e is the base of the natural logarithm, and w is defined above. For common values of w, the associated values of P_w are given here in hexadecimal:
- For w = 16: 0xB7E1
- For w = 32: 0xB7E15163
- For w = 64: 0xB7E151628AED2A6B
Q_w – The second magic constant, defined as Odd((𝜙 − 1) × 2), where Odd is the nearest odd integer to the given input, where 𝜙 is the golden ratio, and w is defined above. For common values of w, the associated values of Q_w are given here in hexadecimal:
- For w = 16: 0x9E37
- For w = 32: 0x9E3779B9
- For w = 64: 0x9E3779B97F4A7C15

# Break K into words
# u = w / 8
c = ceiling(max(b, 1) / u)
# L is initially a c-length list of 0-valued w-length words
for i = b-1 down to 0 do:
    L = (L <<< 8) + K
# Initialize key-independent pseudorandom S array
# S is initially a t=2(r+1) length list of undefined w-length words
S = P_w
for i = 1 to t-1 do:
    S = S + Q_w
# The main key scheduling loop
i = j = 0
A = B = 0
do 3 * max(t, c) times:
    A = S = (S + A + B) <<< 3
    B = L = (L + A + B) <<< (A + B)
    i = (i + 1) % t
    j = (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.

void RC5_SETUP(unsigned char *K)
{
   // w = 32, r = 12, b = 16
   // c = max(1, ceil(8 * b/w))
   // t = 2 * (r+1)
   WORD i, j, k, u = w/8, A, B, L;
   for (i = b-1, L = 0; i != -1; i--)
      L = (L << 8) + K;
   for (S = P, i = 1; i < t; i++)
      S = S + Q;
   for (A = B = i = j = k = 0; k < 3 * t; k++, i = (i+1) % t, j = (j+1) % c)
   {
      A = S = ROTL(S + (A + B), 3);
      B = L = ROTL(L + (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, B - The two words composing the block of plaintext to be encrypted.

A = A + S
B = B + S
for i = 1 to r do:
    A = ((A ^ B) <<< B) + S
    B = ((B ^ A) <<< A) + S
# The ciphertext block consists of the two-word wide block composed of A and B, in that order.
return A, B

The example C code given by Rivest is this.

void RC5_ENCRYPT(WORD *pt, WORD *ct)
{
   WORD i, A = pt + S, B = pt + S;
   for (i = 1; i <= r; i++)
   {
      A = ROTL(A ^ B, B) + S;
      B = ROTL(B ^ A, A) + S;
   }
   ct = A; ct = B;
}

Decryption

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

for i = r down to 1 do:
    B = ((B - S) >>> A) ^ A
    A = ((A - S) >>> B) ^ B
B = B - S
A = A - S
return A, B

The example C code given by Rivest is this.

void RC5_DECRYPT(WORD *ct, WORD *pt)
{
   WORD i, B=ct, A=ct;
   for (i = r; i > 0; i--)
   {
      B = ROTR(B - S, A) ^ A;
      A = ROTR(A - S, B) ^ B;
   }
   pt = B - S; pt = A - S;
}

Cryptanalysis

Twelve-round RC5 (with 64-bit blocks) is susceptible to a differential attack using 2 chosen plaintexts. 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. 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. The task has inspired many new and novel developments in the field of cluster computing.

RSA Security, which had a (now expired) patent on the algorithm, offered a series of US$10,000 prizes for breaking ciphertexts encrypted with RC5, but these contests were discontinued as of May 2007. 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.

References

^ Biryukov, Alex; Kushilevitz, Eyal (31 May 1998). Improved Cryptanalysis of RC5 (PDF). EUROCRYPT 1998. doi:10.1007/BFb0054119.
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.
http://people.csail.mit.edu/rivest/Rivest-rc5rev.pdf Archived 2018-09-21 at the Wayback Machine
^ "distributed.net: Project RC5". www.distributed.net. Retrieved 14 December 2019.
RC5-72 / Overall Project Stats
"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.
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.
"distributed.net: staff blogs – 2008 – September – 08". Retrieved 15 December 2019.

External links

v t e Block ciphers (security summary)
Common algorithms	AES Blowfish DES (internal mechanics, Triple DES) Serpent SM4 Twofish
Less common algorithms	ARIA Camellia CAST-128 GOST IDEA LEA RC5 RC6 SEED Skipjack TEA XTEA
Other algorithms	3-Way Adiantum Akelarre Anubis Ascon BaseKing BassOmatic BATON BEAR and LION CAST-256 Chiasmus CIKS-1 CIPHERUNICORN-A CIPHERUNICORN-E CLEFIA CMEA Cobra COCONUT98 Crab Cryptomeria/C2 CRYPTON CS-Cipher DEAL DES-X DFC E2 FEAL FEA-M FROG G-DES Grand Cru Hasty Pudding cipher Hierocrypt ICE IDEA NXT Intel Cascade Cipher Iraqi Kalyna KASUMI KeeLoq KHAZAD Khufu and Khafre KN-Cipher Kuznyechik Ladder-DES LOKI (97, 89/91) Lucifer M6 M8 MacGuffin Madryga MAGENTA MARS Mercy MESH MISTY1 MMB MULTI2 MultiSwap New Data Seal NewDES Nimbus NOEKEON NUSH PRESENT Prince Q RC2 REDOC Red Pike S-1 SAFER SAVILLE SC2000 SHACAL SHARK Simon Speck Spectr-H64 Square SXAL/MBAL Threefish Treyfer UES xmx XXTEA Zodiac
Design	Feistel network Key schedule Lai–Massey scheme Product cipher S-box P-box SPN Confusion and diffusion Round Avalanche effect Block size Key size Key whitening (Whitening transformation)
Attack (cryptanalysis)	Brute-force (EFF DES cracker) MITM Biclique attack 3-subset MITM attack Linear (Piling-up lemma) Differential Impossible Truncated Higher-order Differential-linear Distinguishing (Known-key) Integral/Square Boomerang Mod n Related-key Slide Rotational Side-channel Timing Power-monitoring Electromagnetic Acoustic Differential-fault XSL Interpolation Partitioning Rubber-hose Black-bag Davies Rebound Weak key Tau Chi-square Time/memory/data tradeoff
Standardization	AES process CRYPTREC NESSIE NSA Suite B CNSA
Utilization	Initialization vector Mode of operation Padding

v t e Cryptography
General	History of cryptography Outline of cryptography Classical cipher Cryptographic protocol Authentication protocol Cryptographic primitive Cryptanalysis Cryptocurrency Cryptosystem Cryptographic nonce Cryptovirology Hash function Cryptographic hash function Key derivation function Secure Hash Algorithms Digital signature Kleptography Key (cryptography) Key exchange Key generator Key schedule Key stretching Keygen Machines Cryptojacking malware Ransomware Random number generation Cryptographically secure pseudorandom number generator (CSPRNG) Pseudorandom noise (PRN) Secure channel Insecure channel Subliminal channel Encryption Decryption End-to-end encryption Harvest now, decrypt later Information-theoretic security Plaintext Codetext Ciphertext Shared secret Trapdoor function Trusted timestamping Key-based routing Onion routing Garlic routing Kademlia Mix network
Mathematics	Cryptographic hash function Block cipher Stream cipher Symmetric-key algorithm Authenticated encryption Public-key cryptography Quantum key distribution Quantum cryptography Post-quantum cryptography Message authentication code Random numbers Steganography
Category

Categories: