[darcs-devel] cryptographic hash functions in darcs (re: announcing darcs 2.0.0pre3)

[zooko]

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.

> Excessive
> 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  
economics.".

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.


Regards,

Zooko