Home page logo

fulldisclosure logo Full Disclosure mailing list archives

Re: Chinese Professor Cracks Fifth Data Security Algorithm (SHA-1)
Date: Thu, 22 Mar 2007 00:48:09 +0300

Dear Blue Boar,

To  be more precise, theoretically, if compare bruteforce with birthday,
160  bit  birthday  is  equivalent  to  81-bit bruteforce by calculation
complexity (number of arithmetic operations).

I  do  not  compare  birthday  vs  bruteforce,  I  compare bruteforce vs
bruteforce and birthday vs birthday.

Practically,  if  you  define  some  real values instead of mathematical
symbols, software algorithm implementation and physical limitations must
be also considered. Software implementation may be impossible or require
more  CPU  cycles to implement algorithm with less arithmetic operations
because, e.g. it requires more physical memory than you can address with
64bit integer :)

--Thursday, March 22, 2007, 12:24:03 AM, you wrote to 3APA3A () SECURITY NNOV RU:

BB> My understanding that the kind of birthday attack under discussion would
BB> start at 80-bits if SHA-1 (at 160-bits) were 100% secure. The attack
BB> under discussion is reported to reduce that to the neighborhood of
BB> 60-something bits.

BB> I am not a mathematician though, so I would be perfectly willing to
BB> believe I was wrong about that.

BB>                                     BB

BB> 3APA3A wrote:
Dear Blue Boar,

It's  not  clear  if  this 'crack' cam be applied to birthday attack. My
in-mind computations were: because birthday attack requires ~square root
of N computations where bruteforce requires ~N/2, impact of 2000 times N
decrease  for birthday is ~64 times faster. 64 = 2^6. Because complexity
is ~square root of possible combinations, it's equivalent of traditional
birthday  attack,  with  160-(2*6)=148  bits  hash (150 is my mistake in
in-mind computations).

Of  cause,  since  I  completely  wasted 10 years after obtaining Master
degree  in  Mathematics  and  3 years after loosing last pencil I may be
completely wrong in computations :)

--Wednesday, March 21, 2007, 9:48:55 PM, you wrote to 3APA3A () SECURITY NNOV RU:

BB> 3APA3A wrote:
I  know  meaning  of  'hash  function'  term,  I  wrote  few articles on
challenge-response   authentication   and   I  did  few  hash functions
implementations  for  hashtables  and  authentication  in FreeRADIUS and
3proxy.  Can  I  claim  my  right  for  sarcasm after calling ability to
bruteforce 160-bit hash 2000 times faster 'a crack'?

BB> Fair enough, your sarcasm tags didn't render properly in my MUA. I was
BB> fooled by you stating that the birthday attack would be 150 bits.

BB>                                          BB

~/ZARAZA http://securityvulns.com/
Íó à â öåëîì, Óèëüÿì, çäåøíèé êëèìàò - åæåëè òîëüêî
ýòî ìîæíî íàçâàòü êëèìàòîì, âïîëíå ñíîñíûé. (Òâåí)

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

  By Date           By Thread  

Current thread:
[ Nmap | Sec Tools | Mailing Lists | Site News | About/Contact | Advertising | Privacy ]