RSA: Theory and Implementation | Hacker News Reader

RSA: Theory and Implementation

eli.thegreenplace.net

112 pointsingve27 comments

This is a fine article, but of course, you should never use RSA implemented like this. In fact, the PKCS1v15 implementation here is itself vulnerable to a textbook padding oracle attack (it errors out on busted padding). This is in set #6 of the cryptopals challenges and is a pretty fun way to learn some things about how RSA works.

A cool recent paper on automating not just this attack but all kinds of "format oracle" attacks --- padding, headers, &c --- using SMT solvers:

https://eprint.iacr.org/2019/958.pdf

RSA is just notoriously difficult to implement correctly, unless you're some kind of crypto expert. https://www.youtube.com/watch?v=lElHzac8DDI

Cryptographers who are much smarter than me disagree with me when I say this but I think there's some truth to this; RSA has, by design, more footguns than the comparable systems you'd create with a modern curve design, starting with the fact that the "directly encrypt with the RSA block transform" primitive is a misfeature.

Tbh RSA should be deprecated; there's really almost no user for it in standard crypto IMO

https://blog.trailofbits.com/2019/07/08/fuck-rsa/

It's been all but deprecated in TLS 1.3... however, it's been replaced with ECDH/ECDSA - which the NSA is now recommending against: https://threatpost.com/nsas-divorce-from-ecc-causing-crypto-...

That's mostly bullshit. NSA is just saying "don't start a multi-year project to upgrade from RSA to NIST P-256 because you will not be finished with that upgrade before we'll ask you to upgrade to a recommended PQ crypto scheme".

There is nothing wrong with X25519 and Ed25519, except that they are vulnerable to quantum computers (like anything else currently in use).

All crypto is difficult to get right unless you're a crypto expert. RSA is not unusual in this regard.

The thing that is unusual about RSA is how many people /kind of/ understand it. Crypto people who dislike RSA say that this leads to a proliferation of terrible RSA implementations, and that it is therefore more dangerous to use than eg ECC. Crypto people who like RSA say that its relative accessibility makes it a more popular target, and that in the absence of a catastrophic break the more-studied cryptosystem should be assumed to be more secure.

Personally I've spent some time recently with badly implemented ECC, and I don't think the mistakes being made there are fundamentally different from or rarer than the mistakes you see in poorly implemented RSA.

> The thing that is unusual about RSA is how many people /kind of/ understand it.

I wouldn't say this is that unusual about RSA but your point is otherwise good.

There are a lot of mechanistic "this is how you do ECC" writeups resulting in a lot of people who think they understand it while having no real intuition for it (and particular for the security considerations).

Over and over-again in cryptography the biggest danger is overconfidence. If you aren't scared of vulnerabilities hiding behind every seemingly minor decision, then you're in trouble.

Probably the worst "kind of understand it" I've seen in cryptography is shamir secret sharing, RSA comes right behind that. The big difference between RSA and ECC is that for a long time people were mystified by the group operations while they felt they understood modular multiplication, but the rise in mechanical group law tutorials has leveled the playing field a lot there.

Interesting, do you mind if I ask what kind of environment you work in? Most of the non-crypto people I know will mumble about primes and factors when asked how public key crypto works, but maybe I'm just wildly out of date.

> All crypto is difficult to get right unless you're a crypto expert. RSA is not unusual in this regard.

Maybe all asymmetric crypto. Symmetric can be a lot easier.

Hmm, I still see a lot of table-driven AES implementations, secrecy-only modes, GCM with attacker-controlled nonces, CBC padding oracles, etc. All of that is anecdata of course, but I don't think I'm completely off course when I say that symmetric crypto is pretty commonly messed up too.

There's a whole line of SSL/TLS attacks stemming from the mistakes experts --- some of them unquestionably competent --- made in putting the symmetric cryptography in that protocol together. Asymmetric cryptography is harder to get right, but they're both extraordinarily tricky.

It is commonly messed up, and I'm not claiming it's easy by any means, although a lot of pitfalls are just because some ciphers are a lot worse than others in being able to get right. But what I mean is that the difficulty of asymmetric crypto is in a very different league IMO. The kinds of pitfalls that are in symmetric crypto (with the better ciphers at least) tend to be pretty understandable for non-experts (regardless of how obvious they are a priori). Whereas with asymmetric crypto it seems like a PhD in number theory (or similar) is more or less a prerequisite.

