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

121–130 of 131 posts

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

#121

Post by mcpherrinm »

Maxious wrote: post #71
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 Schneider's 1995 book he estimated factoring a 512-bit number would take roughly 30,000 MIPS-years (a one-million-instruction-per-second computer running for one year). When a research team actually factored RSA-155 in August 1999, it took 8,400 MIPS-years due to efficiencies discovered. It still took 35 CPU-years spread across a cluster of 300 fast SGI/SUN workstations and Pentium II PCs (400-500 MIPS each), crun…

I don't know how fast my CPU cores are in MIPS, but it's 4.5 Ghz and some random googling indicates that might be about 10 MIPS per Mhz, so 45,000 Dhrystone MIPS.

And assuming about ((32x32 core-hours) / 8766 (hours/year)) x 45,000 = 5256 MIPS-years.

So within the order of magnitude of the 1999 factoring! Of course, the MIPS number is kinda made up, so

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

#122

Post by necovek »

jetbalsa wrote: post #80
hnmullany wrote: post #75

I was the product manager with responsibility for root certificates in the Netscape 4.51 browser. It's crazy to see someone factor it 25 years later. Just to reply to some people in the comments. Yes, we knew export grade encryption was weak - that was the point - that the NSA could decrypt it - and the govt. required us to do it anyway. FWIW - we had the goal of expanding the list of root authorities in the 4.5x rel…

Its a shame that Microsoft ate Netscape's lunch so early on. I still use Firefox and have fond memories of Netscape (v7) when growing up.

IIRC, Netscape 4.* series was the last in the proprietary line of Netscape Navigators (though 4.* had a broader name like "Communicator" or something, since it included more than just the browser — but "3.0 Gold" was the one I remember most fondly as my first true good browser).

After that, open source efforts to rebuild the entire browser and mail client took years as XUL and Gecko were being built as very generic reusable components, opening up the space for competition to spring up. On top of that, Microsoft leveraged the Windows moat, including IE 3.0 and later 4.0 as the basis of Windows "97" (95 something-something) and 98, along with ActiveX push. By the time legal systems caught up with the practice of bundling a browser into a dominant OS, Netscape and Mozilla were toast.

Everything from there on was an uphill battle, and when KHTML was turned into WebKit by Apple, and adopted by Google for Chrome, there was also an open source engine (or two) supported by infinite money.

That's at least how I remember it, but you are welcome to fact-check me on any of those since this is now 20-30 years ago.

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

#123

Post by necovek »

mdemare wrote: post #114
otabdeveloper4 wrote: post #113

Earlier quoted context omitted.

You don't need a "root certificate". Just publish a public key in your DNS TXT records. ACME is just that anyways but with extra (pointless) steps. The whole SSL certificate grift is just a way to extort money out of nothing.

Ok, but now you need to trust DNSSEC.

The point GP was making is that DNS-record based ACME mechanism for verification of ownership implies trust in the domain name owner (or really, anyone who can edit records in the domain zone), making the issuance of a certificate actually superfluous.

DNSSEC is probably not even used, though I never checked.

Eg. as a domain owner, you will put a cryptographic hash into your DNS zone so a CA can validate you have control over it, and then issue a different cryptographic hash derived from their private key, and browser will use their public key to validate this cryptographic hash (TLS cert) is valid.

So we could simply push public key into a DNS zone, and browsers could use it to decrypt the traffic encrypted by the private key from the server hosted under that DNS name: no CAs needed, similar to SSH except the DNS-ownership-implied-trust component.

"Extended validation" certificates involved a lot more (in theory, checking true ownership, business address, physical presence, etc), but nobody really cares about these, and with the push to automated renewal and 45-day expiration dates by 2028, it's going to make even less sense.

Edit: I realize now that you may be referring to the fact that MITM DNS server can inject a different public key in there and thus DNSSEC is required — you are absolutely right, and this is a good and important point.

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

#124

Post by throw1234567891 »

wartywhoa23 wrote: post #76
throw1234567891 wrote: post #54

Earlier quoted context omitted.

The slop machine gives answers to your questions. It hallucinates so it's recommended to verify what it says. Shit in, shit out. If you have no idea whatsoever and can't use other sources to verify claims, well, get a different job I guess.

Why use the slop machine then, if you already know or precognize the answer?

Because you move faster.

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

#125

Post by strenholme »

nly wrote: post #116
tptacek wrote: post #107

Earlier quoted context omitted.

Forget whether you "roll your own" or not, userspace RNGs are a bad idea. The advice to rely on getrandom or urandom is as much about the superior security properties of a kernel RNG as they are about whether you'll fuck up AES somehow.

A read() on /dev/urandom on every packet isn't economical, so there's going to be some user space element to RNGion

In addition to the overhead of a /dev/urandom read(), since my programs run in a chroot() sandbox, there’s the possibility that the file descriptor to /dev/urandom will no longer function—since chroot() is not part of POSIX, there’s no rigorous standard on how chroot() is supposed to behave with a given operating system.

