Date: Sat, 19 Feb 2005 22:43:59 -0600 (CST)
From: peeon+securityfocus@...on.net
To: bugtraq@...urityfocus.com
Subject: Re: SHA-1 broken


The Research Summary was posted to Yiqun Lisa Yin's MIT site.

http://theory.csail.mit.edu/~yiqun/

Only 2 pages, maybe the 90 page paper is forthcoming.

-Joel

On Sat, 19 Feb 2005, Anatole Shaw wrote:

> 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@...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@...il.com]
>>> Sent:   Thu 2/17/2005 10:30 PM
>>> To:     Scovetta, Michael V; bugtraq@...urityfocus.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@...com]
>>>> Sent: Friday, 18 February 2005 8:34 AM
>>>> To: Kent Borg; Gadi Evron
>>>> Cc: bugtraq@...urityfocus.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@...g.org]
>>>> Sent: Wednesday, February 16, 2005 6:27 PM
>>>> To: Gadi Evron
>>>> Cc: bugtraq@...urityfocus.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
>>>
>>>
>>>
>

Powered by blists - more mailing lists