A few days ago socat, a popular networking tool, issued a curious sounding security advisory:

"In the OpenSSL address implementation the hard coded 1024 bit DH p parameter was not prime. The effective cryptographic strength of a key exchange using these parameters was weaker than the one one could get by using a prime p. Moreover, since there is no indication of how these parameters were chosen, the existence of a trapdoor that makes possible for an eavesdropper to recover the shared secret from a key exchange that uses them cannot be ruled out."

More background information on this vulnerability can be found on Ars Technica and Hacker News, in this post I want to focus on building an exploit.

The patch shows that

p = 143319364394905942617148968085785991039146683740268996579566827015580969124702493833109074343879894586653465192222251909074832038151585448034731101690454685781999248641772509287801359980318348021809541131200479989220793925941518568143721972993251823166164933334796625008174851430377966394594186901123322297453

It has been discovered that

p = 271 * 13597 * 38894884397634366007356454548332370646972724268802781973440208895542936165564656473524541403310393405820598366261673173802130771236325314878371830363723788045821711985461441675679316058246609104355161134470046705337593170498462616195650378975298117141144096886684800236261920005248055422089305813639519

The last factor, let's denote it F3889, is a 1002-bit non-prime integer, whose factors remain unknown. By trial division __we__ know that its smallest factors are larger than $2^{40}$. If we want to go further, we'll need to deploy a proper factorization algorithm. In that case I'll choose Lenstra elliptic curve factorization, whose running time depends on the size of smallest factor of F3889 rather than the size of the number itself. If the smallest factor is smaller than $2^{250}$, the Lenstra's algorithm would recover it before too long. The other factors can then be recovered by either Lenstra's or the general number field sieve algorithm.

On the other hand if F3889 is a product of two 500-bit primes, chances are we might never be able to factor it (without spending a million of dollars or so). This is very unlikely, if $p$ was indeed randomly generated. Thus, it's reasonable to assume that anyone determined and lucky enough can factor F3889 completely. It'll be a fun project, let me know if you want to work on it :).

But, you might ask, why do we care so much about the factors of $p$? It seems to have nothing to do with solving the discrete log problem (DLP) on $Z_p$, doesn't it? The answer is yes, knowing the factors of $p$, and if they are small enough, allows one to solve DLP on $Z_p$, thanks to the Chinese Remainder Theorem (CRT).

As I wrote before on this blog, CRT is one of the most powerful cryptanalysis tools ever. I've seen countless systems broken because of it. Whenever analyzing or designing a new system, ask yourself if you can break it using this simple trick, and you'll be surprised that most of the times the answer is yes. Pohlig and Hellman probably asked this question themselves, and eventually figured out that if the order of a group is a product of small primes (i.e., a smooth number), one can solve DLP in the subgroups, which is easier, and combine the results using CRT to obtain the discrete log in the original group.

Let's look at an example. Suppose that we want to solve for $x$, given $g$ and $h = g^x \pmod{n}$, where the order of group $Z_n$ is $\phi(n) = q_1 * q_2$ with $q_1$ and $q_2$ are prime. We can break this problem into three smaller sub-problems:

1/ Find $x_1$ such that $h^{q_1} = (g^{q_1})^{x_1} \pmod{n}$

2/ Find $x_2$ such that $h^{q_2} = (g^{q_2})^{x_2} \pmod{n}$

3/ We can prove that $x = x_1 \pmod{q_2}$ and $x = x_2 \pmod{q_1}$, and thus can figure out $x$ with CRT.

Note that 1/ and 2/ are themselves DLP, but they are in subgroups of order $q_1$ and $q_2$, respectively. Hence, the Pohlig-Hellman algorithm reduces DLP in group of order $q_1 * q_2$ to DLP in group of order $q_1$ or $q_2$. If $q_1$ or $q_2$ or small, we can brute-force for $x_1$ or $x_2$. If they are larger, we can deploy the Pollard's rho or the index calculus algorithm. It has been estimated that an academic team can break discrete log if $q_1$ or $q_2$ is a 768-bit prime and that a nation-state can break a 1024-bit prime.

I hope that it's clearer now why we need to factor $p$. We want to calculate $\phi(p)$ and its factors, which we need to deploy the Pohlig-Hellman attack. Is it surprising that the factors of the order of the group determines how hard DLP is on that group?

