Asymmetric Encryption

RSA

RSA is both a signature and an asymmetric encryption scheme. It is important to know which algorithm and which version of it you are using (as not all of them are secure); they are mostly defined in PKCS#1 documents (v1.5, v2.0, v2.1, v2.2).

What RSA encryption algorithms are secure?

There are many encryption schemes that have been standardized, unfortunately not all of them are that great and the great ones are often not implemented by libraries.

  • The PKCS#1 v1.5 padding was discovered to be broken in 1998. You should avoid this algorithm at all cost unless you have very good reasons and have implemented strong mitigations. See our section Is RSA PKCS#1 v1.5 secure? for more information.
  • OAEP was introduced in PKCS#1 v2 and has an incorrect proof of security as well as issues close to PKCS#1 v1.5 but that are easier to mitigate. See our section Is RSA-OAEP secure? for more information.
  • OAEP+ corrects the proof of security of OAEP. Unfortunately did not get standardized.
  • OAEP++ is another attempt at correcting the proof of security of OAEP. Unfortunately did not get standardized.
  • RSA-KEM (from Shoup's work) is the simplest way to encrypt with RSA, it also benefits from a tight security proof. Unfortunately it is not always implemented by libraries.

Is RSA PKCS#1 v1.5 secure?

No. Bleichenbacher found an attack on PKCS#1 v1.5 in 1998 which allows to decrypt the content of any encrypted payload, as long as the server advertises (or leaks) the validity of a ciphertext's PKCS#1 v1.5 padding. In spite of this, most certificates on the internet (and thus most internet protocols) are stil using this old and broken primitive. This has led to difficult to implement workarounds and mitigations, that have consequently been found not to work over and over:

Is RSA-OAEP secure?

RSA OAEP standardized in PKCS#1 v2.x is deemed "good enough" if you do not have access to better standards like RSA-KEM. Nonetheless, implementations of OAEP must mitigate against Manger's attack meaning that they must check in constant time the full padding of the ciphertext, even if the first null byte is incorrect. For example an error returning too early could give indication on the value of the first padding byte.

What keysize should be used?

First, when we talk about keysize what we're talking about is the bit-size of the RSA public modulus.

As with every keysize concerns, www.keylength.com is often the answer (spoiler alert: 2048-bit).

In addition, the cryptography by the numbers page gives some idea of what academic attacks have been able to do (spoiler alert: a 768-bit modulus has been broken). Although academic estimates that state adversary should be able to break 1024-bit modulus.

Is it safe to use a non-standardized RSA algorithm?

Probably not, depending on how you use RSA there might exist more attacks. See Twenty Years of Attacks on the RSA Cryptosystem.

Are there any known issues with RSA Key generation?

RSA's key generation requires good randomness and good algorithms to generate prime numbers. Both these requirements have been butchered in the past:

To ensure that a key generation algorithm is safe, it needs to be audited.

Side Channel on RSA, a problem?

not really, unless your threat model involve attackers being able to physically observe or tamper with your device OR you are running adversarial code on the same computer. TKTK (fault attacks (rowhammer), timing attacks, etc.)

results matching ""

    No results matching ""