Analyzing CVE-2022-0778: When Square Root Results in a Denial of Service

Generally speaking, secure communications should be part of infosec’s solution set, not part of the problem. When CVE-2022-0778 revealed that a maliciously crafted SSL certificate could lead to near-total CPU utilization and denial of service on a targeted machine, we thought it would be instructive to see exactly how something so right can, in very specific situations, go so wrong.

CVE-2022-0778 in a Nutshell

OpenSSL is a very popular library, widely used by many organizations and software applications requiring secure communications. A recently revealed OpenSSL vulnerability, CVE-2022-0778, can use specially crafted certificates to cause a Denial of Service (DoS). The vulnerability affects both clients and servers.

The vulnerability lies in OpenSSL’s implementation of the Tonelli-Shanks algorithm, used to find the square roots of numbers in the elliptic curve cryptography at the heart of the encryption library. This vulnerability occurs when instead of a prime number, a composite number is passed to the algorithm. This results in a computational problem like integer factorization.

In this report we’ll first explain the basics of elliptic curve cryptography, and then provide a detailed analysis of the issue that leads to CVE-2022-0778. This is interesting math, so we’ll walk through it carefully.

Elliptic Curve Cryptography in Short

Elliptic curve cryptography (ECC) is a public-key cryptography based on elliptic curves. It is a modern successor of the legendary RSA cryptosystem, but using the interesting properties of elliptic curves instead of RSA’s multiplication of prime numbers. Because ECC can use smaller key sizes, it is faster than RSA – an obvious benefit.

Elliptic curves are algebraic curves. The following equation describes an elliptic curve:

Ax³ + Bx² y + Cxy² + Dy³ + Ex² + Fxy + Gy² + Hx + Iy +J = 0

Here A,B…J defines the curve. In cryptography, however, a simplified form of the equation – called the Weierstrass elliptic function — is used:

y² = x³ + ax + b

If we visualize the curve, we see something like this:

Figure 1: An elliptic curve. (“Elliptic” in this context refers to the algebra describing the curve, not to the oval shape known as an ellipse.) Image source: https://www.desmos.com/

If we take two points on this curve — point 1 and point 2 — and draw a line, that line intersects the curve at point 3. If we take the opposite point (that is, the point equal to point 3, on the other side of the X axis), it will be point 1 + point2 as shown in the above image.

ECC uses an elliptic curve over finite fields, and the points on the curve are limited to integer coordinates. Thus, the above curve in the modular form will be as follows:

y² ≡ x³ + ax + b (mod p)

where p is a prime number denoting the size of the field. (The symbol ≡ denotes congruence.)

Secondly, elliptic curves are defined over finite fields. Because of this, there exists for every elliptic curve a pre-defined constant point, which is denoted G — the generator point, also known as the base point. Any point P in the subgroup over the elliptic curve can be generated by multiplying G with some integer, K, like so:

P = K*G

Finally, performing the algebraic equation on any two points in the field will result in another point in the field. All the points in the elliptic curve over a finite field form a finite group; the total number of points is called the order of curve, and is denoted by n. There can be multiple non-overlapping subgroups and those will be denoted by h; this is called the cofactor. The number of points in each subgroup is denoted by r. So:

n=h*r

We will not delve further into order and cofactor in this report; it is sufficient for our purposes here to note they exist.

How Is It Used for Encryption?

So, in an elliptic curve we have the following:

1. The elliptic curve over a finite field of form – y²≡ x³ + ax + b (mod p)
2. The generator point or base point — denoted by G.
3. An integer value K which, when multiplied with G, results in another point P on the curve – P = K*G.

Now, it is quick and easy to calculate P as shown, by multiplying K and G. But if we want to figure out K  by dividing P by G, i.e., K =P/G, then it is very difficult or infeasible for large values of K.

This asymmetry, in which multiplying is easy but dividing (factoring) is hard, is the basis of elliptic curve cryptography and is known as the elliptic curve discrete logarithmic problem (ECDLP). Many ECC algorithms rely on this problem by using carefully chosen elliptic curves — fields for which no efficient algorithm exists.

In ECC encryption, K is the private key, P is the public key, and G is the generator point. By understanding ECDLP as shown above, we know that given a generator point G, it’s very easy to figure out public key P on the elliptic curve by multiplying G by private key K. But even with the generator point G and public key P known, it remains very difficult to calculate private key K!

