Thanks @roadicing,

The docs for ModularSquareRoot already states p must be prime. I think the problem is in the callers. Internal callers like ECP::DecodePoint need to perform the check before calling ModularSquareRoot, just like external callers.

$ grep ModularSquareRoot *.h *.cpp
nbtheory.h:...
ecp.cpp:                P.y = ModularSquareRoot(P.y, p);
nbtheory.cpp:Integer ModularSquareRoot(const Integer &a, const Integer &p)
nbtheory.cpp:           Integer s = ModularSquareRoot(D, p);
rabin.cpp:      cp = ModularSquareRoot(cp, m_p);
rabin.cpp:      cq = ModularSquareRoot(cq, m_q);

Hi @noloader

Yes, considering that users are directly vulnerable to DoS attacks when using the API as shown below to parse external public key files (also including parsing certificates using APIs from cryptopp-pem):

DL_PublicKey_EC<ECP> pubKey;
FileSource fs(".malformed-pub.der", true);
pubKey.Load(fs); // infinite loop

I think it is necessary to introduce a check for whether p is a prime number, at least in ECP::DecodePoint.

@roadicing ,

Take a look at 9aa07aebbdc6 and see if it helps.

@noloader

Yes, I think it is feasible. However, since primality testing can also become time-consuming when the p contained in the external public key or certificate is extremely large, a more recommended approach is to also check the size of p before testing its primality in ECP::DecodePoint. Currently, the largest p used in NIST-recommended ECDSA parameters is 521 bits, which can serve as a reasonable upper bound.

external public key or certificate is extremely large, a more recommended approach is to also check the size of p before testing its primality in ECP::DecodePoint. Currently, the largest p used in NIST-recommended ECDSA parameters is 521 bits, which can serve as a reasonable upper bound.

I disagree with this one. All security parameters must be checked before use. If you don't validate it, then you can't use it. If you can't use it, then there's no sense in even loading it.

(And I don't buy into the crap like CVE-2023-3446).

Hi @noloader

The issue is that in the current version with primality checks added, an attacker can change their approach by constructing an ECDSA public key containing a very large prime number. Consequently, any user who uses the API in the same way as before the fix will still be vulnerable to a DoS attack. The difference is that before the fix, it was an infinite loop, whereas after the fix, it becomes a pseudo-infinite loop with the duration depending on the size of the prime number. When the prime number used by the attacker is extremely large (e.g., 20,000 bits), the time consumed by the pseudo-infinite loop is still very significant.

In the current fixes applied by other algorithm libraries, they generally adopt a combination of primality checks and limiting the size of p. In fact, there are other fix approaches (such as changing the implementation of finding the smallest quadratic non-residue in the ModularSquareRoot function as mentioned in the original email, OpenSSL also uses this method). However, this would require more modifications to the implementation from the fix perspective. Therefore, if you do not consider the time cost caused by checking excessively large prime numbers to be a threat, then adding only primality checks would also be acceptable.

However, I feel that adding primality checks within the ModularSquareRoot function already covers the necessary validation. With primality checks already added within this function, conducting further primality checks in other external functions like ECP::DecodePoint seems somewhat redundant. After all, primality checks are relatively time-consuming, and the infinite loop only occurs within the ModularSquareRoot function. Hence, I think that adding primality checks directly into ModularSquareRoot function itself should be sufficient.