Re: SHA-1 broken

From: Michael Silk (michaelsilk_at_gmail.com)
Date: 02/18/05

  • Next message: Luigi Auriemma: "Multiple vulnerabilities in TrackerCam 5.12" 
    Date: Fri, 18 Feb 2005 17:06:42 +1100
To: "Scovetta, Michael V" <Michael.Scovetta@ca.com>, bugtraq@securityfocus.com

    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
    >
    >
    >

  • Next message: Luigi Auriemma: "Multiple vulnerabilities in TrackerCam 5.12"

    Relevant Pages

    • Re: Match GetHashCode between .NET 1.1 app and non-.NET app
      ... string that matches the hash that the same string returns from the .NET 1.1 ... Michael has replied with the algorithm, but it should be stressed that ... you *should not* rely on a hashcode being valid outside the environment ...
      (microsoft.public.dotnet.framework.clr)
    • This Weeks Finds in Mathematical Physics (Week 226)
      ... The first week they had lots of talks on "higher-dimensional rewriting", ... to find two files that give the same bit string. ... Now, if you're a mathematician, the whole idea of a cryptographic ... You can see the algorithm for this ...
      (sci.math.research)
    • This Weeks Finds in Mathematical Physics (Week 226)
      ... The first week they had lots of talks on "higher-dimensional rewriting", ... to find two files that give the same bit string. ... Now, if you're a mathematician, the whole idea of a cryptographic ... You can see the algorithm for this ...
      (sci.physics.research)
    • Re: Attention Sean - question about CSI
      ... the best compression algorithm you have. ... It should compress very ... which compresses that string to a single bit. ... from the binary code, and use it to decompress the data, then ...
      (talk.origins)
    • Re: Optimize an IEnumerable
      ... Though, personally it seems to me that unless you have a very specific need to reuse the enumeration in completely different places in the code, it might be better to just have the _client_ of the enumerator cache the results as needed. ... foreach (string someThingToFind in _list) ... That is, yes it has the potential for improving performance, but it doesn't really change the efficiency of the algorithm. ... A common one used for string searches such as yours would be a state machine implementation, where the nodes of the state graph are connected according to the letters in the search words. ...
      (microsoft.public.dotnet.languages.csharp)
    • Quantcast