Slashdot Mirror

← Back to Stories (view on slashdot.org)

More on Newly Broken SHA-1

Posted by CowboyNeal on from the all-hands-abandon-ship dept.

AnonymousStudent writes "Details are out about the reported broken SHA-1 hash function. The findings are that SHA-1 is not collision free and can be broken in 2^69 attempts instead of 2^80. This is about 2000 times faster. With todays computing power and Moores Law, a SHA-1 hash does not last too long. Using a modified DES Cracker, for the small sum of up to $38M, SHA-1 can be broken in 56 hours, with current computing power. In 18 months, the cost should go down by half. Jon Callas, PGP's CTO, put it best: 'It's time to walk, but not run, to the fire exits. You don't see smoke, but the fire alarms have gone off.' As Schneier suggests, 'It's time for us all to migrate away from SHA-1.' Alternatives include SHA-256 and SHA-512."

6 of 362 comments (clear)

  1. Collision free hash? by baadger · · Score: 5, Insightful

    "The findings are that SHA-1 is not collision free"

    Since when is it possible to have a collision free hash when the hashed data has more possibile bit combinations than the hash itself?

    Genuine question.

    1. Re:Collision free hash? by mre5565 · · Score: 5, Interesting
      With 160 bits of hash, the probability that two pieces of data will hash to the same value is incredibly low.

      The width of hash has little to do with the probability of a collision by an attacker. The cleverness of the hash algorithm is the key to collision resistance. For example, a checksum is a hash that merely breaks the int into 160 bit chunks, adds each chunk to together, takes the lower 160 bits of the sum, resulting a 160 bit hash. It is trivial to find for any given message, multiple messages that checksum hash to the same value. Thus far, no one has proven they can do that with SHA-1 (or MD5 for that matter), at least not trivially.

      Of course, once one has a clever algorithm, width of the hash can be a nice factor in building up its strength, assuming the hash algorithm lends itself to scaling that way, as SHA apparently does, with SHA-256, SHA-512 being available.

      Of course, for random data corruption due to faulty hardware or software, a 160 bit checksum would be excellent (if costly) protection. But that isn't what we are talking about here.

  2. SHA-1 by mboverload · · Score: 5, Funny

    SHA-1? pshhhh. They should be using SHA+1. Thats 2 more!

  3. Theoretical security concerns... by Temporal · · Score: 5, Insightful

    So someone with $36 million to throw around can, in 56 hours, produce two random messages with the same SHA-1.

    Great.

    So, presumably, this devious (and very rich) hacker might produce the following two messages:
    "bma p3 rjphta,-9p.u2#H50982u.yha,cp. hxasnip"
    and
    "BUEQXBBX2 jma93#9g5xbaida htuEXOAhkra1255,y"

    And then, of course, he'd somehow trick me into signing "bma p3 rjphta,-9p.u2#H50982u.yha,cp. hxasnip". Because I sign random pieces of gibberish all the time, if asked. And then, having done this, he could go around claiming that I had actually signed "BUEQXBBX2 jma93#9g5xbaida htuEXOAhkra1255,y".

    OH NO! ::cough::

    Sure. Moving to SHA-256 is all well and good. But, frankly, I think these reports are horribly overblown. Crypto geeks are jumping up and down with their hair on fire (just like George Tenet!) because their perfect algorithm is slighly less perfect in a way that doesn't have any real practical meaning in most situations.

    Meanwhile, there are real security problems out there in the form of poorly written software and poorly administered systems. Please, please do not spend your time rewriting your software to use SHA-256 when you could be patching real security holes. Leave SHA-256 until you have nothing better to do.

  4. Follow-on work by fhmiv · · Score: 5, Informative

    The concern is not so much that the method described in this break is feasible on today's hardware, or even that this method will get cheaper and cheaper as hardware gets faster. The BIG concern is that this method provides insight in to the SHA-1 in general, and will be used by others to come up with more efficient breaks or more egregious flaws.

  5. Clearing up some myths... by MLopat · · Score: 5, Insightful

    Having worked in the crypto field, I thought I would take some time to clear up a few misconceptions. First off, the results of this paper in no way compromise the security of email or other data encrypted with algorithms that use this hash. As an extension of Moore's law prevails, these characteristics of any hash function are bound to be discovered. However, with that said, it is important to realize that this new discovery in mathematics allows us to move forward with hash technology to develop better algorithms.

    Hash algorithms are one of the least understood principles in cryptography. The established mathematics around them is contemporarily vague, but under constant research. Therefore, anytime a new publication illustrates a flaw, technique, weakness, etc. we should be pleased that our understanding has grown and that a new, more advanced algorithm can be created with the knowledge gained.

    This discovery is a not something to panic about, but rather an achievement that will bring about newer, stronger encryption technology.