The jury is still out on whether quantum computers can be used against the Discrete Logarithm Problem. It’s believed that they can be, but to the best of my knowledge no–one has made a real–world demonstration.
However, in a demonstration of the perversity of the quantum world, quantum computers fare poorly against symmetric–key systems. We have to use a different algorithm, and while it’s still an enormous improvement over conventional computing, enormous in this case simply isn’t enormous enough. We can slash the effective keyspace by a ridiculous factor: we can turn a 256–bit key into a 128–bit key, a 128–bit key into a 64–bit key, and so on and so on.
So what's the upshot?
- The nsa is probably not that far ahead of us in cryptanalysis.
- They’re not able to brute–force modern ciphers.
- Everything has limits. Even math and quantum mechanics.
- Modern crypto is designed with those limits in mind.
… Please don’t fool yourself into thinking you have nothing to worry about. Keep in mind that so far I’ve talked only about cryptanalysis and brute force. There are plenty of ways to skin a cat, and there are plenty of ways to compromise a cryptosystem. All that I want to convey here is how phenomenally unlikely it is that anyone is using classical cryptanalysis or brute force on your traffic.
If, from this, you conclude that you’re safe… well, you’re almost definitely not. It doesn’t matter how smart you are: there’s someone out there who’s smarter. It doesn’t matter how careful you are; you’re human and you’ll slip sooner or later, and someone who’s prepared can take full advantage of that.
What happened to sha–1?
Short version? It fell down, went boom.
Longer version? Some very bright people at Shengdong University in China discovered an attack against it. The attack is not yet practical, except maybe for extraordinarily large and well–funded groups who don’t mind throwing huge truckloads of money away just to forge a single message.
However, it happens without fail that as soon as someone announces an academic break against an algorithm, someone in the crypto community will say “you’re scaremongering! Until I see a practical attack, I’m not going to change!” (See, e.g., the section on ckt builds.)
If you’re thinking this, I’d like to propose a thought experiment. It involves you watching me load a magazine of ammunition into a pistol. You watch me chamber a round, flip the safety off, and fire a shot through your favorite vase. I then put the gun to your head. Do you feel threatened? Why, or why not?
“Well, of course I do!” you might answer. “I don’t know if you’re going to pull the trigger. I don’t know if the gun is going to go off. I don’t know what you want. I don’t know why you’re randomly shooting my favorite ceramics. Yes, I feel threatened!”
The same argument applies here. We’ve seen, from Shengdong University and other researchers, ample evidence that the gun is loaded and can fire. It is a matter of time until someone comes along and decides to pull the trigger for–real. It is best if we all stop using sha–1 right now, before the Shengdong University attack has enough time to turn into something practical.
In 1997, Hans Dobbertin proved the popular hash algorithm md5 was flawed. People continued using it regardless, on the grounds that attacks against it weren’t “practical”. Today, we can create collisions in md5 in under one second… and we have tons of embedded systems in security–critical infrastructure, installed after 1997, which still use md5.
How does that make you feel about the people who say that no attack is meaningful until a practical attack is demonstrated?
Please stop using sha–1 right now.
What happened to dsa?
Depends. Which dsa do you mean?
First, the short answer: nothing, really. The longer answer is… well… longer.
dsa, like any other algorithm, is pretty much useless by itself. It’s always used as part of a larger system. Sometimes, the choices made by that larger system can compromise the security of an algorithm.
ietf rfc 4880 very slightly compromised the security of dsa signatures by not putting in a hash function firewall. A hash function firewall is a mechanism which prevents someone from being able to lie about what hash function they used to create the signature.
If there’s a single weak hash function anywhere in the system, an attacker could get a good signature from you, and then construct a new message which — when using the weak hash function — would hash out to the same value. They then present your good signature on a forged message, and lie about what algorithm you used to sign it with.
For that reason, some reputable people in the OpenPGP community are skeptical of the long–term viability of dsa signatures, given the recent attacks against sha–1.
However, I am generally of the opinion these concerns are overstated. If you’re electronically signing a thirty–year mortgage, then yes, I’d recommend not using dsa, but those sorts of instances are few and far between. Regular users can feel confident in the security of dsa.
Why don’t you like tiger192?
When people ask me why I hate tiger192, they’re usually referring to my emphatic recommendation that people not use it in OpenPGP. So let me say it very clearly here: just because I recommend people not use it in OpenPGP, it does not follow that I do not like tiger192.
I like tiger192. Ross Anderson is a very competent cryptographer and his hash algorithm is plenty worthy of study. It’s a shame that it hasn’t caught on more broadly.
However, “I like it!” is not sufficient reason to include an algorithm in an ietf standard. tiger192 is not part of the OpenPGP suite of algorithms, it has never been part of the OpenPGP suite of algorithms, its only normative reference comes from a brief mention in ietf rfc 3156.
There’s an old software engineering maxim: “nobody’s talented enough to put a bug in a line of code they don’t write.” We introduce bugs at the same time we introduce lines of code. When we reduce lines of code, we almost always reduce bugs.
If tiger192 brought some new capability to the table, something the other hash algorithms couldn’t provide, then I’d be one of the first people demanding its inclusion in the standard. It doesn’t, though.
tiger192’s base of users is extraordinarily small. I would estimate it at under half a percent. This half–percent of users makes signatures that 99.5% of OpenPGP users cannot verify. This is an interoperability nightmare.
So — my reasons for emphatically recommending against tiger192 are:
- It adds complexity to software
- Complexity is the enemy of security
- It harms interoperability
- It doesn't bring any new capabilities to OpenPGP
When people argue in favor of tiger192, they typically argue in its favor as:
- But I like it!
Great, I like it, too. But liking it just isn’t enough.
Why don’t you like Camellia?
I encourage people to not use Camellia, but that doesn’t mean I think it’s a bad algorithm. I only think it’s a poorly supported algorithm. Although Camellia is part of the OpenPGP standard, very few OpenPGP implementations include it. The overwhelming majority of them do not. Encrypting your data with algorithms your recipients can’t use strikes me as unwise.
If you have a real need for Camellia — if you’re working for an agency that requires Camellia as an encryption algorithm, for instance — then use Camellia with confidence.
What would you like to see added to OpenPGP?
whirlpool. Unlike tiger192, it brings new capabilities to the table.
Without exception, every hash in the OpenPGP suite right now is built around the Merkle–Damgård construction. Given how many algorithms in this family have been successfully attacked, it’s worth wondering whether there’s some deep, fundamental flaw in the basic ideas behind the Merkle–Damgård construction.
whirlpool is a 512–bit hash algorithm built around a Miyaguchi–Preneel construction. I think it would be a good idea for OpenPGP to end the Merkle–Damgård monoculture and get some variety in, just to offset the (small) risk of some catastrophic future attack against Merkle–Damgård.
What’s the best algorithm?
I hope by this time you’ve come to realize that cryptography is an intensely mathematical art and that it’s easy to get lost in a maze of twisty little theorems, all alike. If you think you’ve done well so far, be careful patting yourself on the back. Earlier on, when I said “[m]athematicians and cryptographers will wince at how much I’m glossing over, handwaving, or outright not talking about,” well — I meant it.
First, let’s start with the word “best.” Best by whose metric? Best against linear cryptanalysis, best against differential cryptanalysis, best against impossible–differential cryptanalysis? Best in terms of fewest clock cycles per encrypted block? Best in terms of lowest memory footprint, fastest s– and p–box setup and teardown? Best in terms of overdesign? Best in terms of mathematical elegance? Best in terms of…?
As you can tell, there are many, many things you could be referring to when you say “best.” Using words like “best” to describe cryptographic algorithms leads me to think you don’t know what you mean.
As such, this question really has no useful answer. You have not defined what it means to be “best,” or even how “bestness” should be quantified among the many competing criteria.
What size of key should I use?
The only real recommendation I have is to stick with the defaults. I don’t know your needs. People who are just trying to protect their email against random eyes have different needs from people who are guarding nuclear weapon launch codes.
My standard advice is “unless you know what you’re doing and why, stick with the defaults.” It is very likely that the people who wrote your crypto application already chose very sensible defaults.
That said, if you want to know particulars, here are my opinions with respect to OpenPGP keys:
Most people will be very well–served with 2048–bit keys. Either dsa2 or rsa will work just fine. There is no real reason to believe one algorithm is superior to the other.
Beware of falling prey to the kind of shortsighted thinking that says only key size matters. It is far better to use a reasonable keysize and keep your healthy skepticism than to become blinded by the hype of a 4096–bit key.
Is a 2048–bit key equal to a 128–bit key?
Depends on who’s providing the numbers. All of these “equivalency” charts you see on the internet are really speculation. Worse than that, they’re speculation tied to a particular point in time, anticipating only that era’s technology and mathematical developments. If you look at Ron Rivest’s original estimates about rsa key lengths from the 1970s, they seem hopelessly naïve. When you look at today’s estimates, please keep in mind that these, too, are just as hopelessly naïve… we just don’t yet know precisely how naïve.
That said: according to the latest nist report, a 1024–bit key is roughly equal to an 80–bit symmetric key; a 2048–bit key is roughly equal to a 112–bit symmetric key; a 3072–bit key is roughly equal to a 128–bit symmetric key; and a 4096–bit key is roughly equal to a 168–bit key.
But I use aes256! Don’t I need a 16384–bit key to protect it?
No.
Some people advocate that the symmetric and asymmetric components of a cryptosystem be balanced. This is balderdash. While it’s true that any attacker will go after the weaker of the two systems, it simply doesn’t follow that the two systems should be equal in strength. All that follows is you should make sure the weaker of your two systems is still stronger than you need.
Yes, it really is that simple.
What public–key algorithm should I use? In what length?
I recommend using your cryptosystem’s defaults for encryption algorithms and for key lengths. Unless you know what you’re doing and why, don’t mess with it.
What symmetric–key algorithm should I use? In what length?
I recommend using your cryptosystem’s defaults for encryption algorithms and for key lengths. Unless you know what you’re doing and why, don’t mess with it.
What software do you use?
I use Mac OS X, Windows XP, Windows Vista, FreeBSD and Ubuntu on a fairly regular basis. I use the same software on all of them. Thunderbird, Enigmail and GnuPG.
Why don’t you use GnuPG 2.x?
GnuPG 2.x is, if you ask me, badly misnamed. It adds a lot of capabilities, sure, but the capabilities it adds are ones that don’t matter to the majority of GnuPG users. Maybe “GnuPG 1.4 plus some other things you won’t use” — but not “GnuPG 2.x.”
GnuPG 2.x does not offer any new capabilities to OpenPGP users. The new features are all related to supporting another email encryption standard called s/mime.
Thunderbird has excellent s/mime support built in. Therefore, I don’t need any of GnuPG 2.x’s new features. Why should I switch?
There’s an old adage in software engineering: “nobody is talented enough to put a bug in a line of code they don’t write.” Or, put another way, every unnecessary line of code is a bug vector. If I don’t need GnuPG 2.x’s features, why should I open myself up to the bug vectors?
Why don’t you recommend ckt builds?
I strongly advise against Imad Faiad’s ckt builds for both legal and engineering reasons. From a legal standpoint, it’s a clear violation of copyright law to download a ckt build or to make one available for download. It’s a clear violation of the Network Associates, Inc., 6.5.8 license agreement to apply the ckt patches to 6.5.8 source you already possess. Given we live in a lawsuit–happy culture, I recommend people not download the ckt builds.
From a software engineering standpoint, several people of repute within the pgp community do not have much respect for the software engineering of the ckt builds. Nor do I, given that a couple of well–publicized showstopper bugs in nai’s 6.5.8 have not been fixed even as late as ckt–8. This causes me to harbor serious doubts about Imad’s commitment to secure software engineering practice.
I and others also have concerns about Imad’s knowledge of cryptography and cryptanalysis. As far back as 1996, the cryptanalytic community was strongly urging people to move away from md5. By 1999, nai recognized that md5 needed to be deprecated and supported only with legacy keys. This was also the attitude of the GnuPG crew for the entire duration of the GnuPG project’s existence. Imad was arguing as recently as 2002 that md5 was secure and that talk of its weakness was hype and fearmongering. When the Dobbertin attack and its consequences were explained to him, his response was to challenge with a “well, if you say it’s insecure, let’s see you break it!” Those responses were neither professional nor constructive.
The ckt builds have also not been peer reviewed to the extent of nai’s 6.5.8 or pgp Corporation’s 8.x or 9.x. Due to the legal problems associated with ckt, many cryppies and programmers — myself included, as well as the majority of cryppies I know — believe that studying the ckt codebase and/or publishing weaknesses would open the door to copyright infringement lawsuits of one form or another. It’s hard enough being a cryptographer nowadays without running afoul of the dmca; most professional cryptographers and cryptographic engineers don’t need the additional headache of downloading the ckt source in violation of copyright law.
Why shouldn’t I use idea?
As a matter of personal ethics, I refuse to support software patents. The idea algorithm is patented by Ascom–Tech A.G., and they have expressed their willingness to enforce it. Now, since I’ve paid for a licensed copy of pgp I have a license to use idea for any purpose I want… but still. There are better ciphers out there, ciphers unencumbered by patents. Let’s use them.
It’s been my good fortune to know some members of the various intelligence communities. Many people know so–called “spooks”. My uncle served in military intelligence; does that make him a spook?
I have other friends who served in counterintelligence. Are they spooks?