Slashdot Mirror

← Back to Stories (view on slashdot.org)

PGP Moving To Stronger SHA Algorithms

Posted by timothy on from the 511-upmanship dept.

PGP Corp. is moving to a stronger SHA Algorithm (SHA-256 and SHA-512) as consequence of the research conducted by the team at Shandong University in China who broke the SHA-1 algorithm. (See this earlier story for more information on the SHA-1 vulnerability.)

25 of 247 comments (clear)

  1. Not a solution by Esine · · Score: 4, Insightful

    They're just trying to avoid the problem, not solve it. Moving to SHA-512 is not a solution. :/

    1. Re:Not a solution by anothergene · · Score: 5, Insightful


      They're just trying to avoid the problem, not solve it. Moving to SHA-512 is not a solution. :/

      Could also be a stop gap solution. At least it will be harder to break in the mean time until a real solution is devised.

      --
      Who's leg do I have to hump to get a dry martini around here?
    2. Re:Not a solution by Anonymous Coward · · Score: 5, Insightful

      What, then, is?

      Moving to Tiger? Or Whirlpool? Or RIPEMD-160?

      The amount of effort it took to discover the weakness in SHA-1 was incredible, and SHA-256 and SHA-512 are even more complex. Tiger and Whirlpool are relatively untested, and RIPEMD-160 was put out as an update after the original RIPEMD was broken (Much like SHA-0).

      SHA-256 and SHA-512 are the most likely successors to the throne, because they're based on an algo that is STILL, despite being "broken", known to have very strong collision resistance.

    3. Re:Not a solution by Mr2cents · · Score: 4, Interesting

      Why not sign using two hashes? You'll need to find a chunk of data that generates two collisions with two different hashing algorithms. Let'em chew on that one!

      --
      "It's too bad that stupidity isn't painful." - Anton LaVey
    4. Re:Not a solution by CajunArson · · Score: 4, Informative

      I do see your point, but remember that you could argue the RSA is useless because if I did it over a 32 bit address space it's easy to prime-factorize any number and therefore increasing it to a 2048 bit space is "just avoiding the problem". As CPU power increases it becomes more economical to move to more complex hash/ecryption schemes over larger address spaces. And there's even good news: it's a hell of a lot cheaper for me to move my PC to a new SHA system than it will be to crack it, even with the algorithm issues.

      --
      AntiFA: An abbreviation for Anti First Amendment.
    5. Re:Not a solution by Dolda2000 · · Score: 4, Informative
      It's the same solution that's been used with RSA for ages. When 512-bit keys were broken, 1024-bit keys were recommended. Now when they're almost broken, 2048-bit keys are recommended. I hear that some are already recommending 4096-bit keys.

      There's no fool-proof "solution" to this problem. The key (no pun intended) is to keep a high enough ratio between hash length (or key length) and the kind of processing power that potential crackers (including the NSA) can be thought to have access to.

      Thus, as the processing power of the world increases, so do we increase the hash/key lengths. There's nothing strange about that, if you ask me -- especially considering how the required processing power increases exponentially with the hash/key length in use.

    6. Re:Not a solution by Anonymous Coward · · Score: 5, Informative
      As it turns out PGP (well, GPG) already has support for RIPEMD160 built in to it. To use this:
      gpg --clearsign --digest-algo RIPEMD160 foo.txt

      gpg -b --armor --digest-algo RIPEMD160 foo.tar.gz

      (First one: Clear signuatre; second one: detached signature)
    7. Re:Not a solution by uhoreg · · Score: 4, Insightful
      1. SHA-256 is not just SHA-1 with more bits; it's a different algorithm. So moving from SHA-1 to SHA-256 is not the same as moving from RSA-512 to RSA-1024. (However, moving from SHA-256 to SHA-512 would be.)
      2. RSA was never broken in the same way that SHA-1 is now (allegedly -- since the paper is not yet published) broken, or that MD5 is broken. SHA-1 is broken in the sense that the researchers were able to find a collision in much less than the expected 2^80 calculations. This indicates that the algorithm is weaker than previously believed, and may soon result in much quicker attacks. RSA-512 is broken because computing power has caught up with it, and it's possibly economical to build a computer that can crack 512-bit RSA keys. Weaknesses that are solely due to key/hash size may be fixed by switching to a larger size. Weaknesses that are inherent in the algorithm may not be able to be fixed in this way.
      --

      To get something done, a committee should consist of no more than three persons, two of them absent.

  2. Why only small improvements in security? by ABeowulfCluster · · Score: 5, Funny

    I think I'll wait for the SHA-65000 algorithm instead.. it'll be harder to crack.

  3. Come on... by debilo · · Score: 4, Informative

    ... who broke the SHA-1 algorithm.

    They did not break it. They just found a way to reduce the number of trials needed to find a collision.

    1. Re:Come on... by no+parity · · Score: 5, Insightful
      They did not break it. They just found a way to reduce the number of trials needed to find a collision.

      That is what's usually referred to as "breaking" a hash algorithm.

    2. Re:Come on... by octaene · · Score: 4, Informative

      Finally, someone who has a clue! no parity is absolutely right. All they did was provide a hash that produces 1 collision as a proof that they have an algorithm that makes finding collisions easier. This doesn't mean we all need to rush out and change our public/private keys...

    3. Re:Come on... by menscher · · Score: 4, Informative
      All they did was provide a hash that produces 1 collision

      No, they didn't. No hash has been produced. Only a claim that they can do it in 2^69 operations. The collisions they gave were for SHA-0 and for a reduced-round version (58 rounds instead of 80) of SHA-1. Unless someone can extend the break (which is likely) then it's still quite secure.

    4. Re:Come on... by Anonymous Coward · · Score: 4, Insightful

      Okay, even if you can find a collision in, say, a day... Great. You can find a collision in a day. But how many collisions will you have to sort through before you find one that even resembles a will, especially one that, say, gives all your property to me?

      Oh, sure, lots. But if the SHA-1 is being used for, say, passwords - where all that's stored and checked is the hash - then ANY collision will do. So if you can find a collision in a day, you can break into any system using SHA-1 for password authentication in a day.

      That's broken.

    5. Re:Come on... by abelsson · · Score: 4, Interesting

      Bruce Schneier estimates that a SHA-1 collision finding machine, built along the same lines as the old DES cracker would cost $25M-$38M and could do the needed 2^69 calculations in 56 hours. distributed.net has already completed a 2^64 operation challenge a few years ago, which along with Moores law puts 2^69 ops into the realm of the possible.

      Fighting the FUD, indeed.

    6. Re:Come on... by kiltedtaco · · Score: 4, Informative

      MD5 and SHA-1 are both iterated hashes. They work by take one block, hash it, then use the output from that round as the IV for hashing the next. This allows a curious sort of failure:

      The attack on MD5 worked independently from the initial state of the cipher, i.e., any arbitrary message could be prepended to the calculated collision, and the hashes would still collide. It doesn't matter what the text before the discovered collision block is. It could be anything (plus padding to make it to a multiple of the block length.)

      This makes the break a much more serious problem than simply finding two completely random messages that happen to have the same hash. It's only a guess at the moment, but I assume the SHA-1 attack will work the same way. The brief findings mentioned using the same sort of attack, hopefully the results will be similar.

      (Side note 1: The term used by every cryptographer i've ever encountered is "break". Feel free to use what you want, but don't claim that "break" is for some reason incorrect. If you want to argue about it, see my prior post on "Stealing" vs. "Copyright Infringement.")

      (Side note 2: Even if one was going to brute force SHA-1, you would still get the same failure mode as described. When trying all the possible hashes, you would simply use the output of SHA1 of the nefarious file as the IV in the brute-force attack. Iterated hashes, in my very uneducated opinion, are on their way out. What they will be replaced with, however, I have no idea. )

  4. Why not move sooner? by }InFuZeD{ · · Score: 4, Insightful

    Is there a reason to wait until someone breaks the existing algorithm before moving to a stronger one?

    It seems to me that if you start working on implementing the stronger ones BEFORE your existing one is broken?

    An ounce of prevention...

  5. Re:Bah. by WombatDeath · · Score: 4, Funny

    Same here, though I apply it twice for additional security. Can't be too careful...

  6. I don't think they've officially decided to change by papercut2a · · Score: 4, Informative

    There's a discussion about this very subject going on on the IMC's discussion list for OpenPGP. From reading the posts, particularly the ones by PGP's Jon Callas, I don't think that PGP has officially decided to implement this change just yet. (On the list, the thread titled "SHA-1 broken" is the one you will want to follow.)

    But then, I could have missed something.

  7. SHA-1 break illustrated.. by __aaijsn7246 · · Score: 5, Interesting

    http://lists.gnupg.org/pipermail/gnupg-users/2005- February/024862.html

    Atom Smasher atom at smasher.org
    Wed Feb 16 21:56:25 CET 2005

    Hash: SHA256

    this should help put the (alleged until proven otherwise) SHA-1 break into
    perspective. thanks to Sascha Kiefer for giving me the idea.

    let's say that unbroken SHA-1 represents a 100 meter (328 ft) wall. if a
    break allows a collision to be found in merely 2^69 operations (on
    average), that would mean the wall has crumbled to 4.9 cm (1.9 in) tall.
    that's broken!!

    OTOH, let's say that unbroken MD5 represents a 100 meter (328 ft) wall.
    comparing unbroken MD5 to broken SHA-1 means the wall would actually grow
    from 100 meters (328 ft) tall to 3.2 km (1.99 miles) tall. SHA-1, even if
    it's broken enough to find a collision in 2^69 operations (on average), is
    still stronger than MD5 was ever meant to be.

    again, using unbroken MD5 as our reference of a 100 meter (328 ft) wall,
    unbroken SHA-1 would be a wall 6553.6 km (4072 miles) tall. SHA-1 was
    intended to be incredibly stronger than MD5.

    - -- ...atom

  8. Re:What about GPG? by papercut2a · · Score: 5, Informative

    IIRC, GPG already allows SHA-256 and SHA-512, but doesn't default to them.

  9. Re:Bah. by God!+Awful+2 · · Score: 4, Funny

    Who needs fancy things like PGP? I encrypt all my sensitive data in ROT-13, and it hasn't been cracked yet!
    Are ROT-13 jokes still +1 funny?

    I thought we had moved past ROT-13 and ROT-26 and you had to posit ROT-39 or up in order to get a rise out of people.

    -a

    --
    /. users can't
  10. Re:i'm no crypto expert... by Sweetshark · · Score: 4, Insightful

    but why not take a hash of a hash ?
    Because breaking the hash means finding two documents resulting in the same hash. If the first hash ist the same for both documents all hashes of hashes will be the same too.
    What you could do is using different hash-algos, but it increases the amount of code to be managed and reviewed thoroughly (security by obscurity rarely works). And it increases the size of the digest - SHA-256 does that too but it keeps the algorithm simple.

  11. Re:What about GPG? by papercut2a · · Score: 5, Informative

    Just to confirm, GPG 1.4 DOES support the more-bits versions of SHA. Run GPG with the --version parameter to get something like this for your copy:

    Supported algorithms:
    Pubkey: RSA, RSA-E, RSA-S, ELG-E, DSA
    Cipher: 3DES, CAST5, BLOWFISH, AES, AES192, AES256, TWOFISH
    Hash: MD5, SHA1, RIPEMD160, SHA256, SHA384, SHA512
  12. Missing details to complete the perspective by mukund · · Score: 4, Insightful

    Adding to what you've said, if the cumbled SHA-1 wall is 4.9 cm (1.9 in) tall, our current average reach of scaling the wall is still a few nano metres.

    It appears as if that 4.9 cm wall is very scalable, but it still isn't easily scalable.

    Quoting Bruce Schneier's quote of what Jon Callas, PGP's CTO said: "It's time to walk, but not run, to the fire exits. You don't see smoke, but the fire alarms have gone off."

    --
    Banu