Paper 2019/032
Safety in Numbers: On the Need for Robust DiffieHellman Parameter Validation
Steven Galbraith, Jake Massimo, and Kenneth G. Paterson
Abstract
We consider the problem of constructing DiffieHellman (DH) parameters which pass standard approaches to parameter validation but for which the Discrete Logarithm Problem (DLP) is relatively easy to solve. We consider both the finite field setting and the elliptic curve setting. For finite fields, we show how to construct DH parameters $(p,q,g)$ for the safe prime setting in which $p=2q+1$ is prime, $q$ is relatively smooth but fools randombase MillerRabin primality testing with some reasonable probability, and $g$ is of order $q$ mod $p$. The construction involves modifying and combining known methods for obtaining Carmichael numbers. Concretely, we provide an example with 1024bit $p$ which passes OpenSSL's DiffieHellman validation procedure with probability $2^{24}$ (for versions of OpenSSL prior to 1.1.0i). Here, the largest factor of $q$ has 121 bits, meaning that the DLP can be solved with about $2^{64}$ effort using the PohligHellman algorithm. We go on to explain how this parameter set can be used to mount offline dictionary attacks against PAKE protocols. In the elliptic curve case, we use an algorithm of Broker and Stevenhagen to construct an elliptic curve $E$ over a finite field ${\mathbb{F}}_p$ having a specified number of points $n$. We are able to select $n$ of the form $h\cdot q$ such that $h$ is a small cofactor, $q$ is relatively smooth but fools randombase MillerRabin primality testing with some reasonable probability, and $E$ has a point of order $q$. Concretely, we provide example curves at the 128bit security level with $h=1$, where $q$ passes a single randombase MillerRabin primality test with probability $1/4$ and where the elliptic curve DLP can be solved with about $2^{44}$ effort. Alternatively, we can pass the test with probability $1/8$ and solve the elliptic curve DLP with about $2^{35.5}$ effort. These ECDH parameter sets lead to similar attacks on PAKE protocols relying on elliptic curves. Our work shows the importance of performing proper (EC)DH parameter validation in cryptographic implementations and/or the wisdom of relying on standardised parameter sets of known provenance.
Note: Fixed URL links. Added Section 4.4 on disclosure to OpenSSL.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 A minor revision of an IACR publication in PKC 2019
 Keywords
 Primality testingMillerRabin testDiffieHellmanPAKEElliptic Curve DiffieHellmanCarmichael numbers
 Contact author(s)
 Jake Massimo 2015 @ rhul ac uk
 History
 20200408: last of 2 revisions
 20190117: received
 See all versions
 Short URL
 https://ia.cr/2019/032
 License

CC BY
BibTeX
@misc{cryptoeprint:2019/032, author = {Steven Galbraith and Jake Massimo and Kenneth G. Paterson}, title = {Safety in Numbers: On the Need for Robust DiffieHellman Parameter Validation}, howpublished = {Cryptology ePrint Archive, Paper 2019/032}, year = {2019}, note = {\url{https://eprint.iacr.org/2019/032}}, url = {https://eprint.iacr.org/2019/032} }