doc/dh.md - platform/external/wycheproof - Git at Google

 # 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.
 -->
	# 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.
	-->