from Hacker News

RSA is deceptively simple and fun

by mikecarlton on 1/17/24, 3:46 PM with 84 comments

• by tptacek on 1/18/24, 7:10 PM

  This is a fun exploit to code up, and, stealing a note from a workshop tutorial we found, we build up to it with an RSA parity oracle in Cryptopals 6:

  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.

• by lisper on 1/18/24, 6:48 PM

  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.)

• by coppsilgold on 1/18/24, 7:19 PM

  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>

• by Tainnor on 1/19/24, 2:59 AM

  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).

• by uticus on 1/18/24, 7:13 PM

  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?

• by woodruffw on 1/18/24, 6:58 PM

  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/

• by mathiasgredal on 1/19/24, 3:28 AM

  Could someone enlighten me on how one goes about testing whether a particular crypto implementation is vulnerable to side-channel attacks?

  In high school I implemented a basic ECDH key exchange algorithm, which I compiled to WASM, and it can be tested at the bottom of my blog: https://gredal.dev/projects/elliptic-curves

  Using only the WASM blob, without looking at the source code for exploits, how would Alice find Bobs private key?

• by vitiral on 1/19/24, 2:39 AM

  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?

• by mo_42 on 1/19/24, 5:45 PM

  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.

• by thatxliner on 1/19/24, 12:33 AM

  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?

• by xnacly on 1/19/24, 8:55 AM

  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/

• by jbverschoor on 1/18/24, 9:23 PM

  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.

• by 1000thVisitor on 1/20/24, 10:56 PM

  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

• by stevefan1999 on 1/19/24, 4:23 AM

  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