Slashdot Mirror
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..."
'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.
My work here is dung.
Is there any hash function that actually is secure?
Of course the good ol' rot13 !
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.
He tried to kill me with a forklift!
Perfect security is not feasible. "Secure enough" changes over time.
From TFA, so others don't have to read it, GPG will stay with SHA 224, SHA 256, SHA 384 and SHA 512.
Rethinking email
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.
My work here is dung.
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.
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
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
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.
'...if only "Jumping to a Conclusion" was an event in the Olympics.'
I guess I'll just go back to good old MD5.
...I am moving "off of" this grammar-school newsletter piece.
This is news for nerds, not news for dropouts.
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.
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.
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?
Hash functions are not used in encryption and decryption. Their cryptographic use is in authentication, for example in key exchange protocols and cryptographic signatures.
Guess the Aussies overpaid, since their $560k "unbreakable" cryptosystem relies on SHA-1. Shock of shocks, I know...
Oh god, that woman is John Romero!
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.
http://lkml.org/lkml/2005/8/20/95
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.
Find free books.
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.
Live today, because you never know what tomorrow brings
Noob. Use your brain. What good will the three-booting do without the chicken bone?
Fuck systemd. Fuck Redhat. Fuck Soylent, too. Wait, scratch the last one.
SHA-1, and monkeys might fly out of my butt!
Give me Classic Slashdot or give me death!
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.
Some drink at the fountain of knowledge. Others just gargle.
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.
All ideas^H^H^H^H^Hprocesses in this post are Patent Pending. (as well as the process of patenting all postings)
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.)
// MD_Update(&m,buf,j);
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.
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.
my GF always says its a good idea to "double up" -- you can never be too sure.
Practice Safe Hex -- Wear a computer condom.
"i lost my dignity on a slippery wiener"
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.
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.
"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.
It's a small world and it smells funny; I'd buy another if it wasn't for the money; Take back what I paid (SoM)
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.
It's a small world and it smells funny; I'd buy another if it wasn't for the money; Take back what I paid (SoM)
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.
It's a small world and it smells funny; I'd buy another if it wasn't for the money; Take back what I paid (SoM)
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.
note: i'm known as plugwash most places but i screwd up registering that here somehow in the past and now can't register
Of course the good ol' rot13 !
<pedant>ROT13 isn't a hash function.</pedant>
Dewey, what part of this looks like authorities should be involved?
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?
"People who do stupid things with hazardous materials often die." -- Jim Davidson on alt.folklore.urban
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.
I hereby place the above post in the public domain.
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.
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
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.
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.
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.
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
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.
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
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.
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
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.
It's a small world and it smells funny; I'd buy another if it wasn't for the money; Take back what I paid (SoM)
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).
A slashdotter who didn't build his own computer is like a Jedi who didn't build his own lightsaber.
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.
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.
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
Good point.
404555974007725459910684486621289147856453481154 in hex is "You sank my Battleship?"
[GPG key in journal]
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
404555974007725459910684486621289147856453481154 in hex is "You sank my Battleship?"
[GPG key in journal]
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.
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....
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?
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.
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.