3 ms·
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
by glial 3y ago
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 https://gmplib.org
- pvg 3y agoRandom 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.
- woodruffw 3y agoGenerally 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/ https://people.redhat.com/~hkario/marvin/
- zimmerfrei 3y agoBut 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.
- remexre 3y agoThe post linked in the article as "shouldn't use RSA" has a few examples: https://blog.trailofbits.com/2019/07/08/fuck-rsa/ https://blog.trailofbits.com/2019/07/08/fuck-rsa/
- nolist_policy 3y agoA 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 https://eprint.iacr.org/2023/1711.pdf
- mratsim 3y agoGMP 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
- BunsanSpace 3y agoThe 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.
- nick__m 3y agoI will give you an algorithm that can factor any prime: let's p be a prime. return the set {1,p}. I think you meant factor the semi-prime.
- adgjlsfhk1 3y agoI 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.