HN Theater @HNTheaterMonth

Relevant "Fuck RSA", or why you don't want to use this in the real world.

https://youtu.be/lElHzac8DDI

(That being said, I think it's still interesting to do this to understand RSA, but please don't roll out your own crypto).

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

⬐ debatem1

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.

⬐ mehrdadn

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

⬐ debatem1

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.

⬐ mehrdadn

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.

⬐ tptacek

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

⬐ mehrdadn

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.

⬐ tptacek

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.

⬐ sdevlin

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

The English professor finished set 8 as well!

⬐ some_furry

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.

⬐ tptacek

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

⬐ some_furry

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.

⬐ im3w1l

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.

⬐ tptacek

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.

⬐ zaarn

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.

⬐ nullc

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

⬐ debatem1

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.

⬐ tptacek

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.

⬐ Ar-Curunir

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

⬐ commandlinefan

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

⬐ wolf550e

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

⬐ jcims

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