You can understand most of the seriously exploited asymmetric crypto vulnerabilities --- understand well enough to exploit them, if you can code --- with 9th grade algebra, and just a little bit of linear algebra, enough to set up a lattice basis and reduce it with LLL†, will get you through cutting edge attacks. You do not need deep understanding of number theory (or abstract algebra) to get a grip on this stuff; you just need to study it seriously. It's frustrating that so many people design with cryptography without taking the time to work through and gain an intuition for the well-understood attacks.

The mathematics background will help you find new kinds of vulnerabilities, or spot flaws in novel constructions, but it's worth debunking the idea that the security of the constructions we actually deploy requires some kind of deep mathematical aptitude.

† if you were going to draw a comparison to some other discipline, I'd say this is like knowing enough about routing protocols to implement OSPF, but not needing Leslie Lamport's facility with distributed systems; just a small subset of the overall theory is required

Understanding enough to exploit is not what I meant. I meant understanding enough to know how to secure it. Like how understanding how to design a secure RNG is a heck of a lot harder than knowing how to exploit an insecure one.

> enough to set up a lattice basis and reduce it with LLL

This gets across my point perfectly well. I rest my case.

Can you un-rest it for a second and tell me what you mean by that? For our purposes, a lattice is just a specialization of a vector space, and LLL is (1) not a whole lot harder to grok than Graham-Schmidt and (2) available in every serious library and in Sage, which is how people generally do this. If you have zero linear algebra, this sounds forbidding, but the fundamentals you need before tackling lattices and LLL are like, 1st semester linear algebra, and you can self-study your way to it.

Sean Devlin has talked a bunch of people through actually writing these attacks in cryptopals set 8. We talked English professors through the "number-theoretic" attacks on RSA in cryptopals set 6. It's fine if you don't want to dip into this stuff, but I'm not OK with the pretense that this intuition is somehow unattainable.

We need more people playing with these attacks, and fewer people trying to assemble new cryptosystems out of libraries they understand only from the documentation on the web page.

> We talked English professors through the "number-theoretic" attacks on RSA in cryptopals set 6.

The English professor finished set 8 as well!

Hell, I'm teaching digital artists (the sorts of people whose most technical experience distills to "install tablet drivers so I can work with Photoshop") how to do work through the set, and live-streaming the whole experience on Twitch.

If I can teach random furries how to break RSA, I think it's safe to say that anyone determined can gain the necessary intuition.

Your Twitch stream intrigues me and I wish to subscribe to your newsletter.

https://twitch.tv/soatok

I had to take a hiatus for a few weeks but I'm going to be working through the Cryptopals sets in the coming weeks, starting tomorrow.

IMO, the issue is that the publicly known "brands" only specify a primitive and not the whole thing. This is bad for implementers who are forced into a choice they aren't qualified to make, and it's bad for users who see AES256 or something and think they are safe, not realizing that it's used with an unsafe mode.

You don't need to understand it that much. I don't get ECC entirely but I'd implement Ed25519 straight from the RFC any day over implementing RSA from anything else.

This article sticks out in my memory as my go-to guide on the subject: https://blog.trailofbits.com/2019/07/08/fuck-rsa/

RSA is pretty easy to implement, but hard to get right, PKCS#1v1.5 can be broken using padding attacks, and should not be used. OAEP is generally recommended.

The entire RSA suite (keygen, encrypt/decrypt, padding) can be implemented in about 300 loc[1]. Which is probably why there are so many of these 'walkthroughs'.

[1]: https://github.com/i404788/tiny-rsa

Very few systems in the real world implement OAEP, and even with OAEP you have to watch out for Manger's padding oracle attack (susceptibility to which may be commented out of the Javascript RSA you've posted here --- I'm like 50/50 on this because I've never taken the time to implement Manger because I've never been professionally asked to look at an OAEP implementation because, again, OAEP is pretty rare --- at this point, if you're designing a modern system, you're not using RSA.)

Well, TLS 1.2 still mandates PKCS 1.5:

"The RSAES-OAEP encryption scheme defined in [PKCS1] is more secure against the Bleichenbacher attack. However, for maximal compatibility with earlier versions of TLS, this specification uses the RSAES-PKCS1-v1_5 scheme." [RFC 5246, 7.4.7.1]

Reply on news.ycombinator.com