<<

. 2
( 19 .)



>>



,
rather too close for
comfort and caution re-
quires that MD2 be no
longer recommended
for new applications
where collision-resis-
tance is required. Ques-
tions about the con-
Initial Value
tinuing suitability of
MD2 for existing appli-
cations remain open.
Certainly MD2 has not
been broken and exist-
4. The Status of MD2 ing signatures are not at risk since it is still difficult
When hashing a message with MD2 there are three to find preimages (input messages which yield a given
different phases. The first is a padding phase whereby target value with MD2). In addition, future signing
the message is padded to form a string that has a will only become vulnerable if full collisions for MD2
length in bytes which is divisible by 16. The second can be found. Despite this, while MD2 might still be
phase is the computation of a 16-byte checksum C used in the short term, our recommendation would
which is appended to the end of the message; the be to upgrade applications away from MD2 when-
ever it is practical.
checksum is a function of the message and it is com-
puted under the action of a non-linear substitution
5. The Status of MD4
table based on the digits of K. The resultant string is
then divided into 16-byte blocks. The final block, MD4 was an early design for a particularly fast hash
therefore, is the 16-byte checksum. The third phase function. Successful cryptanalysis of reduced-round
consists of repeated application of the compression versions of MD4 [15, 51 soon demonstrated, how-
ever, that the design of MD4 represented an uncom-
function to compute new values for the chaining
variable as a function of both the current value and fortable compromise between security and speed. As
each message block in turn. The initial value of the a consequence, the more conservatively designed
chaining variable is fixed as part of the algorithm MD5 has always been recommended for use instead
of MD4.
specifications and the last value for the chaining
variable becomes the 16-byte (128-bit) MD2 hash
Work by Dobbertin [7, 81 has vindicated this early
value.
concern about MD4 and it has been shown that col-
Considerable progress has been made in the crypt- lisions for MD4 can be found in about a minute on a
analysis of MD2 [23] and it has been shown that it is typical PC. In addition, a variant of MD4 called ex-
possible to find collisions for the compression f&c- tended-MD4 (201, which offers a 256-bit hash value
tion of MD2. More precisely, it is possible to find instead of the usual 128-bit MD4 output, has also
two 16-byte strings such that compression, when been seriously undermined by the work of Dobbertin.
starting with particular values of the chaining vari-
able (including the correct initial value), will yield While much of this cryptanalytic work is concerned
exclusively with finding collisions, considerable in-
the same output from the compression function.
sight into the behavior of MD4 has also been gained,
Such work would lead directly to collisions in MD2
particularly when combined with other independent
were it not for the fact that the final computation of
the MD2 hash value depends on the value of the cryptanalytic work. Both MD4 and extended-MD4
checksum C and this is likely to be different for the should not be used.
two messages.
6. The Status of MD5
Currently, it appears to be difficult to make allow- Attacking MD5 is a much more involved proposi-
tion than attacking MD4 since it is a far more com-
ances for the existence of the checksum during crypt-
analysis. Without the checksum MD2 would be bro- plicated algorithm to analyze. The first important
ken but with it, this attempt at cryptanalysis has been advance in the cryptanalysis of MD5 was the dis-
covery of what are termed pseudo-collisions for the
thwarted at the very last hurdle. This is perhaps
Page 4
Previous Page Home Next Page
RSA LABORATORIES B U L L E T I N #4 - N O V E M B E R 12, 1996




compression function of MD5 [6]. A pseudo-colli- Given the surprising speed with which techniques
on MD4 were extended to MD5 we feel that it is
sion for the compression function is exemplified by
only prudent to draw a cautious conclusion and to
fixing the value of some message block and finding
two distinct values for the chaining variable that expect that collisions for the entire hash function
provide the same output. While the existence of might soon be found.
pseudo-collisions is significant on an analytical level,
it is of less practical importance. Recall that only a Recalling our comments in Section 2, however, we
single chaining variable is used during hashing and note that there may well be situations where this
so the behavior of two related chaining variables is cryptanalytic work on MD5 has little impact. Note
not directly relevant. Instead, it would be more sig that existing signatures that were generated using
nificant if we could identify the value of a single MD5 are likely to remain safe from compromise since
chaining variable for which two different message it seems that current techniques used to cryptana-
blocks produce the same output from the compres- lyze MD5 do not offer any advantage in finding a
sion function. Such an occurrence would have ob- second preimage. Existing signatures should not be
vious implications for the collision-resistant prop- considered as being at risk of compromise at this
erty we often desire of a hash function. If the value point. Likewise the random-looking appearance of
of the chaining variable involved were not the same the output from MD5 and the property of being one-
as the initial value (as provided in the algorithm way are not considered to be seriously in question.
specifications) then such an occurrence would be Finally, one major recent proposal for the use of MD5
termed a collision for the compression function. If, how- has been in what is sometimes referred to as the
ever, we could identify two message blocks which keyed-MD5 approach to message authentication. In
provide a collision when the pre-specified initial particular, one proposal termed HMAC [l, 21 pro-
value is used, then we would have full collisions for duces a message authentication code for some mes-
the hash function. sage with the help of a hash function, and for imple-
mentation efficiency, the use of MD5 in particular
At Eurocrypt ˜96 it was announced that collisions has been proposed. The design and properties of
for the compression function of MD5 had been found HMAC are such that Dobbertin™s current techniques
[9]. In a modification to the techniques used so that might find collisions for either the compression
devastatingly on MD4, Dobbertin demonstrated that function or the full hash function of MD5 seem to
collisions for the compression function of MD5 could have little immediate impact on the security of
be found in around 10 hours on a PC. Whereas the HMAC when MD5 is used [IO].
pseudo-collisions discovered by den Boer and
7. Some Alternative Hash Functions
Bosselaers could not be extended to full collisions
for MD5, no such comfort can be drawn with regard As alternative hash functions, SHA- 1, RIPEMD-128
to the recent work of Dobbertin. This, of course, and RIPEMD-160 can still be recommended as be-
should not be viewed as a statement that such an ing secure for any application. While all three hash
extension is trivial. With the current attack, the functions bear similarities to MD4 and MD5 in their
cryptanalyst has some freedom in deriving the colli- design, the techniques of Dobbertin do not readily
extend to these hash functions. Indeed, one of the
sion for the compression function, but once this col-
lision has been achieved it seems to be difficult for design criteria for RIPEMD-128 and -160 was that
the cryptanalyst to account for the fact that the ini- this be the case.
tial value to the chaining variable is pre-specified as
part of the algorithm. Clearly, to become an attack SHA-1 is a revision [17] of the Secure Hash Algo-
rithm (SHA) which first appeared as part of the
on the full MD5, some means of directing the value
of the input chaining variable to the one specified Secure Hash Standard, FIPS 180 [16]. While the
fault in the original SHA and the reasons for the
in the algorithm is required.
particular change made in SHA-1 are not known, it
While more, possibly very complex, analytical work can be anticipated that SHA-1 is a good hash algo-
is required in designing an attack for MD5, there is rithm to use.
no telling how much time or effort this might re-
quire. Nevertheless, it would be a mistake to rely too The forerunner to both RIPEMD- 128 and RIPEMD-
much on the fact that current techniques only pro- 160 was RIPEMD [19], a 128-bit hash function de-
vide collisions for the compression function of MD5. veloped within the framework of the European
Page 5
Previous Page Home Next Page
B U L L E T I N #4 - N O V E M B E R 12, 1996
LABORATORIES
RSA




Union project RIPE (Race Integrity Primitives Existing signatures formed using MD5 are not at risk
Evaluation). Its design was based very closely around and while MD5 is still suitable for a variety of appli-
the principles adopted by Rivest in the design of cations (namely those which rely on the one-way
MD4, and was the subject of considerable analysis, property of MD5 and on the random appearance of
chiefly during the writing of the RIPE report. De- the output) (IS a precaution it should not be used for
spite this however, the techniques recently devel- future applications that require the hash function to
oped by Dobbertin were first used in attacks on re- be collision-resistant.
duced-round versions of RIPEMD [ll]. While not
extending to the full hash function, the situation In this bulletin we have considered various crypt-
analytic developments in the analysis of the com-
with regards to RIPEMD is analogous to that which
pression functions of MD2 and MD5 and for the en-
existed for several years with MD4 when only at-
tire MD4 hash function.
tacks against a reduced-round version of MD4 were
known.
Some of this new cryptanalytic evidence confirms
suspicions voiced several years ago by Ron Rivest
As a consequence, two variants of RIPEMD were
proposed [12]. RIPEMD-128 (providing a 128-bit and makes clear that MD4 should not be used. With
regards to existing applications which use MD2 and
hash value) was intended as a drop-in replacement
MD5, collisions for these hash functions have not
for RIPEMD and offers additional protection against
yet been discovered but this advance should be ex-
the cryptanalytic techniques of Dobbertin. However,
pected. As a consequence applications which rely
the longer hash value provided by RIPEMD-160
on the collision-resistance of a hash function should
(with a 160-bit hash value) is likely to be appealing
in the longer term 1241. With regards to performance, be upgraded away from MD2 and MD5 when practi-
cal and convenient. They can probably be safely
while RIPEMD-128 appears to be somewhat faster
than SHA-1, RIPEMD-160 is slightly slower [12]. “swapped out” in coordination with the vendor™s
normal product release cycle. RSA Laboratories cur-
All three hash functions are slower than MD5.
rently recommends that in general, the hash func-
8. Summary and Conclusions tion SHA-1 [17] be used instead but RIPEMD-160
In summary, we list the more significant cryptana- would also be a good alternative. (It is interesting
lytic results on MD2, MD4 and MD5 and describe that both hash functions borrow heavily from the
initial structural design of MD4.)
some of their immediate consequences.

Occasionally performance requirements or the ex-
MD2 Collisions have been demonstrated for a
istence of fielded applications might make a move
modified version of MD2 1231.
to SHA-1 undesirable when contrasted with the
possibility of using MD5. In such cases it should be
Existing signatures formed using MD2 are not at risk,
confirmed that either collision-resistance is not re-
but MD2 can no longer be recommended for future
quired within the application or that existing colli-
applicutions that will depend on the hush function be-
sion attacks do not apply in that particular envi-
ing collision-resistant. MD2 remains suit&e for use
ronment.
as a one-way hash function.


M D 4 A variety of cryptanalytic results cast doubt It is important to note that these recent cryptana-
lytic efforts on both MD2 and MD5 are almost
on the complexity of the MD4 design [15, 5, 251.
exclusively relevant to finding collisions. The most
Collisions have been demonstrated for MD4 [7, 81.
significant impact of the discovery of hash function
collisions is on the suitability of that hash function
MD4 should not be wed. (This merely restates a rec-
as a part of the process of digitally signing some docu-
ommendation which has been present in the literature
ment. Even then, some signature schemes might well
for some time, in fuct, its use has not been recom-
be more tolerant of the presence of collisions than
mended since the introduction ofMD5.J
others and so careful analysis is recommended to as-
MD5 Both pseudo-collisions [6] and collisions [9, sess exactly what properties of the hash function are
lo] for the compression function of MD5 have been being relied upon in an application. Note that we
demonstrated, though collisions for the full MD5 expect the discovery of collisions to have little or no
have not yet been achieved. impact on the other properties that we usually asso-
Page 6 Previous Page Home Next Page
B U L L E T I N #4 - N O V E M B E R 12,
LABORATORIES 1996
RSA




ciate with a hash function, such as pseudo-random- [16] National Institute of Standards and Technology (NIST).
ness or one-wayness. FIPS Publication 180: Secure Hash Standard (SHS). May
1993.
BSAFE customers should note that while the con- [17] National Institute of Standards and Technology (NIST).
tinued suitability of MD5 for applications requiring FIPS Publication 180-l : Secure Hash Standard. April 1994.
collision-resistance is in question, the use of MD5 in Availablefromhttp://csrc.ncsl.nist.gov/fips/.
other roles, for example as part of a mechanism for [18] B. Preneel. Analysis and Design of Cryptographic Hnsh
random number generation, is still considered safe. Functions. Ph.D. Thesis, Katholieke Universiteit, Leuven,
Indeed, MD2 and MD5 may well remain suitable for 1993.
a wide range of applications. [19] RIPE Integrity Primitives. Final report of RACE Integrity
Primitives Evaluation (R1040), Part III: Recommended
References Integrity Primitives, Chapter 3: RIPEMD, June 1992,
[l] M. Bellare, R. Canetti and H. Krawczyk. The HMAC pages 67-109.
construction. CryptoBytes, 2( 1): 12-15, 1996. [20] R.L. Rivest. The MD4 message digest algorithm. In
Advances in Cryptology - Crypto ˜90, pages 303-311,
[2] M. Bellare, R. Canetti and H. Krawczyk. Keying hash
functions for message authentication. In Advnnces in Springer-Verlag, 199 1.
Cryptology-Crypto ˜96, pages l-15, Springer-Verlag, 1996. [21] R.L. Rivest. RFC 1321: The MD5 Message-Digest Algo-
[3] M. Bellare and P. Rogaway. The exact security of digital rithm. M.I.T. Laboratory for Computer Science and RSA
signatures - how to sign with RSA and Rabin. In Ad- Data Security, Inc., April 1992.
vances in Cryptology - Eurocrypt ˜96, pages 399-416, [22] M.J.B. Robshaw. MD2, MD4, MD5, SHA and other Hash
Springer-Verlag, 1996. Functions. RSA Laboratories Technical Report TR-101,
[4] I. Damgard. A design principle for hash functions. In Ad- version 4.0, July 24, 1995.
vances in Cryprology - Crypto ˜89, pages 416-427, [23] N. Rogier and P. Chauvaud. The compression function of
Springer-Verlag, 1990. MD2 is not collision free. Presented at Selected Areas in
[S] B. den Boer and A. Bosselaers. An attack on the last two Cryptography ˜95, Carleton University, Ottawa, Canada.
rounds of MD4. In Advances in Cryptology - Crypto ˜9 I, May 18-19, 1995.
pages 194-203, Springer-Verlag, 1992. [24] I? van Oorschot and M. Wiener. Parallel collision search
[6] B. den Boer and A. Bosselaers. Collisions for the com- with application to hash functions and discrete loga-
rithms. In Proceedings of 2nd ACM Conference on Com-
pression function of MDS. In Advances in Cryptology -
Eurocrypt ˜93, pages 293*304, Springer-Verlag, 1994. puter and Communicntion Security, pages 210-218, ACM
[7] H. Dobbertin. Alf swindles Ann. CryptoBytes, l(3): 5, Press, 1994.
1995. [25] S. Vaudenay. On the need for multipermutations: Crypt-
analysis of MD4 and SAFER. In Proceedings of the 2nd
[8] H. Dobbertin. Cryptanalysis of MD4. In Proceedings of the
3rd Workshop on Fast Software Encryption, Cambridge, Workshop on Fast Software Encryption, Leuven, Belgium,
U.K., pages 53-70, Lecture Notes in Computer Science pages 286-297, Lecture Notes in Computer Science 1008,
1039, Springer-Verlag, 1996. Springer-Verlag, 1995.
[26] G. Yuval. How to swindle Rabin. Crypto&a, July 1979.
[9] H. Dobbertin. Cryptanalysis ofMD.5 Compress. Presented

<<

. 2
( 19 .)



>>