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