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