Is an >=2048bit key with Asymmetric encryption secure enough to negotiate a Symmetric encryption key?

Question

Let's say that a client app already knows the public key of the server to which it needs to communicate with and the client app needs to connect to the server using a normal non-secured internet connection then may I assume that currently (in the current state of cryptography) a 2048bit Asymmetric Public Key and Encryption will be secure enough to allow the client and server to negotiate a symmetric encryption key?

You may ask how the client will know what the public key of the server is. In this scenario the client is written specifically for the server and they will use their own communication protocol and data thus I would assume that the server's public key might be coded into the client or maybe accessible to the client app from where it runs. I do understand that that scenario leaves the security open to anyone that has access to the client app.

I am in no way informed about which of the currently used asymmetric encryption algorithms provides the best security balanced with computational cost. I know a bit about RSA. If you have any suggestions about which are preferred then that may help me in my research as well.

Thank you for your input.

Answer 1

First let's recall a few notions, to avoid confusion.

Asymmetric encryption keys have structure, which is needed to support the "asymmetric" thing. Invariably, the best method to break properly defined and implemented asymmetric encryption is to try to unravel that internal structure. In the case of RSA, the public key is the combination of a big integer (the modulus) and a (normally short) exponent, and the "internal structure" is the knowledge of the prime factors of the modulus.

Different asymmetric encryption algorithms will use distinct structural elements, and there is no strong reason why different key types would offer the same "strength" for a given length, especially since the "length" is not an absolute property. In the case of RSA, the length is the size of the modulus; a 2048-bit RSA key is a RSA key whose modulus lies between 2²⁰⁴⁷ and 2²⁰⁴⁸. The complete RSA key is of course larger, when encoded into bytes, since you have to put the public exponent somewhere too.

Generally speaking, the main asymmetric cryptographic algorithms that can be encountered in practice are:

• Algorithms based on integer factorization: the public key contains a big composite integer, and knowledge of the prime factors of that integer allows recovery of the private key. Main algorithm of that type is RSA; other (much less used) algorithms in that category include Rabin's encryption (and Rabin-Williams signatures) and Paillier's asymmetric encryption.

• Algorithms based on discrete logarithm: there is a publicly known prime modulus p, and some integer g modulo p; private key is some integer x, and the public key is g^x mod p. Most well-known algorithms of that category include Diffie-Hellman (key exchange), El Gamal (asymmetric encryption) and DSA (signatures).

• Algorithms based on elliptic curves: these are actually the same algorithms as the discrete logarithm ones, except that computations are done in an algebraic object known as an elliptic curve, instead of modulo a prime integer p. The maths are more complex, but elliptic curves appear to be much more resilient to discrete logarithm for a given size, thus allowing the use of shorter elements (which, in turn, implies better performance).

• Algorithms based on lattice reduction. This category is for NTRU. That algorithm has not yet gained significant acceptance (the patents do not help).

---

Factoring integers, breaking discrete logarithms... requires the use of some specialized algorithms that need both a lot of CPU and a lot of RAM. We usually like to "compare strengths" by trying to normalize attack costs against the cost of breaking a symmetric key by brute force. Symmetric keys are just bunches of bits; brute force is trying all possible combinations.

Of course, such a simple comparison does not, actually, work:

• Cost of trying out one symmetric key depends on the involved encryption algorithm. Not all of them imply the same per-key effort.
• Brute force of symmetric keys requires no RAM at all, and is amenable to parallelization. Algorithms for integer factorization, for instance, cannot be made fully parallel, and need an awful lot of RAM (especially the non-parallel parts).
• Asymmetric keys are usually long-lived, contrary to symmetric keys; e.g., in your case, you have one RSA key, and will generate many symmetric keys on the fly. Thus, the return on investment for a key-cracking machine is usually higher for asymmetric keys (breaking one asymmetric key tends to yield a lot more power).

Nevertheless, this has not stopped various bodies from estimating the strength of various asymmetric keys, e.g. saying that a RSA 2048-bit key has roughly the same strength as a 112-bit symmetric key. For some freak and poorly understood reason, it seems that discrete logarithm and integer factorization offer similar strengths for the same modulus size (strictly speaking, the discrete logarithm is slightly stronger, with the currently known algorithm).

See this site for extended information on these estimations.

Bottom-line: RSA-2048 will be fine. When your system is broken, it won't be through upfront breaking of your key; rather, it will be through compromise of the server where you store the private key, be it because of a mundane buffer overflow, a careless mislaying of a backup tape, or the action of a disgruntled employee with shifty morals.

Answer 2

According to PGP, the company, a 2,048 bit RSA key is equivalent to a 112 bit symmetric key. A 3,072 bit RSA key is equivalent to 128 bits. According to NIST, 2,048 bits should be "good enough" until about the year 2030. beyond that, an RSA key length of at least 3,072 bits is needed.

It seems to me that an attacker would go after your asymmetric key since that can be inferred to be constant through the protocol you describe. So, you'd want strength at least equivalent to the symmetric key you are exchanging. I wouldn't worry very much about the computational cost even if the client is running on a relatively low-powered mobile device because you will be encrypting perhaps 256 bits.

I agree with what CodesInChaos has to say about ECC, but I fret about the security of the algorithms given what the NSA has been up to. Personally I'd prefer to stick to something more clearly understood by more people. Perhaps that's just paranoia, and lack of understanding, on my part.

The information from PGP Corporation can be found on P. 27 of this document: http://csrc.nist.gov/groups/STM/cmvp/documents/140-1/140sp/140sp630.pdf The information from NIST can be found here: http://csrc.nist.gov/publications/nistpubs/800-57/sp800-57_part1_rev3_general.pdf on p. 64. The reference to year 2030 came from an earlier version of NIST SP 800-57 which can be found here: http://csrc.nist.gov/publications/nistpubs/800-57/sp800-57-Part1-revised2_Mar08-2007.pdf