20 ms·
I've factored the RSA keys of a Certificate Authority from the 90s
- ggm 25d agoThe 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.)
- mcpherrinm 25d agoIt’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.
- throwawayk7h 25d agoout of curiosity, how long would 2048-bit RSA take to factor?
- mcpherrinm 25d agoIt'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 25d ago[deleted]
- mitxela 25d agohttps://en.wikipedia.org/wiki/Key_size#Asymmetric_algorithm_key_lengths 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.
- entrope 25d ago2048-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.
- upofadown 24d agoMy article: 2048 Bit RSA and the Year 2030 https://articles.59.ca/doku.php?id=em:20482030 https://articles.59.ca/doku.php?id=em:20482030 We don't have any way to predict when and if 2048 bit RSA would be factorable at this time. We would need a breakthrough in hardware and/or algorithms. The common estimation that it is equivalent to the difficulty of brute forcing symmetrical 112 bit encryption seems to be based on some sort of straightforward extrapolation. It doesn't take into account the amount of memory required for the poorly reducible matrix reduction step in the currently known best algorithm. That's 10^18 bytes of memory, or a million terabytes, somehow coupled to enough processing power to actually make anything possible. Even if you accept the 112 bit estimate, that works out to something like 400 thousand years using the Bitcoin network as a reference to what we could reasonably achieve.
- mitxela 24d agoWhich isn't a very good margin in cryptography, where we usually aim for things like "longer than the universe's lifetime if every atom was a CPU". But RSA is really slow so we have to compromise encryption speed with cracking speed.
- WhiteDawn 25d agoYeah, 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…
- rcxdude 25d agoThere 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).
- mitxela 25d agoDoubling 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.
- ColinWright 25d agoCan you point at some papers or articles that talk about attacks specifically on RSA? I've done a search and have a few references, but I'd be interested to know if you have any particular examples in mind. I know that factoring (which attacks RSA) is sub-exponential, and I know that implementations of RSA (bad choices of primes, timing attacks, etc) can have weaknesses ... I'm just interested as to whether you have something else in mind. Thx.
- hannob 25d agoI think you're looking for the large formula at the top here: https://en.wikipedia.org/wiki/General_number_field_sieve https://en.wikipedia.org/wiki/General_number_field_sieve Reference to a scientific paper is given: https://www.ams.org/notices/199612/pomerance.pdf https://www.ams.org/notices/199612/pomerance.pdf
- ColinWright 24d agoThat's referring to attacking the factoring problem, which is one method of attacking RSA, and as I said is known to be faster than exponential, but it felt like the comment to which I was replying was talking about something other than just faster factoring. I know there are other attacks on RSA, I was interested to know if the poster to whom I was replying knew of any others (other than factoring, which is kinda obvious). After all, I said: > I know that factoring (which attacks RSA) is sub-exponential, ...
- gosub100 24d agoCheck out the ROCA attack: www.techtarget.com/cybersecurity/tip/The-ROCA-vulnerability-How-it-works-and-what-to-do-about-it%3famp=1 In practice it was confined to specific TPM modules, but in principle it shows how one flaw in the RNG can jeopardize the whole system. I also remember seeing a similar vuln in certificates where an attacker _generated_ millions of certs and was able to somehow get the private cert by trying every possible seed for the RNG. (Like seeding every second from 2003-2011 for example, then generating a cert with it). I know I'm getting major parts of this wrong but it conveys the general idea.
- goalieca 25d agoBasically 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.
- Neywiny 25d agoCPU?
- akoboldfrying 25d agoThe 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.
- mcpherrinm 25d agoI 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 https://x.com/sweis/status/2095570645505700165
- ThePowerOfFuet 25d agoMuskless link: https://xcancel.com/sweis/status/2095570645505700165 https://xcancel.com/sweis/status/2095570645505700165
- adzm 25d agoIt'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 https://radar.cloudflare.com/post-quantum
- pvillano 25d agoThat SSL report with four different automatic 'F's is an amazing punchline
- mitxela 25d ago> 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.
- mcpherrinm 25d agoI 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.
- joshka 25d agoI think you're assuming that the output of the page is LLM generated and not the process to produce the page.
- Aurornis 25d agoFor 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.
- mitxela 24d agoThe OP is separately advertising a list of all the keys.
- 63 25d agoA 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.
- mcpherrinm 25d ago(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.
- dividuum 25d agoI 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.
- WatchDog 25d agoIf 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.
- excalibur 25d ago> 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.
- MrDOS 24d agoAre very many of them time travellers?
- Sophira 24d agoYou'd be surprised.
- jasomill 24d agoNo, but some are retrocomputing enthusiasts who might occasionally run vintage browsers on non-Y2K compliant systems. The cert in question has a "not before" date in 1998, and Netscape 4.51 hails from around same time. Probably zero doing anything worth MitMing, though.
- Retr0id 25d agoI 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.
- andytratt 25d agolol nice job Marc Andreesen
- rootsudo 25d agoThis 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!
- forgotmypw17 25d agoThis is amazing news for people building hyper-compatible websites!
- ranger_danger 25d agoHow was it actually factored though? Where is the code for that? How was the private key created and how are the new certs issued?
- zatkin 25d agoThe author mentions CADO-NFS right in the article: https://cado-nfs.gitlabpages.inria.fr/ https://cado-nfs.gitlabpages.inria.fr/
- ranger_danger 24d agoYes but used how? What is the exact configuration and details for reproducing this?
- mcpherrinm 24d agoThat's a good point. I've added to the post. It's simple enough I'd expect anyone who wants to do it can follow the docs from CADO-NFS, which are very good, but I can write it down explicitly. Install CADO-NFS per upstream directions. Get the number you want to factor. I just did this in a python repl, something like: from cryptography import x509 f = open("gold-server.pem", "rb").read() print(x509.load_pem_x509_certificate(f).public_key().public_numbers().n) That gets you the `n` to factor - The big number below. Then pass it to CADO-NFS. The full invocation for the server root was: ./cado-nfs.py 10754123440737946604182274398563307850262685121187325065132187145895199633213947273310647001521000121802425390193123548314361970563322281259804690831526167 -t 32 --workdir /data/cert1 All run in a tmux to keep it alive for the few days, of course.
- jrmg 25d agoIn the 90s, how long did people expect it would be until consumer computer hardware would be able to do this so quickly?
- axionbraid 25d agoIn 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.
- hashar 25d agoFrom 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).
- LastTrain 24d agoIt was also illegal to export software with cryptography in the early 90s, anything with keys bigger than 40 bits, so there was a lot of intentionally weak connections.
- Maxious 24d agoIn 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), crunching in parallel for seven months. https://cs.ccsu.edu/~pelletie/local/risks/cryptography/Factoring-a-512-bit-number.html https://cs.ccsu.edu/~pelletie/local/risks/cryptography/Facto... Robert Silverman, a senior research scientist at RSA Laboratories, published an analysis projecting these new hardware requirements against Moore's Law. His expectation was that within 10 years (roughly 2009–2010), common desktop machines would possess the speed and memory necessary to handle a 512-bit factorization entirely on their own. https://cr.yp.to/bib/2000/silverman.pdf https://cr.yp.to/bib/2000/silverman.pdf
- teiferer 25d ago> 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?
- bpbp-mango 25d agoamusing the site is available over ipv6. I suppose ipv6 was around back then, at least.
- tunahanfaruksav 25d agoGreat 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.
- deleted 25d ago[deleted]
- frays 24d agoopenssl 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
- GracefullyShot 24d agoI 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.
- upofadown 24d agoThis article from 2000 is about estimating what would be required to factor 1024 bit RSA: A Cost-Based Security Analysis of Symmetric and Asymmetric Key Lengths https://cr.yp.to/bib/2000/silverman.pdf https://cr.yp.to/bib/2000/silverman.pdf It was a response to the idea that 1024 bit RSA was under threat at the time.
- rbtms 24d agoAs 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 equivalent) bits based on the best factoring algorithms (for comparison, the RSA-512 the article mentions has an 56 bit equivalent and RSA-1024 has a 80 bit equivalent security, so RSA-1024 would take roughly 2^(80-56) ~= 17 million times to compute the worst-case scenario and RSA-2048 would take 2^(112-80) = 4.3 thousand million times more). According to the Wikipedia article on RSA numbers, RSA-220 (66b) was factored in 2016, RSA-230 (69b) in 2018, RSA-240 (72b) in 2019 and RSA-260 (76b) this year, which is too close to RSA-1024 (80b) to be comfortable. For RSA-250, the team reported it took "roughly 2,700 core-years, using Intel Xeon Gold 6130 CPUs at 2.1 GHz.". I am not going to (or feel qualified to) make estimates of how that would translate to RSA-1024, but it does sound plausible given enough resources.
- rwissinger 24d ago[flagged]
- hnmullany 24d agoI 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 release - and this might have been the first release to monetize the root slots because Netscape was under severe pressure to generate revenue. (Also - Verisign hated that we were expanding competition and tried to convince us to implement a program that would re-restrict the list to a set of "responsible" companies aka Verisign and one or two others. We declined.)
- jetbalsa 24d agoIts 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.
- cyanydeez 24d agoIts a shame public internet is npt viewed as a public utility
- AnthonyMouse 24d agoHow 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 versa? The existing system is more than the usual amount of messed up but that seems like one of the things that could actually make it worse.
- cyanydeez 24d agosame way every public utility works. It's great until a capitalist buys your government and forces you to sell it back to them while they rent seek.
- 6thbit 24d agoSo this is why forward secrecy matters eh
- gadders 24d agoI womder if you could do the old Lotus Notes weak non-US Keys now, and if there are any old .nsf files floating around to be decrypted.
- alexpotato 24d agoI owned the "broker FTP" service at a hedge fund. There was a project in 2021 to talk to the banks and brokers that we connected and ask them to upgrade their keys and ciphers to modern versions. IIRC, the oldest key/cipher was from the late 2000s so it wouldn't surprise me if someone is using RSA keys from the 90s somewhere. You can read more about how hedge funds use FTP here: https://x.com/alexpotato/status/1809579426687983657?s=20 https://x.com/alexpotato/status/1809579426687983657?s=20 Or listen to patio11 and I talk about these systems in general here: https://www.complexsystemspodcast.com/episodes/two-banks-cant-agree-on-fourth-grade-math/ https://www.complexsystemspodcast.com/episodes/two-banks-can...
- nly 24d agoI used to work on market data feeds, which occasionally require a reference data file from an FTP to be delivered before market open before you can do anything useful with the feed. Nothing like being on-call when the file doesn't get delivered, or fails to parse Fortunately most feeds deliver reference data inband these days
- alexpotato 23d agoA lot of this is also moving to SWIFT (as in banking system) messages. I guess in some ways this is better but SWIFT is famously a giant pain in the ass to install and support.
- Neat_comfort007 24d ago[flagged]