9 ms·

1024 is still many orders of magnitude hard to crack than 512. For the record, the last RSA number having been broken was RSA-250 (829 bits) and it took 2700 co

1024 is still many orders of magnitude hard to crack than 512. For the record, the last RSA number having been broken was RSA-250 (829 bits) and it took 2700 core-years to crack back in 2020[1]. In comparison, RSA-155 (512 bits) was factorized as early as 1999! You aren't in danger. [1]: https://sympa.inria.fr/sympa/arc/cado-nfs/2020-02/msg00001.html https://sympa.inria.fr/sympa/arc/cado-nfs/2020-02/msg00001.h...

DarkmSparks 2y ago
There are several open source GNFS tools that can do 1024 very efficiently on GPUs, and even cheap consumer GPUs have 10s of thousands of cores now, even by your measure "2700 core-years" is only around a month or so on a single consumer grade GPU. Not "free", but any malicious actor has access to a lot more than a single GPU. The UK government also has several huge arm based solutions dedicated to cracking internet encryption, zero chance that isn't breaking mostly everything, for sure the Chinese and Russians have similar.
- SahAssar 2y ago
  > The UK government also has several huge arm based solutions dedicated to cracking internet encryption, zero chance that isn't breaking mostly everything, for sure the Chinese and Russians have similar. So you seriously think that almost all current RSA is being decrypted in real time by at least UK, China and Russia (and I would assume US)? Do you have any source or reference for this at all?
- upofadown 2y ago
  >There are several open source GNFS tools that can do 1024 very efficiently on GPUs, ... Reference? Why has no one demonstrated this?
- littlestymaar 2y ago
  Yet nobody is collecting the RSA-numbers bounties? RSA-270 (much, much easier than 1024 compute-wise) has a bounty of $75k, why would it be unclaimed then when you can spend three years worth of cloud rented H100 (I'm being conservative here and count $3/h which is far from the best deal you can get) and still make a profit? Also a GPU core and CPU cores really aren't comparable individually, so your “consumer graphic card having thousands of core already” is comparing apples to oranges.
  - DarkmSparks 2y ago
    had a bounty. the RSA challenge unexpectly finished in 2007, task is left to the reader to speculate what happened in 2007.
    - littlestymaar 2y ago
      Oh, I wasn't aware of the end of the challenge. But 1024 was definitely not broken by then, at least not by brute force.
      - DarkmSparks 2y ago
        none of it is "brute force", GNFS is a process that rapidly excludes numbers from the search space that cannot be the answer, in principle similar to the way they broke enigma. numberphile has a great video on that one https://www.youtube.com/watch?v=V4V2bpZlqx8 https://www.youtube.com/watch?v=V4V2bpZlqx8 Also, taking the OP as a "worse case", afaik: 512bit = $8 so 1024 = 8^2 = $64 2048 = 8^2^2 = $4,096 4096 = 8^2^2 = $16,777,216 noting $8 for 512 seems very expensive to me.
        deleted 2y ago
        [deleted]
        btdmaster 2y ago
        That's not correct. Consider, for example, a processor that can handle 2^31 computations per second. 2^32 operations can be computed in 2 time units, whereas 2^64 operations will take 2^33 time units. search_space(n: number_of_bits) = 2^n * k so search_space(1024)/search_space(512)=2^512, not 2^2. Asymptotics in GNFS are better[0], but only on the order of e^(cbrt(512 * 64/9)) times more work, not 2^2. This would give an approximation of math.exp(math.cbrt(512 * 64/9))*$8 = $40 million for 1024 bits. [0] https://en.wikipedia.org/wiki/General_number_field_sieve https://en.wikipedia.org/wiki/General_number_field_sieve
        DarkmSparks 2y ago
deleted 2y ago
[deleted]
daneel_w 2y ago
You and I aren't the ones in immediate danger. The service providers we rely on are. In discussions like these we have a "tragicomic" tendency to forget mankind's unstoppable progress. RSA-1024 offers 80 symmetric equivalent bits of security and we've been heading down this path for decades at an exponentially increasing pace.
- littlestymaar 2y ago
  Those service providers have had plenty of time to migrate to 2048 and most of them have already. > a "tragicomic" tendency to forget mankind's unstoppable progress When it comes to compute, it's no faster than Moore's Law, which means roughly one bit of symmetric encryption every two years. > and we've been heading down this path for decades at an exponentially increasing pace. Given that the encryption security is itself exponential in bit length, we are in fact heading down this path linearly! (A doubling in compute power means the ability to crack twice as hard cryptosystems, which means ones that have 1 bit more of security). Key must be extended over time, and they are, and have been for decades. A PoC of an attack of a security system broken since 1999 should be treated exactly like how we are amazed at little computing power was available to the Apollo program: this is a cool bit of trivia that shows the growth of available computing power, but not a display of any kind of security issue.

DarkmSparks 2y ago

There are several open source GNFS tools that can do 1024 very efficiently on GPUs, and even cheap consumer GPUs have 10s of thousands of cores now, even by your measure "2700 core-years" is only around a month or so on a single consumer grade GPU. Not "free", but any malicious actor has access to a lot more than a single GPU. The UK government also has several huge arm based solutions dedicated to cracking internet encryption, zero chance that isn't breaking mostly everything, for sure the Chinese and Russians have similar.

SahAssar 2y ago
> The UK government also has several huge arm based solutions dedicated to cracking internet encryption, zero chance that isn't breaking mostly everything, for sure the Chinese and Russians have similar. So you seriously think that almost all current RSA is being decrypted in real time by at least UK, China and Russia (and I would assume US)? Do you have any source or reference for this at all?
upofadown 2y ago
>There are several open source GNFS tools that can do 1024 very efficiently on GPUs, ... Reference? Why has no one demonstrated this?
littlestymaar 2y ago
Yet nobody is collecting the RSA-numbers bounties? RSA-270 (much, much easier than 1024 compute-wise) has a bounty of $75k, why would it be unclaimed then when you can spend three years worth of cloud rented H100 (I'm being conservative here and count $3/h which is far from the best deal you can get) and still make a profit? Also a GPU core and CPU cores really aren't comparable individually, so your “consumer graphic card having thousands of core already” is comparing apples to oranges.
- DarkmSparks 2y ago
  had a bounty. the RSA challenge unexpectly finished in 2007, task is left to the reader to speculate what happened in 2007.
  - littlestymaar 2y ago
    Oh, I wasn't aware of the end of the challenge. But 1024 was definitely not broken by then, at least not by brute force.
    - DarkmSparks 2y ago
      none of it is "brute force", GNFS is a process that rapidly excludes numbers from the search space that cannot be the answer, in principle similar to the way they broke enigma. numberphile has a great video on that one https://www.youtube.com/watch?v=V4V2bpZlqx8 https://www.youtube.com/watch?v=V4V2bpZlqx8 Also, taking the OP as a "worse case", afaik: 512bit = $8 so 1024 = 8^2 = $64 2048 = 8^2^2 = $4,096 4096 = 8^2^2 = $16,777,216 noting $8 for 512 seems very expensive to me.
      - deleted 2y ago
        [deleted]
      - btdmaster 2y ago
        That's not correct. Consider, for example, a processor that can handle 2^31 computations per second. 2^32 operations can be computed in 2 time units, whereas 2^64 operations will take 2^33 time units. search_space(n: number_of_bits) = 2^n * k so search_space(1024)/search_space(512)=2^512, not 2^2. Asymptotics in GNFS are better[0], but only on the order of e^(cbrt(512 * 64/9)) times more work, not 2^2. This would give an approximation of math.exp(math.cbrt(512 * 64/9))*$8 = $40 million for 1024 bits. [0] https://en.wikipedia.org/wiki/General_number_field_sieve https://en.wikipedia.org/wiki/General_number_field_sieve
        DarkmSparks 2y ago

deleted 2y ago

[deleted]

daneel_w 2y ago

You and I aren't the ones in immediate danger. The service providers we rely on are. In discussions like these we have a "tragicomic" tendency to forget mankind's unstoppable progress. RSA-1024 offers 80 symmetric equivalent bits of security and we've been heading down this path for decades at an exponentially increasing pace.

littlestymaar 2y ago
Those service providers have had plenty of time to migrate to 2048 and most of them have already. > a "tragicomic" tendency to forget mankind's unstoppable progress When it comes to compute, it's no faster than Moore's Law, which means roughly one bit of symmetric encryption every two years. > and we've been heading down this path for decades at an exponentially increasing pace. Given that the encryption security is itself exponential in bit length, we are in fact heading down this path linearly! (A doubling in compute power means the ability to crack twice as hard cryptosystems, which means ones that have 1 bit more of security). Key must be extended over time, and they are, and have been for decades. A PoC of an attack of a security system broken since 1999 should be treated exactly like how we are amazed at little computing power was available to the Apollo program: this is a cool bit of trivia that shows the growth of available computing power, but not a display of any kind of security issue.