RE: SHA-1 broken

From: Scovetta, Michael V (Michael.Scovetta_at_ca.com)
Date: 02/17/05

  • Next message: Martin Pitt: "[USN-78-2] Fixed mailman packages for USN-78-1"
    Date: Thu, 17 Feb 2005 16:34:15 -0500
    To: "Kent Borg" <kentborg@borg.org>, "Gadi Evron" <gadi@tehila.gov.il>
    
    

    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: Martin Pitt: "[USN-78-2] Fixed mailman packages for USN-78-1"

    Relevant Pages

    • Re: This Weeks Finds in Mathematical Physics (Week 226)
      ... Yeah, I said SHA-1 and MD5 are different, and I said they were both vulnerable ... Attacking hash functions by poisoned ... where Ldenotes the length of the axiom system A, ...
      (sci.physics.research)
    • Re: Re-secured Algorithm?
      ... >>MD5 collisions are actually trivial to generate. ... SHA-1 had real collisions in MD5. ... Personal attacks aside I doubt many ...
      (sci.crypt)
    • Re: Crypto Hash functions
      ... crypto-hash functions were "broken". ... MD5: ... SHA-1: wounded but still fighting. ... If you're signing bulk data, probably SHA-256 is your best bet. ...
      (sci.crypt)
    • Re: Crypto Hash functions
      ... crypto-hash functions were "broken". ... MD5: ... SHA-1: wounded but still fighting. ... If you're signing bulk data, probably SHA-256 is your best bet. ...
      (sci.crypt)
    • RE: sha-1 cryptography
      ... MD5 and SHA-1 are not used to ensure Confidentiality, ... the confidentiality of passwords or credit card numbers or the ... Computer Emergency Response Teams, and Digital Investigations. ...
      (Security-Basics)