Re: Crypto Hash functions

Dear Will,

Thanks very much for this informative reply.

Will Dickson wrote:
On Fri, 16 Jun 2006 09:41:40 -0700, robin_carey5 wrote:

Dear sci.crypt,

Fairly recently there was some articles on sci.crypt about how some
crypto-hash functions were "broken". I seem to remember MD5 was one of
the functions that were broken.

Could someone please summarise which functions were broken and to what
extent ?

AIUI (NB. I am not a cryptographer):

MD5: for cryptographic purposes, it's dead. Don't use it. If you are using
it, stop right now. However, if you need a *non-cryptographic* checksum,
which has a much lower probability of returning a false positive purely by
chance than, say, CRC-32, it's still OK. You need to be absolutely sure
that the only thing you're worried about is accidental corruption. If
there's any chance of malicious tampering, MD5 is no good. (For that
matter, MD4 is faster than MD5, and probably comparable for detecting
accidental, and only accidental, corruption.) Collisions in MD4 can now be
engineered by hand.

SHA-1: wounded but still fighting. Its effective strength is now down from
80 bits to 69 bits (source: NIST, 2005.) I have heard that there's a
refinement of the attack that can reduce the workload to 63 bits, but
that it doesn't always work.

The attack against SHA-1 doesn't always apply; there are some
constructions in which it's still as strong as before (80 bits). In
particular, HMAC-SHA1 is still OK.

Before the break, NIST recommended retiring SHA-1 by 2010. This
recommendation has not changed, which some consider rather optimistic.

RIPEMD: gut-shot, but nobody uses it anyway.

RIPEMD-160: comparable speed to SHA-1, and still unbroken last I heard.
Not many people use it because us.gov said to use SHA-1; it does have
a certain amount of EU backing though. Now too short for long-term use.

"SHA-2" series (SHA-{224,256,384,512} - NB. SHA-2 is not an official term
and is probably best avoided): nothing yet. OTOH they're big and
slow, and since they use a similar technique to MD4, MD5, SHA-0 and SHA-1
(all now broken) I personally wish there was something else with official
backing. A NIST-sponsored hash competition, like the one for AES, would be
a good thing.

Tiger, Whirlpool: no results yet AFAIK. Tiger in particular is fast, and I
think these two deserve a lot more attention than they seem to have
received.


My advice (but see disclaimer at the start) would probably be:

- Don't use SHA-1 for signatures unless you absolutely have to. If you do,
make sure whatever you're signing expires before 2010 at the latest.

- If you're using HMAC-SHA1 for authenticating bulk data, carry on for
now, but keep an eye on the situation. It's still good enough, and
SHA-256 is disagreeably slow. Make sure that the software has some
kind of upgrade mechanism; eventually you will need to migrate. Aim to
migrate before 2010: whatever's left of Moore's law ought to have taken
most of the sting out of SHA-256 by then, or there may be a better
alternative. NB. RIPEMD-160 will be too small by 2010, even if nobody
breaks it in the meantime.

- If you're signing bulk data, probably SHA-256 is your best bet. If
you're using RSA signing keys, prefer PSS padding to PKCS#1-v1.5.

- If you're signing certificates, especially ones which need to have long
lifetimes, grit your teeth and use SHA-512. Certs aren't that big, and
quantity may help if quality turns out to be lacking later on.

- If you're doing something else with hashes, clearly the best choice will
depend on your requirements.

HTH

Will.

.

Relevant Pages

  • Re: Crypto Hash functions
    ... crypto-hash functions were "broken". ... MD5: ... SHA-1: wounded but still fighting. ... If you're signing bulk data, probably SHA-256 is your best bet. ...
    (sci.crypt)
  • Re: This Weeks Finds in Mathematical Physics (Week 226)
    ... Yeah, I said SHA-1 and MD5 are different, and I said they were both vulnerable ... Attacking hash functions by poisoned ... where Ldenotes the length of the axiom system A, ...
    (sci.physics.research)
  • Re: Re-secured Algorithm?
    ... >>MD5 collisions are actually trivial to generate. ... SHA-1 had real collisions in MD5. ... Personal attacks aside I doubt many ...
    (sci.crypt)
  • RE: sha-1 cryptography
    ... MD5 and SHA-1 are not used to ensure Confidentiality, ... the confidentiality of passwords or credit card numbers or the ... Computer Emergency Response Teams, and Digital Investigations. ...
    (Security-Basics)