diff options
Diffstat (limited to 'doc/dh.md')
| -rw-r--r-- | doc/dh.md | 141 |
1 files changed, 141 insertions, 0 deletions
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. +--> |