RSA is deceptively simple and fun(ntietz.com)
ntietz.com
RSA is deceptively simple and fun
https://ntietz.com/blog/rsa-deceptively-simple/
85 comments
> 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!
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.
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 in CTR, which underpins a bunch of AEADs, gives you direct plaintext recovery. It leads to a repeated keystream.
Nonce reuse in nonce-based AEADs gives you authentication key recovery; it destroys authentication completely.
Nonce reuse in nonce-based AEADs gives you authentication key recovery; it destroys authentication completely.
Yes, it's that bad. See Hanno's talk a few years ago about nonce reuse.
https://www.usenix.org/conference/woot16/workshop-program/pr...
It was presented at Black Hat by injecting their slides into the MI6 website, IIRC, using this exact weakness.
It's not just a bad issue, it's also deceptively easy to run into and not realize it.
AES-GCM has a 96-bit nonce. If you sample these randomly, after 2^32 messages, you have a greater than 2^-32 chance of reuse for each subsequent message.
If you're using this algorithm with a static key to encrypt customer records, as a small business, you might never hit this bound.
If you're as large as a cloud provider, you get a nonce reuse every hour.
(Check out Amazon's KMS white paper if you'd like to see how they avoid this sharp edge in practice.)
https://www.usenix.org/conference/woot16/workshop-program/pr...
It was presented at Black Hat by injecting their slides into the MI6 website, IIRC, using this exact weakness.
It's not just a bad issue, it's also deceptively easy to run into and not realize it.
AES-GCM has a 96-bit nonce. If you sample these randomly, after 2^32 messages, you have a greater than 2^-32 chance of reuse for each subsequent message.
If you're using this algorithm with a static key to encrypt customer records, as a small business, you might never hit this bound.
If you're as large as a cloud provider, you get a nonce reuse every hour.
(Check out Amazon's KMS white paper if you'd like to see how they avoid this sharp edge in practice.)
> AES-GCM has a 96-bit nonce.
why do cryptographers ever do things with fewer than 256 bits? like sure speed is nice, but it's also really nice to know that even if you have a birthday attack and lose another factor of a billion somewhere you're still fine.
why do cryptographers ever do things with fewer than 256 bits? like sure speed is nice, but it's also really nice to know that even if you have a birthday attack and lose another factor of a billion somewhere you're still fine.
Aes has a blocksize of 128bits, which so 96 bit is the nonce size that gets you a 32 bit counter. You probably don't want a smaller counter. Things xsalsa technically have a larger nonce but in reality still derive a smaller nonce.
Right, but the larger key (in XSalsa and X-everything-else) effectively gets mixed into the key, which is fine.
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
Would love to see such a resource, would a static site for a leaderboard be enough to maintain a top 10 list, even for drama and protest?
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.
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/
[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.
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
[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/
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.
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
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.
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:
let's p be a prime.
return the set {1,p}.
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
[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
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...
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.
> "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.
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.
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 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/...>
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.
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.
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.
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.
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
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
[deleted]
> if your implementation.. is used as the first layer...
Don't you have this backward? The inner-most (first) layer would be the unverified roll-your-own, the outer layer would be standard. Outer layers are the first to be penetrated to get to the plaintext, not the inner layers... I'm intuiting as a non-crypto guy so please correct me if wrong.
Don't you have this backward? The inner-most (first) layer would be the unverified roll-your-own, the outer layer would be standard. Outer layers are the first to be penetrated to get to the plaintext, not the inner layers... I'm intuiting as a non-crypto guy so please correct me if wrong.
The point of a timing attack is that some operations take different amounts of time depending on the plaintext and/or key. Depending on the attack in question and your access to the system, this potentially lets you draw conclusions about what was encrypted by observing how quickly the system responds to various requests.
If the custom algorithm is an outer layer, it only processes data that has already been encrypted by another presumably strong algorithm. Even if there's a timing attack, breaking the outer layer can't help you unless you can also break the well-studied inner layer. If the custom algorithm sees the actual plaintext directly, the timing attack can let you straight to the original message, no matter how strong any of your outer layers are.
If the custom algorithm is an outer layer, it only processes data that has already been encrypted by another presumably strong algorithm. Even if there's a timing attack, breaking the outer layer can't help you unless you can also break the well-studied inner layer. If the custom algorithm sees the actual plaintext directly, the timing attack can let you straight to the original message, no matter how strong any of your outer layers are.
Indeed, if the home-made RSA algorithm is the outer layer, and someone manages to break it, then we're back to the status quo. And the status quo is unbreakable encryption, right?
On the other hand, if the home-made RSA algorithm is part of the inner layer, how is it different than any of the other poorly designed code that we use in the user facing side of encryption? If an API call goes through 100,000 lines of business logic, and the result gets encrypted and sent as an API response, that's okay, it happens billions of times per day. In terms of security, what does it matter if a few of those 100,000 lines are a home-made RSA implementation?
On the other hand, if the home-made RSA algorithm is part of the inner layer, how is it different than any of the other poorly designed code that we use in the user facing side of encryption? If an API call goes through 100,000 lines of business logic, and the result gets encrypted and sent as an API response, that's okay, it happens billions of times per day. In terms of security, what does it matter if a few of those 100,000 lines are a home-made RSA implementation?
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.
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.
> 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.
But, the scenario described - that you've responded to - isn't the max of an unordered system; it is the max of a composite system with a specific order. In other words, perceived weakest system is run always before perceived strongest system.
And, if you are saying it still doesn't matter, and if payload1->weak_crypto->strong_crypto causes a vulnerability, what keeps the same vulnerability from occurring naturally with some payload2->strong_crypto that doesn't use weak_crypto?
In other words, why would you choose strong_crypto if it has vulnerabilities with certain payloads but not other payloads? If these vulnerabilities are truly known for certain payloads, then why not inject a decision to avoid strong_crypto if the payload is known to cause vulnerabilities?
Apologies for the first-grade level questions and fervor. Maybe this is why crypto is hard. Or maybe things that are this hard to explain and understand should just not be depended on. I've experienced both.
But, the scenario described - that you've responded to - isn't the max of an unordered system; it is the max of a composite system with a specific order. In other words, perceived weakest system is run always before perceived strongest system.
And, if you are saying it still doesn't matter, and if payload1->weak_crypto->strong_crypto causes a vulnerability, what keeps the same vulnerability from occurring naturally with some payload2->strong_crypto that doesn't use weak_crypto?
In other words, why would you choose strong_crypto if it has vulnerabilities with certain payloads but not other payloads? If these vulnerabilities are truly known for certain payloads, then why not inject a decision to avoid strong_crypto if the payload is known to cause vulnerabilities?
Apologies for the first-grade level questions and fervor. Maybe this is why crypto is hard. Or maybe things that are this hard to explain and understand should just not be depended on. I've experienced both.
If it's true that modifying my plaintext before putting it through a standard encryption algorithm might affect the security, then it might also be possible that sending, say, an HTML payload is more secure than sending a JSON payload. That would be weird.
Can existing encryption algorithms encrypt any payload or can't they? It would be odd if we're worrying about timing attacks, etc, when we can't even securely encrypt any possible plaintext first.
Can existing encryption algorithms encrypt any payload or can't they? It would be odd if we're worrying about timing attacks, etc, when we can't even securely encrypt any possible plaintext first.
Yes, a correct encryption algorithm can encrypt (essentially) any bit string. But it's quite easy to turn a correct encryption algorithm into an incorrect one by bolting on something seemingly innocuous.
Here's a concrete example. Let's say you decide you want to make AES encryption more efficient by defining a new standard, "lzAES", that is just:
Here's why: the definition of a secure cipher is that ciphertexts resulting from the encryptions of any two messages of equal length are indistinguishable. In other words, for any two messages you can choose, if I encrypt both messages under a randomly generated key, you can't tell which ciphertext corresponds to which message. In contrast, lzAES as defined above does not have this property: you could choose one message that's easily compressible (say, a string of zeros) and one that's not (say, a uniformly random string), and then you'd be able to tell which ciphertext corresponds to which plaintext just by looking at the ciphertext lengths.
And this is not just a definitional issue! If you use lzAES to encrypt something, an attacker can guess your message and test whether compressing the guess gives the same length as your ciphertext. Guess-and-check isn't possible with a secure cipher, but it is with lzAES---in other words, it gives away information about your plaintext!
Here's a concrete example. Let's say you decide you want to make AES encryption more efficient by defining a new standard, "lzAES", that is just:
Enc_lz(key, msg) := AES-Encrypt(key, lzw_compress(msg))
Dec_lz(key, ctxt) := lzw_decompress(AES-Decrypt(key, ctxt))
Here's why: the definition of a secure cipher is that ciphertexts resulting from the encryptions of any two messages of equal length are indistinguishable. In other words, for any two messages you can choose, if I encrypt both messages under a randomly generated key, you can't tell which ciphertext corresponds to which message. In contrast, lzAES as defined above does not have this property: you could choose one message that's easily compressible (say, a string of zeros) and one that's not (say, a uniformly random string), and then you'd be able to tell which ciphertext corresponds to which plaintext just by looking at the ciphertext lengths.
And this is not just a definitional issue! If you use lzAES to encrypt something, an attacker can guess your message and test whether compressing the guess gives the same length as your ciphertext. Guess-and-check isn't possible with a secure cipher, but it is with lzAES---in other words, it gives away information about your plaintext!
Thank you for taking the time to explain, your explanation is clear and gives me something to think about. But I have a question about:
> But it's quite easy to turn a correct encryption algorithm into an incorrect one by bolting on something seemingly innocuous.
Isn't every poorly designed web app essentially a giant "bolt on" to the encryption algorithm (HTTPS, etc) it is served through?
If there's a get_thread API, which zips the comment thread, includes it in some JSON as base64 along with other metadata (only the thread itself is zipped), and then sends that as the response over HTTPS, is that not secure? Nobody would bat an eye at this scenario, but it's essentially the same as your example because the plaintext is compressed before encrypting and sending. If it's okay to do this for a web app, why is it not okay to do it as part of a home-made RSA implementation.
(Of course, I'm not actually arguing for a second layer of encryption because it is unnecessary. But my understanding is that it wouldn't cause any harm and I'm trying to understand if that's correct or not.)
> But it's quite easy to turn a correct encryption algorithm into an incorrect one by bolting on something seemingly innocuous.
Isn't every poorly designed web app essentially a giant "bolt on" to the encryption algorithm (HTTPS, etc) it is served through?
If there's a get_thread API, which zips the comment thread, includes it in some JSON as base64 along with other metadata (only the thread itself is zipped), and then sends that as the response over HTTPS, is that not secure? Nobody would bat an eye at this scenario, but it's essentially the same as your example because the plaintext is compressed before encrypting and sending. If it's okay to do this for a web app, why is it not okay to do it as part of a home-made RSA implementation.
(Of course, I'm not actually arguing for a second layer of encryption because it is unnecessary. But my understanding is that it wouldn't cause any harm and I'm trying to understand if that's correct or not.)
The example you give is similar to but not quite the same as "lzAES". The distinction is that in your example, the application is deciding whether to compress or not---the input/output behavior of the cipher doesn't include the compression step, so the cipher it self doesn't suffer from the problem I mentioned in my first note.
But it's still possible for an application to use a cipher incorrectly. In particular, an application-level decision about whether to compress some data before encrypting can have an effect on the application's security. In the case you mention it seems unlikely to be a problem (but that's an application-level question, so it could be).
As an example where it seems like the application-level decision to compress or not matters a lot, imagine an application that sends an encrypted password to a server. If the application compresses the password first, an attacker could learn which values are not my password via guess-and-check-length. (Of course, even without compression the attacker can learn something about the length of my password just by looking at the length of the ciphertext---so probably this is a case where the application should first pad the message to some fixed length before encrypting. But in any case it almost certainly shouldn't compress the password!)
But it's still possible for an application to use a cipher incorrectly. In particular, an application-level decision about whether to compress some data before encrypting can have an effect on the application's security. In the case you mention it seems unlikely to be a problem (but that's an application-level question, so it could be).
As an example where it seems like the application-level decision to compress or not matters a lot, imagine an application that sends an encrypted password to a server. If the application compresses the password first, an attacker could learn which values are not my password via guess-and-check-length. (Of course, even without compression the attacker can learn something about the length of my password just by looking at the length of the ciphertext---so probably this is a case where the application should first pad the message to some fixed length before encrypting. But in any case it almost certainly shouldn't compress the password!)
You should look into the CRIME, BEAST, and BREACH attacks on TLS/SSL. They're related to using compression before encryption.
The TL;DR is that you generally should not compress secret data before encrypting, especially if part of the request might be reflected in the response.
If you look carefully at your browser's HTTPS traffic, you'll notice that dynamic data is never sent using HTTP compression, though static (basically guaranteed to not contain anything secret) data might still use it.
The TL;DR is that you generally should not compress secret data before encrypting, especially if part of the request might be reflected in the response.
If you look carefully at your browser's HTTPS traffic, you'll notice that dynamic data is never sent using HTTP compression, though static (basically guaranteed to not contain anything secret) data might still use it.
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.
If you don't know what you're doing SHA-512/256 (note that's not a choice, that's the name of a single SHA-2 family member) is probably the member of the SHA-2 family to choose.
I go the other way and tell people to ignore KMAC and just use HMAC for everything, and then you don't really need to know about truncated SHA2.
Fair, I have no experience with which approach is more likely to prevent naive users from blowing their own feet off in practice.
My feeling is that like in 2001 it would have been valuable to get people to switch to a non-extendable hash by default because people were freelancing their own MACs, but sometime in the intervening 2 decades people switched fully over to HMAC, so that if you're dealing with someone who is literally writing their own prefixed key hash MAC, you've got bigger problems than Merkle Damgard.
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].
[1]: https://robotattack.org/
[2]: https://people.redhat.com/~hkario/marvin/
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].
[1]: https://robotattack.org/
[2]: https://people.redhat.com/~hkario/marvin/
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?
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.
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?
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..
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.
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.
You are right that it increases the confidence. If you’re following a known algorithm conformance- and edge case tests can be a blessing. Of course in the case of RSA you need arbitrary precision bigint math which is another issue with adversarial inputs.
(What I meant is that you can’t test whether the algorithm is secure, because you can’t enumerate the weaknesses that a cryptanalyst would attempt.)
(What I meant is that you can’t test whether the algorithm is secure, because you can’t enumerate the weaknesses that a cryptanalyst would attempt.)
Ah, you can test the implementation but not the algorithm itself. Got it. I see now I said "roll your own crypto" and I should have said something like "reimplement a crypto"
To prevent side channel, can't you do something as stupid as add a randomized [0-0.1) second sleep to your crytpographic operations? That would make any difference in your algorithms performance negligible.
To prevent side channel, can't you do something as stupid as add a randomized [0-0.1) second sleep to your crytpographic operations? That would make any difference in your algorithms performance negligible.
Bottom line: Yes and no. Yes, you can do that. No, it won't really do what you want.
The best way I've found to imagine a timing attack is as a set of graphs produced from thousands to millions of data points, each of which is a time measurement. Any given high-level input takes a certain amount of time to process (example: trying a login). Curves - and thus timing side channels - are distinguishable from one another when the curves have different peaks. The width of the (probably bell-shaped) curves are going to be determined by the amount of variance.
What happens if you add a little predictable random variance to each operation that's the same in each operation? Each curve probably gets a little wider, but you don't move their peaks relative to one another. At most, it might mean the person carrying out a timing attack needs to gather more data. Timing attacks already work with network noise implicitly doing what you've suggested doing explicitly.
You can simulate this yourself. Graph a thousand points of [0-1] and another thousand points of [0-1]+0.1. Superimpose the curves on one another. You may have to use some bucketing to make the curves visible.
The best way I've found to imagine a timing attack is as a set of graphs produced from thousands to millions of data points, each of which is a time measurement. Any given high-level input takes a certain amount of time to process (example: trying a login). Curves - and thus timing side channels - are distinguishable from one another when the curves have different peaks. The width of the (probably bell-shaped) curves are going to be determined by the amount of variance.
What happens if you add a little predictable random variance to each operation that's the same in each operation? Each curve probably gets a little wider, but you don't move their peaks relative to one another. At most, it might mean the person carrying out a timing attack needs to gather more data. Timing attacks already work with network noise implicitly doing what you've suggested doing explicitly.
You can simulate this yourself. Graph a thousand points of [0-1] and another thousand points of [0-1]+0.1. Superimpose the curves on one another. You may have to use some bucketing to make the curves visible.
That makes sense. So instead you could just require that your crypto stuff takes an absurd amount of time, say 0.5 seconds / MiB? Then every operation will take that long and no information can be gleaned.
I'm not saying this is a good solution, just trying to understand the problem space.
I'm not saying this is a good solution, just trying to understand the problem space.
> So instead you could just require that your crypto stuff takes an absurd amount of time, say 0.5 seconds / MiB?
To add to the other (correct) answer: it’s not a terrible idea, because constant time does not leak. However:
- You need to make sure the time is only a function of input data, otherwise you might leak info about internal code paths.
- If the operation cannot complete in time you may be leaking information, even if you only return a generic error.
These are not massive attack surfaces, but they do exist. As with regular programming, you want to reduce the risk of things that can go wrong by reducing the number of code paths. Only now, the cost of an error is much higher, and can go undetected. But no, other than the various and highly subtle side channels there’s no magic to rolling your own crypto, only a long track record of people who overestimated their abilities (or underestimated their adversaries). Oftentimes it’s due to optimizations in the CPU, memory, disks, language runtimes etc that are the culprits. These subsystems often cache, share, or soft-delete data that the programmer thought was exclusive or lifetime-bounded in a way that it wasn’t.
That’s why I like ECC or AES much more than say RSA or other bigint math heavy things. Bit operations are very predictable, and if they run in a loop of constant iterations even better. All else equal, I’d pick an ECC implementation (and not just because it’s faster and smaller). Almost all vulnerabilities have been implementation or parameter choices, not the foundational math. That said, say OpenSSL RSA has been battletested heavily and for a long time.
To add to the other (correct) answer: it’s not a terrible idea, because constant time does not leak. However:
- You need to make sure the time is only a function of input data, otherwise you might leak info about internal code paths.
- If the operation cannot complete in time you may be leaking information, even if you only return a generic error.
These are not massive attack surfaces, but they do exist. As with regular programming, you want to reduce the risk of things that can go wrong by reducing the number of code paths. Only now, the cost of an error is much higher, and can go undetected. But no, other than the various and highly subtle side channels there’s no magic to rolling your own crypto, only a long track record of people who overestimated their abilities (or underestimated their adversaries). Oftentimes it’s due to optimizations in the CPU, memory, disks, language runtimes etc that are the culprits. These subsystems often cache, share, or soft-delete data that the programmer thought was exclusive or lifetime-bounded in a way that it wasn’t.
That’s why I like ECC or AES much more than say RSA or other bigint math heavy things. Bit operations are very predictable, and if they run in a loop of constant iterations even better. All else equal, I’d pick an ECC implementation (and not just because it’s faster and smaller). Almost all vulnerabilities have been implementation or parameter choices, not the foundational math. That said, say OpenSSL RSA has been battletested heavily and for a long time.
That works if you're willing to have your system be DoS'd. If every request takes half a second, that just means the attacker needs more systems sending requests in parallel to get the required number of samples quickly. In today's world, you'd probably just scale up a bit to ensure you could still serve requests. If you let your system go down under load, you can severely restrict how much data attackers can get at the cost of being useless to whoever your intended users are.
The attacker would also likely need more patience, but timing attacks are not for those looking for quick wins.
The preferred way to handle this is to make sure your operations are constant-time. This eliminates the timing side channel. This is harder, and often slower, but solves the problem entirely.
The attacker would also likely need more patience, but timing attacks are not for those looking for quick wins.
The preferred way to handle this is to make sure your operations are constant-time. This eliminates the timing side channel. This is harder, and often slower, but solves the problem entirely.
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.
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.
[1]: https://xnacly.me/posts/2023/rsa/
[1]: https://xnacly.me/posts/2023/rsa/
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.
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
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
[2]: https://en.wikipedia.org/wiki/RSA_Factoring_Challenge
[3]: https://en.wikipedia.org/wiki/Shor%27s_algorithm
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
[2]: https://en.wikipedia.org/wiki/RSA_Factoring_Challenge
[3]: https://en.wikipedia.org/wiki/Shor%27s_algorithm
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.
https://cryptopals.com/sets/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.