RC6
RC6 is a symmetric-key block cipher algorithm derived from RC5, developed by Ronald Rivest, Matt Robshaw, Ray Sidney, and Yiqun Lisa Yin in 1998 specifically to meet the cryptographic requirements of the U.S. National Institute of Standards and Technology's (NIST) Advanced Encryption Standard (AES) selection process.[1] The algorithm is parameterized as RC6-w/r/b, where w denotes the word size in bits (typically 32 for AES compatibility), r the number of rounds (20 for AES submissions), and b the key length in bytes (16, 24, or 32 for AES key sizes of 128, 192, or 256 bits), enabling flexible block sizes of 4w bits while emphasizing efficiency on 32-bit processors through data-dependent rotations and multiplication by a fixed odd constant.[1] RC6 advances RC5 by incorporating four working registers, quadratic behavior in its core function, and a key schedule that expands the user key into subkeys using pseudorandom mixing, providing resistance to known attacks like differential and linear cryptanalysis as demonstrated in its security evaluation.[1][2] Submitted by RSA Laboratories, RC6 advanced to the final round of five AES candidates in 1999 but was not selected, with Rijndael chosen as the basis for FIPS 197 (AES) due to its performance across platforms and perceived security margins, though RC6 excelled in software speed on certain hardware.[3][4] Post-AES, RC6 has seen implementations in embedded systems and niche applications, with ongoing cryptanalytic scrutiny confirming no practical breaks against full-round versions under standard parameters.[2]History and Development
Origins in RC5 and AES Submission
RC6 originated as an evolutionary adaptation of the RC5 block cipher, which Ronald Rivest designed and published in 1995 as a simple, parametric symmetric cipher relying on data-dependent rotations, modular addition, and XOR operations for mixing. While RC5's flexibility in word size, block length, key size, and rounds made it efficient for various implementations, its standard configurations—often using 32- or 64-bit words—did not fully align with the fixed 128-bit block size mandated for AES candidates.[1] To address these constraints for the Advanced Encryption Standard (AES) competition, initiated by NIST on January 2, 1997, to replace the aging Data Encryption Standard (DES), the RC6 designers—Ronald Rivest of MIT, and Matt Robshaw, Ray Sidney, and Yiqun Lisa Yin of RSA Laboratories—modified RC5 by expanding to four 32-bit words for the 128-bit block and introducing integer multiplication as a quadratic operation to improve diffusion and non-linearity.[1][5] This multiplication, applied to two registers followed by rotation by the higher-order bits of the result, provided stronger avalanche effects compared to RC5's purely linear and rotational mixing, while preserving the core iterative structure of three operations per round.[2] RC6 was formally submitted by RSA Laboratories in 1998 as one of 15 initial candidates in the AES process, supporting the required key sizes of 128, 192, and 256 bits with a variable number of rounds (typically 20).[6] The submission emphasized RC6's simplicity, speed on modern processors benefiting from multiplication hardware, and security margins extrapolated from RC5's resistance to known attacks, positioning it as a practical evolution suited for both software and hardware.[1] It advanced through the first two rounds of evaluation but was not selected as a finalist in the third round, where Rijndael ultimately prevailed in 2000.[5]Designers and Key Milestones
RC6 was designed by Ronald L. Rivest of the Massachusetts Institute of Technology, along with Matt Robshaw, Ray Sidney, and Yiqun Lisa Yin, all affiliated with RSA Laboratories at the time.[1] The team drew from Rivest's earlier RC5 cipher, incorporating modifications such as quadratic operations and variable rotation amounts to enhance security and performance for 32-bit architectures, while meeting the AES requirements for a 128-bit block size and key lengths of 128, 192, or 256 bits.[1] RSA Laboratories coordinated the submission, leveraging its expertise in symmetric ciphers, though Rivest provided the foundational design principles rooted in data-dependent rotations and minimal memory usage.[2] Development of RC6 occurred in mid-1998, evolving directly from evaluations of RC5's suitability for the AES process, with the initial technical specification released as version 1.1 on August 20, 1998.[7] This version targeted 20 rounds (denoted RC6-32/20/256 for the AES variant) and was submitted to NIST during the AES candidate solicitation period, which ran from April to September 1998.[8] RC6 advanced through the first round of evaluations, announced by NIST in October 1998 among 15 initial candidates, due to its efficiency on modern processors and preliminary security claims against differential and linear cryptanalysis.[8] In April 1999, RC6 was selected as one of five AES finalists alongside MARS, Rijndael, Serpent, and Twofish, based on performance metrics, security analyses, and implementation versatility across platforms.[8] During the second round, the designers addressed community feedback, including potential correlations in low rounds, but RC6 was not chosen as the standard; on October 2, 2000, NIST announced Rijndael (later AES) as the winner, citing its balance of security margins and efficiency.[8] Post-AES, RC6 has seen limited adoption but remains analyzed for its parameterized flexibility and resistance to known attacks up to 14 rounds.[2]Design Principles
Core Parameters and Structure
RC6 designates a family of symmetric-key block ciphers parameterized as RC6-w/r/b, where w represents the word size in bits, r the number of rounds, and b the cipher key length in bytes.[1] The plaintext and ciphertext blocks consist of four w-bit words, denoted as registers A, B, C, and D, yielding a block size of 4w bits.[1] For the AES selection process, the proposal specified w=32 (producing 128-bit blocks), r=20, and b=16, 24, or 32 bytes (equivalent to key sizes of 128, 192, or 256 bits).[1] The cipher's structure is an iterated design with r rounds, employing a four-branch generalized Feistel network that cycles the registers left after each round.[1] Encryption begins with key expansion, which derives an array of 2r+4 subkey words S through S[2r+3] from the input key.[1] The plaintext words are loaded into A, B, C, D, followed by pre-whitening: B ← (B + S) mod 2^w and D ← (D + S[9]) mod 2^w.[1] Each round i (for i=1 to r) computes two temporary w-bit values using a quadratic mixing function:t ← (B × (2×B + 1)) ≪ lg(w) mod 2^w,
u ← (D × (2×D + 1)) ≪ lg(w) mod 2^w,
where × denotes multiplication modulo 2^w and ≪ k is left rotation by k bits.[1] These update the odd-positioned registers:
A ← (( A ⊕ t ) ≪ u ) + S[2i] mod 2^w,
C ← (( C ⊕ u ) ≪ t ) + S[2i+1] mod 2^w,
followed by a left cyclic shift of the registers: (A, B, C, D) ← (B, C, D, A).[1] After all rounds, post-whitening applies: A ← (A + S[2r+2]) mod 2^w and C ← (C + S[2r+3]) mod 2^w, with the resulting words forming the ciphertext.[1] The fundamental operations—addition and subtraction modulo 2^w, bitwise exclusive-or (⊕), and data-dependent left rotation—extend those of RC5 by incorporating the quadratic temporaries t and u to enhance diffusion through variable rotations up to w-1 bits.[1] Decryption inverts this process by reversing the rounds with subtractions instead of additions and right rotations.[1]
Mathematical Foundations and Operations
RC6 is a family of parametric block ciphers denoted RC6-w/r/b, where w is the word size in bits (typically 32 for AES compatibility, yielding a 128-bit block across four words), r is the number of rounds (default 20), and b is the key length in bytes (128, 192, or 256 for AES).[1] The cipher processes the plaintext as four w-bit registers A, B, C, D initialized from the input block, with all arithmetic performed modulo 2^w in the ring of w-bit integers.[1] The core operations leverage integer arithmetic for efficient diffusion: addition (+), subtraction (-), bitwise exclusive-or (⊕), and multiplication (×), all modulo 2^w; left rotation (<<< k), which cyclically shifts the bits of a word left by k positions (where k is taken from the least significant lg w bits of the shift amount, with lg w = ⌈log₂ w⌉ = 5 for w=32); and right rotation (>>> k), defined analogously.[1] These operations exploit hardware support for modular arithmetic and bit shifts to achieve rapid mixing, with multiplication providing quadratic growth in bit dependencies per round.[1] Central to RC6's design is the function f(x) = (((x × (2x + 1)) mod 2^w) <<< lg w), a quadratic transformation followed by a fixed rotation, which generates data-dependent rotation amounts with strong avalanche properties due to the odd multiplier (2x + 1) ensuring full bit involvement in the low-order bits.[1] In each round i (1 to r), the transformation applies f to words B and D to compute t = f(B) and u = f(D), then updates A ← ((A ⊕ t) <<< u) + S[2i] and C ← ((C ⊕ u) <<< t) + S[2i+1], where S is the expanded round key array, followed by a cyclic shift of the registers: (A, B, C, D) ← (B, C, D, A).[1] This structure combines substitution via XOR and multiplication-induced nonlinearity with permutation through variable rotations and word cycling, promoting balanced diffusion across the state.[1] Key expansion derives the 2r + 4 subkey words S from the b-byte key via an iterative process starting with constants P_w = 0xb7e15163 (in hexadecimal, derived from the second golden ratio base-2^w) and Q_w = 0x9e3779b9, mixing the key words L with S over v = 3 × max(⌈b/w⌉, 2r + 4) iterations using additions, XORs, and left rotations by 3: S ← ((S[j-1] + L) <<< 3) ⊕ S ⊕ L, cycling indices modulo their lengths.[1] Encryption prepends subkey additions A ← A + S and D ← D + S[2r + 1], applies the r rounds, then appends B ← B + S[2r + 2] and C ← C + S[2r + 3]; decryption inverts these steps using subtractions and right rotations.[1]Encryption and Decryption Process
Key Expansion
The key expansion in RC6-w/r/b generates an array of 2r + 4 words, denoted S to S[2r + 3], from a user-supplied secret key of b bytes, where w is the word size in bits (typically 32 for AES candidates), r is the number of rounds (e.g., 20), and b ranges from 0 to 255.[1] This process, nearly identical to RC5's key schedule but producing more subkey words to support additional rounds, initializes S with magic constants derived from the base of the natural logarithm e and the golden ratio φ: S = P_w = odd((e - 2) × 2^{w-1}) (hex 0xB7E15163 for w=32), and S = S[i-1] + Q_w for i=1 to 2r+3, where Q_w = odd((φ - 1) × 2^{w-1}) (hex 0x9E3779B9 for w=32).[1] The secret key is copied into an array L of c words, where c = ⌈b / (w/8)⌉, with padding zeros if b is not a multiple of the word byte length, and words loaded in little-endian byte order.[1] A mixing phase then follows, with variables A, B, i, j initialized to 0 and v = 3 × max(c, 2r + 4). For s = 1 to v, the subkeys and key words are updated as S ← (S + A + B) ≪≪ 3 (left rotation by 3 bits) and L ← (L + A + B) ≪≪ (A + B mod 2^w) (left rotation by the sum A + B), followed by i ← (i + 1) mod (2r + 4) and j ← (j + 1) mod c; all arithmetic is performed modulo 2^w.[1] This iterative mixing, performed three times the larger of the key or subkey array sizes, ensures diffusion between the key material and subkeys through additions and data-dependent rotations, leveraging the same even-odd reordering principle as in RC5 to avoid weak keys.[1] For AES-relevant parameters like RC6-32/20/128 (b=16 bytes, c=4 words, 2r+4=44 words), v=3×44=132 iterations suffice, producing a 176-byte expanded key schedule that supports both encryption and decryption without recomputation.[1]The resulting S array provides subkeys S, S[2i+1], and S[2i+2] for the initial transformation and each of the r rounds, with S[2r+3] used in the final step, ensuring the schedule's security relies on the proven resistance of the RC5-like mixing to related-key attacks over extended analysis.[1][2]pseudocodeS[0] ← P_w for i ← 1 to 2r + 3 do S[i] ← S[i-1] + Q_w A ← B ← i ← j ← 0 v ← 3 × max(c, 2r + 4) for s ← 1 to v do S[i] ← (S[i] + A + B) ≪≪ 3 L[j] ← (L[j] + A + B) ≪≪ (A + B) i ← (i + 1) mod (2r + 4) j ← (j + 1) mod cS[0] ← P_w for i ← 1 to 2r + 3 do S[i] ← S[i-1] + Q_w A ← B ← i ← j ← 0 v ← 3 × max(c, 2r + 4) for s ← 1 to v do S[i] ← (S[i] + A + B) ≪≪ 3 L[j] ← (L[j] + A + B) ≪≪ (A + B) i ← (i + 1) mod (2r + 4) j ← (j + 1) mod c
Round Function Details
RC6 processes data in four w-bit working registers denoted as A, B, C, and D, where w is the word size, typically 32 bits for 128-bit blocks as in the AES proposal.[1] Prior to the rounds, the second and fourth words are augmented by adding the first two subkeys: B ← B + S and D ← D + S[9], where S is the expanded key schedule array.[1] Each of the r rounds (r=20 for AES variants) applies a function that leverages data-dependent rotations derived from quadratic expressions, followed by a cyclic shift of the registers.[1] In round i (for i from 1 to r), temporary values t and u are computed as t ← ((B × (2B + 1)) mod 2^w) ≪ lg w and u ← ((D × (2D + 1)) mod 2^w) ≪ lg w, where × denotes multiplication modulo 2^w, + denotes addition modulo 2^w, and lg w is the base-2 logarithm of w (e.g., lg 32 = 5).[1] These temporaries drive rotations: A ← ((A ⊕ t) ≪ u) + S[2i] and C ← ((C ⊕ u) ≪ t) + S[2i+1], with ⊕ as bitwise XOR and ≪ as left rotation by the least significant lg w bits of the right operand.[1] The registers are then rotated as (A, B, C, D) ← (B, C, D, A).[1] This structure emphasizes the quadratic form x(2x + 1) for generating large, data-dependent rotation amounts, enhancing diffusion over fixed rotations in predecessor RC5.[1] [2] Following the r rounds, whitening adds the final subkeys: A ← A + S[2r + 2] and C ← C + S[2r + 3].[1] All operations occur modulo 2^w except rotations, which are bit-level. The design's reliance on multiplication and variable rotations aims for efficient software implementation on 32-bit processors while resisting linear and differential attacks through high nonlinearity.[1] [2][1]pseudocodefor i = 1 to r do t = (B * (2*B + 1)) << lg w // mod 2^w implicit in operations u = (D * (2*D + 1)) << lg w A = ((A ⊕ t) << u) + S[2*i] C = ((C ⊕ u) << t) + S[2*i + 1] (A, B, C, D) = (B, C, D, A)for i = 1 to r do t = (B * (2*B + 1)) << lg w // mod 2^w implicit in operations u = (D * (2*D + 1)) << lg w A = ((A ⊕ t) << u) + S[2*i] C = ((C ⊕ u) << t) + S[2*i + 1] (A, B, C, D) = (B, C, D, A)
Decryption Inverse
The decryption process in RC6 inverts the encryption by applying the inverse operations in reverse order, ensuring perfect reversibility for the same expanded key schedule. Operations such as modular addition are inverted with modular subtraction (all arithmetic modulo $2^w, where w is the word size, typically 32), left rotations (\lll) are inverted with right rotations (\ggg), and XOR remains its own inverse. The round keys S{{grok:render&&&type=render_inline_citation&&&citation_id=0&&&citation_type=wikipedia}} to S[2r+3] are applied in reverse indexing, with the register permutation (A, B, C, D) \to (D, A, B, C) undone by its inverse (A, B, C, D) \to (B, C, D, A). This structure leverages the involutory nature of certain steps, such as the quadratic function f(x) = x(2x + 1) \lll \lg w, which is inverted through the data-dependent rotations derived from it.[1] The decryption algorithm begins by loading the ciphertext into registers A, B, C, D (each w bits) and subtracting the final round keys from C and A: C \leftarrow C - S[2r + 3], \quad A \leftarrow A - S[2r + 2] For each round i from r down to 1, the steps are:- Rotate registers: (A, B, C, D) \leftarrow (D, A, B, C)
- Compute t = B(2B + 1) \lll \lg w and u = D(2D + 1) \lll \lg w
- Invert the inner operations: C \leftarrow ((C \oplus u) \ggg t) + S[2i + 1], A \leftarrow ((A \oplus t) \ggg u) + S[2i]
This formulation ensures that applying decryption to ciphertext recovers the exact plaintext, as verified in the algorithm's design and implementations.[1]Input: [Ciphertext](/page/Ciphertext) (four w-bit words A, B, C, D); number of rounds r Output: [Plaintext](/page/Plaintext) (four w-bit words A, B, C, D) C ← C - S[2r+3]; A ← A - S[2r+2] for i = r downto 1 do t ← (B × (2B + 1)) ≪ lg w; u ← (D × (2D + 1)) ≪ lg w C ← ((C ⊕ u) ≫ t) + S[2i+1]; A ← ((A ⊕ t) ≫ u) + S[2i] (A, B, C, D) ← (B, C, D, A) B ← B - S[1]; D ← D - S[0]Input: [Ciphertext](/page/Ciphertext) (four w-bit words A, B, C, D); number of rounds r Output: [Plaintext](/page/Plaintext) (four w-bit words A, B, C, D) C ← C - S[2r+3]; A ← A - S[2r+2] for i = r downto 1 do t ← (B × (2B + 1)) ≪ lg w; u ← (D × (2D + 1)) ≪ lg w C ← ((C ⊕ u) ≫ t) + S[2i+1]; A ← ((A ⊕ t) ≫ u) + S[2i] (A, B, C, D) ← (B, C, D, A) B ← B - S[1]; D ← D - S[0]
Security Analysis
Resistance to Cryptanalytic Attacks
RC6 exhibits strong resistance to differential cryptanalysis, with the designers providing rigorous bounds demonstrating that the maximum probability of a differential characteristic over the full recommended rounds (typically 20 for AES-strength parameters) is exponentially small, on the order of $2^{-200} or lower for 128-bit blocks, rendering exhaustive search infeasible.[2] This resistance stems from the variable rotation amounts derived from data-dependent quadratic operations, which decorrelate inputs across rounds and thwart high-probability differentials.[10] Linear cryptanalysis similarly faces substantial barriers, as the bias in linear approximations decays rapidly due to the non-linear mixing in the round function; analysis shows that even multi-linear approximations require $2^{100} or more known plaintexts to detect biases with statistical confidence, far exceeding practical data availability for full-round RC6.[2] No linear trails with non-negligible bias propagate beyond 10-12 rounds, and the key schedule's expansion further randomizes subkey influences, preventing effective partitioning attacks.[11] For reduced-round variants, cryptanalysts have identified theoretical weaknesses, such as correlation-based distinguishers exploiting linear relations in the rotation mechanism, which can differentiate up to 15 rounds from random permutations with $2^{64} queries under weak keys, though the full 20-round structure remains unaffected.[12] Multiple linear cryptanalysis breaks 18-round RC6 with weak keys using $2^{112} known plaintexts and comparable time, but these require specific key classes and do not extend to standard parameters or full rounds.[13] Key-recovery attacks via multiset or impossible differentials target up to 10-12 rounds without whitening layers, with complexities around $2^{100} operations, underscoring a security margin of at least 8 rounds against such methods.[14][15] No practical attacks—such as algebraic, integral, or boomerang cryptanalysis—have been published that compromise full-round RC6 under recommended parameters (128-bit block, 128-256-bit keys, 20 rounds), and independent evaluations during the AES selection process confirmed its robustness against then-known techniques, with no disqualifying vulnerabilities identified.[16][17] The absence of structural flaws, combined with the data-dependent rotations, positions RC6 as secure against generic attacks like meet-in-the-middle, which would demand $2^{128} time for the block size.[2]Performance and Efficiency Evaluations
RC6 demonstrates strong software performance on 32-bit processors, achieving encryption rates of approximately 254 cycles per 128-bit block in optimized assembly on a 266 MHz Pentium II, equivalent to roughly 12.6 MB/s throughput.[1] In ANSI C implementations on the same platform, encryption required 616 cycles per block, yielding about 5.19 MB/s.[1] Decryption performance is comparable, at 566 cycles per block in C and 254 in assembly, reflecting the algorithm's symmetric design with efficient inverse operations.[1] Key setup times range from 2,350 to 2,360 cycles for 128- to 256-bit keys in C, scaling linearly with key length due to the key expansion process involving modular reductions.[1] On platforms like the Pentium Pro, RC6 outperformed other AES finalists in first-round evaluations, achieving up to 97.8 Mbit/s encryption speeds in certain compiler configurations and leading in Java implementations with 25.2 Mbit/s per RSA Labs benchmarks versus NIST's lower figures for competitors.[18] However, performance varies by architecture: on 64-bit systems such as DEC Alpha, RC6 required about 467 cycles per block, lagging behind optimized candidates like DFC at 304 cycles.[18] For constrained 8-bit environments like Intel MCS-51 microcontrollers, encryption demands around 12,700 cycles per block plus 27,000–43,000 for key scheduling, with 176 bytes of RAM usage, rendering it less efficient than lighter alternatives.[18]| Platform | Implementation | Cycles per Block (Encryption) | Throughput (MB/s, scaled to 200 MHz) |
|---|---|---|---|
| Pentium II (266 MHz) | Assembly | 254 | 12.6[1] |
| Pentium II (266 MHz) | ANSI C | 616 | 5.19[1] |
| Pentium Pro (200 MHz equiv.) | Optimized C | ~273 (minimal rounds) | N/A (faster than Rijndael's 440)[18] |
| DEC Alpha | C | 467 | N/A[18] |