Comment by mswphd | Hacker News Reader

Comment by mswphd | Hacker News Reader

Parent Full thread

the researchers from the RSA-250 record have publicly claimed that factoring 1024-bit RSA keys is within reach of nation states. Your 1024 bit key is only "fine" because you are a small fry, not because cryptographers think it cannot be attacked. This would be true if you used a (non-standard) RSA-768 parameterization as well, which is easier than what we are talking about on this post.

It's also worth mentioning the main concern for RSA is not GNFS, but something stronger. SOTA RSA attacks (such as GNFS) use "index calculus". You can also use index calculus to attack finite field diffie hellman. In the 2010's, there was remarkable progress in index calculus attacks against finite field DH in the small characteristic case. For example, the current record for binary characteristic finite field DH is ~30k bits (and this is by an academic --- a nation state could definitely do more).

It is not known that similar progress is possible in other cases (such as for RSA). But it's very much possible that factoring is much easier than expected. Simultaneously I wouldn't personally bet money on it, and if that breakthrough happened, there were sufficient warning signs that I would feel justified in saying "told you so" to people trusting RSA.

It's not just because the GPG user is small fry that 1024 bit RSA is low risk for them. It is mostly because there is only one of them. A nation state attacker would have to spend billions of dollars and years of lost opportunity to use their resource more effectively to get the messages/files of a single person. There are much cheaper and faster ways to accomplish the same thing.

If, say, Gmail was using some static 1024 bit RSA based scheme things would be different. Then an attacker would get the messages of billions of users.

> Your 1024 bit key is only "fine" because you are a small fry, not because cryptographers think it cannot be attacked.

This is falling for an xkcd 538 fallacy, btw. Nation states obviously have vast higher capability to subvert individual data than brute forcing its crypto. I stand by what I said: 1024-bit RSA keys are "fine" and will remain so. RSA-309 will not fall within our lifetime.

> it's very much possible that factoring is much easier than expected

And this is sort of toothless? I mean, that's true for ECC too. It's true for all cryptography. It's true for all software. For all engineering. For all math. We'll never know what we don't know. New discoveries tomorrow may upend everything any given property ("safety" is just one) we think our existing machines hold.

But they probably won't. And the moments where that happens are extremely rare. And to be blunt RSA already got hit with that particular lightning bolt.

That's a weirdly confident prediction. Why do you think 309 isn't going to fall in our lifetimes?

"SHA2 will never be broken in our lifetimes" is something I've heard JP Aumasson say many times, but that's based on the fact that there's no line of sight anywhere to techniques that could break it. But you can't say that about 1024 bit RSA.

Everyone wants to argue crypto when my point was precisely the opposite (to wit: "Two decades after the factoring freakout, RSA is fine, go figure"), but whatever. I'll retract that when they break it. But the pace has been slowing down, not speeding up. Getting from RSA-250 to -260 was six years. That's not going to get us there before I kick it, at least.

If you want to pin me down on something slightly more formal: DRAM density scaling kinda stopped a few years back, systems aren't getting any bigger (much to Sam Altman's public dismay), and there is a superlinear matrix size requirement in factorization techniques that AFAIK no one knows how to fix. We can get the cycles to do it, but not the space.

Probably. Maybe not! But even so, it will remain cheaper to steal my secrets with the proverbial $5 wrench. RSA? It was fine.

The last few jumps between 2x0 were 3 years, 2 years, 1 year, 1 year, and 6 years.

I don't think you can extrapolate that into "slowing down". It wouldn't even be surprising if the next five jumps averaged 2 years each and RSA-1024 was cracked in a decade.

I'm sure RAM is an issue but I don't expect it to be a hard wall.

honestly I wouldn't be shocked if 2048 bit rsa gets factored in our lifetime. GNFS doesn't have the feel of an optimal algorithm. dropping to L(1/4) would bring 1500 bits into reach, and it seems plausible still that factoring is polynomial.

any cryptography can break at any time. Sometimes "sudden" breaks happen. You can't defend against these, so there (perversely) isn't that much of a point worrying about them, besides using schemes many people have thought about for a while.

Another way cryptography breaks is via iterative improvements. For example, in the last few months there are two big cryptanalytic stories

1. The novel scheme (though not standardized) HAWK had its security reduced by ~1/2 by AI. It is no longer compelling in any way. This was in a sense "predictable" though. There was a series of papers showing that HAWK-like schemes were vulnerable to an attack of this type. Then, AI was able to bridge the gap and apply these attacks directly to HAWK.

2. The ISO-standardized scheme McCliece (from ~45 years ago) has had some alarming security reductions, and may be effectively broken (it's still a little early to tell, many cryptanalytic papers require heuristics that must be justified, etc). Again, this was in a sense "predictable". Starting ~3 years ago it was discovered that McCliece had some yet-unexploited structure, and since then there have been more and more papers exploiting this further, until recently more dramatic attacks have occurred.

In both cases, there is a clear "story" you can (post-hoc) tell about the attacks. You can't always predict precisely where the attacks will end up (for the McCliece attack, it appears more effective than I would have predicted at least). But you can often tell when things are gradually weakening, before a full collapse.

RSA has a cousin (binary characteristic finite field DH) that had this gradual weakening into total collapse happen in the 2010s. It is possible this cousin was a problem child, and GNFS will remain the best attack against RSA until quantum computers fully break it. I can't predict the future. But I can say that ECC has had no such problematic cousins.

This is to say that we are blessed that we have extremely strong cryptography available. Why you would choose to use the weakest defensible option is beyond me, and not something anyone serious about security would ever recommend doing. There is no upside, and only downsides.

> Why you would choose to use the weakest defensible option

I still remain confused why people are interpreting this from what I wrote. I'm not "choosing" to use RSA nor advocating for its use. I'm pointing out anecdotally that I have a GnuPG keychain still live with a 1024 bit key from the last millenium (or close to that, honestly I don't know for sure) that everyone was *sure*, 20 years ago, was broken and insecure. And... it wasn't. It's fine.

The xkcd point seems profound to me: the crypto nerds were entirely wrong about their focus and sense of urgency here. Today, it's much cheaper to steal my key with simple violence. It will remain so when I'm on my death bed. Probably when my heirs are too. And I find that interesting. What else are we nerds getting wrong?

There's also the question of why anyone would bother. You can factor RSA-1024 today in about a year with a national-lab-level supercomputer. Which 1k-bit RSA key would you shut down a national lab for a year for to factor? Heck, which key would you shut it down for a week for to factor? There's no single key out there of any interest when you can just spear-phish your intended target, or get RCE on their unpatched router, or get the cleaners to plug in a USB key and let it do its thing while they're vaccuuming, or whatever.

Reply on news.ycombinator.com