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