Sam Tuke samtuke@fsfe.org wrote:
Yes indeed. I just dug up some articles:
http://www.theregister.co.uk/2013/09/23/rsa_crypto_warning/ https://www.schneier.com/essay-446.html
Also: https://www.schneier.com/blog/archives/2013/09/the_nsa_is_brea.html#c1675929
The solutions are pretty easy though - stop using RSA (most FS products already did this some time ago afaics), and use longer key lengths with elliptic curve cryptography (sort of obvious in the first place, but developers need to take note).
I don't see a good reason to recommend against RSA for public key (asymmetric) cryptography given the alternatives. The recommendation from Schneier was to use symmetric where possible.
The RSA issue from 2006 was due to the default random number generator (Dual_EC_DRBG) in one of it's products (RSA refers to a company, it's product, and the algorithm). This is an issue, but one that can be rectified with configuration. I don't know of any evidence that shows the RSA algorithm is crippled, but if you do please do tell.
RSA was not used in free software due to patent issues. These are now resolved, and GnuPG now defaults to using RSA for signing and encryption.
DSA is the major alternative to RSA for signing in GnuPG, and ElGamal is a variant of it used for encryption. DSA is faster than RSA. I think, based on readings from various sources, it may have an advantage of a smaller key size for the same effective encryption, but I don't know, and it's hard to measure. (See http://www.keylength.com/ for comparisons of various algorithms from different sources.)
However, DSA has a big problem: it is highly reliant on a good PRNG (pseudo-random number generator). Unfortunately PRNGs are easier to subvert than the mathematics, and the subversion can easily go unnoticed. The case in point (though I think it is more likely to be accidental than actual subversion) is the Debian PRNG weakness that affected OpenSSL and OpenSSH (https://www.schneier.com/blog/archives/2008/05/random_number_b.html). It was apparently present for nearly two years. DSA is also standardised by NIST, which may have been influenced by the NSA (though RSA could also have been pressured by government agencies).
OpenPGP actually does use symmetric algorithms. It encrypts a message using symmetric algorithm with a key generated on the spot, and then uses the asymmetric encryption key to encrypt the symmetric key. To decrypt a message it uses the asymmetric decryption key of the recipient to decrypt the symmetric key, which is then used to decrypt the message (this is simplified somewhat). This reduces the amount of data encrypted with the asymmetric key, and therefore reduces the amount of data that can be used for cryptanalysis.
Similar happens with digital signatures: a one way hash (mathematic function, hard to reverse efficiently) of the message is made, and then it is this that is signed using the asymmetric signing key.
If public key algorithms are truly broken (e.g. a backdoor or a mathematical breakthrough), then this is all moot, but the reduction in the amount of data that asymmetric encryption algorithms are use on, and also data that is less likely to repeat due to the random looking output of the encryption and hash algorithms, makes any other cryptanalysis seem unfeasible, unless a truly large volume of messages are encrypted with the same key.
With TLS and other "immediate" protocols, those where the public key algorithm used to encrypt the symmetric session keys is performed between both sender and recipient at the time of the connection (with email you don't get to do this), known as key exchange, there is an alternative known as Diffie-Hellman key exchange. The basic form has some weaknesses where a man-in-the-middle could obtain the key exchanged at the start of a connection, but this is a relatively short period of time. An enhancement to this is Ephemeral Diffie-Hellman key exchange: this provides what is known as Perfect Forward Secrecy (PFS), which essentially means that the symmetric key used to encrypt a message cannot be recovered from previous messages where the same asymmetric key was used.
So, use symmetric algorithms as much as possible, but that means you still need to exchange the keys. Public key encryption is handy for the case where the sender and recipient meet infrequently, and its use in OpenPGP boils down to key exchange, so it's relatively more secure than directly encrypting or signing messages using asymmetric keys.
You might want to use larger asymmetric keys: 2048 bit RSA or DSA2 is considered a minimum now. You may want to use 3072 or 4096 bit keys to increase the security margin. Using larger keys with asymmetric algorithms offers lesser improvement in security (it could be logarithmic).
Avoid the elliptic curve algorithms for now: they're relatively new and the constants are suspect.
Use ephemeral key exchange where possible.
Change your asymmetric keys after some period of time. With OpenPGP you could keep a large primary key for, say, four years, but create smaller sub-keys that you change every year. This means that you would need to start you web of trust every four years, but arguably that is a good thing to do anyway.
Simon