The discovered vulnerability triggers an infinite loop in the function BN_mod_sqrt() of OpenSSL while parsing an X.509 certificate.

This happens because the p parameter is supposed to be prime, but it is not checked inside the function, and most importantly nowhere in the stack of calls while parsing the certificate.

The prerequisite is having installed gcc and a vulnerable version of OpenSSL.

Compile with gcc -o my_bad_sqrt my_bad_sqrt.c -lcrypto, run ./my_bad_sqrt and watch it hang forever! :D

The function BN_mod_sqrt() implements the Tonelli-Shanks algorithm for finding a modular square root, i.e. given an integer a and a prime number p, returns a value r such that r^2 == a (mod p).

Analyzing the commit that patches the vulnerability we see that the culprit is the loop that finds the least index i for which b^(2^i)==1 (mod p), where b is defined before in the algorithm.

The loop is changed from

i = 1;
if (!BN_mod_sqr(t, b, p, ctx))
    goto end;
while (!BN_is_one(t)) {
    i++;
    if (i == e) {
        ERR_raise(ERR_LIB_BN, BN_R_NOT_A_SQUARE);
        goto end;
    }
    if (!BN_mod_mul(t, t, t, p, ctx))
        goto end;
}

to

for (i = 1; i < e; i++) {
    if (i == 1) {
        if (!BN_mod_sqr(t, b, p, ctx))
            goto end;
    } else {
        if (!BN_mod_mul(t, t, t, p, ctx))
            goto end;
    }
    if (BN_is_one(t))
        break;
}

In the second case, there is a for loop limited by the variable e; in the original code however there is only a check for the case i==e inside a while loop.

Since these loops are inside a bigger loop that for each iteration sets the new value of e to the current value of i, we try the following attack strategy:

1. in the first execution of the outer loop, make so that i=1 at the end; for this, we need that b^2=1 (mod p).
2. in this way, during the second execution we will have e=1, and if we can get into the inner loop the i==e check will always fail
3. if we manage to always have t != 1 (mod p), we will then stay in the loop forever

Notice that the first two steps can actually happen in a "normal" execution, i.e. with a prime p. However, if p is composite we can also satisfy the third step!

The Tonelli-Shanks algorithm works by writing p - 1 = 2^e * q, with an odd q. This is also the order of the multiplicative group of integers modulo p, and the values e and q will be used many times during the execution; however, if p is not prime, the order of the multiplicative group will not be p-1, and this will help us to get into the infinite loop.

In particular, b is initialized as b = a^q (mod p), meaning that if p was prime, then b would have order some power of 2, which we will then find using the loop.

But if we set p = r * s, the order of the multiplicative group is (r-1)*(s-1) = r*s - r - s + 1 instead of r*s-1. The algorithm uses the q value to obtain an element y of order exactly 2^e; however, when p is not prime, the q value will not have a special meaning for the order, so the element y will not have order a power of two modulo p=r*s.

Since at the end of the first outer loop b is set to b = b*y^(e-i) (mod p), at its second iteration the inner loop will try to find a value i for which b^(2^i) == 1 (mod p), but will fail given that y is no more guaranteed to have order a power of two.

The numbers in the exploit are very simple: we take r=17,s=41, which give p=r*s=697. This means that the computed values of e and q will be p-1 = 2^5 * 87.

We then pick a=696, which means that a == -1 (mod p) and also b == -1 (mod p) when initialized. This will satisfy step 1 setting e=1 for the following outer loop.

Then b will be set to an element with order not a power of 2, and the inner loop will be stuck trying to find and i for which b^(2^i)==1 (mod p).

WIP