5 ms·

Does any one here care to explain what impact this will have on modern crypto security systems?

by max_ 7y ago

deleted 7y ago
[deleted]
m-p-3 7y ago
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.
- tptacek 7y ago
  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.
  - pvg 7y ago
    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.
  - bscphil 7y ago
    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.
    - schoen 7y ago
      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.
      - AaronFriel 7y ago
        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.
        schoen 7y ago
        Surely it's at least a different power bill on modern hardware depending on what the hardware is computing, right?
        estomagordo 7y ago
        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.
        Dylan16807 7y ago
        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.
        eru 7y ago
        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.
  - Thorrez 7y ago
    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 https://weakdh.org/imperfect-forward-secrecy.pdf
    - tialaramex 7y ago
      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.
- SethTro 7y ago
  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&postcount=2 https://www.mersenneforum.org/showpost.php?p=531861&postcoun...
  - waynecochran 7y ago
    Maybe I am missing something. 2^((1024 - 795)/5.5) = 3.4e12 Isn't that over 3.4 trillion times harder?
    - abbeyj 7y ago
      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
namirez 7y ago
They have factorized another challenge number [1]. It doesn't have any surprising impact. As computational power grows, it becomes easier and easier to factorize semi-primes (ignoring quantum computers). So either we have to use larger semi-primes in RSA, or use a different kind of algorithm like elliptic curves. [1] https://en.wikipedia.org/wiki/RSA_numbers https://en.wikipedia.org/wiki/RSA_numbers
ljhsiung 7y ago
Zero. If you're using anything with 800-bit security, you're probably a time traveler from the 90s. The more fun academic contribution to this is they found a faster sieve, here http://cado-nfs.gforge.inria.fr http://cado-nfs.gforge.inria.fr. It's very neat stuff, I think they claim 30% less CPU years using the identical hardware to crack RSA-768, when applying this same software to RSA-768. As with the original list, it's just unsolved problems that may help reveal more and more efficient ways to find/generate primes.
- DuskStar 7y ago
  > I think they claim 30% less CPU years using the identical hardware to crack RSA-768, when applying this same software to RSA-768. Are you sure? My reading was "in 70% of the the time it took to crack RSA-768, using their hardware, we cracked RSA-240" - this would match up relatively well with the fact that the expected difficulty increase was x2.25 and then they say "Taking this into account, and still using identical hardware, our computation was 3 times faster than the expected time that would have been extrapolated from previous records." Collaborating this, the previous record took ~4000+1500+900+200=6600 core years and the current one 4000. The Xeon Gold 6130 used has a single thread passmark of 1754 while the Xeon E5-2660 used in the RSA-768 factorization scored 1471, from [0]. Normalizing for passmark, the new RSA-240 factorization took 72.3% as much compute as the RSA-768 factorization. I would not be at all surprised if their software saw smaller gains through the generations than Passmark did, and it wouldn't take much to bring 72.3% to 70%. 0: https://www.cpubenchmark.net/compare/Intel-Xeon-Gold-6130-vs-Intel-Xeon-E5-2660/3126vs1219 https://www.cpubenchmark.net/compare/Intel-Xeon-Gold-6130-vs...
  - SethTro 7y ago
    I agree, this was 3x faster than expected. Note: Factoring RSA-240 only took 900 core-years the additional 3100 core-years were on the discrete log. RSA 240 is 8 digits longer, it takes ~2x as much work for each 5.5 additional digits so this should have taken 2.7x as much compute.
    - deleted 7y ago
      [deleted]

Does any one here care to explain what impact this will have on modern crypto security systems?

by max_ 7y ago

Does any one here care to explain what impact this will have on modern crypto security systems?

deleted 7y ago

[deleted]

m-p-3 7y ago

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.

tptacek 7y ago
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.
- pvg 7y ago
  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.
- bscphil 7y ago
  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.
  - schoen 7y ago
    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.
    - AaronFriel 7y ago
      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.
      - schoen 7y ago
        Surely it's at least a different power bill on modern hardware depending on what the hardware is computing, right?
      - estomagordo 7y ago
        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.
        Dylan16807 7y ago
        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.
      - eru 7y ago
        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.
- Thorrez 7y ago
  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 https://weakdh.org/imperfect-forward-secrecy.pdf
  - tialaramex 7y ago
    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.
SethTro 7y ago
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&postcount=2 https://www.mersenneforum.org/showpost.php?p=531861&postcoun...
- waynecochran 7y ago
  Maybe I am missing something. 2^((1024 - 795)/5.5) = 3.4e12 Isn't that over 3.4 trillion times harder?
  - abbeyj 7y ago
    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

namirez 7y ago

They have factorized another challenge number [1]. It doesn't have any surprising impact. As computational power grows, it becomes easier and easier to factorize semi-primes (ignoring quantum computers). So either we have to use larger semi-primes in RSA, or use a different kind of algorithm like elliptic curves. [1] https://en.wikipedia.org/wiki/RSA_numbers https://en.wikipedia.org/wiki/RSA_numbers

ljhsiung 7y ago

Zero. If you're using anything with 800-bit security, you're probably a time traveler from the 90s. The more fun academic contribution to this is they found a faster sieve, here http://cado-nfs.gforge.inria.fr http://cado-nfs.gforge.inria.fr. It's very neat stuff, I think they claim 30% less CPU years using the identical hardware to crack RSA-768, when applying this same software to RSA-768. As with the original list, it's just unsolved problems that may help reveal more and more efficient ways to find/generate primes.

DuskStar 7y ago
> I think they claim 30% less CPU years using the identical hardware to crack RSA-768, when applying this same software to RSA-768. Are you sure? My reading was "in 70% of the the time it took to crack RSA-768, using their hardware, we cracked RSA-240" - this would match up relatively well with the fact that the expected difficulty increase was x2.25 and then they say "Taking this into account, and still using identical hardware, our computation was 3 times faster than the expected time that would have been extrapolated from previous records." Collaborating this, the previous record took ~4000+1500+900+200=6600 core years and the current one 4000. The Xeon Gold 6130 used has a single thread passmark of 1754 while the Xeon E5-2660 used in the RSA-768 factorization scored 1471, from [0]. Normalizing for passmark, the new RSA-240 factorization took 72.3% as much compute as the RSA-768 factorization. I would not be at all surprised if their software saw smaller gains through the generations than Passmark did, and it wouldn't take much to bring 72.3% to 70%. 0: https://www.cpubenchmark.net/compare/Intel-Xeon-Gold-6130-vs-Intel-Xeon-E5-2660/3126vs1219 https://www.cpubenchmark.net/compare/Intel-Xeon-Gold-6130-vs...
- SethTro 7y ago
  I agree, this was 3x faster than expected. Note: Factoring RSA-240 only took 900 core-years the additional 3100 core-years were on the discrete log. RSA 240 is 8 digits longer, it takes ~2x as much work for each 5.5 additional digits so this should have taken 2.7x as much compute.
  - deleted 7y ago
    [deleted]