-
Notifications
You must be signed in to change notification settings - Fork 1.5k
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
Comments
Thanks @roadicing, The docs for $ 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
I think it is necessary to introduce a check for whether |
Take a look at 9aa07aebbdc6 and see if it helps. |
Yes, I think it is feasible. However, since primality testing can also become time-consuming when the |
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 However, I feel that adding primality checks within the |
Guess this issue can be closed / is resolved by that 9aa07ae is on master? Thank you 😄 |
Hi Firstly, the infinite loop issue in 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 |
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 incrementsn
by one each time until we find ann
such thatJacobi(n, p) = -1
. However, this overlooks the case whenp
is in the form ofm^2
andm
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 be1
or0
but not-1
, therefore, no matter hown
continues to increase, it will never satisfyJacobi(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 parameterp
as:which is the square of:
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 handles03
compression encoding, we need to ensure that the points in the constructed DER file are in compressed form (start with03
).Fix
To fix this issue, the simplest method is to check whether
p
is a prime number at the beginning of theModularSquareRoot
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).The text was updated successfully, but these errors were encountered: