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:

> >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

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))))