Bugtraq mailing list archives
Re: SHA-1 broken
From: Anatole Shaw <shaw_bugtraq20050218 () autoloop com>
Date: Sat, 19 Feb 2005 00:42:56 -0500
Sadly, there is no magic bullet for the SHA-1 problem. Let me say, in classic Bugtraq style, that I believe the "temporary workaround for this vulnerability" is to move to SHA-512 as quickly as possible. NIST was going to recommend SHA-256 and SHA-512 by 2010, but for the security-conscious the time is now. The "computer security response" should not be to re-jigger the hashes, bet on crypto tricks that haven't seen any review, and guess at the computational complexity of the result. The only fix will be informed analysis of the new paper from the Chinese team (which hasn't even been released yet) and the informed development of a solid cryptographic response. Anatole On Fri, Feb 18, 2005 at 05:06:42PM +1100, Michael Silk wrote:
Michael, But with such functions the point is that "input" isn't a function, it's a string - and it can only be the inverse of one, not both; i.e. the result of "invHashFunc1( foo )" _wont_ equal "invHashFunc2( foo )". So if the user is attempting to break a login screen with his invHashFunc's, and the hash of the users password is implemented as described, they can't possibly provide the right inversions for _both_ functions in one string; unless they happen to be the same. No? -- Michael On Fri, 18 Feb 2005 00:45:24 -0500, Scovetta, Michael V <Michael.Scovetta () ca com> wrote:Michael, I'm not sure that it would help significantly. If the end-result of this research on breaking hash algorithms is to create "inverse-MD5" and "inverse-SHA" functions, then: input = invHashFunc2( substring(invHashFunc1(result)) ) By our assumptions, invHashFunc1 and invHashFunc2 are both tractable, the substring function would simply add a polynomial factor to the calculation to guess it right. You could create arbitrarily complex functions, like: MD5(SHA(input+salt)+MD5(input+salt)+salt) But in the end, if invHashFunc1 and invHashFunc2 are both tractable, then nothing you do could help it (beyond a polynomial factor). And keeping the actual algorithm-composition secret wouldn't help much either. -Mike -----Original Message----- From: Michael Silk [mailto:michaelsilk () gmail com] Sent: Thu 2/17/2005 10:30 PM To: Scovetta, Michael V; bugtraq () securityfocus com Cc: Subject: RE: SHA-1 broken Michael, But wouldn't it render a login-based hashing system resistant to the current hashing problems if it is implemented something like: -- result = hashFunc1( input + hashFunc1(input) + salt ) // // instead of // result = hashFunc1( input + salt ) -- We can see that the input to the functions is the same, so although a collision could be found within one or the other but it would not give the correct result unless the hashFunc1( foo ) = hashFunc2( foo ) where foo is the magical input that gives the same result as "bar" (the initial password). -- Michael-----Original Message----- From: Scovetta, Michael V [mailto:Michael.Scovetta () ca com] Sent: Friday, 18 February 2005 8:34 AM To: Kent Borg; Gadi Evron Cc: bugtraq () securityfocus com Subject: RE: SHA-1 broken Kent-- Compositions won't really help very much. Lets say (I'm sure the exact numbers are wrong here) that it takes brute-forcing MD5 takes 2**80, and brute-forcing SHA-1 takes 2**90. And due to recent discoveries, we can push those down to 2**50 and 2**55 respectively. Breaking a composition would still take on the order of 2**55 (the harder of the two)-- you're not going to make it exponentially harder to crack by composing. Doing something a little more slick like interweaving the bits of the two algorithms would make it geometrically harder, but not exponentially. You'd really have to get a new algorithm. Of course, this is assuming that the actual attack allows one to take some predefined input A, and compute some evil input A' such that Hash(A)=Hash(A'). If the attacks are simply to create colliding input data, then the underlying algorithm is still safe for most applications. Of course, I'm not a crypto-expert, so this may all be totally wrong. Michael Scovetta Computer Associates Senior Application Developer -----Original Message----- From: Kent Borg [mailto:kentborg () borg org] Sent: Wednesday, February 16, 2005 6:27 PM To: Gadi Evron Cc: bugtraq () securityfocus com Subject: Re: SHA-1 broken On Wed, Feb 16, 2005 at 02:56:27PM +0200, Gadi Evron wrote:Now, we've all seen this coming for a while. http://www.schneier.com/blog/archives/2005/02/sha1_broken.html Where do we go from here?I am feeling smug that in a project I am working on I earlier decided our integrity hashes would be a concatenation of MD5 and SHA-1, not that that's a fix, but it helps. I am also appreciating that hashes are used (this project included) for many different things, not all of which are directly affected by this break. Yes, this is a bad omen for the longevity of SHA-1 for other uses, so we will keep an eye on it. Something I am intrigued about is more sophiticated compositions of, say, SHA-1 and MD5. -kb
Current thread:
- Re: SHA-1 broken, (continued)
- Re: SHA-1 broken Denis Jedig (Feb 21)
- Re: SHA-1 broken Steve Friedl (Feb 17)
- Re: SHA-1 broken Jonathan G. Lampe (Feb 17)
- RE: SHA-1 broken Scovetta, Michael V (Feb 17)
- RE: SHA-1 broken Frank Knobbe (Feb 21)
- RE: SHA-1 broken Michael Silk (Feb 19)
- Re: SHA-1 broken exon (Feb 19)
- Re: SHA-1 broken Peter J. Holzer (Feb 21)
- Re: SHA-1 broken Brian May (Feb 19)
- Re: SHA-1 broken exon (Feb 19)
- Re: SHA-1 broken Michael Silk (Feb 19)
- Re: SHA-1 broken Anatole Shaw (Feb 19)
- Re: SHA-1 broken Michael Silk (Feb 19)
- Re: SHA-1 broken peeon+securityfocus (Feb 21)
- Re: SHA-1 broken Peter Jeremy (Feb 21)
- Re: SHA-1 broken Anatole Shaw (Feb 19)
- Re: SHA-1 broken securityfocus (Feb 19)
- Re: SHA-1 broken Damian Menscher (Feb 21)
- Re: SHA-1 broken Paul Johnston (Feb 21)
- Re: SHA-1 broken Michael Silk (Feb 21)
- Re: SHA-1 broken exon (Feb 21)