Slashdot Log In
Preparing To Migrate Off of SHA-1 In OpenPGP
Posted by
kdawson
on Fri May 08, 2009 10:14 AM
from the orderly-fashion dept.
from the orderly-fashion dept.
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..."
This discussion has been archived.
No new comments can be posted.
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
Full
Abbreviated
Hidden
Loading... please wait.
He's Got a Knife! (Score:5, Funny)
'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.
2^52 (Score:2)
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 perf
Re: (Score:3, Interesting)
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, stu
Re: (Score:3, Informative)
Avoid bignums whenever possible
(2^57)/(2^52) = 2^(57-52) = 2^5 = 32 times speedup
Powers of 2 sneak up on you! :)
Re: (Score:3, Informative)
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.
SHA2 Family still secure (Score:5, Informative)
Re: (Score:2, Interesting)
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
Aww man, I just upgraded to SHA-1 (Score:4, Funny)
I guess I'll just go back to good old MD5.
In a related news... (Score:2, Insightful)
...I am moving "off of" this grammar-school newsletter piece.
This is news for nerds, not news for dropouts.
Re:In a related news... (Score:4, Insightful)
...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?
Parent
Stupid question, but... multiple hashes? (Score:4, Interesting)
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: (Score:3, Informative)
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 [gmane.org]
Re:Stupid question, but... multiple hashes? (Score:5, Informative)
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.
Parent
Re:Stupid question, but... multiple hashes? (Score:4, Informative)
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.
Parent
Re:Stupid question, but... multiple hashes? (Score:5, Insightful)
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.
Parent
Re: (Score:2)
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
Well that's unfortunate (Score:5, Funny)
If so, someone please put this to good use! (Score:4, Insightful)
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: (Score:2)
better packaging for debian (Score:5, Insightful)
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 [lightandmatter.com] 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: (Score:2, Funny)
However, as this is Debian they are more likely to "disable" SHA-1 by making it emit the plaintext.
What about SSL certificates? (Score:5, Interesting)
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 [wikipedia.org].
Re: (Score:3, Informative)
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.
Can someone give me a quick rundown? (Score:4, Interesting)
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? (Score:5, Informative)
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
Parent
Re: (Score:3, Funny)
Is there any hash function that actually is secure?
Of course the good ol' rot13 !
Re: (Score:3, Funny)
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: (Score:2)
In theory, no (Score:4, Insightful)
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.
Parent
Re: (Score:2, Insightful)
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: (Score:2)
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: (Score:2, Insightful)
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
Re: (Score:3, Interesting)
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: (Score:2)
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: (Score:2)
A paradox in that an extremely valuable transaction may need less security than an almost worthless (to anyone else) file.
Re: (Score:2)
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: (Score:3, Insightful)
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 e
Re: (Score:2)
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:First MD5 and now this (Score:5, Insightful)
Parent
Re:First MD5 and now this (Score:5, Informative)
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
Parent
Re:First MD5 and now this (Score:5, Informative)
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.
Parent
Re: (Score:3, Informative)
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: (Score:2)
OTP and physical security are the only way to go.
Re: (Score:2)
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 (Score:4, Informative)
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.
Parent
Re:First MD5 and now this (Score:5, Informative)
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.
Parent
Re: (Score:2)
Re: (Score:2)
SHA-1, and monkeys might fly out of my butt!
Re:Reencrypting Stored Secrets? (Score:5, Informative)
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.
Parent
Re: (Score:2)