either the Shanks or the Pollard algorithm. Hence serious. Special designs for sieve processors for

we can conclude that 160 bits for q is likely to be safe factoring have been proposed (see 1131), but the

for at least 20 years, and 200 bits (which would re- economics of the electronics industry favors general

quire at least 106 as much computing power to break) purpose computers. (Fast parallel modular multi-

for much longer. (As with all the other projections plication units could be of use in the implementa-

about algorithms, this one could turn out to be faulty tion of the Pollard and Shanks exponential-time

if a breakthrough occurs.) algorithms, though, or of the subexponential-time

elliptic curve method.) b

As another example where only exponential attacks

To find a single

are known, we can cite elliptic curve cryptosystems

DES key will

[9], proposed initially by Neal Koblitz and Victor

on average

Miller. If the elliptic curve is chosen carefully, only

take about

RSA Laboratories Minimum Key

300 times as the Shanks and Pollard methods are known for com-

puting the analog of discrete logs on these curves. Size Recommendations

much as the

There is still some reluctance to use elliptic curve

factorization

cryptosystems, though, since they have not been scru- It is clear from articles like Andrew Odlyzko™s

of RSA 129

tinized as carefully as integer factorization and ordi- in this issue ofCryptoBytes, that considerable

required.

nary discrete logs. thought is required in choosing the size of a

modulus used in an implementation of RSA.

Balancing the issues of security against per-

AppedixJ:AttacksonDES

formance is difficult with any cryptosystem,

For comparison, we present some estimates of the but it is particularly difficult when one wants

computing power needed to break DES. We consider to make allowances for potential cryptana-

known plaintext attacks on cipher codebook mode. lytic developments.

We assume that only exhaustive key search will be

tried, so that on average 255 keys will have to be tested Currently, RSA Laboratories make the fol-

to find the right one. The best software implementa- lowing recommendations for the size of

tions (written in C) appear to achieve rates of up to RSA moduli:

about 200 KB/sec on 25 mips machines (such as 50

MHz 80486 PCs), which (since each iteration of DES User keys,

involves encrypting 8 bytes) corresponds to 25,000 short-term security 768 bits

encryptions per second, or about 1,000 encryptions

per second on a 1 mips computer. Hence 1 MY al- Organizational keys,

lows us to test about 3 * lOi encryptions. Therefore medium-term security 1024 bits

-˜_---,“.-.“..- ...” , , ,.,. . - .__.._. ._. ._. -- .._,-...

to find a single DES key will on average take 1.2 * 106

MY, or about 300 times as much as the factorization Root keys,

of RSA129 required. long-term security 2048 bits

DES was made to run fast in hardware, and special Since developments in factoring can be very

purpose machines can provide substantial assistanoz unpredictable, implementations of RSA

in breaking it. Michael Wiener 1151 has proposed a should ideally allow for variable keysizes

pipelined parallel computer that could be built for where at all possible.

about $1.5M (both development and construction

SUMMEi?

CRYPTOBYTES 1 9 9 5 -THE TECHNICAL NEWSLETTER OF RSA LABORATORIES

la

Page 54

Previous Page Home Next Page

On the Security of the RC5 Encryption Algorithm

We have developed differential and linear attacks 121

Burt KdiSki and Yicpl.tl L&l yin

on RC5 that are quite effective when the number of

RSA Laboratories

rounds is very small. Both attacks recover every bit of

100 Marine Parkway, Suite 500

the expanded key table. However, the plaintext re-

Redwood City, CA 94065 USA

quirement is strongly dependent on the number of

In this article, we give a brief report on the security rounds, and the requirement for RC5 with 64-bit

of the RC5 encryption algorithm 151 against three block size is summarized in the following table.

different types of attack including exhaustive search,

Table 1

differential cryptanalysis 111, and linear cryptanalysis

131. RC5 is a new block cipher recently designed by

Ron Rivest. It has a variable block size, a variable

number of rounds, and a variable-length secret key.

The secret key is used to fill an expanded key table

which is then used in encryption. A detailed descrip

tion of the RC5 encryption algorithm was provided

in the Spring issue of CryptoBytes 161.

The chosenpkxintex requirementsfor di&zntil cmmnalysis of

64-bitRCSwi˜b theindicatednumberof lounu?auesbown in the

To attack RC5, we can try to find either the original

f?tstnnuoftbetable. 7beknownp&zintextnx+zmentsforlinear

secret key or the expanded key table. Clearly, if the lat- crypranalysisawshown in thesewndnnv.

ter approach is used, the attack is independent of the

length of the secret key. One can see that for the 64-bit block size, our differ-

ential attack on nine-round RC5 uses 246 chosen

The secret key used in RC5 has a variable length plaintexts (about the same as DES 141); the plaintext

with allowed values from 0 to 2,040 bits and the requirement becomes increasingly impractical for

expanded key table for RC5 with rrounds has 2X2r+2) more rounds. Similarly, our linear attack on five-

