Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

A security issue in the ModularSquareRoot function leads to a DOS attack #1249

Open
roadicing opened this issue Nov 20, 2023 · 8 comments · May be fixed by #1255
Open

A security issue in the ModularSquareRoot function leads to a DOS attack #1249

roadicing opened this issue Nov 20, 2023 · 8 comments · May be fixed by #1255

Comments

@roadicing
Copy link

roadicing commented Nov 20, 2023

Hi, recently I found a security issue in the ModularSquareRoot function of Crypto++ library that would cause an infinite loop, since this function is being used in ECP::DecodePoint, an attacker could potentially craft a malformed DER public key file, and any user or server attempting to read this public key file in processes such as ECDSA may be susceptible to a DOS attack.

Issue

The issue lies in the second while loop in this function, the loop starts with n = 2 and increments n by one each time until we find an n such that Jacobi(n, p) = -1. However, this overlooks the case when p is in the form of m^2 and m is an odd number.

In this case, jacobi(n, p) = jacobi(n, m^2) can be converted into the product of a series of squares of Jacobi symbols using the properties of Jacobi symbols, this means that its value can only be 1 or 0 but not -1, therefore, no matter how n continues to increase, it will never satisfy Jacobi(n, p) = -1 to break out of the loop, thus leading to an infinite loop.

Furthermore, since this function is being used in ECP::DecodePoint, we can construct a malformed DER public key file that includes an elliptic curve parameter p as:

72358384006116823815439217615866351214375729203207450702838342058601772551609

which is the square of:

268995137513890432434389773128616504853

and repackage it into a DER file, then any attempt to read and parse this DER file in Crypto++ will trigger an infinite loop immediately.

In addition, since the ModularSquareRoot function is in the branch that handles 03 compression encoding, we need to ensure that the points in the constructed DER file are in compressed form (start with 03).

Fix

To fix this issue, the simplest method is to check whether p is a prime number at the beginning of the ModularSquareRoot function. If it is not a prime number, then directly reject any further calculations (after all, even if it is not rejected, the result calculated in this way will be wrong).

@roadicing roadicing linked a pull request Dec 20, 2023 that will close this issue
@noloader
Copy link
Collaborator

noloader commented Jun 10, 2024

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);

@roadicing
Copy link
Author

roadicing commented Jun 10, 2024

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.

@noloader
Copy link
Collaborator

@roadicing ,

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

@roadicing
Copy link
Author

roadicing commented Jun 10, 2024

@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.

@noloader
Copy link
Collaborator

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).

@roadicing
Copy link
Author

roadicing commented Jun 11, 2024

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.

@gsantner
Copy link

Guess this issue can be closed / is resolved by that 9aa07ae is on master?

Thank you 😄

@roadicing
Copy link
Author

roadicing commented Aug 8, 2024

Guess this issue can be closed / is resolved by that 9aa07ae is on master?

Thank you 😄

Hi

Firstly, the infinite loop issue in ModularSquareRoot has indeed been fixed by patch 9aa07ae. However, to be honest, as mentioned in my previous response, this fix introduces a new risk in the form of pseudo-infinite loops due to excessive time overhead from checking large primes. Particularly, since a prime check is already performed within the ModularSquareRoot function, re-introducing prime checks in other functions are somewhat redundant and further increases the time overhead.

Nevertheless, the time consumed by prime checks is finite. If you do not consider the time overhead caused by these checks, then this fix could be viable. Given that the Crypto++ project currently appears to be in a phase with relatively lower update and maintenance frequency, if you need further improvements, you may manually patch the IsPrime function to include necessary limits on prime size, and also thanks for your reply.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

3 participants