I've factored the RSA keys of a Certificate Authority from the 90s
mcpherrin.ca250 points by ahlCVA 6 hours ago
250 points by ahlCVA 6 hours ago
A bit unfortunate that so many of the interesting bits were left to ai. I would've enjoyed some commentary on why the custom TLS implementation was necessary. Oh well.
Update: found this explanation in a comment at the top of the (surprisingly short) Go file in the linked repo:
The target client is Netscape Communicator 4.51 (both the 40-bit export build and the 128-bit US build) with its clock set to the year 2000.
Go's crypto/tls cannot help: it dropped SSLv3 in Go 1.14, never accepted the SSLv2-compatible ClientHello that Netscape 4 sends, and never had RC4-MD5 or the 40-bit export suites. So this file carries its own tiny SSLv3 server-side implementation on top of stdlib primitives (RSA PKCS#1 v1.5, RC4, DES, 3DES, MD5, SHA-1). The server key is 512-bit RSA so that export clients can encrypt the premaster secret to it directly, without a ServerKeyExchange.
(As the author of the post)
I've written and worked on a few TLS implementations, so it wasn't terribly interesting to me. And I have to go to work tomorrow and solve real, modern CA problems :)
But in short, I wanted to use Go, and it doesn't support SSLv3, the SSLv2 Client Hello, or the 40-bit RC4-MD5 export-grade cipher suites which I wanted to support too.
I was more shocked that I managed to get stock OpenSSL to issue a certificate that worked. There's a number of things that didn't work there, too. You can find my scars in mkcert.sh in the repo. Perhaps all of this is worthy of a follow-up post.
I could have tried to get some old server running instead, but I wouldn't have wanted to deploy that on the internet, even on an isolated Fly VM.
I bet all the certificate metadata shown in the „View a certificate“ popup window is vulnerable to cross-site scripting. Back then you probably wouldn’t get a <script> tag through a CA's review process and I found such a problem in Netscape's image „About page“ popup.
If it were vulnerable to XSS, why would you even want it properly signed by a CA? People almost never inspect the certificates of working websites, the only time they might look at it is when it fails validation.
A while back I helped a friend (read: dumped a bunch of compute power into it) brute force the SSL keys for Sega's "Phantasy Star Online" Dreamcast game.
They used a similar kind of custom (and flawed) TLS implementation in their game(s) which allowed signing new certificates after brute forcing.
The benefit to this is that users can now play these games without needing to burn a new CD with either the SSL certs swapped, or the code patched to dummy out the checks. A "retail CD" will simply work with private servers now.
I've also been on the other side of the fence, building a "retro internet" service [1] has meant trying to implement ancient SSL/TLS services for things and people that want to use them on the network.
Getting modern OpenSSL (aka what ships in Debian) to even accept these ciphers, let alone keys that short is an uphill battle. Understandably, they're disabled by default and (in Debian at least) the cipher support isn't even compiled into the binary! This requires building a custom OpenSSL to build Nginx against to serve ancient SSL.
Presumably for the OP this kind of work was either outside of their realm of knowledge, or simply "easier" to outsource to the slop machine. Though I hope the machine they're running their demo TLS implementation on is separated completely from their own network. Rolling your own crypto libraries is always a bad idea [2] and I doubt LLM's have "improved" that
[1] https://www.youtube.com/watch?v=cSJsGNIDjtc
[2] https://soatok.blog/2025/01/31/hell-is-overconfident-develop...
(I have next to zero knowledge of matters crypto)
“Presumably for the OP this kind of work was either outside of their realm of knowledge,”
Unnecessary? I don’t even follow the statement’s framing even if I validated the apparent nerdswipe tendency.
For what it's worth, this comment was better than the article...
When you outsource to the slop machine, you don't have anything interesting to say (usually).
Oh, I have *strong* opinions about the slop machine. But I try to temper them so I don't get buried by the usual "pro AI" mob
I will say that my projects have a "leading the pack" anti-AI policy [1]
Is the "pro AI" mob in the room with us? The only real mob I ever see is the one taking every chance to try to put AI down and imply its users are somehow deficient.
I don't recall doing any of that. But thanks for affirming my point? :)
Did I imply you did? I simply said I never see a "pro AI" mob, only an "anti AI" mob.
Let's flip it, then
Is the "anti AI mob" in the room with us right now? If not, why did you feel the need to lament it?
This entire comment section is almost entirely people bemoaning AI output, calling AI a "slop machine", and you posted your regressive religious screed against it as if it were something to be proud of, seemingly to the approval of others. nearly every comment section with AI involved is like this, and many comment sections where AI is not involved. It deserves pushback.
Probably because modern libraries dropped support for ancient insecure SSL. Backwards compatibility is really not a valued thing for that area.
Basically 2 days on a consumer GPU to crack a 512 bit cert. The thing is much of the traffic back then did not use ephemeral keys. Most of it wasn't even encrypted at all! But about a decade later, it became normal to encrypt everything. I do wonder which governments around the world are just waiting to crack anonymous political speech by recording and saving for later when decryption can happen.
It's possible symmetric encryption may never really be defeated by anything other than brute force. The exchange of the ephemeral key really is the important part, as you mention. Thankfully looks like we are getting closer to full adoption of post quantum TLS... but that doesn't help recorded communications before very recently. Scary thought.
Looks like 70% of cloudflare requests are using post-quantum TLS! https://radar.cloudflare.com/post-quantum
> which governments around the world are just waiting to crack anonymous political speech by recording and saving for later
Probably not too many, because anonymous political speech from 10+ years ago isn't that interesting. Punishing people a decade after the fact isn't very effective for anything.
Activists 10 years ago are probably still linked to interesting people the government wants to survey though, even if they are maybe less active now
The linked CADO-NFS Inria page makes no mention of GPUs, and nor does its downloads page, which makes me think that TFA's factoring was done purely on CPUs. If so, there could still be considerable speedup on the table!
The CADO-NFS page gives some benchmark results for 16 threads, suggesting the algorithm parallelises at least somewhat well.
I didn't use any GPUs, but Steve Weis (who factored the final key at the bottom of the post) did. He's posted about that factoring setup over on https://x.com/sweis/status/2095570645505700165
That SSL report with four different automatic 'F's is an amazing punchline
> While I haven’t verified this LLM output is entirely trustworthy, it looks pretty plausible.
It's essential that you do, because generating pretty plausible outputs is an LLM's bread and butter. Otherwise, only the one that you actually tested should be expected to be correct.
I agree to some degree, but it's not essential for what I wanted to do (which is find a 512-bit RSA key).
The biggest thing I'm afraid of is that the generated scripts missed some entries, or otherwise mis-classified them, in particular whether it got the trust bits right for each root. I would put the chances of that having some errors relatively high.
But there's too many roots across too many browser installers, so I'm not going to confirm the Netscape UI matches what the extracted data says.
For a problem like this it doesn't matter. The part the LLM generated was a hurdle to clear on the way to the final result. Once the final result was achieved, you know the earlier step was valid enough to get there.
I think you're assuming that the output of the page is LLM generated and not the process to produce the page.
In the 90s, how long did people expect it would be until consumer computer hardware would be able to do this so quickly?
From my recalling, a few years at most. There was, and apparently still exists, distributed.net which was aimed at brute forcing DES (easy), RC5-56 bits and then RC5-64 bits by establishing a web of personal computers (via a client one had to install). Thus it was well known brute forcing was achievable in a reasonable time.
PGP (1991) was considered secure as it was considered not brute forceable. With 128 bits, it was considered military grade at the time and the US had an export restriction due to that. That might have been an incentive for GNU Privacy Guard. In France you had to give your private key to the government authority if an encryption system used anymore than 56 bits (as I recall, I don't remember the exact number).
In 1999, factoring RSA-512 required roughly 292 CPU-years of work distributed across hundreds of academic machines, running for about 7 months. The community already knew it was weak -- the US export restrictions on 512-bit RSA were explicitly calibrated so the NSA could break it while casual adversaries couldn't.
Consumer hardware doing it in a couple of days in 2025 is roughly in line with Moore's Law extrapolations people were drawing at the time. The surprise isn't really the timeline. It's that someone did it as a weekend project rather than a nation-state effort.
This is amazing news for people building hyper-compatible websites!
This is so cool, I love reverse archeology of this, having another understanding of something functional but invisible from my childhood to finally understand it and then at a later now where we can break it. So cool!
I went down the same line of thought in the past! But I guess I was less thorough with my search, I never found any certs that small.
> Assuming you’re somehow running Netscape 4.51 with a clock set before E-Certify roots expired on 2003-10-16, you can use these private keys to issue certificates. This describes zero people on the planet… except for this VM I set up.
The planet has a lot of people.
How was it actually factored though? Where is the code for that? How was the private key created and how are the new certs issued?
The author mentions CADO-NFS right in the article: https://cado-nfs.gitlabpages.inria.fr/
lol nice job Marc Andreesen
The cost per bit is a doubling in time. So factoring a 512 RSA, compared to a 1024 RSA is significantly cheaper. The OP used contemporary hardware to do this. so, we'd have to ask if the orders of magnitude improvement in tech (QC aside) would permit 1024 in tractable time. I tend to no, but I appreciate there are other points of view. And of course, the belief that one day we can apply Shor with success exists. At which point the question is moot. Not that Shor does not itself demand significantly more stable gates, per extra bit of RSA. I always wonder why people don't look at the trend line in stable QuBits and the trendline in cost of RSA. Do the lines intersect?
Remember, Shor is like a coded gate level algorithm expressed as sequences of interconnected stable QuBits. So, if you double the cost for each RSA bit you add, its not "nothing" in terms of how you wire the rig.
(not a cryptographer, or a QC person so I expect to be hit by a very cold but stable quantum clue-by-four shortly. Maybe they have to hit me 1 million times, to confirm I'm hit. Its statistics.)
It’s not quite a doubling per bit, which is why RSA keys are relatively large compared to similar-strength ECDSA keys, for example.
Steve Weis, who has been doing RSA factoring on some large GPU clusters, estimates factoring 1024-bit RSA would take about 2000 GPU-years, which is well within the range of anyone with a serious budget.
Yeah, 2000 years sounds like a lot till you do the math. Apparently astra was trained on 100k Blackwell gpu’s. So just over 7 days to crack 1028-bit rsa on that cluster…
out of curiosity, how long would 2048-bit RSA take to factor?
It's hard to extrapolate that far, but maybe hundreds of thousands or millions of years.
Naively looking at scaling factors is going to be tricky, because computation of this scale is going to involve things like "how do I hijack every GPU on the planet", or worrying about when the sun will run out of hydrogen if you're using a single CPU.
https://en.wikipedia.org/wiki/Key_size#Asymmetric_algorithm_...
says approximately the same as a 112-bit symmetric key, so 1/65536 as fast as however your target platform does at AES128, but probably 2000 times slower again because RSA is a really slow algorithm.
128-bit security is the de-facto minimum standard. Anything less than that is suspect. That's a 3072-bit RSA key. We only ever tolerated shorter keys because RSA is so slow. You should switch to ed25519 if you can.
2048-bit RSA gives something like 28 more bits of security than 1024-bit RSA has, so it would take about 250 million times as long to factor one 2048-bit key.
Doubling per bit is for symmetric encryption, where no attack better than brute force is known. RSA can be attacked using much faster techniques than brute force.
There are techniques to speed up the search for RSA keys quite significantly: they don't scale as with a pure brute force search, nor with a very useful rule of thumb (it's not even the case that doubling the RSA key length doubles its effective security, it's actually a fair bit less than that).