<<

. 14
( 19 .)



>>

lOi MY on general purpose computers to implement computing power on the Internet that seems most
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.

<<

. 14
( 19 .)



>>