9 ms·
RSA is deceptively simple and fun
- lisper 3y agoThe 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.)
- glial 3y agoI always hear this caveat, and I'm sure you're right, but I'm curious about the threat model here. If I roll my own RSA using e.g. GMP[1], what would it take to find vulnerabilities? Is there some automated software that could do it automatically for free/cheap, or would it take the resources of a highly specialized org? [1] https://gmplib.org https://gmplib.org
- pvg 3y agoRandom nerds on the internet with little more training than a few of the cryptopals exercises will likely find gaping, game-over vulnerabilities in an RSA implementation you threw together with an arbitrary precision maths library.
- woodruffw 3y agoGenerally speaking: if your RSA decryption implementation has any timing sidechannels, then it is probably vulnerable to some kind of Bleichenbacher variant. As far as I know, GMP doesn't many any attempts to be generally resistant to timing channels. This year's Bleichenbacher variant[1] specifically calls out GMP's modular exponentiation API (which is what you'd use for RSA) as being susceptible to timing. [1]: https://people.redhat.com/~hkario/marvin/ https://people.redhat.com/~hkario/marvin/
- zimmerfrei 3y agoBut then, the vast majority of the affected libraries in that page don't use GMP at all, but their own custom implementation (including openssl). In reality, RSA signing with blinding will make any implementation (including those based on GMP) resistant to side channel attacks, targeted at the private key. What most of these library tripped over in that case, is the treatment of the plaintext in a side channel-safe way after the private key operation. For instance, just the simple conversion of an integer to a byte string can be targeted.
- remexre 3y agoThe post linked in the article as "shouldn't use RSA" has a few examples: https://blog.trailofbits.com/2019/07/08/fuck-rsa/ https://blog.trailofbits.com/2019/07/08/fuck-rsa/
- nolist_policy 3y agoA single fault during signature computation (bit-flip, etc.) allows an attacker to derive the private key[1], if you don't guard against it by validating everything before sending it over the wire. [1] https://eprint.iacr.org/2023/1711.pdf https://eprint.iacr.org/2023/1711.pdf
- mratsim 3y agoGMP is not a cryptographic library and using it prevents you from being constant-time, you'll also be very slow. That's for the math. Then you'll have non-erased secrets in memory. Now for RSA specifically, you'll likely have one or more issues linked to: - padding oracles - falling to fake primes due to using non-hardened Miller-Rabin vs Baillie - Confusion on the various PKCS specs - Bleichenbeicher attacks - anything in the Wycheproof repo or cryptofuzz
- BunsanSpace 3y agoThe issue with RSA is mainly that not all primes are treated equally. Certain primes are easier to factor which can weaken your encryption. That was the biggest one when we where taught RSA.
- nick__m 3y agoI will give you an algorithm that can factor any prime: let's p be a prime. return the set {1,p}. I think you meant factor the semi-prime.
- adgjlsfhk1 3y agoI don't think this is true any more. From what I've read, weak primes are rare enough at current RSA sizes that software generally doesn't check for them.
- wim 3y agoMeanwhile 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/RsaHashedKeyGenParams 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.
- thadt 3y agoWebCrypto 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/ https://datatracker.ietf.org/doc/rfc9180/
- tptacek 3y agoThere 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.
- archgoon 3y agoSadly, 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?
- 3y ago
- medo-bear 3y agoThis 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
- lisper 3y agoNo, 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-bindings.lisp https://github.com/rongarret/tweetnacl/blob/master/tweetnacl...
- medo-bear 3y agoThanks. 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.
- lisper 3y ago"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.
- medo-bear 3y ago> "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.
- woodruffw 3y agoNice 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/ https://robotattack.org/ [2]: https://people.redhat.com/~hkario/marvin/ https://people.redhat.com/~hkario/marvin/
- tptacek 3y agoThis 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: https://cryptopals.com/sets/6 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.
- 616c 3y ago> 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!
- tptacek 3y agoNope, it's off the top of my head, and partially proffered as a provocation to other professionals to protest.
- woooooo 3y agoIn 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.
- some_furry 3y ago
- uticus 3y agoI 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?
- sacrosanct 3y agoAs 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
- tptacek 3y agoSHA2 is fine. The "reputable" RNG comes with your OS; just use getrandom.
- tialaramex 3y agoIf 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.
- tptacek 3y agoI 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.
- tialaramex 3y agoFair, I have no experience with which approach is more likely to prevent naive users from blowing their own feet off in practice.
- 3y ago
- coppsilgold 3y agoThe 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://en.wikipedia.org/wiki/Key_encapsulation_mechanism> , <https://datatracker.ietf.org/doc/html/rfc5990 https://datatracker.ietf.org/doc/html/rfc5990>
- SAI_Peregrinus 3y agoRSA-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.
- coppsilgold 3y agoOne 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/pdf https://www.degruyter.com/document/doi/10.1515/JMC.2008.006/...>
- jbverschoor 3y ago0 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.
- thatxliner 3y agoPeople 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?
- userbinator 3y agoHere's some discussion about that: https://crypto.stackexchange.com/questions/15596/are-there-any-elliptic-curve-asymmetric-encryption-algorithms https://crypto.stackexchange.com/questions/15596/are-there-a...
- tptacek 3y agoWhen 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.
- vitiral 3y agoI 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?
- klabb3 3y ago> […] 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..
- vitiral 3y ago> 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.
- Tainnor 3y agoOne 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).
- mathiasgredal 3y agoCould 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 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?
- adrianN 3y agoI would recommend using the crypto implementation to secure a large amount of money. If it is vulnerable, the money will disappear eventually.
- lifthrasiir 3y agoBy 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.
- stevefan1999 3y agoYes, 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 https://en.wikipedia.org/wiki/Trapdoor_function [2]: https://en.wikipedia.org/wiki/RSA_Factoring_Challenge https://en.wikipedia.org/wiki/RSA_Factoring_Challenge [3]: https://en.wikipedia.org/wiki/Shor%27s_algorithm https://en.wikipedia.org/wiki/Shor%27s_algorithm
- xnacly 3y agoI 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/ https://xnacly.me/posts/2023/rsa/
- mo_42 3y agoOnly 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.
- 1000thVisitor 3y agoIs 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