1# RSA 2 3[TOC] 4 5## RSA key generation 6 7**Default size:** If a library supports a key default size for RSA keys then 8this key size should be at least 2048 bits. This limit is based on the minimum 9recommendation of [NIST SP 800-57] part1 revision 4, Table 2, page 53. NIST 10recommends a minimal security strength of 112 bits for keys used until 2030. 112 11bit security strength translates to a minimal key size of 2048 bits. Other 12organizations recommend somewhat different sizes: [Enisa], Section 3.6 also 13suggests that 2048-bit RSA keys provide a security strength of about 112 bits, 14but recommends a security strength of 128 bits for near term systems, hence 3072 15bit RSA keys. [ECRYPT II], Section 13.3 suggests at least 2432 bits for new 16keys. 17 18All the references above clearly state that keys smaller than 2048 bits should 19only be used in legacy cases. Therefore, it seems wrong to use a default key 20size smaller than 2048 bits. If a user really wants a small RSA key then such a 21choice should be made by explicitly providing the desired key length during the 22initalization of a key pair generator. 23 24According to https://docs.oracle.com/javase/7/docs/api/javax/crypto/Cipher.html 25every implementation of the Java platform is required to implement RSA with both 261024 and 2048 bit key sizes. Hence a 2048 bit default should not lead to 27compatibility problems. 28 29**Cryptographically strong random numbers:** 30So far the tests check that java.util.Random is not used. This needs to be 31extended. 32 33**Other bugs:** 34The public exponent e should be larger than 1 [CVE-1999-1444] 35 36## RSA PKCS #1 v1.5 encryption 37 38PKCS #1 v1.5 padding is susceptible to adaptive chosen ciphertext attacks and 39hence should be avoided [B98]. The difficulty of exploiting protocols using 40PKCS #1 v1.5 encryption often depends on the amount of information leaked after 41decrypting corrupt ciphertexts. Implementations frequently leak information 42about the decrypted plaintext in form of error messages. The content of the 43error messages are extremely helpful to potential attackers. Bardou et al. 44[BFKLSST12] analyze the difficult of attacks based on different types of 45information leakage. Smart even describes an attack that only needs about 40 46chosen ciphertexts [S10], though in this case the encryption did not use PKCS #1 47padding. 48 49**Bugs** 50 51* Bouncycastle throws detailed exceptions: 52 InvalidCipherTextException("unknown block type") or 53 InvalidCipherTextException("block padding incorrect"). 54 55<!-- the SUN provider used to include that block type --> 56 57**Tests** To test whether an implementation leaks more information than 58necessary a test decrypts some random ciphertexts and catches the exceptions. If 59the exceptions are distinguishable then the test assumes that unnecessary 60information about the padding is leaked. 61 62Due to the nature of unit tests not every attack can be detected this way. Some 63attacks require a large number of ciphertexts to be detected if random 64ciphertexts are used. For example Klima et al. [KPR03] describe an 65implementation flaw that could not be detected with our test. 66 67Timing leakages because of differences in parsing the padding can leak 68information (e.g. CVE-2015-7827). Such differences are too small to be reliably 69detectable in unit tests. 70 71## RSA OAEP 72 73Manger describes an chosen ciphertext attack against RSA in [M01]. There are 74implementations that were susceptible to Mangers attack, e.g. [CVE-2012-5081]. 75 76## RSA PKCS1 signatures 77**Potential problems:** 78 79* Some libraries parse PKCS#1 padding during signature verification 80 incorrectly. 81* Some libraries determine the hash function from the signature (rather than 82 encoding this in the key) Effect: 83* If the verification is buggy then an attacker might be able to generate 84 signatures for keys with a small (i.e. e=3) public exponent. 85* If the hash algorithm is not determined by in an authentic manner then 86 preimage attacks against weak hashes are possible, even if the hashes are 87 not used by the signer. 88 89**Countermeasures:** A good way to implement RSA signature verification is 90described in the standard PKCS#1 v.2.2 Section 8.2.2. This standard proposes to 91reconstruct the padding during verification and compare the padded hash to the 92value $$s^e \bmod n$$ obtained from applying a public key exponentiation to the 93signature s. Since this is a recurring bug it makes also a lot of sense to avoid 94small public exponents and prefer for example e=65537 . 95 96**List of broken implementations** 97This is a large list. 98 99## References 100 101\[B98]: D. Bleichenbacher, "Chosen ciphertext attacks against protocols based on 102the RSA encryption standard PKCS# 1" Crypto 98 103 104\[M01]: J. Manger, "A chosen ciphertext attack on RSA optimal asymmetric 105encryption padding (OAEP) as standardized in PKCS# 1 v2.0", Crypto 2001 This 106paper shows that OAEP is susceptible to a chosen ciphertext attack if error 107messages distinguish between different failure condidtions. [S10]: N. Smart, 108"Errors matter: Breaking RSA-based PIN encryption with thirty ciphertext 109validity queries" RSA conference, 2010 This paper shows that padding oracle 110attacks can be successful with even a small number of queries. 111 112\[KPR03]: V. Klima, O. Pokorny, and T. Rosa, "Attacking RSA-based Sessions in 113SSL/TLS" https://eprint.iacr.org/2003/052/ 114 115\[BFKLSST12]: "Efficient padding oracle attacks on cryptographic hardware" R. 116Bardou, R. Focardi, Y. Kawamoto, L. Simionato, G. Steel, J.K. Tsay, Crypto 2012 117 118\[NIST SP 800-57]: 119http://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-57pt1r4.pdf 120 121\[Enisa]: "Algorithms, key size and parameters report – 2014" 122https://www.enisa.europa.eu/publications/algorithms-key-size-and-parameters-report-2014 123 124\[ECRYPT II]: Yearly Report on Algorithms and Keysizes (2011-2012), 125http://www.ecrypt.eu.org/ecrypt2/documents/D.SPA.20.pdf 126 127\[CVE-1999-1444]: Alibaba 2.0 generated RSA key pairs with an exponent 1 128 129\[CVE-2012-5081]: Java JSSE provider leaked information through exceptions and 130timing. Both the PKCS #1 padding and the OAEP padding were broken: 131http://www-brs.ub.ruhr-uni-bochum.de/netahtml/HSS/Diss/MeyerChristopher/diss.pdf 132