MD4-derived hash functions
-----BEGIN PGP SIGNED MESSAGE-----
Date: Tue, 24 Oct 1995 13:14:41 -0400 From: hallam@w3.org Subject: Re: MD5 weakness
Ron has not mentioned such an event to me and if that were the case I would seriously doubt that he would not have been told about it. The only comment he generally makes is that he wrote MD5 because "MD4 was making me nervous".
In the MD5 RFC, I seem to recall the statement that MD4 was trading off too much strength for additional speed. However, sometime around that time, it came out that there were attacks on two-round variants of MD4, which is the stated reason for the development of RIPE-MD. Does anyone know whether Rivest was motivated to design MD5 by the partial attacks on MD4, or whether those came later? (This is totally idle curiousity.)
NIST and the NSA trusted MD4 sufficiently to base SHA upon it. SHA is preferable in many ways to MD5, it has a different approach to extending the scheduling and resist differential cryptanalysis. There is a problem with the compressor function of MD5 which I dislike.
All of the well-known software hash functions seem to be based on MD4 these days, but that doesn't mean much about the security of MD4--3DES with three independent keys looks pretty strong, as does 3DES with two independent keys, but that doesn't mean that single DES is a strong enough cipher for modern applications. One issue that exists with MD5, but not with SHA or the longer hash versions of Haval, is that MD5 has only a 128 bit hash function output, which corresponds loosely to having a 64-bit key. This implies that a wealthy enough opponent could determine a pair of MD5 inputs that collide, and conceivably use this in an attack. I think we should stick to 160 bit or longer hashes for future designs. (See P. van Oorschot and M. Weiner, "Parallel Collision Search with Application to Hash Functions and Discrete Logarithms," in the proceedings of the 1994 Fairfax Conference, for example). As an aside, what hash functions are there out there that look reasonably strong, have hash outputs of at least 160 bits, and aren't based on MD4? Some of the Snefru variants with many passes (eight?) come to mind, and the GOST hash function fits all the criteria, except I have a hard time convincing myself it's as strong as it claims to be. Is there a generic construction for arbitrary-length hash functions from good block or stream ciphers?
Phill
--John Kelsey, jmkelsey@delphi.com PGP 2.6 fingerprint = 4FE2 F421 100F BB0A 03D1 FE06 A435 7E36 -----BEGIN PGP SIGNATURE----- Version: 2.6.2 iQCVAwUBMI+Mc0Hx57Ag8goBAQFJ9gP/VMvNefSm77prSY/NMbJfGO1EVmQrUAHn kEQEse+cXiaoJTe7njxUqycuDX0PN09C4XhNVOQJ6IBpCPZOKQMiXsI9FwAfjGWb mibwSfzyiXwxny1kYgfDCffS8KwdlWiVjxj1+MhvqhGQnxPsVA6UVrSCyAyHPZVJ UTXUWBJlJho= =2Pti -----END PGP SIGNATURE-----
Does anyone know whether Rivest was motivated to design MD5 by the partial attacks on MD4, or whether those came later? (This is totally idle curiousity.)
It was after...
All of the well-known software hash functions seem to be based on MD4 these days, but that doesn't mean much about the security of MD4--3DES with three independent keys looks pretty strong, as does. 3DES with two independent keys, but that doesn't mean that single DES is a strong enough cipher for modern applications.
3DES with only two independent keys is only slightly more secure than DES, consider a variant of the meet in the middle attack exploiting the fact that the constraint network is reductible to two equations in one unknown.
Is there a generic construction for arbitrary-length hash functions from good block or stream ciphers?
Yes, see Bruce's book. Phill
On Thu, 26 Oct 1995 12:03:57 -0400, you wrote:
3DES with only two independent keys is only slightly more secure than DES, consider a variant of the meet in the middle attack exploiting the fact that the constraint network is reductible to two equations in one unknown.
I believe you meant 2DES? I've not heard of a meet in the middle attack on 2-key 3DES better than brute force of a 112-bit key. Even for 2DES, or for 3-key 3DES, doesn't a meet in the middle attack require on the order of 2^56 words of memory? This, as a practical matter, makes a brute-force attack much more difficult than it would appear at first glance.
-----BEGIN PGP SIGNED MESSAGE----- In article <199510270413.VAA29718@ix7.ix.netcom.com>, John Lull <lull@acm.org> wrote:
Even for 2DES, or for 3-key 3DES, doesn't a meet in the middle attack require on the order of 2^56 words of memory?
Actually, as it turns out, van Oorschot & Wiener have a recent paper which describes how to break 2DES without the huge space requirements without sacrificing too much time (by using their parallel collision search method). They estimated the cost to break 2DES via specialized hardware, and decided that breaking 2DES was only about 2^14 times as costly as breaking DES. The conclusion to take away from this is simple: double encryption doesn't give you much extra security over single encryption. Don't use double encryption. - --- [This message has been signed by an auto-signing service. A valid signature means only that it has been received at the address corresponding to the signature and forwarded.] -----BEGIN PGP SIGNATURE----- Version: 2.6.2 Comment: Gratis auto-signing service iQBFAwUBMJLKmSoZzwIn1bdtAQEk5gF/VtAgBNgB6o8SrTWSSMaciikdzoVCIqYF JdXxs4pWt6ueY8WVsSEj5yU5EKAT0/4M =6YNF -----END PGP SIGNATURE-----
The conclusion to take away from this is simple: double encryption doesn't give you much extra security over single encryption. Don't use double encryption.
That doesnt make sense. If one accepts that double encryption is securer than single encryption, wether marginally or twice as secure, why not use it? I would rather stand behind a steel door and a wooden door than a steel door alone if anyone was shooting rounds at me. Cheers, Mark mark@lochard.com.au
On Mon, 30 Oct 1995, Mark wrote:
That doesnt make sense. If one accepts that double encryption is securer than single encryption, wether marginally or twice as secure, why not use it?
Hi Mark - The problem with double encryption with DES is that it's vulnerable to a meet-in-the-middle attack if you have known plain text. You can encrypt the plaintext with all possible keys and store them in a (big) table, then decrypt the cypher text until you get a match with one of the values in the table. Doesn't work too well on an 8Mb P90 (2^59 bytes is half a peta byte), but since memory capacity theoretically increases as the square of processor speed, the attack becomes feasible much, much, sooner than breaking a 112 byte key. Using 3-DES,even with only two distinct keys, makes this attack infeasible, as the table size becomes much to large. 2-IDEA is similarly safe (2^131 bytes of memory is a long way off (I wonder what the first version of M$ Word to need that much memory will be). Simon --- (defun modexpt (x y n) "computes (x^y) mod n" (cond ((= y 0) 1) ((= y 1) (mod x n)) ((evenp y) (mod (expt (modexpt x (/ y 2) n) 2) n)) (t (mod (* x (modexpt x (1- y) n)) n))))
On Mon, 30 Oct 1995, Mark wrote:
The conclusion to take away from this is simple: double encryption doesn't give you much extra security over single encryption. Don't use double encryption.
That doesnt make sense. If one accepts that double encryption is securer than single encryption, wether marginally or twice as secure, why not use it?
Ah yes, but the vagarities of crypto don't lend themselves to real-world analogies so easily. With crypto schemes, if you use double-encryption, you effectively halve the amount of time needed to crack them. This is because of the "man in the middle attack." Schneier talks about it in Applied Crypto, and I am sure others on this list know the technical details better than I. What Schneier says has been proven to be secure is, instead, a triple encryption scheme. Using two different keys, it goes something like this (if memory serves): Cipertext = P1xorEK1 -> C1xorDK1 -> C2xorEK1 Where P1 is the plaintext, EK1 is encrypt key 1, and DK1 is decrypt key 1. That doesn't look right the longer I consider it, but the basic idea is there. Encrypt, decrypt, then encrypt again. "Freedom is meaningless unless | ic58@jove.acs.unt.edu - James Childers you can give to those with whom| No man's freedom is safe you disagree." - Jefferson | while Congress is in session EA 73 53 12 4E 08 27 6C 21 64 28 51 92 0E 7C F7
participants (7)
-
Childers James -
daw＠quito.CS.Berkeley.EDU -
hallam＠w3.org -
JMKELSEY＠delphi.com -
John Lull -
Mark -
Simon Spero