Nördnytt! 🤓I've factored the RSA keys of a Certificate Authority from the 90s
- 63 - 32200 sekunder sedanA 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.
- goalieca - 32917 sekunder sedanBasically 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.
- GracefullyShot - 2546 sekunder sedanI 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 factoring a key of that size, it’s within the realm of possibility for a government or other organization with a large number of computers.
Is it? How do I verify such claim?
---
> Just a few days ago, someone factored the 862-bit RSA-260 key from the RSA factoring challenge.
Yeah, but how much time it required? and what about the resources? It is just a number, it is not all the 861 bits n numbers.
- teiferer - 12631 sekunder sedan> I don’t have any good reason to do that, but it seems like fun.
What better reason is there to do something than it being fun?
- tunahanfaruksav - 5050 sekunder sedanGreat writeup. The fact that CADO-NFS still takes 32 hours on a 5950X for a 512-bit key that's trivial by today's academic standards really puts into perspective how comically undersized these were even for 1999 — RSA-155 fell that same year. Also love that verifying against real Netscape 4.51 ended up being harder than the factoring itself.
- pvillano - 32327 sekunder sedanThat SSL report with four different automatic 'F's is an amazing punchline
- - 3498 sekunder sedan
- mitxela - 32260 sekunder sedan> 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.
- forgotmypw17 - 25472 sekunder sedanThis is amazing news for people building hyper-compatible websites!
- frays - 3322 sekunder sedan
openssl rsa -in private.key -text -noout prime1: 00:f7:5b:73:5c:13:9b:7b:70:58:36:22:d6:25:e6: 44:15:f3:f7:b3:18:c5:11:65:77:f2:85:af:cc:79: fa:d2:bd prime2: 00:d4:81:b4:f5:af:a8:56:0e:a3:34:c0:e3:e8:60: fb:b2:96:83:e2:af:6d:d7:09:3f:37:2a:bf:31:32: cf:92:63 - rootsudo - 28654 sekunder sedanThis 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!
- jrmg - 21993 sekunder sedanIn the 90s, how long did people expect it would be until consumer computer hardware would be able to do this so quickly?
- bpbp-mango - 9363 sekunder sedanamusing the site is available over ipv6. I suppose ipv6 was around back then, at least.
- Retr0id - 31541 sekunder sedanI 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.
- excalibur - 31769 sekunder sedan> 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.
- ranger_danger - 24894 sekunder sedanHow was it actually factored though? Where is the code for that? How was the private key created and how are the new certs issued?
- andytratt - 29035 sekunder sedanlol nice job Marc Andreesen
- ggm - 33226 sekunder sedanThe 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.)