ModularSquareRoot in Crypto++ (aka cryptopp) through 8.9.0 allows attackers to cause a denial of service (infinite loop) via crafted DER public-key data associated with squared odd numbers, such as the square of 268995137513890432434389773128616504853.
Hi, recently I found a security issue in the [ModularSquareRoot](https://github.com/weidai11/cryptopp/blob/3e3b8af96d4d957b77588be91df7715efbe2ed69/nbtheory.cpp#L544) function of `Crypto++` library that would cause an infinite loop, since this function is being used in [ECP::DecodePoint](https://github.com/weidai11/cryptopp/blob/93208e83937a351babdfd9cfa07d7908ba15f68b/ecp.cpp#L117), 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](https://github.com/weidai11/cryptopp/blob/3e3b8af96d4d957b77588be91df7715efbe2ed69/nbtheory.cpp#L558) 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). 
A security issue in the `ModularSquareRoot` function leads to a DOS attack
This is a GitHub Issue
repo:cryptopp
owner:weidai11
Title : A security issue in the `ModularSquareRoot` function leads to a DOS attack
Issue date:

--- start body ---
Hi, recently I found a security issue in the [ModularSquareRoot](https://github.com/weidai11/cryptopp/blob/3e3b8af96d4d957b77588be91df7715efbe2ed69/nbtheory.cpp#L544) function of `Crypto++` library that would cause an infinite loop, since this function is being used in [ECP::DecodePoint](https://github.com/weidai11/cryptopp/blob/93208e83937a351babdfd9cfa07d7908ba15f68b/ecp.cpp#L117), 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](https://github.com/weidai11/cryptopp/blob/3e3b8af96d4d957b77588be91df7715efbe2ed69/nbtheory.cpp#L558) 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). 
--- end body ---

A security vulnerability in the `ModularSquareRoot` function of the Crypto++ library can lead to a Denial of Service (DoS) attack due to an infinite loop. This occurs when the function processes a malformed DER public key file containing an elliptic curve parameter `p` that is a perfect square of an odd number. The infinite loop arises because the function fails to find an `n` such that `Jacobi(n, p) = -1`, causing it to run indefinitely. An attacker can exploit this by crafting a specific DER file, leading to potential service disruption.