7 ms·

The Factorization of RSA-240

131 points by hsnewman 7y ago

crookshanked 7y ago
What is going on with the URL? Also this user submitted something along this RSA-240 factoring twice. Seems really phishy that they're using a .exe in the url.
- wahern 7y ago
  wa.exe is the web interface for LISTSERV on Windows: https://www.lsoft.com/manuals/16.0/htmlhelp/list%20subscribers/IntrototheWebInterface.html https://www.lsoft.com/manuals/16.0/htmlhelp/list%20subscribe... AFAICT this mailing-list post is the original public announcement, but perhaps the submitter followed up with the Schneier link in anticipation of concerns like yours.
  - crookshanked 7y ago
    Thanks for the explanation!
- deleted 7y ago
  [deleted]
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.
- 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]
6nf 7y ago
Wolfram Alpha won't do the multiplication for me. Google does it but I only get the 7 most significant digits. Any other online ways to check this? https://www.google.com/search?q=509435952285839914555051023580843714132648382024111473186660296521821206469746700620316443478873837606252372049619334517+*+244624208838318150567813139024002896653802092578931401452041221336558477095178155258218897735030590669041302045908071447 https://www.google.com/search?q=5094359522858399145550510235... EDIT: This one works: http://www.javascripter.net/math/calculators/100digitbigintcalculator.htm http://www.javascripter.net/math/calculators/100digitbigintc...
- vworldv 7y ago
  https://repl.it/repls/BeneficialSomberExtension https://repl.it/repls/BeneficialSomberExtension
- lokedhs 7y ago
  I will take the opportunity to promote Maxima, which is a very nice open source maths tool with a very long history (started in the 60's, and still being developed). It leverages the bignum support in Common Lisp, and has no problems handling numbers like these. http://maxima.sourceforge.net/ http://maxima.sourceforge.net/ https://wxmaxima-developers.github.io/wxmaxima/ https://wxmaxima-developers.github.io/wxmaxima/ You can use Maxima's built-in command "factor" on this number as well, although I guess you'll have to be very patient. I obviously also want to promote my own project, which is different UI on top of Maxima: https://flathub.org/apps/details/com.dhsdevelopments.Climaxima https://flathub.org/apps/details/com.dhsdevelopments.Climaxi...
  - kazinator 7y ago
    Bignums are there because of Macsyma (Maxima's ancestor)! "Bignums—arbitrary precision integer arithmetic—were added [to MacLisp] in 1970 or 1971 to meet the needs of Macsyma users." [https://www.dreamsongs.com/Files/HOPL2-Uncut.pdf https://www.dreamsongs.com/Files/HOPL2-Uncut.pdf, P. 10 bottom]
- AnotherGoodName 7y ago
  Python. It has unlimited precision out of the box. python >>>509435952285839914555051023580843714132648382024111473186660296521821206469746700620316443478873837606252372049619334517 * 244624208838318150567813139024002896653802092578931401452041221336558477095178155258218897735030590669041302045908071447 124620366781718784065835044608106590434820374651678805754818788883289666801188210855036039570272508747509864768438458621054865537970253930571891217684318286362846948405301614416430468066875699415246993185704183030512549594371372159029236099
bane 7y ago
Interesting, RSA-230 was factored a little more than 1 year ago.

131 points by hsnewman 7y ago

What is going on with the URL? Also this user submitted something along this RSA-240 factoring twice. Seems really phishy that they're using a .exe in the url.

wahern 7y ago
wa.exe is the web interface for LISTSERV on Windows: https://www.lsoft.com/manuals/16.0/htmlhelp/list%20subscribers/IntrototheWebInterface.html https://www.lsoft.com/manuals/16.0/htmlhelp/list%20subscribe... AFAICT this mailing-list post is the original public announcement, but perhaps the submitter followed up with the Schneier link in anticipation of concerns like yours.
- crookshanked 7y ago
  Thanks for the explanation!
deleted 7y ago
[deleted]

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

6nf 7y ago

Wolfram Alpha won't do the multiplication for me. Google does it but I only get the 7 most significant digits. Any other online ways to check this? https://www.google.com/search?q=509435952285839914555051023580843714132648382024111473186660296521821206469746700620316443478873837606252372049619334517+*+244624208838318150567813139024002896653802092578931401452041221336558477095178155258218897735030590669041302045908071447 https://www.google.com/search?q=5094359522858399145550510235... EDIT: This one works: http://www.javascripter.net/math/calculators/100digitbigintcalculator.htm http://www.javascripter.net/math/calculators/100digitbigintc...

vworldv 7y ago
https://repl.it/repls/BeneficialSomberExtension https://repl.it/repls/BeneficialSomberExtension
lokedhs 7y ago
I will take the opportunity to promote Maxima, which is a very nice open source maths tool with a very long history (started in the 60's, and still being developed). It leverages the bignum support in Common Lisp, and has no problems handling numbers like these. http://maxima.sourceforge.net/ http://maxima.sourceforge.net/ https://wxmaxima-developers.github.io/wxmaxima/ https://wxmaxima-developers.github.io/wxmaxima/ You can use Maxima's built-in command "factor" on this number as well, although I guess you'll have to be very patient. I obviously also want to promote my own project, which is different UI on top of Maxima: https://flathub.org/apps/details/com.dhsdevelopments.Climaxima https://flathub.org/apps/details/com.dhsdevelopments.Climaxi...
- kazinator 7y ago
  Bignums are there because of Macsyma (Maxima's ancestor)! "Bignums—arbitrary precision integer arithmetic—were added [to MacLisp] in 1970 or 1971 to meet the needs of Macsyma users." [https://www.dreamsongs.com/Files/HOPL2-Uncut.pdf https://www.dreamsongs.com/Files/HOPL2-Uncut.pdf, P. 10 bottom]
AnotherGoodName 7y ago
Python. It has unlimited precision out of the box. python >>>509435952285839914555051023580843714132648382024111473186660296521821206469746700620316443478873837606252372049619334517 * 244624208838318150567813139024002896653802092578931401452041221336558477095178155258218897735030590669041302045908071447 124620366781718784065835044608106590434820374651678805754818788883289666801188210855036039570272508747509864768438458621054865537970253930571891217684318286362846948405301614416430468066875699415246993185704183030512549594371372159029236099

bane 7y ago

Interesting, RSA-230 was factored a little more than 1 year ago.