More on Newly Broken SHA-1

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."

Comments

People still use SHA-1?

[Anonymous Coward]

Do people really still use SHA-1?

I've been using SHA-256 for a while now.

Re:People still use SHA-1?

[AKnightCowboy]

Yea, what losers. I use nothing but MD5 for my hashing needs and DES for encryption. Unbreakable government certified encryption!

/10 years ago

Re:2000 times faster?

[harmonica]

2^69 attempts instead of 2^80 seems like only 11 times faster, then again, thats just me.

2^80 = 2^11 * 2^69 = 2048 * 2^69

Re:2000 times faster?

[synthparadox]

2^69 = 590295810358705651712
2^80 = 1208925819614629174706176

2^80 / 2 ^ 69 = 2^11, which = 2048.

Yep. 2000 times faster.

Re:2000 times faster?

[rbarreira]

No, it's 2^11 times faster, which is 2048 times faster... Rule:

a^n / a^m = a^(n-m)

Re:2000 times faster?

[Anonymous Coward]

2^11 = 2048

Re:2000 times faster?

[Temporal]

2^80 / 2^69 = 2^11 = 2048

Break only affects carefully constructed messages

[Sam Ruby]

The new SHA-1 break only affects very carefully constructed messages. This means that it is completely useless for an attacker impersonating an existing message, unless that message was purposely constructed to be attackable. The attack is only useful if the attacker creates both messages, and the attacker can choose the exact format of both messages.

Re:2000 times faster?

[selectspec]

2*2*2*2*2*2*2*2*2*2*2 = 2048 times faster

Collision free hash?

[baadger]

"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.

Re:Collision free hash?

[Anonymous Coward]

Since hell froze over in 1852. Read the constitution! It happened!

Re:Collision free hash?

[HeghmoH]

This is cryptography, so it's always talking about possibilities.

With 160 bits of hash, the probability that two pieces of data will hash to the same value is incredibly low. Using a brute-force technique, you'd have to use all of the computers on the planet for thousands of years to find a collision. This is, for all intents and purposes, "impossible", and thus the hash is effectively collision-free.

With the new findings, a wealthy organization could actually find a collision with a reasonable amount of money and time.

Re:Collision free hash?

[IWannaBeAnAC]

It simply means that it is possible to find a collision without a brute-force scan of O(2^80) messages. Instead, because of weaknesses in the algorithm, it is only necessary to scan O(2^69) times.

Re:Collision free hash?

[mboverload]

It's not. I'm sure there is some law, but if you are hasing data that has more data than the hash itself, there are going to be collisions.

(Stupid Mean Girls quote)"Anything else is like...against the laws of feminism or something!"

Re:Collision free hash?

[ajs]

Obviously, it's not. The article is also not "new" information by any account (everything said was in B.S.'s original blog entry).

I also want to stress that while this is a blow to the faith we placed in SHA-1 (why were we trusting a hash invented by the NSA, anyway?) it doesn't do much for most uses of SHA-1. For example, it could allow you to perform a successful man-in-the-middle attack against an SSL-encrypted HTTP session, but the user might notice something was up when response times were measured in days ;-)

It also does not impact the strength of encryption used for such sessions.

Re:Collision free hash?

[vandy1]

Yep, it's called the Pigeonhole Principle, and is tought in first year discrete mathematics.

Cheers,

Michael

Re:Collision free hash?

[Anonymous Coward]

That, to be honest, is rubbish.

First of all, of course SHA-1, like any has function, is not collision-free, not even "effectively" or "practically" or anything like that.

Furthermore, the successful attack on SHA-1 (if it is one; until the paper is actually published, that's not 100% sure) does not change anything about that in any way, and it does not mean that collisions suddenly will occur more often than previously thought. It only means that there is a way to find collisions (under certain circumstances) that's faster than brute-force.

Statements like "you'd have to use all of the computers on the planet for thousands of years to find a collision" are also uninformed, sensationalist rubbish. If I could use a computer in the (currently) ~30M USD range to compute a collision in 56 hours, as Schneier claims, then I could just as well brute-force SHA-1 in about 12,8 years (2000 times 56 hours) using the same equipment. Probably not really practical, depending on what exactly you want to do, but it's hardly "thousand of years" using "all the computers on the planet", is it?

Next time, don't post about topics you don't understand.

Re:Collision free hash?

[vandy1]

Oops, spelling should be taught (/me learns not to click "Submit" immediately...)

Re:Collision free hash?

[baadger]

Are there any dynamic length hash/one-way encryption functions out there? Would these provide greater collision prevention than SHA-1?

Why are hashes like CRC-32, MD5 and SHA-1 fixed length anyway?

Re:Collision free hash?

[Vexler]

It's important, when we speak of using cryptographic algorithms, to distinguish between "impossible" and "infeasible". Given enough processing power and enough time, any key can be cracked. The question is one of feasibility: By the time you crack the key and use it to extract the information, (a) would the information still be relevant and useful to you? and (b) would your fourth-generation decendent be the person who actually cracks the key in your place?

It's quixotic to look for an algorithm that is "impossible" to crack. I do think that we should make it as "infeasible" to crack as possible.

Re:Collision free hash?

[MoogMan]

An idea: This could be a good thing. If there was a one-one relationship, then that would mean theoretically there could be an inverse function to "expand" the hash. Given that there are going to be collisions, this may give us (if only a little) more confidence that hashes are not reversible.

Re:Collision free hash?

[Anonymous Coward]

You, sir, in your haste to showboat your "expertise" and rubbish other posters, have managed to prove only that you are a prat.

What "effectively collision free" means, in terms of a hash function, is that no two similar pieces of data will collide. That is what the parent meant. For such a hash function, it would be very difficult to construct (for example) two similarly worded contracts, such that one could easily substitute another after the signing process, and not have it be blatantly obvious that a change had been made. Such a hash function is "effectively" collision free. It has collisions, but they are unlikely to be useful or important.

For those of us with half a brain and the reading comprehension skills of a Republican president, the statement "you'd have to use all of the computers on the planet for thousands of years", etc., clearly refers to a strong, unbroken hash function. It does not refer to SHA-1.

Next time, don't reply to posts you don't understand.

Re:Collision free hash?

[sjasja]

Dynamic length collision free hashing is called encryption. The "hash" is necessarily at least as long as the message itself (see pigeonhole principle.)

Re:Collision free hash?

[InvalidError]

Fixed-length fields make data flows more regular and therefore easier to manage.

For hardware and software designers, knowing that every field in a data structure is in a specific order and are of specific lengths make their lives an awful lot easier.

Variable length field might be nice for high-level languages but for low-level stuff and hardware implementation, they can be awfully troublesome and are usually avoided wherever possible.

Re:Collision free hash?

[mre5565]

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.

Re:Collision free hash?

[Anonymous Coward]

How the hell isn't this modded up?

Re:Collision free hash?

[tod_miller]

I spoke about this at length, how absurd stating that they have found that any data being hashed into a smaller data space 'has colisions', and got modded a troll.

I think the first ever boring lecture I had was on memory paging and has colision detection of paging algorithms... that is right, hash colisions.

Now, there seems to be too much huff and puff and not enough actual insightful talk about what this actually means, which means the fallout of this will bea bout 68.5 /. articles all being submitted by different people, all pointing to different blogs, all written by different people, who all thought different things about different articles they read about this one issue.

Which sucks.

Basically, this seems very unusable, and doesn;t indicate that this goes further (in so much that there might be a step 2).

Is this fuel for someones security consultancy? I think the people behind it are genuinely curious, by the way it has been taken and portrayed in so many different lights is a bit daft, I feel like the whole IT community can be like a school yard of giggling girls at times, instead of the fact based enquiring minds I expected.

Re:Collision free hash?

[mikiN]

Given enough processing power and enough time, any key can be cracked.

Except for OTP (one-time pad) encryption, which has been proven impossible to crack when implemented and used correctly.

Re:Collision free hash?

[waveclaw]

This is cryptography, so it's always talking about possibilities.

With 160 bits of hash, the probability that two pieces of data will hash to the same value is incredibly low. Using a brute-force technique, you'd have to use all of the computers on the planet for thousands of years to find a collision. This is, for all intents and purposes, "impossible", and thus the hash is effectively collision-free.

With the new findings, a wealthy organization could actually find a collision with a reasonable amount of money and time.

So? All that these two groups have done is prove that MD5 and SHA-1 are hashes, nothing more. There is also a known and finite probability that I could generate examples of hash collisions on SHA-256, SHA-512 (and on up to SHA-n) on my first try by typing gibberish into a hex editor.

While doing so wouldn't win me the fame of he MD5 and SHA-1 researchers, it is just as usefull as both results. Eventually all hashes will have collisions. Still, there are security nuts screaming to abandon MD5 and SHA-1 for a few more bits. They tend to forget that without (1) easy collision generation and (2) gerenation from an arbitrary message that neither of these are 'broken' for security use. Furthermore, neither of these techniques are more usefull in making (2) true than my random typing technique.

---------
Come to think of it, there are already a million monkeys on a million
typewriters, and Usenet is NOTHING like Shakespeare.
-- Houghton, Blair

Re:Collision free hash?

[Igmuth]

Yes, but the existance of collisions isn't the suprising part to anyone involved in this. Hashes, by their definition will have collisions. (See Pigeon Hole Principle). Any 1:1 encoding algorithm, is better called an encryption algorithm. (Possibly a very weak algorithm, but one none the less)

The part that is suprising (and the point of the article), is the speed at which these collisions can be found. Yes, it requires ~56 hours, and works best with certain types of messages. So they are encouraging people to start changing now, so that as computational power increases over the next few years (reducing the time to find the collisions), people will be safe.

Re:Collision free hash?

[evilviper]

if you are hasing data that has more data than the hash itself, there are going to be collisions.

That's only completely accurate if the data in quastion is 100% random.

A simple compression program like gzip can create a unique "hash" that is smaller than the input data. Or more accurately, you could make a unique hash of the compressed data, which would be smaller than the uncompressed data.

Re:Collision free hash?

[Anonymous Coward]

with SHA-256, SHA-512 being available.

And we're talking about SHA-1 here? Surely it can't be hard to generate collisions in a 1-bit hash! I'm definitely upgrading to a 256-bit version.

Re:Collision free hash?

[typobox43]

The part that the grandparent left out is that this only applies to fixed-length hashes. Anytime you hash data to a fixed-length hash smaller than the data, there are collisions. Obviously variable-length "hashes" such as gzip don't follow this rule.

Re:Collision free hash?

[Anonymous Coward]

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.

Despite the name, SHA-256 and SHA-512 are not scaled up versions of SHA-1. They're totally different beasts. It's unlikely the same attack works without significant work.

Re:Collision free hash?

[Theatetus]

For such a hash function, it would be very difficult to construct (for example) two similarly worded contracts, such that one could easily substitute another after the signing process, and not have it be blatantly obvious that a change had been made.

Yeah, and it still is very difficult. It's just that they've found a way somewhat faster than brute force to find essentially random data (NOT "data with any particular characteristics" -- that would be useful to an attacker, at least) that hashes the same as the piece of data in question.

All you can really do with this is replace any message verified by a hash with garbage. Perhaps useful in a DoS attack if the hash verification is a step of the routing, but hard to imagine another use for it.

Re:Collision free hash?

[Shanep]

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.

Genuine answer.

But I'll need to slightly modify your question to answer what I think you are really asking...

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

Never, ever. Unless you are considering only a finite list which won't generate any collision and ignoring those that will (an infinite list).

; )

Re:Collision free hash?

[Shanep]

This is, for all intents and purposes, "impossible", and thus the hash is effectively collision-free.

From what you have written, I gather you already agree with this. But I'll state this to ellaborate on what you've written and if not maybe it will spark discussion...

Collision-free? No. Not even effectively.

Extremely difficult to infeasible to find any one of the infinite number of possible collisions? Yeah, sure. But this does not make it collision free. A collision does not just suddenly exist once it is found by a human or machine. It always existed within the realm of mathematics. The difficulty is in the finding.

A good hashing algorithm will have maximal strength possible by it's intended design. A weaker one will allow more collisions than the design should have allowed. Regardless of how strong a hashing algorithm is intended to be or is in reality, they ALL will exhibit an infinite number of collisions.

Sorry to be so literal, but I think it is important to adhere to definitions, lest they be forgoten after being loosely used. No hashing algorithm is "effectively collision-free". Effectively impossible to find a collision, maybe.

Taken literally your post is interesting, because the first and second sentence of your second paragraph might have been commonly accepted a few weeks ago if regarding SHA-1. But your third paragraph is closer to the reality today, yet one speaks of thousands of years and the other a reasonable amount of time! The problem here is that people think something like "160 bits", do the quick math and then proclaim of the extreme strength, because they assume maximal strength. The reality is that an error prone human or group of humans designed these algorithms with typical animal creativity. Animal creativity gets further and further from mathematical perfection as complexity becomes greater.

Hashing algorithms are very complex, by typical standards and it took all this time for SHA-1 to be found weaker than first believed. The real weakness, is not the algorithms, it's the people designing them and people relying on them to be maximal strength. It's a difficult situation, because few people are gifted or knowledgable enough to know better, so the common man must reach a point where the line into faith must be crossed. ; )

Re:Collision free hash?

[Shanep]

The width of hash has little to do with the probability of a collision by an attacker.

If a hash algorithm attains true maximal strength to it's message digest bit depth, then it has everything to do with the probability of finding a collision.

If you can pass an infinite combination of a data set which can have an infinite size, through an algorithm which will reduce that to a fixed message digest, then there will ALWAYS be collisions. An infinite number in fact.

The "probability of a collision" is meaningless in this context. It would be meaningful if you wrote "the probability of finding a collision". The bit depth is meaningful if the algorithm attains maximal strength. Knowing if that is really the case, is very difficult with complex algorithms of any great strength.

It is not possible to uniquely represent the full bit space allowed by 2 bits with a digest of 1 bit. 50% of the values will collide if the algorithm used attains maximal strength.

With modern hashing algorithms and a finite amount of data of sizes typically used, it is not like finding a needle in a haystack. It is like find one of a trillion needles in a haystack the size of our Earth.

Re:Collision free hash?

[m50d]

The main reason they are fixed-length for signing is that the actual encrypting-with-private-key bit is computationally very expensive, and worse, it's fully exponential with the length of the message. When pgp was first written, signing an actual email would have taken days for the average desktop PC. Nowadays you could probably manage a short email, but your desktop PC couldn't sign a 700mb iso in several times the age of the universe. The hash is meant to maintain the security (because you can't change the message without changing the hash) whilst meaning you only have to do the actual calculation on 128 or 256 bits.

Re:Collision free hash?

[vandy1]

There's no point in avoiding collisions. The point is that it should be computationally infeasible to come up with a message that has the same hash as another message. They're fixed length because there's no reason to make them variable length - what in particular would it help? The only way to avoid collisions is to send the entire message, and our only aim is to make it verifiably so that a missive was sent by the person signing the hash (listening in undergrad *does* help :) ). CRC-32 is only good for transmission stuff - computationally, it's trivial to come up with a message with a particular CRC-32.

SHA-1

[mboverload]

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

Re:SHA-1

[Anonymous Coward]

I'll wait for SHA+/-1 dual format

Re:SHA-1

[stutterbug]

Soon, there will be SHA-++. And inevitably, Microsoft will make SHA-# ("sha-SHARP") that will take as much computing power to generate as it will to break. Ah, progress.

Re:SHA-1

[isorox]

This one goes up to 11!

Re:SHA-1

[Anonymous Coward]

That's already obsolete. The future is Blu-SHA.

Re:SHA-1

[Paleomacus]

Personally I can't wait for SHA-! ("sha-BANG").

I admit it, I am an utter moron.

Re:SHA-1

[DrSkwid]

been done

Re:SHA-1

[Anonymous Coward]

I'll wait for sha-zam thanks

Re:SHA-1

[Jah-Wren Ryel]

Now that SHA-1 has been overthrown, we can expect that AYATOLLAH-1 will replace it as the ruling hashish maker.

Re:SHA-1

[myowntrueself]

Yeah, I mean if SHA-256 is SHA in 256 bits and SHA-512 is SHA in 512 bits, surely even an idiot would have seen an upcoming hole in SHA-1

Re:SHA-1

[Anonymous Coward]

Wouldn't that me SHA-Ching? (sorry, can't type the symbol)

