Re: SHA1 hash safety

["Brian O'Mahoney" <omb@khandalf.com>]

Please see below:

C. Scott Ananian wrote:
> On Sat, 16 Apr 2005, Brian O'Mahoney wrote:
> 
>> (1) I _have_ seen real-life collisions with MD5, in the context of
>>    Document management systems containing ~10^6 ms-WORD documents.
> 
> 
> Dude!  You could have been *famous*!  Why the
> aitch-ee-double-hockey-sticks didn't you publish this when you found it?
> Seriously, man.

The MD5 has was fine, or at least the code (a) produced the correct
results on the published test cases, and, (b) was properly applied to
all bytes of the file(s). I was surprised when it happened, which is why
I bothered to post to this list at this time, so I make two more points

(1) These hashes were designed, to assist in the construction of digital
signatures, ie so it is hard to produce a document to hash to a known
hash value, and that with a defined document format so they are designed
(i) hash similar documents far apart, and (ii) be hard to reverse;

it says nothing about naturally ocurring collisions, ie where the
document is not constrained to be similar,

> 
> Even given the known weaknesses in MD5, it would take much more than a
> million documents to find MD5 collisions.  I can only conclude that the
> hash was being used incorrectly; most likely truncated (my wild-ass
> guess would be to 32 bits; a collision is likely with > 50% probability
> in a million document store for a hash of less than 40 bits).
> 
> I know the current state of the art here.  It's going to take more than
> just hearsay to convince me that full 128-bit MD5 collisions are likely.
> I believe there are only two or so known to exist so far, and those were
> found by a research team in China (which, yes, is fairly famous among
> the cryptographic community now after publishing a paper consisting of
> little apart from the two collisions themselves).

(2) I am not concerned with cryptography here, merely sound engineering
tradeoffs and the avoidance of _pain_in_the_ass_ when we do see a
random collision, [NB the 2^69 is to 'cause a collision in SHA1' not the
odds against such a collision] ... (below)

> 
> Please, let's talk about hash collisions responsibly.  I posted earlier
> about the *actual computed probability* of finding two files with an
> SHA-1 collision before the sun goes supernova.  It's 10^28 to 1 against.
> The recent cryptographic works has shown that there are certain
> situations where a decent amount of computer work (2^69 operations) can
> produce two sequences with the same hash, but these sequences are not
> freely chosen; they've got very specific structure.  This attack does
> not apply to (effectively) random files sitting in a SCM.
>   http://www.schneier.com/blog/archives/2005/02/sha1_broken.html
> 
> That said, Linux's widespread use means that it may not be unimaginable
> for an attacker to devote this amount of resources to an attack, which
> would probably involve first committing some specially structured file
> to the SCM (but would Linus accept it?) and then silently corrupting
> said file via a SHA1 collision to toggle some bits (which would
> presumably Do Evil).  Thus hashes other than SHA1 really ought to be
> considered...
>
> ..but the cryptographic community has not yet come to a conclusion on
> what the replacement ought to be.  These attacks are so new that we
> don't really understand what it is about the structure of SHA1 which
> makes them possible, which makes it hard to determine which other hashes
> are similarly vulnerable.  It will take time.
> 
> I believe Linus has already stated on this list that his plan is to
> eventually provide a tool for bulk migration of an existing SHA1 git
> repository to a new hash type.   Basically munging through the
> repository in bulk, replacing all the hashes.  This seems a perfectly
> adequate strategy at the moment.

... [I say again, the problem here is NOT forgery of hashes, though SCO
like paranoia ...] ... but the hashes are a tiny part of the total
space, even for trivial patches, so that, providing _NOW_ for a longer
hash (and then why not use, say, SHA-256 for now as well) is prudent.

We do not want to revisit the plumbing, in the next 3-10 years, for 16
bytes per hash.

Finally I can do no more than quote Schneier:

"SHA-1 has been broken. Not a reduced-round version. Not a simplified
version. The real thing. ...

It's time for us all to migrate away from SHA-1.

Luckily, there are alternatives. The National Institute of Standards and
Technology already has standards for longer -- and harder to break --
hash functions: SHA-224, SHA-256, SHA-384, and SHA-512. They're already
government standards, and can already be used." and there are FOSS
implementations.

Or, put more simply by Jon Callas, PGP's CTO: "It's time to walk, but
not run, to the fire exits. You don't see smoke, but the fire alarms
have gone off." That's basically what he said last August [2004].

>  --scott
> 
> WASHTUB Panama Minister Moscow explosives KUGOWN hack Marxist LPMEDLEY
> genetic immediate radar SCRANTON COBRA JANE KGB Shoal Bay atomic Bejing
>                          ( http://cscott.net/ )
> -
> To unsubscribe from this list: send the line "unsubscribe git" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> 
> 
> 

-- 
mit freundlichen Grüßen, Brian.

Dr. Brian O'Mahoney
Mobile +41 (0)79 334 8035 Email: omb@bluewin.ch
Bleicherstrasse 25, CH-8953 Dietikon, Switzerland
PGP Key fingerprint = 33 41 A2 DE 35 7C CE 5D  F5 14 39 C9 6D 38 56 D5