Re: Thinking aloud.

On Fri, Oct 26, 2012 at 09:40:55AM +1100, Nigel Cunningham wrote:
> >So it is **far** more likely that the hard drive will fail than the
> >chance that you will observe a SHA1 hash collision.  Heck, I'm pretty
> >sure chances of the memory going wonky on you when you do the memcmp
> >is probably more likely....
>
> You wouldn't be concerned about someone trying to craft two pages
> having the same hash and using it as a security vulnerability? (So I
> should just be happy with comparing hashes?) Would you be concerned
> if an MD5 hash was used instead?

I'm not particularly concerned because SHA1 is a cryptographic hash.
What that means is that as far as we know the easist way to find two
pages that have the same SHA1 hash is brute force --- i.e., you would
have to try 2**80 different 4k pages until you found two that had the
same hash, and you were trying to construct a 4k page that had the
same hash as a specific 4k page, the work factor would be 2**160.

The problem with MD5 is not just that with a 128 bit hash size, the
chances of a birthday hack is just within the realm of calculability
today (i..e, a work factor of 2**64).  But rather, due to
cryptographic advances, there are known techniques that allow the
generation of collisions with a work factor of 2**39.  As a result,
using MD5 as a cryptographic hash is *not* recommended.

Could someone find a way of cryptanalyzing SHA1?  Sure, it's possible.
No one has created an actual attach which creates a collision in less
than brute-force time for the full 80-round SHA1 function.  However,
there are successful attacks on simplified, truncated round SHA1
variants (i.e., where you only use the first 64 rounds of the SHA1
compression function).  This is what motiviated NIST to create the
SHA2 and more recently, the SHA3 standards.

But I really really wouldn't worry about it, since even if someone
malicious could figure out a way to create hash collisions in, say,
10**20 years instead of 10**30 years, it's not clear it would be
practical for attacking a Linux system doing a suspend/resume --- and
if you have someone with local shell access to your system, there are
easier ways for them to crash your system.

And if someone did figure out a pratical way to create hash collisions
for SHA1, it will be used to forge digital certificate to steal
millions from banks, or to fake out Microsoft's software update server
so as to introduce a cyberwarefare payload to attack Iran's nuclear
centrifuge program [1].  Trust me, the first use will not be to try to
crash systems using TuxOnIce.  :-)

[1] http://arstechnica.com/security/2012/06/flame-crypto-breakthrough/

> You wouldn't be concerned about someone trying to craft two pages
> having the same hash and using it as a security vulnerability? (So I
> should just be happy with comparing hashes?) Would you be concerned
> if an MD5 hash was used instead?

MD5 has been significantly compromised as a cryptographic hash.  So if
you really are concerned about someone malicious trying to create hash
collisions, someone can use a chosen prefix collision attack to find
collisions in hours using off-the-shelf hardware.  Of course, whether
the target page that you hope to spoof by finding a hash collision is
still valid several hours is somewhat questionable, but MD5 has been
sufficiently broken that its use is not adviseable if you are
depending on collision resistance.

Regards,

						- Ted