Re:SHA-1

[felipin-sioux]

And then there will be SHA-R, SHA-RW, SHA+RW and a lot of other incompatible stuff.

Re:SHA-1

[RichiH]

obviously, you mean shaRP

Re:2000 times faster?

[Temporal]

Jesus Christ. In the time it took to write my post (all of 30 seconds), five other people replied to you.

Just goes to show, the quickest and most effective way to get information on the net is to post something that is wrong.

Hmmm

[Lisandro]

The findings are that SHA-1 is not collision free and can be broken in 2^69 attempts instead of 2^80.

Well, doh - it's a hash you silly, there will always be collisions.

Anyway, it's nothing to panic about really. The ammount of computer power needed to crack it is still massive. Unless you're investigated by the NSA, SHA-1 will be fine for quite a while.

Re:Hmmm

[plalonde2]

My concern with this is that my favorite archiving file system venti uses SHA-1 to generate unique block IDs for each block written to disk. This allows blocks of identical data (even though they are in different parts of the file system) to hash to the same address, making incremental storage (and backup) trivial. Currently collisions are not detected as they are expected to happen with substantially lower frequency than disk failures.

But now I suspect that my nice secure file system can be nastily compromized by generating hash-equivalent blocks. Not a huge worry, but sad to see.

Re:Hmmm

[pyrbe]

Well, how about the digital signatures? They should have the same legality than with the ordinary ones.. atleast if you have used the qualified certificates to create them. This is what the law says (atleast in Finland). So, what happens to the the digital signatures when the cryptographic algorithms that are used to construct them starts to break? Are they still as valid as the ordinary signatures? When the law about digital signatures has been signed, there has been trust for those algorithms.. what happens now? Digital signatures are made of trust. This uncertainty breaks the trust.

Re:Hmmm

[Anonymous Coward]

I love how the third post saying exactly the same thing is Informative, when the first post saying something on another thread today, by me, was Redundant. Is this poster an editor's fuck buddy? I think so.

Re:2000 times faster?

[mboverload]

I was KIDDING! Kidding!

Jesus people, I passed 8th grade....or did I? =)

This is big...

[A beautiful mind]

We need to develop algorithms aside of SHA. SHA-256 only postpones the problem...

Re:This is big...

[mboverload]

So I guess SHA-256 is slower than SHA-1, right?

Why not just use SHA-2048, that wont be broken for like...6 years.

Re:This is big...

[m50d]

They already exist. RIPEMD-160 is tried and tested and seems secure, or at the more experimental stage there's Whirlpool.

Re:This is big...

[A beautiful mind]

I think whirlpool is getting submitted into the linux kernel within the latest or in the next few releases.

Re:This is big...

[Illserve]

No algorithm is unbreakable.

You'll always be upgrading methods to stay ahead of computing power.

Fortunately, it's not that hard to do.

Re:This is big...

[A beautiful mind]

Well, it all depends. Catastrophe didn't happen with DES because there was an early warning and noone used it for serious stuff by that time. With SHA-1 however, the warning came a little later and the shift will be a bit more painful as a lot of things are using it, although not impossible and not a catastrophe neither.

Re:This is big...

[Anonymous Coward]

SHA-256 only postpones the problem...

Well, every new development only postpones the problem. Most secret information is only valuable if it is relatively recent, so "postponing" is usually good enough.

However, if you want to encrypt something and have it unbreakable indefinitely, you're out of luck as far as I know: the typical security argument cryptographers use is "well, if you can break our encryption, you can factor in polytime." But quantum computers can factor in polytime (and who knows what else they can do) so the security argument doesn't hold water.

Re:This is big...

[A beautiful mind]

I think my point needs a bit of clarification. My point was that by saying postponing i mean that there is a higher possibility that the current research can be applied to SHA-256 soon aswell, for example breaking it in a year or a half.

Scneier mentioned that he thought in last september SHA-1 will be broken, just not that it will be broken this soon.

Re:This is big...

[Anonymous Coward]

If it is the same algo as SHA-1 but with a bigger key, then it already is "broken", as it now takes 2^somefuckinghughnumber-somesmallnumber, not 2^somefuckinghughnumber. Just like SHA-1.

Re:This is big...

[Riddlefox]

Factoring in polynomial time is important in public key algorithms. Properly designed secret key algorithms with a key-size of 256 bits or more are unlikely to be broken even by a quantum computer (this is per Zimmerman's introduction to PGP, though he does note that history has a tendancy to make notions like this "amusingly quaint.") Grover's algorithm, as far as I know, is the quantum-computing algorithm for searching. However, this algorithm effectively reduces the keyspace by half. A 128-bit symmetric (secret) key effectively becomes a 64-bit key against a quantum computer, which is not very strong. A 256-bit symmetric key becomes a 128-bit key, which is still very strong.

Of course, there is one unbreakable encryption - one time pads. Fortunately, quantum cryptography seems to be able to implement a convenient one time pad at a decent data rate. It's a race to see whether quantum computing or quantum cryptography becomes widespread first.

Re:This is big...

[steve_stern]

We need to develop algorithms aside of SHA. SHA-256 only postpones the problem...

It postpones it a lot. Lets say the break is linear in the expansion of the SHA-X algorithm family, so 2^69 break for SHA-1 (160 bits) is equivalent to a 2^110 break in SHA-256 and also equivalent to a 2^220 break in SHA-512.

Thats an awful lot. That means both SHA-256 and SHA-512 are still more secure than SHA-1 ever was even supposed to be. Even if you say this algorithm will become more efficient over time, it would have to go down a lot before SHA-512 is less secure than the (unbroken) SHA-1 was designed to be.

In the near future, I would much rather use SHA-512 (or even SHA-1) than a brand-spankin-new algorithm and all the possibly worse breaks you can find there. You know the saying about the devil you know.

Re:This is big...

[hey!]

Well, yeah, but if it postpones longer than the universe needs to run down from heat death, the available energy won't be sufficient to calculate the collision. ;-)

Re:This is big...

[Anonymous Coward]

We need to develop algorithms aside of SHA. SHA-256 only postpones the problem...

SHA-256 is a different from SHA-1. Don't assume the weaknesses apply to both (they probably don't).

Re:This is big...

[TheRaven64]

Also, the people who jumped on SHA-1 when MD-5 was rumoured to be weak a few months back are going to be really pissed off...

Re:This is big...

[evilviper]

RIPEMD-160 is tried and tested and seems secure

Strange that you would say that, because RIPEMD has collisions. Yes, RIPEMD-160 has more rounds, but the vulerability of RIPEMD certainly casts doubts on the strength of RIPEMD-160.

Re:This is big...

[(negative video)]

Fortunately, quantum cryptography seems to be able to implement a convenient one time pad at a decent data rate.

Not for fiber optic communication, it doesn't. Quantum "cryptography" over a long-haul link requires (1) a conventional message authentication code (MAC) to protect against a man-in-the-middle attack, or (2) transmitting the photons on a straight-line path through air so that a man-in-the-middle attack can be detected by measuring time-of-flight. Otherwise an attacker can simply cut the fiber, attach a quantum "cryptography" machine to each end, transparently forward data from each end to the other, and use a radio link to make up for the lost time. Radio travels at the speed of light, whereas signals on a fiber travel at about 0.67c. Every meter of travel through air gives you back 1.1 nanoseconds taken away by the transparent proxy algorithms.

#1 reduces its strength to that of conventional cryptography. #2 is impractical because long air paths require either expensive tunnels or are affected by weather.

Hollow-core fiber might help, although it still has a delay due to the evanescent field sticking out into solid matter, isn't available commercially in 500 km spools, and would be unholy expensive to deploy for every comm link you wanted to protect.

Quantum "cryptography" won't work directly over radio because you can't detect individual radio photons. (They're swamped by thermal noise. For the one meter band, you'd have to cool the transmitter, receiver, and propagating medium to around one millikelvin just to be able to detect the photons.)

I'm sorry to say it, but quantum "cryptography" is just snake oil. Worse, it protects the least-vulnerable part of the system. Software flaws, LAN sniffing, removable media, data radiating from Ethernet cables, adulterous employees who can be blackmailed, etc. are much bigger holes. A hypothetical enemy who can cryptanalyze every cipher you can afford to deploy is not the first thing you should worry about.

Re:This is big...

[Anonymous Coward]

> No algorithm is unbreakable.

I'd certainly be interested in any proof, or even evidence, that you have for this assertion.

Re:This is big...

[m50d]

Hmm, you're right. Guess I'd better switch to tiger or whirlpool, at least once gpg has support for them.

Re:2000 times faster?

[baadger]

http://www.google.com/search?q=2^80+/+2^69&sourcei d=opera&num=0&ie=utf-8&oe=utf-8

Re:2000 times faster?

[Lisandro]

I bet $50 that a hard drive manufacturer came up with that!

Re:2000 times faster?

[harmonica]

Kidding about math on /.? You should know better...

Re:Break only affects carefully constructed messag

[way2trivial]

so you are saying daryl is prepping his 10-k for transmission now?

Further compromises not far behind?

[defile]

Aren't these rarely isolated incidents?

Isn't the probability of discovering further compromises by widespread cryptanalysis of this discovery extremely high?

Re:Further compromises not far behind?

[rbarreira]

RTFA, that's exactly what the article says...

Re:Break only affects carefully constructed messag

[johnhennessy]

Totally agree, however in the crypto community (which I cannot claim to be part of) the consensus is generally that if a weakness if found in an algorithm then it begs the question - "what other weaknesses are there".

Once an algorithms strength is in doubt by the presence of even one weakness people feel very reluctant to trust it.

Its probably up to everyone to see how this affects their own circumstances. Crypto is always about Knowing your enemy (the paranoia has now kicked in !). When picking a scheme one always makes a number of assumptions - Who are you keeping the information hidden from, what resources do they have, how badly do they want it.

No crypto is powerful, or clever enough (yet!) to be completely unbreakable so its all down to making assumptions:

1)
Would someone be willing to pay $38 million (assuming this is correct) to get my credit card number - probably not.

2)
Would someone be willing to pay $38 million to get insider info on a merger between two banks - each worth over $10 billion.

What unsettles people is that their previous assumptions on SHA-1 are now invalid.

Moron!!

[Anonymous Coward]

2^80 / 2^69 = 80 - 69 = 12

Re:Moron!!

[Anonymous Coward]

You're the moron:

$ bc
bc 1.06
Copyright 1991-1994, 1997, 1998, 2000 Free Software Foundation, Inc.
This is free software with ABSOLUTELY NO WARRANTY.
For details type `warranty'.
2^80/2^69
2048

Yet Another Overblown Crypto Hack

[OhBrian]

Wow! 2^69 instead on 2^80. The reality is that use of SHA-1 STILL places a significant cyptographic barrier in front of an attacker trying to discover the contents of hashed payload. I'd argue that using any form of cryptography (save null) presents a barrier that the average hacker won't even attempt to overcome.

Re:Yet Another Overblown Crypto Hack

[Anonymous Coward]

The attack has nothing to do with trying to discover contents based on the hash, it has to do with generating intentional collisions.

Attacks on hashes have absolutely nothing to do with discovering any kind of content, they have to do with the reliability of digital signatures, key exchange, data integrity, authentication etc.

As for any kind of cryptography being sufficient...no, not really. Consider CSS...the encryption used on DVDs is no longer considered any kind of barrier to access.

Similarly publicly visible hashes in password files on Unix systems haven't been considered secure for over 10 years, due to the simplicity and success rate of dictionary attacks (plus more recently, brute force is becoming increasingly easy).

Re:Yet Another Overblown Crypto Hack

[Anonymous Coward]

trying to discover the contents of hashed payload

That's easy, look right next to it. A hash doesn't "contain" anything, it's sent along with the plaintext as an integrity check.

Re:Yet Another Overblown Crypto Hack

[Anonymous Coward]

You don't know much about crypto do you? Even if it was 2^1 to find a COLLISION, that won't tell you jack about a payload. Hashes are one way. (They have to be by the sheer fact that there are collisions.. They are not one-to-one and onto, hence they are not reversible.) The break was being able to find two values, X and X' such that H(X) = H(X') in less than brute force (2^80) time.

Re:Yet Another Overblown Crypto Hack

[bobbuck]

Hashes DO tell you about the payload. If the hash is of an e-mail message, there might be less sensible short english messages than hash values and the size of the hash set statistically precludes other sensible messages (if it didn't, a better hash function would have been used.)

Re:Yet Another Overblown Crypto Hack

[koreaman]

CSS still serves a purpose, believe it or not. The average Joe Sixpack Moviewatcher doesn't know DeCSS exists, all he knows is that the movie companies have some kind of magic to make it so he can't copy his DVDs. Just like Safedisk 2 it's an insanely easy to break copy protection scheme, but it stops a *lot* of copying by home userns who don't know what they're doing.

Re:Yet Another Overblown Crypto Hack

[OhBrian]

Duh? So where does the data used to feed the hash come from? You potentially get a piece of the original message. You said: "The attack has nothing to do with trying to discover contents based on the hash, it has to do with generating intentional collisions." A collision is defined as a string that produces the same hash. The contents of the original message would produce that same hash. A collision can result in disclosing the data used to generate the hash.

Re:Yet Another Overblown Crypto Hack

[TheRaven64]

For any given hash, there are an infinite number of strings that will generate that hash. There is one string that is the original message. Now, assuming that you select a new string at random that matches the hash, what is the probability that it is the same as the original message?

Re:Yet Another Overblown Crypto Hack

[Anonymous Coward]

> I'd argue that using any form of cryptography (save null) presents a barrier that the average hacker won't even attempt to overcome.

"For safety, do not count on your enemies not attacking, count on your invulnerable defenses." Sun Tzu

Re:Yet Another Overblown Crypto Hack

[m50d]

CSS wasn't secure when it was introduced, it's only there so that anyone cracking it is violating the DMCA. Although you can't make something which in a single form will always be secure, it should be possible to make a hash/crypto scheme which is secure as long as you keep extending the key - 128 bit hash/crypto key for now, make it 256 when computers get a bit faster, then 512 and so on. A good enough algorithm should stay secure when doing this.

Question about bit-flipping in SHA-1

[G4from128k]

If one flips a bit in a file, is it "easy" to find a correcting bit flip(s) that returns the file to its old hash value? If so, can one create a slightly modified copy of a file by flipping the bits one wants changed and then doing a series of counterflips (in an unused part of the file) to "undo" the effects of the nefarious change?

Re:Question about bit-flipping in SHA-1

[HeghmoH]

As far as anybody knows, no. If such a technique were known, this article wouldn't be very big news. Before this technique, the best way anybody knew of to generate two pieces of data with the same SHA-1 hash was to just try a ton of random data until you found two pieces with the same hash.

Re:Question about bit-flipping in SHA-1

[Tjoppen]

Serious hash algorithms usually want to have the answer to the zeroth question be "No. It's not easy"
As such, you can't easily(unless you're lucky) counter one bit flip by one or more counter-flips.
In fact, depending on the amount of "unused" data at your disposal, it may be impossible - like with 128b data resulting in a 160b hash, you have(on average) just a 1:2^32 chance of there being a collision at all.

Re:Question about bit-flipping in SHA-1

[lemonjus]

You could try doing that. What will happen is that you will look for 1000 years for the correct "bit flipping sequence" that will generate the same hash as the original file. comsider for example the time it takes to go over all possible flippings of 80 bits ...

If you flipped 1 bit of a message it doesnt means that another single flip will 'fix' the hash. A hash function is built exactly to prevent this kind of simple attacks.

This is the hole point of a hash algorithm like SHA, it is supposed to be extremely hard to find two messages that hash to the same value.

Re:Question about bit-flipping in SHA-1

[onemorechip]

comsider for example the time it takes to go over all possible flippings of 80 bits ...

That's not what was asked. If a collision could be found by flipping exactly two bits, as grandparent wondered, then for an N-bit message you have only N*(N-1) combinations to try. So the correct answer to his question is simply "No (at least, not in the general case)". There are bound to be some messages out there -- very long and boring ones, for the most part -- that have that property.

A hash function is built exactly to prevent this kind of simple attacks.

What a sweeping generalization! In fact, the hash function implemented by XORing blocks of the message has *exactly* the property in question, for all messages.

56 Hours?

[n0dalus]

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.

Is that assuming that that the collision will be found on the last (or in this case, 590,295,810,358,705,651,712nd time) try?
Because statistically it's just as likely you will find a collision on the first try as you are on the last try.

Re:56 Hours?

[Anonymous Coward]

Is that assuming that that the collision will be found on the last (or in this case, 590,295,810,358,705,651,712nd time) try?
Because statistically it's just as likely you will find a collision on the first try as you are on the last try.

Probably the time in which you've tried all the keys.
If it's an average, it would mean that you're guaranteed to find the key in 112h.
Either way, it's not really important as computing power grows quite fast, and both attacks are realistic even today.

BTW, I don't think SHA-xxx should be the new standard. They are all based on UFN, the same as MD4, MD5 and SHA and SHA-1, which have all been broken.
There are other alternatives, like Tiger and Whirlpool which should be considered instead.

Re:56 Hours?

[lseltzer]

The same is true of brute force, just with a larger set of possible data

Re:56 Hours?

[neiko]

ummmm...i don't know what statistics class you took, but in mine every time you eliminate a possibility the likeliness of finding a collision would be greater than the previous since there are a finite amount of possibilities. unless of course you are writing your algorithim to re-try already run values in the possibility that they will magically work later in the day?

Re:56 Hours?

[ptimmons]

If you're looking for a collision, you'll always (100% of the time) find it on your last try. Because after finding it, you have succeeded and discontinue looking.

Re:56 Hours?

[mmkkbb]

Actually, I think you are pretty much guaranteed to find a collision on the last try. (Assuming you stop when you find it, that is)

Re:56 Hours?

[STrinity]

ummmm...i don't know what statistics class you took, but in mine every time you eliminate a possibility the likeliness of finding a collision would be greater than the previous since there are a finite amount of possibilities.

Which is all well and good once you have the algorithim running. But until you do, all you can say is that the odds of finding the right answer will be the same for any given attempt, be it first, last, or 1,000,002,193,439,329,010.

Re:56 Hours?

[emidln]

I wouldn't discontinue looking. There are a lot of possible collisions for any given message, and I'd like to find as many as I can to increase the liklihood that one of them is useful.

The True Deadline

[AaronBaker2000]

It costs $38M to crack SHA-1 now. According to Moore's law, this will be cut by 25% every 3 years.

The cost of cracking SHA-1 in...

3 Years - $9.5 Million
6 Years - $2.3 Million
9 Years - $600,000
12 Years - $150,000
15 Years - $37,000
18 Years - $9,000
21 Years - $2,500

Re:The True Deadline

[thebes]

Why the hell to people quote Moore's law this way? Moore's law says FUCK ALL about chip speed. It talks about chip transistor density. We have already noticed that chip speed in the last while has slowed down. So where the hell do you get that in 18 months, Moore's law says it will cost 1/2 as much to perform the same calculations?

Re:The True Deadline

[JamesD_UK]

Moore predicted that the number of transistors per integrated circuit would double every eighteen months, not that the cost of computing would halve every eighteen months. More strictly speaking it's corollary that some people draw from Moore's law.

Re:The True Deadline

[thebes]

I like that my comment, that says something that people need to be reminded of, gets marked redundant, while the comment AFTER me gets marked insightful for saying the same thing. Yes, I said it with a bit more attitude, but anyone who is actually interested in computers or technology should understand the difference between "doubling transistor density" and "doubling processing speed". Is there anyone out there willing to support me on this?

Re:The True Deadline

[bpier]

Exactly!
Furthermore, even recent history has shown repeatedly that costs and computational throughput, (regardless of chip density and speed), will NOT double in 18 mos. ... unless of course some disruptive technology like the CELL processor complex or other comes along ..

Re:The True Deadline

[Anonymous Coward]

Don't expect any fairness in slashdot moderations... I've seen much more unfair ones (not to say this one isn't unfair...). There are a lot of idiots here :(

Re:The True Deadline

[timeOday]

For problems that can be decomposed and run in parallel, you can always use those extra transistors to make more processors (or more cores per processor). I assume checking billions of crypto keys can be done in parallel.

Re:The True Deadline

[ArbitraryConstant]

In this case I think the OP's post is accurate for first little while. As more and more SHA-1 breaking machines can be built on each chip, the size of the order will decrease. It'll decrease until the size of the order is too small for anyone to bother with (so it'll never reach $2500).

Re:The True Deadline

[mollymoo]

Nobody said anything about chip speed except you. The the figures are based on the EFFs DES cracker based on custom hardware. In that application double the transistors does pretty much mean double the speed.

Re:The True Deadline

[Alsee]

Also note that that is to be able to crack it in 56 hours. However if you are willing to invest a year in cracking something it drops from $38M in hardware to a less than a quarter million in hardware. Note that Trusted Computing security relies on SHA-1. I don't happen to have a quarter million in hardware, but I sure as hell would be willing to spend a year to defeat Trusted Computing and I'd be more than willing to donate my spare CPU cycles to a SETI@HOME distributed project to defeat Trusted Computing.

-

Re:The True Deadline

[kabbor]

I think you both are drawing corollaries from Moore's `law', although I think Aaron's is closer. Moore's famous paper was more about cost than count.
"The number of transistors per chip that yields the minimum cost per transistor has increased at a rate of roughly a factor of two per year."(artechnica.com) for full article.

Theoretical security concerns...

[Temporal]

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.

Re:Theoretical security concerns...

[NotoriousQ]

Ummm. No. It is because given any string, I can produce another string with the same hash faster.

And yes you do sign gibberish...It is called keys, which are used for encrypted communication. Now I can produce the key with the same hash as your key faster, and (depending on session speed) I can substitute my key for your key.

Now -- all this only means that I can do it about 2048 times faster...not by much, and assuming there are no other weaknesses...the sha-1 hash continues to be pretty good. The increase in computing power makes all hashes absolete eventually, and this change only means that SHA-1 will be absolete faster.

And you are right -- if you have another security hole, then it is irrelevant if SHA-1 is broken or not....But consider this: a typical hacker does not know about your specific security hole, but he knows of SHA-1 hole. Sometimes it is easier to just exploit a known hole, as opposed to try to find one that is easier to exploit.

Re:Theoretical security concerns...

[Mike Schiraldi]

The increase in computing power makes all hashes absolete eventually, and this change only means that SHA-1 will be absolete faster.

Obsolutely right!

Re:Theoretical security concerns...

[Anonymous Coward]

Being able to produce collisions (in a reasonably
short amount of time) is actually a practical
problem. Consider the following set of texts:

I certify/confirm that I owe Mr/Mister X the
amount of 100 US Dollars/$ ...

In this manner many different texts with identical
meaning can be produced. Now we just need one
single of them to hash into the same hash value as
any of the above possible texts with 100 replaced
by 10000.

Re:Theoretical security concerns...

[timeOday]

Ummm. No. It is because given any string, I can produce another string with the same hash faster.

Eh? That contradicts what I've heard, which is that only carefully chosen numbers have the easy-to-find collisions.

Meaning that to more easily attack my encryption key, you'd have to be in a position to choose it in the first place.

Re:Theoretical security concerns...

[swillden]

It is because given any string, I can produce another string with the same hash faster.

No, that would be a pre-image attack. This is a collision attack. To perform it, the attacker needs to be able to choose both strings.

Re:Theoretical security concerns...

[bcrowell]

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"

It might not be that much harder to generate a collision like this:

• I, John Smith, agree to sell my coin collection to Fred Jones for $10. -- JonesCo internal business form bma p3 rjphta,-9p.u2#H50982u.yha,cp. hxasnip

and

• I, John Smith, agree to sell my nubile teenage daughter to Fred Jones for $10. JonesCo internal business form BUEQXBBX2 jma93#9g5xbaida htuEXOAhkra1255,y

And if cryptographers are finding stronger and stronger attacks against SHA1, it's foolish to assume the attacks won't get any stronger.

Re:Theoretical security concerns...

[NotoriousQ]

You are probably right...the 2^69 confused me.

Oh I see. So this means that I can generate a colliding pair in 2^69, but I have to generate pairs of strings without fixing any of them. Interestingly enough...if the hash is perfect then the collision attack and pre-image attack would require the same computational complexity....which makes me think is usually not the case given any hash function in P memory and time.

Obviously it is the case in the perfect hash function...but the only perfect hash that I can think of requires exponential space.

Re:Theoretical security concerns...

[mre5565]

Ummm. No. It is because given any string, I can produce another string with the same hash faster.

And yes you do sign gibberish...It is called keys, which are used for encrypted communication. Now I can produce the key with the same hash as your key faster, and (depending on session speed) I can substitute my key for your key.

Now -- all this only means that I can do it about 2048 times faster [...]

Please clarify something for me before I panic. You say the attack is 2048 times faster. I gather you get that figure from 2^80 / 2^69. 2^80 is the number of operations to brute force attack SHA-1, and 2^69 is the new number of operations required to attack SHA-1.

Let's look at 2^80. Where does that come from? It is the square root of 2^160. Why is that significant. Because 2^80 is number of operations required to perform a Birthday Attack on a 160 bit hash.

What is a Birthday Attack? It is merely that that if I run the attack program (which executes SHA-1) for 2^80 operations on 2^80 unique inputs (numbers 1 through 2^80 work just fine here, or generate 2^80 random messages; as long as they aren't longer than your key size), I have a 50% chance that two numbers will produce the same hash. Not a pair of numbers you pick, but some pair out of a set of size 2^80 (or less).

So if you are relating 2^69 to 2^80, then I conclude you are saying that 2^69 is the new Birthday Attack computation cost for SHA-1.

Well then, you cannot, in 2^69 operations produce a key with the same hash as my key (unless you are going to con me into changing me key to the of the pair you found in the birthday attack. I'm not that stupid). More like 2^(2*69) = 2^138 operations.

Schneier, on his web site blog, says:

If you hashed 2^80 random messages, you'd find one pair that hashed to the same value. That's the "brute force" way of finding collisions, and it depends solely on the length of the hash value. "Breaking" the hash function means being able to find collisions faster than that. And that's what the Chinese did.

They can find collisions in SHA-1 in 2^69 calculations, about 2,000 times faster than brute force. Right now, that is just on the far edge of feasibility with current technology.

But perhaps everyone has it wrong; the 2^69 does relate to 2^160 (which is the number of bruteforce operations necessary to find a message with the same hash as a chosen message. If so, then this is a huge, huge, result, I would vehemently disagree with the quote: "It's time to walk, but not run, to the fire exits.". On the contrary, it's probably too late to survive the fire.

Re:Theoretical security concerns...

[swillden]

So this means that I can generate a colliding pair in 2^69, but I have to generate pairs of strings without fixing any of them.

That's it exactly. In the case of an unbroken hash that outputs 160-bit blocks like SHA-1, you'd need to generate 2^80 hashes, on average to find a collision. The reason this is 2^80 and not 2^159th is the effect of the birthday paradox.

Interestingly enough...if the hash is perfect then the collision attack and pre-image attack would require the same computational complexity....which makes me think is usually not the case given any hash function in P memory and time.

That's a very interesting statement. What do you mean by "perfect" and can you elaborate on how a hash that is "perfect" has the same collision and pre-image attack complexity? It seems to me that a "perfect" (my definition) hash that produces n-bit outputs should have no pre-image attack that has better than 2^(n-1) complexity, whereas the birthday paradox will allow a collision attack with approximately 2^(n/2) complexity (that's a really rough approximation, but it's close enough for most purposes).

Obviously it is the case in the perfect hash function...but the only perfect hash that I can think of requires exponential space.

Not so obvious to me, unfortunately, but it could be that I'm just slow. Not an infrequent occurrence, unfortunately :-/

What's the perfect hash function you're thinking of?

Re:Theoretical security concerns...

[puetzk]

No, if the hash is perfect the complexity of a collision attack is the square root of the complexity of a pre-image attack. This is known as the birthday paradox.

Re:Theoretical security concerns...

[rbarreira]

I'm sorry, but those two messages hash to a different value...

$ echo -n "bma p3 rjphta,-9p.u2#H50982u.yha,cp. hxasnip" | sha1sum
adaa573b7b0b0596713141391cd07d016b321a68 *-

$ echo -n "BUEQXBBX2 jma93#9g5xbaida htuEXOAhkra1255,y" | sha1sum
b07ad992aeb0963d19ee7cf52cf5f950c73b6ff4 *-

Re:Theoretical security concerns...

[Anonymous Coward]

Now we just need one single of them to hash into the same hash value as any of the above possible texts with 100 replaced by 10000.

Even you will be happy to replace 100 by any from: 9999, 9998, 10001, 10002, ...

Re:Theoretical security concerns...

[NotoriousQ]

Actually -- it is my mind that is turned off due to it being a Saturday probably. Should that be (2^n) and not 2^(n-1) for the preimage. It sounds like that if you have a 1 over 2^n probability of getting any string to hash to x, then your expected succeess time would be 2^x.

I even forgot that SHA-1 is 160 bit...and I keep thinking it is an 80-bit hash. You are obviously right...shoot I even forgot my favorite latin phrase for "everything is obvious once explained".

The perfect hash does exist, but it is unfeasable. It requires that there is a perfect secure storage of unlimited size...but the basic point of it is for every string generate a unique random number of x bits, and then store the the mapping of the string to the number. Given that number generator is perfect, the strings map uniformly over the entire space, and any string has exactly 1 over 2^x probability of mapping to the same hash, and due to complete random mapping, there can be no weakness in the mapping itself. Now -- since I made 2 mistakes already -- I think I will swallow any traces of remaining pride and immediately ask if there are mistakes in this hash. (assume no one can read the actual mapping)

However, you still get the 2^x preimage attack, and 2^(x/2) complexity for collision due to birthday paradox.

Now obviously I am not an expert in the field...but wouldn't 2^(n/2) mappings result in a huge huge list of strings, which then you have to proceed to find a matching. My mind is quite slow right now ... but how much time would it take to search for which of the 2^(n/2) strings you generated actually collided?

My guess is that if you use any datastructure hash or a trie comes to mind, then you will need the amount of memory to store each of the 2^(n/2) strings that are generated....which seems huge. Is this even feasable....I guess one could reduce the strings to their ordinal numbers and then store those in the hash....but then you would still get 2^69 integers in the hash....still does not sound feasable....

Thanks.

Re:Theoretical security concerns...

[amchugh]

So is it a practical security concern if an attacker maps out a table of collisions ahead of time, and lurks in wait for a key that uses a colliding hash?

Re:Theoretical security concerns...

[NotoriousQ]

Do not panic and read the sibling thread. I am in the wrong here...2^69 is the birthday attack... but for some reason my mind changed the sha-1 to 80-bit and the pair collision to a specific string collision search....

I am clearing up my mind in the your posts sibling.

Re:Theoretical security concerns...

[Nik13]

I can only agree. I still see lots of things using plain text passwords, and even sometimes non-secured access databases, and most of the time it's never caused any problems.

Using a salted SHA1 hash, properly stored, keeping keys for other things like DB connection strings secure (encrypted) and just good general practices are the main thing.

It really wouldn't matter if I used SHA-4096 if the data isn't even secure (and by that, I also mean the data that the login is protecting) or if I can login by just using the old ' or 1=1 (old and very basic sql injection method, but amazingly works too often...)

38M is still a lot of $. One would have to have quite a target if he's willing to spend any kind of money like that to break a hash. In a lot of apps (web or not), it wouldn't take much to get access otherwise...

Sure, it's not just for password hashing, but the whole "abandon ship" thing is very overrated. It looks much to me like changing your dealbolts to some really secure device, while you just may have left your windows open.

Re:Theoretical security concerns...

[Ed_1024]

I understand that there will always be collisions in any hashing algorithm when the data being hashed is larger than the hash. Is it possible that for a given hash value there is unique data, i.e. no collision? Also is it possible that there are hash values which cannot be generated from ANY data? Rather esoteric questions (to me) but there seem to a lot of knowledgeable posters on this thread who could answer...

Re:Theoretical security concerns...

[dbullock]

I don't have a nubile teenage daughter, just two sons. So this exploit won't affect me.

Re:Theoretical security concerns...

[Anonymous Coward]

Ummm. No. It is because given any string, I can produce another string with the same hash faster.


Your willingness to make such authoritative statements when you clearly don't know what the fuck you're talking about sure is interesting.

Re:Theoretical security concerns...

[swillden]

Actually -- it is my mind that is turned off due to it being a Saturday probably.

:-)

Should that be (2^n) and not 2^(n-1) for the preimage. It sounds like that if you have a 1 over 2^n probability of getting any string to hash to x, then your expected succeess time would be 2^x.

Sort of. Usually we talk about the mean expected time to success, and sometimes you get lucky. You could get really lucky and find it on your first try, or you could get really unlucky and search the entire space before finding a match. On average, you have to search about half of the space, so 2^(n-1) rather than 2^n. Likewise, the approximation of 2^(n/2) complexity for a collision attack is the number of operations required to give you a 50/50 chance of having found a match.

The perfect hash does exist, but it is unfeasable. It requires that there is a perfect secure storage of unlimited size...

Ah, I see. Yes, a uniform random mapping is indeed a perfect hash, and is actually the one used most often to model a real hash when analyzing the properties of a cryptographic protocol.

Now obviously I am not an expert in the field...but wouldn't 2^(n/2) mappings result in a huge huge list of strings, which then you have to proceed to find a matching.

Not having read either this paper or the preceding ones (about MD5), I can't say how many results you have to store, so it's hard to know how many you have to search through. It could be a real problem, though. I suspect that the people who estimated the cost of building a SHA-1 collision finder did read the paper and did take space and search time into consideration -- but I wouldn't put money on it.

Re:Theoretical security concerns...

[NotoriousQ]

I am slightly confused over one thing....to do any attacks aren't you searching the string space rather than the message space....which would allow for replacement (duplicates) in the message space.

So in effect -- you could end up searching through unbounded number of strings before finding something that hashes to x. So I do not see where halfing of the space comes from. Each string has a 1/(2^n) probability of hashing to x -- therefore the expected time to success is 2^n.

and I am confused over the term mean expected time to success.....would not that be E(E(X=x)) = E(X=x), since each run of X is independent. So for independent X, mean expected time to success and expected time to success are the same thing.

What am I missing. Sorry to keep bugging you...but it feels like I need a good refresher in statistics.

Thanks.

Re:Theoretical security concerns...

[cartman]

The difficulty is, a random string of bytes appended to the end of a signed message would call into question the authenticity of the signature. It would make the signed document appear like someone was forging the signature by cracking the digital signature scheme.

With any reasonably worded English contract, it's entirely possible that there doesn't even exist another reasonably worded English contract that would collide with the same hash and that's useful for the cracker. Unless, of course, the second contract has quasi-random bytes attached to the end of it; but again, that calls into question the authenticity of the signature.

I certainly agree with you that they're finding stronger attacks against SHA-1, and the trend will likely continue. However they're a very long way from finding useful attacks.

Schneier is taking both of those things into account. He's assuming that we're a long way from useful attacks, but useful attacks may become possible far in the future. That's why he recommends that we gradually migrate ("walk, don't run") away from SHA-1.

Re:Theoretical security concerns...

[tigersha]

If your contract is written in ASCII, this is a valid point. If it is written in any binary file (PDF, Word) as would be likely or if it contains pictures (company logo maybe),no way.

You can insert gibberish in those to match whatever you want and nobody would notice. Or add the gibeerish at the end of the internal picture. Most programs discard the rest of an image file after they have decompressed what they should have (because the sizes are specified in the headers So they know then they have all the pixels they simply stop).

Re:Theoretical security concerns...

[Effugas]

Ahem.

www.doxpara.com/t1.html
www.doxpara.com/t2.html

Throw both through md5sum and tell me we're not worried about something legitimate.

Re:Theoretical security concerns...

[swillden]

I am slightly confused over one thing....to do any attacks aren't you searching the string space rather than the message space....which would allow for replacement (duplicates) in the message space.

Yes, I knew I was glossing over that. To be honest I haven't thought that through thoroughly myself, but I think the idea is that if the hash is a good one, collisions are rare, so although your search of the input space will generate some collisions, it won't generate many of them, and therefore won't increase the search time significantly. I saw some discussion of this topic in a paper, once, but I don't remember it well, and I might be mistaken.

In short, it's possible that the collisions you find while searching increase the complexity to 2^n or even higher, but I have a vague recollection of seeing some analysis that says this is unlikely, given a good hash (i.e. something that approximates a random map).

and I am confused over the term mean expected time to success.....would not that be E(E(X=x)) = E(X=x), since each run of X is independent. So for independent X, mean expected time to success and expected time to success are the same thing.

You're correct, I was misusing the terminology to try to clarify the point... doesn't appear that I succeeded :-)

it feels like I need a good refresher in statistics.

Me, too. Or at least the mental energy to actually think hard about how to estimate the expected success time for a pre-image attack against a random map (or facsimile thereof).

Re:Theoretical security concerns...

[NotoriousQ]

I was misusing the terminology to try to clarify the point

You are not the only one. By message space -- I meant hash space. (So it may have sounded like I said the opposite of what I was trying to say)

And the more I think about it the more I think that it is 2^n. Finding a hash does not yield a string....hence you end up searching for strings....not hashes.

But then again -- there may be a different way to do a brute force attack, that I am not thinking of. I will probably leave this topic at this point , and leave it to real mathematicians to sort this out. I never was strong on counting, and unfortunately it shows.

Thanks for the comments.

Re:Theoretical security concerns...

[Sebastian Jansson]

It might not be that much harder to generate a collision like this:
I, John Smith, agree to sell my coin collection to Fred Jones for $10. -- JonesCo internal business form bma p3 rjphta,-9p.u2#H50982u.yha,cp. hxasnip
and
I, John Smith, agree to sell my nubile teenage daughter to Fred Jones for $10. JonesCo internal business form BUEQXBBX2 jma93#9g5xbaida htuEXOAhkra1255,y

Oh, and that for just 36 million? You know, for 36 million there are lots of ways you can screw someone over, easier ways...

Re:Theoretical security concerns...

[bcrowell]

Oh, and that for just 36 million? You know, for 36 million there are lots of ways you can screw someone over, easier ways...
Stronger and stronger attacks are being discovered against SHA1. If the trend continues, the price of the CPU time will become much less than that.

Re:Break only affects carefully constructed messag

[arkhan_jg]

Yes, but say someone creates a document (such as a contract) for you to digitally sign.

If they're prepared to spend a realistic level of time on it they could create two of them that hash to the same thing, with a small but effective change to the second.

You sign the first with SHA-1, but your signature also matches on the second, putting you in a weak position when you try and claim "I didn't sign _that_!"

The time/money requirements to do this aren't really practical yet, but they will be soon.

As the sub says, time to start shifting off SHA-1.

Re:2000 times faster?

[Eric604]

it wasn't funny and the moderation is disturbing

remember enigma..

[dirtyforker]

Encrypting something is many orders of magnitude less complex than breaking the encryption. Moore's Law means that more complex encoding becomes practical at an exponentially faster rate than the ability to break it. Today's encryption is far more secure than anything in the past inspite of all these advances in code-breaking. Of course this doesn't stop people from using old methods which were once secure but now are not...

Re:Break only affects carefully constructed messag

[Anonymous Coward]

You don't understand the issue. Digital signatures are still safe.

but...

[boeserjavamann]

its just a collision attack, not a preimage attack, so for encryption of an email there is still nothing to fear as far as i understood the problem.

Follow-on work

[fhmiv]

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.

Re:Follow-on work

[Lisandro]

Yes, but again: in time. Unless someone comes up with a way to hash SHA-1 one millon times faster than now, it's still a damn good hash algorithm (hard to crack, fast, and easy to implement). Never mind it's uses beyond criptography.

I can see the importance of this announcement -it IS a major one, but if someone thinks he has to dump SHA-1 inmediatly because script kiddies might mess with his computer, he's far away from the truth. 2000 times faster than "takes a long fucking time" still takes a long fucking time :).

Re:Follow-on work

[God! Awful 2]

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.

But that's not what seems to be happening. We've seen the same basic hack applied to multiple algorithms now, but we haven't seen the Md5 hacks improved for MD5.

-a

Re:2000 times faster?

[Anonymous Coward]

FIRST CORRECTION

omg 2^11 = 2000 noob

Re:2000 times faster?

[Anonymous Coward]

I'll take that bet! (And you owe me $64 if you lose.)

Here is the paper!!

[rbarreira]

http://netlab.fe.up.pt/~ei01024/sha-1/

Re:Here is the paper!!

[rbarreira]

Well, actually it's only a research summary, sorry... But, it is something :)

Re:Break only affects carefully constructed messag

[Everleet]

And you only have to construct 2^69 different contracts with the same meaning.

Creating pseudo-random numbers that hash to the same value != making any arbitrary document hash to the same value.

orders of growth

[oreaq]

No. It means that it took 2^80 "computations" and it now takes 2^69 "computations".
O(2^80) = O(2^69) = O(1). See for example http://mitpress.mit.edu/sicp/full-text/sicp/book/n ode17.html.

Re:orders of growth

[IWannaBeAnAC]

In computational science and cryptography it is common to use notation O(n^x), but it doesn't mean the same thing as Big-Oh notation, it just means 'order-of-magnitude'. Its usually clear from the context what is meant: big-oh notation describes the asymptotic behaviour as a function of input size. In this context, the input size is the length of the hash and that is fixed.

Re:orders of growth

[oreaq]

Do you mean that O(n^x) is a notation for zeroth order approximation to base n "in computational science and cryptography"? I've never before seen it used like this. Do you have any examples?

Re:orders of growth

[IWannaBeAnAC]

Yes, that is basically the idea. I have seen it used before, but I havn't been able to find some examples on the net, it seems to be a really hard expression to search for.

Re:orders of growth

[Rolken]

Does it really MATTER? There're enough geeky things to argue about that actually have a point instead of sniping at someone's syntax. You obviously understood what he meant, and he provided reasoning for it, so whether it's right or not, what's the point in debating it? If it's disprovable with internet sources, he can do it himself without your help. Trying to puff up your ego by "pwning" people with your amazing knowledge of technical terms? Please.

On the other hand, if you'd like to discuss, say, the social implications of the advancement of AI, I'm all game.

Thinking ahead (out loud)..

[bAdministrator]

..a (new) system that handled user authentication (and obviously registration) would also store information about which hash code algorithm was used at the time the user registered.

SystemHashCoding = 1 = MD5
SystemHashCoding = 2 = SHA0
SystemHashCoding = 3 = SHA1
SystemHashCoding = n = x

UserHashCoding = 3

The UserHashCodingData field would be extended to accomodate longer values in the future.

The update would be applied when an existing user with a different hash coding changed her or his password.

whirlpool anyone?

[ubiquitin]

SHA-2 in 256 and 512 bit flavors isn't the only alternative folks. Among other nifty hashes, there's whirlpool: Linux 2.6 kernel crypto API entry for whirlpool and a page with whirlpool details.

Re:2000 times faster?

[Uber Banker]

Dude, I may be the first to point this out:

While the bumbers are only 11 difference yes, 69 is a much slower method for most 80, though I'm not sure its 2000 either.

Unrealistic?

[Rollie Hawk]

One-way hash functions are supposed to have two properties. One, they're one way. This means that it is easy to take a message and compute the hash value, but it's impossible to take a hash value and recreate the original message. (By "impossible" I mean "can't be done in any reasonable amount of time.") Two, they're collision free. This means that it is impossible to find two messages that hash to the same hash value. The cryptographic reasoning behind these two properties is subtle, and I invite curious readers to learn more in my book Applied Cryptography.

If I'm reading this right, then he's saying
1. The hashing function must be 1-to-1 and onto
2. The hashing function cannot be invertible

How is this possible?

Re:Unrealistic?

[Derleth]

Read the whole comment: By "impossible", Bruce means "so hard it isn't worth trying." Obviously, there is no way to make an absolutely one-to-one correspondence between arbitrary-length messages and fixed-length hashes. The idea, therefore, is to make it so difficult to generate two messages with the same hash that it isn't worth anyone's effort to try.

Absolute security is almost always a chimera. You can only really achieve it with one-time pads, which aren't practical for the vast majority of cases. So you try to make things so difficult to crack that by the time anyone has succeeded, nobody still cares about the security of that message. Ideally, therefore, breaking one message does nothing to help you break any other message.

The crack of SHA-1 does help an attacker break any security system that uses SHA-1 by making it much easier to generate two messages that map to the same hash. This kind of thing makes cryptographers sit up and take notice, and hopefully develop some new algorithms. We have algorithms better than SHA, but until now nobody's had much reason to use them. This should change that.

Re:Unrealistic?

[steve_stern]

If I'm reading this right, then he's saying
1. The hashing function must be 1-to-1 and onto
2. The hashing function cannot be invertible

When the article says "impossible to take a hash value and recreate the original message", he really means "infeasible to take a hash value and recreate any message that has that hash value".

Of course its absolutely impossible to recreate the original message, since there are multiple messages that hash to that value. But in almost every use of hash functions, creating any other message with the same hash is good enough to be considered "broken". Thankfully, that hasn't happened yet.

Re:Unrealistic?

[Anonymous Coward]

The crack of SHA-1 does help an attacker break any security system that uses SHA-1 by making it much easier to generate two messages that map to the same hash.

Wrong. If this is really a problem depends very much on the protocol involved and the threat scenario.

PI hash anyone?

[Anonymous Coward]

Since we have the formula to extract digits of PI, what about this algorithm:
n = 0
do while not eof(data)
byte = next input data
for each bit in byte.0-7
n = n * (bit + 1) + 1
n = n + digit at PI[n]
next
loop
hash (digest) = 32 digits at PI[n...n+31]

Could one reconstruct the data by searching for the hash in the digit sequence of PI? Probably not, because there are several ways to get to a certain digit number.

"begs the question"

[Anonymous Coward]

... does not mean what you think it means. Look it up.

Re:"begs the question"

[Anonymous Coward]

Prescriptive grammar is passe. Look it up.

Re:"begs the question"

[Fahrenheit 450]

Is that why they're teaching 1337 speak in grade schools these days?

Feel free to adjust your ideals to the lowest common denominator if you want, but I'll try to maintain some standards.

Re:"begs the question"

[DrSkwid]

it look prescriptive. passe is Grammar up

sure You ? are

Re:"begs the question"

[Anonymous Coward]

You mean passé, right?

Re:"begs the question"

[Anonymous Coward]

Has nothing to do with grammer.
http://www.wsu.edu/~brians/errors/begs.html

Re:"begs the question"

[hunterx11]

I'm willing to accept changes in the language. I know that someday "alright" will be considered a perfectly cromulent word, for example. But some changes make no sense and will never catch on. "Me and my friend went to the store" will never be proper because it makes no logical sense. Likewise, the phrase "begging the question" already has a well-defined meaning disparate from "asking the question." If "begging the question" meant "asking the question" in formal speech, how would one actually say "begging the question?"

Several times on /. I've defended the use of the word "virii," not because I think it will ever be acceptable in formal speech (it won't), but because not all speech has to be formal. Still, using "begging the question" like this stems from ignorance rather than playfulness. It is similar to saying "irregardless." I don't think anyone should conceited and insult people misuses like this, but there's nothing wrong with politely pointing it out. After all, learning from mistakes on /. is a lot less embarrassing than the equivalent in real life.

