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

[3APA3A <3APA3A () SECURITY NNOV RU>]

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/