I always hear this caveat, and I'm sure you're right, but I'm curious about the threat model here. If I roll my own RSA using e.g. GMP[1], what would it take to find vulnerabilities? Is there some automated software that could do it automatically for free/cheap, or would it take the resources of a highly specialized org?
Generally speaking: if your RSA decryption implementation has any timing sidechannels, then it is probably vulnerable to some kind of Bleichenbacher variant.
As far as I know, GMP doesn't many any attempts to be generally resistant to timing channels. This year's Bleichenbacher variant[1] specifically calls out GMP's modular exponentiation API (which is what you'd use for RSA) as being susceptible to timing.
But then, the vast majority of the affected libraries in that page don't use GMP at all, but their own custom implementation (including openssl).
In reality, RSA signing with blinding will make any implementation (including those based on GMP) resistant to side channel attacks, targeted at the private key.
What most of these library tripped over in that case, is the treatment of the plaintext in a side channel-safe way after the private key operation. For instance, just the simple conversion of an integer to a byte string can be targeted.
Random nerds on the internet with little more training than a few of the cryptopals exercises will likely find gaping, game-over vulnerabilities in an RSA implementation you threw together with an arbitrary precision maths library.
GMP is not a cryptographic library and using it prevents you from being constant-time, you'll also be very slow. That's for the math.
Then you'll have non-erased secrets in memory.
Now for RSA specifically, you'll likely have one or more issues linked to:
- padding oracles
- falling to fake primes due to using non-hardened Miller-Rabin vs Baillie
- Confusion on the various PKCS specs
- Bleichenbeicher attacks
- anything in the Wycheproof repo or cryptofuzz
I don't think this is true any more. From what I've read, weak primes are rare enough at current RSA sizes that software generally doesn't check for them.
A single fault during signature computation (bit-flip, etc.) allows an attacker to derive the private key[1], if you don't guard against it by validating everything before sending it over the wire.
Comments
I always hear this caveat, and I'm sure you're right, but I'm curious about the threat model here. If I roll my own RSA using e.g. GMP[1], what would it take to find vulnerabilities? Is there some automated software that could do it automatically for free/cheap, or would it take the resources of a highly specialized org?
[1] https://gmplib.org
Generally speaking: if your RSA decryption implementation has any timing sidechannels, then it is probably vulnerable to some kind of Bleichenbacher variant.
As far as I know, GMP doesn't many any attempts to be generally resistant to timing channels. This year's Bleichenbacher variant[1] specifically calls out GMP's modular exponentiation API (which is what you'd use for RSA) as being susceptible to timing.
[1]: https://people.redhat.com/~hkario/marvin/
But then, the vast majority of the affected libraries in that page don't use GMP at all, but their own custom implementation (including openssl).
In reality, RSA signing with blinding will make any implementation (including those based on GMP) resistant to side channel attacks, targeted at the private key.
What most of these library tripped over in that case, is the treatment of the plaintext in a side channel-safe way after the private key operation. For instance, just the simple conversion of an integer to a byte string can be targeted.
Random nerds on the internet with little more training than a few of the cryptopals exercises will likely find gaping, game-over vulnerabilities in an RSA implementation you threw together with an arbitrary precision maths library.
GMP is not a cryptographic library and using it prevents you from being constant-time, you'll also be very slow. That's for the math.
Then you'll have non-erased secrets in memory.
Now for RSA specifically, you'll likely have one or more issues linked to: - padding oracles - falling to fake primes due to using non-hardened Miller-Rabin vs Baillie - Confusion on the various PKCS specs - Bleichenbeicher attacks - anything in the Wycheproof repo or cryptofuzz
The post linked in the article as "shouldn't use RSA" has a few examples: https://blog.trailofbits.com/2019/07/08/fuck-rsa/
The issue with RSA is mainly that not all primes are treated equally.
Certain primes are easier to factor which can weaken your encryption. That was the biggest one when we where taught RSA.
I will give you an algorithm that can factor any prime:
I think you meant factor the semi-prime.I don't think this is true any more. From what I've read, weak primes are rare enough at current RSA sizes that software generally doesn't check for them.
A single fault during signature computation (bit-flip, etc.) allows an attacker to derive the private key[1], if you don't guard against it by validating everything before sending it over the wire.
[1] https://eprint.iacr.org/2023/1711.pdf