Vulnerability Description
The vulnerability is in the BN_mod_sqrt()
interface function, which is used to compute the square root of a modulus and expects that the argument p should be a prime number, but there is no check within the function, which leads to a possible infinite loop internally. This function is used when parsing certificates of the following format.
 when the certificate contains an elliptic curve public key in compressed format
 certificate with explicit elliptic curve parameters whose base point is encoded in compressed format
In short, this function is called when the certificate is parsed and the point coordinates need to be decompressed. So an external party can trigger an infinite loop by carefully constructing a certificate with an illegal explicit curve parameter, thus causing a DoS denial of service attack.
Function Analysis
Let’s briefly go through the implementation of this function. The function signature is as follows, a is the operand and p is the modulus.


First, a simple check is done on p. The two cases where p is even and 1, which are obviously not prime numbers, are reported directly as errors, and the case where p is 2 is handled specially.
Next, the special case where a is 0 or 1 is handled specially.
Then calculate A := a mod p
, which is to calculate the nonnegative remainder.


The following lines literally count several consecutive zeros from the first digit of p. In fact, p  1 is expressed in the following format: p  1 == 2^e * q
, which is expressed as an odd multiple of a power of 2, where q is an odd number. For example, if p is 49, which means binary is 110001, then e is 4 and q is 3, 49  1 == 2^4 * 3
.
The next special treatment is for the simple case where e equals 1 or 2, which we skip because it does not go to an infinite loop.
For the case e > 2, it is necessary to compute it honestly using the Tonelli/Shanks algorithm. First you need to find a y that is not a square number and 0 < y < p
, because it is not the point we skip it.
Next, the value of q is computed by shifting p right by e bits to get q.
y := (y ^ q) mod p
, because y is a nonsquare number, so calculating the qth power gives a value of order 2^e. (Don’t ask me why, the comment says so ðŸ¤·)


The next step is to calculate x := a^((q1)/2)
.
The following two calculations b := a*x^2 (= a^q)
.
Then calculate x := a*x (= a^((q+1)/2))
.


Finally, we are going to enter the loop structure that we are most concerned about. Here there are two levels of loops, and the dead loop occurs in the inner loop. Let’s look at the difference between the code before and after the modification. The following is the problematic loop code.
At first glance there seems to be no difference, just a while loop changed to a for loop. The difference is very subtle, there are two main points.
 The former is to determine whether t is 1 to end normally and
i == e
to end abnormally within the loop, while the latter is to determine whetheri < e
to end abnormally and t is 1 to end normally within the loop;  Another very important difference is that the former case of i being 1 is not in the loop
The problem arises from this subtle difference. Consider a situation where e is less than or equal to i at the beginning of the following inner loop (e=1, for example), then the i == e
condition will never be satisfied. If then makes t never equal to 1, then it will enter a dead loop.
For the first time into the outer loop, e is definitely greater than 2 and will not enter the dead loop, but don’t forget that i is assigned to e at the end of the outer loop, as follows.


So combining these conditions, one can try to construct attacks that can enter the dead loop by
 Pick suitable a and p such that
b^2=1(mod p)
, where b is computed from a, so that the outer loop does not enter the while inner loop on the first iteration, and the value of i is 1. So e becomes 1 on the second iteration of the outer loop  When the outer loop does the second iteration, just make
t ! = 1 (mod p)
is always satisfied, it will enter the dead loop
Note : The first condition also happens when p is a normal prime, but if p is a composite number then the second condition will also be satisfied.
Reproduction problem
To reproduce the problem, it is really a matter of picking the right parameters a and p so that the above conditions hold. p needs to be chosen in such a way that it passes some checks in front of the function, it cannot be too obviously a composite number, it must be odd, and e needs to be greater than 2, i.e. the binary representation of p must be of the form ...001
. In addition the selection of a needs to satisfy a == 1 (mod p)
and b == 1 (mod p)
so that after the first outer iteration e is set to 1, making the second entry into the outer iteration enter a dead loop.
Determining a and p requires some knowledge of mathematics and an understanding of the implementation of the Tonelli/Shanks algorithm. I’m not a math major and I never studied number theory, so it takes some time to fully understand the math. The good thing is that drago96 colleague helped us to do this, and he finally chose the combination p=697, a=696. If you are interested, you can read the mathematical description [^3].
With a and p, it is then possible to write a simple test program to reproduce the problem