getrandom() is another possible solution, but the problem with getrandom() is that it’s also not part of the POSIX spec, and my program needs to compile in an anally POSIX compliant system: While my programs use chroot() and setgroups(), both of which aren’t part of the POSIX spec, it has a configure time option to disable both chroot() and setgroups() so everything will compile as long as the underlying system follows POSIX.

The reason for this strict compliance with POSIX is because the changes to the C compilers (gcc and clang) between 2022 and 2026 made previous versions of MaraDNS have issues compiling everything, and, indeed, with these C23 changes to C compilers, unpatched djbdns no longer even compiles with a modern compiler. I changed everything to work with the new C23 spec, then I changed the compile flags to compile with a strictly compliant C99 compiler, but to get that to work, I had to make the program strictly POSIX compliant (with the exceptions of chroot() and setgroups()).

This way, should MaraDNS not compile in the future (remember: The post-C23 changes broke a lot of programs that used to compile just fine), it’s a bug with the compiler not following C99 and/or POSIX, and not a bug with MaraDNS.

Hence, my homegrown secure pseudo random number generator, so I can make strong random numbers while remaining POSIX compliant (we seed the PRNG before entering the chroot() sandbox). Of course, /dev/urandom is also not part of POSIX, but it’s on pretty much any modern *NIX, and trying to open /dev/urandom is not going to raise compile-time errors.

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

#126

Post by tptacek »

strenholme wrote: post #125
nly wrote: post #116

Earlier quoted context omitted.

A read() on /dev/urandom on every packet isn't economical, so there's going to be some user space element to RNGion

In addition to the overhead of a /dev/urandom read(), since my programs run in a chroot() sandbox, there’s the possibility that the file descriptor to /dev/urandom will no longer function—since chroot() is not part of POSIX, there’s no rigorous standard on how chroot() is supposed to behave with a given operating system. getrandom() is another possible solution, but the problem with getrandom() is that it’s also not…

I don't think trading resilience for POSIX compliance is a good call, and I don't think "strong random numbers" is at all the right way to think about this problem.

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

#127

Post by tptacek »

otabdeveloper4 wrote: post #113
AnthonyMouse wrote: post #109

Earlier quoted context omitted.

How do you imagine that would work for something like this? Suppose you live in South America, register a domain from a registry in Canada and then have users accessing it from Ukraine. Are we going to give every local government a global root certificate? Have a single one in California or Texas that every other country is somehow forced to use? Or make it so people in Europe can't access sites in Asia and vice vers…

You don't need a "root certificate". Just publish a public key in your DNS TXT records. ACME is just that anyways but with extra (pointless) steps. The whole SSL certificate grift is just a way to extort money out of nothing.

It's all an elaborate scheme by the ISRG: compete all the commercial CAs out of existence, and then charge A MILLION DOLLARS for a certificate renewal. I've seen this movie before.

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

#128

Post by tptacek »

necovek wrote: post #123
mdemare wrote: post #114

Earlier quoted context omitted.

Ok, but now you need to trust DNSSEC.

The point GP was making is that DNS-record based ACME mechanism for verification of ownership implies trust in the domain name owner (or really, anyone who can edit records in the domain zone), making the issuance of a certificate actually superfluous. DNSSEC is probably not even used, though I never checked. Eg. as a domain owner, you will put a cryptographic hash into your DNS zone so a CA can validate you have con…

... but then, as they point out, you have to trust DNSSEC, and that's pretty fraught --- probably more fraught than trusting a CA.

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

#129

Post by rurban »

rbtms wrote: post #68
GracefullyShot wrote: post #62

I am not a cryptography expert but I am interested in the field. Having said that: I am lately having an hard time understanding the actual strength of a crypto suite based on the underlying problem, the sized of the material and the computation strength needed to break it either via optimization and parallelism capabilities. > The Web PKI deprecated 1024-bit RSA over a decade ago, and while I don’t know of anyone fa…

As you probably know, the computing time in the worst case scenario for brute forcing a cryptographic key generally doubles by each bit added. That is, it would take twice the effort to brute-force 129 bits compared 128 bits. The security of RSA however depends on the factoring of very large numbers, and that means that for example, RSA-2048 doesn't translate into 2048 bits of security but 112 (roughly symmetric equi…

RSA-1024 about 2000 GPU years. With clusters of size 100k typical right now. https://x.com/sweis/status/2095570657367278051

Consider it broken already for AI or NSA guys

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

#130

Post by rurban »

Maxious wrote: post #71
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 Schneider's 1995 book he estimated factoring a 512-bit number would take roughly 30,000 MIPS-years (a one-million-instruction-per-second computer running for one year). When a research team actually factored RSA-155 in August 1999, it took 8,400 MIPS-years due to efficiencies discovered. It still took 35 CPU-years spread across a cluster of 300 fast SGI/SUN workstations and Pentium II PCs (400-500 MIPS each), crun…

Only lunatics would do it on CPU's though. They'd use their GPU cluster, with custom SW (not yet online). RSA-1024 would cost about a week then.
Post reply on HN