RSA is deceptively simple and fun
ntietz.com
ntietz.com
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.
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!
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.
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.)
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.
Nonce reuse in nonce-based AEADs gives you authentication key recovery; it destroys authentication completely.
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.
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.
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
Certain primes are easier to factor which can weaken your encryption. That was the biggest one when we where taught RSA.
let's p be a prime.
return the set {1,p}.
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.
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.
https://github.com/rongarret/tweetnacl/blob/master/tweetnacl...
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.
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-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/...>
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.
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.
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.
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.
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!
> 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 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!)
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.
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.
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
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.
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.
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?
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.
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.
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].
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?
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.
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?
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..
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.
(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.)
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.
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.
I'm not saying this is a good solution, just trying to understand the problem space.
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.
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.
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.
Better watch some discrete math 2 videos from Kimberly Brehm or TrevTutor to see how you can actually compute it.
42^3 = 138 mod 493
It should read
42^3 mod 493 = 138
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