Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

I've factored the RSA keys of a Certificate Authority from the 90s

mcpherrin.ca

Post reply on HN
Print view View original

41–50 of 131 posts

Re: I've factored the RSA keys of a Certificate Authority from the 90s

#41

Post by axionbraid »

jrmg wrote: post #38

In the 90s, how long did people expect it would be until consumer computer hardware would be able to do this so quickly?

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.

Re: I've factored the RSA keys of a Certificate Authority from the 90s

#42

Post by hashar »

jrmg wrote: post #38

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

Re: I've factored the RSA keys of a Certificate Authority from the 90s

#43

Post by icefo »

tgsovlerkhgsel wrote: post #40
goalieca wrote: post #4

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.

> 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

Re: I've factored the RSA keys of a Certificate Authority from the 90s

#44

Post by [deleted] »

mcpherrinm wrote: post #12
throwawayk7h wrote: post #8

Earlier quoted context omitted.

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.

[deleted]

Re: I've factored the RSA keys of a Certificate Authority from the 90s

#45

Post by WatchDog »

dividuum wrote: post #36
mcpherrinm wrote: post #15

Earlier quoted context omitted.

(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…

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

Re: I've factored the RSA keys of a Certificate Authority from the 90s

#46

Post by jimmaswell »

CursedSilicon wrote: post #37
jimmaswell wrote: post #35

Earlier quoted context omitted.

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.

Re: I've factored the RSA keys of a Certificate Authority from the 90s

#47

Post by WhiteDawn »

mcpherrinm wrote: post #3
ggm wrote: post #2

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 w…

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…

Re: I've factored the RSA keys of a Certificate Authority from the 90s

#48

Post by ricksunny »

CursedSilicon wrote: post #19
63 wrote: post #11

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

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 swap…

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

Re: I've factored the RSA keys of a Certificate Authority from the 90s

#49

Post by ThePowerOfFuet »

mcpherrinm wrote: post #29
akoboldfrying wrote: post #26

Earlier quoted context omitted.

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

Muskless link: https://xcancel.com/sweis/status/2095570645505700165
Post reply on HN