Re: [SC-L] [Full-disclosure] Chinese Professor Cracks Fifth Data Security Algorithm (SHA-1)

2007-03-21 Thread der Mouse
 Cracking a hash would [...].  There are an infinite number of
 messages that all hash to the same value.

Yes, but there's no guarantee that this is true of any particular hash
value, such as the one you're intersted in, only that there exists at
least one hash value that it's true of.

(At least, for hash functions in general.  A *good* hash function will
of course have this property for all hash values.  I don't know whether
SHA-1 is good in this respect, though I would expect it is.)

Okay, nitpicky-mathematician mode off :-)

/~\ The ASCII   der Mouse
\ / Ribbon Campaign
 X  Against HTML   [EMAIL PROTECTED]
/ \ Email!   7D C8 61 52 5D E7 2D 39  4E F1 31 3E E8 B3 27 4B
___
Secure Coding mailing list (SC-L) SC-L@securecoding.org
List information, subscriptions, etc - http://krvw.com/mailman/listinfo/sc-l
List charter available at - http://www.securecoding.org/list/charter.php
SC-L is hosted and moderated by KRvW Associates, LLC (http://www.KRvW.com)
as a free, non-commercial service to the software security community.
___


Re: [SC-L] [Full-disclosure] Chinese Professor Cracks Fifth Data Security Algorithm (SHA-1)

2007-03-21 Thread Blue Boar
3APA3A wrote:
 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.

Cracking a hash would never mean recovering the full original message,
except for possibly messages that were smaller than the number of bits
in the hash value. There are an infinite number of messages that all
hash to the same value.

The best crack you can have for a hash is to be able collide with an
existing hash value and be able to choose most of the message contents.

BB
___
Secure Coding mailing list (SC-L) SC-L@securecoding.org
List information, subscriptions, etc - http://krvw.com/mailman/listinfo/sc-l
List charter available at - http://www.securecoding.org/list/charter.php
SC-L is hosted and moderated by KRvW Associates, LLC (http://www.KRvW.com)
as a free, non-commercial service to the software security community.
___


Re: [SC-L] [Full-disclosure] Chinese Professor Cracks Fifth Data Security Algorithm (SHA-1)

2007-03-21 Thread Blue Boar
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'?

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

BB
___
Secure Coding mailing list (SC-L) SC-L@securecoding.org
List information, subscriptions, etc - http://krvw.com/mailman/listinfo/sc-l
List charter available at - http://www.securecoding.org/list/charter.php
SC-L is hosted and moderated by KRvW Associates, LLC (http://www.KRvW.com)
as a free, non-commercial service to the software security community.
___


Re: [SC-L] [Full-disclosure] Chinese Professor Cracks Fifth Data Security Algorithm (SHA-1)

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

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

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 [EMAIL PROTECTED]:
 
 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
 
 
___
Secure Coding mailing list (SC-L) SC-L@securecoding.org
List information, subscriptions, etc - http://krvw.com/mailman/listinfo/sc-l
List charter available at - http://www.securecoding.org/list/charter.php
SC-L is hosted and moderated by KRvW Associates, LLC (http://www.KRvW.com)
as a free, non-commercial service to the software security community.
___