The RC5 Encryption Algorithm Ronald L. Rivest MIT Laboratory for Computer Science 545 Technology Square Cambridge, MA 02139 USA Introduction RC5 is a fast symmetric block cipher suitable for hardware or software implementations. A novel feature of RC5 is the heavy use of data-dependent rotations. RC5 has a variable-length secret key, providing flexibility in its security level. RC5 is a parameterized algorithm, and a particular RC5 algorithm is designated as RC5-w/r/b. We summarize these parameters below: w - The word size, in bits. The standard value is 32 bits; allowable values are 16, 32, and 64. RC5 encrypts two-word blocks: plaintext and ciphertext blocks are each 2w bits long. r - The number of rounds. Allowable values are 0, 1, ..., 255. b - The number of bytes in the secret key K. Allowable values of b are 0, 1, ..., 255. RC5 uses an "expanded key table" S, derived from the user's supplied secret key K. The size t of table S depends on the number r of rounds: S has t = 2(r+1) words. It is not intended that RC5 be secure for all possible parameter values. On the other hand, choosing the maximum parameter values would be overkill for most applications. We provide a variety of parameter settings so that users may select an encryption algorithm whose security and speed are optimized for their application, while providing an evolutionary path for adjusting their parameters as necessary in the future. As an example, RC5-32/16/7 is an RC5 algorithm with the number of rounds and the length of key equivalent to DES. Unlike unparameterized DES, however, an RC5 user can easily upgrade the above choice to an 80-bit key by moving to RC5-32/16/10. As technology improves, and as the true strength of RC5 algorithms becomes better understood through analysis, the most appropriate parameters can be chosen. We propose RC5-32/12/16 as providing a "nominal" choice of parameters. Further analysis is needed to analyze the security of this choice. Overview of the Algorithm RC5 consists of three components: a key expansion algorithm, an encryption algorithm, and a decryption algorithm. These algorithms use the following three primitive operations (and their inverses). 1. Two's complement addition of words, denoted by "+". This is modulo- [Image] addition. 2. Bit-wise exclusive-OR of words, denoted by [Image]. 3. A left-rotation (or "left-spin") of words: the rotation of word x left by y bits is denoted x <<< y. Only the lg(w) low-order bits of y are used to determine the rotation amount, so that y is interpreted modulo w. Encryption and Decryption We assume that the input block is given in two w-bit registers A and B. We also assume that key-expansion has already been performed, so that the array S[0...t-1] has been computed. Below is the encryption algorithm in pseudo-code. The output is also placed in registers A and B. A = A + S[0]; B = B + S[1]; FOR i = 1 TO r DO A = ((A [Image] B) <<< B) + S[2*i]; B = ((B [Image] A) <<< A) + S[2*i+1]; We note the exceptional simplicity of this five-line algorithm. We also note that each RC5 round updates both registers A and B, whereas a "round" in DES updates only half of its registers. An RC5 "half-round" (one of the assignment statements updating A or B in the body of the loop above) is thus perhaps more analogous to a DES round. The decryption algorithm can be easily derived from the encryption algorithm. Key Expansion The key-expansion routine expands the user's secret key K to fill the expanded key array S, so that S resembles an array of t = 2(r+1) random binary words determined by K. The key expansion algorithm uses two "magic constants" and consists of three simple algorithmic parts. The key-expansion algorithm uses two word-size binary constants [Image] and [Image]. They are defined for arbitrary w as follows: [Image] = Odd((e-2)[Image]) [Image] = Odd(([Image]-1)[Image]) where e = 2.718281828459... (base of natural logarithms) [Image] = 1.618033988749... (golden ratio), and where Odd(x) is the odd integer nearest to x (rounded up if x is an even integer, although this won't happen here). The first algorithmic step of key expansion is to copy the secret key K[0...b-1] into an array L[0...c-1] of c = [Image] words, where u=w/8 is the number of bytes/word. This operation is done in a natural manner, using u consecutive key bytes of K to fill up each successive word in L, low-order byte to high-order byte. Any unfilled byte positions of L are zeroed. The second algorithmic step of key expansion is to initialize array S to a particular fixed (key-independent) pseudo-random bit pattern, using an arithmetic progression modulo [Image] determined by the "magic constants" [Image] and [Image]. Since [Image] is odd, the arithmetic progression has period [Image]. S[0] = [Image]; FOR i = 1 TO t-1 DO S[i] = S[i-1] + [Image]; The third algorithmic step of key expansion is to mix in the user's secret key in three passes over the arrays S and L. More precisely, due to the potentially different sizes of S and L, the larger array will be processed three times, and the other may be handled more times. i = j = 0; A = B = 0; DO 3*max(t,c) TIMES: A = S[i] = (S[i] + A + B) <<< 3; B = L[j] = (L[j] + A + B) <<< (A+B); i = (i + 1) mod(t); j = (j + 1) mod(c); The key-expansion function has a certain amount of "one-wayness": it is not so easy to determine K from S. Speed The encryption algorithm is very compact, and can be coded efficiently in assembly language on most processors. The table S is accessed sequentially, minimizing issues of cache size. The RC5 encryption speeds obtainable are yet to be fully determined. For RC5-32/12/16 on a 90MHz Pentium, a preliminary C++ implementation compiled with the Borland C++ compiler (in 16-bit mode) performs a key-setup in 220 microseconds and performs an encryption in 22 microseconds (equivalent to 360,000 bytes/sec). These timings can presumably be improved by more than an order of magnitude using a 32-bit compiler and/or assembly language -- an assembly-language routine for the '486 can perform each round in eight instructions. Security A distinguishing feature of RC5 is its heavy use of data-dependent rotations -- the amount of rotation performed is dependent on the input data, and is not predetermined. The encryption/decryption routines are very simple. While other operations (such as substitution operations) could have been included in the basic round operations, our objective is to focus on the data-dependent rotations as a source of cryptographic strength. Some of the expanded key table S is initially added to the plaintext, and each round ends by adding expanded key from S to the intermediate values just computed. This assures that each round acts in a potentially different manner, in terms of the rotation amounts used. The xor operations back and forth between A and B provide some avalanche properties, causing a single-bit change in an input block to cause multiple-bit changes in following rounds. The use of variable rotations helps defeat differential cryptanalysis (Biham/Shamir [1]) and linear cryptanalysis (Matsui [3]), since bits are rotated to "random" positions in each round; Kaliski and Yin analyze the security of RC5 against both types of cryptanalysis [2]. For the standard word size w = 32, their differential attack can be applied to RC5 with less than 12 rounds and their linear attack can be applied to RC5 with less than six rounds. An assessment of the RC5 encryption algorithm will appear in the Summer issue of CryptoBytes; meanwhile, I invite the reader to help determine the strength of RC5. ------------------------------------------------------------- References [1] E. Biham and A. Shamir. Differential Cryptanalysis of the Data Encryption Standard. Springer-Verlag, New York, 1993. [2] B. S. Kaliski Jr. and Y. L. Yin. On differential and linear cryptanalysis of the RC5 encryption algorithm. Accepted to Crypto '95. [3] M. Matsui. The first experimental cryptanalysis of the Data Encryption Standard. In Y. G. Desmedt, editor, Advances in Cryptology -- Crypto'94, volume 839 of Lecture Notes in Computer Science, pages 1-11, Springer-Verlag, New York, 1994. ------------------------------------------------------------- Professor Ronald L. Rivest is associate director of MIT's Laboratory for Computer Science. He can be contacted at rivest@theory.lcs.mit.edu. A complete paper on RC5 was presented at the Leuven Algorithms Workshop in December 1994. An on-line version of the complete paper can be obtained by ftp or web. FTP: under pub/rivest/rc5 on theory.lcs.mit.edu; WEB: under http://theory.lcs.mit.edu/~rivest. Parts of this article originally appeared in Dr. Dobb's Journal, Copyright -- 1995 Miller Freeman Inc. ------------------------------------------------------------- Return to the contents page. Read about Message Authentication with MD5 Read the latest news and announcements ------------------------------------------------------------- In an ongoing effort, we will be making our information available through RSA's Web site. To provide feedback to our site, please use the following mail address:rsa-labs@rsa.com. We may not be able to respond to all messages, but we do appreciate any feedback that you may have on our information. Copyright (C) 1995 RSA Laboratories (a division of RSA Data Security, Inc.) -- All Rights Reserved. Terms used in this document are trademarks, copyrights, or registered to their respective owners. Last modified: Fri, 14 July 1995 17:00:00 PST