Re: Chinese Professor Cracks Fifth Data Security Algorithm (SHA-1)

[Tim <tim-security () sentinelchicken org>]

Hello,

On Wed, Mar 21, 2007 at 06:45:19PM +0300, 3APA3A wrote:
> Dear Michael Silk,
>
> First,  by  reading  'crack'  I thought lady can recover full message by
> it's signature. After careful reading she can bruteforce collisions 2000
> times faster.

Both of you guys are confused.

First off Michael: this is old news.  It doesn't seem to indicate that
finding collisions is any faster than 2^63, which was reported quite
some time ago[1].


> SHA-1  is  160  bit  hash. Bruteforced 2000 times faster, it retains the
> strength  of  149-bit  hash for bruteforce collision attack (150 bit for
> birthday attack) by given text (MD5 is 128 bit). Great achievement. This
> can only be treated seriously by US court, like it was with MD5 :)


Secondly, 3APA3A, birthday attacks against the collision-resistance
property of a hash take approximately 2^(b/2) time, where b is the
number of bits.  That is, brute-force birthday attacks would take around
2^80 time against SHA-1.  These attacks reduce the complexity to 2^63,
or thereabouts, at least from what I've read previously[1].

As for US courts... which case are you referring to (as I'd be
interested to read the results)?  The only one I know of involving MD5
was an Australian case[2].

cheers,
tim

1. http://www.schneier.com/blog/archives/2005/08/new_cryptanalyt.html

2. http://news.com.com/2061-10789_3-5829714.html

_______________________________________________
Full-Disclosure - We believe in it.
Charter: http://lists.grok.org.uk/full-disclosure-charter.html
Hosted and sponsored by Secunia - http://secunia.com/