20 June 1998: Text revised by Vin McLellan
18 June 1998
Date: Thu, 18 Jun 1998 20:09:07 -0400 From: Vin McLellan <vin@shore.net> Subject: Rivest posts RC6 paper - New Block Cipher Ron Rivest has just posted a technical paper describing RC6, his new block-cipher. See: http://theory.lcs.mit.edu/~rivest/rc6.ps or http://theory.lcs.mit.edu/~rivest/rc6.pdf RC6 seems to be a speedy, versatile, and unusally compact algorithm which -- in Rivest's trademark style -- argues for both the power and the elegance of simplicity. The standard mode RC6 operates on 128-bit input/output blocks (32-bit words) with variable-length keys -- but the RC6 design offers great inherent flexibility in the word-size of the basic computational unit, and the number of rounds to be specified, as well as in the length of the encryption key. Rivest has submitted RC6 to the American National Institute of Standards and Technology (NIST) as a candidate to become the US Advanced Encryption Algorithm (AES). Rivest, Webster Professor of Electrical Engineering and Computer Science at MIT in Cambridge, Ma., credits Matt Robshaw, Ray Sidney, and Yiqun Lisa Yin -- all on the research staff at RSA Laboratories, San Mateo, Calif. -- as co-developers of RC6. Rivest is best known as one of the three inventors of the RSA public key cryptosystem; the "R" of RSA; and a founder of RSADSI (now part of Security Dynamics Technologies, Inc.) Among his other cryptographic inventions of note are the widely-used (and widely-copied) RC2 and RC4 algorithms, and the recently-patented RC5 cipher (all commercial products from SDTI's RSA subsidiary) -- as well as the MD2, MD4, and MD5 hash functions. RC6 may, at first glance, appear to be a straight-forward evolutionary development from RC5, but Rivest noted in his paper that he and his team had explored dozens of alternatives in great depth before he finally decided upon this design as providing what he felt was an optimal mix of security, simplicity, and performance. From his comments, it is also apparent that RC6 has benefited considerably from the cryptanalytic insights that have been generated in the public review of RC5. For those without web access, I append the abstract and the introduction from the RC6 paper below. Suerte, _Vin <Rivest text follows> The RC6 Block Cipher by Ronald L. Rivest, M.J.B. Robshaw, R. Sidney, and Y.L. Yin Abstract: We introduce the RC6 block Cipher. RC6 is an evolutionary improvement of RC5, designed to meet the requirements of the Advanced Encryption Standard (AES). Like RC5, RC6 makes essential use of data-dependent rotations. New features of RC6 included the use of four working registers instead of two, and the inclusion of interger multiplication as an additional primitive operation. The use of multiplication greatly increases the diffusion achieved per round, allowing for greater security, fewer rounds, and increased throughput. 1. Introduction RC6 is a new block cipher submitted to NIST for consideration as the new Advanced Encryption Standard (AES). The design of RC6 began with a consideration of RC5 as a potential candidate for an AES submission. Modifications were then made to meet the AES requirements, to increase security, and to improve performance. The inner loop, however, is based on the same "half-round" found in RC5. RC5 was intentionally designed to be extremely simple, to invite analysis shedding light on the security provided by extensive use of data-dependent rotations. Since RC5 was proposed in 1995, various studies have provided a greater understanding of how RC5's structure and operations contribute to its security. While no practical attack on RC5 has been found, the studies provide some interesting theoretical attacks, generally based on the fact that the "rotation amounts" in RC5 do not depend on all the bits in the register. RC6 was designed to thwart such attacks, and indeed to thwart all known attacks, providing a cipher that can offer the security required for the lifespan of the AES. To meet the requirements of the AES, a block cipher must handle 128-bit input/output blocks. Which RC5 is an exceptionally fast cipher, extending it to act on 128-bit blocks in the most natural manner would result in using two 64-bit reisters. The specified target architecture and languages for AES do not yet support 64-bit operations in an efficient and clean manner. Thus, we have modified the design to use four 32-bit registers rather than two 64-bit registers. This has the advantage that we are doing two rotations per round, rather than the one found in a half-round of RC5, and we are using more bits of data to determine rotation amounts in each round. The philosophy of RC5 is to exploit operations (such as rotation) that are efficiently implemented on a modern processor. RC6 continues this trend, and takes advantage of the fact that 32-bit integer multiplication is now efficiently implemented on most processors. Integer multiplication is a very effective "diffusion" primitive, and is used in RC6 to compute rotation amounts so that the rotation amounts are dependent on _all_ of the bits of another register, rather than just the low-order bit (as in RC5). As a result the new RC6 has much faster diffusion than RC5. This also allows RC6 to run with fewer rounds at increased security and with increased throughput. <snip> 2. Details of RC6 Like RC5, RC6 is a fully parameterized family of encryption algorithms. A version of RC6 is more accurately specified as RC6-w/r/b where the word size is "w" bits, encryption consists of a nonnegative number of rounds "r," and "b" denotes the length of the encryption key in bytes. Since the AES submission is targetted at w=32, and r=20, we shall use RC6 as shorthand to refers to such versions. When any other value of "w" or "r" is intended in the text, the parameter values will be specified as RC6-w/r. Of particular relevance to the AES effort will be the versions of RC6 with 16-, 21-, and 32-byte keys. For all variants, RC6-w/r/b operates on units of four w-bit words using the following six basic operations. The base-two logarithm of "w" will be denoted by "lg w." a + b integer addition modulo 2 *w a - b integer subtraction modulo 2 *w a <EOR> b bitwise exclusive-or of w-bit words a x b integer multiplication modulo 2 *w a <<< b rotate the w-bit word a to the left by the amount given by the least significant lg w bits of b a >>> b rotate the w-bit word a to the right by the amount given by the least significant lg w bit of b Note that in the descriptions of RC6 the term "round" is somewhat analogous to the usual DES-like idea of a round: half of the data is updated by the other half; and the two are then swapped. In RC5, the term "half-round" was used to describe this style of action, and an RC5 round was deemed to consist of two half-rounds. This seems to have become a potential cause of confusion, and so RC6 reverts to using the term "round" in a more established way. <end Rivest excerpt> ----- "Cryptography is like literacy in the Dark Ages. Infinitely potent, for good and ill... yet basically an intellectual construct, an idea, which by its nature will resist efforts to restrict it to bureaucrats and others who deem only themselves worthy of such Privilege." _ A thinking man's Creed for Crypto/ vbm. * Vin McLellan + The Privacy Guild + <vin@shore.net> * 53 Nichols St., Chelsea, MA 02150 USA <617> 884-5548