hash attacks and hashcash (SHA1 partial preimage of 0^160)

[Adam Back]

(This discussion from hashcash list is Cc'd to cryptography and
cypherpunks.)

Hashcash uses SHA1 and computes a partial pre-image of the all 0bit
string (0^160).

Following is a discussion of what the recent results from Joux, Wang
et al, and Biham et al on SHA0, MD5, SHA1 etc might imply for hashcash
SHA1 (and for hypothetical hashcash SHA0, MD5 etc by way of seeing
what it will mean if SHA1 eventually suffers similar fate to SHA0).

(All as far as I understand so far).

Hashcash stresses the SHA1 function in a different direction than
sigantures and MACs -- in assuming partial pre-images are hard (ie an
k-bit partial pre-image should take about 2^k operations).  (Partial
2nd pre-images are also "interesting" against hashcash -- see below).

(As a security argument if partial pre-images say up to m<n bits were
to turn out to be easy (take much less than 2^m work effort) then this
could be used to find full pre-images with < 2^n effort, and full
birthday collisions with < 2^(n/2) effort -- where n is the hash
output size).


Hashcash is computing partial preimages (of the all 0 bit string).

The original hashcash (alpha format) computed partial 2nd-preimages as
follows:

H( time || resource ) =partial H( time || resource || random )

so the image is H( time || resource ), the pre-image is time ||
resource, and the (partial) 2nd pre-image is time || resource ||
random, and the images 

H( time || resource ) and H( time || resource || random )

partially match.

Then several people independently (Hal Finney, Thomas Boschloo)
suggested using a fixed image (0^160, ie all 0 bits) instead of the
image H( time || resource ).  (Hashcash version 0 and version 1
formats use the all 0 bits approach.)  ie so one is looking for:

H( time || resource || random ) =partial 0^160

As long as SHA1 is a good hash function this should be just as "fair"
a string to find partial pre-images of.


So with the last days news: as I read it the MD5 attack can find
relatively arbitrary pairs of pre-images (which differ in a few
well-chosen bits).  As a birthday attack, or perhaps with some more
work as a 2nd pre-image attack (2nd pre-image unclear).

Birthday style attacks don't help against hashcash as the atacker has
limited control over the H( time || resource ) in the alpha format and
no control over the 0^160 in v0 and v1 format hashcash.


So the way to apply a 2nd pre-image attack (if general 2nd pre-image
is possible with the approach) is to find one partial hash collision
the usual way (brute force), then re-use the work a bit and use it to
get subsequent collisions.  As far as hashcash is concerned these will
be of approximately the same value as the original (and not full
collisions) because they are against 0^n and the partial hash
collision (which a full collision was found against) only has 0^k bits
of leading 0s.


So I think if hashcash were using SHA-0, the following attack should
work: spend lots of work create eg a 50-bit hashcash token, use the
SHA-0 attack (Wang et al attack has work order 2^40 hash operations)
to find another (and maybe a small family of) hashcash stamps which
are full collisions with the 40-bit partial collision we just created.

I have not seen any indication if there is a family of collisions that
come more cheaply after the initial 2^40 operations of the Wang et al
approach.

As long as the work to create each 2nd pre-image in the family that
can be derived from one starting stamp is less than the value of the
stamp, the spammer wins in some way.  He can get some economies of
scale (up to the family size) in creating multiple stamps for the same
recipient.  However this is not so interesting to the spammer he would
sooner have economies of scale in sending to _everyone_ not DoSing one
user.  Also until we know the family size we do not know how bad even
a DoS advantage there would be.


For SHA-1 so far none of the above holds.  If someone manages to
extend the Biham attack to the full 80 rounds then the similar
argument to the SHA-0 based hashcash would presumably hold.

But this is based on what has been said so far about how the attacks
work.  Perhpas the same or related techniques now people have seen how
they work could be adapted to provide partial pre-images more
efficiently than brute force directly.

Adam

On Wed, Aug 18, 2004 at 02:03:09PM -0400, Jean-Luc Cooke wrote:
> To be clear:
>   MD5 is borken.  The whole thing:
>     http://www.md5crk.com/md5col.zip
>   SHA-0 is broken.  The whole thing:
>     http://www.md5crk.com/sha0col
>   HAVAL-128 and RIPEMD-128 and MD4 are also broken using the same techniques.
> 
> 56 round SHA-1 (out of a possible 80) is broken.
> 
> The event of the pasat week cast heavy doubt on the current common techniques
> used in hash algorithms.  MD4 was the first to use this unblanced Fiezel
> network.
> 
> Wirlpool and Tiger are sometimes called "wide-trail" hashs.  Different beasts
> entirly.
> 
> I suspect even SHA-256 and SHA-384/512 may be vulnerable to these attacks to
> some extent.
> 
> I expect there to be a flurry of new hashs proposed and adopted as
> industry/government/international standards.