Paper 2019/032

Safety in Numbers: On the Need for Robust Diffie-Hellman Parameter Validation

Steven Galbraith, Jake Massimo, and Kenneth G. Paterson

Abstract

We consider the problem of constructing Diffie-Hellman (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 random-base Miller-Rabin 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 1024-bit $p$ which passes OpenSSL's Diffie-Hellman 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 Pohlig-Hellman 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 co-factor, $q$ is relatively smooth but fools random-base Miller-Rabin primality testing with some reasonable probability, and $E$ has a point of order $q$. Concretely, we provide example curves at the 128-bit security level with $h=1$, where $q$ passes a single random-base Miller-Rabin 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)
PDF
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in PKC 2019
Keywords
Primality testingMiller-Rabin testDiffie-HellmanPAKEElliptic Curve Diffie-HellmanCarmichael numbers
Contact author(s)
Jake Massimo 2015 @ rhul ac uk
History
2020-04-08: last of 2 revisions
2019-01-17: received
See all versions
Short URL
https://ia.cr/2019/032
License
Creative Commons Attribution
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 Diffie-Hellman 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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.