112 lines
6.6 KiB
Markdown
112 lines
6.6 KiB
Markdown
# Diffie-Hellman
|
|
|
|
## Subgroup confinement attacks
|
|
|
|
The papers by van Oorshot and Wiener [[OorWie96]](bib.md#oorwie96) rsp. Lim and
|
|
Lee [[LimLee98]](bib.md#limlee98) 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-SP800-56A]](bib.md#nist-sp800-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]](bib.md#pkcs-3).
|
|
[[PKCS #3]](bib.md#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]](bib.md#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-SP800-56A]](bib.md#nist-sp800-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]](bib.md#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 [[Gordon92]](bib.md#gordon92). 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]](bib.md#fght16). Moreover some
|
|
libraries use primes that are susceptible to this attack
|
|
[[FGHT16]](bib.md#fght16).
|
|
|
|
TODO(bleichen): So far no 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. The authors of
|
|
[[WeakDh]](bib.md#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.
|
|
|
|
<!--
|
|
## 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.
|
|
-->
|