Follow Slashdot stories on Twitter

 


Forgot your password?
Close
typodupeerror
×
Encryption Security

New, Faster Attack against SHA-1 Revealed 298

Posted by CowboyNeal from the not-so-safe-anymore dept.
VxSote writes "According to Bruce Schneier's blog, a team of Chinese cryptographers has announced new results against SHA-1 that speed up the time required to find collisions compared to their previously published attack. Schneier says that a SHA-1 collision search is now 'squarely in the realm of feasibility,' and that further improvements are expected."
This discussion has been archived. No new comments can be posted.

New, Faster Attack against SHA-1 Revealed More

New, Faster Attack against SHA-1 Revealed

Comments Filter:

  • Is that the attack... (Score:5, Funny)

    by RevDobbs ( 313888 ) * on Thursday August 18, 2005 @06:37PM (#13351887) Homepage
    Is that the same attack the chinese exchange student used in Lineage II?

  • The world is collapsing around me! (Score:5, Funny)

    by frinkacheese ( 790787 ) * on Thursday August 18, 2005 @06:38PM (#13351899) Journal
    Next there will be massive ASIC machines crunching your PGP ciphertext and nobody will be able to proove anything until Lt Cmdr Data comes up with another Fractal Encryption algorythm that even the Borg cannot break.

  • oh God bless them, those kooky spookies (Score:5, Funny)

    by peculiarmethod ( 301094 ) on Thursday August 18, 2005 @06:38PM (#13351900) Journal
    I repeat the saying I've heard comes from inside the NSA: "Attacks always get better; they never get worse."

    And THAT kind of forward thinking, gentlemen, is why we're number one over here in the good ol' U.S. of A. So glad we spend money in all the right places.
    • Is that why a team from CHINA are the ones making this discovery?

      /From the USA :)

      • Re:oh God bless them, those kooky spookies (Score:5, Informative)

        by Anonymous Coward on Thursday August 18, 2005 @06:51PM (#13351971)
        The NSA doesn't release its finding about new attacks against encryption algos. They use the info to crack and keep secure. Promote AES as a standard, and have a decades worth of research about useful attacks against AES that no-one knows about but the NSA.

        Like public-key encryption. People in Britain discovered it first, but kept the research secret.
        • LOL, yea...

          If there exists a flaw, it does not matter that we are the only ones that know about it. Sooner or later one of US is going to sell it.

        • Well that would assume a few things (Score:5, Insightful)

          by Sycraft-fu ( 314770 ) on Thursday August 18, 2005 @10:25PM (#13352911)
          #1) That the NSA has better cryptologists than everyone else. Remember AES was widely reviewed before becomming an accepted standard, and not just by US researchers. Top experts from all over the globe looked at it, an decided it was secure. So for the NSA to know a weakness, means that they have experts beyond all others combined.

          #2) They are very ballsy, and very certian that no one will find those exploits. The US government uses AES for secret and top secret data. It would be amazingly arrogant to know how to crack the crypto, and yet to still use it for the most secure documents.

          #3) They are willing to trust that the authors, two foriegners (Dr. Daemen and Dr. Rijmen are Belgian) were unaware of this exploit. Remember that if an exploit was found, it is always possible the authors knew, and intended that they'd be able to use it.

          It thus seems EXTREMELY unlikely that the NSA would know of a crack for AES and simply be sitting on it. It would put a great deal of incerdibly sensistive government data at risk, as well as US economic intrests.

          No, what seems far more likley is that the US government came to the realization that strong crypto is widely available outside the US, and thus is makes no sense to try and restrict it from the public as it would only serve to give other nations an advantage.

          So no, I don't believe AES is strong because the NSA is strong, though I respect their opinon to a great degree, I believe it's strong because the world cryptography community believes it is.

          To date there have been two proposed attacks. One is called the XSL attack. It's not an actual break, simply something that would in theory make it easier to brute force, but still well out of the realm of possibility. More, the math behind it is suspect, it may not even be workable at all. Then there was teh cache timing attack. It does work, but required a special SSL server that gave out as much timing information as possible, and 200 million known plaintext bytes. Nifty, but not practical in the real world.
          • that what we WANTED you to think!

            - NSA
            PS. pwned
          • 1) When DES came out, academia were demonstrably at least 20 years [schneier.com] behind the NSA in terms of cryptographic skills.

            2) I'm impressed that you know what they use for top secret data - do you have any references for that? I'd note that, if USA top-secret data were encrypted by a different system, the NSA might well decide it was worth the risk of AES being cracked to be able to read their enemies' data.

            3) If the authors, on their own, were capable of finding a break then their work would most likely have
      • Heh heh, we wish the team from CHINA were the discoverers. What they really are is the _publishers_.
      • The NSA already said that people should stop using SHA-1 in favor of other methods. It can be assumed they already knew about attacks.
    • Yeah but us Brits cracked Enigma, no matter what Holly Wood would have y'all believe.

      OK so thats bait.

  • Big deal (Score:5, Funny)

    by That's Unpossible! ( 722232 ) * on Thursday August 18, 2005 @06:40PM (#13351914)
    All they did was look for a near-collision
    differential path which has low Hamming weight in the "disturbance vector" where each 1-bit represents a 6-step local collision. Then they simply adjusted the differential path in the first round to another possible differential path so as to avoid impossible consecutive local collisions and truncated local collisions. Then obviously the final step taken was to transform two one-block near-collision differential paths into a twoblock
    collision differential path with twice the search complexity.

    Duh...

  • Now can we panic? (Score:4, Funny)

    by John.P.Jones ( 601028 ) on Thursday August 18, 2005 @06:41PM (#13351915)
    Alas poor SHA-1, I knew him...

    Okay so we still have SHA-256 and SHA-512 but can we really feel good about them?

    Wanted: One reliable hash...

    • Re:Now can we panic? (Score:5, Funny)

      by MightyMartian ( 840721 ) on Thursday August 18, 2005 @06:55PM (#13351989) Journal
      Commit everything to memory, keep a cyanide pill close by and hope like hell that that crazy guy with the tinfoil hat is wrong.

      • Commit everything to memory, keep a cyanide pill close by and hope like hell that that crazy guy with the tinfoil hat is wrong.

        Buddy, if you're keeping that cyanide pill close by, the guy with the tinfoil hat isn't the only crazy one. You might as well label yourself correctly and put your own tinfoil hat on.

      • Commit everything to memory, keep a cyanide pill close by and hope like hell that that crazy guy with the tinfoil hat is wrong.

        You do know he's wearing that hat so people can't read his mind right? Maybe your memory isn't the safest place to store things.

    • Wanted: One reliable hash...

      I know of one. It has a problem with snack collisions though... or rather, the user has a problem with snack collisions. ;)

    • Re:Now can we panic? (Score:3, Interesting)

      by Ckwop ( 707653 ) *
      Whirlpool. It's based on the mathematics that gives AES it's proofs of security against certain classes of attack.

      It's slower than SHA-1 but guess what? Security costs CPU cycles. A lot of people tend to forget this most important lesson.

      Simon.

  • Two questions... (Score:3, Interesting)

    by meditation_dude ( 907877 ) on Thursday August 18, 2005 @06:47PM (#13351939) Homepage
    One is, is this really relevant when most terrorist threats these days are so low tech? Two, does anyone know what kind of funding the NSA gets these days? I remember a news report a couple years back that said they were deeply out of date with hardware and so forth.

    • Re:Two questions... (Score:5, Insightful)

      by Anonymous Coward on Thursday August 18, 2005 @07:12PM (#13352080)
      I think that the greatest threat in this case is not terrorists but the institutions such as government and security forces. Terrorists have a great interest in keeping their own transmissions secure but little interest in the communications of others.

      Their tagets are soft, security is fairly low and information can be obtained using people on the street.

      Counterintelligence is a game played by large beauracracies who are at peace at the moment but would really like not to be. It involves the use of large ammounts of resources for the main purpose of maintaining the status quo. Terrorists are not interested in the status quo, they want things to change.

    • Two, does anyone know what kind of funding the NSA gets these days? I remember a news report a couple years back that said they were deeply out of date with hardware and so forth.

      Come on. You know that report was a plant!

      --Rob

  • Few Details? No report? No paper? (Score:5, Insightful)

    by hoka ( 880785 ) on Thursday August 18, 2005 @06:50PM (#13351960)
    I mean, I'm sure that these guys are the real thing, judging by their past experience breaking SHA-1 and how much notoriety they have. But they have been inconsistent with presenting information. It would be nice to see something thats really solid with information rather than what looks at best like a bit of speculation. Last I checked information on their last attack (2^69) was still pretty thin and I suppose its time to move on to SHA-256 anyways.

  • Security (Score:5, Funny)

    by bredk ( 838817 ) on Thursday August 18, 2005 @06:56PM (#13351999)
    I've just changed away from using SHA-1. Double ROT13 seems most appealing these days. ;)

  • Crypto is an evolutionary process (Score:4, Interesting)

    by Crixus ( 97721 ) on Thursday August 18, 2005 @07:02PM (#13352030)
    Things like this are inevitable. Crypto is an evolving science, and this kind of thing is healthy.

        I for one am very excited about the future of crypto.

  • RFC4109 (Score:5, Interesting)

    by fwr ( 69372 ) on Thursday August 18, 2005 @07:19PM (#13352108)
    I wonder how this will effect RFC 4109 [x42.com] in that it depreciates MD5 in favor of SHA1. Does this mean that SHA1, at 2^63 is less secure than MD5 at a brute-force 2^64? I'm not a crypto expert or anything, just asking the question; will this effect the proposed standard for the HASH algorithm used in IPsec?
    • TFA says that it holds implications for IPsec, and a number of other algorithms that depend on SHA-1.

      Now, this SHA-1 attack is 2^63 complexity, but this is orders of magnitude less than the 2^80 brute force.

      Now, what makes you think that there isn't a faster MD5 attack than just the plain brute force 2^64? Assuming a relative number of orders of magnitude, we're talking around 2^50 or so complexity for an MD5 hash attack.

    • Re:RFC4109 (Score:4, Informative)

      by mre5565 ( 305546 ) on Thursday August 18, 2005 @09:43PM (#13352754)
      I wonder how this will effect RFC 4109 in that it depreciates MD5 in favor of SHA1. Does this mean that SHA1, at 2^63 is less secure than MD5 at a brute-force 2^64? I'm not a crypto expert or anything, just asking the question; will this effect the proposed standard for the HASH algorithm used in IPsec?
      First there are already attacks on MD5 that are less than O(2^64) which don't involve brute force.

      Second, RFC 4109 refers to the HMAC algorithms used for computing per packet integrity checksum that is resistant to tampering by a man in the middle. HMACs take as input both a known message and a shared secret (often, a session key for a symmetric key algorithm like DES, triple DES, AES, RC4, etc) and compute hash result ( MD5, or SHA1, or SHA-256, etc. ). In other words, part of the input to the hash algorithm is unknown. This makes it very difficult to find two messages, X and Y that compute the same HMAC. I.e. find X and Y such that HMAC(X, K) == HMAC(Y, K), where K is the shared secret. The attacks on MD5 and SHA-1 so far assume that there is no K, or if there is, it is known. And if the man in the middle knows K, he doesn't need to use these new cool attacks to tamper with messages; he's the man in the middle, he just tampers and re-computes the HMAC with far less computational overhead.

      I've see no indication in Schneir's blog entry that these attacks break HMACs.

      That said, it is surprising that SHA-256 wasn't added to the MUST list for RFC4109, given that when this RFC was published, it was known that SHA1 had be shown to be vulnerable to attacks of less than O(2^69). But then again, the RFC also mentions AES128 as MUST, but not AES256. Odd.

  • Solution? (Score:2, Insightful)

    by Phil246 ( 803464 )
    Im no expert but wouldnt using several different hashes on the same file be better?
    Sure you could get a hash collision in one or more of them but getting the collision to happen in all would be somewhat more tricky no?

    • Re:Solution? (Score:4, Insightful)

      by Krach42 ( 227798 ) on Thursday August 18, 2005 @07:43PM (#13352212) Homepage Journal
      This is no better than increasing the hash key size. In fact, it's worse than increasing the hash key by the same.

      If you take hash algo A at 32 bits, and algo B at 32 bits, but B is weaker than A, then hash collision calculation would be less than the complexity of A squared. (Since B is weaker than A)

      If instead you double the hash size of A to 64 bits, then your collision calculation would be the square of the complexity of A at 32.

      So, combining MD5 with SHA-1 could cause some problems, with both of them having weaknesses, neither is going to provide you much protection, even if you use them together.

      If you built a safe out of paper and cardboard. Sure such a safe would, yes, be better than one made of just paper, or just cardboard, but it's still not better than a safe built out of two cardboard sheets.

      Ideally, you don't want to build a safe out of either.

    • Re:Solution? (Score:3, Interesting)

      by acidblood ( 247709 )
      Look up Joux's construction for breaking concatenated hashes. Concatenated hashes are only as strong as the strongest among them, whereas you would expect that the concatenation of an n-bit hash with an m-bit hash would provide (n+m)-bit security.

      Although I'm not sure how these shortcut collision attacks fit in Joux's construction -- my recollection of it was that it was useful for collision search using the birthday paradox.
  • Anyone know for sure whether the SHA-1 attack also will compromise SHA-256? I've seen conflicting reports.
    How about RIPEMD? Anyone using it seriously?
    • RIPEMD is in the SHA/MD5 family and if this attack is like previous ones it can probably be extended to any algorithm in that family with some significant effort.

      At the moment, Tiger and Whirlpool seem to be the only hash algorithms outside of the family that haven't been successfully attacked. I'd go with Whirlpool, personally.
    • The old RIPEMD was announced broken at the same time as the attacks on MD5 etc. There have been no attacks announced either for the new RIPEMD-160 hash and related variants, or for the longer SHA-2 variants (SHA-224, SHA-256, SHA-384, and SHA-512).

      All these hashes are in the same family, but it's not clear at present how likely it will be that attacks will be found on the longer RIPEMD/SHA variants.

  • Anonymous "team of Chinese cryptographers" (Score:5, Insightful)

    by clap_hands ( 320732 ) on Thursday August 18, 2005 @08:07PM (#13352330) Homepage
    Have you ever noticed how you never hear the names of these Chinese researchers...Professor Xiaoyun Wang and her colleagues (for SHA-1, Yiqun Lisa Yin and Hongbo Yu) have broken the greater share of the popular hash functions: MD4, MD5, SHA-0, SHA-1, RIPEMD...and the only name that gets mentioned is "Bruce Schneier reports that Chinese cryptographers...". Not to belittle Schneier, but what these anonymous "Chinese cryptographers" have achieved is exceedingly significant in the field of cryptography, and the least we can do is mention their names occasionally, right?

    Even if they are unpronouncable ;-)

  • So tell me : should I stop using SSHA to store password hash ?
    • Depends if it's your hotmail password, then no. if it's the passphrase on your private key on a server with millions of dollar's worth of transactions then yes. Going forward, I wouldn't use them (MD5 or SHA-1) for anything resembling security anymore

  • Dumb question (Score:3, Funny)

    by XorNand ( 517466 ) * on Thursday August 18, 2005 @08:15PM (#13352350)
    Let's say I take a binary file and I grab both it's MD5 and SHA1 hashes. I then combine the output of those two into one really long string. Them I take the SHA1 hash of that string. How secure is this?
    • Hard to say, but it'd be harder than either of MD5 or SHA-1 on their own. But there's no point in taking the SHA-1 of the string the second time, if you're trying to avoid the collision attacks. This is because if it's collided before the second SHA-1, it'll collide after, right?
    • Let's say I take a binary file and I grab both it's MD5 and SHA1 hashes. I then combine the output of those two into one really long string. Them I take the SHA1 hash of that string. How secure is this?

      Afaik all attacks against MD5 and SHA1 are not "post-image" attacks. That is, the acttacker can generate two hashes with different data but with same hash, but not take existing data and generate new data with same hash.

  • Visa problems for the authors (Score:5, Informative)

    by clap_hands ( 320732 ) on Thursday August 18, 2005 @08:44PM (#13352474) Homepage
    Two of the Chinese researchers (Xiaoyun Wang and Hongbo Yu) were due to present their SHA results at the CRYPTO 2005 conference in the US, but were denied visas in time to attend. Adi Shamir (the A in RSA) ended up announcing this latest result on their behalf.
          http://cipher-text.blogspot.com/2005/08/visas-for- chinese-crypto-researchers.html [blogspot.com]

    • Re:Visa problems for the authors (Score:5, Informative)

      by clap_hands ( 320732 ) on Thursday August 18, 2005 @08:50PM (#13352492) Homepage
      Oh, I must be tired: Shamir is, of course, the *S* in RSA. Crikey.

  • SHA-1 is still good for a lot of applications (Score:5, Interesting)

    by greenrom ( 576281 ) on Thursday August 18, 2005 @10:05PM (#13352835)
    While this finding definitely shows a weakness in the SHA algorithm, it isn't a weakness that makes most applications that use SHA any more vulnerable. They found a way to generate two texts that produce the same hash using an algorithm with a time complexity of 2^63 instead of 2^80 as would be required for a brute force attack. However, being able to generate two texts that produce the same hash won't help you exploit most systems that rely on SHA. If someone finds a way to generate text that produces a SPECIFIED hash in 2^63 time, then there's reason to be concerned. However, since these findings show that SHA-1 has some weaknesses, it's probably time to start looking for a better hashing algorithm before a more serious vulnerability is found.

  • "Freeform" collision (Score:5, Interesting)

    by Gadzinka ( 256729 ) <rrw@hell.pl> on Friday August 19, 2005 @01:36AM (#13353525) Journal
    What no one seems to mention is that their attack finds "freeform" collisions. I mean, they go and find two plaintexts with the same hash. I wouldn't worry about it until they find 2^63 attack against given plaintext/hash.

    You can read about the distinction in Birthday Paradox article on Wikipedia [wikipedia.org]. In short, when the difficulty of finding collision against a given message is 2^n, the difficulty of finding any two colliding plaintexts is 2^(n/2).

    So, while they may have found 2^63 attack against SHA-1, it is still a "birthday attack" [wikipedia.org], and to find collision against my message signed with sha-1 the attack would still be 2^126.

    Or did I miss something?

    Robert

Slashdot Top Deals

To be awake is to be alive. -- Henry David Thoreau, in "Walden"

Close