Re:"begs the question"

[Gil-galad55]

Or perhaps it does: Bastardising English

Re:"begs the question"

[Anonymous Coward]

Me and my friend went to the store" will never be proper because it makes no logical sense? It doesn't make logical sense? When someone says to you "me and my friend went to the store", you obviously understand that they mean "my friend and I...", thus it does make logical sense.

Re:"begs the question"

[Anonymous Coward]

I say we should bastardize everything... that way, no one will know what we are saying... for example, I'm going to bastardize the phrase:

"You are an idiot."

To mean something else entirely. It doesn't mean what you think it does now!

Re:"begs the question"

[hunterx11]

Went is an intransitive verb. Even if it were transitive, it would hardly make sense for me to be the object if I'm the one going somewhere. What the phrase means makes perfect sense, and any native English speaker will understand it without any confusion. But what the phrase actually says is nonsensical and impossible.

Say for example that someone asks, "Who here reads Slashdot?" To reply "me" is technically incorrect. Saying "I do" makes perfect sense, but saying "I" is awkward. In this case, however, one could make an argument for "me" being acceptable because it is used disjunctively (that is, not with ellipsis but rather independent of any verb). This is not standard formal usage, but there is some logical process whereby it foreseeably could be at some point in the future. But for "Me and my friend went to the store" there is no such conceivable process unless English were radically different.

Re:"begs the question"

[rbarreira]

I'm not english speaking. Now your link has left me really confused. I thought that the "begs the question" war was about two alternatives for it's meaning:

a) makes us think of the question (without explicitly asking it)
b) the fallacy we all know (assuming the thing being proved)

According to your link, the war seems to be about those two alternatives instead:

a) explictly asks the question
b) makes us think of the question

So what's the deal after all? I thought I understood what those wars were about...

Re:"begs the question"

[jonadab]

> "Me and my friend went to the store" will never be proper because it makes
> no logical sense.

You clearly have not been paying close attention to the direction the English
language has been headed. Noun inflection has been in the process of dropping
out of the language for several hundred years now, because, frankly, we
mostly don't need it; we have word-order mechanisms for indicating case, so
the inflection is redundant. We've already lost the distinction between the
subjective and objective (not to mention singular and plural) in the second
person pronouns; we're now beginning to lose the distinction between
subjective and objective in the first person singular and are already well
on our way to losing the inflections for gender and number in the third
person. Chart follows...
1650:
1st I, me, my/mine we, us, our/ours
2nd thou, thee, thy/thine ye, you, your/yours
3rd m he, him, his they, them, their/theirs
3rd f she, her, her/hers they, them, their/theirs
3rd n it, it, its they, them, their/theirs
1950:
1st I, me, my/mine we, us, our/ours
2nd you, you/ you/yours you, you, your/yours
3rd m he, him, his they, them, their/theirs
3rd f she, her, her/hers they, them, their/theirs
3rd n it, it, its they, them, their/theirs
2150 (projected):
1st me, me, my/mine we/us, us, our/ours
2nd you, you/ you/yours you, you, your/yours
3rd they, them, their/theirs they, them, their/theirs

We might also lose the attributive possessive and keep only the predicate
form of it, reusing the same form as the subjective and objective for the
attributive possessive. You can already see that starting to happen
colloquially; for now it still sounds very wrong to most of us, but the
change has already begun, albeit gradually.

FWIW, I agree with most of your points in principle, including the one
about begging the question, but I felt the need to point out that the
distinction between the subjective and the objective is more and more
carried only by position in the sentence, rather than by form. The days
when you can say "Him I like" or "Him like I" or "Like him do I" are
rapidly passing; it already sounds pretty odd and Yoda-esque -- but if
we don't do that any more, then we don't need distinct forms for the
subjective and objective case any longer; they are archaisms and will pass
out of use.

Re:"begs the question"

[pjt33]

Likewise, the phrase "begging the question" already has a well-defined meaning disparate from "asking the question." If "begging the question" meant "asking the question" in formal speech, how would one actually say "begging the question?"

You would still say "begging the question", but intransitively. Whenever "begging the question" is used as "asking the question" it is transitive: thus there need be no confusion.

Re:"begs the question"

[axlrosen]

The opposite of prescriptive grammar is descriptive grammar - not no grammar.

Re:"begs the question"

[DrSkwid]

"Him I like" is still in common usage in the UK, particularly about DrSkwid =)

Re:"begs the question"

[Anonymous Coward]

Grr, first we see a post with poor grammar, then we see a complaining post about the poor grammar because it's modded up... *sigh* Sometimes it's best to just shut up. Or save the mod points.

Re:"begs the question"

[Spetiam]

I didn't bother following the "bastardizing English" link, but whatever it says, ignore it, because you understand the "to beg the question" controversy correctly.

The bastardized definition of "begs the question" was spawned in the minds of ignorant people and draws life from the thick-skulled arrogance of the same.

Re:"begs the question"

[rbarreira]

Thanks for the clarification :)

Re:"begs the question"

[neitzsche]

Languages get more complex over time, not less complicated.

*Especially* when there is no authority dictating what is right or wrong about a particular language.

Re:"begs the question"

[jonadab]

> Languages get more complex over time, not less complicated.

English is getting more complicated, but in other ways. For example, our
vocabulary is ever heading in the general direction of hyperagglutinativity,
to say nothing of the sheer vast impressive array of available words, far
more words than any other human language; most of these words have been
added to the language within the last three hundred years, some by importation
from other languages, some by recombination of extant roots and affixes, and
of course some by new coinage. For example, a hundred years ago, the phrase
"synergistic remediation" would never have been uttered.

Also, word order has increased in importance and to some extent changed its
meaning. Punctuation has also gained much importance and complexity. The
case inflection system, however, is (quite gradually) going away. Already
most people who speak English don't understand the difference between "thou"
and "thee" or "you" and "ye", for instance, or "dost" and "doth", or cetera.

Advice: use toolkits like SASL

[ites]

All crypto algorithms age, and even if the news of SHA-1's death is somewhat dramaticised by people who make their living from security work, it's important to see _all_ crypto algorithms as temporary shims.

That is why anyone developing new protocols and products that rely on security should use SASL, which abstracts the crypto layers in such a way that it's easy to change them over time.

SASL is an IETF standard and there are open source implementations like Cyrus.

Re:Advice: use toolkits like SASL

[Anonymous Coward]

All algorithms are temporary shims? Really?

Block ciphers have mostly survived the test of time, except for the fact that they (DES especially) used insufficient key lengths for quite some time.

Most modern block ciphers have not been compromised in the sense that there would be known attacks significantly easier than brute force. Seriously, name one post-DES block cipher that has been widely trusted but later compromised.

Re:Advice: use toolkits like SASL

[Anonymous Coward]

name one post-DES block cipher that has been widely trusted but later compromised.

Not being able to name compromised block-ciphers is not proof of their permanant security. It means they're practical today.

Key lengths are part of the algorithm (if we can put hair-splitting semantics aside), so all algorithms that are practical today will be weaker tomorrow. -Always- by brute force, and rarely by an intelligent compromise. Pretty simple, really.

Re:Advice: use toolkits like SASL

[evilviper]

That is why anyone developing new protocols and products that rely on security should use SASL, which abstracts the crypto layers in such a way that it's easy to change them over time.

It may be useful for negotiating the encryption of network protocols (though protocols like SSH already have equivalent functionality), but it really won't help with hashes.

SSH is perhaps a good example. Sure, if 3DES is broken tomorrow, you can just disable it, and continue connecting to other SSH servers, using AES, Blowfish, etc. However, if there is a problem with any component of RSA/DSA, you can't just swap them out... You have to create new keys with something else, and then manually distribute them to every place you had the old one.

Same goes for any public-key encryption, and for hashes as well. P2P programs that use SHA-1 to identify files can't just switch. They use the SHA-1 hash as a unique identifier, and there's practically no way to add an abstraction layer above that. If they switch from SHA-1, sites like bitzi.com have no choice but to start from scratch... You can't create a RIPEMD hash from an SHA-1 hash, so they essentially have to erase everything and start from zero...

How would you hope to abstract the use of hashes in any reasonably effecient way?

Price

[Uber Banker]

The £38mn is to build the machine. It is in 1-time use for 56 hours.

There are 8776 hours in a year. Assume the machine has a life of 3 years before it becomes obselete. That means (discouting TVM at 0% for simplicity) the machine can do 470 problems of this type in three years, breaking even at a little over $80 per problem.

Damn that just got a lot lot cheaper.

Re:Price

[Uber Banker]

Apologies, $80k per problem.

Re:Price

[Anonymous Coward]

Can i get a loan in your bank?
I love dealing with people who forget '000' or 'K's at the ending of amounts on documents

Re:Price

[KarmaMB84]

Actually, as long as people continue to use SHA-1 for more than 3 years and they can keep the machine running, they can continue to work a lot more problems. ;)

Re:Price

[Fenresulven]

£80851 per problem actually.

Re:Price

[InvalidError]

$80/problem?

My calculator must be broken, it says $80k.

3.8 * 10^7 / (4.7 * 10^2) = something * 10^5

0 |something| 10
(0.8 in this case)

I think it is a safe bet that my calculator must be right.

Re:Price

[Uber Banker]

Indeed, but we should also discount future revenue streams, etc. In 3 years the computation power of the machine will become obseleted meaning it would take a lot longer to work on a problem than a competitor machine, and would have to reduce the price of its service significantly. Usually high-power computers are written down in company accounts to zero value over 2-5 years.

Perhaps we should risk-weight the investment too... this is all getting technical and I fear we may incriminate ourselves on planning to set up a money-earning hacking system, which is probably illegal under some DMCA or 'terrorism' law.

Of course with widespread GRID computing around the corner we'd pay for things in computational units which makes it all a lot simpler.

Re:Price

[Anonymous Coward]

Since when did the pound sign work in Slashcode?! Slashcode is maintained, updated and extended?!

I need a stiff drink.

Re:Price

[MPHellwig]

yeah, html is cool huh...

Re:Price

[pangur]

Uber Banker: "...breaking even at a little over $80 per problem." ...

Uber Banker: "Apologies, $80k per problem."

__

Mr. Banker, I'd like to talk to you about refinacing my home loan. I'm sure you can give me a great deal. :)

Re:Price

[tonsofpcs]

Yes, but if you solved the first 3 years worth of problems seeing it costing 80k per problem, then the next problem would only cost you the power needed to run the machine, your 38M is already paid off.

Re:Price

[Uber Banker]

While I am not a mortgage broker, how about I offer you a load of $80 for your new home with $80k repayable over 20 years at a fixed rate of 4.5% p.a.? I'm sure I could rustle that deal up with my compliance department.

Re:Price

[pangur]

4.5%!?! Sign me up!

Hee hee.

Re:Price

[YU Nicks NE Way]

The parent offers a loan

of $80 for your new home with $80k repayable over 20 years at a fixed rate of 4.5% p.a.? I'm sure I could rustle that deal up with my compliance department.

Really? Hey, cool! Listen, I have this mortgage I hold against a bridge in Brooklyn. The borrower has been really reliable with her monthly payments -- d'you think your compliance committee would be able to see their way clear to you guys buying the loan from me? I'd sell it for, say, a third of face.

Clearing up some myths...

[MLopat]

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.

Re:Clearing up some myths...

[Anonymous Coward]

Well said. There's too much FUD on this site.

Re:Clearing up some myths...

[Anonymous Coward]

Nice to hear from an expert once in a while and not some kid that has scared himself into thinking his porn habits maybe found out

Re:Clearing up some myths...

[T-Ranger]

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

Thats great if your a math geek and are doing purely theoretical work. Or if you are still evaluating crypto technology and put off investing in something untill now. But for the everyone else (which is everyone) who already have stuff protected with SHA-1, then it is someting to be worried about. Not panic, but be worried. And sory, it does compromise the security of things that use SHA-1. If the functionality of SHA-1 doesnt effect the functionality of the whole system, then it wouldnt be used at all. Since it is used, it must do something, and now it does that something not as well as we thought.

Does this make a practical difference? No. Was the discovery of a flaw inevitable? No, but the ability to brute force break something is always there.. The effects of the flaw (breaking it) was alwayhs there; this just shortens the timeframe where this is possible.

Re:Break only affects carefully constructed messag

[marcello_dl]

I presume that finding two colliding contracts both written in a meaningful and legally binding language is harder than finding a simple collision.

Re:2000 times faster?

[isorox]

FIRST CORRECTION

15th actually, and you were wrong anyway.

It doesn't matter that there is still 2^69 barrier

[Anonymous Coward]

When the understanding on a domain starts to gather - in other words the nut to crack - it usually does all the way. It's quite commong to knownledge. In such a notion for instance going to SHA-2 would be moronic and keeping using SHA-1 plain suicidal.

This is a lot worse than many people understand. 38 millions for a cracking machine? Yes, providing there isn't someone who knows one tiny bit more from the domain an has took off more from the complexity. For instance 2^40 would be a disaster. The sad fact is that it is near. Way too near for anyone who really cares.

Re:Break only affects carefully constructed messag

[Sweetshark]

1) Would someone be willing to pay $38 million (assuming this is correct) to get my credit card number - probably not.
He needs to pay the 38 million only once and can get a million every second day - sounds like a good deal. But OTOH his interest might be different, as you said in your bank merger example. However, there are things that are worth a lot although it is not as obvious as in this case. (Research stuff leading to military and industrial advantages.)

So that would be what...

[Anonymous Coward]

The slashdot secondary effect.

Give it a rest

[0x4a6f6e43]

>In 18 months, the cost should go down by half. Nope. It will not. >Moores Law Never said your super computer cost would half and speed double every 18 months. Give Moore a rest.

Re:2000 times faster?

[Anonymous Coward]

An excellent troll. You got an enormous amount of gullible idiots to show their 'intelligence' by correcting you. Pure genius.

Making collisions easy

[Sweetshark]

I presume that finding two colliding contracts both written in a meaningful and legally binding language is harder than finding a simple collision.
Write the contract in MS Word and use huge uncompressed BMPs for the company logos. You have instantly enough space for subtile changes to create collisions.

Re:Making collisions easy

[rahard]

Write the contract in MS Word and use huge uncompressed BMPs for the company logos. You have instantly enough space for subtile changes to create collisions.

1. Is it practical? (I don't think so.) How big is an image to be considered "huge" and create a dent?
2. Wouldn't adding more data create a better separation? (ie. avalance effect?)

I am still unconvinced that adding more data automatically increase the probability of collision.

Re:Making collisions easy

[Sweetshark]

1. Is it practical? (I don't think so.) How big is an image to be considered "huge" and create a dent?
You are right. 2^69 is still huge. 6.7E+7 TB. And then you need something to hide in in addition.
2. Wouldn't adding more data create a better separation? (ie. avalance effect?)
Since IIRC SHA-1 flips almost half the bits for each block, the separation doesnt gain much after two or three blocks, because it is statistically already totally unrelated to the original. And since the change in the message (contract text) affects probably two or three blocks, you dont loose much anymore.

Re:Making collisions easy

[sorbits]

I am still unconvinced that adding more data automatically increase the probability of collision.

It doesn't, but each byte you add/change in the message results in a new hash value. So imagine we find the bytes that needs to be added to our fake message, in order for it to hash to the same value as the message the victim signed.

Problem is that we can't just add random bytes to our fake message, since that would show, but we could hide all these bytes in e.g. the BMP of our company logo (or actually just in any bitmap in the image with the palette set to all white).

So basically adding a large bitmap to the contract gives us a lot of bytes that we can change w/o the victim noticing it.

Why SHA1

[eric1207]

Why bother using SHA1 in the first place... what ever happened to MD5? Why not encrypt your data with two algorithms at once, that'd double the hacker's fun. Who has 38M million to blow on a cracker when good old free social engineering is around?

Re:Why SHA1

[Riddlefox]

MD5 was found to have several flaws in 2004. Security advisors recommended that people migrate from MD5 to SHA-1.

Your last question is the interesting one. Encryption has been described as transfering a credit card in an heavily armored truck to a guy living in a cardboard box. Oftentimes, the easiest way to circumvent the encryption is not to break it, but to look for flaws in the implementation of the algorithm, or to social engineer your way to a password.

assume it is a word document

[The Creator]

Or a pdf-file, i bet there is more that 69 bits of entropy there that is not visible to the reader.

Re:assume it is a word document

[tomjen]

You could hide it in the comments in the pdf file.

LOL WHAT

[Anonymous Coward]

I'll see your BSD and raise you a Public Domain.

Breaking encryption systems is like /, stories

[zenst]

If you post the same story enough times, eventualy your'll get the right combination and break it :)

--
There is no such thing as duplication, only verification, alas alot verify the stupid.
--

Insightful

[Anonymous Coward]

Thank you for this brief, yet reassuring analysis.

--AC

Why use SHA at all?

[ltwally]

As I have not installed linux or solaris for over a year now, so I cannot comment on either of them... But I do know that all the *BSD's, at least, have native support for Blowfish (everything from user passwords to SSH, apache, java, etc).

Having found this and other comparisons, I see little reason to use SHA (any of the versions of it) for anything. Blowfish (BFS) has military grade strength and is insanely fast to compute. While the newer versions of SHA (-256 & -512) might be significantly more secure than SHA-1, they're still dog slow compared to BFS.

For all my encryption tasks I make sure to use BFS. Just my 2 cents.

Re:Why use SHA at all?

[Tim Browse]

Hmm...but SHA is a hashing (i.e. one way) algorithm, and Blowfish is an encryption (i.e. bidirectional) algorithm. (For more on this, see the page you actually linked to.)

So you don't use SHA-1 as an encryption algorithm for stuff like SSH, etc., because, well, you can't. Well, you can encrypt, but good luck decrypting :-)

But you might use SHA-1 to generate crypto keys from plaintext data (e.g. passwords) for use by an encryption algorithm. So 'switching to Blowfish' won't help - you need to switch to a different hashing algorithm (assuming you consider this recent discovery to be a concern for such usage of SHA-1).

Re:Why use SHA at all?

[Anonymous Coward]

The page you link to seems old.

Additionally, you should consider that Blowfish is a block cipher, while SHA-1 is a one-way hash.

While you can use a block cipher as a hash, that's likely something that's been studied far less than SHA-1 or MD5.

Blowfish is usually considered reasonably secure when used as a block cipher (e.g. in CBC mode for encryption), however you should consider that it has a small block size (64 bits) which makes it (despite the key length) less secure than more modern algorithms (e.g. the AES finalists).

It's also not really one of the most heavily studied algorithms; the "military grade" strength listed on the page you link to is based entirely on key length.

Re:Why use SHA at all?

[Anonymous Coward]

Because SHA-1 is actually a widespread standard. Lots of people use it, and it's STILL very sufficient for all but the most extreme cases.

And it shows you clearly lack the most basic knowledge at cryptography or anything related. You propose (without really making a point or anything valid) to jump ship - from a secure hashing algo - to some encryption algo. Like apples and oranges.

Besides, I see no real use for such heavy encryption at home (unless you got something to hide from law enforcement or whatever) as you clearly don't work in a related industry...

Re:Why use SHA at all?

[Creepy Crawler]

---Hmm...but SHA is a hashing (i.e. one way) algorithm, and Blowfish is an encryption (i.e. bidirectional) algorithm. (For more on this, see the page you actually linked to.)

Im kinda confused.. From what I understand, a hash is like a modulus. Easy to get, but an infinite sets of data that it can be derived from (Think how many division problems have a remainder of 1..). Essentially, this equasion has a 1 to infinity relationship.

Now, an Encryption mechanism is a 2-way function. This function, compared to the data, has a 1 to 1 relationship.

My confusion lies in the actual difference between the 2. Couldnt the full-blown encryption be just as good as the hash? I know the sizes between the 2 are quite varied.

From what next I understand about hashes (amateur mathematician), the collision points on a 128 bit hash are 2^128. So, if you were to find a hash of hash(X), it would have 1 answer on a domain of 2^128.

So, wouldnt it have 2 answers on 2^129, 4 answers on 2^130 and so on?

Well, going into my main point about the hashes, couldnt you harden a hash by including exact bitsize of document/file you need hashed? WHen I mean included, I mean as the last line not counted in the line/char counter. (sort of like not counting the PGP wrapper data).

And as another hardening idea (which I think isnt very good.. but its an idea) is by using a semirandom forumula (the way Linux makes /dev/urandom) and computing a sort of a random-jumping-around hash of specific locations and include that hash. An example of what I mean is by getting 10 bits around this document, and then xor'ing them together. So, even if you could find a collision , it had better be the same size, and those specific bits had better be correct.

---So you don't use SHA-1 as an encryption algorithm for stuff like SSH, etc., because, well, you can't. Well, you can encrypt, but good luck decrypting :-)

Err... I might be wrong, but I believe you can technically 'decrypt' text phrases shorter than 128 bits, as they have only 1 solution within 2^128.

Re:Why use SHA at all?

[Anonymous Coward]

Actually, the SHA-1 compression core can be used for encryption instead of hashing. See this Wiki article.

Re:Why use SHA at all?

[Anonymous Coward]

No, you have it all wrong.

Re:2000 times faster?

[KarmaMB84]

Depends on the desired precision. :D

Re:2000 times faster?

[Anonymous Coward]

Never attribute to wittiness what can be attributed to plain, near infinite, stupidity. Yes, the typical /. poster is _that_ dumb.

Wow, a karma whore...

[rbarreira]

http://it.slashdot.org/comments.pl?sid=139602&cid= 11685615

(no, it's not even the same nickname)

Re:Break only affects carefully constructed messag

[Vellmont]

2)
Would someone be willing to pay $38 million to get insider info on a merger between two banks - each worth over $10 billion.


Except SHA-1 isn't an encryption scheme, it's a hashing algorithm. For your 38 million you could construct an machine that would create two random messages that hash to the same value. Totally useless. Really what you want to do is find a message that hashes to the same value of a specific message. Or even better you'd want to create an arbitrary message, tack on some header or footer and have that hash to some chosen hash.

If I understand message signing and digital signatures, an attacker wants to make it look like they're the intended target. Say I send a signed message to my bank saying "please transfer $1,000,000 to account 123456". An attacker wants to generate a message like "please transfer $1,000,000 to account -attacker account number- that will hash to the same value, so he/she can use the same signed digital signature. The 38 million dollar device won't be able to do that in 56 hours, I doubt you could do it in 56 years (and I highly suspect it would take MUCH MUCH longer).

Crypto custom...

[abulafia]

is to speak of averages. So, it is likely that 56 hours is the time to search half the keyspace on such a machine, as over a large number of uses, that will be the average time required per use.

Re:Crypto custom...

[Qzukk]

SHA-1 isn't about keys, or keyspaces. This attack is about finding two messages that hash to the same SHA-1 hash.

It takes roughly 56 hours to go from a message of

Please transfer $1,000,000 from account 123456789 to account 987654321

which hashes to 0xAABBCCDD11223344, to a message of

Please transfer $1,000,000 from account 123456789 to account 555555555 Its a nice sunny day please pardon the line noise Ab29!jqMV3o$2__#%#992mx...w,ea@L@L

whichh also hashes to 0xAABBCCDD11223344, which means that it would have an identical signature, meaning that the original signature would validate the fake message.

Personally its not the huge end-of-the-world scenario everyone thinks it is. It would probably take tens of thousands of years for this machine to output a well-formatted message that had a hash collision and could not be trivially discarded as gibberish.

Re:Crypto custom...

[abulafia]

Yes, you're correct. Sorry to have been imprecise; it isn't right to speak of keyspace. I probably should have said 'search space'.

If I'm not mistaken, though (paper isn't out yet), this isn't finding a collision for a given message,this is about finding two arbitrary messages that hash to the same value, which is an easier proposition than the scenario you outline. Of course, I may be wrong about that.

Re:Crypto custom...

[kiltedtaco]

Assuming the SHA-1 break is similar to the MD5 break, it would take about 56 hours to go from:

Please transfer $1,000,000 from account 123456789 to account 987654321

to

Please transfer $1,000,000 from account 987654321 to 123456789 CRUH(YI(L*GPIHcdpncxacn.dy4idpi98l(YD$L&Dl94,3x9lx 9(Y

MD5 and SHA-1 are both iterated hashes. 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. Which is a much more serious problem than simply finding two 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, considering it was discovered by two of the people working on the MD4/5/RIPEMD attack.

Re:Crypto custom...

[Jhan]

It takes roughly 56 hours to go from a message of
Please transfer $1,000,000 from account 123456789 to account 987654321
which hashes to 0xAABBCCDD11223344, to a message of
Please transfer $1,000,000 from account 123456789 to account 555555555 Its a nice sunny day please pardon the line noise Ab29!jqMV3o$2__#%#992mx...w,ea@L@L
which also hashes to 0xAABBCCDD11223344

Except, that's not at all how I read this news. In 56 hours you can generate a completely random string that you have no control over whatsoever that hashes to the same value.

You would have to repeat the process quite a few times before the random text becomes the message you want... I guess you could hire some chimps to overlook the process.

Even worse, one report I read claimed that all this hack can really do is to generate two random strings with the same hash, ie. no way to target a specific message at all.

Re:Crypto custom...

[Anonymous Coward]

The problem is if there's a small hack for it now, then expect more hacks for it in the future (small or big doesn't really matter.) Moreover, SHA came from the NSA and they silently modified it to SHA-1. Hence, many are asking if the whole SHA (1, 256, 512) is worth using or it's worth adopting/creating something else independently and better.

How long can we keep using SHA and its improvements until the "end-of-the-world" arrive? Since the NSA knew about a vulnerability in SHA-0, why didn't they publish their findings? Is SHA-X really secure or just secure in obscurity?

Re:Crypto custom...

[rah1420]

It takes roughly 56 hours to go from a message of

Please transfer $1,000,000 from account 123456789 to account 987654321

which hashes to 0xAABBCCDD11223344, to a message of

Please transfer $1,000,000 from account 123456789 to account 555555555 Its a nice sunny day please pardon the line noise Ab29!jqMV3o$2__#%#992mx...w,ea@L@L

whichh also hashes to 0xAABBCCDD11223344

Geez, that's 17,857.14 per hour. Not freakin' bad. :)

Distributed computing?

[daijo78]

-"Please download my DC client." -"Whats it for?" -"Something good... err... cancer research, finding E.T. You know. Just download and run it! Geeze..."

Re:2000 times faster?

[Anonymous Coward]

Not quite right, you could simply use Wikipedia. //this is meta-funny, laugh!

Re:Break only affects carefully constructed messag

[mt v2.7]

IANAC(ryptographer)

Why don't they make a type of verification where both the hash and the filesize are used?

Seems to me that there are a finite number of comobnations of an x bit file that have the same hash, and in all likely hood they wouldn't be able to insert something malicious into one of those comobnations..

Can anyone point out why this wouldn't work? it seems kind of obvious to me, but again IANAC.

Re:2000 times faster?

[swillden]

>>> FIRST CORRECTION

>> 15th actually, and you were wrong anyway.

> Depends on the desired precision.

Certainly. Because 1 is approximately equal to 15 for large values of 1 and small values of 15. If you squint.

Re:Break only affects carefully constructed messag

[Daedala]

For 2, it's still cheaper to buy an insider.

Re:2000 times faster?

[Anonymous Coward]

This is true.

Whenever I can't figure out how to do something in Linux, I just make a post saying, "Linux sucks because it can't do XXX like Windows can!"

Within 10 minutes, I'll have 50 replies from Linux gurus around the world telling me, "You idiot, Linux's implementation is better than Windows! You just do YYY and ZZZ and boom! Bill Gates sucks!"

Re:2000 times faster?

[swillden]

While the bumbers are only 11 difference yes, 69 is a much slower method for most 80, though I'm not sure its 2000 either.

Wow. That's an absolutely amazing post. It's so wrong, on so many different levels, in so many different ways, and in so *few* words... impressive as hell. You have my respect, sir.

Why I don't like the idea of using SHA-{256,512}

[ScytheBlade1]

Here's a slight story for you. Certain gaming company 'X', in their online gaming services, uses SHA-1. However, how they implimented it, basically sucked. The person that found this posted it on a couple newsgroups, wanting to just just how heavily borked it was.

He didn't get around to verifying the results, however it cames back that one could see anything 12 bytes or less from the hash given. (Company X did a couple things that made this pointless, involving taking what was input, and then adding to it in order for it to form at least 22 bytes).

As the guy that explained this to me said, "See where this is going?"

The longer the hash, the more information you have to reverse. Meaning, hey, you can get more of the plaintext out of it, if you know what you're doing (and likewise, if the dev is incompetent).

On top of that, you know, a hash size that much larger is a LOT of more data to store.

Why is this bad?

[He Who Has No Name]

I have no idea what SHA-1 is or why the heck it being cracked has made headlines twice now. Somebody want to explain this?

todays computing power and Moores Law

[tod_miller]

do not use moores law

Please do not mention moores law. Why not stop all research into CPU core technology, and just wait for my CPU in my computer to double its speed every 18 months.

If anything it is an insult to those minds who give us the CPU power that we have. It is taking it for granted, that these people develop the crazy shit they do.

And I hear people using it far too much, please do not use moores law.

Re: ante up

[ubiquitin]

I'll see your Public Domain and raise you a TCP/IP network freeforall. ;)

The Revolutionary Alternative

[CyberSpaZtiK]

Now that SHA-1 has been broken, there is another alternative besides SHA-256 and SHA-512 that the crypto experts forgot to mention: AYATOLLAH-1, a hash algorithm with fundamentalist fervor that shall beat back attempts to break it with fire and jihad.

Re:Break only affects carefully constructed messag

[arodland]

Or, and this is a good one, you could do that. For any message that I create, and sign for SHA-1, it's now possible that I created another duplicate message, and that I could, at any point in the future, say "Oh no, I didn't sign _that_!"

So, there are two lessons to be learned.
1. Don't trust SHA1 as part of an algorithm for signing a document that someone else gave you. Actually, this is not so much of a risk, because any reasonable signature algorithm signs more than just a straight hash of the document.

2. Don't trust any document signed by someone else with an algorithm using SHA1, if they created that document themselves; they might have a way to repudiate that signature, leaving you out in the cold. This one is actually more dangerous.

not yet a fire alarm.

[davids-world.com]

The findings are that SHA-1 is not collision free

What, is that new? That already follows from the fact that there are only N possible hashes, and M possible messages, and NM. In other words, if you have an 8-bit hash (256 values) for a, say, 1K message, then you must get a lot of collisions.

If it takes only three days or so to find a collision, what does that mean practically? Almost nothing. Because the collision that you would find is most likely meaningless. The modification that you'd like to apply to the message (while sticking with the same, given hash) is likely to be something very specific, for example, change $1000 to $10.000. And that, unfortunately, is not easy. This vulnerability can't be easily exploited at this point.

But even saying that "if the algorithm has one vulnerability, then it's likely to have others" is totally illogical - unless a whole class of vulnerabilities has been pointed out.

It's not even time to 'walk to the door' because the fire alarm has gone off, as someone said later down in the comments. Instead, it's time to read the Chinese paper, produce more truthful descriptions of how much of a problem we are going to get with this (does it lead to more severe vulnerabilities), and start working on better hashing algorithms.

Re:not yet a fire alarm.

[igny]

and start working on better hashing algorithms.

Something tells me that the work on better hacking algorithms has already been started.

Re:not yet a fire alarm.

[davids-world.com]

Something tells me that the work on better hacking algorithms has already been started.

Agreed. DJB's Poly1305-AES might be worth mentioning here (?).

Re:not yet a fire alarm.

[Kymermosst]

The findings are that SHA-1 is not collision free

What, is that new? That already follows from the fact that there are only N possible hashes, and M possible messages, and NM. In other words, if you have an 8-bit hash (256 values) for a, say, 1K message, then you must get a lot of collisions.

Thank you for addressing this early in the postings. I was about to go insane when I read that in the story post.

Come on, it's the basic Pigeonhole Principle. Computers Science students should have learned this in Discrete Mathematics. If you didn't, it says this: If you've got 10 holes and 11 pigeons in them, then one hole has two pigeons.

If it takes only three days or so to find a collision, what does that mean practically? Almost nothing. Because the collision that you would find is most likely meaningless. The modification that you'd like to apply to the message (while sticking with the same, given hash) is likely to be something very specific, for example, change $1000 to $10.000. And that, unfortunately, is not easy. This vulnerability can't be easily exploited at this point.

Precisely. Really, it doesn't matter if it is easy to find a message with the same hash, if the new message is obviously incorrect or unintelligible.

What I don't understand is why nobody has simply suggested using two distict hashes in any particular application. Say, MD5 and SHA-1 together. The ability to find a collision in a few days for either one may exist, but finding a message that causes a collision for both should be very hard.

Re:not yet a fire alarm.

[shannara256]

Copy'n'paste from an anonymous coward in a previous discussion:

It would seem as though even if SHA-1 were to fail, the two algorithms used together could bolster each other security-wise. This slows things down, of course, but would it not suffice for the time being?

Using two hashes in conjunction does not work as well as you would expect it to work. There are at least half a dozen posters here proposing this idea, so I will try to explain in some detail why it does not work.

In general an n-bit hash can be collided in 2^(n/2) time using the birthday paradox attack. When you concactenate two hashes of lengths n and m bits, you get a hash of length n+m bits. However, this (n+m)-bit hash can in fact be collided in m*2^(n/2) + 2^(m/2) time (assuming n is greater than or equal to m). This is only slightly more effort than it takes to collide both hashes separately. In the case of SHA-1 and MD5, n is 160 and m is 128, so colliding both hashes would take 128*2^80 + 2^64 = 2^87.00000017 effort versus 2^80 effort for SHA-1 alone.

It must be especially stressed that m*2^(n/2) + 2^(m/2) is considerably smaller than the attack time of 2^((n+m)/2) which you would normally expect from a well designed hash having n+m output bits.

So how does the attack on two hashes work, you ask? It exploits a curious property of the birthday attack which says that generating a multicollision (three or more messages all with the same hash) by brute force takes only marginally more effort than generating a single collision. Specifically, generating a 2^(m/2) way multicollision takes only m/2 times as much effort as generating a single collision. So what you do to collide two hash functions is: you generate a huge multicollision in the first hash function, and then from that set you look randomly for a pair that collides the second function. It seems very counterintuitive, but the point is you can break the hash functions one by one instead of having to break both of them at once. Strength in numbers doesn't apply here.

If one of the hash functions (say MD5) has a better than brute force attack, then that can be used to speed up the attack against both hash functions by the same factor. The only uncertainty is if both of the hash functions have better than brute force attacks; in this case it would depend on the particulars of the attacks as to whether one can make them interact in such a way as to break both. However, no matter what, the idea of concactenating two hash functions has such low security compared to designing a good hash function of the same length from scratch that it is unlikely that this concept will ever be useful from a pure cryptography standpoint.

For more information on multicollisions and attacking concactenated hash functions, see A. Joux "Multicollisions in Iterated Hash Functions", Proceedings of Crypto 2004, LNCS 3152.

Re:not yet a fire alarm.

[shobadobs]

Come on, it's the basic Pigeonhole Principle. Computers Science students should have learned this in Discrete Mathematics. If you didn't, it says this: If you've got 10 holes and 11 pigeons in them, then one hole has two pigeons.

To be precise, one hole has at least two pigeons.

Re:not yet a fire alarm.

[Anonymous Coward]

You _could_ put 1.5 pigeons in two of the holes...

Re:not yet a fire alarm.

[Anonymous Coward]

So the correct statement is: If you have N holes and N+1 pigeons in them, at least one hole has more than one pigeon.

Re:not yet a fire alarm.

[m50d]

And in its basic form, the principle simply states that given at least one pidgeon all of which are in pidgeonholes and n pidgeonholes there is at least one pidgeonhole which contains at least one pidgeon.

Re:not yet a fire alarm.

[m50d]

Using multiple hashing algorithms does not increase security more than a double length version of the most secure one, in your example one of the SHA-2 variants. MD5 and SHA-1 have the same ancestry, so combining them doesn't increase security anywhere near as much as the extra bits ought to imply.

With regard to the break, the worrying thing is not that it is possible to crack SHA-1 in x years, but that it is possible to crack it 2000x as fast as should be possible. We saw things like this shortly before MD4 was fully broken, maybe someone older than me remembers the same happening with MD2 and RC4. An algorithm which is not as secure as expected should not be trusted, even if it still seems secure enough. If a bridge that was supposed to take 10 tonnes collapsed when someone tried to drive a 7-tonne truck over it, would you be happy driving your 1-tonne car over a bridge built to the same plans?

Re:not yet a fire alarm.

[Kymermosst]

Ah, that makes a lot of sense.

To you and the original AC who wrote it, thanks for the info and the reference.

ALlow me to explain it...

[Anonymous Coward]

69 = dual felacio

80 = tittyfuck with oral

I think the GP is saying he(?) cums quicker with oral tittyfuck than 69 position, but not 2000 times quicker.

I think you fail it where it is understanding inuendo.

impossible to recreate original message?

[wanderingstan]

One-way hash functions are supposed to have two properties. One, they're one way. This means that it is easy to take a message and compute the hash value, but it's impossible to take a hash value and recreate the original message. (By "impossible" I mean "can't be done in any reasonable amount of time.") ...

If you only have the hash, how can you recreate the original message (even with infinite time)? Is he saying that with only a 128bit hash of a LoTR avi, and an unreasonable amount of time, it would be possible to re-create the movie? I'm no encryption expert, but that don't sound right.

Re:impossible to recreate original message?

[TheRaven64]

No, you can create the original message from the hash if you have infinite time. Unfortunately, you also create an infinite number of wrong messages in the same time, so it's not particularly useful.

Re:impossible to recreate original message?

[wanderingstan]

Well in that case, why even mess with the hash? A program that randomly spits out 0's and 1's will eventually create every possible data file, including the LoTR avi. Too bad. I was hoping to compresss my entire HD into a single 128 bit hash. :)

I dunno about that...

[mosel-saar-ruwer]

[NB: For computer science geeks, a "pre-image of a hash" is more or less the same thing as a "bucket"; for math geeks, it's more or less the same thing as a "variety".]

If they're prepared to spend a realistic level of time on it they could create two of them that hash to the same thing, with a small but effective change to the second.

I dunno - my guess would be that the subspace of all grammatically correct English language sentences [and paragraphs, and chapters/essays/"contracts"] is, for all intents and purposes, infinitesimally small within the space of all ASCII [not to mention Unicode] strings of similar length.

If you doubt that, consider the trouble a really good English language wordsmith [like Yeats, or Frost, or Stevens] has to go to just to force the final words of lines to rhyme within a poem [and yet maintain any sense of cohesion in the result]. And we only seem to get about four or five of those guys every century. To get a second, meaningful, relevant, grammatically correct "contract" within the same hash pre-image as your existing "contract" strikes me as nigh unto impossible [although I'm more than happy to listen to any argument to the contrary].

Re:I dunno about that...

[arkhan_jg]

I'd agree with you on that; which is why you'd include other extraneous material in the original contract file, such as graphic logos, hidden comments or other meta-data which would give you enough 'secret' collision space to work with, to counteract the changes you wanted to make.

Still, it would take a rediculous amount of time and money to pull it off, even with this known weakness. Thing is, that cost will drop over the next few years, and there's always a possibility that further weaknesses will be found in SHA-1 after this one, making that cost drop even faster.

SHA-1 isn't dead yet; but it will be in the forseeable future, as MD5 alone is already (for important hashes, anyway). One solution is to switch to SGA-256, whirlpool, or some other hash algorithm, or use multiple different hashes at once.

Re:I dunno about that...

[hey!]

I'd agree with you on that; which is why you'd include other extraneous material in the original contract file, such as graphic logos, hidden comments or other meta-data which would give you enough 'secret' collision space to work with, to counteract the changes you wanted to make.

Which suggests a principle for using (or rather accepting) digital signatures that mirrors one you should use for sending encrypted data. It's unwise to encrypted stuff that's not needed (like the Gernman Enigma operator who always opened his transmissions with "Heil Hitler"); likewise it may be unwise to trust digital signatures that include extraneous material.

Time to switch to "one time" pads...

[quarkscat]

I guess I'll have to send all my friends an
eBook on CDROM for use as a "one time" pad.

Clearly, SHA-1 is broken. And given the low
cost of clustered computing power, SHA-256
can't be too far behind.

Last night's episode of Battlestar Galactica...

[mosel-saar-ruwer]

Write the contract in MS Word and use huge uncompressed BMPs for the company logos. You have instantly enough space for subtile changes to create collisions.

Obviously you didn't watch last night's episode of Battlestar Galactica...

Re:Last night's episode of Battlestar Galactica...

[Sweetshark]

Obviously you didn't watch last night's episode of Battlestar Galactica ...
(handwaving) There was no Battlestar Galactica on TV yesterday.
At least not here.
Reading the story plot didnt enlighten me at all about what you are trying to say. Please be a bit more specific.

Re:Break only affects carefully constructed messag

[ethan0]

For your 38 million you could construct an machine that would create two random messages that hash to the same value. Totally useless.

Not true. The use of that is creating one legitimate document and apply a certification to it, with the authority of a trusted certifier (who would have verified it, because it is legitimate).
At the same time your $38M machine would create a second document, with whatever information you care to put in, which that certifier would never touch. They have the same hash, so you could substitute in the bad document for the real one, and the certification would be entirely indistinguishable from authentic.

Combining SHA-1 and MD-5 as a workaround

[ronys]

While both of the above algorithms are "broken" in the sense that a collision may be found relatively easily, if a signature is done on both hashes, the attacker has to find a message that provides the same MD5 hash and the same SHA-1 hash, which I strongly doubt is possible theoretically.
In other words, if I provide text T and a signature derived from both MD5(T) and SHA1(T), an attacker wil have to find T' such that MD5(T) == MD5(T') AND SHA1(T) == SHA1(T').
Note also that using SHA-1 (or MD5 for that matter) with HMAC is still secure, which means that many protocols using HMAC are OK.

Re:Combining SHA-1 and MD-5 as a workaround

[rbarreira]

Actually, it has been proven (by Antoine Joux and maybe others, if you want a starting point for some googling) that using two hashes simultaneously is not as good as we used to think...

Re:Combining SHA-1 and MD-5 as a workaround

[Dolda2000]

While both of the above algorithms are "broken" in the sense that a collision may be found relatively easily, if a signature is done on both hashes, the attacker has to find a message that provides the same MD5 hash and the same SHA-1 hash, which I strongly doubt is possible theoretically.

It's certainly theoretically possible. If you use SHA1, which is 160 bits, and MD5, which is 128 bits, then you have a hash that is 160+128=288 bits in length. That yields 2^288 combinations.

There are, however, 2^296 messages that are 37 bytes in length, which means that for any 37-byte message, there are by necessity 255 other 37-byte messages that yield the exact same hashes. Sure, most (all?) of the others will be binary gibberish, but there are nonetheless 255 colliding messages for any given 37-byte message.

And that's just for 37-byte messages. If you send a 1 KiB message, there are 2^7904, or around 10^2379 colliding messages.

Where's the 90 page version?

[dwhite20899]

good enough for now - thanks!

Shamir said at RSA that there's a complete 90 page version in existance... I haven't found that one yet.

WHAT IDIOT MOD MODDED PARENT OFFTOPIC?

[Anonymous Coward]

THE PARENT POST IS CERTAINLY NOT OFFTOPIC.

Most moderators are fucking idiots, don't you be. /banned from moderation during the great rtbl purge

Re:2000 times faster?

[Anonymous Coward]

He was talking about 2000 v. 2048.

Re:Break only affects carefully constructed messag

[GoCoGi]

1. Just modify every document from someone else without changing it's meaning, and you *should* be fine.

2. This is not a problem. Everyone is allowed to sign as many documents as one wishes with one's own key. You still have the original document that was given to you.

Still, looking for something other than SHA-1 is probably a good idea.

Illustrated Guide to Cryptographic Hashes

[Steve Friedl]

Those wishing some background on this subject to be able to put it in context may want to check out my Tech Tip:

Unixwiz.net Tech Tip: An Illustrated Guide to Cryptographic Hashes

Re:Break only affects carefully constructed messag

[Lulu of the Lotus-Ea]

The grandparent was speaking more generally of assessing risks, not conflating cryptographic hashes with encryption.

But even so, there are several plausible paths by which a "break" in SHA-1 could lead to compromise of very valuable information (e.g. the $10B merger).

(1) Another respondent pointed out the substitution of a good message for a bad message, where both share a hash. E.g. confidential instructions to a bank manager are guarded by a hash: Only follow these instructions if the hash shows the message has not been altered... but the hash doesn't show that, because the hash algorithm is compromised.

(2) Substitution of public keys in systems using hash components (i.e. all of them). I can forge a message that appears to be signed by someone authorized to have the valuable information. When recipient responds, using MY public key (because it passes for the authorized person's public key), they send me the confidential information.

(3) Monkey wrenching: You know certain messages are being sent concerning the details of the transaction (i.e. the merger). These are encrypted, and you (the attacker) cannot read them. However, knowing the general form of the messages, you flood the channel with one or more false messages, each of them apparently legitimate based on hashes. Participants in the transaction cannot distinguish real from fake messages, and the transaction is complicated, delayed, or cancelled (and you make all the money off your puts/gets/shorts/etc. on the merging companies).

Re:Break only affects carefully constructed messag

[einhverfr]

Not true. The use of that is creating one legitimate document and apply a certification to it, with the authority of a trusted certifier (who would have verified it, because it is legitimate).

The is that as soon as you try to place specific content in the message, it becomes *much* harder to find a collision that meets your requirements (especially if there are length requirements too).

Now.... Let me bring up one possible use of these issues. If you store passwords as SHA hashes, and if someone can get a list of hashes, then they can find colliding passwords.

The eternal question

[kernel_dan]

Is SHA pronounced 'ess-aych-ay' or 'shah' or what?

Begs the question

[Nimey]

No, it *raises* the question. "Begging the question" means circular reasoning, e.g. "You can't expect eighteen-year-olds to vote intelligently, because they are too young to have good judgement about the issues".

Yet another part of English butchered by Slashweenies wanting to appear intelligent.

Re:Break only affects carefully constructed messag

[arkhan_jg]

I've just thought of a varient on 2) that's nasty:

Secretly hack a software download site, such as distro mirrors or windows update :). Upload modified files that have had keyloggers/spyware added to them, but give the same SHA-1 hash.

Even systems which check the hashes of downloads (or certificate signed ones, maybe), and would install the modified files and be none the wiser; and if the break-in isn't discovered quickly, the software could get pretty widely spread.

Re:Break only affects carefully constructed messag

[hey!]

Well, sorta.

IANAC, but my understanding is you really have to look at protocols and implementations to understand the impact of a potential weakness in an algorithm.

The one way functions used in public key crypto are very expensive to compute, whereas hash functions are relatively cheap. Therefore it is common practice to sign, not the document, which is large, but a hash of the document. If you have a completely reliable hash function, it is for all purposes just as good as signing the document.

So, any digital signature implementation that works this way, and uses sha-1 as the hash function, is potentially crackable and probably shouldn't be used where more than a million dollars is at stake.

One Would Think

[Moos3d]

There must be better ways of using your $30+ million dollars.

Re:Break only affects carefully constructed messag

[flargleblarg]

Totally agree, however in the crypto community (which I cannot claim to be part of) the consensus is generally that if a weakness if found in an algorithm then it begs the question - "what other weaknesses are there".

At least the information in R2 is still intact. I only hope that when the data's analyzed, a weakness can be found. It's not over yet.

The sky isn't falling.....yet

[BobSutan]

http://www.fcw.com/fcw/articles/2005/0207/web-hash -02-07-05.asp

But Burr said no complete implementation of the SHA-1 function has been successfully attacked. "SHA-1 is not broken," he said, "and there is not much reason to suspect that it will be soon." But advances in computer processing capability make it prudent to phase out SHA-1 by 2010, he said.

Your example begs this question...*

[CaptainPinko]

Not to troll, but I'm wondering how does your example beg the question? It seems like "voting intelligently" and "having good judgement are separate things". For example, you could vote intelligently because you are a good and thorough judge of character, but have little understanding of the actual issues. Also it seems like you could be intelligent that you could have good judgement about the issues, and yet vote unintelligently since you aren't critical of the candidate's promises/platform.

Either I have a poor understanding of a circular argument or you have a poor example. Your terms to be quite independent of each other.

AFAIK, the canonical (right word choice?) example of a circular argument is "God exists because the Bible tells us so, and we know we can trust the Bible since God wrote it."

* Yes, this "error" in the title is intentional and meant humourously.

Re:Your example begs this question...*

[Profane MuthaFucka]

It begs the question because the conclusion is assumed in the premise. Even though you might make the definitional argument that intelligence and good judgement are different things, it doesn't matter.

Let's suppose that you are right, and they are different. An argument is a logical progression from the premise to the conclusion. That mean that there would have to be a certain relationship between intelligence and good judgement for this argument to flow logically. But just a little thought shows that it's possible for an unintelligent person to show good judgment, and it's also possible for an intelligent person to show bad judgement. Therefore, to conclude that an intelligent vote depends on good judgement isn't founded.

Now, suppose you're wrong about your definition distinction. It's reasonable to view both intelligence and judgement as related assessments of a person's cognitive ability. The argument then becomes "You can't expect eighteen-year-olds to utilize good cognitive skills while voting, because they are too young to use good cognitive skills while voting." As someone who is speaking casually would use that sentence, I think that they would interpret it very loosely, and the exact definitions of the words would mean as much as the intent of describing general cognitive abilities.

Anyway, I don't think this was a bad example, but I can see how it has two interpretations.

The Cylons tried to frame Gaius Baltar...

[mosel-saar-ruwer]

The Cylons tried to frame Gaius Baltar using a doctored photograph.

Also a lot of stuff about Baltar's relationship with God [which probably sailed right over the head of the average /.-er].

Re:Break only affects carefully constructed messag

[Ephol]

3) Would the RIAA/MPAA go halvesies in order to find user/password collisions for some people they suspect of being big players on a P2P network, in order to gain some access to see exactly what they're sharing?

I have no idea if a network vulnerable to this exists, and I realize they couldn't use those findings legally but it could sure put them on the track they're looking for.

Well, cmon

[Anonymous Coward]

No hash algorithm is collision free, and will not give perfect distribution across its bit space. A hash's width of N bits doesn't mean you will get 2^N distinct combinations for 2^N different inputs. It is damn well going to be far, far less than that before a collision occurs.

So, the fact that that a 160-bit digest which ideally produces a collision in 2^80 tries, but 2^69 in reality shouldn't be that shocking.

Re:Well, cmon

[Anonymous Coward]

The point is there is a non-brute-force attack of 2^11 times less today. It's only logical to anticipate more non-brute-force attacks in the future Based On This Attack. SHA is not the only one available, it's not the best, and it was created by the NSA, so is it still worth using it than something else?

The article says it's time to look for alternatives, but not in a hysteric way.

Bit Torrents

[Anonymous Coward]

Bit Torrents use SHA-1, I believe. If the MPAA wants to spend the money, I suppose they could start corrupting downloads now by inserting torrents that pass the SHA-1 hash, but do not actually contain valid data.

Re:2000 times faster?

[ChrisCampbell47]

If you're still in high school, then pay attention in math class now before it's too late. Don't miss class, sit up front, and take good notes. It's your only hope.

If you're already out of high school, then I'm sure DeVry or some other fine institution will be happy to take your money and make you feel better about the situation for a while.

Re:Break only affects carefully constructed messag

[God! Awful 2]

No crypto is powerful, or clever enough (yet!) to be completely unbreakable so its all down to making assumptions:

Wow, you made a statment like that without drawing 10 irrelevant replies about 1-time pads. I've never seen that before!

-a

Re:Break only affects carefully constructed messag

[ethan0]

as soon as you try to place specific content in the message, it becomes *much* harder to find a collision

It's pretty easy to put a whole lot of garbage data in a document. Changing this data wouldn't affect how the document looks, but would of course affect the hash. With this to modify, you could create a collision with the ease mentioned in the article.

If you store passwords as SHA hashes, and if someone can get a list of hashes, then they can find colliding passwords.

No, they can't. You can create a hash collision with a known piece of data, not with a known hash. You would have to know the original password (from which of course the hash is easily computable) to create a password with a colliding hash.

Re:Break only affects carefully constructed messag

[einhverfr]

It's pretty easy to put a whole lot of garbage data in a document. Changing this data wouldn't affect how the document looks, but would of course affect the hash. With this to modify, you could create a collision with the ease mentioned in the article.

It is pretty easy to detect a whole lot of seemingly random garbage appended to the end. This "problem" can be solved by simple efforts to detect tampering. You will have to do better than that for a long-term threat.

It's not on Netcraft

[caluml]

I'm afraid I don't believe it. There's nothing on Netcraft about all this.

Or buy zobies

[Flu]

Or Would someone be willing to pay a russian hacker $10.000 to create a virus that infects 100.000 zombie PCs and runs the decryption overnight?

Real Application

[CastrTroy]

I understand that this whole things shows that the SHA-1 algorithm isn't as strong as we thought it was. However, I want to see a real world application of these findings. If for instance you sign a plain text, non-html email, using sha-1, what is the probability that someone could generate another email, non-html, that looked like a real message, that hashed to the same value. It's all well and good to say you can find 2 things that hash to the same value. We knew you could do that. The hard part is getting 2 meaningful messages that hash to the same value. And most of the time, you can't just stick some stuff on the end so nobody will notice, at least not those interested in actually checking if the document is valid.

Re:Break only affects carefully constructed messag

[darco]

• No crypto is powerful, or clever enough (yet!) to be completely unbreakable

Forgive me if I am taking your statement too literally, but there is one method of encryption that is mathematically unbreakable. It is called a "one-time pad".

It is conceptually very simple. Generate a Key filled with cryptographic-quality random data that is as long as the plaintext. XOR the plaintext with the key to get the cyphertext. XOR the cyphertext with the key to get the plaintext. Because of the nature of the algorithm, there is absolutely no way to determine the plaintext or Key form the cyphertext.

Key management for a one-time pad is a huge problem, which makes it only appropriate under certain circumstances, and even then a given key can only be used once if you want it to still be considered "secure".

Just to make a minor commentary on the original story... No hash algorithm that produces output smaller than the data it is hashing can be considered collision-free. The trick is making a hash algorithm in which the only way to find a collision is through a brute force attack.

Out of the frying pan, into the fire?

[chiph]

Now that a weakness has been shown for SHA-1, has the same analysis been done for SHA-256 & 512?

Admittedly, dropping 2^11 values off a 256-bit hash doesn't reduce the time to find a collision that much, but perhaps for the versions other than SHA-1, it's more than 2^11?? I wouldn't want to change algorithms from one that has a known weakness to one which has an even bigger unknown weakness.

So I'll change once the other SHA versions have been shown to be free of this weakness.

Chip H.

Re:Out of the frying pan, into the fire?

[SiegeTank]

Excuse me?! Check the numbers. I think you will find that working through 590295810358705651712 (2^69) combinations using the newly developed algorythm is far easier than trying 1208925819614629174706176 (2^80) brute force combinations.

Like the article says, 2^69 is about **2000 times smaller** than 2^80 (actually it's 2048 - but whose counting ;-)

So think about it, your lovely new SHA-1 hash can get matched in 56 hours now, instead of the 2048 x 56hrs it might have taken otherwise - roughly 13 years, I believe. So whether or not you consider this a big weakness or not (which it is; or will be in a few years) you have been shown the door.

--
Everyone out of the pool!

Does anyone understand these crazy OpenPGP folks?

[Anonymous Coward]

They removed TIGER from the OpenPGP specs and now after SHA-1 has been broken they think loud about moving to SHA-2 which is despite all improvement an algorithm of a similar architecture. When the **** will they finally add WHIRLPOOL to OpenPGP!? WHIRPOOL is a NESSIE (EU) approved algorithm, what are they waiting for?

MirrorDot Link to TFA

[henrypijames]

Poor Schneier has been slashdotted, here the mirrordot link to the article: http://mirrordot.org/stories/8d15245fcd484ffea6ab7 38745bfa642/index.html

Re:2000 times faster?

[swillden]

Obviously. But that's not nearly as funny, is it?

Slowness of SHA-256 / 512

[PureFiction]

For those who complain about the speed of strong digests the VIA Mini-ITX platform with the C5J / C5x? processors from Centaur include the Padlock Engine (as they call it) that implements SHA-1 and 256 on core.

Implementing SHA-256 on core means many times faster performance than a 64bit Itanium on a small 1.4Ghz 10W processor.

Some advice for SHA-1's creators.

[OmgTEHMATRICKS]

2^69? These guys need girlfriends.

preimage vs birthday attacks

[EventHorizon]

Corrupting a BitTorrent transfer would require a preimage attack, where the attacker must determine new (malicious) data with a specific hash. For an ideal hash function, the preimage complexity is 2^(n-1). This research did NOT weaken the preimage complexity of SHA1, so does not affect BT, or HMAC users such as SSL/TLS and IPSec (ESP).

This research instead concerns the birthday attack, where an attacker must (merely) find any two messages with the same hash. For an ideal hash, the birthday complexity is 2^(n/2). This research has shown that SHA1 is far from ideal (colliding in 2^69 attempts instead of 2^80).

The MPAA is still much better off filing lawsuits than going after SHA1.

Re:"begs the question" (OT)

[Arrgh]

The passive voice will be used until all are made sorry!

It's pronounced "shah"

[jdennett]

Not to be confused with the "shar" shell archive format.

Linux updates still using MD5

[Anonymous Coward]

Linux updates are still using MD5 for hash checksums. It's still udeful by looking for both file size and hash, (and with the two combined, still get a unique, unhacked result). At some point though, people may want to look at SHA-256 or SHA-512. Considering the rate that Linux updates appear (fast and furious as always), it would take someone wanting to break the binary/update more time than it takes for the update to be replaced with a newer one.

The number one problem is...

[peeon]

trusting NSA. Like Schneier suggested, we need a competition like AES competition to prevent secretive agency like the NSA have a hand in encryption and hashing. "Additionally, algorithms from the NSA are considered a sort of alien technology: they come from a superior race with no explanations. Any successful cryptanalysis against an NSA algorithm is an interesting data point in the eternal question of how good they really are in there."

The findings are that SHA-1 is not collision free

[Shanep]

The findings are that SHA-1 is not collision free

NO hash algorithm which is capable of reducing an arbitrary number of bits to a smaller message digest, is ever going to be collision free when the input is larger than the digest. Ever.

The difficulty is normally in finding a collision, whether through brute force or algorithmically.

It would be possible to design a hash algorithm to have no collisions with input of a length smaller than or equal to the message digest. But that is of pretty limited use when we're talking about lengths like 160 bits.

Re:Break only affects carefully constructed messag

[Shanep]

Creating pseudo-random numbers that hash to the same value != making any arbitrary document hash to the same value.

I agree, however what sort of document are we talking about here?

Plain text? Okay, that would be super difficult to do without padding with gibberish.

A bitmap image of a faxed document? Easy with all those random noise bits.

A document which allows and has embedded images? Easy, make the required changes within the least significant bits of the images.

etc etc etc.

I will stick to signing plain text only thank you very much.

Re:2000 times faster?

[Anonymous Coward]

Too bad I just put all my moderator points elsewhere. That was hilarious, and so true.

Re:Break only affects carefully constructed messag

[Anonymous Coward]

Actually, it only raises the question. Unless, of course, you want to destroy the distinct meaning of that phrase.

To be precise..

[raehl]

To be precise, one hole has at least two pigeons.

To be precise, at least one hole has at least two pigeons.

Unless there's a hawk.

Various ways to exploit this

[darkonc]

There are a number of ways to exploit breakage of SHA-1. Brute force is not the only way. A modification of one suggestion made on bugtraq:

Write a macro:

if( $TestBlock == "AAAAAAAAAAAAAAAAAAAAAAAA") {
print "Deposit to the account of RMS"
} else {
print "Deposit to the account of Bill Gates"
};

At that point, all you have to do is look for a message that modifies ANY of the characters of $TestBlock while keeping the SHA1 digest intact. You can encode more specific data by specifying multiple such blocks. . If you know what you're doing, you could easily hide this inside a PDF (which is essentially a postscript program) or a word macro.

For the most part, something that takes millions of dollars of hardware to exploit doesn't look like such a big deal, but once in a while we find ourselves caught in the middle of affairs much bigger than our piddly little lives, and knowing that someone with the resources of Bill Gates couldn't mount a man-in-the-middle attack on your PGP communications may be more important than you think in the moment.

A blast from the past.

[Anonymous Coward]

What's grosser than gross? Ten dead babies in one trash can.

What's grosser than that? One dead baby in ten trash cans.

Re:Break only affects carefully constructed messag

[AssFace]

No, they can't. You can create a hash collision with a known piece of data, not with a known hash. You would have to know the original password (from which of course the hash is easily computable) to create a password with a colliding hash.


Wait, explain that again?
The post to which you reply is saying that if a system stores the hashes of passwords instead of the passwords themselves (many places on the net do this - some with MD5, many with SHA1) so that if my password is "pants" the system will hash that when I sign up and then put that in the database.
So then when I login in the future, it hashes my password and compares that to what it has in the database, and if the two hashes are the same, it assumes that it is my password and lets me in.

So that poster you responded to was saying that if we could get that list, we would have the hash. Then all we would need to do is try combinations of characters through the hash to get a collision on the target hash (the "pants" hash in this case).
If it turns out that "balls" makes the same hash that "pants" makes, then they could type in "balls" while logging in as me and it would produce the same hash as "pants" and the system would think that they are me.

They would never need to know what the original password is, and they would never need to care - they can get in due to the collision.

OpenPGP Spec Change?

[xxxJonBoyxxx]

I wonder what the OpenPGP response will be. The spec (http://www.ietf.org/rfc/rfc2440.txt; see section 9.4) doesn't describe these algorithms.

Re:Break only affects carefully constructed messag

[ethan0]

It doesn't have to be random garbage at the end. For example, say you have an image in the document without any sort of compression. Changing a bit here or there will affect, perhaps, the shade of a few colors, but it's possible to have a large amount of modifiable data using that, while the content remains the same. And all the data is used (in displaying the image).

Re:Break only affects carefully constructed messag

[ethan0]

Yes, but the point (well, one of the points) of SHA1 is that it's really fucking hard to find a combination of characters that produces the same hash as known hash. This is not what the process described in the article affects; this is just as hard as it has always been. What the process in the article affects is calculating colliding hashes from known pieces of data. It takes a very long time, given the hash of pants, to find something with the same hash - it now takes less time than it was originally thought to calculate, given "pants", a piece of data that gives an identical hash.

Re:Break only affects carefully constructed messag

[AssFace]

Oh excellent, now I see what was being said. I figured I must have missed something.
Thank you!
(this is where at least one person needs to give me a hard time for not reading enough of the article - and for good reason)