`RsaPrivateKey::from_components` might panic

[Erik1000]

Some internals of the num-bigint-dig crate might panic under some conditions and rsa does not check for these. Therefore, users of the rsa crate experience panics.

I've stumbled upon this while implementing some jose stuff, so this examples uses a key in JsonWebKey format:

use base64ct::{Base64UrlUnpadded, Encoding};
use rsa::{BigUint, RsaPrivateKey};

fn main() -> Result<(), Box<dyn std::error::Error>> {
    let n = BigUint::from_bytes_be(&base64ct::Base64UrlUnpadded::decode_vec("w8XZRYEMzHbSMJXM6kSS2BGicmF5o9_cdlklKYXwey_HpWvI6XtRA9jq_SksGudyvhrLeyNr5P8mUoNPy9DiweXLoidv9kRbU33XLIvJkqbjIXKSwgk9RuQn-v8BoJj8e2uc7sH0eS3RVDtNZ1V1dRbyspC-e2zh9lgcgTRMUVM99pWijcrVD_Wt9hqYlFLM2HA_IoE-9gRrtqrRDwSOrISz_7pzRtJ3RFe3rVkh6MdZVUZ3bNa-D3A6acYmU74YFoVTyKlgSqNmuzFc9yOMM3z4amzLdvfeX_nUxWJdurK80M93vdTqw4-WIzlkkNkUOXq1LUjwZOvtke-t3y87JQ")?);

    let e = BigUint::from_bytes_be(&Base64UrlUnpadded::decode_vec("AQAB")?);

    let d = BigUint::from_bytes_be(&Base64UrlUnpadded::decode_vec("QThDVsVURzV6dpchKhZoOTU-wg45IN_uKTsvhzLI17EmOLS8vRPI_JgiSO6Tc-8RKcXxbfdx9VsPIEQArGzNbj0o5r9urEM_jYQJ0BxNrd6NIlJyE9RSJrDRpOuZVjBBRLioEl5pHImoCACtm7Q7qiNX_Sb9Xk76xD-8V0rd9eVJJBLXpoSV_b_Q80IB9YeZvE8VxzG9dzVjyowzn59SkvG-59G6SteOvLMb9i1in1dzXEKBzauYrExCOlT5t0skJenBVxgD-RNa9Bkjed_4QcNtO3x08F7j2ziqa8iNOtQWRThiArCd14iM2YhdHIZrzPeOYj9DmXIThOlacQ1NAQ")?);

    // original p value
    let p = BigUint::from_bytes_be(&Base64UrlUnpadded::decode_vec("11_iIv_gwowCkC32vALSm3Po9vfirnhX5jIyh2U2mzH9PvLx4OaUQ_O2WWyYRkpTNivSf0erFNjf9xz2efAhVrMX4Y11XPNpWAAsmuawA23Ptgjy6-PGSSHj8PJXXK6jTpoYe6uDtYIe509ODYdTeBU6KNg91T0EbNSV_A4K40E")?);

    let q = BigUint::from_bytes_be(&Base64UrlUnpadded::decode_vec("6LNts0tPvK6J2XgLaWI9rvvztJNzKTznmA5WPDpkApPpKp9U2lDucAyjAIFYJxYuOPN4kJ6tBeFGJAKEU1rv7hW5gXbbkVt6r_v23lV_LQ841pEnsmwvdUEgw3gE7iEviI6ZuiaSQQ-yUSoiKQc0rXeXhdmyVck_y5s1JHl_cuU")?);

    // malicious p
    // when set to zero, it panics and the backtrace points to https://docs.rs/num-bigint-dig/latest/src/num_bigint_dig/algorithms/sub.rs.html#75-79
    // when set to 1 it panics because of a divison by zero, probably because of https://docs.rs/rsa/latest/src/rsa/key.rs.html#344-345
    let p = BigUint::from_bytes_be(&[0x0]);

    // `precompute` in this method will panic
    let private_key = RsaPrivateKey::from_components(n, e, d, vec![p, q]);

    // it could be catched here (maybe, dont know tbh), but since it panics, there's
    // no way
    private_key.validate().unwrap();
    Ok(())
}

This can lead to denial of service attacks if untrusted keys are parsed and isn't mention in the docs at all.
I haven't tried malicious pem/der encoded keys, but it seems realistic that they suffer from the same problem.

I've also noticed that the sign method might loop if an incorrect parameter is used but that can probably be prevented by using RsaPrivateKey::validate.

Also, I really don't like the way primes are passed to RsaPrivateKey::from_components since passing an array with a length < 2 leads to panic because of out of bounds access and that isn't mention in the docs either.

[tarcieri]

I just merged #162 which is a breaking change and puts master on a v0.7.0-pre release series.

This means RsaPrivateKey::from_components could be made fallible as a breaking change, returning errors in cases where it presently panics.

Also, I really don't like the way primes are passed to RsaPrivateKey::from_components since passing an array with a length < 2 leads to panic because of out of bounds access and that isn't mention in the docs either.

One option here would be to drop multiprime RSA support entirely. It's rarely used and provides little performance benefit. The simple solution for better RSA performance is to use a smaller key size, i.e. two smaller primes, rather than using more primes (multiprime RSA provides a minutely better tradeoff for security bounds and prime sizes here).

If we dropped multiprime RSA, then the two primes could be provided as two explicit arguments, which would be straightforward and type safe.

However, if RsaPrivateKey::from_components were made fallible, it could also return a runtime error in this case, which would at least be better than panicking.

[Erik1000]

One option here would be to drop multiprime RSA support entirely. It's rarely used and provides little performance benefit. The simple solution for better RSA performance is to use a smaller key size, i.e. two smaller primes, rather than using more primes (multiprime RSA provides a minutely better tradeoff for security bounds and prime sizes here).

Sadly, I'm not that into RSA to have a good opinion but as long as it stays compatible with other RSA implementations, I would agree.

However, if RsaPrivateKey::from_components were made fallible, it could also return a runtime error in this case, which would at least be better than panicking.

I'm also fine with that as long as we remove the panic. I also think that this decision should be part of #34 as the overall feel of this crate could be better.

[Erik1000]

Revisiting this with an eye on our use case: According to RFC 7518 section 6.3.2 (Algorithms for Json Web Keys), a Json Web Key using RSA is only required to contain the private exponent d. Currently however, p and q are required. So it would be great if we had a way to do RSA (without the possible optimisations) using d only.

Furthermore, I'd suggest something like a separate mode for RSA with optimisations. In this case, I'd suggest to have a constructor which takes a struct with the different values (p, q, dp, dq, qi) needed for optimisation similar how the PrecomputedValues struct is currently used internally.

One way to do this would be to make an RsaMode enum with the variant Default and Optimised like so:

enum RsaMode {
    Default,
    Optimised(OptimisationValues),
}

struct OptimisationValues {
    p: BigUInt,
    q: BigUInt
    dp: BigUint
   // ...
}

The RsaPrivateKey struct could then have a getter function mode which returns the RsaMode.

The constructor for the RsaPrivateKey struct could then look like this:

impl RsaPrivateKey {
    // result cuz the constructor should validate the provided parameters.
    pub fn new(n: BigUInt, d: BugUInt, mode: RsaMode) -> Result<Self>
}

This way, someone who doesn't care about the possible optimisations can still just use the functions for signing / decryption, but those who care are able to match the mode

[tarcieri]

NOTE: accidentally edited your comment trying to quote it @Erik1000. Hopefully it's back to how you had it originally.

So it would be great if we had a way to do RSA (without the possible optimisations) using d only.

You'll need n and e as well.

The algorithm described in Appendix C of https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-56Br1.pdf can be used to recover p and q:

The following algorithm recovers the prime factors of a modulus, given the public and private
exponents. The algorithm is based on Fact 1 in [Boneh 1999].

Function call

RecoverPrimeFactors(n, e, d)

Input

1. n: modulus
2. e: public exponent
3. d: private exponent

Output

(p, q): prime factors of modulus

Errors

“prime factors not found”

Assumptions

The modulus n is the product of two prime factors p and q; the public and private exponents satisfy de ≡ 1 (mod λ(n)) where λ(n) = LCM(p – 1, q – 1)

Process

1. Let k = de – 1. If k is odd, then go to Step 4.
2. Write k as k = 2ᵗr, where r is the largest odd integer dividing k, and t ≥ 1.
3. For i = 1 to 100 do:
   a. Generate a random integer g in the range [0, n-1].
   b. Let y = gʳ mod n.
   c. If y = 1 or y = n – 1, then go to Step g.
   d. For j = 1 to t – 1 do:
   - Let x = y² mod n.
   - If x = 1, go to Step 5.
   - If x = n – 1, go to Step g.
   - Let y = x.
   e. Let x = y² mod n.
   f. If x = 1, go to Step 5.
   g. Continue.
4. Output “prime factors not found,” and exit without further processing.
5. Let p = GCD(y – 1, n) and let q = n/p.
6. Output (p, q) as the prime factors

[Erik1000]

You'll need n and e as well.

Yes, I assumed they are always present since they are the public part of the key. At least according to the JWA RFC

[tarcieri]

API wise, I'd just suggest inherent static functions of RsaPrivateKey that take different parameters.

The recovery algorithm could be provided as something like RsaPrivateKey::recover_prime_factors or RsaPrivateKey::recover_from_private_exponent which accepts n, e, and d.

[tarcieri]

Went ahead and fixed this in #167.

I noted that the recovery function could also be implemented in RsaPrivateKey::from_components when an empty vec of primes is provided, although for clarity it might make sense to sense to have an additional function as well (one can be composed in the form of the other)