Hacker News Reader

Comment by klabb3 | Hacker News Reader

I’m not a cryptographer, but I can see many more pressing reasons for migrating off RSA before 2030. Is there any reason to pick RSA for greenfield today?

RSA, to my knowledge, is vulnerable to side channels and poor parameter choices. Implementation simplicity is an underrated security parameter. The fewer feet you have, the fewer of them you can shoot.

The NSA data centers don’t want to waste time on your RSA key anyway, much less your run-of-the-mill Russian black hat groups. What bites us in practice are 0-days of something stupid like heartbleed or rowhammer that can be automated, and takes a long time to patch.

View on HN

This is my (applied) cryptographic understanding as well: RSA 2048 probably won't be broken by improvements to prime factorization by 2030, but will continue to be a pointlessly dangerous (and slow) cryptosystem when compared to ECC.

I'm not convinced on the first part. That it won't be broken by improvements to prime factorization.

https://www.ams.org/notices/199612/pomerance.pdf has a great writeup on the history of the work around this. Essentially when you see improvements in complexity of the form

Old best: Quadratic Sieve: exp(c(log n)^1/2(log log n)^1/2)

New best: General Number field sieve: exp(c(log n)^1/3(log log n)^2/3)

I can't help but feel that's an exponent there that we've moved to 1/3 that could be moved further. Sure we don't know how and we've been stuck here on the current best for just over 25 years but i just feel that if you give me two methods and one moves a term like that there's a good chance there's a way to reduce that term further. It'd be weird for that complexity statement to stay as is. That's telling me "the universe doesn't allow factorization any faster than a term that's raised to a power of 1/3rd" and i'm asking "why is 1/3 so special?". So i'm not convinced that there's not more here. I don't have a clue how of course. But the history of RSA going "256bits is secure" to 512bits to 1024bits to 2048bits being needed has me worried about the safety of prime factorization.

Top reason to use RSA for me, as with most tech I use, is its longevity.

Lindy Effect has been the best predictor of what will still work in five years.

The fact that the sun rose today, has no effect on whether the sun will rise tomorrow.

And yet I doubt you would be willing to bet against the sun rising tomorrow.

Our understanding is based on imperfect models, sure. That doesn't matter most of the time. It wouldn't matter in this bet.

So much of what any lifeform does is based on past experience, even though that experience isn't the direct driver of future effects. Turns out that bets based on experience work really well.

Of course I’d bet the sun would rise tomorrow, because if it doesn’t, I’m either dead or money will be worthless…

The same applies here, would you bet on a horse that is flagging (RSA won’t work forever)? We have the ability to take in new information, and throw away past information because it is no longer relevant. If you choose to ignore the new information, just because “it’s always been that way”, that doesn’t seem rational.

Indeed. The sun has successfully rose every morning, hundreds of billions of times straight! That's a pretty good record.

Do you have a proof of that?

I've been to places where the sun doesn't rise for months on end...

It does though. If it failed to rise today due to some cosmic anomaly, it would very likely fail to rise tomorrow.

When you die, from your perspective, the sun doesn't rise. It doesn't have to be a cosmic anomaly. For every single human, there are more days the sun doesn't rise than does.

The Lindy effect applies to non-perishables. There are alternatives which are much more likely to conform to a reasonable equivalency of non-perishable for cryptography. Per this article, RSA strongly does not fit reasonable equivalent definitions.

McEliece encryption algorithm was published in 1978 (one year later than RSA) and seems to be considered safe to classical and quantum computers, the only downside is the huge public key size.

If you accept the current assumption of double exponential growth for both computing performance and algorithmic efficiency then you would have to accept that 256 bit elliptic curve keys will become obsolete in the 2040s. So it might be just RSA and discrete logs today but a requirement for pointlessly long EC keys will be along soon.

Yeah but does it matter? Either that’s true or it isn’t. If it is true, we’ll (as usual) have ample time to migrate. With RSA though, it’s already today more complex, slower and about 8x larger key sizes. And the cryptanalysis track record is afaik (please correct me) much more successful than ECC, so it’s “higher risk” that the timeline gets pushed forward or that new patches are needed to avoid bad parameter choices.

> So it might be just RSA and discrete logs today but a requirement for pointlessly long EC keys will be along soon.

It wouldn’t be pointless if computers can crack those sizes. It’d only be pointless if cryptanalysis can exploit structure to reduce the effective entropy, no?

>Implementation simplicity is an underrated security parameter.

Sure, if we were implementing cryptographic algorithms from scratch that would be a proper strong consideration. However, 99% of programmers should just link to an established library/framework and use its cryptographic implementation. These established libraries already paid the price of implementation, and are very battle-tested. There's therefore very good reason to believe their RSA implementation is secure.

Choosing an algorithm should be done on other considerations then. A lower keysize would point to ECC. But maybe we don't want a single algorithm for all encryption - a mixed global ecosystem with RSA and ECC projects would be more robust.

> These established libraries already paid the price of implementation, and are very battle-tested.

Yes absolutely. I’m not saying users should pick the one that’s easier to implement.

Simplicity is good for implementers. It allows for more participants, eg std libs to provide their own. Also, even the security geeks are humans and make mistakes. Heartbleed is a perfect example of where even simple things can go catastrophically wrong.

As a second order effect, users benefit from simplicity in the long run, because less complex systems have fewer bugs, and thus fewer security bugs.

> These established libraries already paid the price of implementation, and are very battle-tested. There's therefore very good reason to believe their RSA implementation is secure.

Many of these established libraries have fallen in battle, some several times. There's always a new up and coming library that works on platform X, in language Y, or has a better license Z, or is integrated into an init system, and while some of them learn from the experience of others, many learn by making the same mistakes others did.

Pushing towards simpler constructions gives hope that those new implementations make fewer mistakes.

To be frank, "RSA is so impossibly complicated that nobody ever could implement it" is just spreading FUD. It's not so complicated an expert* couldn't do it, the code is small to review, it's been done, and safe implementations are well-known. If you decide to use a new up and coming library the risk is on you whatever algorithm you choose. Sure, go to ECC if you want, but there's no good reason to especially doubt the security of existing RSA implementation.

* The only type of person who should be writing a cryptographic implementation in the first place.

Reply on news.ycombinator.com