In this article, we demonstrate a subtle but devastating backdoor in finite-field Diffie–Hellman. By computing public keys modulo $p^2$ instead of $p$ while restricting the secret exponent to $x \leq p-1$, the discrete logarithm becomes efficiently recoverable using Fermat quotients. We show the full derivation and provide a working Sage implementation. Backdoors are always bad — but they are catastrophic when they are embedded in a fundamental primitive like Diffie–Hellman key exchange. If your browser shows a green lock, you assume your connection is secure. But what if the implementation of Diffie–Hellman contains a tiny change that looks harmless in code review — and yet allows an attacker to recover the private exponent in milliseconds? In this post I’ll show a nasty little backdoor that requires only a tiny modification: using a modulus of $p^2$ instead of $p$, while keeping the secret exponent bounded by $p$ This ...
We start with a very brief primer to Binary Quadratic Forms (BQF). For more information ⦗1⦘ is a very good source to start with.
A Binary Quadratic Form is a polynom of the form $Q(x,y) = ax^2+bxy+cy^2$ with integer coefficients. We focus on integer BQF, i.e., $x,y \in \mathbb{Z}$. Often one is only interested in the behaviour of the coefficients $a,b,c$ and in those cases one refers to a BQF simply by the triple $(a,b,c)$. Further, the integer $D$ defined as: $$D = b^2 - 4ac$$ is called the discriminant of $(a,b,c)$.
A positive definite BQF $(a,b,c)$, i.e. $D < 0, a > 0$, is reduced if $-a < b < a < c$. Gauss observed, that all reduced BQF with the same discriminant form an abelian group and he gave a composition algorithm for those group elements. This group is called the class group and is usually denoted as $\mathcal{Cl}(D)$. The size of the group has a special name and is called the class number $h(D)$. Informally spoken, the class group $\mathcal{Cl}(D)$ contains all different reduced quadratic forms with the same discriminant $D$.
The basic idea i want to talk about is the following: Given a BQF $Q_1 = (n,1,c)$, then, if $Q_1$ is reduced and $pq = n$ is a non trivial factorization of $n$, then also $Q_2 = (p,1,qc)$ is a reduced BQF and is contained in the same class group as $Q1$. With the same argument, this holds for the element $Q_3 = (q,1,pc)$. If we take into account all further different divisors of $n$ and also the prime factorization of $c$, the number of BQFs that reveal the factorization of $n$ can be increased. So, can we say something about the following ratio: $$\frac{\text{Number of BQF with discriminant $D$ that reveal the PF of } n}{\text{The class number } h(D)}$$
For simplicity, we assume that $n=pq > 1$ with $p,q \in \mathbb{P}$. To create a reduced quadratic form, a trivial choice would be $Q = (n,1,n+1)$, which is obviously reduced since $1 < n < n+1$. The discriminant is $D = 1-4n(n+1)$. A very very rough estimation for the class number is $h(D) \approx \sqrt{D}$, hence in our case $D =\sqrt{|1-4n(n+1)|}\approx 2n$. For this trivial choice of $Q$ and under the assumption that $\mathcal{Cl}(D)$ is cyclic, how many elements in the class group generated by $Q$ reveal a factorization of $n$? — We know that the following six BQFs $$(n,\pm1,n+1), (p,\pm1,(n+1)q), (q,\pm1,(n+1)p)$$ are all part of the class group and the last four reveal the factorization of $n$ However, there are more. Let $$n+1 = \prod^f_{j=1}p_i^{e_i}$$ The number of divisors of $n+1$ are $$\sigma_0(n+1) = \prod^f_{i=1} (e_i+1)$$ the number of co-prime divisors are $$\sigma_0^{\text{cp}}(n+1) = 2^f$$ If all exponents $e_i$ are equal to $1$, $\sigma_0(n+1) = \sigma_0^{\text{cp}}(n+1)$. But keep in mind that the BQF must be reduced, so we can not build all combinations of the possible divisors of $n$ and $n+1$. We have to ensure that $a < c$, i.e., $pd_i < q\frac{n+1}{d_i}$ and $qd_i < p\frac{n+1}{d_i}$. An often used upper bound for the number of divisors for a number $n$ is $$\sigma_0(n+1) < n^{\mathcal{O}(1/\log\log n)}$$
Compared to the actual size of the class group the elements that reveal a factorization of $n$ are small. We have around $\sigma_0(n+1)/2$ elements that reveal the factorization compared to a group size of $$\sqrt{1-4n(n+1)} \approx 2(n+1)$$ and the ratio $$\frac{\sigma_0(n+1)}{4(n+1)} < \frac{n^{\mathcal{O}(1/\log\log n)}}{4(n+1)} < n^{\mathcal{O}(1/\log\log n)-1}$$ is so small that the corresponding probability is negligible.
\begin{array}[t]{cc}
i & a & b & c & \gcd(n,a) & \gcd(n,c) \\
\hline
0001 & 2993 & 1 & 2994 & 2993 & 1 \\
0002 & 2 & 1 & 4480521 & 1 & 2993 \\
0003 & 1497 & -1 & 5986 & 1 & 2993 \\
0464 & 219 & 1 & 40918 & 73 & 41 \\
0466 & 438 & 1 & 20459 & 73 & 41 \\
0714 & 499 & 1 & 17958 & 1 & 2993 \\
0715 & 6 & -1 & 1493507 & 1 & 2993 \\
0716 & 998 & 1 & 8979 & 1 & 2993 \\
0717 & 3 & -1 & 2987014 & 1 & 2993 \\
1178 & 82 & -1 & 109281 & 41 & 73 \\
1180 & 41 & -1 & 218562 & 41 & 73 \\
1181 & 73 & 1 & 122754 & 73 & 41 \\
1183 & 146 & 1 & 61377 & 73 & 41 \\
1895 & 246 & -1 & 36427 & 41 & 73 \\
1897 & 123 & -1 & 72854 & 41 & 73 \\
2472 & 123 & 1 & 72854 & 41 & 73 \\
2474 & 246 & 1 & 36427 & 41 & 73 \\
3186 & 146 & -1 & 61377 & 73 & 41 \\
3188 & 73 & -1 & 122754 & 73 & 41 \\
3189 & 41 & 1 & 218562 & 41 & 73 \\
3191 & 82 & 1 & 109281 & 41 & 73 \\
3652 & 3 & 1 & 2987014 & 1 & 2993 \\
3653 & 998 & -1 & 8979 & 1 & 2993 \\
3654 & 6 & 1 & 1493507 & 1 & 2993 \\
3655 & 499 & -1 & 17958 & 1 & 2993 \\
3903 & 438 & -1 & 20459 & 73 & 41 \\
3905 & 219 & -1 & 40918 & 73 & 41 \\
4366 & 1497 & 1 & 5986 & 1 & 2993 \\
4367 & 2 & -1 & 4480521 & 1 & 2993 \\
4368 & 2993 & -1 & 2994 & 2993 & 1 \\
4369 & 1 & 1 & 8961042 & 1 & 2993
\end{array}
The group has size $4369$ elements, the table has $31$ entries, whereof $16$ reveal the factorization of $n$. However, as you can see, the elements are not randomly distributed. There are only $6$ different differences between consecutive entries in the table $$ 1, 2, 248, 461, 575, 712 $$
Is there some pattern that could be used?
⦗1⦘ Johannes Buchmann, Ulrich Vollmer: Binary Quadratic Forms, Springer, Berlin 2007, ISBN 3-540-46367-4
A Binary Quadratic Form is a polynom of the form $Q(x,y) = ax^2+bxy+cy^2$ with integer coefficients. We focus on integer BQF, i.e., $x,y \in \mathbb{Z}$. Often one is only interested in the behaviour of the coefficients $a,b,c$ and in those cases one refers to a BQF simply by the triple $(a,b,c)$. Further, the integer $D$ defined as: $$D = b^2 - 4ac$$ is called the discriminant of $(a,b,c)$.
A positive definite BQF $(a,b,c)$, i.e. $D < 0, a > 0$, is reduced if $-a < b < a < c$. Gauss observed, that all reduced BQF with the same discriminant form an abelian group and he gave a composition algorithm for those group elements. This group is called the class group and is usually denoted as $\mathcal{Cl}(D)$. The size of the group has a special name and is called the class number $h(D)$. Informally spoken, the class group $\mathcal{Cl}(D)$ contains all different reduced quadratic forms with the same discriminant $D$.
The basic idea i want to talk about is the following: Given a BQF $Q_1 = (n,1,c)$, then, if $Q_1$ is reduced and $pq = n$ is a non trivial factorization of $n$, then also $Q_2 = (p,1,qc)$ is a reduced BQF and is contained in the same class group as $Q1$. With the same argument, this holds for the element $Q_3 = (q,1,pc)$. If we take into account all further different divisors of $n$ and also the prime factorization of $c$, the number of BQFs that reveal the factorization of $n$ can be increased. So, can we say something about the following ratio: $$\frac{\text{Number of BQF with discriminant $D$ that reveal the PF of } n}{\text{The class number } h(D)}$$
For simplicity, we assume that $n=pq > 1$ with $p,q \in \mathbb{P}$. To create a reduced quadratic form, a trivial choice would be $Q = (n,1,n+1)$, which is obviously reduced since $1 < n < n+1$. The discriminant is $D = 1-4n(n+1)$. A very very rough estimation for the class number is $h(D) \approx \sqrt{D}$, hence in our case $D =\sqrt{|1-4n(n+1)|}\approx 2n$. For this trivial choice of $Q$ and under the assumption that $\mathcal{Cl}(D)$ is cyclic, how many elements in the class group generated by $Q$ reveal a factorization of $n$? — We know that the following six BQFs $$(n,\pm1,n+1), (p,\pm1,(n+1)q), (q,\pm1,(n+1)p)$$ are all part of the class group and the last four reveal the factorization of $n$ However, there are more. Let $$n+1 = \prod^f_{j=1}p_i^{e_i}$$ The number of divisors of $n+1$ are $$\sigma_0(n+1) = \prod^f_{i=1} (e_i+1)$$ the number of co-prime divisors are $$\sigma_0^{\text{cp}}(n+1) = 2^f$$ If all exponents $e_i$ are equal to $1$, $\sigma_0(n+1) = \sigma_0^{\text{cp}}(n+1)$. But keep in mind that the BQF must be reduced, so we can not build all combinations of the possible divisors of $n$ and $n+1$. We have to ensure that $a < c$, i.e., $pd_i < q\frac{n+1}{d_i}$ and $qd_i < p\frac{n+1}{d_i}$. An often used upper bound for the number of divisors for a number $n$ is $$\sigma_0(n+1) < n^{\mathcal{O}(1/\log\log n)}$$
Theorem 1. Let $n=pq$ and $n+1 = d_i\frac{n+1}{d_i}$, then either $\text{max}(d_i,\frac{n+1}{d_i}) > \text{max}(p,q)$ or $\text{min}(d_i,\frac{n+1}{d_i}) > \text{min}(p,q)$.
Proof: If $A$ is the statement $\text{max}(d_i,\frac{n+1}{d_i}) < \text{max}(p,q)$ and $B$ is the statement $\text{min}(d_i,\frac{n+1}{d_i}) < \text{min}(p,q)$, we proof that the statement $A \wedge B$ leads to a contradiction hence $\neg A \vee \neg B$ is true. So w.l.o.g. we assume $d_i \leq \frac{n+1}{d_i}$ and $p \leq q$, so statement $A$ says $\frac{n+1}{d_i} < q$ and $B$ says $d_i < p$. But this together immediately leads to $d_i \frac{n+1}{d_i} < pq = n$, which is a contraction, hence either $\neg A \vee \neg B$ is true. ⬛
Theorem 2. Let w.l.o.g., $n=pq$ and $q > p$ and $n+1$ not a square. Then the element $(pd_i,\pm 1,q\frac{n+1}{d_i})$ is reduced for at least $\sigma_0(n+1)/2$ divisors $d_i$. And the element $(qd_i,\pm 1,p\frac{n+1}{d_i})$ is reduced whenever $\frac{n+1}{d_i} > q$
Proof: We have $q > p$ and that $n+1$ is not a square. For non square number $\sigma_0$ is even and it is $d_i < \frac{n+1}{d_i}$ for $i = 1,...,\sigma_0(n+1)/2$ if the divisors are ordered such that $d_i < d_{i+1}$. Hence the element $(pd_i,\pm 1. q\frac{n+1}{d_i})$ is reduced for at least $\sigma_0(n+1)/2$ values for $d_i$. Since $q > p$ the element $(qd_i,\pm,p\frac{n+1}{2})$ is more critical. From Theorem 1 we know that either $\text{max}(d_i,\frac{n+1}{d_i}) > \text{max}(p,q)$ or $\text{min}(d_i,\frac{n+1}{d_i}) > \text{min}(p,q)$. For $\sigma_0(n+1)/2$ values for $i$ we have $$\frac{n+1}{d_i} > d_i$$. hence in the first case we have $$ \frac{n+1}{d_i}> q > p > d_i$$ Multiplication with $d_i$ yields $$n+1 > qd_i > pd_i $$ Since the fraction $p/d_i$ is larger than $1$ it is $qd_i < p\frac{n+1}{d_i}$ ⬛Compared to the actual size of the class group the elements that reveal a factorization of $n$ are small. We have around $\sigma_0(n+1)/2$ elements that reveal the factorization compared to a group size of $$\sqrt{1-4n(n+1)} \approx 2(n+1)$$ and the ratio $$\frac{\sigma_0(n+1)}{4(n+1)} < \frac{n^{\mathcal{O}(1/\log\log n)}}{4(n+1)} < n^{\mathcal{O}(1/\log\log n)-1}$$ is so small that the corresponding probability is negligible.
# Improvement #
▶ Larger values for b. However, the choice of $b=1$ is actually the worst choice if one wants to keep the class group small. In order to reduce the size of the class group (always assuming that $h(D) \approx \sqrt{D}$), one has to choose $b$ which minimizes the equation $b^2-4ac$.
▶ Distribution of elements with the same coefficient $b$. In the following table, you find the group elements that reveal the factorization of $n=2993=41\cdot 73$ as well have $2993$ as a gcd. The group is generated by the element $Q = (2993,1,2994)$ and has class number $h = 4369$. The left column indicates the $i$ value such that $Q^i$ corresponds to the $a,b,c$ values in the row. E.g. $Q^{715} = (6,-1,1493507)$.
\begin{array}[t]{cc}
i & a & b & c & \gcd(n,a) & \gcd(n,c) \\
\hline
0001 & 2993 & 1 & 2994 & 2993 & 1 \\
0002 & 2 & 1 & 4480521 & 1 & 2993 \\
0003 & 1497 & -1 & 5986 & 1 & 2993 \\
0464 & 219 & 1 & 40918 & 73 & 41 \\
0466 & 438 & 1 & 20459 & 73 & 41 \\
0714 & 499 & 1 & 17958 & 1 & 2993 \\
0715 & 6 & -1 & 1493507 & 1 & 2993 \\
0716 & 998 & 1 & 8979 & 1 & 2993 \\
0717 & 3 & -1 & 2987014 & 1 & 2993 \\
1178 & 82 & -1 & 109281 & 41 & 73 \\
1180 & 41 & -1 & 218562 & 41 & 73 \\
1181 & 73 & 1 & 122754 & 73 & 41 \\
1183 & 146 & 1 & 61377 & 73 & 41 \\
1895 & 246 & -1 & 36427 & 41 & 73 \\
1897 & 123 & -1 & 72854 & 41 & 73 \\
2472 & 123 & 1 & 72854 & 41 & 73 \\
2474 & 246 & 1 & 36427 & 41 & 73 \\
3186 & 146 & -1 & 61377 & 73 & 41 \\
3188 & 73 & -1 & 122754 & 73 & 41 \\
3189 & 41 & 1 & 218562 & 41 & 73 \\
3191 & 82 & 1 & 109281 & 41 & 73 \\
3652 & 3 & 1 & 2987014 & 1 & 2993 \\
3653 & 998 & -1 & 8979 & 1 & 2993 \\
3654 & 6 & 1 & 1493507 & 1 & 2993 \\
3655 & 499 & -1 & 17958 & 1 & 2993 \\
3903 & 438 & -1 & 20459 & 73 & 41 \\
3905 & 219 & -1 & 40918 & 73 & 41 \\
4366 & 1497 & 1 & 5986 & 1 & 2993 \\
4367 & 2 & -1 & 4480521 & 1 & 2993 \\
4368 & 2993 & -1 & 2994 & 2993 & 1 \\
4369 & 1 & 1 & 8961042 & 1 & 2993
\end{array}
The group has size $4369$ elements, the table has $31$ entries, whereof $16$ reveal the factorization of $n$. However, as you can see, the elements are not randomly distributed. There are only $6$ different differences between consecutive entries in the table $$ 1, 2, 248, 461, 575, 712 $$
Is there some pattern that could be used?
⦗1⦘ Johannes Buchmann, Ulrich Vollmer: Binary Quadratic Forms, Springer, Berlin 2007, ISBN 3-540-46367-4
Comments
Post a Comment