Re: Improvements of SHA-1 attacks

I concur with what Hal said about partial preimage of 0.

So that gives us bigger breathing room than other users of SHA1.
(Considering that SHA1 is used pervasively this is a good position).

I think the perceptional problem for hashcash is that the attacks on
SHA1 are epressed as complexity to find full collision and some people
may incorrectly presume the attacks therefore would apply to hashcash
(ie inferring that partial collisions would therefore be findable with
lower complexity; but as Hal notes hashcash is not based on partial
collisions).  (Technically the original version of hashcash was
partial hash collision based, however the inputs were fixed in a
related way so that first a target string was chosen to avoid birthday
attack.  Anyway it was observed by a few people, Hal being one of
them, that it was anyway simpler to use a fixed target and aim for a
partial pre-image).

So I would opt for waiting for the NIST or community consensus on SHA1
replacement or fix.  For example a recent announcement related to this
(in the fix department) was announced by: Charanjit Jutla

http://eprint.iacr.org/2005/247


I think also the objective for hashcash is rather how fast the hash
evaluation is (which determines verification time).  So for example if
a equal to SHA1 speed fix is proposed with a 160 bit hash output, this
would be nicer for hashcash than switching to SHA-256 as SHA-256 is
slower, and the extra output width not useful to hashcash.

Well ideally for hashcash would actually be smaller hash or
construct... like a 64 bit hash.  I experimented a bit with reduced
block size ciphers and Davies Meyer hash construct and such like in
this regard.  But overall the value from sticking to something
standard and designed to be a hash is better I think.

The other thing is that it was not clear that SHA-256 for example
would necessarily be considerably better against Wang's attacks.

So anyway on the basis that the community has not made a clear
decision on the SHA1 replacement I think later is better ... ie we
follow it.

Adam

On Wed, Aug 17, 2005 at 01:35:46PM +0100, Jonathan Morton wrote:
> >This does not affect hashcash, because contrary to some descriptions,
> >hashcash is not based on hash collisions.  Technically it is based on
> >partial preimages of zero.  No attacks are known to speed up searching
> >for such values with SHA-1.  The brute force search that hashcash 
> >depends
> >on is still the best you can do.
> >
> >The only effect might be if people begin to perceive SHA-1 as "broken"
> >then they might mistakenly mistrust hashcash.
> 
> In any case, it is reasonably easy to fix by redefining the token 
> relative to SHA-256 or similar.  I don't mind re-doing the relevant 
> optimisations for that case - in fact, I think SHA-256 has a structure 
> that's slightly more compiler-friendly with respect to heavily 
> optimised implementations, though these would still consume slightly 
> more CPU time per bit than SHA-1.
> 
> The question is whether to make that move sooner or later?