1# Diffie-Hellman 2 3## Subgroup confinement attacks 4 5The papers by van Oorshot and Wiener [OW96] rsp. Lim and Lee [LL98] show that 6Diffie-Hellman keys can be found much faster if the short exponents are used and 7if the multiplicative group modulo p contains small subgroups. In particular an 8attacker can try to send a public key that is an element of a small subgroup. If 9the receiver does not check for such elements then may be possible to find the 10private key modulo the order of the small subgroup. Several countermeasures 11against such attacks have been proposed: For example IKE uses fields of order p 12where p is a safe prime (i.e. $$q=(p-1)/2),$$ hence the only elements of small 13order are 1 and p-1. 14 15[NIST SP 800-56A] rev. 2, Section 5.5.1.1 only requires that the size of the 16subgroup generated by the generator g is big enough to prevent the baby-step 17giant-step algorithm. I.e. for 80-bit security p must be at least 1024 bits long 18and the prime q must be at least 160 bits long. A 2048 bit prime p and a 224 bit 19prime q are sufficient for 112 bit security. To avoid subgroup confinment 20attacks NIST requires that public keys are validated, i.e. by checking that a 21public key y satisfies the conditions $$2 \leq y \leq p-2$$ and $$y^q \mod p = 221$$ (Section 5.6.2.3.1). Further, after generating the shared secret $$z = 23y_a^{x_b} \mod p$$ each party should check that $$z \neq 1.$$ RFC 2785 contains 24similar recommendations. The public key validation described by NIST requires 25that the order q of the generator g is known to the verifier. Unfortunately, the 26order q is missing in [PKCS #3]. [PKCS #3] describes the Diffie-Hellman 27parameters only by the values p, g and optionally the key size in bits. 28 29The class DHParameterSpec that defines the Diffie-Hellman parameters in JCE 30contains the same values as [PKCS #3]. In particular, it does not contain the 31order of the subgroup q. Moreover, the SUN provider uses the minimal sizes 32specified by NIST for q. Essentially the provider reuses the parameters for DSA. 33 34Therefore, there is no guarantee that an implementation of Diffie-Hellman is secure against 35subgroup confinement attacks. Without a key validation it is insecure to use the key-pair 36generation from [NIST SP 800-56A] Section 5.6.1.1 (The key-pair generation there only requires that 37static and ephemeral private keys are randomly chosen in the range \\(1..q-1)\\). 38 39To avoid big disasters the tests below require that key sizes are not minimal. I.e., currently 40the tests require at least 512 bit keys for 1024 bit fields. We use this lower limit because that 41is what the SUN provider is currently doing. 42 43TODO(bleichen): Find a reference supporting or disproving that decision. 44 45## Weak parameters 46 47The DH parameters must be carefully chosen to avoid security issues. A panel at 48Eurocrypt'92 discussed the possiblity of trapdoors in DL based primitives 49[Eurocrypt92 panel]. A. Lenstra pointed out that the primes chould be chosen 50such that the special number field sieve can be used to compute discrete 51logarithms. Gordon has analyzed methods to generate and detect weak parameters 52[G92]. Section 4 of Gordons paper describes a method that can detect some 53special cases, but no general method was given. Recently Fried et al. showed 54that 1024 bit discrete logarithms with the special number field sieve are 55feasible [FGHT16]. Moreover some libraries use primes that are susceptible to 56this attack [FGHT16]. 57 58TODO(bleichen): So far not test for weak DH parameters has been implemented. 59Possibly we should at least implement a test that detects special cases, so 60that weak primes (such as the one used in libtomcrypt) are detected. 61 62DH implementations are sometimes misconfigured. Adrian et al. [WeakDh] analyzed 63various implementations and found for example the following problems in the 64parameters: p is sometimes composite, p-1 contains no large prime factor, q is 65used instead of the generator g. 66 67## References 68[Eurocrypt92 panel]: "The Eurocrypt'92 Controversial Issue Trapdoor Primes and Moduli", 69EUROCRYPT '92, LNCS 658, pp. 194-199. 70 71[G92]: D. M. Gordon. "Designing and detecting trapdoors for discrete log 72cryptosystems." CRYPTO’92, pp. 66–75. 73 74\[FGHT16]: J. Fried, P. Gaudry, N. Heininger, E. Thome. "A kilobit hidden SNFS 75discrete logarithm computation". http://eprint.iacr.org/2016/961.pdf 76 77[OW96]: P. C. van Oorschot, M. J. Wiener, "On Diffie-Hellman key agreement with short exponents", 78Eurocrypt 96, pp 332–343. 79 80[LL98]: C.H. Lim and P.J. Lee, 81"A key recovery attack on discrete log-based schemes using a prime order subgroup", 82CRYPTO' 98, pp 249–263. 83 84[WeakDh]: D. Adrian, K. Bhargavan, Z. Durumeric, P. Gaudry, M. Green, 85J. A. Halderman, N. Heninger, D. Springall, E. Thomé, Luke Valenta, 86B. VanderSloot, E. Wustrow, S. Zanella-Béguelink, P. Zimmermann, 87"Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice" 88https://weakdh.org/imperfect-forward-secrecy-ccs15.pdf 89 90[NIST SP 800-56A], revision 2, May 2013 91http://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-56Ar2.pdf 92 93[PKCS #3]: "Diffie–Hellman Key Agreement", 94http://uk.emc.com/emc-plus/rsa-labs/standards-initiatives/pkcs-3-diffie-hellman-key-agreement-standar.htm 95 96[RFC 2785]: R. Zuccherato, 97"Methods for Avoiding 'Small-Subgroup' Attacks on the Diffie-Hellman Key Agreement Method for S/MIME", 98March 2000 99https://www.ietf.org/rfc/rfc2785.txt 100 101<!-- 102## Sources that might be used for additional tests: 103 104CVE-2015-3193: The Montgomery squaring implementation in crypto/bn/asm/x86_64-mont5.pl 105in OpenSSL 1.0.2 before 1.0.2e on the x86_64 platform, as used by the BN_mod_exp function, 106mishandles carry propagation 107https://blog.fuzzing-project.org/31-Fuzzing-Math-miscalculations-in-OpenSSLs-BN_mod_exp-CVE-2015-3193.html 108 109CVE-2016-0739: libssh before 0.7.3 improperly truncates ephemeral secrets generated for the 110(1) diffie-hellman-group1 and (2) diffie-hellman-group14 key exchange methods to 128 bits ... 111 112CVE-2015-1787 The ssl3_get_client_key_exchange function in s3_srvr.c in OpenSSL 1.0.2 before 1131.0.2a, when client authentication and an ephemeral Diffie-Hellman ciphersuite are enabled, 114allows remote attackers to cause a denial of service (daemon crash) via a ClientKeyExchange 115message with a length of zero. 116 117CVE-2015-0205 The ssl3_get_cert_verify function in s3_srvr.c in OpenSSL 1.0.0 before 1.0.0p 118and 1.0.1 before 1.0.1k accepts client authentication with a Diffie-Hellman (DH) certificate 119without requiring a CertificateVerify message, which allows remote attackers to obtain access 120without knowledge of a private key via crafted TLS Handshake Protocol traffic to a server that 121recognizes a Certification Authority with DH support. 122 123CVE-2016-0701 The DH_check_pub_key function in crypto/dh/dh_check.c in OpenSSL 1.0.2 before 1241.0.2f does not ensure that prime numbers are appropriate for Diffie-Hellman (DH) key exchange, 125which makes it easier for remote attackers to discover a private DH exponent by making multiple 126handshakes with a peer that chose an inappropriate number, as demonstrated by a number in an 127X9.42 file. 128 129CVE-2006-1115 nCipher HSM before 2.22.6, when generating a Diffie-Hellman public/private key 130pair without any specified DiscreteLogGroup parameters, chooses random parameters that could 131allow an attacker to crack the private key in significantly less time than a brute force attack. 132 133CVE-2015-1716 Schannel in Microsoft Windows Server 2003 SP2, Windows Vista SP2, Windows Server 1342008 SP2 and R2 SP1, Windows 7 SP1, Windows 8, Windows 8.1, Windows Server 2012 Gold and R2, and 135Windows RT Gold and 8.1 does not properly restrict Diffie-Hellman Ephemeral (DHE) key lengths, 136which makes it easier for remote attackers to defeat cryptographic protection mechanisms via 137unspecified vectors, aka "Schannel Information Disclosure Vulnerability. 138 139CVE-2015-2419: Random generation of the prime p allows Pohlig-Hellman and probably other 140stuff. 141--> 142