PGP Moving To Stronger SHA Algorithms

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

Comments

Not a solution

[Esine]

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

Re:Not a solution

[anothergene]

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


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

Re:Not a solution

[Storlek]

What solution is there? Moving to a stronger hashing algorithm is surely better than doing nothing at all.

Re:Not a solution

[Anonymous Coward]

What, then, is?

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

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

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

Re:Not a solution

[Mr2cents]

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

Re:Not a solution

[CajunArson]

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

Re:Not a solution

[Eravnrekaree]

It seems like the way to fix the problem (make the encrypted data difficult enough to decode using brute force methods) is to move up to stronger algorithms. This happens continuously, it doesnt mean that the old alogorithm was initially flawed, but rather it has become obsolete due to increasing computing power. As computing power increases, this means it takes less time to decode an algorithm using a trail and error brute force process.

The user should be able to choose from several algorithms depending on their needs, their are tradeoffs for each. A stronger one will require more computing power but will be more difficult to decode using a brute force attack, and will tend to last longer agianst increasing processing power of computers. A weaker one will be much faster but also it is more trivial to decode it with a brute force attack, and as computing power increases it will become more trivial to decode via an attack. Thus there is a constant interaction between CPU speed and algorithms, as faster CPUs arise, this means stronger algorithms are needed as the older ones which were too impractical to easily attack on older CPUs have become trivial to decode on newer CPUs. However, since the CPUs have since become faster, it also means that it takes less time to encrypt the data in any particular algorithm, so while stronger algorithms are needed due to increasing CPU power, those algorithms also become more practical due to increasing CPU power.

Re:Not a solution

[Dolda2000]

It's the same solution that's been used with RSA for ages. When 512-bit keys were broken, 1024-bit keys were recommended. Now when they're almost broken, 2048-bit keys are recommended. I hear that some are already recommending 4096-bit keys.

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

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

Re:Not a solution

[Anonymous Coward]

Hey I know nothing about crypto, and I can get modded up on Slashdot! Unless you have Ph.D. in Math or CSci, you probably shouldn't be suggesting anything relating to cryptography to anyone.

Re:Not a solution

[Anonymous Coward]

Good fucking god. Score 3: Interesting. Who moderates this, Microsoft's security department?

Re:Not a solution

[Anonymous Coward]

As it turns out PGP (well, GPG) already has support for RIPEMD160 built in to it. To use this:

gpg --clearsign --digest-algo RIPEMD160 foo.txt

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

(First one: Clear signuatre; second one: detached signature)

Re:Not a solution

[Anonymous Coward]

They're just trying to avoid the problem, not solve it.

What? To keep PGP Corp alive?

Re:Not a solution

[theLOUDroom]

It seems like the way to fix the problem (make the encrypted data difficult enough to decode using brute force methods) is to move up to stronger algorithms. This happens continuously, it doesnt mean that the old alogorithm was initially flawed, but rather it has become obsolete due to increasing computing power.

Actually, in this case the algorithm IS flawed.
The issue here is not that we have more computing power, it's that someone has found a mathematical method to "beat" SHA1.

The entire point of a secure hashing algorithm is to have no better means of finding a collision than simple brute force.
Since that is no longer true for SHA1, the algorithm is indeed broken. The break isn't a total worst case scenario, nor as bad as the recent MD5 break, but this hash is indeed broken.

Sure you can take a chance and up your hash lengths, but you have no guaratee that this partial break isn't going to turn into a more complete, more severe break (which is exactly what happened with MD5).

Re:Not a solution

[hunterx11]

They are pretty forward about it. After all, PGP stands for Pretty Good Protection, not Totally Secure Protection. If you want it to be totally secure you have to use one-time pads or quantum cryptography. But 99.99% secure is enough for most people.

Re:Not a solution

[Anonymous Coward]

When 512-bit keys were broken, 1024-bit keys were recommended. Now when they're almost broken, 2048-bit keys are recommended. I hear that some are already recommending 4096-bit keys.

And it's just ridiculous, because even at 512 bits, it's much easier to socially engineer the key or plaintext away, or use other such interception mechanisms. Do you really think your script kiddie neighbor has a farm of keycracking machines in his basement? If you're transmitting information that's sensitive enough for governments to be actively going after it, do you really think you've secured your channel endpoints enough after throwing all that cpu at the channel?

Yes, key length should increase naturally, but anyone who claims they're more secure with their 4096 bit key than their 1024 bit key is basically just holding a dick size contest.

Re:Not a solution

[Dolda2000]

I've already replied to a similar question.

In short, having two different hashes doesn't add more security (at least not significantly more) than just doubling the hash length.

Re:Not a solution

[uhoreg]

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

Re:Not a solution

[Anonymous Coward]

having two different hashes doesn't add more security (at least not significantly more) than just doubling the hash length

Sure it does, because you're talking about two different algorithms. If a fatal flaw is found in one algorithm, you're still left with *something*, vs. being left with no pants.

Re:Not a solution

[Q Who]

RSA was never broken in the same way that SHA-1 is now

That's bullshit, 1024-bit keys were supposed to be safe for the foreseeable future ("military strength"), but increasingly better factorization algorithms have been devised over time.

Re:Not a solution

[theLOUDroom]

I do see your point, but remember that you could argue the RSA is useless because if I did it over a 32 bit address space it's easy to prime-factorize any number and therefore increasing it to a 2048 bit space is "just avoiding the problem".

You are comparing apples to oranges.
We're talking about a mathematical breakthrough, not the release of the newest processor.

This problem isn't arising because we have faster processors, it's arising because someone has discovered a fundamental flaw in the algorithm. Sure you can take your chances and hope that this work won't beget more research which shows that SHA-1 can be comprimised even easier than we think now, but that would just make me think you weren't paying attention during the whole MD5 situation.

First somebody finds a chink in the armor.

The next person punches right through it.

Maybe somebody won't be able to take this finding any further, but I think it definately hasn't been out there long enough to be able to say that yet. Worry that someone else will be able to take this reseach and the newfound insight into the algorithm that it provides to show that SHA-1 is even less ecure than we think now.

Re:Not a solution

[vagabond_gr]

Such use-whatever-you-can solutions can indeed make intruder's life harder, but cannot offer true security. Even using two algorithms concurrent collisions will exist (due to the infinite number of collisions for each algorithm). If someone can find collisions for each hash function, nothing can guarantee that he will not find one for both. The problem is that the algorithm's security foundations are shaken, so we can no longer trust it.

It's like using two passwords instead of one. Of course it's better, but it can only slow down an attacker who knows how to break passwords.

Re:Not a solution

[uhoreg]

Yes, you are right. I will blame a brain hiccup.

Re:Not a solution

[omb]

I beg your pardon; this is what is the matter with /. today; knee jerk posts with absolutely no inderstanding. Read the Papers.

Re:Not a solution

[Tzarius]

Such use-whatever-you-can solutions can indeed make intruder's life harder, but cannot offer true security.

Indeed, nothing can. But Mr2cents' suggestion is definetely interesting, as it would exponentially increase the difficulty of generating a specifically sized chunk of data to match two different hash algorithms, while still containing the intended message. (Perhaps even more so than just doubling the keylength, as the complexity is increased).

It's like using two passwords instead of one. Of course it's better, but it can only slow down an attacker who knows how to break passwords.

That's not the best analogy - it would be more accurate to say "It's like using two different passwords, methods and sets of software to double-encrypt your data", but as you can see I'm pretty terrible with analogies.

Re:Not a solution

[uhoreg]

I should add, though, that RSA keys have never been claimed to be of a certain bit-strength. It's always been contingent on "what's the best factoring algorithm at this time?" The strength of RSA keys is based only on the belief that factoring is NP-hard.

On the other hand, SHA-1 was supposed to give 80 bits worth of collision resistance. Now it seems like it only gives 69 bits.

Re:Not a solution

[Captain Segfault]

The strength of RSA keys is based only on the belief that factoring is NP-hard.

Umm... this actually *isn't* generally thought to be true.

It *is* generally thought that factoring is not in P, but since the associated decision problem is in both NP and co-NP, showing it to be NP-hard would imply that NP=co-NP, which would be a result almost as big as resolving P vs. NP.

Re:Not a solution

[Anonymous Coward]

Er, using multiple hashes doesn't help you.

sha1(md5(input)) would just make a weird input for sha1, but sha1 is breakable not through simplistic input, it's just breakable.

Now appending hashes is the next obvious step, which I think is what you're talking about. Here's some scenarios that demonstrate appending or merging hashes isn't good security,

1. If you're going to be appending hashes you shouldn't merge two already broken hashes to each other -- that has an attack better than brute force.

2. It's possible that multiple hashes might be easier to crack than a single, because they can attack the MD5 and then those valid inputs as tests against the SHA1. The weakness of MD5 has now described possible inputs for the SHA1, significantly lowering the time to attack SHA1.

Merging hashes is not a good idea... for the length and the processing time - it's still not as secure as SHA-256 or SHA-512.

Please Slashdot readers, look for crypto experts, not posts on this forum.

Oh crap, irony.

The approach to take is to have multiple hashes of md5, sha1, and other hashes

Besides, this

Re:Not a solution

[Zangief]

What do you propose? That they change this universe's mathematics, so SHA-1 is secure again?

Re:Not a solution

[darkonc]

Sure it does, because you're talking about two different algorithms.

Not really. SHA1+MD5 can be expressed as a singular algorithm that produces the combined signature.... thing is, you now end up with one algorithm broken in two different ways that may actually allow for an easier breakage down the road (it's a bit harder to predict, given that you're now looking at a relatively ad-hock concatonation).

It's not that it's a known breakage -- rather that you're now looking at a very ad-hock union that hasn't been carefully designed. In some ways, it's better to go with widening the key on a well designed system with known breakage than to go with an ad-hock system with unknown properties (other than two different kinds of classes of known holes).

Re:Not a solution

[Anonymous Coward]

I didn't say it was as secure as sha-256 or sha-512. A week ago you might have been saying 'as secure as SHA-1'. Read for comprehension ... oh yes, this is slashdot, the irony.

Say I have a message 'M', and two digests 'D1' and 'D2', which are each calculated using different algorithms. Answer this question: Will it be easier for you to find a message that you can digest to just 'D1', or to find a message that will digest to both 'D1' and 'D2'?

If one of the algorithms is compromised (SHA-512, say), would you like to have a backup digest, or nothing at all?

Re:Not a solution

[vagabond_gr]

Mr2cents' suggestion is definetely interesting, as it would exponentially increase the difficulty of generating a specifically sized chunk of data to match two different hash algorithms

