Denial of Service (DoS) via Large Public Key

[missytake]

This issue was not discovered by me, but during and audit, see "L3" in https://delta.chat/assets/1907-otf-deltachat-rpgp-rustrsa-gb-reportv1.pdf:

"The RSA library allows operating upon large keys, which can consume a large amount of
computation time. An attacker who can force an application to encrypt with a million-byte RSA
public key can force the application into a Denial of Service (DoS) condition."

"The assessment team recommends exposing a higher-level API which performs additional
security checks. For instance, key sizes may be limited to 4096 bits by default but can be
overridden if necessary."

[tarcieri]

Thanks for opening a tracking issue for this.

I agree that something like 4096 or 8192 would be a reasonable limit for a "checked" API.

My understanding is some applications (i.e. OpenPGP) need to support significantly larger keys. I'm not sure what the sanity limit should actually be there (IIRC @dignifiedquire mentioned up to 16384 iirc?)

So perhaps the default API could be changed to have a sanity limit, and an additional *_unchecked API could be added which doesn't enforce the sanity check in order to support exotic key sizes.

[dignifiedquire]

So for gpg the default limit seems to be 8KiB, with a compile time option to go larger than that: https://wiki.gnupg.org/LargeKeys.
I have not heard of any use case other than pgp for larger keys, so I think we could follow the same approach

• default: up to 4kib
• medium-keys: up to 8kib
• ´large-keys`: up to 16kib

[tarcieri]

@dignifiedquire how about reducing that to just two options, one which allows keys <= 4096-bits, and "large keys" mode which supports up to 16384-bits?

[tarcieri]

#170 restricts the maximum modulus size to 16384 bits. That's a stopgap, but not sufficient to close this issue.

To go further, we need to relegate keys that large to the previously proposed "large keys" mode, and set a lower bound which is used by default. I'm still thinking 4096-bits there.

Edit: opened #171 which restricts public keys to 4096-bits by default.

[tarcieri]

#176 now restricts the max public key size to 4096-bits, unless the special RsaPublicKey::new_with_max_size function is used to override the limit.

Note we place no limit on max RsaPrivateKey size. However, I can't think of a threat model where we should consider attacks based on a malicious private key. It seems like if that's a possibility, you have bigger problems than DoS.