RSA-260 Factorized
twitter.com
twitter.com
For reference, check this out:
> cuda-sieve is an experimental, standalone CUDA implementation of the lattice-sieving relation-collection pipeline used by the Number Field Sieve. It builds factor bases, sieves both sides of a special-q lattice, performs trial division and GPU cofactorisation, and emits relations for msieve.
Background: https://en.wikipedia.org/wiki/RSA_Factoring_Challenge
And how come much larger numbers have already been solved? Based on that information one cannot strictly assume that the current solution required improvements to the strategy or hardware, no?
Like, it really looked like everything was going to fall apart. We all rushed to 1024 bit keys, and then to 2048 bit after what felt like a few months. And... maybe even that wouldn't be enough?
And actual history ended up being the boring version: it was absolutely enough, factorization is seemingly settled math at this point, no new techniques have been discovered.
At the end of the day RSA was just fine and no one really needed to bother with ECC and all of its confusing tutorials.
And the ~23 year old 1024 bit key holding my GnuPG box closed is still just fine, cryptographically. (Though the chances of getting hit with a keylogger or other side channel attack over that period are nontrivially high and I suppose I really should rotate it or something).
We don't know yet how much work OP put into factoring the RSA-260 challenge. No doubt it was a lot, but probably done with general purpose GPU hardware. That will continue to get cheaper to mount in the near future, and we ought to assume that nation states have access to RSA factoring hardware that would be multiple orders of magnitude more efficient.
It is quite likely that there are at least two actors (US and China) that can break RSA-1024, and they are no doubt working through a priority list of all accessible servers with such weak keys. If your firewall is not broken & now back-doored, it is only because you're not important enough to have gotten to yet.
RSA-2048 (or better, RSA-3072) is usually a drop-in replacement. ECC would be even better. There is no reason not to.
And from that perspective RSA-1024 is still perfectly adequate
"But they're not going to spend resources breaking my router!" No, not your router specifically. But batch GCD gives sqrt speedup over multiple keys, potentially 10's to 100's of millions of keys at once with off-the-shelf GPU clusters at NSA scale. Looking at that many keys at once tends to discover low-entropy biases common in consumer router hardware, which makes brute-forcing new keys from those devices trivial to do.
If you are actually operating a service relying on RSA-1024 security, it is almost certainly pwoned.
If you're running something with code from a large US corporation, or outsourced to contractors, or made in China, or with a web interface, or [3 more pages of stuff] and your main worry is the size of your RSA keys, then I've got a Fortigate security appliance to sell you.
Compared to elliptic curves, it is comically easy to build an RSA implementation which is catastrophically broken. Both the number of and subtlety of footguns in RSA are extreme.
Even ignoring that, ECC is far more efficient (in part thanks to smaller key sizes and being able to be done with fixed-width arithmetic rather than needing bignums) and far better suited for embedded devices. Migration has been an enormous win even if you think the security of RSA is fine.
There are no consumer CPUs that have 2048-bit-wide registers; even AVX10 tops out at 512 bits. Thus, mathematical operations on RSA keys are performed using arbitrary precision integer libraries like OpenSSL's own BN (BigNum) library, or GMP (the GNU Multiple Precision Arithmetic Library) as used by GNUTLS, in software.
For example, adding 1 to an arbitrary precision integer is not a CPU add or increment instruction, nor is multiplying 2 integers (or an integer and a constant factor) a CPU multiplication instruction.
Yeah, you don't need variable width, you just need a kind of register that basically doesn't exist.
So oddly enough the supposedly really bad insecure terrible etc PKCS #1 RSA is the only one where the signature is totally unambiguous.
ECC is definitely more efficient though.
Then again, we're all supposed to switch to post-quantum.
Depends on what your goal is and if you like more footguns.
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.
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.
"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.
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.
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.
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.
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?
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.
A "perfect" or "indefinitely stable" qubit sounds impossible. But so would a DRAM cell to an electrical engineer in the 40's. A DRAM cell continuously refreshes to maintain state, and as a result a single bit in RAM can have a mean time to failure measured in geologic time. Likewise a quantum error correction algorithm with a sufficiently large factor, driven continuously, will maintain qubit state indefinitely.
2048 Bit RSA and the Year 2030 https://articles.59.ca/doku.php?id=em:20482030
I guess it could be updated to include this latest factoring result. Said result would not change the conclusion of the article.