1 files changed, 131 insertions, 0 deletions
diff --git a/doc/rsa.md b/doc/rsa.md
new file mode 100644
index 0000000..b1f47c5
--- /dev/null
+++ b/doc/rsa.md
@@ -0,0 +1,131 @@
+# 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