If the largest factor of $p$ is smaller than 2^800 it's reasonable to assume that anyone knowing this factor can solve DLP on the multiplicative group $Z_p$. That is, they can find $x$ given $g$ and $h$, where $g^x = h \pmod{p}$; this in turn allows them recovering the shared secret just by passively eavesdropping on the Diffie-Hellman key exchange. Note that if the larger factors of $p$ are not safe prime, i.e., not in the form of $2 * q + 1$ where $q$ is also a prime, the computation cost is even smaller.

In summary you can exploit this bug by following these steps:

1/ Using Lenstra elliptic curve factorization and the general number field sieve to factor $p$ completely, and

2/ Using Pohlig-Hellman and CRT to reduce DLP on the multiplicative group $Z_p$ to the multiplicative group $Z_{p'}$ where $p'$ is the largest factor of $\phi(p)$, and

3/ Using Pollar's rho or index calculus to solve DLP on $Z_{p'}$, and

4/ Sniffing socat traffic and recovering the DH shared secret, and

5/ Profit!

If this is a backdoor, it's trivial for its creators to exploit it, because they can skip 1/ and pre-compute most of 2/ and 3/. Even if this is not a backdoor, I suspect that it doesn't cost more than \$10K on AWS or Google __Cloud__ Platform to perform step 1/, 2/ and 3/. If we're so lucky that F3889 is a product of 3 primes, 2 of which are 250-bit, step 1/ might cost less than \$2K, and pre-computation for step 2/ and step 3/ might cost even less.

## 13 comments:

Great introduction, and that is the reason why we just need to care about DLP on cyclic groups of large prime orders. And to avoid most attacks (which are very similar to methods mentioned in your post), we must use strong primes.

As far as I know (please correct me if I am wrong), to generate a strong prime, i.e. a prime $p$ that has the form $kq + 1$, where $q$ is also large prime, we use the properties of arithmetic progresses, which is stated as Dirichlet's theorem: "Let $r, m$ are integers such that $\gcd(r,m)=1$, then there exists infinitely many primes of the form $r + km$ (that is all the set of prime $p$ such that $p \equiv r \mod m$. Denote this set as $\pi_{r,m}$. Then $\pi_{r,m}$ approximates $\frac{1}{\phi(m)}\frac{x}{\log x}$, where $\phi(m)$ is the Euler's totient function." For reference, see

https://primes.utm.edu/notes/Dirichlet.html

From this, if we want to find a 100 bit strong prime, we can start with a 80 bit prime $q$, and choose random $k$, and then test whether $kq + 1$ is prime. The theorem of Dirichlet above give us the estimation of success probability. Also, the next question might be how we can test a prime number in an efficient way? As far as I know, people prefer using elliptic curve primality proving. The construction of suitable curves for testing is difficult, and Morain-Atkin have to use complex multiplication method.

But these things cannot defend the very efficient attack, the index calculus. Amazingly, the analogue generally fails for ECDLP, though it is again true for curves of higher genus (hyperelliptic curves)! These things mentioned in this comment can be found in the book of L. C. Washington about elliptic curves.

Awesome post! I've been looking into it myself. Some people also told me about pollard's p-1 and p+1 factoring algorithm that might work.

The other thing is that the new 2048bits prime they used might have a "bad" order. If you can factor it in primes small enough, there is Pohlig-Hellman attack as well.

Last thing: this is not only vulnerable to passive Pohlig-Hellman attacks, but also to more active attacks like small subgroup attacks where you would send a different generator of each of the smaller subgroups. 1) Since the subgroup of the generator they used (2) for the new prime is unknown, it must be that they're not verifying that publickey sent to their program are indeed in the right subgroup 2) since we can generate our own generators, we can build smaller base for our discrete log problems and it should be faster than Pohlig-Hellman. Significantly faster? I don't know

Thanks for the comment, Thuong (somehow while writing this I actually wondered what you would say :-P). You're right that in practice people find a prime q, then test if 2 * q + 1 is also a prime, if so use that as the final output. I haven't seen anyone using any other values for k rather than 2 though. If the generator is chosen such that its order is k * q, and if a larger k is used, adversary might perform the small-subgroup attack to extract log(k) bits of the Diffie-Hellman exponent. With k = 2 they can extract one bit, but they can already know that by calculating the Legendre symbol.

For primality, I think most implementations don't use primality proving but only primality testing using a combination of Miller-Rabin and Lucas tests.

I'm still working on that book of Washington, and I'll greatly appreciate if you explain how complex multiplication works. I found it's very hard to understand :(.

David Wong: yes, small-subgroup attacks should work too. Though I don't think they are too practical in real world settings, where most people use ephemeral keys.

> I haven't seen anyone using any other values for k rather than 2 though

You can't use something else than 2, otherwise you get an even number > 2 => not a prime

Thanks you for your waiting :D. Unfortunately, I know very little on the topic of complex multiplication. I just mention a little bit about the definition here. Though it is used to construct curves with given number of points (very important in ECDLP, right?), I really don't know how it works.

Let us consider an elliptic curve over $\mathbb{Q}$, denoted $E(\mathbb{Q})$. As we know, it is an abelian group, which has the ring of endomorphism. Recall that an endomorphism is a polynomial map from $E(\overline{\mathbb{Q}})$ to itself, that transform $\infty$ to $\infty$. Then it is obvious to see that the multiplication by an integer $n$, defined by $P$ to $nP$ is an endomorphism. For ordinary curves, $End(E(\overline{\mathbb{Q}}))$ is isomorphic to $\mathbb{Z}$, the ring of integers. For curves with complex multiplication, this ring is strictly larger than $\mathbb{Z}$.

For example, consider the curve $y^2=x^3+x$, it has the complex multiplication $\phi(x,y)=(-x,iy)$, where $i^2+1=0$ (Recall that this curve defined over $\mathbb{F}_p$, where $p > 3$ and $p \equiv 3\mod 4$, it is a supersingular curve. In the finite fields case, the Frobenius map $(x,y) \rightarrow (x^p,y^p)$ is also an endomorphism, the endomorphism ring is strictly larger than $\mathbb{Z}$ in this situation).

A very important application of this curve is the following theorem, that has a profound meaning: Let $F/\mathbb{Q}(i)$ be the Galois extension of $\mathbb{Q}(i)$ of finite degree, and suppose that $Gal(F/\mathbb{Q}(i))$ is abelian. Then there is an integer $n \ge 1$ such that $F \subset \mathbb{Q}(i)(E[n])$, where $E[n]$ is the set of $n$-torsion group, and $\mathbb{Q}(i)(E[n])$ is the extension field of $\mathbb{Q}(i)$ obtained by adding $x$ and $y$ coordinates of elements in $E[n]$.

The content of this comment can be found in the book of Silverman and Tate "Rational points on elliptic curves" (Chapter VI). For applications of complex multiplication in cryptography, if you are curious (me too), why don't we establish a small program for understanding about this?

P.S: TEX really works in the comments, when we see the full post mode.

Thanks Thuong. I didn't even know that LaTex works correctly =).

Yes, let's set up a small reading group or something that sought out to understand everything one needs to know about elliptic curve crypto :). My personal email address is thaidn@gmail.com, I can create a group on Google Groups or something, and we can start from there. Occasionally we can blog about what we've found and learned on this blog or elsewhere. Jet let me know which medium you prefer.

I propose starting with this question: how the hell did mathematicians discover that points on elliptic curve form a group? The point addition law doesn't look natural at all. It looks like the book of Washing actually explains why (chapter 9 and 11), but I still don't quite understand. Do you?

Thanks you for your comment. I really appreciate your ideas about creating a group to discuss on ECC. It is a very good way to learn. I will think about this and send email to you later.

For the question, I do think that the addition law on elliptic curves is naturally defined in the algebraic viewpoint. In Chapter XI, the author develops the theory of divisors, which allows us to define addition law for curves of higher genus. The addition law on these groups is not "point plus point" as elliptic curves. We have to work with reduced divisors. And these groups are called Jacobian varieties. For an elliptic curve, we have a bijective map between "points" on its Jacobian variety and its "actual" points. Hence, we can define the addition law based on the addition law on the variety. It is an interesting story (but a little bit long), and it cannot be fully covered in this comment.

> how the hell did mathematicians discover that points on elliptic curve form a group

I think they were just trying to figure out how to find rational points on a curve. At first there were easy points to find, then how to find new ones? A good way was to trace a line between two of them, and you get a new point. And by reversing it on the y axis you would get a new point again (this is because of y^2). Later on they figured out that it was forming a group (apparently the proof is pretty easy so I guess it is not so difficult to imagine). There is a video of Bonneh on the subject: https://www.youtube.com/watch?v=4M8_Oo7lpiA

Post a Comment