diff options
Diffstat (limited to 'doc')
-rw-r--r-- | doc/bugs.md | 5 | ||||
-rw-r--r-- | doc/dh.md | 141 | ||||
-rw-r--r-- | doc/dsa.md | 192 | ||||
-rw-r--r-- | doc/ecdh.md | 58 | ||||
-rw-r--r-- | doc/index.md | 80 | ||||
-rw-r--r-- | doc/rsa.md | 131 |
6 files changed, 607 insertions, 0 deletions
diff --git a/doc/bugs.md b/doc/bugs.md new file mode 100644 index 0000000..1533e3b --- /dev/null +++ b/doc/bugs.md @@ -0,0 +1,5 @@ +# List of bugs in common algorithms +* [RSA](rsa.md) +* [DSA](dsa.md) +* [ECDH](ecdh.md) +* [Diffie-Hellman](dh.md) diff --git a/doc/dh.md b/doc/dh.md new file mode 100644 index 0000000..ca8c410 --- /dev/null +++ b/doc/dh.md @@ -0,0 +1,141 @@ +# Diffie-Hellman + +## Subgroup confinement attacks + +The papers by van Oorshot and Wiener [OW96] rsp. Lim and Lee [LL98] show that +Diffie-Hellman keys can be found much faster if the short exponents are used and +if the multiplicative group modulo p contains small subgroups. In particular an +attacker can try to send a public key that is an element of a small subgroup. If +the receiver does not check for such elements then may be possible to find the +private key modulo the order of the small subgroup. Several countermeasures +against such attacks have been proposed: For example IKE uses fields of order p +where p is a safe prime (i.e. $$q=(p-1)/2),$$ hence the only elements of small +order are 1 and p-1. + +[NIST SP 800-56A] rev. 2, Section 5.5.1.1 only requires that the size of the +subgroup generated by the generator g is big enough to prevent the baby-step +giant-step algorithm. I.e. for 80-bit security p must be at least 1024 bits long +and the prime q must be at least 160 bits long. A 2048 bit prime p and a 224 bit +prime q are sufficient for 112 bit security. To avoid subgroup confinment +attacks NIST requires that public keys are validated, i.e. by checking that a +public key y satisfies the conditions $$2 \leq y \leq p-2$$ and $$y^q \mod p = +1$$ (Section 5.6.2.3.1). Further, after generating the shared secret $$z = +y_a^{x_b} \mod p$$ each party should check that $$z \neq 1.$$ RFC 2785 contains +similar recommendations. The public key validation described by NIST requires +that the order q of the generator g is known to the verifier. Unfortunately, the +order q is missing in [PKCS #3]. [PKCS #3] describes the Diffie-Hellman +parameters only by the values p, g and optionally the key size in bits. + +The class DHParameterSpec that defines the Diffie-Hellman parameters in JCE +contains the same values as [PKCS #3]. In particular, it does not contain the +order of the subgroup q. Moreover, the SUN provider uses the minimal sizes +specified by NIST for q. Essentially the provider reuses the parameters for DSA. + +Therefore, there is no guarantee that an implementation of Diffie-Hellman is secure against +subgroup confinement attacks. Without a key validation it is insecure to use the key-pair +generation from [NIST SP 800-56A] Section 5.6.1.1 (The key-pair generation there only requires that +static and ephemeral private keys are randomly chosen in the range \\(1..q-1)\\). + +To avoid big disasters the tests below require that key sizes are not minimal. I.e., currently +the tests require at least 512 bit keys for 1024 bit fields. We use this lower limit because that +is what the SUN provider is currently doing. + +TODO(bleichen): Find a reference supporting or disproving that decision. + +## Weak parameters + +The DH parameters must be carefully chosen to avoid security issues. A panel at +Eurocrypt'92 discussed the possiblity of trapdoors in DL based primitives +[Eurocrypt92 panel]. A. Lenstra pointed out that the primes chould be chosen +such that the special number field sieve can be used to compute discrete +logarithms. Gordon has analyzed methods to generate and detect weak parameters +[G92]. Section 4 of Gordons paper describes a method that can detect some +special cases, but no general method was given. Recently Fried et al. showed +that 1024 bit discrete logarithms with the special number field sieve are +feasible [FGHT16]. Moreover some libraries use primes that are susceptible to +this attack [FGHT16]. + +TODO(bleichen): So far not test for weak DH parameters has been implemented. +Possibly we should at least implement a test that detects special cases, so +that weak primes (such as the one used in libtomcrypt) are detected. + +DH implementations are sometimes misconfigured. Adrian et al. [WeakDh] analyzed +various implementations and found for example the following problems in the +parameters: p is sometimes composite, p-1 contains no large prime factor, q is +used instead of the generator g. + +## References +[Eurocrypt92 panel]: "The Eurocrypt'92 Controversial Issue Trapdoor Primes and Moduli", +EUROCRYPT '92, LNCS 658, pp. 194-199. + +[G92]: D. M. Gordon. "Designing and detecting trapdoors for discrete log +cryptosystems." CRYPTO’92, pp. 66–75. + +\[FGHT16]: J. Fried, P. Gaudry, N. Heininger, E. Thome. "A kilobit hidden SNFS +discrete logarithm computation". http://eprint.iacr.org/2016/961.pdf + +[OW96]: P. C. van Oorschot, M. J. Wiener, "On Diffie-Hellman key agreement with short exponents", +Eurocrypt 96, pp 332–343. + +[LL98]: C.H. Lim and P.J. Lee, +"A key recovery attack on discrete log-based schemes using a prime order subgroup", +CRYPTO' 98, pp 249–263. + +[WeakDh]: D. Adrian, K. Bhargavan, Z. Durumeric, P. Gaudry, M. Green, +J. A. Halderman, N. Heninger, D. Springall, E. Thomé, Luke Valenta, +B. VanderSloot, E. Wustrow, S. Zanella-Béguelink, P. Zimmermann, +"Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice" +https://weakdh.org/imperfect-forward-secrecy-ccs15.pdf + +[NIST SP 800-56A], revision 2, May 2013 +http://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-56Ar2.pdf + +[PKCS #3]: "Diffie–Hellman Key Agreement", +http://uk.emc.com/emc-plus/rsa-labs/standards-initiatives/pkcs-3-diffie-hellman-key-agreement-standar.htm + +[RFC 2785]: R. Zuccherato, +"Methods for Avoiding 'Small-Subgroup' Attacks on the Diffie-Hellman Key Agreement Method for S/MIME", +March 2000 +https://www.ietf.org/rfc/rfc2785.txt + +<!-- +## Sources that might be used for additional tests: + +CVE-2015-3193: The Montgomery squaring implementation in crypto/bn/asm/x86_64-mont5.pl +in OpenSSL 1.0.2 before 1.0.2e on the x86_64 platform, as used by the BN_mod_exp function, +mishandles carry propagation +https://blog.fuzzing-project.org/31-Fuzzing-Math-miscalculations-in-OpenSSLs-BN_mod_exp-CVE-2015-3193.html + +CVE-2016-0739: libssh before 0.7.3 improperly truncates ephemeral secrets generated for the +(1) diffie-hellman-group1 and (2) diffie-hellman-group14 key exchange methods to 128 bits ... + +CVE-2015-1787 The ssl3_get_client_key_exchange function in s3_srvr.c in OpenSSL 1.0.2 before +1.0.2a, when client authentication and an ephemeral Diffie-Hellman ciphersuite are enabled, +allows remote attackers to cause a denial of service (daemon crash) via a ClientKeyExchange +message with a length of zero. + +CVE-2015-0205 The ssl3_get_cert_verify function in s3_srvr.c in OpenSSL 1.0.0 before 1.0.0p +and 1.0.1 before 1.0.1k accepts client authentication with a Diffie-Hellman (DH) certificate +without requiring a CertificateVerify message, which allows remote attackers to obtain access +without knowledge of a private key via crafted TLS Handshake Protocol traffic to a server that +recognizes a Certification Authority with DH support. + +CVE-2016-0701 The DH_check_pub_key function in crypto/dh/dh_check.c in OpenSSL 1.0.2 before +1.0.2f does not ensure that prime numbers are appropriate for Diffie-Hellman (DH) key exchange, +which makes it easier for remote attackers to discover a private DH exponent by making multiple +handshakes with a peer that chose an inappropriate number, as demonstrated by a number in an +X9.42 file. + +CVE-2006-1115 nCipher HSM before 2.22.6, when generating a Diffie-Hellman public/private key +pair without any specified DiscreteLogGroup parameters, chooses random parameters that could +allow an attacker to crack the private key in significantly less time than a brute force attack. + +CVE-2015-1716 Schannel in Microsoft Windows Server 2003 SP2, Windows Vista SP2, Windows Server +2008 SP2 and R2 SP1, Windows 7 SP1, Windows 8, Windows 8.1, Windows Server 2012 Gold and R2, and +Windows RT Gold and 8.1 does not properly restrict Diffie-Hellman Ephemeral (DHE) key lengths, +which makes it easier for remote attackers to defeat cryptographic protection mechanisms via +unspecified vectors, aka "Schannel Information Disclosure Vulnerability. + +CVE-2015-2419: Random generation of the prime p allows Pohlig-Hellman and probably other +stuff. +--> diff --git a/doc/dsa.md b/doc/dsa.md new file mode 100644 index 0000000..0c2f631 --- /dev/null +++ b/doc/dsa.md @@ -0,0 +1,192 @@ +# DSA + +[TOC] + +The digital signature algorithm (DSA) is one of three signature schemes +descripted in the digital signature standard [DSS]. + +## Key generation + +4.2 Selection of Parameter Sizes and Hash Functions for DSA +The DSS specifies the following choices for the pair (L,N), +where L is the size of p in bits and N is the size of q in bits: + +L | N +---:|----: +1024| 160 +2048| 224 +2048| 256 +3072| 256 + +The tests expect the following properties of the parameters used during +key generation: + +* If only the parameter L is specified by the caller then N should be one + of the options proposed in [DSS]. +* If no size is specified then L should be at least 2048. This is the minimal + key size recommended by NIST for the period up to the year 2030. + +## Signature generation + +The DSA signature algorithm requires that each signature is computed with a new +one-time secret k. This secret value should be close to uniformly distributed. +If that is not the case then DSA signatures can leak the private key that was +used to generate the signature. Two methods for generating the one-time secrets +are described in FIPS PUB 186-4, Section B.5.1 or B.5.2 [DSS]. There is also the +possibility that the use of mismatched implementations for key generation and +signature generation are leaking the private keys. + +## Signature verification + +A DSA signature is a DER encoded tuple of two integers (r,s). To verify a +signature the verifier first checks $$0 < r < q$$ and $$0 < s < q$$. The +verifier then computes: + +$$ +\begin{array}{l} +w=s^{-1} \bmod q\\ +u1 = w \cdot H(m) \bmod q\\ +u2 = w \cdot r \bmod q\\ +\end{array} +$$ + +and then verifies that \\(r = (g^{u1}y^{u2} \bmod p) \bmod q\\) + +## Incorrect computations and range checks. + +Some libraries return 0 as the modular inverse of 0 or q. +This can happen if the library computes the modular +inverse of s as \\(w=s^{q-2} \mod q\\) (gpg4browsers) of simply +if the implementations is buggy (pycrypto). if additionally to such +a bug the range of r,s is not or incorrectly tested then it might +be feasible to forge signatures with the values (r=1, s=0) or (r=1, s=q). +In particular, if a library can be forced to compute \\(s^{-1} \mod q = 0\\) +then the verification would compute \\( w = u1 = u2 = 0 \\) and hence +\\( (g^{u1}y^{u2} \mod p) \mod q = 1 .\\) + +## Timing attacks + +TBD + +# Some notable failures of crypto libraries. + +## JDK + +The jdk8 implementation of SHA1withDSA previously checked the key size as follows: + +```java +@Override + protected void checkKey(DSAParams params) + throws InvalidKeyException { + int valueL = params.getP().bitLength(); + if (valueL > 1024) { + throw new InvalidKeyException("Key is too long for this algorithm"); + } + } +``` + +This check was reasonable, it partially ensures conformance with the NIST +standard. In most cases would prevent the attack described above. + +However, Oracle released a patch that removed the length verification in DSA in +jdk9: http://hg.openjdk.java.net/jdk9/dev/jdk/rev/edd7a67585a5 +https://bugs.openjdk.java.net/browse/JDK-8039921 + +The new code is here: +http://hg.openjdk.java.net/jdk9/dev/jdk/file/edd7a67585a5/src/java.base/share/classes/sun/security/provider/DSA.java + +The change was further backported to jdk8: +http://hg.openjdk.java.net/jdk8u/jdk8u/jdk/rev/3212f1631643 + +Doing this was a serious mistake. It easily allowed incorrect implementations. +While generating 2048 bit DSA keys in jdk7 was not yet supported, doing so in +jdk8 is. To trigger this bug in jdk7 an application had to use a key generated +by a third party library (e.g. OpenSSL). Now, it is possible to trigger the bug +just using JCE. Moreover, the excessive use of default values in JCE makes it +easy to go wrong and rather difficult to spot the errors. + +The bug was for example triggered by the following code snippet: + +```java + KeyPairGenerator keygen = KeyPairGenerator.getInstance("DSA"); + Keygen.initialize(2048); + KeyPair keypair = keygen.genKeyPair(); + Signature s = Signature.getInstance("DSA"); + s.initSign(keypair.getPrivate()); +``` + +The first three lines generate a 2048 bit DSA key. 2048 bits is currently the +smallest key size recommended by NIST. + +```java + KeyPairGenerator keygen = KeyPairGenerator.getInstance("DSA"); + Keygen.initialize(2048); + KeyPair keypair = keygen.genKeyPair(); +``` + +The key size specifies the size of p but not the size of q. The NIST standard +allows either 224 or 256 bits for the size of q. The selection typically depends +on the library. The Sun provider uses 224. Other libraries e.g. OpenSSL +generates by default a 256 bit q for 2048 bit DSA keys. + +The next line contains a default in the initialization + +```java + Signature s = Signature.getInstance("DSA"); +``` +This line is equivalent to + +```java + Signature s = Signature.getInstance("SHA1withDSA"); +``` +Hence the code above uses SHA1 but with DSA parameters generated for SHA-224 +or SHA-256 hashes. Allowing this combination by itself is already a mistake, +but a flawed implementaion made the situation even worse. + +The implementation of SHA1withDSA assumeed that the parameter q is 160 bits +long and used this assumption to generate a random 160-bit k when generating a +signature instead of choosing it uniformly in the range (1,q-1). +Hence, k severely biased. Attacks against DSA with biased k are well known. +Howgrave-Graham and Smart analyzed such a situation [HS99]. Their results +show that about 4 signatrues leak enough information to determine +the private key in a few milliseconds. +Nguyen analyzed a similar flaw in GPG [N04]. +I.e., Section 3.2 of Nguyens paper describes essentially the same attack as +used here. More generally, attacks based on lattice reduction were developed +to break a variety of cryptosystems such as the knapsack cryptosystem [O90]. + +## Further notes + +The short algorithm name “DSA” is misleading, since it hides the fact that +`Signature.getInstance(“DSA”)` is equivalent to +`Signature.getInstance(“SHA1withDSA”)`. To reduce the chance of a +misunderstanding short algorithm names should be deprecated. In JCE the hash +algorithm is defined by the algorithm. I.e. depending on the hash algorithm to +use one would call one of: + +```java + Signature.getInstance(“SHA1withDSA”); + Signature.getInstance(“SHA224withDSA”); + Signature.getInstance(“SHA256withDSA”); +``` + +A possible way to push such a change are code analysis tools. "DSA" is in good +company with other algorithm names “RSA”, “AES”, “DES”, all of which default to +weak algorithms. + +## References + +[HS99]: N.A. Howgrave-Graham, N.P. Smart, + “Lattice Attacks on Digital Signature Schemes” + http://www.hpl.hp.com/techreports/1999/HPL-1999-90.pdf + +[N04]: Phong Nguyen, “Can we trust cryptographic software? Cryptographic flaws + in Gnu privacy guard 1.2.3”, Eurocrypt 2004, + https://www.iacr.org/archive/eurocrypt2004/30270550/ProcEC04.pdf + +[O90]: A. M. Odlyzko, "The rise and fall of knapsack cryptosystems", Cryptology + and Computational Number Theory, pp.75-88, 1990 + +[DSS]: FIPS PUB 186-4, "Digital Signature Standard (DSS)", National Institute + of Standards and Technology, July 2013 + http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf diff --git a/doc/ecdh.md b/doc/ecdh.md new file mode 100644 index 0000000..c86b140 --- /dev/null +++ b/doc/ecdh.md @@ -0,0 +1,58 @@ + +# ECDH + +[TOC] + +##ECDH description: +See https://en.wikipedia.org/wiki/Elliptic_curve_Diffie%E2%80%93Hellman + +##Bugs +Some libraries do not check if the elliptic curve points received from another +party are points on the curve. Encodings of public keys typically contain the +curve for the public key point. If such an encoding is used in the key exchange +then it is important to check that the public and secret key used to compute +the shared ECDH secret are using the same curve. +Some libraries fail to do this check. + +**Potential exploits:** +The damage done depends on the protocol that uses ECDH. E.g. if ECDH is used +with ephemeral keys then the damage is typically limited. If the EC keys are +static, i.e. used for multiple key exchanges then a failure to verify a public +point can disclose the private key used in the same protocol. +(To do: add papers describing the attack). + +##Libraries +**Sun JCE provider:** +ECDH does not check if the points are on the curve. +The implementer must do this. + +**Bouncycastle:** +The ECDH implementation does not check if the point is on the curve. +Furthermore, Bouncycastle does not even check if the public and private key are +on the same curve. It performs a point multiplication \\(x \cdot Y\\) over the +curve specified by the public key. + +**OpenSSL:** +Point verification is done in OpenSSL if the right functions are used. +Since OpenSSL is not well documented it is a bit tricky to find the right +functions. +(To do: maybe add an example). + +##Countermeasures +TODO: +* use point compression. Formats such as X509EncodedKeySpec +in Java include bits that indicate whether the point is compressed or not. +Hence an attacker can always choose to use uncompressed points as long as this +option is incorrectly implemented. +* check that public and private key use the same curve +* restrict the protocol to named curves +* reconstruct the public key explicitly using the parameters of the private + key. + +**Further recommendations:** +If possible I also check if the points are on the curve after point +multiplications on an elliptic curve in the hope to catch implementation +and hardware faults. + +## Some notable bugs: +* ECDHC in bouncy castle could be broken by modifying the order of the public key. diff --git a/doc/index.md b/doc/index.md new file mode 100644 index 0000000..9fe48b3 --- /dev/null +++ b/doc/index.md @@ -0,0 +1,80 @@ +# Project Wycheproof + +This page describes the goals and strategies of project Wycheproof. See +[README](../README.md) for an introduction to the project. + +## Defense in depth + +There are a number of tests where we check for expected behaviour +rather than exploitability. Examples: + +* default values: we expect that default values are reasonable and correspond + to recommendations by current standards. Concretely, in 2016 it is not OK + if an RSA key generation uses 1024 bits as default or digital signatures + use SHA-1 as default. +* timing attacks: any timing that relation between keys (or other sensitive) + data and the measured time fails the test. However tests are set up + such that too much noise during the test can prevent that a relation + is detected. +* wrong exceptions: The JCE interface often specifies the exceptions that + should be thrown when the input is invalid. We expect the specified + exceptions in the tests. +* leaking information through exceptions: While it is a good practice to not + return detailed logs to a sender, we consider text in exceptions as + information that a potential attacker can learn. For example padding + failures during decryption should not contain information about the + reason why a decryption failed. +* RSA PKCS #1 signatures: If a signature verification allows signatures + with lots of modifications, then RSA signatures can be forged for small + public exponents. Tests do not measure how many bytes can be modified. + Any accepted modification of the PKCS #1 padding fails the test. + +## Compatibility between providers + +One of the goals of Wycheproof is to test for compatibility issues. +Switching JCE providers should not introduce vulnerabilities simply because +the solution was developed by another provider. + +An example for this was the following observation: When using AES-GCM then +javax.crypto.CipherInputStream worked sort of with JCE and +org.bouncycastle.jcajce.io.CipherInputStream.java worked with BouncyCastle. +However, authentication was skipped in some cases when +javax.crypto.CipherInputStream was used with BouncyCastle. + +## Comparing cryptographic libraries is not a primary goal + +Because of the strategies mentioned above we expect that a comparison of +cryptographic libraries based on the bugs found would be biased: + +* Libraries used internally in Google get more attention. + Serious vulnerabilities in these libraries should be fixed at the time the + tests are added to Wycheproof. On the other hand it is also likely that + tests find a larger number of bugs in these libraries when old versions are + tested. +* Tests often check for expected behaviour and compatibility. + Expected behaviour is often defined by a prominent library. + Pointing out such problems can therefore penalize smaller third party + libraries. +* We are working toward covering as many potential vulnerabilities as possible + with test vectors, because this simplifies porting the tests to other + languages or interfaces. Thus a single test case can cover multiple + vulnerabilities. + +We are not trying to remove this bias when this interferes with more important +goals such as early reporting. +Hence we are reluctant to publish comparisons. + + +## Thoughts on the design of cryptographic libraries + +We should promote robust interfaces with the goal to simplify +the use of the library, code reviews of applications using the +library and testing the library. + +* When cryptographic primitives require randomness then the random + numbers should be chosen by the library. It shouldn't be possible + for a user to provide randomness. If the library itself chooses the + randomness then it is possible (at least to some degree) to check + that the random number generation is appropriate for the primitive. + If the user can provide the randomness then it is not possible to + catch this in our tests. 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 |