What I'm trying to say is that you don't know that this would exponentially increase the dufficulty, you just complicate things and this is not good for security. That's why the response to the discovery of an attack is not "let's encrypt 5-times with all available algorithms". Understanding and extensively testing an algorithm is indispensable for security. After a lot of work we now know that SHA-1 breaks in 2^69 calculations and we believe that SHA-512 wont break so easily, at least not very soon. Combining hash functions is just a "dirty" trick for which we have no results and no knowledge.

Re:Not a solution

[Anonymous Coward]

If one of the algorithms is compromised (SHA-512, say), would you like to have a backup digest, or nothing at all?

Well, lets say you've got message 'M' and 'D1' which is an MD5 and 'D2' which is SHA1, and there's an assumption that the message is 1-32 chars long.

So you attack and break the MD5 and get many possible messages that generate the same MD5. Now you've got significantly fewer messages to test against the SHA1.

This applies to all hashes. Scheiner and other crypto guys talk about merging hashes as having a problem of any hash being the weakest link in the chain.

Re:Not a solution

[Anonymous Coward]

Sure it's ad-hoc. But as we've seen, "carefully designed" doesn't guarantee anything either.

I'm *not* trying to say that using both SHA1 and MD5 digests is equivalent to creating a digest who's bit length is effectively 160 bits plus 128 bits. I'm just saying that it may provide better security than either one of them individually. The fact that the algorithms are disparate helps protect against one of them being potentially useless.

Can it hurt? If one algorithm is compromised, then that reduces the set of messages that have to be searched in order to find messages that will create the digest calculated by the other algorithm. Not good. In that case, you'd rather just be using the other algorithm by itself.

You've increased your probability of attack, because now there are two algorithms that are potentially vulnerable. But you've decreased the potential severity of a compromise, because there is still another algorithm in the way. Even if it's not as effective in combination with the compromised algorithm, it's still provides *some* protection.

If a compromise was discovered for one algorithm, then you can stop using it immediately. If your application was initially designed to use both, that's much easier than if it wasn't.

Re:Not a solution

[Anonymous Coward]

So you attack and break the MD5 and get many possible messages that generate the same MD5. Now you've got significantly fewer messages to test against the SHA1.

Sure. And by using two digests, you increase the probability of compromise because if either one of them gets hit, the other suffers. So then you'd like to just use the other one. But you've still got something that's better than just using the compromised algorithm. Which is 'better' or 'worse'? Depends on your application, I'd say.

If your application was designed to use both from the outset, switching to the uncompromised algorithm will be easier than if you only designed around one of them.

Look at all the digest options built into popular tools like GPG. Makes it easy to pull a switcheroo.

So here's a question. Is it better to use multiple algorithms simultaneously, and then switch them off when a compromise is found, or to just use what seems best at the time, and then start using something else if a problem is found? Of course this starts to get into specific application design, but in a general sense, I'd still lean towards using multiple simultaneous algorithms, and build in a 'kill' switch.

This is actually relevant to a [et project I've been kicking around, so I *do* want to make sure I understand this as best I can.

Re:Not a solution

[darkonc]

Once you do that, then why not just go to a brand new algorithm? That's actually what's being done -- whether it's sha256, or tiger.

Re:Not a solution

[Anonymous Coward]

The crypto experts disagree with you.

Re:Not a solution

[Anonymous Coward]

So the question is whether it's more safe to storer multiple hashes and then kill them off as they're compromised?

Well, there's the weakest link thing.

If your database is stolen and you've got a weak link then they'll attack that to generate valid messages, and then try the messages on the more complex hashes.

Say if you've got SHA-256 though and they find an attack on that in 1 year, and they stole your database today, then that weak link of SHA-256 would be exploitable.

If you could kill the weak links immediately then that'd be good, because you can move to a better hash. But you've got to weigh that up against how you can't delete old stolen data.

I think that's the argument.

Re:Not a solution

[E_elven]

I'm certainly no crypto expert. Is it even potentially possible to devise an unbreakable crypt/hash algorithm? As I understand, even the quantum crypto thing-o'magic would only reveal if the message had been compromised but not prevent that happening? All the literature I've read suggests that we're working from an unfeasibility standpoint, not an impossibility-one.

Re:Not a solution

[Tzarius]

Understanding and extensively testing an algorithm is indispensable for security.

Of course - I understand that complexity isn't necessarily security. I was referring to hashes though, not encryption. I'm not suggesting to make a hash of a hash or anything like that, but to use 2 different hash functions to verify a single public file.
For example, if it became common practice to use SHA-256 and RIPEMD-160 on BSD downloads, then even if one algorithm was reported "broken" or significantly compromised, then there is still the other function to weaken before it becomes feasible to modify the file without changing either of the hash results.
Of course, this sort of technique wouldn't carry over to many other areas, as you say.

Re:Not a solution

[ArbitraryConstant]

"Once you do that, then why not just go to a brand new algorithm? That's actually what's being done -- whether it's sha256, or tiger."

SHA1-256 is not a new algorithm. It's essentially the same algorithm with twice the bits. I'm pretty sure it's also vulnerable (it just has more bits so an attack is harder).

It's an acceptable solution for the time being, as an attack on SHA1-160 is just barely this side of practical even now.

As for why they don't just hop on new algorithms... SHA-1 was designed very carefully by the best of the best, and it's been in the wild for a very long time for a crypto algorithm. And it's just now that it's been broken.

Nobody wants to commit to a new standard only to have it turn out to be flawed as well.

The next few years are going to be a time for math grad students to become men, I'll tell you that much.

Re:Not a solution

[EsbenMoseHansen]

It is perfectly possible that when a SHA-256 and RIPEMD-160 a both present/combined, some trick will break the combined algorithm. Indeed this is just as likely as either algorithm having a flaw.

That is the heart of the problem.

If we are talking brute-forcing, it would be simpler (=fewer bugs) to just double the length of one hashing function.

Re:Not a solution

[Anonymous Coward]

Exactly. I cant figure out if the people who say that are just random idiots or TLA trying to lure people into a false sense of security.

Why have two? One is MOOOOOOOOOOOOOORE than enough. In fact, just put your secrets in a MS Word doc and use a long password.

Re:Not a solution

[Kjella]

I'm certainly no crypto expert. Is it even potentially possible to devise an unbreakable crypt/hash algorithm? As I understand, even the quantum crypto thing-o'magic would only reveal if the message had been compromised but not prevent that happening? All the literature I've read suggests that we're working from an unfeasibility standpoint, not an impossibility-one.

Well, it might be possible, but it is as good as impossible to prove. Take a crypto algorithm. We can make one unbreakable by brute force (i.e. not enough power in the universe to do it). But we also know it is solvable in a relatively short time with the decryption key. So you can't use a "lower bound" approach. What you're looking for is a proof that it is not solvable (in less than brute-force time) by any other algorithm. It might *be* so, but you'd have hell proving it (again usually you do a lower bound approach - which doesn't work).

A perfect hash function is also quite simple to describe: A perfectly chaotic function. But to prove that any function does *not* have any pattern is again extremely difficult, if at all possible.

Kjella

Re:Not a solution

[mattpalmer1086]

I'm not too clear what you mean by "widening the key" - these are hashing algorithms. They don't have keys. Do you mean using an algorithm that produces a longer hash output, or one that operates on more bits simultaneously to produce it's output (potentially giving better mixing, for example)?

You are probably right that sequentially applying one hash algorithm to another may not give increased security - impossible to know really without cryptanalysis, but probably not worth taking the chance.

But I think the parent poster is correct to say that applying both hash algorithms to the original file and recording both hash outputs would give increased security, as it would be much, much harder to find a single alternate file that produced a collision for each algorithm. What's likely to work in producing a collision for one algorithm is not likely to work for the other.

Re:Not a solution

[darkonc]

SHA1-256 is not a new algorithm. It's essentially the same algorithm with twice the bits. I'm pretty sure it's also vulnerable (it just has more bits so an attack is harder).

Er, yeah. I kinda deduced that, but my point there is that you still have to edit the code to SHA1-160 to get to sha1-256.. once you do that, you then have the choice to go to 512 bits as well -- or completely replace it with one of the newer candidates. -- rather than going with two known-broken algorithms in their current forms and bitcounts, which is at least as much work for a less well-defined result

One thing that gets me is why would people have presumed that SHA-1 wouldn't have smaller collision fields than it's bit width? I realize that it's carefully designed by really good people, but they should know that if you can't prove that it's not possible then you shouldn't bet on it.

Re:Not a solution

[Rei]

How is this just a stop-gap, or "avoiding the problem"? The crack in the SHA-1 algorithm simply reduced the search space. They just expanded the search space. To counter their dramatic increase in the size of the search space would require finding yet *another* weakness in the algorithm. I'd be more concerned about switching to a less analyzed cipher.

What I don't get is why PHP was using so few bits before. I mean, it's not like your average user of PGP was made to wait for hours to decrypt its contents....

Re:Not a solution

[rbarreira]

Actually it adds less security than doubling the hash length, due to a result found by Antoine Joux. Look it up :)

Re:Not a solution

[Tony-A]

Closer to being left with no pants if there is a fatal flaw in either algorithm.

Combining is too much like Knuth's "Super-random" number generator. [p 4, Algorithm K, AOCP vol 2] "In fact, when this algorithm was first put onto a computer, it almost immediately converged to the 10-digit value 6065038420."

Why only small improvements in security?

[ABeowulfCluster]

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

Re:Why only small improvements in security?

[TheKidWho]

I think ill wait for the SHA-QuantamExtreme algorithm instead thank you.

Re:Why only small improvements in security?

[Anonymous Coward]

Hmmph. In my day, we used ROT13, and WE LIKED IT!

Spoiled brats. /geezer

Re:Why only small improvements in security?

[fatman22]

Ah ha - so you're the clown causing EICAR hits in my cache. Any particular reason you're using that as your sig?

Re:Why only small improvements in security?

[Anonymous Coward]

Don't you mean SHA-65536?

Re:Why only small improvements in security?

[Jarvo]

Bah. RSA-640k should be enough key length for everybody.

Re:Why only small improvements in security?

[Jarvo]

Oops. I meant SHA...

Remember kids, preview your posts first.

Re:Why only small improvements in security?

[MighMoS]

Bah! I think I'll just resort to bit-flips and hope no one knows what I'm doing :-D

Re:Why only small improvements in security?

[MighMoS]

Wait...SHA isn't encryption. Its just a hash. Damn. So I'll just write a program that bit-flips the hash and...oh never mind.

Come on...

[debilo]

... who broke the SHA-1 algorithm.

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

Re:Come on...

[no parity]

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

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

Re:Come on...

[JoshRosenbaum]

Mod parent up. Please get your terminology right on this and stop spreading FUD. They 'crippled' it, they did not 'break' it. -- Josh

Re:Come on...

[Anonymous Coward]

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

And what exactly would you consider broken? Since when was "it don't work as we thought" not good enough?

Let me give you an example. You sign your Last Will and Testament digitally. You can do that; the courts will uphold it. Now, these fine researchers can concoct a new Will that says something different, but still appears to be signed by you.

Of course you already knew they could do that, but you thought it would take 20 million or so years. As it turns out, your estimate was several orders of magnitude too high. That's what these researchers have proven.

Is SHA-1 broken yet?

Re:Come on...

[octaene]

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

Re:Come on...

[slavemowgli]

From a cryptography point of view, that *is* breaking it.

Re:Come on...

[abelsson]

No, they did indeed break it. An attack is now practical for a well funded adversary, where it wasn't before - practical attacks being known is the very definition of when a cryptographic algorithm is considered broken.

Re:Come on...

[tomjen]

--you thought it would take 20 million or so years. As it turns out, your estimate was several orders of magnitude too high.--

So it will only take them a thousand years? that i can accept too.

Re:Come on...

[pherthyl]

And since "large number of trials to find a collision" is one of the major selling points of an algorithm like that, they effectively broke it.

Yes its still mostly secure, but do you really want to trust that "mostly"? Better to go to something better before the shit hits the fan.

Re:Come on...

[sahonen]

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

Re:Come on...

[Anonymous Coward]

I'd rather have a 1024 bit hash "broken" by a 2^1023 attack than an unbroken 12 bit hash.

What matters is the complexity of the attack (2^1023 vs 2^12), plain and simple.

Re:Come on...

[menscher]

All they did was provide a hash that produces 1 collision

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

Re:Come on...

[menscher]

No, it's not practical for a well-funded adversary. Their attack only made it 2048 times easier. That's not particularly significant, in itself. What *is* significant is that it suggests that other attacks might be possible. But as it stands, SHA-1 is quite secure.

Fighting the FUD....

Re:Come on...

[Anonymous Coward]

I'd say -- what matters is that there has been a proven method to solve SHA-1 with less complexity than what should be possible. Who knows how "optimized" the current solution is, who knows if there are more efficient ways to solve it. The only thing we know now is that there is at least one method to reduce the complexity by orders of magnitudes.

Re:Come on...

[Daniel Ellard]

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

... by people who don't know better.

Re:Come on...

[Anonymous Coward]

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

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

That's broken.

Re:Come on...

[abelsson]

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

Fighting the FUD, indeed.

Re:Come on...

[CastrTroy]

Didn't they already prove this broken by creating a database of all hashes possible for all alpha-numeric passwords up to a certain length. I think it was for a different hash though. Anyway, if you're going to spend all the computation power to break passwords, you might as well just make a reverse hash database, it will be much more useful to you.

Re:Come on...

[Anonymous Coward]

They didn't produce a hash, they produced a technique better than brute force for producing arbitrary hashes.

The way you describe it makes it sound like they stumbled upon a collision.

Re:Come on...

[Taladar]

And even if it isn't it is much better to talk of a non-broken algorithm as broken than talking of a broken one as anything less than broken.

Re:Come on...

[kiltedtaco]

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

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

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

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

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

Re:Come on...

[Anonymous Coward]

SHA-1 may be insecure if you:

• Have a well-funded advisary tell you "Document A is singed by us" and then replace Document A with Document B.
• Sign something a well-funded advisary gives you, without adding some noise yourself to what you sign.

Otherwise, SHA1 is secure. For example, SHA1 can still be used for protecting against people rooting your file server and replacing your programs with trojans.

Re:Come on...

[theLOUDroom]

distributed.net has already completed a 2^64 operation challenge a few years ago, which along with Moores law puts 2^69 ops into the realm of the possible.

What's interesting about this is that a project like this might actually have a chance of succeeding now.


See this link, section 1.2 for a little more detail on the subject.
While this doesn't help them with discovering Microsoft's private key, it could allow them to generate a modified version of a tool like GRUB who's bits hash to the same value as a Microsoft-approved binary.

Although not quite as cool as getting the actual key, this would allow running arbitray unsigned code without the need to buy a game and use a buffer overflow exploit, solder in a modchip, etc. This might also work for other game systems and similarly locked down devices.

Re:Come on...

[uhoreg]

What you are describing is a different type of attack from what the Chinese researchers discovered. Their attack allows them to generate two messages that have the same hash; it doesn't allow them to generate a message that hashes to a fixed value. So password hashing is still safe -- AFAIK, there are no known attacks against it other than brute force (or rubber hose).

Re:Come on...

[Aeiri]

If someone uses funding of $25-38M to break an algorithm of mine, then I want them to be able to break it. It'll make me feel good that someone wants my information that badly, especially when it's stuff like "hmm I need to get eggs tonight after work".

Re:Come on...

[uhoreg]

All hash algorithms are vulnerable to this if you don't use a salt (or too small of a salt). UNIX-like OSes have been using salt for a very long time (if not forever). See, for example, the crypt(3) man page. If you use a large enough salt, precomputed hash databases are pretty much useless.

Re:Come on...

[Rich]

Are you sure about this? as i recall you could easily append, but the collision needed to be at the start.

Re:Come on...

[jallen02]

According to Bruce Schneier a machine can be built that can do it in 56 hours.

Jeremy

Re:Come on...

[kiltedtaco]

I re-read the paper, and realize there is more than one way to interpret a part of it. I'm looking, but until then don't trust what I just posted. I may be forced to mod myself -5 misread the fine paper.

Re:Come on...

[m50d]

I only start with ones that say that. As someone else suggested in the last thread, use a .doc or .pdf and make 2^80 versions just by putting various garbage in the comment.

Re:Come on...

[tigersha]

If your will is written as an ASCII text file, yes.

If your will is written in a binary format (word, PDF, OO) then its feasible to insert junk to compensate for that extra 0 you added to the amount you inherit.

Many file formats ignore junk or have the ability or can have comments inside the file which never appear in the document.

OO, for instance is a compressed XML file. You can insert you junk as an XML comment in the file which will never show up in the word processor unless someone unzip it andexamine the XML itself. Which ain't gonna happen.

Re:Come on...

[Anonymous Coward]

All they did was provide a hash that produces 1 collision as a proof that they have an algorithm that makes finding collisions easier.

That was the MD5 weakening, not the SHA-1 one.

Re:Come on...

[Anonymous Coward]

i found a way to reduce the number of trials needed to find a collision...

i just have to try one of the possibilities and there you have it... there is one less trial needed..

Woohoo.. I have broken every encryption method ever known and every one that will be made in the future.
im a 1337 h4x0r

Re:Come on...

[da_matta]

I quess quess it's a matter of an opinion what is considered a "break", but the required 2^69 is still pretty damn much. According to http://citeseer.ist.psu.edu/287428.html it's (complexity theory wise) somewhere in the neighbourhood of breaking 880-bit RSA! To give some more perspective, breaking of RSA-512 (about 1/1000th of breaking RSA-880) in 1999 took thousands of computers and several months of distributed computations. So it's quite safe to say that it's still not easy to find collisions in SHA-1.

Re:Come on...

[Anonymous Coward]

I suspect you'd have to put the canned collisions at the beginning of a sequence but, if you know enough of the internal state at the end, you'd be able to compute new collisions to append. Or maybe you only would for some property of the internal state. But I can't see any good reason why it'd be limited to the beginning - that's just a simpler, more frequent case.

Re:Come on...

[Anonymous Coward]

if the salt is encrypted by another method it would make databases useles, as the crypt algorithm uses its salt, databases are quite usefule, you break a password, and you only need to use every other salt on the password file to breake any matching one

Re:Come on...

[virtual_mps]

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

That's false for two reasons. First, you'd need to actually get the hashed version of the password. On most systems that requires privileged access--they aren't just available to anyone who asks. If an intruder has privileged access to your system you have bigger problems than the possibility of someone breaking your hashed passwords. The other thing is that not all collisions will result in valid passphrases. Most systems won't accept, for example, null bytes or special characters or thousands of characters in passwords. So its not enough to find a collision, you need to find a valid collision.

the problem is still there

[bird603568]

wouldn't the problem still exist but the odds of cracking it would be so huge it wouldn't be worth it?
right? correct me if im wrong.

Re:the problem is still there

[Shazow]

There is no way to make an encryption algorithm without it being utterly uncrackable, if even by trial and error.

There's always "problems", the game is making them as insignificant as possible.

Re:the problem is still there

[cnettel]

The problem in SHA-512, as known now, would be far more unlikely than the inherent "weakness" in the original SHA-1 hashing (i.e, you can [just about] always find a collision by trying enough combinations).

[just about] => if one hash was unique for a very specific data set with data sizes larger than the hash size, one could argue that this would also be a problem in the hashing algorithm. If you were able to backconvert to password + salt from hash, that would be minusminusgood.

Re:the problem is still there

[pclminion]

Well, until mankind figures out a way around the pigeonhole problem -- which is NEVER -- this "problem" will always exist.

What we should be asking ourselves is, is there a way to construct a hashing algorithm for which the OPTIMAL method for finding collisions is a brute force search? So far it hasn't been done, and it hasn't been definitely proven to be possible or impossible, either.

I see a lot of people on these forums complaining that we should "just" make a hash algorithm that is unbreakable. It's a logical impossibility. Can you fit an infinite number of things into a finite number of holes and guarantee that each hole has at most one object in it? I hope people are capable of grasping that, at least.

Re:the problem is still there

[Anonymous Coward]

SHA-1 is NOT AN ENCRYPTION ALGORITHM.

It's a cryptographic one-way hash function. It's entirely possible to make one which is utterly uncrackable (Short of Brute Force), in theory. The trick then is to make it large enough to make brute force not an acceptible option.

Re:the problem is still there

[Ziviyr]

If you were able to backconvert to password + salt from hash, that would be minusminusgood.

According to my newspeak dictionary, that'd be double-plus-ungood.

Re:the problem is still there

[kiltedtaco]

HAH. That's the first times i've ever seen someone get their newspeak grammar corrected. I like it.

Re:the problem is still there

[InvalidError]

Singularities most likely do exist but finding them for all common block sizes would take something close to infinite time... even with shortcuts to cut the effective key size in half, testing 2^80 cases (instead of 2^160) for one particular block size would still take milions of years even if processing power increased by hundreds of times.

Now that processing power fell from doubling every 18 months to increasing by less than 50% every two years, crypto should be relatively safe from exponential advances in the future - at least until the next big thing happens.

Re:the problem is still there

[Llywelyn]

Slight clarification.

It is a logical impossibility to make one that dodges the pigeonhole principle, i.e., one that is "collisionless."

This is different from whether one can be "broken," i.e., a message can be found that collides in less than brute force time (2^80 for SHA1).

Re:the problem is still there

[m50d]

That's not what he's asking. Is the break still there, making SHA-256 under strength? Is it just a question of going to 2^149 to break it, raising the possibility of further breaks, or will it be a full 2^160 to get a collision?

Why not move sooner?

[}InFuZeD{]

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

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

An ounce of prevention...

Re:Why not move sooner?

[tomjen]

true, but it takes time for a hash function to be proven secure - that is a lot of different people have to crypto analyse it to se if it can be craked.

Try googling for whirlpool

Re:Why not move sooner?

[Anonymous Coward]

If you had RTFA you would have known that they did in fact start working on SHA-256 and SHA-512 last year.

Re:Why not move sooner?

[Storlek]

Google for whirlpool produces a bunch of pages about the washing machine company. This is probably what you're referring to.

Re:Why not move sooner?

[Anonymous Coward]

Is there a reason to wait until someone breaks the existing algorithm before moving to a stronger one?
It seems to me that if you start working on implementing the stronger ones BEFORE your existing one is broken?

Because of the chance that someone might find a weakness in the supposedly stronger one before a weakness is found in the supposedly weaker one.

Since you don't know which algorithm is going to be broken first, you pick one based on other advantages, like wider availability and more efficient calculation.

And, BTW, SHA-1 is not cracked wide open yet; it just looks worryingly like a usable flaw will be found in the very near future. Therefore, people are moving away from it. An ounce of prevention... exactly like you said.

Re:Why not move sooner?

[Webmonger]

They started moving to SHA-256 last September. According to TFA:

Jon Callas ... addressed the company's design philosophy in a September 2004 ... article ... At the same time, PGP engineers began implementing a shift from SHA-1 to the stronger algorithms (SHA-256 and SHA-512)

Re:Why not move sooner?

[thogard]

If this hack was for a 128 bit SHA (which its not) that results in reduction of search space by a factor of 2048 or so, then there is a good chance that the same technique can reduce a 256 bit SHA by a factor of 4096, 4194304 or 8589934592.

Hashes major weakness is the fact that its block related. As soon as you find one block you can swap out in a file, then the rest doesn't matter at all. A hash that can keep state is much harder to mess with but that gets rid of the ability to hash as stream process.

Re:Why not move sooner?

[Webmonger]

Personally, I'm more worried about the possibility that further investigation will break SHA-1 wide open. SHA-256 breaking won't be practical with current techniques for quite some time.

Re:Why not move sooner?

[Anonymous Coward]

SHA-256 is not strong if SHA-1 is broken wide open so moving to SHA-256 at this point doesn't buy you anything.

Re:Why not move sooner?

[tomstdenis]

Jon callas is an asshat half-wit who wouldn't know his arse from a hole in the ground. I met him at ToorCon and he basically was a snotty little bitch interrupting people and causing a stir.

As for why people aren't already using SHA-256 instead? Because things like DSS mandate the use of SHA-1 *AND* people are too lazy to keep up.

Not that *cough* libtomcrypt *cough* free crypto is hard to get. Just people have to realize that, yes, you have to spend time and money to get crypto right...

Tom

Re:Why not move sooner?

[Webmonger]

No one has broken it wide open yet. Any attacks that make it easier to hack SHA1 will probably make it easier to hack SHA-256, but since SHA-256 is much harder than SHA-1, it will remain very hard to hack.

Not saying we shouldn't find better hash techniques, but there *is* a reason to move to SHA-256

i'm no crypto expert...

[Phil246]

but why not take a hash of a hash ?
if its broken once - all you get is another hash and with no way of telling if you`ve cracked it or not, its useless

Re:i'm no crypto expert...

[Shazow]

Technically, that would simply double the number of operations required to perform the decryption, which does not effectively raise its complexity..

ie. say it takes n time to crack a hash, then cracking a hash of a hash would take 2n...
O(2n) is still O(n)

Of course that's assuming they aren't doing it by "eye" and they have some sort of solid algorithm to do it.

- shazow

Re:i'm no crypto expert...

[bird603568]

im not 100% sure but if the hash is CRACKED you can just crack the second hash. Also from the little but if hashingive dont in class, you proball you ahve alot of collisions, which arent good.

Re:i'm no crypto expert...

[bird603568]

im perty sure it would be O(n) for the first break, then O(n) again which you said, but i THINK that would come out to be O(n^2). its like running a for loop inside a for loop

Re:i'm no crypto expert...

[Anonymous Coward]

No, it's O(2n).

You have to find a collision for the first hash, then one for the second hash, and then it's broken.

This doesn't matter what hashing algos you use, even if you use different hashes, because you break the first one, then break the second one.

It WOULD be O(n^2), however, if you hashed the data in two separate hashing algos, and then used BOTH to sign... So hash it in SHA-1, SHA-256, SHA-512, MD2, MD4, MD5, Tiger, Whirlpool, AND RIPEMD-160 if you're really paranoid.

Re:i'm no crypto expert...

[Sweetshark]

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

Re:i'm no crypto expert...

[Anonymous Coward]

But what is the complexity of finding an identical collision for two hashing algorithms ? If I hash document D with MD5 and SHA-1 and always use both hashes (by concatenating them for example) I would need to find a document D' which is a collision for both MD5 and SHA-1, pretty tough no?

Same question, if we use SHA-1(D+MD5(D)), finding a collision become really hard too no?

Re:i'm no crypto expert...

[Trejkaz]

Tough, but not as hard as O(n^2). For various reasons, adding two hashes together doesn't actually make the work much harder than it already was. You get better security out of switching to a newer hash function.

Re:i'm no crypto expert...

[Shazow]

Well, as I said, if you have a safe algorithm which reliably cracks a hash string, then it's O(n) (since O(n) + O(n) = O(n) ). If you brute force it, then yes, for every hash string of brute forcing, you'd have to do just as much brute forcing, which is O(n^2).

Re:i'm no crypto expert...

[rastos1]

Several answers were provided in other replies, but IMHO the major point is that you reduce the length of the input (probably large) docoument to fixed (small) size of 1st hash. Which makes it much easier to create a list of possible values for 2nd hash.

Re:i'm no crypto expert...

[Anonymous Coward]

No, it's O(2n).

You have to find a collision for the first hash, then one for the second hash, and then it's broken.

True, if you have means to reverse it completely, but when you can merely force a birthday-like collision because of a vulnerability, it doesn't work the same way. (but no, the problem doesn't necessarily become squared either..)

In other news...

[slavemowgli]

In other news, advertising on Slashdot is now free: just submit your ad as a story, and some editor will post it without even reading it.

Bah.

[koreaman]

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

Re:Bah.

[WombatDeath]

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

Re:Bah.

[God! Awful 2]

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

Are ROT-13 jokes still +1 funny?

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

-a

Re:Bah.

[Anonymous Coward]

That's why I stopped reading Slashdot Articles. All of them seemed to be double ROT-13 encrypted.

Re:Bah.

[HermanAB]

Nah ROT is soooo passe. I use Double DES.

Re:Bah.

[Wordsmith]

Actually, Rot-13 jokes are still +14 funny.

Re:Bah.

[TheRaven64]

I'm sorry, but encrypting your post with ROT-52 didn't make it any more funny.

Re:Bah.

[Spunk]

Man, this joke has been done. Stop beating a dead wombat.

Have to buy it again?

[ehiris]

Would current customers have to buy PGP again? I see the problem as a bug not an "old version" weakness.

Re:Have to buy it again?

[cnettel]

I think it's a bit of both. The current weakness shown is still so computationally intensive that, IIRC, it's equal to less than two decades of Moore's observation. Ok, that's quite a lot of time, but it's not like it was thought that it could "never" be cracked (by Turing machines) before the discovery.

Re:Have to buy it again?

[Anonymous Coward]

Are you really that cheap? How is this possibly a bug? It would be a bug if it was done in a way that would easily allow for the decryption of the original message. And that looks to be still at least 10 years away based on computing speed laws that hold fairly steady. Step up and pay for the new versions (if necessary) which will include a more robust algorithm that again will someday be broken.

Re:Have to buy it again?

[Orion Blastar]

Yes and apparently older versions of PGP for abandoned platforms may not be updated. Which means those OS/2, MacOS 7.X (and earlier), BeOS, MS-DOS, and AmigaDOS ports may not have an update to deal with the new SHA methods.

I use an Amiga 500 using AmigaDOS 2.0, I want my PGP for it updated! I'll give up my Amiga when they pry my cold dead fingers off the Amiga 500 keyboard and Amiga mouse. I've already written nasty letters to OSS developers who refuse to support my platform of choice. I mean they should be able to release that GCC compiler for AmigaDOS and then port Mozilla Firefox, OpenOffice.org, Mozilla Thunderbird, and others to the AmigaDOS platform. I currently have PGP 4.0 for AmigaDOS, and I want it updated, please! I am also stuck using the Wordperfect 4.0 for the Amiga to write my letters with. There were over 3 million Amigas sold, and many more Amiga users via Amiga emulators, we currently number as many Amiga users as the same number of MacOSX and Linux users due to all of us using emulator on different platforms. We want our new generation of software, please! Don't ignore us, or you'll find people in Amiga checkmark t-shirts picketing your workplace!

What about GPG?

[stm2]

Will GPG follow it? should they do it?

Re:What about GPG?

[papercut2a]

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

Re:What about GPG?

[papercut2a]

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

Supported algorithms:
Pubkey: RSA, RSA-E, RSA-S, ELG-E, DSA
Cipher: 3DES, CAST5, BLOWFISH, AES, AES192, AES256, TWOFISH
Hash: MD5, SHA1, RIPEMD160, SHA256, SHA384, SHA512

Re:What about GPG?

[uhoreg]

However, note that most people use DSA as their signing algorithm, and DSA can only use a 160-bit hash. So if you don't want SHA-1, you have to use RIPEMD-160. If you want to use SHA-256, you'll need to use RSA as your signing algorithm (which would mean creating a new key).

Re:What about GPG?

[danalien]

• but doesn't default to them.

well no, but you could set it to do it, just open ~/.gnupg/gpg.conf , and add:

#change default 'digest-algo', to:
digest-algo SHA512

.... or what ever you prefer...

BTW, if you use a DSA pub-key, you have to set 'digest-algo RIPEMD160', as your pub-key req.'s a 160-bit hash algorithm.. as you can't use the rest and MD5 & SHA1 been 'broken', doo'h :)

PS. all --<double-dashed-parameters>, can be set in gpg.conf, just strip the '--' ... saves you from needlessly long commands, +plus the added bonus of, all the apps that use gpg, will use your settings by-default.

Re:I'm all for encyrption

[GerbilSoft]

PGP, not PHP. PHP = scripting language, commonly used on Web sites. PGP = encryption program.

Re:I'm all for encyrption

[Anonymous Coward]

nicely done! Bravo!

I don't think they've officially decided to change

[papercut2a]

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

But then, I could have missed something.

Re:Article rejected by lameness filter

[Anonymous Coward]

This article is of course posted by timothy who also managed to post 2 dupes within the last 24 hours.

SHA-1 break illustrated..

[__aaijsn7246]

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

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

Hash: SHA256

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

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

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

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

- -- ...atom

Re:SHA-1 break illustrated..

[Lord Ender]

Hou don't have to tell Americans how tall 100 meters is in feet. We all know that a football field is 100 yards and a meter is about a yard.

Re:SHA-1 break illustrated..

[MrResistor]

I'm still confused. How many elephants standing on each others backs would that be?

Re:I'm all for encyrption

[Storlek]

(PHPBBQ? *mentally runs sed s/PHP/PGP/g on post*)

I would still rather see people encrypt all their data than to send (even potentially) sensitive data in plain text. Sure, the best option would be educating people on what is really important, and thus worth encrypting, but a lot of people can't seem to grasp the concept of privacy/security. I know people who would submit a credit card number to some shady website over plain HTTP, without even looking on the page for a privacy policy.

Granted, it is borderline ridiculous to encrypt anything and everything, but it's better than not encrypting anything at all and hoping nobody's looking.

Re:I'm all for encyrption

[Anonymous Coward]

Ok you're a fucking moron.

Re:I'm all for encyrption

[martinoforum]

... so, that should read "I'm not for encryption at all!"? How are you "All for encryption" if you think that having the technology available is a bad thing?

As for "There's no good excuse... doing so wastes the time of others"... which others? Sorry, but I do have problems with the possibility of an automated censor reading everybody's mail, and if having some crypto there wastes their time then that's fine by me. If you're talking about wasting the time of my family and friends, well, that's another matter. The ones that care for it will use it. The ones that don't, won't.

And... err... PHP? Do you mean PGP? Sure, it might be interpreted and a little weird on the syntax front ("->" ?!?!?), but I don't think it's a major threat to national security. Unless you're talking about SQL injection attacks, of course.

Beware of doubling the hasing

[Anonymous Coward]

IANACE too (I am not a Crypto Expert ) But, it may happen that doubling the hasing you are making it much weaker. I am not sure but my intuition tells me that it can be the case.

Re:I'm all for encyrption

[Anonymous Coward]

Hey dumb ass.. he was *obviously* joking. There is noone on this planet that dumb (that would be able to manipulate a keyboard/mouse well enough to get to Slashdot).

Collisions

[b0lt]

Why not use two hashes? It's exponentially harder to find a collision that fits for two hashes, isn't it?

-b0lt

Re:Collisions

[theLOUDroom]

Why not use two hashes? It's exponentially harder to find a collision that fits for two hashes, isn't it?

Two reasons:

1. The first is implementation specfic. Say you're using this hash function for a typical /etc/passwd file. By using two hashes you've just made yourself even weaker than if you had only used one hash. (It's like having two doors with one lock each, not two locks on one door.)
   Note that there are circumstances where you don't care about this, because the original data is public and you just want to be sure it wasn't fiddled with.
2. The second lies in that fact that yes, you are making it hard to tamper with a file by using two algorithms, but unless you have two algorithms that are exactly equally secure, you would be better off just applying those extra bits to make the hash from the stronger algorithm longer.

Re:Collisions

[Anonymous Coward]

Why not use two hashes? It's exponentially harder to find a collision that fits for two hashes, isn't it?

Sadly, no. Joux proved last year that for many hash functions (including all of the ones currently in use), concatenating hashes doesn't actually buy you that much. Goggle for multicollision attack for details.

Re:Collisions

[m50d]

Not fully when the two hashes share the same family, as SHA, MDx, and to a lesser extent RIPEMD all are. Doubling the length of the hash, as SHA-256 does, gives you a fully exponential increase. Combining two hashes may make sense when both are thought to be secure, but it's not a way to make a broken hash secure.

Re:Collisions

[mattpalmer1086]

My understanding of multi collision attacks is that it is focussed on the sequential applicaiton of a hash function:

e.g.

hash = SHA1( SHA1( message ))

Whereas I think the parent poster is talking about recording two hashes in parallel, using two different algorithms:

hash1 = SHA1( message )
hash2 = MD5( message )

Now the problem is to find a single file message2, with a collision for hash1, and for hash2. This would appear to be considerably harder, even though you can use the collisions from MD5 to feed your SHA1 testing, it is still extremely unlikely that any of them will collide - they're still quite resistant to random collision - nothing has changed there.

Of course, I'm not advocating this as a good practical solution - just pointing out that parallel application of hashes appears to be more secure than using a single one, whereas sequential application has been shown to be vulnerable to multi collision attacks.

Of course, I could be completely wrong about multi collision attacks, and if so, I'd appreciate a better explanation from someone more knowlegeable than I.

Judging from the links in the headline

[Aexia]

This appears to be a bold move.

Re:Obsolete encryption algos ....

[Anonymous Coward]

How the hell was this moded informative?

Meanwhile, in the real world....

[CastrTroy]

I realize that this means that 2 messages can be generated with the same hash. However, does this really signify such a big weakness. The person generating the hashes has no control over the content of either of the messages, nor do they have control over what the resulting hash will be. So, you can, in a reasonable amount of time, generate 2 arbitrary messages with the same, yet still arbitrary hash. So what. Unless you can generate meaningful messages with identical hashes, you don't really accomplish anything through using this technique.

Re:Meanwhile, in the real world....

[Ewan]

I believe with the md5 research by the same people, they were able to generate 2 "visibly" identical messages with the same hash by appending junk to the end of one of the messages.

so basically "This is a message" produced the same hash as "This is another message "©{"

Re:Meanwhile, in the real world....

[Rikus]

I'm sure it's already been mentioned that SHA-1 and other algorithms like MD5 are used for verifying passwords, and any collision, however meaningless it is, may be enough to match the hash stored on the system verifying the password, therefore granting the login request. Of course, this would require the hash to have been leaked first, which is also not very likely.

Re:Meanwhile, in the real world....

[Anonymous Coward]

Corrupting signed data isn't accomplishing anything?

I'd say that'd depend entirely on what sort of data.

Phones tapped?

[theLOUDroom]

So what do you guys wanna bet that at least a few of these researchers have their phones tapped at this point?

I can't think of any intelligence agency that that wouldn't like a few days head start with any more findings these guys come up with.

I'm not really headed anywhere specfic with this comment, other than getting this thought out there. People have been bugged to gain access to much less exciting information than this.

Re:Phones tapped?

[Anonymous Coward]

I seem to forget something: most of those people are in China my friend. So long with American scientific dominance ;) /just jokin'

Re:Phones tapped?

[Wesley Felter]

Sure. This sounds like exactly the kind of thing that Echelon is designed for.

Re:Phones tapped?

[Anonymous Coward]

Shouldn't they just encrypt their phone calls?

Name change!

[Anonymous Coward]

I propose a name change. Instead of "Secure Hash Algorithm", we should name it "Secure is Not this Hash Algorithm" or SNHA. That name would be more accurate.

- R. Stallman

Re:Name change!

[MPHellwig]

To be more precise:
Secure Has Is Not Ment For Encryption But For Message Digest.
SHISNMFEBFMD

Secure Hash Algorithm 1

[NEOtaku17]

SHA-1 Hash Algorithm and Source Code

Re:Secure Hash Algorithm 1

[Anonymous Coward]

Standards document for SHA-1/256/384/512 in pdf http://csrc.nist.gov/publications/fips/fips180-2/f ips180-2.pdf

Missing details to complete the perspective

[mukund]

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

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

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

Re:Missing details to complete the perspective

[Anonymous Coward]

Quoting Bruce Schneier's quote of what Jon Callas, PGP's CTO said: ...

Can I quote you on that?

MOD PARENT UP

[Anonymous Coward]

think about it, it's simple yet totally effective

For those who use PGP with email:

[Vroem]

What about S/MIME?

Re:For those who use PGP with email:

[papercut2a]

What about it?

PGP/GPG are far more flexible than S/MIME.

They started last September

[Webmonger]

According to the article,

Jon Callas ... addressed the company's design philosophy in a September 2004 ... article entitled "Much ado about hash functions" . At the same time, PGP engineers began implementing a shift from SHA-1 to the stronger algorithms (SHA-256 and SHA-512)

So they were actually ahead of things, not reacting to the break.

+1 funny, you morons

[Anonymous Coward]

Interesting????!

Re:I'm all for encyrption

[Anonymous Coward]

if that was a joke, that was not funny... I also really thought this guy was THAT dumb

Morons

[Anonymous Coward]

with every additonal hash there you give more and more information about the original key => it makes it easier to find attacks combining the info from two results from different algorithms

Re:Morons

[mattpalmer1086]

There is no key. It's a hash algorithm. Morons indeed.

Winston Churchill's Quote

[toonerh]

Churhill said, "Nothing is so exhilarating in life as to be shot at with no result", not "there's no greater thrill in life than being shot at and missed."

American paraphrasing of Churchill is no thrill to me.

Re:Winston Churchill's Quote

[Anonymous Coward]

Yeah, like toonerh said: Saying a Churchill quote American-style doesn't do anything for me.

Or.....

[grolschie]

Or... they could do a Microsoft and pretend that the vulnerability doesn't exist until after a patch has been released.

Hmmm.... methinks that perhaps moving to SHA-512 in the meantime might be a safer alternative.

Re:I'm all for encyrption

[Anonymous Coward]

Indeed. Please stop encrypting random crap, we have enough of that in our hands already. Next thing you know, some random would-be terrorist will be claimig illegal decryption of family mail under DMCA and ye'd REALLY hate to explicitly ammend the DMCA to read "US Government Intelligence Services excepted"

Best Regards,
Anonymous NSA Spokesman.

PS. also, please use ROT-1 consistently, it's RHR not PHP

Re:I'm all for encyrption

[hunterx11]

I never knew PHP was used for encryption.

Perl scripts, on the other hand, are clearly far too illegible to be considered plaintext.

This reminds me...

[Audacious]

This reminds me of the DRM debate of about a month ago here on SlashDot. I took the stance that DRM would be broken just like any of the other algorithms that anyone has come up with. I was told by one person that DRM could never be broken. Well, when SHA-0 came along they thought it could never be broken either. Then SHA-1, now SHA-256, and later it will be SHA-512. As someone else pointed out - it is just a matter of how much computing power do you want to put behind your attempt to break an encryption.

But here's a scarey thought for you: The new Playstation 3 is packed with at least three CELL CPUs and a maximum of eight. The PS3 is supposed to be an order of magnitude faster than any currently existing microcomputer. It is, therefore, a supercomputer in its own right. But that's not the scarey part. The scarey part is that the PS3 runs Linux, can be programmed just like a regular computer, and is stackable. At SIGGRAPH 2001 Sony displayed a box you could buy where you could stack up to ten PS2s and they would act like a networked supercomputer. They had a really neat display of a girl in a space station with the earth and stars outside of the window. One PS2 controlled the earth simulation and stars. One did the interior of the space station. One did the hair (so they could do individual hairs), one did the body (breathing, texture, etc...), one for facial expressions, and the rest did arms, hands, legs, feet, and some special effects (like the weightlessness). All of these functions can be done on one PS3.

Ok, so if you can buy a PS3 for an estimated cost of $350.00 USD, how many PS3s would it take to break SHA-512? DRM? Or any other encryption method? Remember that they are 64bit computers also so they can move the data around a lot faster. And - they may also be able to handle many GIGABYTES of memory (which means they will be able to break codes even faster).

We basically are building our own nightmare. We want the faster computers so we can do things faster but that means those who are destructive are also getting the same toys to play with to make our lives miserable.

Re:This reminds me...

[Unnngh!]

We want the faster computers so we can do things faster but that means those who are destructive are also getting the same toys to play with to make our lives miserable.

Which is the whole point of this research in the first place--making stronger algorithms by attempting to break the current ones. Unless funded by a government or similarly large entity, nobody is going to be breaking your SHA-1 hashes any time in the near future. The private-sector crypto community has developed very rapidly over the last 20 or so years and is capable of keeping up with even a fairly large boost in computing power.

Re:This reminds me...

[Have Blue]

We're not building a nightmare or a paradise. We're building technology that can be used for a variety of purposes. If we refrained from building anything that someone somewhere might put to a use someone somewhere else might disapprove of, we wouldn't have most of the things Slashdot reports on.

Re:This reminds me...

[Anonymous Coward]

I think perhaps you underestimate the complexity of the problem. The breaking of SHA-1, if breaking it can even be called, was not performed by hurling computing power at the task, but by very clever humans thinking very very hard.

The presence or otherwise of a ps3 would have no effect on this, unless Squaresoft released another Final Fantasy in which case the performance of said researchers would actually decrease for at least two weeks.

In the general sense, the only thing extra computing power is useful for is brute-force searching of the keyspace. Computers don't have enough operations per second left until the heat-death of the universe to break a 512bit keyspace, it is simply enormous:

134078079299425970995740249982058461274793658205 92 39337772356144372176403007354697680187429816690342 76900318581864860508537538828119465699464336490060 84096

That's a number. If you could do 100 trillion operations per second, and every single operation was a complete SHA-512 hashing operation, it would take you

425158800416749020153920122977100650922100641190 77 85825001129326395790217552494601979285355836790787 57294262372732307548635016578258

years to find the answer. Keep adding digits, cluster your system until every inch of the earth is covered, and you're simply not going to make an appreciable dent in that number. It's enormous. Sit down with a calculator and work out how much processing power you would need in hashing ops/second in order to be able to search the 512bit space in a human lifetime.

We are not talking 640kb should be enough for everyone kind of advancement here.

Many crypto algorithms will be partially or completely broken in the following years, but for the most part it won't be due to additional computing power, just motivated, smart people.

Re:This reminds me...

[Lord Ender]

Moderators: please realize this guy is talking completely out of his ass. It is clear he has never studied cryptology, even just a little. Please make sure nobody reads this comment, because everyone who does will be made dumber as a result.

Re:This reminds me...

[burns210]

And at the same time, with faster computers will be able to use larger and more advanced encryption techniques. SHA-512, -1024, 2048. It is all relative. Besides which, ecnryption is known to be breakable, the deciding factor is HOW LONG your information needs to remain a secret.

Re:This reminds me...

[DeadMeat (TM)]

the PS3 runs Linux

No, it doesn't.

can be programmed just like a regular computer

No, it can't.

64bit computers [...] can move the data around a lot faster

No, they can't.

Re:This reminds me...

[Tzarius]

You've intrigued me, sir. Particularly with regards to the "640k should be enough" comment.
I was under the impression that once quantum computing becomes practical, many complex calculations such as these would become almost trivial to brute-force. I it's not too much trouble, could you comment on this?

Re:This reminds me...

[theLOUDroom]

As someone else pointed out - it is just a matter of how much computing power do you want to put behind your attempt to break an encryption.

NO IT'S NOT.

Moore's law applies to encryption as well as decryption. Sure we can crack keys faster than we ever could before, but we can also use longer key lengths.
Furthermore, Moore's law is understood to be a fact of life at this point so it's pretty easy to plan for future increases in computing power.
Even more importantly, a linear increase in key length results in and exponential increase in difficulty.
We basically are building our own nightmare.

Chill dude.... the sky is not falling.
Cryptography does not become irrelevant just because you've got a "fast" computer.

Good crypto, not-broken-at-the-algorithm-level relies on some frickin hard math problems. Things you wouldn't be able to solve in your lifetime if you turned every atom on the planet into a transistor.

Re:This reminds me...

[Audacious]

the PS3 runs Linux

No, it doesn't.

Reply: The CELL process can run linux (and therefore the PS3 will be able to run linux) (Not to mention that the PS2 can already run Linux and why the PS3 would be unable to do so just doesn't make sense. After all, Sony is one of the companies who has come on-line for pushing Linux as the operating system.)

can be programmed just like a regular computer

No, it can't.

If caveat #1 is correct, then #2 must follow.

64bit computers [...] can move the data around a lot faster

No, they can't.

Last time I looked, 16bit computers could transfer more data than 8bit computers because the 8bit databus was updated to 16bits. The 32bit computers could transfer more data than 16bit computers because the databus was upgraded again. It stands to reason then that with a 64bit system it too will be able to transfer information at a more rapid rate than the 32bit systems. Not only because the databus would again be updated to allow larger reads and writes, but just because of improvements in overall speed of the system.

Still if a 32bit system was attempting to do 64bit manipulations and a 64bit system was attempting to do 64bit manipulations, then the 64bit system would (and should) out perform the 32bit system. Maybe not 2:1 but it should be faster because it requires fewer reads and writes to memory and/or other external devices.

I will admit that the databus itself has a lot to do with the overall speed of a given system. After all, IBM once sent us their top of the line graphic computer which had a 32bit graphics system built into it. Only it ran slower than our 16bit systems. This was because (after weeks of dealing with the IBM reps and engineers who always returned to "It was our fault") we found out they were using an 8bit databus on the graphics pipeline. Not the brightest thing IBM has ever done.

But all things being equal (that being that each system uses and/or has an appropriate structure (such as the proper databus, memory units, and such) then a 64bit system will be a 32bit system every time.

As a side note - Even if you want to talk about multiple cpus you have to have apples and apples. Thus if the CELL cpu has 6 million cpus on its chip running at 64bits each then you have to have the same with the 32bit cpus in order to properly compare them.

Re:This reminds me...

[Audacious]

Ok, I realize this is just flamebait but I have to say that this is just untrue. First you know absolutely nothing about me or my background. Second my statements are true.

Let's look at the second one first:

1. No matter how brainy you are, it requires a computer (now-a-days) to break any kind of cryptology which is in place.

2. No matter how smart you may be, you won't be able to test your premise without the usage of a computer. Further, it is not so much hard core number crunching (as in testing each and every possible combination which would take millions or billions of years to do) as it is coming up with an algorithm which will work.

3. In the case of DRM, we are using and following rules which we have devised to tell us how we can make use of Quantum particles to generate random numbers. As such, it is not impossible for someone to accidentally stumble upon or even develop on purpose an algorithm which will undo what was done. It is just a matter of when this will happen.

Now let's look at the first one:

1. I have never said I was a genius or even brilliant at cryptography.

2. But I have studied the field since I have worked with DoD before in various ways.

3. I have also let it be known that I do work at NASA without any degree at all. However, NASA does consider me to have several masters. Both in mathematics as well as computer science.

Finally, you are entitled to your opinion and I probably could do with some more reading in the area of cryptology. Unfortunately, presently I'm helping NASA rebuild their CAD system of information about the Space Shuttle and do not have the time. Maybe later.

Enjoy life.

Re:This reminds me...

[Anonymous Coward]

Certainly. In fact, I'll let someone else comment for me :)

Cipher reference

Esssentially a quantum computer provides many remarkable benefits, but it does not completely obliviate the benefits of a large bit size for a standard symmetric cipher, in this case you have essentially half the bit length equivalent, or 256bits...that's still a bloody huge number:

115792089237316195423570985008687907853269984665 64 0564039457584007913129639936

The big fuss about quantum cryptography is its effect on crypto systems with *known* faster than brute force weaknesses, such as public key ciphers. The problem in there is not a complete key space search, but a factoring problem. That's why we use 2048 and 4096 bit keys for RSA for example, a ludicrous size for a symmetric cipher but due to the inherent weakness in the algorithm, a necessity for RSA.

In this instance, the main defense for the algorithm is the difficulty in factoring large numbers, something which a quantum computer would be spectacularly good at.

Once again it may turn out that the availability of a quantum computer may make some algorithms weaker than expected, but it is not the mere presence of vast quantities of computational power that will break them. Nobody is going to wake up tomorrow and go, oh, by the way, we can hash the entire 160bit space of SHA-1 in a day. They will come up with cleverer and clever methods and techniques for reducing the search space utilising all the tools available, and eventually some (possibly many) algorithms will fall to one attack or another.

Re:This reminds me...

[Anonymous Coward]

Our 32-bit computers have had 64/128/256-bit data buses for ages.

Re:This reminds me...

[Lord Ender]

A lot of dumb people have worked for the DoD and NASA. That doesn't mean you know anything about mathematics or crypto.

This article was about consequences of finding a weakness in SHA-1. You started spouting off about how "computing power" is what is needed to break crypto. You said something silly about all crypto being broken with more computing power. Then you went off with some completely false information about playstations that really had nothing to do with anything.

Since you were interested enough to reply, I'll elaborate. I didn't in my previous post because I just wanted you modded down--you really were posting just plain wrong information and saying it confidently.

First of all, increased computing power is a given. But SHA-1 was broken by finding a mathematical way to find colisions with many orders of magnitude less computing power (perhaps I should say "fewer" since computing power is discrete?).

Secondly, your remark about increased computing power breaking all crypto is absurd. Computing power can not keep growing exponentially. There are only so many atoms on planet earth. But we can grow crypto without bound. A good algorithm with large keys is not ever going to be beaten just by increased computing power. Again, your statement was just wrong.

Also, this DRM talk had not much to do with anything. Do you know what a hash is used for in crypto? Do you know the difference between public and private key crypto or the math involved in them? These basics must be understood before you post as if you have a clue on a crypto article.

Also, Quantum crypto is not about random number generation. And Quantum computing is also NOT about 'really fast computers'. It is really about being able to do one kind of operation in a smaller big-o time.

I'm sure you are very good at your job, but don't hide behind the word 'flamebait'. I saw someone posting wrong and misleading information and I called him out. Don't take it personally.

Re:This reminds me...

[Audacious]

Sounds good. :-)

The largest databus I've seen was a 512 databus for a specialized graphics card. But that was a few years back at SIGGRAPH 2001. I'm sure they are past that point even now. :-)

For the majority of people - they probably either have a 32bit databus or a 64bit databus. The more you know about computers though - usually the better equipped the person becomes. Like Tom's Hardware. I knew nothing about Tom's Hardware until around 2002. Now I check it any time I am going to buy new hardware because they have very good in-depth articles about the state of computer products. I've even recommended them to several people here at NASA to check out before making a purchase.

Found 2ROT-13 insecure, use 3ROT-13 instead

[fleppir]

had to be said ......

I disagree with Schneier - not broken yet

[Whiteout]

My understanding of the 'break' is simple: given a hash, we can now find another 'message' with the same hash, not by 2^80 brute force guesses, but by 2^69 cleverer tries, a factor of 2000 improvement, and potentially bringing this attack into the realm of computational feasibility.

So what?

Until we can find a 'meaningful' message with the same hash, or until we can remove data from or add data to the original message, and preserve the hash, we can sleep easy - except the file-sharers :). Of course as soon as someone can insert something into the original data, code signing is completely broken.

But please, somebody explain to me how we're vulnerable. You can take my message and - if you try very very hard - you can create a garbage message that you could claim I signed. And that's all.

BTW, I'm well aware that applying one hashing mechanism to a message then another will not help, but why not apply two in parallel? The message would have two hashes, which isn't too much of a burden, and barely increaes the message length. Sounds good to me.

Re:I disagree with Schneier - not broken yet

[twistedcubic]

The next step is not too far off. There are already billions of ways to convert even a short message into one that looks almost identical-- swapping tabs for spaces, adding blank lines, replacing newlines with carriage returns, and of course, rephrasing messages. A large document, or a document with embedded info, like PDF or JPEG, would be even more fun to experiemnt with, since you can insert data and get the exact same rendering of the file.

Re:I disagree with Schneier - not broken yet

[m50d]

If academics have broken it by this much, how much more have the NSA broken it? They're often years ahead of the public, and a break like this is usually a sign that a full break is coming. Cracks are appearing in the wall, not big enough to be dangerous, but the fact that there are cracks is plenty of cause for concern. And the two hashes does not help, as I'm tired of explaining.

Re:I disagree with Schneier - not broken yet

[Whiteout]

Regarding the two hashes, perhaps you could point me to some reference.

If I apply two fundamentally different hashing algorithms separately to the same message, and call my hash the - say - concatenation of these, I have a hash that's (only) twice as long and twice(ish) as expensive, but presumably much less open to analysis.

Re:I disagree with Schneier - not broken yet

[m50d]

Take a look at this post and the reference there. With two fundamentally different hashing algorithms which both seem to be secure it might make sense, but very few modern hashes are fundamentally different, and SHA-1 is broken, so if you were going to combine it with something else you're better off just using a longer version of whatever you would combine it with.

Re:I disagree with Schneier - not broken yet

[Whiteout]

Good link. Thanks. My intent, though, is not to create a harder hash (which the link refutes well), but to provide a "safety net" in the case that one is broken. This of course depends on the assumption that there *are* fundamentally different hashes. Basically I agree with ericpi's response to the linked post.

Re:I disagree with Schneier - not broken yet

[Anonymous Coward]

But please, somebody explain to me how we're vulnerable. You can take my message and - if you try very very hard - you can create a garbage message that you could claim I signed. And that's all.

In that context, I think what the fissure in SHA-1 means is that if I try very very hard, I can create a perfectly valid message (that happens to include some garbage padding) that I can claim that you signed. Taking a broader view however, it's the first credible demonstration that SHA-1 isn't as impervious as most of us thought it was. I now consider symmetric encryption algorithms that are based on the security of SHA-1 to have been broken.

Re:I'm all for encyrption

[jay-be-em]

Look, we all know that PHP is broken and a huge waste of time.

PGP on the other hand is a different matter.

Wrong

[Anonymous Coward]

You are NOT trying to ensure that there is only one item per pigeonhole, although this is a frequent side effect of having 2^wow pigeon holes. If there are more pigeonholes than atoms in the universe, then collisions will be rare.

But the real concern is not collisions, but predicting and/or causing collisions. If I told you a hash had several collisions, that information is useless for most crypto uses unless you can find them.

So the pigeonhole issue is only a concern for DBA's who might use a hash as a primary key. For crypto, the issue is different.

GnuPG has this already

[Gemini]

To forestall the obvious question about GnuPG compatibility, GnuPG has had SHA-256, SHA-384, and SHA-512 since version 1.2.2 (2003-05-01) so it will interoperate nicely with the new PGP.

Incidentally, despite what the article implies, PGP has actually had SHA-256 support for a while now. It's not exposed in the GUI, but if you use GnuPG to generate a SHA-256 message, PGP can handle it.

In terms of what the SHA-1 "break" means, it is certainly time to start migrating to something stronger, but it is not time to panic and start revoking keys. Think of this as the MD5 situation in the late 1990s: a flaw was found, people migrated away, and when the serious MD5 crack was found last year, most people had already stopped using it.

The sky isn't falling. It's just a wake up call to start moving to something better.

or another perspective...

[Anonymous Coward]

If SHA-1 was a 100km wall, then now it is only 49m tall. You're still not going to scale it.

The use of wall heights where one is much taller than a person and one is much smaller is very prejudicial.

Also, note that all this talk of "breaks' is only true if you are the sender of the original message. This is a subsceptibility to a birthday attack, not a recipients' break.

Clearing up some misconceptions

[cpeikert]

Some comments (that I have not seen emphasized much) about all this SHA-1 stuff:

• The fact that there is a 2^{69}-time attack (versus a 2^{80} naive attack) on SHA-1 may only be the tip of the iceberg. Once the methods of attack are published and studied widely, other more efficient attacks may be found (historically, this is more likely than not). Saying "we're still safe; the attack is too slow and doesn't find a second preimage" is very naive.
• Hash algorithms like SHA-1 are used for more than just digital signatures. They are often used to achieve certain strong properties (like chosen-ciphertext security) in some public-key encryption algorithms (like OAEP). So saying "this only affects signatures" is wrong -- we don't yet know what effect these attacks might have on the security of the many other cryptographic schemes and protocols that use hashing primitives.

moving to a stronger SHA Algorithm ;)

[irf]

FYI, alternate hashes which were in RFC2440, such as TIGER, and HAVAL are
no more, and the reason for their removal was done for the sake of "keeping things simple", while at the same time all sorts of bells and whistles have been added to the aforementioned RFC to make it's implementation harder for any newcomer.
TIGER was removed because PGP Inc, never implemented it in their products, while HAVAL was removed because none of the implementers who mattered had it, and it goes without saying that if PGP Inc, has not implemented an algo, be it hash, symmetric..., then it will be axed or never make it to the RFC.
The suite of hash, and symmetric algorithms in RFC2440 are deficient, they ought to be more diverse, so that if one is broken one may fall back on another which has yet to be broken. Sadly, that is not the case, i.e. there are problems with AES, and it is only a matter of time before... There is another symmetric encryption algo out there which is immune to this problem(it was one of the AES candidates), and it has yet to make it to the rfc, reason given, other than above, it's slow!(it's a hell of a lot faster than any of the pre AES algos)
The title of this article is misleading, in that it proclaims "moving to a stronger SHA Algorithm (SHA-256 and SHA-512)", while this hash algorithm is newcomers in the zoo, and it has yet to stand the test of time...
To conclude, I wouldn't worry about the above, however, I would very much worry about RFC2440, as regardless of the algo suite, it may be deemed broken in many ways.
HTH
Best Regards
IRFe scrutinized

Quantum processing

[DigiShaman]

Just wait till modern processors get the ability to process data using Quantum mechanics. Processors can already do FP, Vector...and maybe soon Quantum. At least, untill a full scale Quantum processor is fabricated.

What the "break" means...

[Anonymous Coward]

Seems to me that what this break means, regardless of the work needed to use the break is that SHA-1 has been proven to be less secure than predicted, and therefore it is not as well-understood as previously thought.

I'd rather have something that is theoretically sound and reasonably tested, than something that has been shown to be theoretically unsound.

Re:Not a solution, 'cause there's no problem (yet)

[olden]

PGP changing algorithm is pure PR, IMHO. SHA1 may be technically broken, but PGP/GPG digital signatures are not.

What this much-publicised break offers is a faster-than-brute-force way to create 2 messages whose hash is identical, but not to construct a message with a predetermined hash (which is what you'd need to do if you wanted to alter the content of an existing PGP-signed document).
The best such attack against SHA1 known to date, Kelsey & Schneier (Nov 2004, cf. http://eprint.iacr.org/2004/304), requires 2**106 operations; way beyond our reach today.

only if you already own the system

[Anonymous Coward]

if you can view the SHA-1 encoded passwords
then you already own the system, so there is no point

Uhmmm...

[T'hain Esh Kelch]

Someone please fill me in; What are the advances in breaking a security algorithm if you arent a bad guy trying to steal something?

Re:Uhmmm...

[mattpalmer1086]

The short answer is that if it breaks, it needed fixing anyway. The long answer is that we have no absolute proofs of security, except for impractical things like using one-time-pads.

It is only by resisting cryptanalysis for long periods of time that confidence is built. So given that we have imperfect knowledge, the question becomes: do you want the bad guys (who are looking) to find the vulnerabilities first, if they exist?

Which is why good guys attack security systems.

Re:Uhmmm...

[T'hain Esh Kelch]

Thx for informing me! But in my eyes its pretty pointless.. At some point your PlayStation XX has enough power to decrypt it in a few minutes, so why dont they just wait a few years, and then 'retire' the encryption?

Re:Uhmmm...

[mattpalmer1086]

This is exactly what does happen. But there are two reasons why a cryptographic entity may be considered broken.

One is the reason you give, that processing power makes brute force searching practical. For example, the most common encryption algorithm in use today is probably DES. It was designed in the 70s, and was explicitly recommended that it's useful shelf life was only for a couple of decades. They already knew back then that processing power would overtake it's usefulness. As time has gone on, numerous other encryption algorithms have risen, including the new standard AES to take it's place, and have been tested extensively, with sufficient time to have a good sense of whether there are any "obvious" flaws in it.

Which brings us to the second reason why a cryptographic product may cease to be useful - an attack on the fundamental way the algorithm works. For example, if you can find a way of pulling out statistical patterns and using that information in some way, you may be able to get around the already known amount of brute-force processing you would have to do, to considerably shorten the attack - which may suddenly make an attack feasible with *current* amounts of processing power. This is what is happening with SHA-1 right now - although the current attack is still not very feasible for most people, it has moved into the "possible" territory for large organisations. And the likelihood is that once one attack has been found, others will follow. So we're all going to migrate away from MD5 and SHA1 to something else. No need to panic just yet, but we need to pay attention when attacks are found that no-one knew about before.

Since we just don't know how "secure" any of our encryption algorithms really are - a new form of mathematical analysis could be found at any time - people keep attacking them, yes, hoping to find that no attack is possible, or of course hoping that they are the ones who find an attack - it can do the career no end of good. But we all benefit when this is done openly.

The longer a cryptographic entity resists attack by all these frighteningly intelligent people, the more secure we all feel. But a new attack is always just around the corner... :)

Updating GPG Keys

[FU_Fish]

Can someone please post how to update GPG key preferences to make SHA256 my preferred hasing algorithm? I know I've done it before, but I just can't figure out the preference string this time. Thank you.

Re:I'm all for encyrption

[ArbitraryConstant]

"Since then, the USA's encyrption policy has been undermined from so-called allies such as Canada and Mexico such that these technologies are in the public domain and commonly used in communicating things that threaten our national security."

The US's encryption policy has been undermined because it's stupid. Canada and Mexico are only two of the dozens of countries that agree with my assessment.

Even if the USA were the only source of strong crypto (Not the case. Rijndael aka AES comes from Belgium.) or every other country agreed with the American position (ha!), it only takes one leak for the bad guys to get the good cyphers.

One leak. When every computer has a binary implementation that can be reverse engineered. When open source software has the source code available for all to see. Even if nobody sold/distributed the good versions outside of the US, it would still be trivial to get a good version out.

Re:I'm all for encyrption

[Anonymous Coward]

Are you familiar with the Wassenaar agreement? If you aren't just blowing smoke, it would be nice to see a few links to back up what you are saying.

Re:I'm all for encyrption

[dajalas]

But the U.S. government wants to hinder adoption, not keep the bad guys from getting good cyphers.

It's still a brain dead policy, but their behavior makes more sense viewed in this light.

Re:This reminds me...of flamebait

[Audacious]

A lot of dumb people have worked for the DoD and NASA.

This is true.

That doesn't mean you know anything about mathematics or crypto.

This is not.

This article was about consequences of finding a weakness in SHA-1.

This is true.

You started spouting off about how "computing power" is what is needed to break crypto.

This is true.

You said something silly about all crypto being broken with more computing power

This is false. Or would you like to go buy, from a junk dealer, an old Apple ][+ and try to break SHA-1? Can't do it? Oh, but I thought you said more computing power isn't needed. Maybe I'm mistaken, but these people didn't use toliet paper to figure this stuff out. They tried various algorithms on their nice supercomputer. Which is where the PS3 came in. Only you really failed to think about it in that light.

Since you were interested enough to reply, I'll elaborate. I didn't in my previous post because I just wanted you modded down--you really were posting just plain wrong information and saying it confidently.

PLEASE! The pity ploy! Gack! I think I'm going to get sick.

First of all, increased computing power is a given.

Oh my god! You agreed with me! And after bashing me so terribly before about saying this same thing! Oh still my beating heart!

But SHA-1 was broken by finding a mathematical way to find colisions with many orders of magnitude less computing power (perhaps I should say "fewer" since computing power is discrete?).

Oh my god! You agree with me again! I can't believe it! They used a mathematical algorithm to do this! Oh! This is too funny!

Secondly, your remark about increased computing power breaking all crypto is absurd.

Now wait! First you agree with me then you disagree with yourself! Oh god! This is too funny! I'm sorry! I just can't go on with a conversation with someone who can't even get stay with one stance! Either you agree with me or you don't!

Tell you what! You go ahead and say whatever you want. Just, if everyone will mod this person into flamebait city I'd appreciate it. Cause I have a lot of better things to do with my time than to go through such obviously stupid reasoning.

Later Lord Gator!

Re:This reminds me...of flamebait

[Lord Ender]

Those are cute quips but you didn't back them up with anything. Your statement about me contridicting myself further shows you don't understand the subject matter. And it looks like I have to reiterate: growing computing power, in the form of playstations or whatever other crap you come up with, would never have had an effect on SHA-1 as it is used in public key crypto. So don't spread disinformation. And your call for me to be modded down is futile. This story is way off the front page. You are only talking to me now. Not that I would have cared. I've been at the karma cap since before the cap existed. I'm sorry I was so harsh on you, but you were just wrong.

Re:I'm all for encyrption

[agraupe]

Well, it does say something about the state of the world when someone *can* believe that that person was telling the truth... there are enough crazy Americans that something like this could actually happen.

Re:This reminds me...of flamebait

[Audacious]

Ok, I know I'm going to hate myself for even lending a modicum of credence to your message but since this message was a bit more subdued in tone as well as a bit more reasonable I felt I should answer.

Those are cute quips but you didn't back them up with anything.

Neither did you. All you did was to state your opinions (as I have) on this subject.

Your statement about me contridicting myself further shows you don't understand the subject matter.

First, this is a jibe or slur. Whichever way you wish to take it and shows that instead of being able to stick to the subject matter you must resort to junvenile behavior in order to attempt to degrade your opponent rather than just stick to the subject matter and present facts, figures, and links to back up your stance.

Note: When you knowingly first said I was right about computing power and then I was wrong about computing power you did a flip flop on your stance. This is also known as "talking out of both sides of your mouth", "being two faced", and so on. (And here I must pause. Because I already know that you will take the above as an insult - which it is not. It is simply a statement about a state of being. Children will take it as a personal insult and some adults will do so as well. But it is not. Which is why I have placed the colloquialisms in double quotes.)

Jumping from one side of an argument to the other and back again makes people think you do not know what you are talking about. Further, my stating your jumping back and forth has absolutely nothing to do with the subject matter and therefore your logic is terribly flawed. It is like saying I know nothing about Australia because radeon gas inflitrates a person's house.

If you really had any kind of point to make in this matter, then you should have just said so. Like: The reason I said you were right and then wrong was becasue of X. Instead, you have to resort to childish, immature jabs in an attempt to goad me. *YAWN* Boring.

And it looks like I have to reiterate: growing computing power, in the form of playstations or whatever other crap you come up with, would never have had an effect on SHA-1 as it is used in public key crypto.

So again we start with a put-down which just makes be go bleck. Why even bother trying to hold a conversation with someone who can't do anything but try to bully you into submission.

So don't spread disinformation.

So look who's talking? Turn the mirror around and ask if you are helping or hurting? Don't see any help here.

And your call for me to be modded down is futile.

More boorish statements. *YAWN* Listen, you asked that I be mod'ed down as a Troll so I requested you be mod'ed down as flamebait. My call is just as stupid as yours was.

This story is way off the front page.

So what? If you look back just a few short messages you'll see I was mod'ed Interesting. So someone must be reading.

You are only talking to me now. Not that I would have cared.

If you don't care then why bring it up in the first place? Because you really do care.

I've been at the karma cap since before the cap existed.

Ok - so what? On SlashDot, once you reach a certain point it is almost impossible to do back down unless: 1)You really try hard at it, or 2)One of the SlashDot people reset you back down. Otherwise, by the very nature of posting your karma increases. But that is another subject for another day.

I'm sorry I was so harsh on you, but you were just wrong.

That is your stance. But I beg to differ. I know I am not wrong and you can talk until you are blue in the face. It will make no difference. Perhaps you should re-read the original posting and take it as it was meant - an opinion/general statement and not cold hard facts.

Forwards:

I do not mind being wrong - when I am wrong. I

Re:This reminds me...of flamebait

[Lord Ender]

Opinions? Chaining together playstations... or any other form of parallel processing, is not going to break hashes like SHA-1. That's not an opinion. That's a fact. And that's the fact you had wrong. Also, you have an annoying habit of breaking apart thoughts in your replies so thoroughly that some of their meanings are lost. That is very annoying. But as for saying someone modded you as insightful--that is why I made my original response to your message. It "seemed" to make sense to at least one moderator. But it was wrong in fact, not in opinion. I did not want it to continue being modded up by moderators who don't understand the material because that lends credibility to an erroneous statement. The fact that my statement was later modded up and yours was modded down after my post was made is interesting. It is my opinion that this because my post was successful in drawing attention to the multiple factual errors in your post.

Re:This reminds me...of flamebait

[Audacious]

Chaining together playstations... or any other form of parallel processing, is not going to break hashes like SHA-1. That's not an opinion.

Ok, so the fact that they:

1. Used a super computer to test their algorithms on.
2. That because most super computers operate in parallel they were able to either break the problem up into multiple parts or were able to test against multiple situations at the same time.
3. The super computer they used is probably doing terraflops worth of computations on this problem whereas older computers can't even do a terraflop.
4. That, because of their tests they were able to circumvent the N! problem and came up with a solution which only entailed 269 steps on their super computer. (And we still do not know exactly how many substeps or iterations are required in their program to reach an unencrypted state. We only know it took them a certain number of steps in their program.)

So I don't get it. The article specifically stated that they were using a super computing facility to do their work. We also know that super computers now-a-days are not one CPU but are multiple CPUs (like the recently talked about supercomputers purchased from IBM, HP, and even Apple Computer) strung together. That these CPUs work in parallel. They have a special OS and compilers which can break apart a program into individual chunks which are then fed to the multiple CPUs at the same time.

So given all of the above facts (items #1-4). And knowing (using common sense) that the breaking of SHA-1 would have been impossible on old, slower systems. You are still going to insist on saying they didn't use a super computer to break SHA-1? And knowing that all of today's super computers are really a large set of cpus stacked one against the other and that they run in parallel to process the given equations - you are still going to say it makes no difference?

If so, then please illuminate me with just how they went about breaking SHA-1. And please! Do not insult me by saying they did it by hand. Anyone who has had anything to do with encryption knows that you could not do this by hand. So tell me - how did they break SHA-1? And you better not try to tell me they used a computer after ranting and raving about how a computer can't help you solve this problem.

As for your post being modded up - I have not seen that. However, as you stated in your last post - we are fairly far down the ladder now and not many people will see anything we post to each other. Still, I do have two mod'ed messages. Both originally were mod'ed up and both are still positively mod'd. If, when you post something high on the list, I were to yell for people to mod you down and stated that your message was erroneous. Do you not think that some people might, as a knee-jerk reaction, just mod you down without really thinking for themselves as well?