▲ 157 points
back
84 comments
This is a fun exploit to code up, and, stealing a note from a workshop tutorial we found, we build up to it with an RSA parity oracle in Cryptopals 6:
The parity oracle is much easier to code, but I've never seen it in the wild. BB'98 (the "million message attack") on the other hand comes up all the time, even in new code; it's deceptively tricky to prevent.
I think this bug is probably a contender for the top 3 practical cryptography vulnerabilities on the Internet. Its close cousin, Vaudenay's CBC padding oracle, is a lock for #1. Then it's just down to whether nonce reuse is #2 or #3.
> I think this bug is probably a contender for the top 3 practical cryptography vulnerabilities on the Internet. Its close cousin, Vaudenay's CBC padding oracle, is a lock for #1. Then it's just down to whether nonce reuse is #2 or #3.
Is this top 3 list from some public resource that exists and I am a noob who missed the reference and how the community knows what the Top 3 are? If not a resource would love to see it or help make it.
P.S. Been loving SCW podcast from time to time when I can list, keep up the good work!
Nope, it's off the top of my head, and partially proffered as a provocation to other professionals to protest.
In the same provocative vein, is nonce reuse that big of a deal without an associated cleartext leak of some kind? Or is it more like reducing cracking time from thousands of years to hundreds of years?
Not that I'm saying people should do obviously bad things, I'm just wondering how bad it is if some nonces get reused for a particular short-lived session key.
Nonce reuse covers a whole bunch of attacks in different algorithms. It's weird to compare that broad category against two specific examples of padding oracle attacks
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.
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.
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.
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.
This is somewhat of a side question, but do you have an opinion on Ironclad, the Common Lisp encryption library?
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...
The way RSA key exchange has been implemented everywhere involves padding. RSA-KEM[1] has been available since forever and no padding is required, though no one uses it for some reason.
RSA-KEM is also trivial to implement as it's virtually identical to textbook RSA, with the sole restriction that m has to be randomly sampled from 1 .. n-1. The shared secret (technically, the encapsulated key) is the hash of the randomly sampled number.
And just like that, no padding oracles or the headache of implementing padding in the first place.
[1] <https://en.wikipedia.org/wiki/Key_encapsulation_mechanism> , <https://datatracker.ietf.org/doc/html/rfc5990>
RSA-KEM is nice, but RSA keygen is expensive. That makes using RSA for ephemeral key exchange less attractive than ECDHE. RSA-KEM is fine for static-static key exchanges, and RSASSA-PSS is fine for signatures. But we often want ephemeral-static or ephemeral-ephemeral key exchange, and there RSA is slow for little benefit.
One aspect of RSA that may help it become relevant again is that the key size can be arbitrary by utilizing multiple primes (RSA-MP[1]) and therefore increase the qubit requirement for a successful quantum attack. This could lead to a situation where large RSA keys would remain secure for decades longer than ECC keys, and if quantum computers hit a growth wall then those RSA keys could remain secure forever.
RSA-MP would then serve as a hedge (by either ending up completely secure, or buying time) against novel* PQC algorithms being broken. The cost being large public keys, large ciphertexts, slow decryption and very slow keygen.
Another option is to come up with enormous safe primes for good old DH. This would result is very fast keygen, and decryption performance will equal encryption - but will probably be worse than RSA anyway. The biggest public DH safe prime I'm aware of is 16384 bits (unofficially released by someone who worked on some DH standard which ended on 8192 bits).
* McEliece is not novel but did not see as much scrutiny as RSA. And has huge public keys - so might as well be paired with RSA?
[1] <https://www.degruyter.com/document/doi/10.1515/JMC.2008.006/...>
Any RSA scheme must pad messages, otherwise you can leak huge amounts of information.
A high level approximation of what I vaguely recall from back when I worked on crypto (non scam money version) you get stuff along the lines of ((p^m1 mod N) * (p^m2 mod N)) mod N being the same as (p^(m1+m2) mod N). The padding also acts as something of a nonce, and prevents you from inferring the length of the message itself (e.g. you want 'no', 'yes', 'of course I still love you despite you losing all our money investing in beanie babies' to be the same length).
Of course all of this seems more relevant for protocols that are optimized to perform small data transfers in the key exchange itself due to the monumentally giant key exchanges RSA needs to achieve the same security as ECC (seriously people just use ECC), but I'm sure some cryptographers who understand math better than I ever will can explain why these problems also apply even if all you're doing is an exchange of truly random AES keys.
RSA-KEM isn't padded. It fills the whole modulus with random bits, transforms it, and then feeds that to a KDF to generate an encryption key.
One thing that many people aren't aware of (even mathematicians writing textbooks) is that "textbook" RSA isn't actually secure without random padding (it's a theorem that deterministic ciphers can't be semantically secure).
I always wonder who's watching the watchers with encryption. I know there are standard, recommended libraries available. But how are those vetted if mere mortals like myself don't even know what known vulnerabilities to look for? Is there like a high council of crypto wizards that keep checks and balances on each other?
Cryptography engineers and vulnerability researchers who specialize in cryptography look for vulnerabilities in the popular libraries. Cryptographic vulnerabilities are high-status (if you find a pattern of them, you can even get published in the Big 4 academic venues). So there's a lot of incentive to find stuff, at least in popular software.
It's a much bigger problem for bespoke crypto people roll themselves, because the expertise required to find crypto vulnerabilities is uncommon, and there's not that much incentive at all to find a vulnerability in something nobody uses.
> Is there like a high council of crypto wizards that keep checks and balances on each other?
Not exactly, but certainly there are some crypto wizards that would love to get famous for figuring out how to break the so-called trusted algorithms and libraries.
I think this "high council of crypto wizards" is academia, at the end of the day we are talking about advanced math and i think there are many experts on that field eager to prove and correct each other.
Whenever I'm roleplaying with my tinfoil hat, I say that the NSA is behind the "never implement your own crypto" advice.
If you're really worried, roll your own encryption, and then also run the encrypted message through standard encryption implementations. After all, if the standard implementations work, it doesn't matter if you mess up your own crypto implementation, because the standard implementation is unbreakable.
> After all, if the standard implementations work, it doesn't matter if you mess up your own crypto implementation, because the standard implementation is unbreakable.
This sounds like obviously good advice but it actually isn't, if your implementation is vulnerable to timing attacks and is used as the first layer, it can potentially reveal (parts of) your plaintext. Vulnerabilities like this is exactly why "don't roll your own crypto" is good advice
Whenever I'm roleplaying with my tinfoil hat, I say that the NSA is behind comments like yours.
You cannot assume that the security of a composite crypotsystem is max(system1, ..., systemN), i.e. that bolting a secure system to an insecure one is at least as secure as the most secure system. Sometimes it is; sometimes it is not and the insecure system breaks the whole thing in a way that casual analysis can't spot. If I were the NSA trying to inject memes into the software ecosystem to make my job easier, I would definitely recommend that everybody start with vetted open-source cryptosystems and then bolt their hand-rolled crap to them.
As a rule of thumb, pay attention to crypto parameters and cipher 'suites'. Use the highest SHA, use seven word diceware phrases for the password, ensure the latest TLS version is used, use a reputable & robust RNG, etc
SHA2 is fine. The "reputable" RNG comes with your OS; just use getrandom.
Nice writeup, and the point (RSA is very simple, until you actually to need it securely!) is conveyed well.
One thing of note: BB98 essentially springs eternal; a new way to find the single bit of oracle state needed for it is discovered every few years. See ROBOT[1] (2018) and this year's Marvin[2].
Could someone enlighten me on how one goes about testing whether a particular crypto implementation is vulnerable to side-channel attacks?
In high school I implemented a basic ECDH key exchange algorithm, which I compiled to WASM, and it can be tested at the bottom of my blog: https://gredal.dev/projects/elliptic-curves
Using only the WASM blob, without looking at the source code for exploits, how would Alice find Bobs private key?
By changing one's system clock.
Your code shows that `random` is seeded with `time(nullptr)` which has a second precision, so you can guess the generated private key by knowing the exact second the wasm module was initialized and the number of `random` calls until the eventual key was derived. You can see this yourself by loading two identical windows around the same time and generate keypairs from both, resulting in the same keypairs.
Even the most generous assumption gives only ~30 bits of information entropy, so it is extremely unsafe. Forget side-channel attacks---you are not even prepared against direct attacks.
I would recommend using the crypto implementation to secure a large amount of money. If it is vulnerable, the money will disappear eventually.
I hear so much about "side channel attacks", and I get why they are important if you don't know what software is running on your computer. But are they important if you don't run any outside code (not on the cloud, not running JavaScript in a "container", etc?)
Are there other major reasons not to roll your own crypto besides "you might do it wrong"? Wouldn't a fuzz tester (comparing your implementation to a known good one) be well adapted to making sure you didn't do it wrong?
> […] and I get why they are important if you don't know what software is running on your computer.
Side channel attacks are not limited to attackers on the same device. Timing attacks can be remote for instance, and with RSA some operations are slow enough to be noticeable over networks.
> Wouldn't a fuzz tester (comparing your implementation to a known good one) be well adapted to making sure you didn't do it wrong?
Not really. Cryptography is inherently not very conducive to tests, because they can only prove the outcome of specific inputs. You need to be a lot more defensive than that, and use reason, proofs etc to prove properties like “an adversary cannot gain any knowledge about X or Y given that they control Z”.
Of course reimplementing a vetted spec like RSA is better than rolling your own primitives which is beyond doomed. OTOH an opportunistic attacker will probably not bother with a custom crypto - it’s still a lot of work to find the flaws. But once found, game over..
> Timing attacks can be remote for instance, and with RSA some operations are slow enough to be noticeable over networks.
Huh, I'd be pretty curious about that.
> Not really. Cryptography is inherently not very conducive to tests, because they can only prove the outcome of specific inputs
I'm pretty confused by this. It's a completely deterministic operation on a series of bytes. If you have identical results to 2 billion randomized inputs how can that not be pretty high confidence that the underlying algorithm is sound?
Obviously it's good to do the math and reasoning as well, but... I just don't get it. It's not magic, it's math and bit munging.
Only simple in what I call the first level of RSA. But all levels could be fun in an effortful sense.
1. Level: encrypting and decrypting a single number or a couple of characters using public and private keys in a couple of lines of code
2. Level: Follow mathematical proofs and understand why it's theoretically secure
3. Level: come up with an implementation that can be used in production
I guess 1 takes minutes to implement, 2 takes days to understand, 3 weeks to implement assuming a standard programmer who hasn't done security.
People have been talking about using ECC (elliptic-curve cryptography) instead of RSA but I can’t really find a way to use ECC for asymmetric encryption (not signing). I’m pretty sure only RSA (instead of ECC) can be used for asymmetric encryption (disregarding the quantum-resistant algorithms which I haven’t looked into), unless I’m missing something important?
When you want to encrypt asymmetrically with ECC, you do an ECDH operation with the public key of the entity you're sending to, and then include enough information in the file or message for the counterparty to complete the DH operation on their side to derive the message encryption key. This is generally the "right" way to encrypt with RSA as well (with RSA-KEM). Even old PKCS1v15 systems do "hybrid" encryption, with RSA used to establish a key and then AES to do the actual encrypting.
Here's some discussion about that: https://crypto.stackexchange.com/questions/15596/are-there-a...
I wrote a similar blog post a while ago using python [1]. I however attacked RSA using prime number factorization.
0 lessons learned in this write up without knowing almost everything about RSA..
Better watch some discrete math 2 videos from Kimberly Brehm or TrevTutor to see how you can actually compute it.
Is no one going to point out the sloppy math in this equation?
42^3 = 138 mod 493
It should read
42^3 mod 493 = 138
Yes, RSA itself is as simple, you probably just need to know what a prime is, what is greatest common divisor (gcd) and what coprime means (gcd(a, b) = 1) and how Chinese Remainder Theorem (that Chinese nephew of Bézout's Identity) works, and know a little bit of Euler's totient theorem (also known as Euler's Phi function) which can be optimized to Carmichael function (no need to know the proof just yet), then you should be able to understand RSA real good.
The reason RSA works because to crack RSA you need to solve the integer factorization problem which is sufficiently hard until lately (as it is a NP-intermediate problem, which is somewhere between NP-Complete and P-complete, and we don't know whether P=NP yet...), but the key generation is pretty easy (as it can be done in polytime), and so this represents a trapdoor function [1].
Really it is just year 3 uni stuff that everyone has to exam with. I still remember having to do RSA manually on an exam paper and it sucked to be honest.
Mind you: RSA primes may not be unique if you have faulty implementation, because you can do semiprime by squaring a prime. Then you can get another pairs that are effectively the same that can spoof yours, although in reality this shouldn't happen.
Alas, the problem is, RSA is not really invincible, as processing power doubled every few years thanks to Moore's law, the problem of integer factorization is not that hard lately, so much so the RSA challenge was declared dead [2].
So, what did people do? They just turned to using bigger and bigger primes to mitigate this, but another problem is, finding primes that are big enough are also getting harder and harder, it takes more space as the bit size expands from RSA-1536 to RSA-8192.
Maybe it is fine for a Ryzen PC to do it with fine-tuned AVX2 vectorization to get instant prime generations (I think OpenSSL did that), for MCUs, smartphones and most importantly, smartcards (yes, RSA Security formed just to sell smartcards), that's a no-go.
Do you want to see your RSA key goes into the range of Kilobytes and even Megabytes? Clearly not. And the gist is that this can't go on forever and ever, not only that, it has been proven that by using a quantum computer, the problem of integer factorization was reducible to polytime [3], that also means you can crack RSA in polytime! All in theory of course, as quantum computers they are still in its infancy and it can crack no more than 128-bit for now, but the math tells the fact, many people bet it would catch up lately, and in order to get future proofed, RSA is considered a no-can-do now.
And instead, people started moving on to Elliptic Curve Cryptography (ECC) which I clearly lacked the fundamental knowledge to know, but you may need to know Group Theory, know what is finite field arithmetic, and what the heck is an Edwards curve. To this day, even Group Theory looked like a mindfuck to me. But I heard that's what Math major students have to suffer along, packaged together with Abstract Algebra.
As I'm just a computer science John Doe who can barely navigate through the abstract algebra textbook, I can tell the pain.
N.B. Shor's algorithm also spawned a whole slew of Post-Quantum Cryptography such as McEliece cryptosystem, and we are slowly turning into mindfuck category for crypto now. Wish it can be easier and simpler to understand and implement.
[1]: https://en.wikipedia.org/wiki/Trapdoor_function
Advancing classical computer power, of the kind found in GPUs and vectorization silicon, doesn't really do anything to threaten RSA-2048, which is (at least) what's deployed in all modern RSA applications. The thing that threatens RSA-2048 is likely to threaten all the rest of RSA; that might be quantum computing, or it might be mathematical advances, but either way there isn't so much an arms race of increasing RSA key sizes.