4 ms·

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,

by klabb3 3y ago

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.

forgotmypw17 3y ago
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.
- withinboredom 3y ago
  The fact that the sun rose today, has no effect on whether the sun will rise tomorrow.
  - Strom 3y ago
    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.
    - withinboredom 3y ago
      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.
    - cbm-vic-20 3y ago
      Indeed. The sun has successfully rose every morning, hundreds of billions of times straight! That's a pretty good record.
      - withinboredom 3y ago
        Do you have a proof of that? I've been to places where the sun doesn't rise for months on end...
  - sn0wf1re 3y ago
    It does though. If it failed to rise today due to some cosmic anomaly, it would very likely fail to rise tomorrow.
    - withinboredom 3y ago
      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.
- raggi 3y ago
  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.
- HappyPanacea 3y ago
  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.
upofadown 3y ago
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.
- klabb3 3y ago
  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?
woodruffw 3y ago
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.
- AnotherGoodName 3y ago
  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 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.
yyyk 3y ago
>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.
- klabb3 3y ago
  > 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.
- toast0 3y ago
  > 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.
  - yyyk 3y ago
    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.

by klabb3 3y ago

forgotmypw17 3y ago

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.

withinboredom 3y ago
The fact that the sun rose today, has no effect on whether the sun will rise tomorrow.
- Strom 3y ago
  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.
  - withinboredom 3y ago
    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.
  - cbm-vic-20 3y ago
    Indeed. The sun has successfully rose every morning, hundreds of billions of times straight! That's a pretty good record.
    - withinboredom 3y ago
      Do you have a proof of that? I've been to places where the sun doesn't rise for months on end...
- sn0wf1re 3y ago
  It does though. If it failed to rise today due to some cosmic anomaly, it would very likely fail to rise tomorrow.
  - withinboredom 3y ago
    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.
raggi 3y ago
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.
HappyPanacea 3y ago
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.

upofadown 3y ago

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.

klabb3 3y ago
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?

woodruffw 3y ago

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.

AnotherGoodName 3y ago
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 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.

yyyk 3y ago

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

klabb3 3y ago
> 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.
toast0 3y ago
> 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.
- yyyk 3y ago
  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.