Saving Space with Compressed EC Points… at a Price

Now we know that a public key is simply a point on the elliptic curve. As such, it will have an X coordinate and a Y coordinate. As a reminder, the equation for the elliptic curve itself is

y² ≡ x³ + ax + b (mod p)

So, if we know x, we can easily figure out two values of y by solving the following two equations:

p is an odd prime number, so one value of y would be even and another one would be odd, and either will satisfy the equation.

So we don’t need to use {x,y} coordinates in the public key; we can simply use {x, [even] or [odd]} for our x coordinates, with even or odd denoted by an extra parity bit called a Compressed EC Point. Doing so can save us some space, which is useful for network encryption since it’s less data to transfer.

However, it’s at this point we encounter the vulnerability in OpenSSL’s implementation of the Tonelli-Shanks algorithm, which is used to calculate the two square-root values that give us y1 and y2. Basically, thanks to incautious implementation, the issue in OpenSSL can be triggered while finding the value of y from x if the public key uses coordinates in the Compressed EC Point format.

How Is It Used in SSL Certificates?

With all this in mind, we can see a number of things when looking at an SSL certificate that uses elliptic curve cryptography, as shown in Figure 2:

Figure 2: Details of an SSL certificate

As we see, in SSL certificates we have the following fields:

1. Public Key (pub) = this is P, a point on the curve; i.e., x and y coordinates. This can be in compressed format.
2. Prime = this is the prime number p, which will be used as (mod p)
3. A and B = these two define the curve, i.e., y² ≡ x³ + ax + b (mod p)
4. Generator = This is the base point on the curve by which any other point on the curve can be calculated.
5. Order and Cofactor = These denote the order and cofactor of the curve. (Again, we will not be using these for this report.)

This certificate can be used by the server or by clients. Once this certificate reaches the receiver, the receiver will use the public key to encrypt. If the public key is in the compressed format, the receiver needs to decompress it to figure out y, and to do that they need to solve the curve equation — y² ≡ x³ + ax + b (mod p) .

Since solving the curve equation requires calculating a modular square root of a potentially big number, the function BN_mod_sqrt() will be called. This is the specific function where the CVE-2022-0778 vulnerability can be triggered by a specially crafted certificate with malicious values.

Calculating the Modular Square Root

As mentioned, OpenSSL uses the function BN_mod_sqrt() to calculate modular square roots. As per OpenSSL’s documentation, BN_mod_sqrt() returns the modular square root of a such that in² = a (mod p). The modulus p must be a prime or an error or an incorrect “result” will be returned. The result is stored into in which can be NULL. The result will be newly allocated in that case. We can see, therefore, that p must be a prime number or the result would be incorrect.

As mentioned, the CVE-2022-0778 vulnerability lies in OpenSSL’s implementation of the Tonelli-Shanks algorithm used to perform that calculation.  This algorithm finds a square root or a number n modulo p and expects two parameters, p and n. Here p is a prime number, and n is the number for which we want to find a square root.

There are a few fundamental assumptions and steps for this algorithm, which are summarized below. (For detailed information on the algorithms and proofs supporting this, please check the reference section at the end of this blog.)

1. If given a non-zero number n and an odd prime p, as per Euler’s criterion, n will have a square root if and only if following holds true:

n will be a quadratic residue.

2. If a number z doesn’t have a square root, then as per Euler’s criterion the following will hold true:

Half of the integers between 1 and p-1 will have this property. z will be non-residue.

3. Since p is a prime number, we can write p – 1 = 2^s * Q (Here Q is an odd number.)

Now if we try:

Then:

Here, if we say t = n^Q, we can have the following conditions:

1. If t=1, then R will be the square root of n, as the equation will become

R² ≡ nt (mod p)

Also, for M=S it will satisfy the following:

t is 2^M-1 root of 1

2. If t = 0, then R will be 0 as per the above equation.

3. If t is not 0 or 1, we need to calculate another value of R and t for M-1, and we need to repeat this until t becomes 1 (i.e., t becomes 2⁰, at which point R will be the square root of n).

4. To find new values of R and t, we can multiply it by a factor b² which will be 2^M-2 — the root of -1. To calculate b, z^Q will be repeatedly squared.

If the first solution is R, the second will be p-R.

Replicating the Issue and Debugging the Code

Proof-of-concept code has been posted to GitHub by drago-96 (Riccardo Zanotto). We can generate a certificate with crafted parameters and use the following command to replicate the issue with a vulnerable OpenSSL version:

Figure 3: Passing OpenSSL a certificate with improper parameters

We can see the CPU utilization is almost 100%:

Figure 4: OpenSSL 100% CPU utilization

For debugging purposes we will use drago96’s simple proof of concept, which calls the vulnerable function. On compiling and running it, we can see that it goes into an infinite loop causing almost 100% CPU utilization.

Figure 5: Parsing the improper certificate leads to severe CPU utilization

Looking at the certificate we can see that it uses two specific values of p and a, which are 697 and 696 respectively.

If we look at the elliptic curve equation using those values, it becomes

where x³ + ax + b = 696

Since we know the value of p should be prime, we should notice that 697 is not actually a prime number. (It can be written as 2³ * 87 + 1.)

Figure 6: Prime or not prime? Not prime.

If we try this program with any other random numbers, then this issue will not be replicated. (The logic behind using these specific values, and finding more such values of p and a, is discussed later in this post.)

On running OpenSSL with this proof of concept and looking at the call to bn_mod_sqrt, we can see that parameters passed to it are 696 and 697, as shown in Figure 7.

Figure 7: Passing the parameters to the square-root function.

There is a check to see if p is odd, or if it is 1 or 2, but there is no check to see whether p is prime, as shown below. First p is checked:

Figure 8: p is an odd number that is neither 0 nor 1, so it passes the checks

Then there is a check to see if a is 0 or 1:

Figure 9: Making sure a is neither 1 nor 0

At this point, the function sets the value of e as 1 and calls the BN_is_bit_set function, which basically converts it in the form 2^e * q as shown below, incrementing the value of e for each loop iteration:

Figure 10: Converting the value of e

So, e is the power of 2, and q is an odd number.

At this point there are different potential outcomes depending on the value of e. If the value of e is either 1 or 2, the vulnerable code will not be reached. But if the value of e is 3 or more, then the vulnerable code can be reached, and the Tonelli-Shanks algorithm will be used:

Figure 11: In search of a value of y that is not a square

It takes y from 2 to 22 and then finds a Kronecker symbol (which is a generalized version of a Jacobi symbol, which is a generalized version of a Legendre symbol) with a value of q.

This in turn is used to find the non-quadratic residue modulo p. There are few conditions at this point:

1. If the returned value is 0 or < -1, then the program will exit.
2. If the returned value is 1, then the do while loop will continue.
3. If the returned value is -1, then the program will go to the next step, and we have found z ; that is, the non-quadratic residue modulo p.

It will then calculate the value of b, and enter into a while loop:

Figure 12: In the loop

It then checks if b is one; if so, then the solution is found. Otherwise, it will calculate the value of t = b²(mod p).

But in our example, t will be 1 for the first time, as the value of p is 697 and b is 696.

Figure 13: And now t=1

Under these circumstances, the program will not enter the second while loop. After performing a few operations, the value of t will be changed:

Figure 14: A change in value

Then it will move the value of i, which is 1, to e:

Figure 15: Adding the value of i to e

It will then again go to the while loop start. At this point t is not 1, so this time it will enter in the while loop. The value of i is 2 but the value of e is still 1, so the exit condition is not satisfied.

Figure 16: No exit

Next the process will call another function, BN_mod_mul, to calculate the value of t:

Figure 17: Enter BN_mod_mul

If we step through this function, we can see the following:

Figure 18: With a and b equivalent, the BN_sqrt function is called

Here a and b are the same, so the process will call the BN_sqrt function, which will calculate t = a²(mod p).

The value of t will never become 1, as p is not a prime number but a composite number. This loop will therefore continue forever. The endless, pointless calculation will thus cause extreme resource utilization and ultimately DoS in the application.

How does a loop like this happen? In this article we’re looking at the math and code, not the coding choices, but our colleagues at Naked Security have a post concerning CVE-2022-0778 that leads into a discussion of the oddly framed and nested loops in OpenSSL’s code that led to this problem.

Generating Numbers That Can Cause DoS

So far during the debugging we have used p=697 and n=696 as our values. But there are many such pairs of numbers that can cause this infinite loop (and thus the DoS). We can easily set forth the conditions for such pairs:

1. p should be a composite odd number. (Again, if it is a prime number, the value of t becomes 1 and we exit the loop.)

2. As mentioned earlier in the blog, if p is an odd prime number, then we can write p-1 as

p-1 = 2^Q * S

Now we need value of e >= 3, so let’s use 3. This equation becomes

p-1 = 2³ * 2^c * S  (where c=Q-3) , which we can write as

p-1 = 8 * 2^c * S

This means p-1 must be a multiple of 8.  We can write that as:

p-1 = 8 * d * S

Now if we calculate p, it will be:

p= 8*d*S+1  

Here S should be an odd number.

3. We have seen how the Kronecker symbol was calculated from 2 to 22 with p:

1. If it’s 1, we continue the loop.
2. If it’s 0, we discard that value.
3. If it’s -1, that’s the number.

Based on this we can write a simple program in C that can generate various problematic pairs for p and p-1.

Figure 19: A simple C program to find dangerous pairs of values

If we run this program, we get the following:

Figure 20: Five pairs of numbers that can trigger the CVE-2022-0778 DoS

Twitter user fwarashi has explained this in detail in a post. (A sample python program is also available at that URL.)

As we see in Figure 20, a few other number pairs that can cause the CVE-2022-0778 DoS are (184,185), (328,329), (376,377), (424,425), and (472,473). There are more, but to look briefly at two sets we found:

y² ≡ 184(mod  185) — i.e., x³ + ax + b = 184

y² ≡ 328(mod  329) — i.e., x³ + ax + b = 328

and proper values of x,a and b can be selected that satisfy this equation.

Fixing a Hole

In the unpatched version of OpenSSL, there was a while loop checking for the value of t, and inside that there was an if condition which was checking the value of i ==e, so the program was missing cases where i>e. If the value of i > e, and the value of t does not become 1 in case of a non-prime number, an infinite loop results, and DoS results from that.

Figure 21: The unpatched code

If we look at the patched code, we can see that instead of the while loop, a for loop is added. This runs till the value of i<e, thus preventing the infinite loop issue.

Figure 22: Patched code

If the value of i > e, then it will simply exit.

Conclusion

OpenSSL is a popular, broadly used library; it is not limited to any specific platform or application. Thus, the CVE-2022-0778 vulnerability could potentially affect systems of all sorts around the globe. The issue in OpenSSL can be triggered while finding the value of y from x if the public key uses coordinates in the Compressed EC Point format, causing high system utilization and potentially leading to a Denial of Service attack.

Since implementing cryptographic algorithms is a niche task, sometime errors such as these may go unnoticed. In cases such as OpenSSL, where the code itself is complex, the complexity of the math itself can make it hard to spot a potential bug. All is not lost, though, as careful analysis can unpack the problem and guide us toward a solution.

Sophos coverage

Sophos IPS customers are protected against this threat by following sids which checks for malicious certificate download:  2306976, 2306977 .

References and Credits

This vulnerability involves cryptography, number theory, algorithms, and so on. During this research I was helped by various available resources over the web and offline books. The following are some of the online materials I have used.

Source code and proof of concept:

OpenSSL: https://www.openssl.org/

OpenSSL’s repository:  https://github.com/openssl/openssl

POC for CVE-2022-0778 from Drago-96 [Riccardo Zanotto]: https://github.com/drago-96/CVE-2022-0778

Analysis by Kurenaif [@fwarashi]: https://zenn.dev/kurenaif/articles/ec2eec4ec7ec52

For further information:

Elliptic Curve Cryptography (from Nakov, Svetlin, Practical Cryptography for Developers [2018]):  https://wizardforcel.gitbooks.io/practical-cryptography-for-developers-book/content/asymmetric-key-ciphers/elliptic-curve-cryptography-ecc.html

Hasan, Harady, Elliptic Curves: A journey through theory and its applications (2019):   https://uu.diva-portal.org/smash/get/diva2:1334316/FULLTEXT01.pdf

Integer Factorization Problem (HandWiki): https://handwiki.org/wiki/Integer_factorization

“OpenSSL patches infinite-loop DoS bug in certificate verification,” Naked Security (Sophos blog, 18 March 2022), https://nakedsecurity.sophos.com/2022/03/18/openssl-patches-infinite-loop-dos-bug-in-certificate-verification/

Tonelli-Shanks algorithm (HandWiki): https://handwiki.org/wiki/Tonelli%E2%80%93Shanks_algorithm

Tonelli-Shanks algorithm (Wikipedia): https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm