[Haskell-cafe] Re: [darcs-devel] cryptographic hash functions in
darcs (re: announcing darcs 2.0.0pre3)
zooko at zooko.com
Thu Jan 24 18:37:50 EST 2008
On Jan 24, 2008, at 2:57 PM, Achim Schneider wrote:
> And anyway, if your goal is security 'till 2015, SHA1 seems to be
> secure enough(TM) for all practical purposes
This is true, only given several of assumptions: no further
algorithmic improvements will arise that further reduce the
complexity of cracking SHA-1, it will prove impossible to parallelize
SHA-1 cracking or to build custom hardware to do it more quickly and
cheaply, the global market for computing-on-demand will not cause the
cost of distributed computation to fall too fast, quantum computation
will not become sufficient, etc..
These are a lot of big "if"'s to place long-term bets on.
> (that is, without using
> par on a beowolf cluster on all ps3's in the world), as the
> speed^H^H^H^H^Hcomplexity of a single CPU core won't obey Moore's law
> anymore, for physical reasons.
Nobody says you have to use a single CPU to crack SHA-1. Distributed
efforts and custom hardware have cracked other crypto algorithms in
the recent past.
> \OTOH, when quantum computing arrives, you're fucked, anyway.
Quantum computing would not by itself render SHA-256 insecure.
Unless, of course, there were a new improved kind of cryptanalysis
against SHA-256 which puts it "within range" of quantum computation.
> paranoia in general doesn't pay off if the to protected data is
> publicly accessible in any way whatsoever.
Agreed. There is a reasonable case to be made for darcs: "If you use
darcs to maintain your source code you are willing to be vulnerable
to everyone with whom you transitively exchange patches, that such
people might choose to subvert your repository.". This is what darcs
1 offers, and it has not deterred me from using darcs 1 for my open
source projects with few contributors.
There is also a reasonable case to be made: "To the best of our
current knowledge, you can for at least the near future rely on the
property that a patch id can match at most one patch.". SHA-1 does
not offer this.
What I object to is false advertising -- telling people that darcs
has the latter guarantee when the best minds who have studied the
issue are in agreement that it does not currently offer that
guarantee, and as time passes it will become increasingly likely that
more and more unknown people gain the ability to violate that guarantee.
> THEY would be much more cost-effective if THEY'd go for
> physically hacking your system instead of paying N million € for
> hardware to crack your codes.
This is a very good argument -- an economic argument. Security gurus
nowadays like to say "Amateurs study algorithms; professionals study
But it turns out, if you pay the cost to generate collisions in a
widely used hash function like SHA-1, then you can use your results
against all kinds of users of that function, without paying much
marginal cost for each added target. This includes targets whose
physical security is high.
Put it this way: sure you can subvert *my* computer on the cheap. It
would probably cost you a few thousand dollars -- I have no idea how
much really. But then you would have to pay again to subvert someone
else's computer. Whereas if you build a SHA-1-cracking machine and
rainbow tables of collisions, you can use this in many ways,
targetting many different algorithms.
Another way to approach the issue is: why SHA-1? SHA-256 would be
slower and safer, including, probably, safe even if someone out there
builds a quantum computer without telling us about. Tiger would be
faster and safer (although not safe against a quantum computer).
SHA-1 is the worst of both worlds -- slow and unsafe.
More information about the Haskell-Cafe