For the code before the fix, the program will enter a dead loop after execution
And the modification can end normally.
Constructing an Illegal Certificate
Next we try to construct an illegal certificate so that the certificate has an explicit elliptic curve parameter and the base point is encoded in compressed format. Then we modify the curve parameter in the certificate to the value we want.
Create a normal certificate with explicit curve parameters
First we need to create an ec key, because we want the certificate to contain explicit curve parameters, so we also choose to generate the key with explicit parameters


Next, for convenience, we directly selfissue a certificate. Here the output format is set to DER also to facilitate us to modify the ASN1 structure later.


Confirm the certificate information, which contains the curve parameter information.


Where Prime, A, B, and Generator are the target parameters that we need to change. So what should we change them to? And then by what method to modify it?
Constructing illegal certificates
First, we need to figure out what these values mean and what relationships they need to satisfy before we can actually do it. An elliptic curve defined over a finite field satisfies the following equation
$$y^2 \equiv x^3+ax+b\quad (mod\ p)$$
Where a is the curve parameter A, b is the curve parameter B, p is the curve parameter Prime, a, b, p parameters determine an elliptic curve. Decompression point coordinates is based on the xcoordinate to calculate the ycoordinate, from the above formula can see that this requires the operation of finding the square root of.
$$y=\sqrt{x^3+ax+b}\quad (mod\ p)$$
We follow the 697/696 combination used before, i.e. at this point p = 697 and $x^3+ax+b=696$. We just have to choose the right a, b, and x to be the ones for which that latter equation holds.
We make x=8, a=23, b=0, and the equation holds.
The next step is to modify our certificate. Modifying the ASN1 structure with my bare hands is really killing me, so if you know of any handy tools, please do not hesitate to ask. The tool I used was mainly xxd
to hex format for editing, and then xxd r
to go back after I finished. (Thanks to wllmrbnt for the asn1template tool, see later for a detailed description)
 you need to modify the values of the four target fields Prime, A, B and Generator.
 where Prime is 697, i.e. 02b9 in hexadecimal.
 where A is 23, i.e. 17 in hexadecimal
 where B is 0.
 where Generator has an x of 8, and because it is in compressed format, it is changed to 020008 (or 030008) in hexadecimal.
 because ASN1 is a nested structure, after modifying the inner length, you also need to correct the outer length accordingly, which is a manual task.
 in addition, the OpenSSL code will check the padding format of ASN1_INTEGER, so the Prime value cannot be preceded by extra 0 bytes, so we must modify the length of the Prime.
 and OpenSSL also checks the relationship between the length of the point string and the length of Prime (for the compressed format, the point string needs to be 1 more than the length of Prime), which is why we set the Genrator to 030008 instead of 0308.
 One more thing to note is that
xxd r
may add a 0a newline at the end of the file after turning back, and you need to eliminate it. There are many ways to do this, one of which is to use the split command.
Let’s take a look at the ASN1 structure of the certificate, the parts underlined are the parts we need to modify


The target values of Prime, A, B, and Generator have been stated above, and the values before and after modification of the relevant lengths are listed in the following table.
from(dec)  from(hex)  to(dec)  to(hex) 

549  225  488  1e8 
460  1cc  399  18f 
266  10a  205  cd 
227  e3  166  a6 
215  d7  154  9a 
44  2c  13  0d 
33 Prime  21  2  02 
33 Generator  21  3  03 
The specific modification process is as follows, where the steps for editing the text have been omitted.
Update March 21, 2022.
A more convenient method is to use the asn1template tool written by wllmrbnt.
Pull repository.


Generate a DER template from the certificate.


Then modify those parameters we mentioned above, the difference before and after the modification is as follows.


Then use ASN1_generate_nconf(3)
to convert it back to the DERencoded ASN1:


The output certificate file cert_new.der
is the same as the version we edited manually before.
At this point our certificate is constructed and we now take a look at the modified ASN1 structure.


The redlined parts have all been modified by us and the ASN1 encoding of the certificate is normal.
Testing with an illegal certificate
OK, now let’s try to parse this constructed illegal certificate, and if nothing else, it will enter an infinite loop.


You can see that the CPU usage of the openssl process is 100% and the call stack is in the BN_mod_sqrt()
function.
If a malicious attacker uses a carefully constructed certificate like this during the SSL handshake with the server, the server will enter a dead loop, resulting in a DoS attack.
The constructed certificate and intermediate process products have been uploaded to the Github repository and are available for those who need them.