Checks performed in check_public seem insufficient

[randombit]

The check_public function nominally checks "that the public key is well formed and has an exponent within acceptable bounds."
https://github.com/RustCrypto/RSA/blob/master/src/key.rs#L642

But it also accepts even exponents, as long as they are within the defined range.

And it does not perform any checks on the modulus, accepting values including zero, even numbers, or modulus smaller than the public exponent.

Is accepting such keys intentional?

[dignifiedquire]

no, this is likely a carry over from the fact thah originally it was not possible to specify a custom exponent. So this should be fixed

[dfabregat]

In fact, the checks should be carried out in a couple of places. For instance, passing an even exponent to the function RsaPrivateKey::new_with_exp will hang forever, since the computation of the modular inverse in src/algorithms.rs:128 will never succeed. This simple test showcases the issue:

    #[test]
    fn test_new_with_exp() {
        let mut rng = rand::thread_rng();
        let bits = 2048;
        let _priv_key = RsaPrivateKey::new_with_exp(&mut rng, bits, &BigUint::from_u64(65536).unwrap());
    }  

I think this should be given some thought to make sure checks are in place where needed and not much duplicated code is introduced. Maybe one could also set a lower bound to the modulus size (e.g., 1024), and add to the checks. NIST SP 800-56B Revision 2 (section 6.4) may provide some guidance.

If you give me some time to get familiarized with the code, I can propose some changes.

[tarcieri]

We added an initial set of public key checks in #170 and #176.

There currently aren't any such checks on private keys, beyond checking that there are at least two primes.

Checks on both public and private keys could definitely be further improved. A minimum modulus size definitely seems like a good idea (with the ability to bypass it through an _unchecked API, which seems important to @dignifiedquire's goals of supporting exotic legacy OpenPGP keys).

I think the private key APIs currently permit a number of potential misuses (see above-mentioned exponent-related DoS) which it would be good to mitigate.

[dfabregat]

Thanks for your feedback @tarcieri. I'd be happy to know more about those exotic/legacy use cases. @dignifiedquire: Any pointer where this has been discussed or documented?

[dignifiedquire]

The original reason why I wrote this implementation was to support https://github.com/rpgp/rpgp which is a full rust implementation of OpenPGP, which is used with a variety of existing keys out there in the wild. There is a set of keys in the tests there, but in general I have to follow roughly "if Gnupg accepts the key, I have to accept it"

[tarcieri]

We can still make the default APIs misuse resistant, with *_unchecked APIs that bypass the checks.

See the existing RsaPublicKey::new_unchecked API.

[dfabregat]

Hi guys. I took a look at this issue in a bit more detail, and have a couple of considerations:

1. I find the "unchecked" approach dangerous. It leads to inconsistencies such as accepting a key of length outside the bounds that are accepted in key::check_public_with_max_size. This would currently clash with the check in oaep::encrypt and oaep::decrypt. Moreover, it may lead to duplicating code all over the place to allow a "checked" and an "unchecked" interface for all algorithms/schemes.
2. From what I see at GnuPG's website, they support keys from 1k to 4k (up to 8k/16k with a compile-time flag):

RSA is the world’s premier asymmetric cryptographic algorithm, and is built on the difficulty of factoring extremely large composites. GnuPG supports RSA with key sizes of between 1024 and 4096 bits.

Since version 2.0.27 and 1.4.19 GnuPG can be compiled with --enable-large-secmem to offer an --enable-large-rsa option that can create keys up to 8 KiB. Some elder versions supported creating of keys up to 16 KiB.

In light of this, a reasonable approach to satisfy all parties may be to

• accept keys >= 1k at RsaPrivateKey::from_components and public keys (since these are built "from components" too), and
• generate keys >= 2k only, since this is the best practice these days.

Then the checks simply ensure the least restrictive of these conditions.

According to the above, I would suggest:

For RsaPublicKey::new*:

• 3 <= e <= upper_bound, and odd
• 1024 <= bits(n) <= 4096 (or larger), and odd
• e < n

I'm not sure why RsaPublicKey::new_with_max_size exists. Maybe one should rather find a reasonable upper bound and stick to it for the checks. Also, as I mentioned above, I would drop RsaPublicKey::new_unchecked.

For RsaPrivateKey::{new*,from_components}:

At most, I would consider checking for primality of the primes. Everything else I can think of is already there.

What do you think?

[dignifiedquire]

I understand the desire to avoid the unchecked versions, but it will reduce the value of this library. There is still work happening today, eg for using RSA for accumulators, and other experiments, where being able to widely vary the modulus is quite beneficial, from tests to benchmarks, etc. So I think the we need to keep unchecked versions available.

[dfabregat]

Understood. In that case, I guess we can leave the key bounds, the unchecked versions, etc., aside for now, and address the minimum requirements that originated this issue. That is, adding the following checks to key::check_public_with_max_size:

• n odd
• e odd and e < n