[hashcash] Re: Hashcash and the cracking of SHA1
- From: Adam Back <adam@xxxxxxxxxxxxxxx>
- To: hashcash@xxxxxxxxxxxxx
- Date: Thu, 1 Feb 2007 19:02:56 -0500
I think it is a quite different thing to attack hashcash (partial 2nd
preimage) than to create collisions on SHA1 (based on birthday
principle).
finding a preimage means given Y = H(X), find X
find a 2nd preimage means given X and Y such that Y = H(X) to find
another X' such that Y = H(X') = H(X).
a birthday collision means to start from scratch to find X and X' such
that H(X) = H(X')
Now in a secure hash (of output size 160 bits) the work of finding a
preimage is 2^160 operations, and the work of finding a second
preimage is 2^160 operations, but the work of finding a birthday
collision is "only" 2^80 operations.
So from one point of view we can say the attack on birthday collisions
is easier than the attack on a 2nd preimage.
Hashcash is basically like a 2nd preimage attack except we're given
Z = 0^160 (ie the all 0 string), and we're asked to find an X such that
H(X) =partial Z
=partial just means as many 0 bits as possible ie for k bits:
or H(X) >> (160-k) == Z (where >> is right shift)
If Wang et al can create multiple collisions ie:
H(X1) = H(X2) = ... = H(Xn)
very cheaply after the 2^69 effort for a large n, then for 2^89 effort
they could hypothetically create a set of collisions which are also 20
bit hashcash stamps. So on that basis I'm not worried that effort is
huge.
But the main thing I think is if SHA1 is broken badly enough to affect
signatures, then there are hundreds of protocols in need of
re-writing. So I think we have a big safety margin over those uses of
SHA1 because they do rely on birthday collision resistance much more
than hashcash does.
So even though you might from the wording that if Wang et al can find
birthday collisions on SHA1 for 2^69 effort, that they could find
partial collisions with less work. However as I explain above, as far
as I understand the attacks that is not the case because their attack
doesnt apply to hashcash partial 2nd preimages.
Adam
On Sun, Jan 28, 2007 at 01:14:48PM -0500, David Fuelling wrote:
> Hey List,
>
> Sorry if this has been covered in the last two years, but I just want to be
> sure I've got my facts straight.
>
> So, sometime in 2005, the SHA1 algorithm was cracked by a Chinese
> mathematician. Bruce Schneier blogs about it here:
>
> http://www.schneier.com/blog/archives/2005/02/sha1_broken.html
>
> In a nutshell: "Collisions in the the full SHA-1 in 2**69 hash operations,
> much less than the brute-force attack of 2**80 operations based on the hash
> length."
>
> I'm wondering if this has any implications on Hashcash. From my way of
> thinking, if the supposed "crack" still takes 2^69 operations (instead of
> the typical 2^80 via brute force), that's still going to be a lot *longer*
> than computing a partial hash collision that might take seconds or minutes
> (as is the case in Hashcash).
>
> I guess I'm just wanting to be sure that Hashcash isn't somehow vulnerable
> in its current form. I don't think it is, but figured I'd ping the list
> just to be sure.
>
> Thanks!
>
> David
>
>
>
>
>
Other related posts:
