The basics of RSA are deceptively simple and fun but if you actually care about security then there are dozens of details you have to worry about which are deceptively nuanced and complicated. It's fine to play around with toy implementations like this, but you should never ever use such an implementation in an application where security actually matters. (In fact, if security matters, you probably should not be using RSA at all because there are so many ways to shoot yourself in the foot with it if you are not extremely careful. ECDH and ECDSA are much better, especially when used with Edwards curves like Curve25519.)
Meanwhile on the web RSA keeps popping up because for some odd reason it's the easiest way to do public key encryption using the built-in option, Web Crypto (it does support RSA-OAEP, but still). With interfaces like this https://developer.mozilla.org/en-US/docs/Web/API/RsaHashedKe... I'm sure there's plenty of typos to be found just setting the publicExponent for example.
There are good third-party libraries but it's too bad Web Crypto doesn't offer something like libsodium's sealed box (or XChaCha for that matter on the symmetric side) to make encryption less of a footgun for devs building web apps.
WebCrypto also supports ECDH/ECDSA, so one could get by without RSA. But point well made about it being too bad that WebCrypto doesn't offer higher level tools. I'm developing one such third-party library right now, and while HPKE[1] is a pretty thin layer on top of WebCrypto, it's unfortunate that it has to be written in JS at all. Last I checked, the crypto library sitting under Chrome (and probably Firefox as well?) already has HPKE implemented. If only there were a nice API through to it..
There aren't many times where direct application of RSA's encryption transform, to recover semantically meaningful data, is useful. But widespread use of RSA predates modern crypto (what people used to call "Crypto 2.0", hallmark feature being authenticated encryption), so it's still in all the APIs.
Sadly, but unsurprisingly, searching for "Crypto 2.0" does not yield information about a shift in cryptography. What time period was this around when this phrase was being used? Where could I find more info on it? What was the shift primarily about?
That's a very good question. I heard it from Nate Lawson, and this would have been right around the time I wrote the [A-E-S "doing it wrong"] (just Google that) blog post. It's bugged me for years, too. I pretty sure he didn't make it up!
The big shift I perceived from him was from generic composition of authenticators and ciphers and such, and long sprawling discussions about E-t-M and M-t-E and "the Horton Principle" and stuff, to the AEAD ciphers pretty much everybody uses now.
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.
No, I don't. On the one hand I am very biased in favor of CL, and I have no reason to doubt Irconclad's quality. On the other hand, it almost certainly has very few users and so has almost certainly received very little scrutiny. Personally, I use libsodium (actually TweetNaCl) for all my crypto applications. I have CL bindings for TweetNaCl here:
Thanks. I was looking forward to your input because ironclad is the usual reccomendation in the CL ecosystem and you are one of the few lispers who also did security work. I'm not in the field but to me the Ironclad library looks very well maintained and honnest. It is also well doccumented and the code is very readable. The maintainer seems anonymous but judging by their github profile they do mainly security work.
"Well-maintained and honest" is not the same as "secure". But as with anything in security, it all turns on your threat model: how sophisticated are your potential attackers, and how valuable are the assets you are trying to protect? If the answer to both is "not very" then Ironclad is probably plenty good enough. Besides, even if you do succumb to an attack, the most likely vector will not be your crypto library but some mistake you made in how you embedded it in your application.
"Well-maintained and honest" is not the same as "secure".
Sure, but it is a vital pre-requisite. Unfortunately many things that are taken for granted as "secure" and are well used are neither well-maintained (not the same thing as actively maintained) nor honnest, especially in js and python world.
Comments
The basics of RSA are deceptively simple and fun but if you actually care about security then there are dozens of details you have to worry about which are deceptively nuanced and complicated. It's fine to play around with toy implementations like this, but you should never ever use such an implementation in an application where security actually matters. (In fact, if security matters, you probably should not be using RSA at all because there are so many ways to shoot yourself in the foot with it if you are not extremely careful. ECDH and ECDSA are much better, especially when used with Edwards curves like Curve25519.)
Meanwhile on the web RSA keeps popping up because for some odd reason it's the easiest way to do public key encryption using the built-in option, Web Crypto (it does support RSA-OAEP, but still). With interfaces like this https://developer.mozilla.org/en-US/docs/Web/API/RsaHashedKe... I'm sure there's plenty of typos to be found just setting the publicExponent for example.
There are good third-party libraries but it's too bad Web Crypto doesn't offer something like libsodium's sealed box (or XChaCha for that matter on the symmetric side) to make encryption less of a footgun for devs building web apps.
WebCrypto also supports ECDH/ECDSA, so one could get by without RSA. But point well made about it being too bad that WebCrypto doesn't offer higher level tools. I'm developing one such third-party library right now, and while HPKE[1] is a pretty thin layer on top of WebCrypto, it's unfortunate that it has to be written in JS at all. Last I checked, the crypto library sitting under Chrome (and probably Firefox as well?) already has HPKE implemented. If only there were a nice API through to it..
[1] https://datatracker.ietf.org/doc/rfc9180/
There aren't many times where direct application of RSA's encryption transform, to recover semantically meaningful data, is useful. But widespread use of RSA predates modern crypto (what people used to call "Crypto 2.0", hallmark feature being authenticated encryption), so it's still in all the APIs.
Sadly, but unsurprisingly, searching for "Crypto 2.0" does not yield information about a shift in cryptography. What time period was this around when this phrase was being used? Where could I find more info on it? What was the shift primarily about?
That's a very good question. I heard it from Nate Lawson, and this would have been right around the time I wrote the [A-E-S "doing it wrong"] (just Google that) blog post. It's bugged me for years, too. I pretty sure he didn't make it up!
The big shift I perceived from him was from generic composition of authenticators and ciphers and such, and long sprawling discussions about E-t-M and M-t-E and "the Horton Principle" and stuff, to the AEAD ciphers pretty much everybody uses now.
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
This is somewhat of a side question, but do you have an opinion on Ironclad, the Common Lisp encryption library?
https://github.com/sharplispers/ironclad
No, I don't. On the one hand I am very biased in favor of CL, and I have no reason to doubt Irconclad's quality. On the other hand, it almost certainly has very few users and so has almost certainly received very little scrutiny. Personally, I use libsodium (actually TweetNaCl) for all my crypto applications. I have CL bindings for TweetNaCl here:
https://github.com/rongarret/tweetnacl/blob/master/tweetnacl...
Thanks. I was looking forward to your input because ironclad is the usual reccomendation in the CL ecosystem and you are one of the few lispers who also did security work. I'm not in the field but to me the Ironclad library looks very well maintained and honnest. It is also well doccumented and the code is very readable. The maintainer seems anonymous but judging by their github profile they do mainly security work.
"Well-maintained and honest" is not the same as "secure". But as with anything in security, it all turns on your threat model: how sophisticated are your potential attackers, and how valuable are the assets you are trying to protect? If the answer to both is "not very" then Ironclad is probably plenty good enough. Besides, even if you do succumb to an attack, the most likely vector will not be your crypto library but some mistake you made in how you embedded it in your application.
Sure, but it is a vital pre-requisite. Unfortunately many things that are taken for granted as "secure" and are well used are neither well-maintained (not the same thing as actively maintained) nor honnest, especially in js and python world.