Hacker News Reader

Comment by debatem1 | Hacker News Reader

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.

View on HN

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

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.

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

The English professor finished set 8 as well!

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.

Reply on news.ycombinator.com