<<

. 17
( 19 .)



>>

any information revealed from the outer application
trinsic problem with this option, since MD5 is de-
of the hash function compromises security, but we
signed to resist collisions, at least to a certain level
know of no such attack on MD5.
of difficulty. Nevertheless, we have no objection if
the design of a message authentication code raises
Although the third approach has a shorter key size
than the first, the first could also be implemented that level even further.)
with a 12%bit key, without
any apparent loss in security.
For instance, the keys k,
Key
Key Key Padding Message
and k, could be derived
from a single 12%bit key I
k as kl = MD5 (k . a) and
k2 = MD5 (k . /$I, where a
and p are distinct constants.
MD5


The second approach (see
Figure 3) is somewhat like
triple encryption, where the
first and third keys are the
MAC
same (the second key is the
2
message). The padding on
.._...__.......,,,.....˜....˜.....,,._ . ____.. . ., , , , .˜˜˜.. ˜˜,. . . ˜. . . . . . ., ., , ., .˜˜˜˜.˜. - -_.. _._.” .,,_.. _ __.___.._ _ ..._....” _ . -. . . . . . . - -.-- _.. _. . . . . . . . . . --._- . _. . . . . . . . . . . . . - ..-....___-........
the key at the beginning en-
Yet another approach that we considered was
sures that overall, there are at least two iterations of
MD5( MD5 (k . ml), which again applies MD5 in a
the compression function. Message extension in the
familiar way. However, in terms of “provability”
prefer approach is solved by the key at the end, and
under certain assumptions it is less attractive than
the cryptanalysis of the suffx approach is solved by
the three we recommended. (This does not mean
the key at the beginning. (Without the padding, very
short messages might be vulnerable.) that the approach is insecure, simply that the
assumptions required for it to be secure are more
complicated.)
It remains to be seen which, if any, of these three
approaches is adopted.
As the IBM team has pointed out to us, all of the
Interestingly, one of the approaches we had been pre- approaches are vulnerable to a chosen message at-
tack involving about 2@ chosen messages. This gen-
viously promoting is not among the three we recom-
eral attack exploits the iterative structure of the mes-
mended to the IPSEC working group, based on our
concerns about key exposure. That approach, MD5 sage authentication code and applies to MACs based
on encryption functions as well. The basic idea is
(k . MDS(m)), had the advantages that the inner
that if two messages ˜1, . b and uj . b have the same
MD5 is applied to the message in the familiar way -
MAC, then it is possible that the “collision” occured
as a hash function - and the outer MD5 is applied
before b was processed, so that for any c, a, . c and
to a fixed-length value, thereby avoiding message
uj . c have the same MAC. Having found two mes-
extension. However, since MD5 (ml is known, the
sages ai . b and aj . b with the same MAC, the oppo
door is open for possible cryptanalysis of the outer
nent asks for the MAC of ai . c for some c, thereby
MD5 to recover the key k. While we once again do
obtaining (fraudulently) the MAC of aj - c.
not have an attack that recovers the key, we felt as a
general design principle that the key should be bet-
As chosen message attacks go, 264 is quite a large
ter concealed.
number, and we know of no general way to extend
the attack to known messages, except when the
(Another concern with this approach, observed by
known messages are all the same length and end with
some, is that collisions in MD5 -two messages with
the same suffix. Full details are given intlj.
the same hash -result in collisions in the message

1995
SPRING CRYPTOBYTES
THE TECHNICAL NEWSLETTER OF RSA LABORATORIES -
Page 65
Previous Page Home Next Page




are a consequence of the fact that the key is pro-
Starting over
cessed only once, or maybe twice. As a result, the
So far, our research has focused on adapting an exist-
key is isolated, and information about it can be
ing hash function to message authentication, which
is a practical solution, since MD5 is already trusted, obtained, or other parts of the message can be ma-
and software for MD5 is widely available. For the nipulated independent of the key. By contrast, in
message authentication codes based on encryption
long term, designing a message authentication code
from scratch is perhaps a better solution. functions, such as DES-MAC, the key is processed
at every step. In Bellare et al™s techniques, the key is
Mihir Bellare, Roth Guerin and Phillip Rogaway [*I processed at every step.
describe techniques for such message authentication
that are “provably secure,” under certain assumptions We expect that MD5™s compression function or a
about the underlying functions. Their techniques are variant of it may be a suitable pseudorandom func-
tion for Bellare et al™s techniques, something which
also highly parallelizable, a feature that the iterative
approach lacks by definition. further research will determine.

References
Bellare et al™s techniques assume the existence of a
pseudorandom function, which takes two inputs, a [l] M. Bellare, R. Canetti and H. Krawctyk. KeyingMD5-
key and a message block, and produces one output. Message authentication via iteratedpseudorandomness.
By assumption, if the key input is fixed and un- In preparation.
known, it is difficult to distinguish the pseudoran- [2] Mihir Bellare, Roth GuCrin and Phillip Rogaway. XOR
dom function on the message block from a truly M4C.k New methodsfor message authentication using bhzk
random one in any reasonable amount of time. ciphers. Accepted to Crypto ˜95.
(This is similar to the idea that it is difficult to find [3] Mihir Bellare, Joe Kilian and Phillip Rogaway. The
collisions for a hash function -although it is pos- security of cipher block chaining. In Yvo G. Desmedt,
sible because they exist, the amount of time required editor, Advances in Cryptology- Crypto ˜%, volume 839
is large.) of Lecture Notes tn Computer Science, pages 341-358.
Springer-Verlag, New York, 1994.
The message authentication code is computed by [4] LB. Damgard. A design principle for hash functions. In
combining, perhaps by bit-wise exclusive-or, the out- G. Brassard, editor, Advances In 0yptology: Proceedings
puts of the pseudorandom function applied to the of Cypto ˜89, volume 435 of Lecture Notes in Computer
blocks of the message. To maintain the ordering of Science, pages 416427. Springer-Verlag, New York, 1990.
the different blocks, each block is tagged with its [5] J. Galvin and K. McCloghrie. RFC 1446 Secun™ty
Prvtocohfor wrsion 2 of the Simple Netuxxk Management
position in the message. A random block is also
included for technical reasons. Protocol (SNMPv2.I. Trusted Information Systems and
Hughes IAN Systems, April 1993.
Bellare et al show that if an opponent can forge mes- [6] R. Me&e. One way hash functions and DES. In G. Bras-
sage authentication codes, even with the opportu- sard, editor, Advances in Cryptology: Proceedings of Ctypto
nity to request message authentication codes on ˜89, volume 435 of Lecture Notes in ComputerScience,
many different messages, then the opponent can also pages 428446. Springer-Verlag, New York, 1990.
distinguish the pseudorandom function from a truly [7] National Institute of Standards and Technology (formerly
random one. Thus, under the assumption that it is National Bureau of Standards). FZPS PLIB 113: Computer
difficult to distinguish the pseudorandom function Dara Authentication. May 30,1985.
from a truly random one, the message authentication [S] National Institute of Standards and Technology. FZPS
code is secure. PUB 180: Secure Hash Standard (SHS). May 11,1993.
[9] R. Rivest. RFC1321: 7%eMDSMessage-LIigtxtAJqorttbm.
The independent processing of the message blocks RSA Data Security, Inc., April 1992.
leads to the parallelizability of this approach. [lo] Gene Tsudik. Message authentication with one-way hash
functions. ACM Computer Communications Review,
It seems that many of the concerns about designing 22(5):29-38, 1992.
m
a message authentication code from a hash function

CRYPiOBYTES IP?S -
SPRih!G THE TECHNICAL NEWSLETTER OF RSA LABORATORIES
Page 66
Previous Page Home Next Page
The RC5 Encryption Algorithm*

DES. Unlike unparameterized DES, however, an RC5
Ronald L Rivest ˜RCSand
RSA-RC5 are
user can easily upgrade the above choice to an go-bit
MIT laboratory for Computer Science
w-
key by moving to RC5-32/16/10.
545 Technology Square
t?lYdma˜of
Cambridge, MA 02139 USA RSA Data
As technology improves, and as the true strength of Security, Inc.
Introduction Patentpznding
RC5 algorithms becomes better understood through
RC5 is a fast symmetric block cipher suitable for hard- analysis, the most appropriate parameters can be cho
ware or software implementations. A novel feature sen. We propose RC5-32/12/16 as providing a “nomi-
of RC5 is the heavy use of data-dependent rotations. nal” choice of parameters. Further analysis is needed
RC5 has a variable-length secret key, providing flex- to analyze the security of this choice.
ibility in its security level.
Overview of the Algorithm
RC5 is a parameterized algorithm, and a particular RC5 consists of three components: a key eqansion
RC5 algorithm is designated as RC5-w/r/b. We algorithm, an encryptionalgorithm, and a decryption
summarize these parameters below: algorithm. These algorithms use the following three
primitive operations (and their inverses).
w The word size, in bits. The standard value is 32
bits; allowable values are 16, 32, and 64. RC5 1. Two™s complement addition of words, denoted by
encrypts two-word blocks: plaintext and “+“. This is modulo-2w addition.
ciphertext blocks are each 2w bits long. 2. Bit-wise exclusive-OR of words, denoted by 2.
r The number of rounds. Allowable values are 3. A left-rotation (or “left-spin”) of words: the
0, 1, . . . . 255. rotation of word x left by y bits is denoted x <<< JI.
b The number of bytes in the secret key K. Allow- Only the lg(w) low-order bits ofy are used to
able values of b are 0, 1, . . . . 255. determine the rotation amount, so that y is
interpreted modulo w.
RC5 uses an “expanded key table”S, derived from the
user™s supplied secret keyK. The sizet of tablesdepends Encryption and Decryption
on the number rof rounds: S has t = 2(til) words. We assume that the input block is given in two whit
registersA andB. We also assume that key-expan-
It is not intended that RC5 be secure for all possible sion has already been performed, so that the array
parameter values. On the other hand, choosing the 30. . . t-l] has been computed. Below is the encryp-
maximum parameter values would be overkill for most tion algorithm in pseudo-code. The output is also
applications. placed in registers A and B.

We provide a variety of parameter settings so that A = A + S[O]; As technology
users may select an encryption algorithm whose B=B+xl]; improves, and
security and speed are optimized for their application, FOR˜=˜TO?-DO as the true
while providing an evolutionary path for adjusting A = ((A 2 B) <SK B) + s[2*i]; strength of
their parameters as necessary in the future. As an B = ((B 2 A) <SK A) + s[2*i+l]; RC5 algorithms
example, RC5-32/16/7 is an RC5 algorithm with the becomes better
number of rounds and the length of key equivalent to We note the exceptional simplicity of this five-line understood
algorithm. We also note that each RC5 round up- through analysis,
dates both registers A and B, whereas a “round” in the most
Professor Ronald L. Rivest is associate director of MIT™s
DES updates only half of its registers. An RC5 “half- appropriate
Laboratoy for Computer Science. He can be contacted at
round” (one of the assignment statements updating parameters
riwst@tbeoy.lcs.mit.edu.
A or B in the body of the loop above) is thus perhaps
A c˜˜˜˜onRC5uxrspvesenredattheLeu˜nAlgorith˜ can be chosen.
Workshop in Decemtxr 1994. An on-line thzsion of the co?n@ete more analogous to a DES round.
papercan beobtained@&oruxb. FE underpuWtimtit/5on
theoy.h.mit.edu; WEB: underh˜://t/theoy.Ics.mit.ed˜-˜˜˜t.
The decryption algorithm can be easily derived from
Parts of this article originullyappeared in Dr. Dobb™s Journal,
the encryption algorithm.
Copynbt 0 1995MiNwFmemun Inc.


THE TECHNICAL NEWSLETTER OF RSA SPRIIIG
LABORATORIES - CRYPTOBYTES
Page 67
Previous Page Home Next Page




Key Expansion Do 3max(t,c) TIMES:
The encryption
The key-expansion routine expands the users secret A = s[i] = (s[i] + A + B) G=X 3;
algorithm is
key K to fill the expanded key array S, so that S re- B = Lfjj = (Lfj] + A + B) = (A+B);
very compact,
sembles an array oft = 2(rt 1) random binary words i = (i + 1) mod(t);
and can be
determined by K. The key expansion algorithm uses j = cj + 1) mod(c);
coded efficiently
two “magic constants” and consists of three simple
in assembly
algorithmic parts. The key-expansion function has a certain amount of
language
“one-wayness”: it is not so easy to determine K from S.
on most
The key-expansion algorithm uses two word-size
processors.
binary constants P, and QU. They are defined for Speed
arbitrary was follows: The encryption algorithm is very compact, and can
be coded efficiently in assembly language on most
P, = Odd((e-2)2w) processors. The table S is accessed sequentially, mini-
Qw = Odd((q&1)2w) mizing issues of cache size. The RC5 encryption
speeds obtainable are yet to be fully determined. For
where RC5-32/12/16 on a 90MHz Pentium, a preliminary
e = 2.718281828459... (base of natural logarithms) C++ implementation compiled with the Borland
4 = 1.618033988749... (golden ratio), C++ compiler (in 16bit mode) performs a key-setup
in 220 microseconds and performs an encryption in
and where Odd(x) is the odd integer nearest to x 22 microseconds (equivalent to 360,000 bytes/set).
(rounded up ifx is an even integer, although this won™t These timings can presumably be improved by more
happen here). than an order of magnitude using a 32-bit compiler
and/or assembly language-an assembly-language
The first algorithmic step of key expansion is to copy routine for the ˜486 can perform each round in eight
the secret key K[O...b-1] into an array L[O...c-1] of instructions.
c = cz b/u+ words, whereu=w/8 is the number of bytes/
word. This operation is done in a natural manner, Security
using u consecutive key bytes ofK to ffi up each suc- A distinguishing feature of RC5 is its heavy use of&ta-
cessive word it-r& low-order byte to high-order byte. dependwlt rotations--the amount of rotation performed
Any unfilled byte positions ofL are zeroed. is dependent on the input data, and is not predeter-
mined.
The second algorithmic step of key expansion is to

<<

. 17
( 19 .)



>>