Public Key Sizes and Their Importance

June 14, 2020 | Posted in certificates,security

A public key’s size and its algorithm is usually the first thing we see when we look at the “Public Key Info” section of an x.509 certificate.

Can we evaluate security of a website or a digital signature based on its public key without any access to the private key?

Turns out that we can, at least, to a degree.

First, we need to understand that it’s the combination of the algorithm and the key size that defines the “strength” of the key. The most widely used public-key algorithm today is RSA. Elliptic Curve (EC) algorithms (that are truly superior to RSA) are quickly gaining ground and taking the second place.

As per NIST definition:

Cryptographic algorithms can provide different “strengths” of security, depending on the algorithm and the key size used (when keys are required by the algorithm). Security strength is a number associated with the amount of work (i.e., the number of operations) that is required to break a cryptographic algorithm or system.

The same document provides a handy summary of the strength of various popular algorithms/key sizes.

Roughly speaking, RSA-2048 (the de-facto today’s standard) is equal in strength to EC-255.

What about the relationship between the public key and its private key?

For both RSA and EC the size of the public key depends on the size of the private key. This dependency is less direct for EC and pretty much one-to-one for RSA, at least for TLS certificates.

This, of course, is only part of the story. For TLS, asymmetric cryptography is used only during the handshake phase of the TLS negotiation. As part of the handshake, the two parties agree on the symmetric key, which is actually much smaller than the asymmetric key. The algorithm and the size on the symmetric key depend on the supported cipher suites.

For example, a TLS_DHE_RSA_WITH_AES_256_GCM_SHA384 suite shows that the symmetric AES-256 key will be used for “bulk encryption”, that is, as the session key for encrypting the actual data.

More detailed explanation can be found here.

The public/private key strength is even more important for application-level protocols, like OAuth2/OpenID Connect. In this case, public-key cryptography is used for signing/verifying the signature of a JWT token (and, optionally, for its encryption).

JWT/OAuth2 uses a slightly different nomenclature for key sizes, specifically, the size is in bytes versus bits, e.g., RS256, which is the same with RSA-2048.

The key’s size/strength is also critical for any kind of data at rest encryption or in a situation when a digitally signed document can be stored for a prolonged period of time.

The size of a key is deemed sufficient only for some period of time until the hardware becomes more powerful to allow for cracking the crypto algorithm with brute force or other approaches. This is the reason why the key strength has been marching upwards for many years.

RSA-2048 is considered secure until 2030, but it could be just a guess, given advances in quantum computing.

Imagine a digitally signed PDF contract (e.g., a real estate deed) that has to be stored for potentially tens of years. Currently, Adobe digital ID utilizes RSA-2048, so what if this algorithm becomes vulnerable five years from now?

The same problem applies to encrypted backups, disk encryption, and database encryption. In general, these use cases require stronger keys than the ones used for inherently transient TLS sessions and OAuth2 tokens.