bits (for the 64-bit block size). Hence, if both the round RC5 uses 24™ known plaintexts (about the same

length of the secret key and the number of rounds as DES) and the plaintext requirement increases rap

are sufficiently large, RC5 is secure against exhaus- idly with additional rounds.

tive search.

We now briefly describe the idea used in the two at-

Differential and linear cryptanalysis are two powerful tacks on RC5. Since RC5 is iterative, if we can derive

techniques developed in recent years for analyzing the subkey in the last round, we can derive all the

subkeys in the expanded key table. In our differential

the security of block ciphers. For differential crypt-

attack, the characteristics for each round have the

analysis, the basic idea is that two chosen plaintexts

property that the differences in the pair of inputs do

P and P with a certain difference P™= P 2 P™ provide Rivest™s

not affect the rotation amounts and they can easily

two ciphertexts C and C such that C™= C 2 C has suggested use

be joined together. Moreover, the characteristics for

a specific value with non-negligible probability; of 12 rounds

the last round have a special form, allowing us to

such a “characteristic” (P™,C> is useful in deriving for RC5 with

recover the subkey in the last round. In our linear at-

certain bits of the key. For linear cryptanalysis, the a 64-bit block

tack, the linear approximations relate the least sig-

basic idea is to find linear approximations (parity size is sufficient

nificant bits of the input, the output, and the subkey

relations among certain bits of plaintext, ciphertext, to make

in each round. When enough plaintexticiphertext

and key) which hold with probabilityp j l/2 (i.e., differential

pairs are obtained, the experimental biases of the ap

bias = # p - 1/2# j 0); such approximations can be and linear

proximations reveal the subkey in the last round. cryptanalysis

used to obtain information about the key.

There is strong evidence that the characteristics and impractical.

the linear approximations used in our attacks are close

to optimal. Thus, Rivest™s suggested use of 12 rounds

ButthZll˜˜ischiefscientistandY˜nLisa IFnisareseanAxYen-

for RC5 with a 64-bit block size is sufficient to make

titatRSALuboraton& 7beycan becontactedatburt@sa.wm

differential and linear cryptanalysis impractical.

and*n@rsa.wm.

q

THE TECHNICAL NEWSLETTER OF RSA LABORATORIES - SLIMMER 1995 CRYPTOBYTES

Page 55

Previous Page Home Next Page

References

In sum, we can conclude that RC5 provides good se-

Our analysis

curity against all three types of attacks when both Ill E. Biham and A. Shamir. Differential Cryptanalysis of the

shows that

the length of the secret key and the number of rounds Data Encqm™on Standard. Springer-VerIag, 1993.

data-dependent

are sufficiently large. Unlike DES, RC5 is a param- f21 B.S. Kaliski and Y.L. Yin. On differential and linear crypt-

rotations are

eterized algorithm, giving flexibility in the level of analysis of the RC5 encryption algorithm. To appear at

very helpful for

security. As a next step, we will consider other pos- Crypto ˜95.

preventing

sible forms of analysis and study the key expansion [31 M. Matsui. The first experimental cryptanalysis of the

differential and

algorithm of RC5. Data Encryption Standard. In Y.G. Desmedt, editor, Ad-

l i n e a r aftacks.

vances in Ckyptology- Crypto ˜94, pages l-l 1, Springer-

Finally, we want to point out two distinguishing Verlag, 1994.

features of RC5. The first feature is the heavy use of I41 National Institute of Standards and Technology (NISI™).

data-dependent rotations. Our analysis shows that FlPSPublication 46-2: Data Encryption Standard. Decem-

data-dependent rotations are very helpful for prevent- ber 30,1993.

ing differential and linear attacks. The second fea- I51 R.L. Rivest. The RC5 encryption algorithm. In Proceed-

ture is the exceptional simplicity of the encryption ings of the Wor&op on Cryptographic Algorithms, K.U.

algorithm. Such a simple design makes the analysis Leuven, December 1994. To appear.

easier and will help fully determine the security of 161 R.L. Rivest. The RC5 encryption algorithm. CryptoBytes,

RC5 in a rather rapid way. b l(l), 9-11, Spring 1995.

A L G 0 R I T H M S U P D A T E

MD5 Performance for IP Security message blocks are processed one after another, each

Questioned one being combined with the result of previous

computation through a compression function. Thus

A paper to be presented at ACM SigComm ˜95 ques- the only hardware optimization possible is within

tions whether the MD5 message-digest algorithm is the compression function; it is not possible to

fast enough to handle packets on high-speed Inter- process multiple blocks at the same time with addi-

net links. tional hardware. Moreover, the compression func-

tion itself is complex and somewhat hard to

The paper, “Performance Analysis of MD5” by Joe parallelize. Many other hash algorithms including

Touch of ISI, argues that with today™s hardware NIST™s Secure Hash Algorithm (SHA) are subject

MD5 can achieve at best a speed of 256 million bits/ to the same limitations.

second (Mbps), not enough to keep up with Asyn-

chronous Transfer Mode (ATM) data rates of up to Alternatives recommended by Touch include tree-

622 Mbps. Though hardware performance will likely based hashing; and internal modifications to the

improve over time, so will network requirements, algorithm.

keeping MD5 behind.

MD5 remains sufficient for many applications, such

MD5 has been proposed as a basis for authenticating as hashing as part of a digital signature algorithm. In-

messages in version 6 of the Internet Protocol (IPv6), deed, Touch reports software performance for MD5

where a message and a secret key are hashed together ranging from 31 Mbps on a 66MHz Intel ˜486 to 87

to form an authentication code that prevents intrud- Mbps on a 190 MHz DEC Alpha. On such proces-

ers from modifying messages. As such, it could be re- sors, files even as large as 10 Mbytes can be hashed

quired to handle packets at network speeds. with MD5 in only a few seconds.

A significant reason for the limitation in perfor- A report by Touch summarizing these results is avail-

mance is that MD5 has an iterative design where able as Internet RFC 1810. m

CRYPTOBYTES SUMMER 1 9 9 5 -THE TECHNICAL NEWSLETTER OF RSA LABORATORIES

Page 56

Previous Page Home Next Page

---_ -..-..

--.-.˜

E D I T 0 R

T H E

T 0

and H. Dobbertin (Rump Session, Eurocrypt%),

Further Comments on Keyed MD5

suggest these functions are susceptible to manipula-

This note follows on the excellent overview by Burt tions of their internal structures. This raises concerns

Kaliski and Matt Robshaw (“Message authentication about hash-based MACs being susceptible to attacks

with MD5,” CryptoBytesvol. 1 no.1) in which three exploiting properties of the underlying hash. We

schemes are recommended to the IPSEC working therefore advise caution in constructing such MACs,

group. Citing forthcoming work, it was suggested the and recommend a design more conservative than the

best attack (forgery) on these schemes required 264 envelope method. We agree customized MACs may

chosen message texts (,, . . . except when the known be preferable, but are reluctant to discard the experi-

messages are all the same length and end with the ence gained over time with MD4 and MD5.

same suffer”).

With exquisite timing, our paper already (as submit-

We have improved this attack in our recent paper”) ted Feb.˜95) makes a proposal in line with most of

“MDx-MAC and building fast MACs from hash the suggestions of Kaliski and Robshaw: MDS-MAC,

functions,” Pm. Crypto™95. A generic attack is given a customized MAC involving key processing at every

requiring 264 known text-MAC pairs and a single compression function step, and built with only mi-

chosen text, independent of message lengths or suf- nor modifications from MD5 (to minimize the likeli-

fixes - only for the second recommended scheme hood of introducing new flaws). The same construc-

we need the messages to be of the same length. (Per- tion yields MACs based on any of MD5, SHA, or

haps more significantly, the attack applied to CBC- RIPEMD.

MAC requires only 2s2 known text-MAC pairs for

MAC forgery.) The attack requires an additional 2” In addition to being more conservative than the en-

chosen text-MAC pairs if only 64 bits of the hash re- velope method, only slightly slower (5-20%, depend-

sult are retained; this suggests modifying the method ing on processor and implementation), and easily

to retain only 64 bits, which also saves bandwidth. implemented from MD5, the theoretical underpin-

The number of text-MAC pairs required can be fur- nings supporting the security of the envelope method,

ther reduced if the known messages contain a com- which assume the compression function of MD5 is

mon (not necessarily chosen) sequence of trailing pseudorandom, appear to similarly apply to MD5-

blocks. The attack also applies if messages are fured- MAC. w caution, however, that we are aware of no We therefore

length or prepended by length fields. results regarding the pseudomndomness of MD5, and advise caution

note this property may be independent of collision- [.,,I, and

Adapting the same attack strategy allows a divide- resistance, the primary property studied to date. recommend

and-conquer attack if the envelope method is used a design more

with distinct front and tail keys, effectively reducing - BartPreneel, Katholkk? UnimiieitLeuuen conservative

security to the larger of the two. We also provide ba?t.˜l˜t.khm,˜.be than the

analysis of the secret prefix and secret suffix meth- Paul C. van Oombot, Bell-Northern Research envelope

ods, and add here that the secret suffer method is sub- pd˜bn˜ca method.

ject to an off-line, memoryless, parallelizable attack

requiring 2” operations and a single chosen text (˜1 the paper is available by FTP at ftp.esat.kuleuven.ac.be,

(P. van Oorschot and M. Wiener, ACM-CCS™94, inthedirectorypub/COSIC/preneel.

Fairfax).

Wevxkomewtnmen˜˜ourreadersaranytime. Inpficuhr

Recent partial attacks on MD4, MD5, and the re-

˜are˜to˜ndand˜˜˜reisnrestbathaue˜™-

lated RIPEMD, including in particular those of S. ou@appearedinCtyptBBytes. CommentscunbesentviuE-mail

Vaudenay (Leuven Algorithms Workshop Dec.˜94) to bytes+d@w.com.