xref: /aosp_15_r20/external/wycheproof/doc/rsa.md (revision 3d322d526be0ef039eebde10aa6ae75db8cc3a3d)

# RSA

[TOC]

## RSA key generation

**Default size:** If a library supports a key default size for RSA keys then
this key size should be at least 2048 bits. This limit is based on the minimum
recommendation of [NIST SP 800-57] part1 revision 4, Table 2, page 53. NIST
recommends a minimal security strength of 112 bits for keys used until 2030. 112
bit security strength translates to a minimal key size of 2048 bits. Other
organizations recommend somewhat different sizes: [Enisa], Section 3.6 also
suggests that 2048-bit RSA keys provide a security strength of about 112 bits,
but recommends a security strength of 128 bits for near term systems, hence 3072
bit RSA keys. [ECRYPT II], Section 13.3 suggests at least 2432 bits for new
keys.

All the references above clearly state that keys smaller than 2048 bits should
only be used in legacy cases. Therefore, it seems wrong to use a default key
size smaller than 2048 bits. If a user really wants a small RSA key then such a
choice should be made by explicitly providing the desired key length during the
initalization of a key pair generator.

According to https://docs.oracle.com/javase/7/docs/api/javax/crypto/Cipher.html
every implementation of the Java platform is required to implement RSA with both
1024 and 2048 bit key sizes. Hence a 2048 bit default should not lead to
compatibility problems.

**Cryptographically strong random numbers:**
So far the tests check that java.util.Random is not used. This needs to be
extended.

**Other bugs:**
The public exponent e should be larger than 1 [CVE-1999-1444]

## RSA PKCS #1 v1.5 encryption

PKCS #1 v1.5 padding is susceptible to adaptive chosen ciphertext attacks and
hence should be avoided [B98]. The difficulty of exploiting protocols using
PKCS #1 v1.5 encryption often depends on the amount of information leaked after
decrypting corrupt ciphertexts. Implementations frequently leak information
about the decrypted plaintext in form of error messages. The content of the
error messages are extremely helpful to potential attackers. Bardou et al.
[BFKLSST12] analyze the difficult of attacks based on different types of
information leakage. Smart even describes an attack that only needs about 40
chosen ciphertexts [S10], though in this case the encryption did not use PKCS #1
padding.

**Bugs**

* Bouncycastle throws detailed exceptions:
  InvalidCipherTextException("unknown block type") or
  InvalidCipherTextException("block padding incorrect").

<!-- the SUN provider used to include that block type -->

**Tests** To test whether an implementation leaks more information than
necessary a test decrypts some random ciphertexts and catches the exceptions. If
the exceptions are distinguishable then the test assumes that unnecessary
information about the padding is leaked.

Due to the nature of unit tests not every attack can be detected this way. Some
attacks require a large number of ciphertexts to be detected if random
ciphertexts are used. For example Klima et al. [KPR03] describe an
implementation flaw that could not be detected with our test.

Timing leakages because of differences in parsing the padding can leak
information (e.g. CVE-2015-7827). Such differences are too small to be reliably
detectable in unit tests.

## RSA OAEP

Manger describes an chosen ciphertext attack against RSA in [M01]. There are
implementations that were susceptible to Mangers attack, e.g. [CVE-2012-5081].

## RSA PKCS1 signatures
**Potential problems:**

*   Some libraries parse PKCS#1 padding during signature verification
    incorrectly.
*   Some libraries determine the hash function from the signature (rather than
    encoding this in the key) Effect:
*   If the verification is buggy then an attacker might be able to generate
    signatures for keys with a small (i.e. e=3) public exponent.
*   If the hash algorithm is not determined by in an authentic manner then
    preimage attacks against weak hashes are possible, even if the hashes are
    not used by the signer.

**Countermeasures:** A good way to implement RSA signature verification is
described in the standard PKCS#1 v.2.2 Section 8.2.2. This standard proposes to
reconstruct the padding during verification and compare the padded hash to the
value $$s^e \bmod n$$ obtained from applying a public key exponentiation to the
signature s. Since this is a recurring bug it makes also a lot of sense to avoid
small public exponents and prefer for example e=65537 .

**List of broken implementations**
This is a large list.

## References

\[B98]: D. Bleichenbacher, "Chosen ciphertext attacks against protocols based on
the RSA encryption standard PKCS# 1" Crypto 98

\[M01]: J. Manger, "A chosen ciphertext attack on RSA optimal asymmetric
encryption padding (OAEP) as standardized in PKCS# 1 v2.0", Crypto 2001 This
paper shows that OAEP is susceptible to a chosen ciphertext attack if error
messages distinguish between different failure condidtions. [S10]: N. Smart,
"Errors matter: Breaking RSA-based PIN encryption with thirty ciphertext
validity queries" RSA conference, 2010 This paper shows that padding oracle
attacks can be successful with even a small number of queries.

\[KPR03]: V. Klima, O. Pokorny, and T. Rosa, "Attacking RSA-based Sessions in
SSL/TLS" https://eprint.iacr.org/2003/052/

\[BFKLSST12]: "Efficient padding oracle attacks on cryptographic hardware" R.
Bardou, R. Focardi, Y. Kawamoto, L. Simionato, G. Steel, J.K. Tsay, Crypto 2012

\[NIST SP 800-57]:
http://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-57pt1r4.pdf

\[Enisa]: "Algorithms, key size and parameters report – 2014"
https://www.enisa.europa.eu/publications/algorithms-key-size-and-parameters-report-2014

\[ECRYPT II]: Yearly Report on Algorithms and Keysizes (2011-2012),
http://www.ecrypt.eu.org/ecrypt2/documents/D.SPA.20.pdf

\[CVE-1999-1444]: Alibaba 2.0 generated RSA key pairs with an exponent 1

\[CVE-2012-5081]: Java JSSE provider leaked information through exceptions and
timing. Both the PKCS #1 padding and the OAEP padding were broken:
http://www-brs.ub.ruhr-uni-bochum.de/netahtml/HSS/Diss/MeyerChristopher/diss.pdf