Hacker News Reader

Comment by m-p-3 | Hacker News Reader

It means we're getting closer to break 1024-bit RSA, as they basically broke a 795-bit RSA modulus.

Most systems and applications currently uses at least 2048-bit keys and are still considered secure.

If someone still uses RSA under 2048-bit, I'd urge them to upgrade their keys or switch to Elliptic Curve if the application can handle it.

View on HN

I think there's a sort of general folk consensus among cryptographers that a state-level adversary that wanted to break 1024-bit RSA has already done so. Eran Tromer costed out a hardware-optimized break of RSA-1024 inside the budget of many tech companies, and that was over a decade ago.

It's worth keeping in mind that this isn't a linear progression. The thing that breaks RSA-2048 might very well break all of RSA; I certainly wouldn't flag anyone for using it instead of 4096-bit RSA.

It's worth keeping in mind that this isn't a linear progression

An additional small detail that makes it somewhat more confusing than it should be is that some challenge numbers (like this one, RSA-240) have the decimal, rather than binary size in their name.

A 1024-bit break seems like the kind of thing Google would do to show off, like they have with a few other projects. Kind of surprised we haven't seen something along those lines.

The cost-effective ways to do it might require making custom hardware from which Google couldn't derive any other benefit, and perhaps from which it wouldn't even derive very much insight that was useful to its business.

The hyperscalers all have lots of idle compute, I'm not sure how many cores they have, but I believe the big three cloud services operate on the order of millions of servers, most of which have tens of cores now. If a 1024 bit key is proportionally more complex to solve, it seems they could solve it with idle compute.

I don't think any of them would want the negative publicity that could arise.

Surely it's at least a different power bill on modern hardware depending on what the hardware is computing, right?

Unless I'm dumb, the 2.25 increased hardness from 768 bits to 795 bits would suggest a 2.25^(1/(795 - 768)) hardness increase per bit. That is roughly 1.0305. Taking 1.0305^(1024-795) yields something like a 970-fold increase.

A thousandfold increase is in the right range.

But this factorization only took a thousand core years.

Millions of servers averaging one donated core each can hit a thousand thousand core years in a few weeks.

Google doesn't have any truly idle compute.

They can turn off their unused computing power to save on electricity. And they have internal tasks that they can throw arbitrary left over computing power at to get slight benefits. (Don't remember how much I am allowed to say about those. But it includes the kind of tasks you can come up with after brainstorming for about two minutes.)

So breaking 1024-bit RSA would need to compete with those uses, not with true idling.

I take it as a... hmm, not a lie of omission, but more, like, an omission of "trust us"? Not really sure what words would be best suited to describe this.

It sounds line the kind of thing that would generate only negative publicity

Google did such a thing with the SHA-1 collission. However RSA-1024 is still challenging even with a Google budget. Maybe they could do it, but likely it's still outside the "we'd do it just to proove a point" range.

Also notably the SHA-1 thing was done in a time where SHA-1 was still widely used and Google engineers were part of discussions about SHA-1 deprecation. RSA-1024 is basically dead already.

This paper basically says the NSA is doing it[1]. They estimate the price of hardware, and correlate it with the NSA's budget and capabilities listed in slides Edward Snowden leaked.

[1] https://weakdh.org/imperfect-forward-secrecy.pdf

It's largely talking about fixed DH groups rather than RSA.

It supposes that the NSA might plausibly break the handful of fixed groups because this would let them passively read the master keys (and thus all the data) for all traffic using these DH groups, which at the time they wrote that was a sizeable fraction of all IPSec and HTTPS traffic (for HTTPS the paper shows the fraction affected passively and the larger fraction that could be coerced by an active attacker with the risk of detection, the NSA's policy objectives mean it prefers not to risk being detected).

In contrast with RSA keys each user will have their own key and might rotate it periodically. If you spent just $1M to break my RSA key and then I replace every 60 days, you're now spending $6M per year _just on attacking me_ and typical estimates are _far_ higher than $1M and you need to do this fast, if you amortize discovery so that you take 100 days to recover new keys you can only begin to read things on average 70 days after they are sent.

For the web, which this paper is especially concerned with, 1024-bit RSA isn't a thing any more, and even if it was RSA key agreement also isn't a thing any more. So the NSA has much less to gain from an attack on RSA (even if it was still 1024-bit) than DHE.

a 1024-bit RSA number is ~5000 times harder (each additional 5.5 digits doubles the difficulty[1])

[1] https://www.mersenneforum.org/showpost.php?p=531861&postcoun...

Maybe I am missing something.

2^((1024 - 795)/5.5) = 3.4e12

Isn't that over 3.4 trillion times harder?

I believe the "digits" above refers to decimal digits, not binary digits. RSA-240 has 240 decimal digits. A 1024-bit number should have 309 digits. So:

2^((309 - 240) / 5.5) = 5978

Reply on news.ycombinator.com