Paper 2023/539

Dlog is Practically as Hard (or Easy) as DH – Solving Dlogs via DH Oracles on EC Standards

Abstract

Assume that we have a group $G$ of known order $q$, in which we want to solve discrete logarithms (dlogs). In 1994, Maurer showed how to compute dlogs in $G$ in poly time given a Diffie-Hellman (DH) oracle in $G$, and an auxiliary elliptic curve $\hat E(\mathbb{F}_q)$ of smooth order. The problem of Maurer's reduction of solving dlogs via DH oracles is that no efficient algorithm for constructing such a smooth auxiliary curve is known. Thus, the implications of Maurer's approach to real-world applications remained widely unclear. In this work, we explicitly construct smooth auxiliary curves for $13$ commonly used, standardized elliptic curves of bit-sizes in the range $[204,256]$, including e.g., NIST P-256, Curve25519, SM2 and GOST R34.10. For all these curves we construct a corresponding cyclic auxiliary curve $\hat E(\mathbb{F}_q)$, whose order is $39$-bit smooth, i.e., its largest factor is of bit-length at most $39$ bits. This in turn allows us to compute for all divisors of the order of $\hat E(\mathbb{F}_q)$ exhaustively a codebook for all discrete logarithms. As a consequence, dlogs on $\hat E(\mathbb{F}_q)$ can efficiently be computed in a matter of seconds. Our resulting codebook sizes for each auxiliary curve are less than 29 TByte individually, and fit on our hard disk. We also construct auxiliary curves for NIST P-384 and NIST P-521 with a $65$-bit and $110$-bit smooth order. Further, we provide an efficient implementation of Maurer's reduction from the dlog computation in $G$ with order $q$ to the dlog computation on its auxiliary curve $\hat E(\mathbb{F}_q)$. Let us provide a flavor of our results, e.g., when $G$ is the NIST P-256 group, the results for other curves are similar. With the help of our codebook for the auxiliary curve $\hat E(\mathbb{F}_q)$, and less than 24,000 calls to a DH oracle in $G$ (that we simulate), we can solve discrete logarithms on NIST P-256 in around 30 secs. From a security perspective, our results show that for current elliptic curve standards the difficulty of solving DH is practically tightly related to the difficulty of computing dlogs. Namely, unless dlogs are easy to compute on these curves $G$, we provide a very concrete security guarantee that DH in $G$ must also be hard. From a cryptanalytic perspective, our results show a way to efficiently solve discrete logarithms in the presence of a DH oracle.