[hashcash] Improvements of SHA-1 attacks
- From: hal@xxxxxxxxxx ("Hal Finney")
- To: hashcash@xxxxxxxxxxxxx
- Date: Tue, 16 Aug 2005 22:21:28 -0700 (PDT)
I am attending the Crypto conference this week, and at tonight's session
it was announced that Professor Wang has continued to improve her attacks
on SHA-1. Recall that it was Wang who stunned the cryptographic world
a year ago by demonstrating practical attacks on MD4 & MD5 among others.
Shortly afterwards she dropped another bombshell, with an attack on SHA-1
that should find collisions in about 2^69 work instead of the designed
strength of 2^80 work.
Tonight it was announced (Wang couldn't be there due problems getting a
visa from the U.S. government) that with some new ideas, she has improved
the attacks to the point where she estimates that it will be possible
to find a SHA-1 collision in about 2^63 work. This is a factor of 64
improvement over her previous results.
This level is small enough that it should be quite feasible for various
groups to search for actual SHA-1 collisions. As of yet none have been
found, but perhaps within a few months we will see serious efforts begin
to find and publish actual colliding values.
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.
Hal Finney
Other related posts:
