Preparing To Migrate Off of SHA-1 In OpenPGP

jamie found a note on debian-administration.org, the first in a promised series on migrating off of SHA-1 in OpenPGP. "Last week at eurocrypt, a small group of researchers announced a fairly serious attack against the SHA-1 digest algorithm, which is used in many cryptosystems, including OpenPGP. The general consensus is that we should be 'moving in an orderly fashion toward the theater exits,' deprecating SHA-1 where possible with an eye toward abandoning it soon (one point of reference: US govt. federal agencies have been directed to cease all reliance on SHA-1 by the end of 2010, and this directive was issued before the latest results). ... So what can you do to help facilitate the move away from SHA-1? I'll outline three steps that current gpg users can do today, and then I'll walk through how to do each one..."

Comments

He's Got a Knife!

[eldavojohn]

'moving in an orderly fashion toward the theater exits'

An elderly application was trampled to death today as everyone struggled to exit the Sha One theater after someone screamed that an unknown assailant had a knife. After the panic, there was no evidence of injuries from the alleged attack and police are still investigating the presence of an actual weapon.

First MD5 and now this

[Anonymous Coward]

Is there any hash function that actually is secure?

Re:First MD5 and now this

[piripiri]

Is there any hash function that actually is secure?

Of course the good ol' rot13 !

Re:First MD5 and now this

[Anonymous Coward]

Perfect security is not feasible. "Secure enough" changes over time.

Re:First MD5 and now this

[eldavojohn]

Is there any hash function that actually is secure?

Of course the good ol' rot13 !

Not secure enough, better apply it twice for double protection.

You can tell the men from the boys by how many times they do things. Like when I restart my computer, I do it three times to make sure it will work when the things start back up inside it.

Re:First MD5 and now this

[sadness203]

Pffff, doing it 2-3 times is for amateur.

I personally use a special rrot13. Or if you prefer, Reverse Rot13.

It's so advanced, they are still trying to break it at NSA.

Re:First MD5 and now this

[swillden]

Is there any hash function that actually is secure?

There are some for which no known attacks exist. SHA-256 and SHA-512, Whirlpool and Tiger are all pretty thoroughly-reviewed with no weaknesses uncovered. The NIST hash function competition is causing a great deal of new hash function research and we'll almost certainly get a bunch of great new hash functions out of it -- many of them not only secure, but significantly faster than SHA-1.

If you're thinking that "no known attacks" isn't good enough, keep in mind that's as good as it every gets in cryptography, with the sole exception of the One Time Pad

Re:First MD5 and now this

[Amouth]

by definishion a hash function can't be safe you are taking something that is of unknown size and giving a specific lenght result which will always be the same for a given input.

due to the limited length of the result using inputs larger than the result you can assure at some point there will be a collision (2 diffrent inputs with the same output)

MD5 failed after enough people looked at it and someone figured out how to salt it to get collisions quite quickly.

as proccessing power increases brute force is getting easier - but when you find a way of cutting down the brute force required.. that is when something can become very weak very quickly.

Re:First MD5 and now this

[Anonymous Coward]

That is not what secure means with regard to hash functions. Secure means that it is not feasible to construct a document which has the same hash value as a given document (pre-image attack) or to construct two documents which have the same hash value (collision attack). The complexity of these attacks is ideally such that simply enumerating documents is the fastest way (brute force). Reducing the number of documents which you have to try to find a match makes a successful attack more likely. The complexity which is deemed as breaking the hash function depends on the adversaries and time frames relevant to a particular application.

Re:First MD5 and now this

[Kjella]

If you're thinking that "no known attacks" isn't good enough, keep in mind that's as good as it every gets in cryptography

I think my math teacher would call that a "necessary but not sufficient" condition, I mean anything can be without known attacks by virtue of never having been reviewed. Minimums should include:

1. Published algorithm, no "secret sauce" security by obscurity
2. Solid peer reviews by other cryptographers, definately not just the vendor or their hirelings
3. Strong links to well-researched hard mathematical problems

Of course, nothing can guarantee that the NSA hasn't found some super-secret math thingie that'll cut through it like a knife through hot butter. But cryptography is also about eating your own dog food, if you don't use it for anything valuable who'd trust it? You can't really keep that a secret because you have to tell lots of people that this isn't really secure or they'd use it as if it were. And if you do use it for your valuables, would you really leave that kind of backdoor for someone else to find? Again it doesn't prove anything, but I think most modern crypto algorithms have no weaknesses known to anybody, and if one showed up it'd be just as big a OMG for those who made/approved it as everyone else.

Re:First MD5 and now this

[oldhack]

Noob. Use your brain. What good will the three-booting do without the chicken bone?

Re:First MD5 and now this

[Hatta]

SHA-1, and monkeys might fly out of my butt!

Re:First MD5 and now this

[Maximum Prophet]

More like no attacks are feasible. If you have an N-bit document, an N-bit quantum computer can attack it. Since the largest quantum computer know is like 3 bits, you should be safe for awhile.

OTP and physical security are the only way to go.

Re:First MD5 and now this

[kestasjk]

Hash functions have many uses, a hash function can be perfectly secure for one application but not for another. (In fact this is practically always the case for defects found in modern hash functions.)

Re:First MD5 and now this

[KingPin27]

my GF always says its a good idea to "double up" -- you can never be too sure.

Practice Safe Hex -- Wear a computer condom.

Re:First MD5 and now this

[cant_get_a_good_nick]

One Time Pad has no technical flaws, but still has to be used correctly. I remember hearing that 's how the US broke a rusian nuclear spy ring - the russians got lazy with the one time pad, and the US spies had enough info to see what was happening.

My basic point - if you fix the human side of all these encryption issues, you'll be plugging up a lot of holes. Don't expect a 'perfect security' you can set and forget.

Re:First MD5 and now this

[Ex-Linux-Fanboy]

SHA-256 and SHA-512, Whirlpool and Tiger are all pretty thoroughly-reviewed with no weaknesses uncovered

Tiger actually is vulnerable to a "pseudo-near-collision" ref. No, I have no idea what a "pseudo-near-collision" is, but Tiger's vulnerable to it.

My favorite hash is RadioGatun, but I also like Keccak. I would like Skein, except there is no published variant of it that uses 32-bit words (Whirlpool [1] and Tiger have the same problem).

[1] Yes, you could make a Whirlpool variant with a 128-bit or even 256-bit hash using AES as the compression function, but I prefer to stick to published crypto, since I don't know how to make a truncated differential.

Re:First MD5 and now this

[jd]

"Perfect security" varies according to what constitutes "perfect". For example, one-time pads can be considered perfect, if you can guarantee the security of the pads.

(One suggested method is to use a cosmological source of randomness and transmit encrypted the position of the radiosource. Since any time delay will result in not having the same pad as the people on either side, the pad is essentially guaranteed secure even if the encryption is broken, provided it cannot be decrypted through the attack faster than it can be decrypted normally.)

This is obviously feasible for, say, GCHQ communicating with the NSA, as they can easily set up small radio observatories at their respective bases. It is equally obviously not feasible for communicating to someone hiking over the Alps, as you can't really fit a decent-sized dish into a backpack.

For very large collaborative groups, it is feasible to use some form of Byzantine key splitting to ensure the key is safe and to do some encryption/decryption in parallel. This is a very different scenario from one person talking to another directly, where both must have the full key and the algorithm complexity is limited by the fact that single computers aren't very good at parallelizing tasks yet.

Re:First MD5 and now this

[jd]

The crypto lounge and hash lounge have a list of known flaws/attacks/documented partial attacks in algorithms. It's a good place to start... ...well, to start being paranoid, anyway, as more than a few of the algorithms listed have this nice skull-and-crossbones by them.

Re:First MD5 and now this

[jd]

Enigma was an approximation to a one-time pad (mostly because you could reconnect the plug boards as you liked and re-order the wheels as you liked), but was likewise cracked because of carelessness of use.

Re:First MD5 and now this

[petermgreen]

Another big issue with a lot of current hash functions (at least MD5 and I think SHA1 too) is that thier block based nature means that if you can reasonablly generate two collisions of "random garbage" you can reasonablly generate two files with a prefix you choose before generating the collisions, followed by the two sets of "random garbage" followed by a suffix you choose AFTER generating the collisions.

Combine that with a carefully selected file format (IIRC it can be done with pdf) and you can make two files that have the same hash with different meaningfull content visible and no visible random garbage.

This makes "random garbage collision" attacks much worse than they would appear at first sight.

Re:First MD5 and now this

[Just Some Guy]

Of course the good ol' rot13 !

<pedant>ROT13 isn't a hash function.</pedant>

Re:First MD5 and now this

[wirelessbuzzers]

Strong links to well-researched hard mathematical problems.

This is usually only true for asymmetric (public-key) crypto. There are hash functions which are provably secure if some math problem is hard... pretty good math problems too (discrete log, not something "easier" like DDH).

But they're fabulously slow, not to mention they operate over prime-order fields instead of on bytes (this is a bigger problem for block ciphers than for hashes). We accept this slowness for public-key crypto because it seems to be required, and because only the header has to go through the public-key part. But every byte has to pass through the symmetric part.

There is an argument to be made that collision-resistance isn't that important (compared to a keyed version) and cryptographers should be willing to pay more for it. In this case, we'd use SHA-1 or MD5 for signatures and some other thing for fancier cases that actually require collision resistance.

Re:First MD5 and now this

[swillden]

If you're thinking that "no known attacks" isn't good enough, keep in mind that's as good as it every gets in cryptography

I think my math teacher would call that a "necessary but not sufficient" condition, I mean anything can be without known attacks by virtue of never having been reviewed. Minimums should include:

1. Published algorithm, no "secret sauce" security by obscurity 2. Solid peer reviews by other cryptographers, definitely not just the vendor or their hirelings 3. Strong links to well-researched hard mathematical problems

Absolutely correct, with the partial exception of #3. It would be nice, perhaps, if #3 applied, but most symmetric ciphers and secure hash algorithms rely on complexity rather than hard problems.

Re:First MD5 and now this

[owlstead]

as proccessing power increases brute force is getting easier - but when you find a way of cutting down the brute force required.. that is when something can become very weak very quickly.

Not really. As processing power increases the internal state and number of rounds can increase as well, together with the complexity of calculations. This might be a problem if you have tiny processors though (smart cards, some PDA's etc).

And you cannot cut down on brute force by doing something smart, because the definition of brute force is that you DON'T do anything smart (duh).

The problem with secure hash algorithms is more that it is impossible to prove that they are secure. You can try and use as many known tricks, try and avoid known obstacles and even prove that particular attacks don't work, but that's about it.

Re:First MD5 and now this

[swillden]

Enigma was an approximation to a one-time pad (mostly because you could reconnect the plug boards as you liked and re-order the wheels as you liked), but was likewise cracked because of carelessness of use.

Enigma was a stream cipher, not an approximation to a one-time pad. The configuration of plug boards, wheel order and initial wheel positions made up the key.

Re:First MD5 and now this

[swillden]

One Time Pad has no technical flaws, but still has to be used correctly. I remember hearing that 's how the US broke a rusian nuclear spy ring - the russians got lazy with the one time pad, and the US spies had enough info to see what was happening.

You're talking about the Venona project. A very impressive bit of cryptanalytic work.

Re:First MD5 and now this

[swillden]

More like no attacks are feasible. If you have an N-bit document, an N-bit quantum computer can attack it. Since the largest quantum computer know is like 3 bits, you should be safe for awhile.

There is no known quantum computer algorithm for attacking any of these hash functions. Shor's algorithm would allow a quantum computer to attack n-bit RSA with an n-bit quantum computer, but I've never heard of any counterpart for any of these hash algorithms, and it would be algorithm-specific.

Also, there may indeed be feasible attacks on the hash algorithms I mentioned. It's just no one knows of any, yet, and lots of very smart people have looked.

Re:First MD5 and now this

[jd]

Essentially, that's exactly what a stream cipher is. A OTP is just a random bit stream as long as the message which you XOR with the message. A stream cipher is a pseudo-random bit stream as long as the message which you XOR with the message.

Re:First MD5 and now this

[Lord Ender]

Over-generalization is generally a bad idea. MD5 and SHA-1 were flawed. That does not mean all cryptographic hashes are flawed. One could conceive of a cryptographic hash long enough that a computer as large as the universe would be required to successfully attack it within the lifetime of the Sun.

A related illustration is that OTP can provably provide perfect encryption (this is not the same as hashing, however).

Re:First MD5 and now this

[Anonymous Coward]

> ... that'll cut through it like a knife through hot butter.

I've found that once butter gets hot, it melts. Liquids tend to be very hard to cut with a knife.

Re:First MD5 and now this

[swillden]

But a stream cipher, being pseudo-random, is by definition not an OTP. The fact that the keystreams are generally used the same way does not make a non-OTP a kind of OTP.

Sorry if this seems like nitpicking, but it's not. From an information theoretic perspective, the difference between a strong PRNG and an OTP is enormous. In particular, it's large enough that the PRNG does not have an OTP's perfect security.

Re:First MD5 and now this

[Anonymous Coward]

Yes. Kinda like there is an impractical encryption algorithm with proven security, the one-time pad, there exists similarly unusable method for hashes as well.

Pick two 256-bit numbers at random, a and b. Init hash with a and then run the message through the following loop: hash = (hash+message[i])*b % largest_256_bit_prime;

As long as you keep a, b and the hashes secret, the attacker cannot generate collisions except by chance.

Re:First MD5 and now this

[fallstoofast]

This is just an idea, but wouldn't it be better for hash algorithms to be slower since it'd make it harder to brute force?

Re:First MD5 and now this

[swillden]

This is just an idea, but wouldn't it be better for hash algorithms to be slower since it'd make it harder to brute force?

You can always slow down a hash algorithm by iterating it, if you really want to. But there are lots of applications where they need to be fast and unless the algorithm is flawed, brute force is simply impractical no matter how fast the hash is.

Finding a collision by brute force for a specific input and an unflawed 256-bit hash algorithm will require, on average, hashing 2^255 trial inputs. That's an impossibly huge number.

Even if you just wanted to generate *any* collision, so you get a major helping hand from the Birthday Problem, you'd still have to try, on average 2^128 inputs. If you had a trillion computers, each able to do a trillion hashes per second, it would take, on average, ten million years. Oh, and you'd also need 2^136 bits of storage. The problem with that is that even if you could use only electron per bit to store your data, there aren't enough electrons in the universe!

These are some seriously big numbers. A couple of orders of magnitude of performance one way or the other isn't going to make any difference. Or rather, if it does, the hash is already too broken to be of any use and should be replaced.

In theory, no

[3.5 stripes]

In reality, given the time and effort, processing power, etc... yeah, there are some secure ones.

They're like locks, they make getting in hard enough that most people will look for an easier target.

Re:In theory, no

[rlseaman]

They're like locks, they make getting in hard enough that most people will look for an easier target.

And they're unlike locks, in that a fruitful attack can occur many years afterwards. A lock need only supply protection for a specific period of time - if no bad guys get in during that period, then the security can be regarded as perfect no matter how insipid in design. In cyber-security, even "near-perfect" is as imperfect as "completely lacking" - at least for high priority targets with legacy value.

Re:In theory, no

[3.5 stripes]

Well, we're then assuming that the encrypted file will remain where it is (and in its current form).. if the object behind the locked door was to remain there indefinitely, the same sort of disclaimers apply (the better technology gets, the easier it will be to open)..

Re:In theory, no

[AvitarX]

Considering the time for even a modestly skilled person to get into most locks is < 5 minutes (home locks anyway), I would say that it is not perfect.

High-security locks take longer, as does high-security encryption. We only need to use algorithms that have a MTBF of around 1000 years today, and baring quantum breakthroughs your pretty safe. I mean how long does even the most sensitive data need to remain protected? 30 years?

I guess if you are a high-profile politician/activist, or a murderer a little longer?

Re:In theory, no

[blueg3]

No, in proper cybersecurity, one should realize exactly that a particular protection mechanism is only likely to be secure for a limited period of time. There are even expected security times associated with different algorithms and key sizes.

This is why, for example, signing keys should only be valid for a limited period of time. It would be foolish to assume that it will remain secure forever, so it should be designed to become useless before it becomes insecure.

Re:In theory, no

[Dragonslicer]

They're like locks, they make getting in hard enough that most people will look for an easier target.

And just like locks, there isn't really a whole lot you can do to prevent brute force attacks.

Re:In theory, no

[AvitarX]

After thinking critically, I will amend my post.

You really need closer to 10,000 with todays tech, this allows it to take about 20 years before it is feasible to try and get it before the end of 30 years.

And by about 30 years it will be readily crackable.

Re:In theory, no

[Nitage]

SHA-1 is a cryptographic hashing algorithm, not and encryption algorithm.

Re:In theory, no

[Maximum Prophet]

Right, almost secure isn't good enough for privacy, where you don't want others to know the contents of a file even after you have passed away. "Mostly Secure", is good enough for multi-million dollar transactions that will be vapor soon after they are completed. As long as someone can't tamper with them during the transfer, it's ok.

A paradox in that an extremely valuable transaction may need less security than an almost worthless (to anyone else) file.

Re:In theory, no

[Zomalaja]

If you are Mr. Bad Guy and you MUST have the document that ensures you world domination, having it encrypted won't make you look for an easier target. A home burglar might, but he/she is just looking for something of value, not something so specific.
Good encryption makes the bad guy say "screw this" after his network of quad core boxes gets no results after 2 weeks/whatever time period of churning.

Re:In theory, no

[coolsnowmen]

I mean how long does even the most sensitive data need to remain protected? 30 years?

Whatever the copyright length is...so about forever.

Re:In theory, no

[OrangeTide]

Decrypting my credit card numbers from 10 years ago will do you no good. The security is as important or unimportant for physical security as it is for cyber security.

A filing cabinet with 50 year old government secrets might need to be as physically secure now as it was 50 years ago. Where as my expired and canceled credit card numbers, not so much.

Re:In theory, no

[rlseaman]

A filing cabinet with 50 year old government secrets might need to be as physically secure now as it was 50 years ago. Where as my expired and canceled credit card numbers, not so much.

Yes, but the value of physical security is cumulative. If you manage to protect government secrets for 50 years - even if this involves a $2 padlock and a footlocker - the security can be upgraded at any point to a higher level suitable for current threats. Cyber security on the other hand is only as good as its weakest expression over those 50 years. Expose a rot13 copy of a file even one time and it doesn't matter if you later re-encrypt the file using the NSA's latest and greatest algorithm.

Re:In theory, no

[iluvcapra]

I mean how long does even the most sensitive data need to remain protected? 30 years?

The exact method for constructing an atomic bomb is still secret, though most nuclear physicists could give you a good surmise... The exact method for constructing a Tellar-Ulam thermonuclear bomb is also still a secret that we wouldn't want to be generally available, and that's over 50 years old.

You do make a good point though, that "planned obsolescence" is a good feature to look for, particularly in a government encryption algorithm. The problem is that when attacks are found in these algorithms, they tend to reduce the amount of time required to crack the key by a factor of thousands, so suddenly your 30-year signature on the data is only good for a month, before some attacker can start passing off his messages as yours.

Re:In theory, no

[Joce640k]

Not true. DES has never been broken and there's no reason to believe it ever will be. All that's happened is that the key size is now too small so a brute force attack is feasible.

128-bit keys can't be brute-forced by any conceivable technology* so if AES holds up as well as DES (and there's every reason to think it will) then you can relax, nobody will ever read your message.

[*] There's not enough energy in the Sun to power such a search.

Re:In theory, no

[blueg3]

A lot more goes into a security system than a private-key cryptographic algorithm. (Not to mention the need to account for the potential development of new attacks against your private-key algorithm.)

For example, your algorithm needs a key. How is it generated? Where is it stored? How long can you reasonably expect that key not to be lost?

Re:In theory, no

[OrangeTide]

Oh, now I understand your point. I never considered that before.

What's this "Off of"

[Anonymous Coward]

"Off of"

Are we in grade school?

SHA2 Family still secure

[marcosdumay]

From TFA, so others don't have to read it, GPG will stay with SHA 224, SHA 256, SHA 384 and SHA 512.

Re:SHA2 Family still secure

[Anonymous Coward]

If I understand the attack correctly, I think most real-world SHA-1 usage should be secure for the time being. From the looks of it, the researchers were able to reduce the time necessary to find two inputs that hash to the same digest. This is very different from finding a second input that hashes to a known digest. If that were the case, common hash applications like storing the digest of passwords or a digital signatures would be vulnerable.

But until researchers can take a known digest value and find an alternate set of input data, most real-world applications should be okay. News like this should make people start to look at when they can conveniently migrate away from SHA-1, but it's not something that requires immediate attention.

Re:SHA2 Family still secure

[Anonymous Coward]

The attack which created a signed bogus SSL certificate was a collision attack, not a pre-image attack. The researchers managed to produce two signing requests, where one was for a legitimate certificate, which got signed, and the other was for a CA certificate, which would never have been signed. They could then transfer the signature to the CA certificate, because the MD5 hash values which were signed were the same for the two certificates. If a similar attack becomes feasible against SHA1 hashed certificates, that will definitely cause quite a stir.

Aww man, I just upgraded to SHA-1

[Anonymous Coward]

I guess I'll just go back to good old MD5.

Re:Aww man, I just upgraded to SHA-1

[DougWare]

I hope you were joking... MD5 isn't encryption, it's a hash. Encryption has to be reversible with a passphrase, hashes are not irreversible.

Re:Aww man, I just upgraded to SHA-1

[DougWare]

Sorry, I meant to say hashes are irreversible, or that that hashes are not reversible...I changed my train of thought in the middle of a sentence.

Re:Aww man, I just upgraded to SHA-1

[Anonymous Coward]

Uh, DougWare, what do you think SHA stands for? The hash is used as part of the digital

Re:Aww man, I just upgraded to SHA-1

[Amazing Quantum Man]

So is SHA-1.... Secure Hash Algorithm

And also, that whooshing sound you heard was the joke going over your head.

Re:Aww man, I just upgraded to SHA-1

[Anonymous Coward]

I hope you were joking... SHA1 isn't encryption either.

In a related news...

[Vexler]

...I am moving "off of" this grammar-school newsletter piece.

This is news for nerds, not news for dropouts.

Re:In a related news...

[Just Some Guy]

...I am moving "off of" this grammar-school newsletter piece.

See also: idioms. No one where I live, ditch digger or professional, would raise an eyebrow at that phrase. Might I suggest you find larger grammatical fish to fry, or perhaps resolve not to get worked up over regional slang?

Re:In a related news...

[Lord Ender]

What country do you live in? In the US, "off of" is a well-established phrase. A patient may move "off of" one drug to another, or an IT system may move "off of" a particular platform to a newer platform.

Re:Reencrypting Stored Secrets?

[John Goerzen]

SHA-1 doesn't encrypt things. It makes a hash of them, to verify they haven't been modified.

There are no secrets encrypted with SHA-1 because SHA-1 doesn't encrypt things.

Stupid question, but... multiple hashes?

[tlhIngan]

Really stupid question (not a cryptographer), but is there anything wrong with using multiple hash algorithms (hopefully none derived from one another)? Surely breaking two or more hashes simultaneously would be far harder?

E.g., MD5 is broken. But what if we use both MD5 and SHA-1?

Re:Stupid question, but... multiple hashes?

[russotto]

Really stupid question (not a cryptographer), but is there anything wrong with using multiple hash algorithms (hopefully none derived from one another)? Surely breaking two or more hashes simultaneously would be far harder?

E.g., MD5 is broken. But what if we use both MD5 and SHA-1?

Unfortunately not; once you've broken the strongest hash, the rest can be broken in polynomial time.

http://article.gmane.org/gmane.comp.encryption.general/5154

Re:Stupid question, but... multiple hashes?

[SparkleMotion88]

Surely breaking two or more hashes simultaneously would be far harder

You can't be "sure" about much in cryptography. If m is a message, and f and g are hash functions, you are assuming that you get more security from f(g(m)) than from f(m). You have to define what kind of security you are hoping for. With hash algorithms, you usually want: given m', it is difficult to find some m where h(m) = m'.

So to answer your question, using f(g(m)) would only be more secure than f(m) if f contains some vulnerability and no cryptanalytic vulnerability is introduced by combining f and g. If I don't have any information about either type of vulnerability, I would have no reason to assume that f(g(m)) is more secure than f(m). In this situation, I would stick with f(m) because it has been studied more and people have probably spent time trying to break it.

To put it another way, breaking f(g(m)) does not necessarily require breaking both f and g. The resulting algorithm that you get by composing f with g is still only one algorithm (just like SHA-1), and that is the only algorithm that needs to be broken.

Re:Stupid question, but... multiple hashes?

[YesIAmAScript]

I'm not so sure he's talking about applying one hash to the other's output, as much as performing both hashes on the same material and storing both results, also checking both results. Then you'd have to create a collision for both hashes in order to beat the system.

Re:Stupid question, but... multiple hashes?

[blueg3]

This has nothing to do with multiple hash algorithms. What you're referring to is that finding an n-way collision from a 2-way collision is polynomial time. That is, a 2-way collision is two documents with the same hash, and an n-way collision is n documents with the same hash.

Finding a pair of documents that have the same SHA1 hash doesn't help you find a pair of documents with the same MD5 hash. Indeed, none of the efficient-collision algorithms allow you to find collisions in both SHA1 and MD5 simultaneously. (Note that, as far as I know, there aren't even any efficient preimage attacks on MD5 or SHA1, only collision attacks.)

Using multiple hash algorithms is helpful, yes.

Re:Stupid question, but... multiple hashes?

[m50d]

Really stupid question (not a cryptographer), but is there anything wrong with using multiple hash algorithms (hopefully none derived from one another)?

Yes, there is a lot wrong with it. I would go into detail but you can find good explanations in any of the past, say, twenty stories posted here about hash algorithms.

Surely breaking two or more hashes simultaneously would be far harder?

No; not by enough to make it worthwhile, possibly not at all. E.g. if you're willing to use 256 bytes of hash, you're much better off using SHA-256 than two 128-byte hashes.

Re:Stupid question, but... multiple hashes?

[RiotingPacifist]

Such a long post for the content:

f(g(m)) may be stronger or weaker than g(m) or f(m) but i have no evidence either way, however g has been tested more than f.g

OR

I dunno, but SHA-1 has been tested more than MD5 on SHA-1

Re:Stupid question, but... multiple hashes?

[atfrase]

I'm not so sure he's talking about applying one hash to the other's output, as much as performing both hashes on the same material and storing both results, also checking both results. Then you'd have to create a collision for both hashes in order to beat the system.

IANAC(ryptogrpher), but..

it seems like the question yet remains whether deriving x (the password, source data, whatever) given both hashes f(x) and g(x) is easier or harder than having only one of the two (just like the question of whether f(g(x)) is harder than f(x)).

On the one hand, I can visualize that as having a smaller set of possible x that, when hashed, yield not only f(x) but also g(x). That reduction in the ratio of collision-hit-x's to all-possible-x's seems like it would at least make brute force harder.

On the other hand, I can also visualize that having g(x) in addition to f(x) is just more data to work with, which seems like it would make the problem easier; i.e. g(x) might not give many clues about x by itself, but combined with clues from a different algorithm f(x), maybe it'd be easier to find x?

Can any real cryptographers comment?

Re:Stupid question, but... multiple hashes?

[Anonymous Coward]

Sitting here I think it may even be worse than that.

Lets say I have hash1 and hash2 and do not know the message.

It gives me a nice intersection space to 'test' if I got the right message! As both hash's would have to work.

Re:Stupid question, but... multiple hashes?

[VeNoM0619]

No; not by enough to make it worthwhile, possibly not at all. E.g. if you're willing to use 256 bytes of hash, you're much better off using SHA-256 than two 128-byte hashes.

Makes some sense, but the difference is, they only have to break 1 algorithm. He is looking at it like "they broke SHA-1, big deal, break another well tested and secure hash algo". But I would say that the more different hashs you throw in, the better (but longer validation process, which some reason to defeat the purpose of a hash, since it's meant to be a short validation).

Re:Stupid question, but... multiple hashes?

[DangerousDana]

Here's an even more off-topic question, but, when brute-forcing an encrypted hunk of data, how does one know when the encryption has been successfully decrypted? Especially so for small data sets. Any hackers wanna weigh in here?

Re:Stupid question, but... multiple hashes?

[Anonymous Coward]

I used to use the rot13 algorithm. But for added security, I use it twice.

Yes, I know, trivial example, but it's still a valid point. Adding a second hash on top of a first may reduce the overall strength.

Re:Stupid question, but... multiple hashes?

[m50d]

He is looking at it like "they broke SHA-1, big deal, break another well tested and secure hash algo".

I know. It's still wrong.

Re:Stupid question, but... multiple hashes?

[blueg3]

For most systems, think about it in terms of the application developer. Say you encrypt a piece of e-mail with a password-based secret key. (Some function k(p) turns a password p into an n-bit key.) If you supply the wrong password, what should the system do? Usually you want the strength of the system to rest on the cryptography and not the inability to tell if a decryption was successful, so you simply include a marker to indicate if the decryption was successful. (There are standard padding and encoding schemes for this.)

Take an extreme mathematical case, though. Let's say I'm doing 128-bit AES, which operates on 16-byte blocks. Say I use no padding and have a 16-byte message. The decrypter will need to guess based on the properties of the mesage if the decryption worked. Even with only 16 bytes, if those bytes are English text, this is quite doable. If you've carefully chosen your messages so that all 16-byte messages are equally probable, then it's impossible, right? A test decryption e+k->p will produce a valid, reasonable plaintext, regardless of what the encrypted block e or key k are.

This is, incidentally, basically how TrueCrypt's deniable plausability works. The TrueCrypt headers are designed so that, in theory, every possible set of bytes is equally likely. The space the header would be stored in is filled with random data, which has the property that every possible set of bytes is equally likely. You then can't differentiate a block containing a header with one containing no header.

Re:Stupid question, but... multiple hashes?

[huwgently]

If by "multiple hashes" you mean a hash of a hash, then it's a bad idea. A hash function compresses the input data (lossily) to a (usually) smaller amount of data. As for computing both hashes and XOR'ing them together, it doesn't seem like too bad an idea, but it's beyond my ability to give a more definitive answer. It's entirely possible that the two hash algorithms effectively cancel out parts of each other, or at least make the job of cryptanalysis easier. That is, it could make the job of finding hash collisions (which is the usual measure of security for hashes, assuming that the hash is effectively one-way to begin with) potentially much easier. When in doubt, it's safer to use a single system.

Also, iirc MD5 and SHA-1 give different length hashes so some additional mungeing will be needed to come up with a uniform length hash.

Re:Stupid question, but... multiple hashes?

[Lord Ender]

An ideal cryptographic hash should require exponential (on the hash length) time to break. A "broken" hash, like MD5 or SHA-1, is one for which an algorithm exists which is capable of finding collisions in less than exponential time.

Combining hashes is the cryptographic equivalent of making a single, longer hash. If you combine broken hashes, you have a long broken hash, which would actually be far easier to break than an ideal cryptographic hash of the same length.

Re:Stupid question, but... multiple hashes?

[tlhIngan]

I'm not so sure he's talking about applying one hash to the other's output, as much as performing both hashes on the same material and storing both results, also checking both results. Then you'd have to create a collision for both hashes in order to beat the system.

Yes, sorry. I meant to say you have message M, and you hash M with multiple algorithms, a(M), b(M), ..., coming up with hashes A, B, ... Now you have message N, and a(M) == a(N). It shouldn't follow (always, that is) that b(M) == b(N), especially if a and b were two different algorithms.

Does using multiple algorithms in this way make it harder to find an N (N not equal to M naturally) that actually will collide all the algorithms chosen at once?

As for using SHA-256 - yes, you could, but what if you're on a system where you only have MD5 and SHA-1 (e.g., embedded systems)?

Re:Stupid question, but... multiple hashes?

[TheLink]

"if you're willing to use 256 bytes of hash, you're much better off using SHA-256 than two 128-byte hashes."

Proof or citation please?

That said SHA1 is 160 bit (not byte), and md5 is 128 bit. So let's just have a proof that SHA256 is harder to crack than SHA1 + MD5 (where the hashes are used independently on the same data - e.g. not something like hash=sha1(md5(data)), but rather hash= concat(sha1(data),md5(data)) ).

Re:Stupid question, but... multiple hashes?

[Cramer]

Broken is broken, sure. But finding two files that generate the same md5 and sha-1 hashes is a much harder nut to crack -- if even remotely possible. I'm not aware of any research into cross hash collisions. I suspect it would be a very remote possibility -- one would need very near complete "boomerang attack"s for both hashes to pull it off. (i.e. knowing what bits to change to keep the hash the same.)

Take for example checksums and crcs. Neither are used in crypto because they are trivial to break. With a checksum, whatever additions are added need to be subtracted elsewhere -- simple. With crc, if you flip one bit, it's easy to know which other bits to flip. CRC's are used in communication systems to detect random bit errors. IP uses simple checksums. Random bit errors can get past a crc or checksum alone, however, it's unlikely to get past both.

Re:Stupid question, but... multiple hashes?

[m50d]

Look it up - seriously, just look at any previous thread about hashes. (I used to have a particularly good post bookmarked, but I've lost it)

Re:Stupid question, but... multiple hashes?

[jonaskoelker]

This has nothing to do with multiple hash algorithms.

You should really read the rest of that post.

Finding a pair of documents that have the same SHA1 hash doesn't help you find a pair of documents with the same MD5 hash.

No, but if you can find one you can also find many, and in the many you can find an MD5 collision. From the link:

Joux then extended this argument to point out that attempts to increase the security of hash functions by concatenating the outputs of two independent functions don't actually increase their theoretical security. For example, defining H(x) = SHA1(x) || RIPEMD160(x) still gives you only about 160 bits of strength

"||" is concatenation. The theoretical argument, in brief: with the Merkle-Damgaard construction (used in MDx, SHAx, RIPEMDx), it takes a factor k to find 2^k collisions, over finding just a single one. By finding many collisions in one hash function, we have enough messages that they're likely to collide in the second as well.

But, he goes on to say

It was pointed out in the questions that another reason for concatenating hashes is not to try to increase the theoretical security, but for practical considerations in case one of them gets broken. This is probably why SSL, for example, used MD5 along with SHA1. That is still a valid reason.

It seems he agrees with you, regarding the general sentiment:

Using multiple hash algorithms is helpful, yes.

My take is that you get security that's at least as good as the best hash function. That is useful if you don't know which one's the best.

As a more practical matter, it eases deployment of new hashes if your software can already handle multiple hash functions; the step from one to two is often easily generalized.

Re:Stupid question, but... multiple hashes?

[TheLink]

But I have looked it up.

So far what I've seen can be summarized by: http://article.gmane.org/gmane.comp.encryption.general/5154

And that says:

"It was pointed out in the questions that another reason for concatenating
hashes is not to try to increase the theoretical security, but for
practical considerations in case one of them gets broken. This is
probably why SSL, for example, used MD5 along with SHA1. That is still
a valid reason."

Thus I'm still not sure that one would be better off using a single X bit hash, than two different smaller hashes of half the size.

So if you do have better info, it'll be good if you could share it.

Re:Stupid question, but... multiple hashes?

[m50d]

The reason it doesn't make sense to concatenate against the possibility of one or the other being broken is that breaking a hash is rarely an all-or-nothing thing - none of the recent published attacks have been "one can find a collision instantly", they're "one can find a collision in 2^96 attempts when it should take 2^128". Suppose you've gone for two 128-bit hashes, and your opponents are capable of 2^64 attempts. Now, you lose if attacks are found that reduce both your 128-bit hashes down to effectively 64-bits - unlikely, yes. But if you went for a single 256-bit hash, you don't lose until there's an attack which reduces it to an effective 64 bits - and if you look at the history of attacks on hash functions, you'll see that's actually much less likely than getting 64-bit attacks on two different hashes.

Re:Stupid question, but... multiple hashes?

[TheLink]

OK that's a better argument :).

Re:Reencrypting Stored Secrets?

[Anonymous Coward]

Hash functions are not used in encryption and decryption. Their cryptographic use is in authentication, for example in key exchange protocols and cryptographic signatures.

Well that's unfortunate

[Morphine007]

Guess the Aussies overpaid, since their $560k "unbreakable" cryptosystem relies on SHA-1. Shock of shocks, I know...

Re:Well that's unfortunate

[jd]

If they pay me another $560k, I'll upgrade them to SHA-2 or Midnight Blue. (Either that, or I'll figure out how to Seuss the names of hashes.)

Re:Well that's unfortunate

[owlstead]

Meh, only for key diversification and PIN hashing. Both are pretty safe. Of course, that won't matter to people that are not too deep into cryptography. Once they hear it is unsafe they will try and migrate away.

If so, someone please put this to good use!

[YesIAmAScript]

So many major systems are secured with PK systems that depend on SHA-1 hashes now. If this can be broken, someone please put this to good use by making a collision that makes it possible for people to write homebrew code for the PS3 or 360.

I keep hearing about all these hash collisions and how I should be scared, but I wish I could at least get the good with the bad.

Re:If so, someone please put this to good use!

[gmuslera]

Reading about collisions and gaming consoles risk to put the context far away from the crypto topic, specially if you think that PK and SHA-1 could be great as car model names.

Re:If so, someone please put this to good use!

[petermgreen]

Afaict collisions aren't much use for such things, unless you could make two apps one malicious one non-malicious that collided and somehow get the non-malicious one signed to high privilages. But if you are in a position to do that you can just get code with a hidden malicious feature signed.

Re:Reencrypting Stored Secrets?

[Anonymous Coward]

SHA-1 doesn't encrypt things. It makes a hash of them, to verify they haven't been modified.

True, though pedantically speaking there are well-documented means of turning any hash function into an encryption algorithm: in fact, I've used SHA myself to do that in software where we were allowed to use hash functions but not algorithms specifically designed for encryption.

better packaging for debian

[bcrowell]

So what can you do to help facilitate the move away from SHA-1?

One specific thing that would really help would be if debian would make it a priority to do a complete job of packaging the relevant hash functions, along with bindings for popular languages. For instance, I have an open-source perl app that uses digital watermarks. The user can choose between SHA1 and Whirlpool. However, I want to keep my app simple for users to install, and the perl binding for Whirlpool hasn't been packaged for debian yet, so I've made SHA1 the default. A debian user who wants to use Whirlpool with my app has to jump through hoops, e.g., installing the perl module via CPAN. That's actually a real pain for a debian or ubuntu user, because CPAN and apt don't play nicely; you can get in all kinds of screwed-up states if you try to install half your perl modules using apt and half using CPAN.

TFA is talking about gpg. Well, realistically, the choice of hash function is not the bottleneck in terms of security when it comes to sending encrypted or signed email. The bottleneck is mainly just that it's too hard to use (isn't built in to most GUI email clients), and in the case of encryption it also suffers from negative network effects -- there's no big benefit to me from using gpg encryption in my email unless the people I'm communicating also use the technology. The world's best crypto doesn't do you any good if you don't use it because it's too much of a pain. I think gpg is clearly a case where the perfect has been the enemy of the good. They've been so hung up on protecting the user against obscure vulnerabilities that they've ended up making the darn thing too hard for the vast majority of users. The docs, last time I checked, were basically written in Martian. I have a bachelor's degree in math, I program computers as a hobby, and I've read Schneier's Applied Cryptography. I'm not claiming that makes me a big expert on crypto, but it does put me out in front of the vast majority of the population. Well, I simply cannot figure out all the ins and outs of gpg. Okay, I could, but it would take more time than I'm willing to invest.

Re:better packaging for debian

[Anonymous Coward]

One specific thing that would really help would be if debian would make it a priority to do a complete job of packaging the relevant hash functions, along with bindings for popular languages.

However, as this is Debian they are more likely to "disable" SHA-1 by making it emit the plaintext.

Re:better packaging for debian

[stevied]

Ouch .. that was a bit below the belt ;-)

Re:better packaging for debian

[Eythian]

installing the perl module via CPAN. That's actually a real pain for a debian or ubuntu user, because CPAN and apt don't play nicely; you can get in all kinds of screwed-up states if you try to install half your perl modules using apt and half using CPAN.

IME, 'dh-make-perl' does a pretty good job of making .debs from CPAN packages.

Of course, this doesn't invalidate your actual point that the bindings should be in there in the first place.

Mod Parent Up

[Anonymous Coward]

And as the time it take to break encryption decrease, so do the time it takes to encrypt something.

Aren't we just throwing more and more bits to the seed?

2^52

[goombah99]

I could not really understand the paper in the answer. But it looked to me like they were talking about a reduction of the brute force time to solve the hash from 2^57 trials to 2^52.

2^52 is about 4x10^15. I don't know how many operations this takes to try, but 2^52 cycles of 1Ghz is 1.7 months of time.

So if it takes 10,000 1Ghz cycles to solve this then you need to accelerate this 10,000 times to get it to 1.7 months.

Brute force parallelism at that kind of scale is now very possible

As I said I did not perfectly understand what is meant by a collision 2^52 however so my consequent analysis may be wrong if it means something else.

Re:2^52

[hannson]

Lets see:

2^57 = 144.115.188.075.855.872

2^52 = 4.503.599.627.370.496

2^52 / 2^57 = 0,03125 = 3,125%

I didn't read TFA but if my math is correct this is a pretty serious attack. The seriousness didn't really show in the 52 vs 57 but wow, 96% is a lot.

Re:2^52

[cheftw]

but if my math is correct

Actually it's wildly wrong;

2^57 is way bigger than 144
2^52 is also much bigger than four 4

2^52 / 2^57 = 0,03125 = 3,125%
^none of those are equal

you must be REALLY stupid

Re:2^52

[iluvcapra]

Avoid bignums whenever possible

(2^57)/(2^52) = 2^(57-52) = 2^5 = 32 times speedup

Powers of 2 sneak up on you! :)

Re:2^52

[Anonymous Coward]

you must be REALLY stupid

typical ignorant american response.

europeans, particularly the french, tend to use the , for what we use the . for and vice-versa.

so in american, this:

2^57 = 144.115.188.075.855.872

2^52 = 4.503.599.627.370.496

2^52 / 2^57 = 0,03125 = 3,125%

becomes this:

2^57 = 144,115,188,075,855,872

2^52 = 4,503,599,627,370,496

2^52 / 2^57 = 0.03125 = 3.125%

which look like much more reasonable numbers.

Re:2^52

[goombah99]

but if my math is correct

Actually it's wildly wrong;

2^57 is way bigger than 144
2^52 is also much bigger than four 4

2^52 / 2^57 = 0,03125 = 3,125%
^none of those are equal

you must be REALLY stupid

I've read that there are places where the people there are so uneducated they often get their commas and periods mixed up. Probably some silly problem with typwriter keys or something I guess. Anyhow how could you expect those backward people who don't even know the right symbol for a decimal point to be able to do math.

Sheesh! good thing you pointed out that bad math to the poor slob. I bet he's feeling pretty stupid right now.

Re:2^52

[Joce640k]

It's a collision attack, that means you can make two files with the same SHA1 in 2^52 operations (via the birthday paradox).

In the best possible application of this attack you can make two files, one good, one incriminating and get somebody to sign the good one.

The two changeling files are generated via a randomizing process so generating meaningful text files really isn't possible, the files have to contain binary data with a 'random' appearance. Examples of this would be crypto keys, SSL certificates, stuff like that.

Anybody who makes his own files and signs them is immune to this attack. The SHA1 of your favorite Linux distro is as safe as ever.

So ... this attack isn't very useful in the real world but it does show that SHA1 is slowly being deconstructed, that relationships are being found between input bits and output bits.

Re:2^52

[hannson]

I bet he's feeling pretty stupid right now.

Actually I do feel kind of stupid for not clearing this up. Should have used a thin space as a thousand separator, it's less confusing to some.

Re:2^52

[Lord Ender]

Actually, the birthday attack IS useful in the real world. The birthday attack has been successfully used to dupe Verisign into issuing an SSL certificate to an address of the attacker's choosing! The attackers simply created two CSRs with the same MD5 hash--one for their website (which they had signed) and another for their victim's site.

Had they been blackhats instead of security researchers, they could have performed flawless MITM against SSL sites.

Re:2^52

[CarpetShark]

Nice optimisation, but this sort of stuff doesn't belong in most programs. Compiler/machine Optimisations should be in libraries where possible (ESPECIALLY in specialist, highly power-hungry areas like bignum libraries), or directly supported in the language/compiler itself. If you find some particular code to be an unacceptable bottleneck, or you're finished implementing the project and have fixed every bug and feel the universe isn't quite right without some new ones, then it's time to start making your code less readable with yak-shaving stuff like this.

Re:2^52

[Anonymous Coward]

Fuck yourself, eurotrash faggot piss-ant.

actually i'm an ameritrash piss-ant.

who happens to be aware of the fact that the world does not revolve around america.

and that there is more than one way of communicating.

Re:2^52

[Cramer]

I know this is hard to grasp, but MD5 is not SHA-1.

By definition, ALL hash functions have collisions; finding any random collision is quite easy (if time consuming.) Put simply, one cannot uniquely represent 4096 bit inputs with 160 bit outputs: 2^4096 is MUCH larger than 2^160. The trick is being able to generate a meaningful document with the same hash as an existing document; that's not at all easy. The only examples I've seen consist of either a single document specifically designed to be altered, or two random, meaningless documents with the same hash. SSL certs fall into the former as they naturally contain a large random section ("key") making them far simpler to tweak. (but that's not saying it can be done in a reasonable time frame with todays technology. however, that day is approaching.)

Re:2^52

[Lord Ender]

I know this is hard to grasp, but MD5 is not SHA-1.

Do you act like that in person, or just online? Either way, you're a real winner.

It doesn't look like you understand the implications of the birthday attack, but perhaps you can cover up that fact by acting like an arrogant jackass. Good luck!

Re:2^52

[goombah99]

it wasn't you I was poking fun at :-)

Re:2^52

[Cramer]

MD5 is not SHA-1. True or False? True. MD5 is a 128bit hash. SHA-1 is a 160bit hash. Without any analysis or tricks, MD5 is already much easier to brute force.

You are suggesting the birthday paradox means collisions can be found in 2^26 (2^(n/2)) trys now? That's not what they are saying. They have reduced the work needed to search for a collision ("brute force") from the previously best known 2^57 to 2^52. They have not effectively reduced the hash size to 2^52. Even though that's a marked improvement, it still puts the work beyond the reach of mere mortals.

(And btw, the "birthday attack" is not an "attack". It's just statistics showing the probabilites of collisions at random.)

Re:2^52

[Lord Ender]

You are suggesting the birthday paradox means collisions can be found in 2^26 (2^(n/2)) trys now?

Show me where I said that. Or are you trying to put words in my mouth to make yourself look less foolish?

PS: When talking about cryptography, it is, in fact, the "birthday attack," as it is used to attack cryptographic systems.

You are a pathetic douche bag. True or False? True.

Re:2^52

[hannson]

I know. I was also joking :-p

Re:2^52

[cheftw]

I hope it wasn't me. Maybe you guizes browsers aren't handling the sarcasm tag properly.

For the record though this sort of nonstandard business does hurt international cooperation in science and maths, even if it's only an annoyance.

Wenn ich Deutcher waere vielleicht wuerde es anders. ;)

Re:Reencrypting Stored Secrets?

[Anonymous Coward]

In the real world, hash algorithm are used in encryption, not as a cipher but for "key expansion."

Re:Reencrypting Stored Secrets?

[Anonymous Coward]

What the fuck are you talking about?

What about SSL certificates?

[200_success]

According to x509(1) and ca(1), OpenSSL supports md2, md5, sha1, and mdc2 as options for message digests for certificates. Since MD2 and MD5 are already broken, and SHA1 is now suspect, that leaves just the relatively obscure MDC-2.

Re:What about SSL certificates?

[Cruicky]

The OpenSSL package in Ubuntu supports SHA224, SHA256, SHA384, and SHA512, even though it's not actually shown in the help, with the command line options being -sha224, -sha256, -sha384 and -sha512.

I've been happily using SHA512 with a personal CA for the last year.

It's possible that other distributions have also compiled in support for these hash functions in their OpenSSL packages.

Re:What about SSL certificates?

[jd]

A good point, especially given that sites upgraded to SHA-1 from MD5 after the debacle over forged certificates. They're not going to want to upgrade again, especially to something obscure.

Re:What about SSL certificates?

[Anonymous Coward]

A good point; it seems common place for minimal computational power to come first, followed by robust hashing - or at least what is left - in second.

Respective life spans are not to be forgotten and thinking ahead can be a virtue.

Re:What about SSL certificates?

[drspliff]

And not blowfish, sha256, sha512?

Re:What about SSL certificates?

[Anonymous Coward]

The default for all platforms running OpenSSL 0.9.8 and later support md5, md4, md2, sha1, sha224, sha256, sha384, sha512, mdc, ripemd160.

Re:Reencrypting Stored Secrets?

[profplump]

I hate to break this to you, but any "well-documented means of turning any hash function into an encryption algorithm" *is* an algorithm specifically designed for encryption, so you're still breaking the rules.

Singularity?

[Sybert42]

Is this very useful for Singularity-related research? There's a generally open-atmosphere (with Opencog spun off from Novamente), and realization of the stakes involved.

Re:Reencrypting Stored Secrets?

[Anonymous Coward]

No....

Not a grammar faux paux

[Anonymous Coward]

"Off of" is actually the accepted common usage in the USA (for > 150 years), whereas British English leaves off the "of."

Can someone give me a quick rundown?

[swordgeek]

It's been a while since I had to deal with PGP keys and the like, and things have multiplied since then. Is there a simple explanation for the status/compatability/equivalency of...

pgp
openpgp
gpg
gnupg

And any others I'm missing?

Re:Can someone give me a quick rundown?

[molo]

Did no one really reply to this?

PGP is the original. Phil Zimmerman, export control, all the history.

OpenPGP is a specification for all input and output of a PGP system. RFC 4880. Diverges from PGP5.

GPG == GNUPG. A Free Software implementation of OpenPGP. Has now become the most commonly used OpenPGP implementation. Werner Koch is the project lead.

-molo

Re:Can someone give me a quick rundown?

[evilviper]

Is there a simple explanation for the status/compatability/equivalency

PGP 2.x primarily used IDEA, which is patented, so it's unsupported everywhere else.

Pretty much everything else (including later versions of PGP) interoperates just fine.

Re:Can someone give me a quick rundown?

[swordgeek]

Couple days later here, but thanks! It's just what I needed.

Re:Reencrypting Stored Secrets?

[Anonymous Coward]

I hate to break this to you, but any "well-documented means of turning any hash function into an encryption algorithm" *is* an algorithm specifically designed for encryption, so you're still breaking the rules.

Yeah, I know that, and you know that, but it made my boss happy.

VeriSign, is that you?

[Anonymous Coward]

I realize you're joking, but just yesterday I received an email VeriSign sent to all resellers that they're upgrading to an SHA-1 root certificate for all SSL certificates. Here's the main part of the message:

In our ongoing dedication to providing you and your customers with the optimum balance of strong security and functionality, VeriSign will be upgrading all GeoTrust and RapidSSL SSL products to a 1024-bit, SHA-1 root on May 28, 2009. The root we will chain all the GeoTrust and RapidSSL products to is the Equifax Secure Certificate Authority. thawte SSL certificates will be upgrading to a 1024-bit, SHA-1 root in the future. You will receive advanced notification before any changes are made.

effect on digital signature algorithms

[huwgently]

The NIST article mentions:

The attack primarily affects some digital signature applications, including timestamping and certificate signing operations, where one party prepares a message for the generation of a digital signature by a second party, and third parties then verify the signature.

There's an easy solution here as mentioned in Applied Cryptography (2nd edition). To paraphrase, when given a document to sign using a hash-based digital signature protocol, make sure to make some trivial edits to the document first. Otherwise, you run the risk that the person asking you to sign the document has already calculated a hash collision for that document, meaning that at a later date they can use your signature as "proof" that you signed some more nefarious document which has the same hash. Funnily enough, I think SHA-1 was mentioned somewhere in that same section...

Re:Reencrypting Stored Secrets?

[owlstead]

Yup, you can use it to create a stream cipher quite easily. There's very little reason to do this though, and stream ciphers have their share of problems (if only the complexity in comparison with CBC ciphers and the unavailability in crypto libraries). Using AES (or 3DES if AES is not available) in CBC mode is the normal way to do things.

Sign with multiple digests simultaneously

[OdinOdin_]

Surely one simple cure to this problem area is to employ last years (MD5), this years (SHA1) and next years (SHA2) digest recommendations all at the same time.

Ma and Pa implementations could select whichever one digest they thought was most secure for verification purposes (a performance verses risk balance). Military implementations would verify all three.

Now try to make a file that is valid now.

MOD PARENT INSIGHTFUL. Can't upgrade encryption.

[KWTm]

If you manage to protect government secrets for 50 years - even if this involves a $2 padlock and a footlocker - the security can be upgraded at any point to a higher level suitable for current threats. Cyber security on the other hand is only as good as its weakest expression over those 50 years. Expose a rot13 copy of a file even one time and it doesn't matter if you later re-encrypt the file using the NSA's latest and greatest algorithm.

Good point.

Damn, *I'M* a moderator!! Stupid. :P

[KWTm]

Okay, I feel really stupid now. After requesting that moderators mod up the GP post, I realize that I actually have mod points. Which I can use on any Slashdot article. Except this one, now. :P

Perfect security implies P != NP

[jonaskoelker]

Is there any hash function that actually is secure?

I think this would imply P != NP. While P != NP is a reasonable thing to believe, it hasn't been proven yet, so if a hash function was proven to be perfectly secure, we would likely have a proof that P != NP.

Well... not exactly; if hashes of a given hash function H have length O(1), then let n be smallest number larger than the length of the longest hash. Then there are at most 2^n - 1 different output values: 1 + ... + 2^(n-1) = 2^n - 1. Then, run through 2^n valid inputs and hash them; two will be equal.

[make some assumptions about polynomial running time of H, and that 2^n input strings can be found that are all of length polynomial in n; the latter follows from a common assumption: all strings are valid inputs]. So collisions can be found in time O(1) if hash sizes are O(1).

What we really want to talk about, in a theoretical sense, is a family of hash functions {H_n | n = 1, 2, ...} with outputs of size n. Any hash function with a fixed-length output will have a collision; similar to above, it's reasonable to assume they're of polynomial length. Then, a non-deterministic turing machine generates two strings which hash to the same value; by assumption of perfect security, no polynomial time turing machine can do this.

And being really pedantic, turing machines only solve decision problems; what you really want your turing machine to do is take two strings and and k, and tell you whether the two strings are prefixes of strings x and y both of length at most k, such that H(x) = H(y). Do binary search for a k that works (using the empty string as prefixes), then find the strings by expanding them bit by bit.

I'm not sure what I said is 100% formally correct, so consider this a near-complete proof sketch.

Actually, ROT13 is a hash function

[gnu-user]

It's a variation on an identity hash, where the hash space and the key space are the same size (one to one mapping).

It might not be a particularly useful hashing function....

Re:Actually, ROT13 is a hash function

[Just Some Guy]

By that definition, all crypto functions are hash functions. Hint: hashes are typically considered to be one-way and fixed length.

Re:Actually, ROT13 is a hash function

[gnu-user]

Hash functions are a general comp-sci idea, of which crypto hashes represent a very small subset of applications

There is no requirement that a general hash function is one way.

What about appending le file length to the hash ?

[Anonymous Coward]

seriously...