22

I wanted to create a new PGP key using GPG Keychain Access on my Mac. One of the options was to choose keytype:

  1. RSA and RSA
  2. DSA and Elgamal
  3. RSA (Sign only)
  4. DSA (Sign only)

I found this Superuser question, but it may be outdated. RSA keys seem to be less secure since it's known that the NSA infiltrated RSA and made their key generation algorithm weaker. I don't know if this has a significant influence for a 4096 bit RSA key. If I choose DSA I see that I can only use 3072 bit keys. It seems that DSA/Elgamal is less common, but messages about this date back to 2009 so is that still relevant?

  • What should I use?
  • What does it matter?
  • A good implementer of PGP (like the GNU team) will update the default selection (often the first in a list) based on current research. So, the default will usually be about the same or better than other choices. – Ned64 Sep 11 '15 at 6:04
34

since it's known that the NSA infiltrated RSA and made their key generation algorithm weaker

If you know that, then you know wrong. You are confusing two things which have no relation whatsoever:

  • RSA, the asymmetric cryptographic algorithm.
  • Dual_EC_DRBG, a PRNG algorithm of poor quality and amenable to backdooring.

RSA can be used for asymmetric encryption and for digital signatures. A PRNG can do neither. A PRNG produces an endless stream of unpredictable bits; this is something that RSA does not do. The two things are really different.

Now what is the source of the confusion ? It is twofold:

  • An asymmetric cryptographic algorithm uses keys that must be randomly generated at some point; the key generation algorithm requires a stream of random bits to work over, normally supplied by a cryptographically strong PRNG (so potentially Dual_EC_DRBG, or just any other PRNG).
  • One software vendor who implemented Dual_EC_DRBG and supplied it to its customers was RSA Security. That company is called "RSA" because it was founded by Rivest, Shamir and Adleman, the three researchers that also invented the asymmetric algorithm RSA and named it that way for exactly the same reason. Basically, Rivest is called Rivest when he invents cryptographic algorithms, and he is still called Rivest when he founds companies. Anyway, they sold the company two decades ago.

The bottom-line is that RSA, the asymmetric algorithm, is in no way "backdoored". What can be backdoored is the PRNG used in a specific implementation of the key pair generation algorithm. But if you use Dual_EC_DRBG to generate an ElGamal key pair, then you are equally hosed. Therefore, existence of poor, weak PRNG is in no way a reason to prefer ElGamal over RSA.

(If we want to nitpick, it goes the other way round: the known backdoor in Dual_EC_DRBG is easier to leverage if Dual_EC_DRBG was used to produce an ElGamal key than a RSA key. But in all generality, if your key generation tool uses a deliberately weak PRNG, then you lose. Regardless of the type of key.)

What about key length ? By some freak chance, it so happens that RSA, DSA and ElGamal keys of similar size offer vaguely similar strength (this is pure luck since they rely on distinct kinds of mathematical objects). 1024-bit RSA/DSA/ElGamal keys currently evade our cryptanalytic abilities, but they seem to be within reach of Earth-based technology (if you spend a few hundred millions or billions of dollars in building a dedicated machine and don't mind if it takes 6 months to break a single key). 2048-bit RSA/DSA/ElGamal keys are waaaay beyond what can be done with foreseeable technology. Any key size beyond 2048 bits is the equivalent of buying a red sports car to woo girls.

For your specific case:

  • The "sign only" options will yield keys usable only for signatures, and not for, say, encrypted emails. If you want a key usage for encryption you will need to use one of the first two options.

  • In older times, RSA was patented (in the USA) so some implementations supported only DSA and ElGamal. Since the patent expired in 2000, any decent implementation of PGP can now handle it just fine.

  • DSA signatures are a tad shorter than RSA signatures; ElGamal-based key exchange will use a few more bytes than RSA-based key exchange. We are only talking about a few dozen bytes here; any optimization of that kind will be dwarfed by the loss incurred if you decide to use red oversized keys to assert your manhood.

  • And red sport cars are cool, right? If implementations allowed, I'd use 8096-bit RSA or even 16384 or maybe elliptic equivalent... Hell with that, I should invest in a nice shiny hardware random number generator, all the geek girls will be mine :) Do they (generators) come in carbon black?.. – Ivan Anishchuk Mar 28 '16 at 19:19
  • 3
    "beyond 2048 bits is the equivalent of buying a red sports car to woo girls." ...doesn't seem to be working. – Philihp Busby Oct 25 '16 at 21:18
  • 2
    @IvanAnishchuk Behold my mighty 5$ wrench to dwarf any encryption ;) – Tobias Kienzler Mar 16 '17 at 6:27
  • Thomas, is 2048 still enough, or should I consider getting that sports car which by now might be a classic? – Tobias Kienzler Mar 16 '17 at 6:28
  • 1
    @TobiasKienzler I think only rare hardware gadgets do not support 4096-bit RSA nowadays (I think one of the yubikeys) and computing/networking restrictions of the past hardly apply anymore (you won't notice those extra nanoseconds anyway). While there is no reason to think about 2048 as weak, a few extra bits of security without any significant downside is usually better, especially for long-term master keys. I personally don't see any reason not to use 4096-bit keys by default. – Ivan Anishchuk Mar 22 '17 at 15:20

protected by Community Sep 11 '15 at 10:18

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.