Want to read Slashdot from your mobile device? Point it at m.slashdot.org and keep reading!

 



Forgot your password?
typodupeerror
×
Encryption Security IT

SHA-1 Broken 751

Nanolith writes "From Bruce Schneier's weblog: 'SHA-1 has been broken. Not a reduced-round version. Not a simplified version. The real thing. The research team of Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu (mostly from Shandong University in China) have been quietly circulating a paper announcing their results...'" Note, though, that Schneier also writes "The paper isn't generally available yet. At this point I can't tell if the attack is real, but the paper looks good and this is a reputable research team."
This discussion has been archived. No new comments can be posted.

SHA-1 Broken

Comments Filter:
  • Sigh (Score:5, Funny)

    by Anonymous Coward on Tuesday February 15, 2005 @11:26PM (#11685458)
    And I just got done upgrading from MD5.
    • Re:Sigh (Score:5, Funny)

      by dasunt ( 249686 ) on Tuesday February 15, 2005 @11:34PM (#11685544)

      About a month ago, I needed a mechanism for password hashes.

      After some research, I decided that SHA1 was more secure than MD5.

      So I hunted down some good public domain SHA1 code, read through it, and added it to my code.

      Thanks /.!

      • Re:Sigh (Score:3, Insightful)

        by ottothecow ( 600101 )
        Well, without /. they would be quietly circulating a paper on how to break your hashes and it would still be quiet.

        Maybe its easier to upgrade from SHA1 than it was from MD5.

      • A mechanism to find collisions does not affect SHA-1's strength as a password hashing algorithm or its use in a hashed message authentication code. So you'll be just fine.
        • Re:Sigh (Score:4, Funny)

          by Frymaster ( 171343 ) on Wednesday February 16, 2005 @12:23AM (#11685896) Homepage Journal
          -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1

          A mechanism to find collisions does not affect SHA-1's strength as a password hashing algorithm or its use in a hashed message authentication code. So you'll be just fine.Z

          really? well, i'm not the real frymaster. what do you say to that?

          -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.2.4 (Darwin) iD8DBQFCEsqV7Kzi+hL3je0RAl7iAJ41SsgjgwMvrS5+1OLLYp pYkXUPOgCgzSQS c42DLVAjebLYs2VTPkT/iIc= =8699 -----END PGP SIGNATURE-----

          • Re:Sigh (Score:5, Insightful)

            by Frobnicator ( 565869 ) on Wednesday February 16, 2005 @01:19AM (#11686181) Journal
            Yes, they found a way to break the hash function. But as the parent said, it does not mean it's suddenly invalid. Sure, the group found a way to break the algorithim, but look at According to TFA a collision can be found in about 2**69 hash operations. That's 590295810358705651712 attempts before they can find a match, as opposed to the 2**80 (1208925819614629174706176) that was expected before the paper. While the paper means it is orders of magnitude less work, it still means a lot of work for the attacker. Lets look at two relevant examples: disc images and passwords. Lets say I have an ISO disk image. I hack it, and want to modify some of the 'junk' bits using their algorithm. I'd still need to perform 590295810358705651712 hash operations on that image. Computing the hash of a disc is a slow operation. That's not something I could do in a day, week, or even a few months. Perhaps if I had a massivly parallel computer available, I could do it, but not as an individual. For a password, hopefully your system would lock the account long before there are that many failed login attempts. However, if your attacker has that kind of resources, you can assume it is feasable for them to find a hash collision. That's really only significant for governments, multi-national organizations, and other major enterprises, but not for most people.
            • Re:Sigh (Score:5, Funny)

              by B3ryllium ( 571199 ) on Wednesday February 16, 2005 @02:03AM (#11686401) Homepage
              You do realize, of course, that the recent preponderance of IRC-controlled botnets and such could easily be applied to a computational challenge such as this?

              Imagine tens of thousands of way-overpowered virus-infected 3Ghz Dell machines chewing threw the data?

              Then imagine a beowulf cluster of those.
              • Re:Sigh (Score:4, Informative)

                by mlyle ( 148697 ) on Wednesday February 16, 2005 @06:40AM (#11687246)
                OK, and then let's do some math.

                Let's say you have 2^20 (1048576) machines. Let's say each can do 2^20 hashes per second (this is optimistic). Then it will take you 2^29 seconds to find a hash collision-- this is about 17 years.

                This doesn't even let you collide with an arbitrary thing-- rather, you can provide something to someone to sign, and have another message that hashes to the same thing.

                It is worrisome, though, because perhaps attacks will improve and it'll continue to get cheaper.
            • Re:Sigh (Score:4, Informative)

              by Craigj0 ( 10745 ) on Wednesday February 16, 2005 @04:28AM (#11686872)
              For a password, hopefully your system would lock the account long before there are that many failed login attempts. However, if your attacker has that kind of resources, you can assume it is feasable for them to find a hash collision. That's really only significant for governments, multi-national organizations, and other major enterprises, but not for most people.

              That is not how it works. THey are using the birthday paradox, that is why brute force is 2^80 not 2^160. Put simple the birthday paradox finds two pieces of data with the same hash. It does NOT (as so many posts believe) allow you to find a matching hash to a fixed piece of data. (This would take 2^160, perhaps less with the weaknesses discovered but not close to 2^69). Hence this does not allow you to break passwords.
            • Re:Sigh (Score:4, Informative)

              by hobbicik ( 229710 ) on Wednesday February 16, 2005 @04:35AM (#11686899)

              Lets say I have an ISO disk image. I hack it, and want to modify some of the 'junk' bits using their algorithm. I'd still need to perform 590295810358705651712 hash operations on that image. Computing the hash of a disc is a slow operation. That's not something I could do in a day, week, or even a few months. Perhaps if I had a massivly parallel computer available, I could do it, but not as an individual.

              No need to compute the hash of a whole disc. You can calculate the internal state of SHA-1 after processing the whole image except - lets say - the last kilobyte (you do it ONCE) and find a collision by modifying only this last kilobyte with great chance of succeeding. There are 2^8192 variants of the last kilobyte, but only 2^160 variants of the hash - that's why you'll probably succeed.

      • Not a problem (yet) (Score:5, Informative)

        by Spy Hunter ( 317220 ) on Tuesday February 15, 2005 @11:52PM (#11685701) Journal
        For password hashes this attack shouldn't be a problem, if it is as described in the article. The attack does only one thing: allows an attacker to generate two streams of data which hash to the same value. This is a problem for digital signatures, because somebody can sign one data stream, then distribute another with the same signature. So the signature doesn't guarantee the data has not been modified. However, this attack does not allow an attacker to magically deduce your password from its hash, or even generate another password that would hash to the same value as yours. So you don't need to immediately jump up and replace SHA-1 wherever you use it.

        OTOH, this attack indicates that other types of attacks may be found sooner than was previously thought. So it is still a good idea to move away from SHA-1 in the medium to long term. Though it's not entirely clear what you should move to. And it is not certain that more attacks will be found soon.

        • by gnuman99 ( 746007 ) on Wednesday February 16, 2005 @12:51AM (#11686048)
          Of course you can make

          SHA1(data1) == SHA2(data2) where data1!=data2

          because SHA1 maps from a large space to 160bits. There WILL be collisions for any maping like that. The question is can you make,

          SHA1(data1)==SHA2(data2) && data1.length==data2.length) ?

          Can you make the length of the hashed data to be equal?

          If you cannot, then most of the signed hashes cannot be compromised anyway.

          • by interiot ( 50685 ) on Wednesday February 16, 2005 @01:39AM (#11686284) Homepage
            Adding data2.length to the check is basically just increasing the number of bits used for the hash (and thus reducing the number of chunks of data that hash to the same value, and increasing the amount of time required to find a collision). However, length turns out to be a very poor thing to hash on (non-linearity is prized in hash functions, and you can't much more linear than the length function). If you're going to set aside more space for a hash value, it's better to use a longer hash or multiple hashes together.
          • by yppiz ( 574466 ) on Wednesday February 16, 2005 @01:40AM (#11686291) Homepage
            Even adding the length restriction, you are still mapping from a large space (the space of all binary strings of length n > 160) to a small space (the space of all binary strings of length 160), so there will still be collisions.

            --Pat / zippy@cs.brandeis.edu
      • by Zeinfeld ( 263942 ) on Wednesday February 16, 2005 @03:58AM (#11686792) Homepage
        After some research, I decided that SHA1 was more secure than MD5.

        MD5 was 'broken' in 1995 by Hans Dobbertin who discovered compressor function collisions. It was almost another 10 years before the compressor function collisions were turned into an attack which produced hash collisions.

        So there is a serious security problem here but it does not mean that everything that uses SHA-1 is now vulnerable. There are many applications where MD5 is completely adequate. If you have a really good reason to do so and a really good understanding of the security requirements and risks you can use even something like MD2.

        Today paul Kocher complained that Microsoft was using MD5 in its anti-spyware to identify known bad software. This is not actually a major problem, much worse would be using MD5 to identify known good software to keep, that is when a collision would bite. For known bad programs well i don't want any variant of the program to run...

        But if you are writing an entirely new application then use SHA-256 or SHA-512, more rounds, more bits.

        Meanwhile we need to research some new hash functions pronto.

  • by Hulkster ( 722642 ) on Tuesday February 15, 2005 @11:27PM (#11685462) Homepage
    For those interested, here is the actual detailed/lengthy FIPS PUB 180-1 from NIST, [nist.gov] as typical, Wikipedia has a nice summary, [wikipedia.org] and the W3 Folks [w3.org] have a short snippet ...
    • by interiot ( 50685 ) on Tuesday February 15, 2005 @11:34PM (#11685541) Homepage
      So SHA-1 was created by the NSA, and was broken nine years after it was released. Is there any chance that the NSA knew it had a secret weakness, and promoted it for that specific reason?
      • Re: (Score:3, Insightful)

        Comment removed based on user account deletion
        • by Anonymous Coward on Tuesday February 15, 2005 @11:52PM (#11685700)
          Any encryption scheme that lasts about 10 years has given a pretty good service I would think.
          SHA-1 is not an encryption scheme, it's a cryptographic one-way hash function.

          There's a significant difference.
      • Isn't this a plot from a Dan Brown book?
      • by OverlordQ ( 264228 ) on Wednesday February 16, 2005 @12:16AM (#11685843) Journal
        DES had a weakness nobody but the NSA knew about, so they recommended changes to it without saying the reasons for them. years later an attack was found against DES, but the NSA changes prevented it from being useful. Why would they change their tune to SHA-1?
        • by Ninja Programmer ( 145252 ) on Wednesday February 16, 2005 @01:24AM (#11686205) Homepage
          DES had a weakness nobody but the NSA knew about, so they recommended changes to it without saying the reasons for them. years later an attack was found against DES, but the NSA changes prevented it from being useful. Why would they change their tune to SHA-1?


          You know, of course, that the NSA did the same thing with SHA right? The original algorithm submitted was SHA-0, then the NSA recommended an unexplained minor change.

          Last August SHA-0 was broken, so their tweak appears to have added about 6 months of extra life for SHA-1.
      • by pchan- ( 118053 ) on Wednesday February 16, 2005 @12:26AM (#11685915) Journal
        So SHA-1 was created by the NSA, and was broken nine years after it was released. Is there any chance that the NSA knew it had a secret weakness, and promoted it for that specific reason?

        I don't know about this, but when SHA (the Secure Hash Algorithm) was submitted as an approved algorithm for government use, the NSA reviewed it and suggested a minor change. That modified algorithm is what we now know as SHA-1. It was a few years before public-sector cryptographers caught on to what the significance of the changes was (I wish I could explain it, but it is beyond me).
        • by SiliconEntity ( 448450 ) * on Wednesday February 16, 2005 @01:27AM (#11686215)
          I don't know about this, but when SHA (the Secure Hash Algorithm) was submitted as an approved algorithm for government use, the NSA reviewed it and suggested a minor change. That modified algorithm is what we now know as SHA-1.

          Note quite right. The NSA invented SHA, but then a couple of years later discovered a weakness and made a slight change, to create SHA-1. The older version is now called SHA-0. According to Schneier's report, SHA-0 was broken even worse by the Chinese team, 2^39 work for a collision vs 2^69 for SHA-1. So the NSA's change was important and made a major increase in the strength of the algorithm.

          It was a few years before public-sector cryptographers caught on to what the significance of the changes was (I wish I could explain it, but it is beyond me).

          They just added a 1 bit rotate in one phase of the algorithm. Without it, SHA tends to keep the bits lined up and there is less mixing.
      • by ftobin ( 48814 ) * on Wednesday February 16, 2005 @12:38AM (#11685992) Homepage
        SHA-1 is not used for encryption, it is used for message authentication. Part of the NSA's mandate is to secure government traffic; it would gain little from promoting a broken digest algorithm. It arguably might have an interest in promoting a broken encryption algorithm, but SHA-1 is used for digital signatures.
  • For more info (Score:3, Informative)

    by response3 ( 751852 ) on Tuesday February 15, 2005 @11:28PM (#11685488)
    I'm not sure if this post is news or what, but for more info, click here:

    http://www.itl.nist.gov/fipspubs/fip180-1.htm [nist.gov]
  • Prison. (Score:5, Funny)

    by Seumas ( 6865 ) on Tuesday February 15, 2005 @11:29PM (#11685496)
    A lot of companies and products use SHA1 in some form or another. Does this mean that we can arrest and imprison these "researchers" if they ever step foot in America?
  • Oh great... (Score:3, Funny)

    by randori82 ( 797156 ) on Tuesday February 15, 2005 @11:29PM (#11685497)
    Time to change the VPN policies
  • by Anonymous Coward on Tuesday February 15, 2005 @11:29PM (#11685498)
    ... to SHA-2!
  • by psetzer ( 714543 ) on Tuesday February 15, 2005 @11:29PM (#11685500)
    If you don't switch to the newest, latest hashing algorithm, you will die horribly when your corrupted emacs RPM performs malicious code!!! Everyone, delete everything and log off of the Internets now!!! We're all gonna die!!! HELP!!!
  • Brought to You By (Score:5, Informative)

    by z0ink ( 572154 ) on Tuesday February 15, 2005 @11:29PM (#11685504)
    Same group of people that found the MD5 Hash Collision. Self [slashdot.org] references [slashdot.org] and the MD5 paper [iacr.org].
  • May be a big deal... (Score:3, Interesting)

    by ThisNukes4u ( 752508 ) <tcoppi@NospAm.gmail.com> on Tuesday February 15, 2005 @11:29PM (#11685505) Homepage
    This may be a big deal, because if I understand correctly, SHA-1 is a similiar algorithm to MD5, which is commonly used to uniquely identify files. If that could be cracked using a similiar technique, a better method of hashing files may have to be found.
    • by ajs ( 35943 ) <ajs.ajs@com> on Wednesday February 16, 2005 @12:19AM (#11685868) Homepage Journal
      if I understand correctly, SHA-1 is a similiar algorithm to MD5, which is commonly used to uniquely identify files

      You do not quite understand correctly. MD5 and SHA-1 are hashing algorithms, and as such it is expected (and accepted) that there are collisions. That is, you might find that your /etc/passwd and /bin/ls files have the same MD5 hash. The value in MD5 and other such hashes is that the probability of that happening is so remote that as a first approximation, comparing hashes is just as good as comparing files.

      That is, you can either keep a backup copy of your filesystem to compare against or you can keep a list of hashes, and mathematically, all this "break" has demonstrated is that the chances are 1:590295810358705651712 not 1:1208925819614629174706176 of a collision. In other words, don't lose sleep.

      Now, for secure cryptographic signatures, the implications are much more unpleasant. It's not the end of the world, but this is that big red light that says: switch to SHA-512 (or something equally secure) ASAP!
  • Now what do we use? (Score:3, Interesting)

    by enos ( 627034 ) on Tuesday February 15, 2005 @11:29PM (#11685509)
    With SHA-1 being MD5's replacement after that was broken, which hash function do we use now?
  • by NEOtaku17 ( 679902 ) on Tuesday February 15, 2005 @11:32PM (#11685532) Homepage

    SHA-1 Hash Algorithm [ietf.org] and Source Code [cr0.net].

  • Bittorrent? (Score:5, Interesting)

    by oman_ ( 147713 ) on Tuesday February 15, 2005 @11:35PM (#11685562) Homepage
    Is it time to update bittorrent?
    How hard is it going to be for people to provide garbage data with correct SHA-1 hashes to screw up downloads?

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

      by rsmith-mac ( 639075 ) on Wednesday February 16, 2005 @01:01AM (#11686098)
      I don't think it's practical right now, but that doesn't mean it will hold true for too much longer. As it stands right now, BitTorrent files have 2 hashes: each chunk has a hash, and then the file as a whole has its own hash. This means that for a torrent to be perfectly polluted(that is, polluted without anyone knowing), the garbage data needs to fit both hashes, which will be harder, though breaking a chunk hash is enough to kill a torrent swarm, even if users know about it. However, the **AA organizations aren't exactly poor, and as unlikely as it is, they do have the finances to get access to a large computing cluster, which would allow them to cause some damage.

      Judging from what's been said about how difficult it is to break SHA-1 even with this discovery, I would think it's fine for now, but a new hash should probably be included with BitTorrent2.

  • by JM ( 18663 ) on Tuesday February 15, 2005 @11:39PM (#11685599) Homepage
    One collision in 2**69 operations... that's quite minimal...

    Sure, for signatures, it means that you can't trust the algorithm 100% anymore.

    But for storing passwords, and other operations where collisions are not important, it doesn't matter much, even if there's another password that can generate the same hash, you still need to brute-force it.
    • by beaststwo ( 806402 ) on Tuesday February 15, 2005 @11:49PM (#11685676)
      You never could trust it 100%! That was the idea! The algorithm gives you a very high probability of authenticity, not any kind of guarantee (unless the original message is shorter than the output of the hash and everyone who hashes it later absolutely knows the length of the original message).

      It's an assurance, that's all. The only guarantee is a one-time pad, and Bruce Schneier's website is full of info on why these aren't practical!

  • by beaststwo ( 806402 ) on Tuesday February 15, 2005 @11:42PM (#11685615)
    I've been reading about hash collisions for the last few years and haven't figured out why this is a crisis problem.

    I'm not a cryptographer, just a nerdy engineer, but let me explain my rationale: a hash algorithm takes an arbitrary message and generates a fixed-length signature that has a high probability (10**50 or better for most modern algorithms) of being the original.

    Let's assume that your hash algorithm generates a 128-bit hash. Anyone who knows anything about probability can see that is the original message is greater than 128 bits, there MUST be more than one message that will generate the same hash. For long messages, there may be thousands or millions of messages out of a filed of 10**50 (or better) that have the same hash, although many of them will be meaningless garbage.

    So SHA-1 has been broken by a group of cryptographers/mathematicians. Does this really mean that they can generate can alter any message in a way that will generate the same hash as the original, thus fooling the math that we use to validate content? No Way! I read Bruce Scheier's Cryptogram every month and he often makes the same argument.

    So yes, this means that from a long-term systems security standpoint, we should all move to stronger hashes. Does it mean that SHA-1-based transactions are inherently secure right now?

    I think not!

    • by iabervon ( 1971 ) on Wednesday February 16, 2005 @12:35AM (#11685970) Homepage Journal
      It is still probably difficult (hard to say without looking at the paper) for someone to find a different document with the same hash as a document you create, but it's now not all that hard to find a pair of documents with the same hash. Someone could give you a document to sign, and get your signature on a different document. Also, IIRC for previous work by this group, the attack applies to chosen pairs of documents with sufficient "random" padding; you can search for a padding for each to generate a hash collision.

      Essentially, don't sign anything that someone else has given you without changing it in some way, or your signature might also apply to some other document they have chosen.
      • by Pseudonym ( 62607 ) on Wednesday February 16, 2005 @12:53AM (#11686057)
        Essentially, don't sign anything that someone else has given you without changing it in some way, or your signature might also apply to some other document they have chosen.

        Right, this is important.

        Decent digital signature protocols (as opposed to just the algorithms) require that you hash more than just the document. For example, you might pick a small amount of random data ("salt"), add that to the message, hash the combination and sign that. You then put the salt in the signature packet so that your signature can be verified.

        OpenPGP, for example, requires that certain signature subpackets be part of the hash, such as the signature creation time. It probably should require random salt.

    • by Kiryat Malachi ( 177258 ) on Wednesday February 16, 2005 @01:49AM (#11686343) Journal
      Here's the worry.

      Let's say someone trusts a digital signature, signed with SHA-1, to the point of allowing money to be predicated on the validity of this signature. If the message is signed and valid, the payer pays the payee $X dollars, where X is some very large amount.

      Message #1 is generated and sent. It validates.

      The money is paid. At which point the payee produces a second message which hashes the same as the first but claims to be turning down the deal, or modifying the terms of the deal s.t. they don't have to do anything to earn that money, and they claim that's what was actually sent.

      This is a problem, since the break apparently allows the construction of two (relatively) arbitrary message sequences that hash to the same value, which is an easier and much different problem from constructing an arbitrary message that hashes the same as a pre-existing message.
  • by jd ( 1658 ) <imipak@@@yahoo...com> on Tuesday February 15, 2005 @11:47PM (#11685659) Homepage Journal
    The Hashing Function Lounge [terra.com.br] lists other problems with the SHA functions:


    • (R04) V. Rijmen, "Update on SHA-1", accepted for CT-RSA'2005
    • P. Hawkes, M. Paddon, G. G. Rose, "On Corrective Patterns for the SHA-2 Family", Cryptology ePrint Archive, Report 2004/207 [iacr.org]


    If this definite break is confirmed, I think we will need to conclude that the entire family is suspect for any genuinely important purpose.


    There are a bunch of hashing algorithms on the Hashing Function Lounge that are listed as having no known attacks. At present, the most widespread is Whirlpool. I think it likely that one of these will replace SHA as the hashing function of choice in major cryptographic areas.

  • by Alan Hicks ( 660661 ) on Tuesday February 15, 2005 @11:50PM (#11685683) Homepage

    Bruce sits at his desk, reading over the encrypted e-mail sent to him about breaking SHA-1, when a loud scream echoes from his office

    I JUST SENT OUT MY NEWSLETTER THIS MORNING!

  • by Dark Coder ( 66759 ) on Tuesday February 15, 2005 @11:57PM (#11685736)
    The MD5 crack team....

    http://www.md5crk.com/ [archive.org] (wayback archive)
  • by Ray Alloc ( 835739 ) on Wednesday February 16, 2005 @12:02AM (#11685764)
    Check this article [fcw.com]: Federal agencies have been put on notice that National Institute of Standards and Technology officials plan to phase out a widely used cryptographic hash function known as SHA-1 in favor of larger and stronger hash functions such as SHA-256 and SHA-512.
  • Some background (Score:3, Informative)

    by ZakMcCracken ( 753422 ) on Wednesday February 16, 2005 @12:05AM (#11685783)
    Applications that would be broken by this are long-lived cryptographic signatures. Indeed, when a document is "signed", usually only a hash of the document is signed. Finding collisions means one can find two different documents with the same signature.

    This affects all applications using SHA-1 for signature, that is signed email (whether PKIX or PGP), server certificates (which are signed documents). This should be mitigated by the fact that in order to be really usable in some cases, the collision must also be meaningful. That is if you find a collision to a signed email but if it is meaningless, you won't really be able to use it to spoof an email. It depends on the attack quality whether collisions are "meaningful" or not.

    Some applications that should not be broken are the use of SHA-1 for key derivation, i.e. where one uses SHA-1 essentially as the basis of a random function to generate deterministic new keys from a pre-shared key. (I think that's what Schneier meant by HMAC applications.)

    Also, some short-lived signatures should still not be realistically breakable in the time that they would need to be for an attack to be successful; short-lived signatures are typically used in protocols such as IPsec or SSL for authentication. Additionally, to mount an attack on some of these protocols an attacker would need to generate a collision involving "unpredictable" data coming from another party, which the attack may or may not allow.
  • by Sophrosyne ( 630428 ) on Wednesday February 16, 2005 @12:06AM (#11685788) Homepage
    ... it looks to me the only solution is wipe Jinan city off the map.
    Now where did I leave my nukes....
  • Is it that bad? (Score:4, Insightful)

    by Anonymous Coward on Wednesday February 16, 2005 @12:36AM (#11685978)
    The article says that 2**69 hash operations are needed to find a collision. If you have a SuperHashOMatic that can do 1 Billion hashing operations per second, thats still an average time of about 18700 years.

    In order for the time to be something to be concerned about (~10 years), you would need a machine capable of doing 1.87e12 hashing operations per second. Thats 1.87 TRILLION hashing operations per second.

    Ah, but what about distributed computing?

    Let's assume that there are 1 billion desktop computers working on this project. Then they must be able to do 1870 hashing operations per second. This is a ridiculously large number for today's implementations (mine gets 100 per second, most could do about twice that).

    So is it bad? Somewhat. Further breaks could make it worse.

    We should move away from SHA-1. But this isn't not the end of the world.
  • by Great_Geek ( 237841 ) on Wednesday February 16, 2005 @12:40AM (#11686002)
    Note that what cryptographers consider a "break" is not necessarily the same as what users consider a break. (Neither is more strict, they are just different criteria for different people).

    In this case, the researchers from Shandong University (supposedly) reduced the work required to find a collision from 2**80 to 2**69; this is a major cryptographic result. It is major because SHA-1, as a "cryptographically strong hash", is not supposed to have any attacks better then random. A factor of 2**11 reduction shows SHA-1 to be very far from ideal; and since lots of clever people have tried to show this, the research team should be proud.

    Does this mean the bad-guy-of-your-choice can now start forging digital contracts? Not yet - there is no guarantee that the collision will be meaningful (as least their earlier papers didn't show that result). For a forgery to be useful, the forger needs to make the fake message say something useful - may be change the $1 to $1 million, or change the name, or something. A collision at a random place (or a non-sensical string) is essentially useless as a forgery (there may be some interested DOS attacks, but I am talking about outright forgery which is the point of the hash functions).

    And lastly, 2**69 (roughly 10**21) is still a big number! Assume that some clever people wrote a super-duper hand-optimized code that does a whole SHA-1 in a micro-second on a late model 4 Ghz PC, that is 10**6 hashes/sec. A grad-student using all the PC's on a campus, say ten thousand, that's another 10**4. This would take 10**11 seconds (or roughly 20K years). Note that for SHA-0, their break is 2**39 operations, which *is* practical - it would take the grad student only a minute, or a single PC a week.

    This break is yet *practical* for *most* people. (Would I still use SHA-1? Not in new application, and I make sure that existing applications get changed over eventually.)

    Lest I be accused of ignoring the big boys, the equation changes for them. If a Three Letter Agency is willing to invest a lot of money and design some cool chips that has awsome parallelism and everything, then each break may take only a week. For example, assume these chips has a bunch of pipes that can do a hash every nano-second (or 10**9 hash/second). Further, say there are 100 of these pipes per chip, 100 chips per board, 100 board per rack (or 10**6 pipes/rack). Each rack can then do 10**15 hash/sec, With such a magical rack, it would take 10**6 seconds (or just under two weeks) to find a collision. This would cost Some Real Dollars, but is it within the budget of some three letter agency? You bet. Hack, I would be willing to sell you one for under a billion dollar US. On the other hand, for that kind of money, cryptanalysis takes on different textures - why spend a billion to crack SHA-1 when you can buy the right wet-ware unit for a million?
  • Poly1305-AES (Score:5, Informative)

    by D. J. Bernstein ( 313967 ) on Wednesday February 16, 2005 @01:14AM (#11686148)
    For people interested in secret-key message authentication: There are authenticators that are (1) much faster than HMAC-SHA-1 and (2) guaranteed to be as secure as AES. In particular, check out Poly1305-AES [cr.yp.to]. Public-domain Poly1305-AES software is now online, though it isn't nicely packaged yet; if you're interested in further announcements, join the Poly1305 mailing list.

    (This is not meant as a comment on the security of HMAC-SHA-1.)

  • by dantheman82 ( 765429 ) on Wednesday February 16, 2005 @01:59AM (#11686386) Homepage
    I read on one site - in answer to the question "What's the big deal - is 2**69 really all that bad?"

    That's 2**11 less operations. Let's say breaking this (2**69 ops) takes the NSA a week. If it had been 2**80, it would have taken 2048 weeks, or 39 years. If it would have taken the NSA (or whomever) a year to break SHA-1 before, it could be broken in 4 hours.

    My guess would be it would still take a lot longer than a week - but would now be in the realm of possibility, whereas before it would have been in the lifetime(s) range. However, this is totally a wild-assed-guess, based on the assumption that it was expected to take 100+ years before this to crack.
  • by ars ( 79600 ) <assd2NO@SPAMdsgml.com> on Wednesday February 16, 2005 @05:22AM (#11687025) Homepage
    I guess I missed posting this before the bulk of the posts, but maybe it'll help someone.

    First: MD* SHA-* etc - they are all basically the SAME algorithm! The are just minor modifications of the same exact thing, so a break in one is a break in all.

    Second: Tons and tons of people ask: can't we merge two hashes together and get a stronger one? Yes you can that's EXACTLY what MD* and HA-* DO! They are a combination of different hashes! That's how they work.

    So if you really did have a good combo of hashes then just give them a name and use them as a hash - don't bother just plain merging existing ones.

    Also, merging say MD5 and SHA-1 is pointless - they are both based on the same hashing code! You are gaining nothing by merging them.
  • by cmacb ( 547347 ) on Wednesday February 16, 2005 @06:23AM (#11687197) Homepage Journal
    I hope they get it fixed soon.
  • by snorklewacker ( 836663 ) on Wednesday February 16, 2005 @12:16PM (#11689266)
    At least they gave the algorithm. If their synopsis is indicative of the paper, they illustrate that SHA-1 has collisions, and collisions can be discovered through the awesomely sophisticated technique of brute force. Pardon me while I dust off my bomb shelter.

    Let's wait for the actual paper. If it takes more CPU power to force a collision within a year than the whole of what IBM sells in that year, I think that the hash is doing its job...

Fast, cheap, good: pick two.

Working...