5 ms·
RSA-896
- madars 7d agoMore details: https://x.com/sweis/status/2101484464807596264 https://x.com/sweis/status/2101484464807596264 I had Claude port CADO-NFS to run on GPUs. Then it orchestrated a fleet to run on scavenged idle capacity. It ran with a max of 2048 GPUs for about of 30 GPU-years over 10 days. I asked Claude if it had a message for a public: “The credit belongs first to the people who built the number field sieve and CADO-NFS over several decades, and to the teams who set the earlier records. This run used their algorithm and much of their code.” Also to clarify: - No new algorithmic factoring improvements. - It’s still exponential. - No new threats to deployed keys.
- sjs382 7d agohttps://xxcancel.com/sweis/status/2101484464807596264 https://xxcancel.com/sweis/status/2101484464807596264
- wslh 7d ago> It’s still exponential It's actually subexponential: https://en.wikipedia.org/wiki/General_number_field_sieve?wprov=sfti1#Method https://en.wikipedia.org/wiki/General_number_field_sieve?wpr...
- cwillu 7d ago…but super-polynomial.
- schoen 7d agoLike in the song! https://www.metzdowd.com/pipermail/cryptography/2004-June/007114.html https://www.metzdowd.com/pipermail/cryptography/2004-June/00...
- homosapien97 6d agoThanks for sharing, that brightened my day
- aidenn0 7d agoWhen's the coming age of crypto-anarchy?
- schoen 7d agoNot sure! It sounded more imminent back in 2000 when I heard Eric Hughes perform the song.
- sweis 7d agoI misspoke and corrected down thread.
- deleted 7d ago[deleted]
- DavideNL 7d agoMore details: https://archive.li/20260920025515/https://x.com/sweis/status/2101484464807596264 https://archive.li/20260920025515/https://x.com/sweis/status...
- whizzter 7d ago10 days of 2048 GPU's. Back of the envelope.. 1024 bit keys with recordings of not too old data can probably be found (MS only deprecated them in 2024 even if they planned on it in 2013) How long would it take for NSA to crack them if they had say the equivalent of a million GPU's? (either GPU's or crypto tuned ASICs)
- walrus01 7d agoA sufficiently motivated person with a good thermal camera and a cessna 172, entirely within the bounds of the law, could probably make an estimate of the waste heat from this, and then calculate backwards for how much compute power it is. https://en.wikipedia.org/wiki/Utah_Data_Center https://en.wikipedia.org/wiki/Utah_Data_Center
- maqp 6d agoExcept that's the "Massive Data Repository" which is mostly just about hoarding mass surveillance data. (Unless of course that's what THEY want us to think!) A better approximation can probably be had by comparing against the performance of the top ones at https://top500.org/ https://top500.org/
- ErroneousBosh 7d ago> How long would it take for NSA to crack them if they had say the equivalent of a million GPU's? (either GPU's or crypto tuned ASICs) Something I've often wondered is where the curve between "shit encryption / nation state cracking" crosses. How much CPU would you need to be Annoyingly Difficult to crack? I reckon with elliptic curves you could be quite annoying within about a minute on a 1980s-level CPU, to the extent that you could send a fairly ephemeral message quite quickly that would take disproportionately long to crack. Certainly long enough for the thing you have communicated to be no longer worth the effort to know. You could probably do 256-bit Curve25519 key generation in under ten minutes on an Apple II or Commodore 64, because the 6502's maths is terribly limited, but something like the Tandy Color or Dragon 32 with its 6809 processor (or hey why not the Ensoniq Mirage sampler?) could do that in probably a minute or so because it has a MUL opcode that's quite fast. I reckon that would keep even a fairly interested nation state chewing away long after your message had been read, understood, and acted upon.
- deleted 7d ago[deleted]
- weinzierl 7d agoWhat does "scavenged idle capacity" mean here?
- JoshTriplett 7d agoThe author works at Anthropic, so probably idle capacity in Anthropic's datacenters.
- bradfa 6d agoIf so, then the class of GPU used here may be significantly higher than mere mortals generally have access to simply due to cost. Obviously nation states will likely have significantly more resources than this, but this is not script kiddie levels of GPUs.
- gosub100 6d ago"idle capacity" - aka subtle advertisement
- dgacmu 6d agoIf you look at the numbers, he managed about 50% utilization of those 2048 GPUs over 10 days, so he was probably sneaking in factoring work between training runs.
- charlieyu1 6d agoI've done a fair amount of heavy computing now. Integer factorisation is not something you can really improve with GPUs. This sounds extremely wasteful, a bunch of cheap CPU cores would do just as well with much lower hardware cost and electricity cost.
- saidnooneever 6d agobut we have AI now so it doesnt matter what people know about computers :'). we got plenty of rainforest to burn afterall have you seen Brazil?
- timcobb 6d ago~so then how does one even understand this post? you have a person who appears to have done some sort of expert-level thing; however, their approach doesn't even make sense...?~ edit: GPU discussed here https://cognition.com/blog/factoring-rsa-260 https://cognition.com/blog/factoring-rsa-260
- hughw 6d agoI don't get your argument. The GPU effectiveness derives from massive parallelism. Has nothing to do with integer vs floating point. You just can't cram 20,000 CPU cores in the same space a GPU puts the same number of SIMTs. You'll never crack it on CPUs.
- bertonvv 6d agoIt seems that Eric Lu at Cognition AI used the exact same strategy on fewer GPUs to factor RSA-260 a couple weeks ago: https://cognition.com/blog/factoring-rsa-260 https://cognition.com/blog/factoring-rsa-260 Devin (their AI agent) ported CADO-NFS to run on GPUs, similarly without any claimed algorithmic factoring improvements, they just let it run for 13 GPU-years. I recommend reading their article since it's much more thorough on details.
- thesz 6d ago34 bits of key growth resulted in resource usage growth slightly more than 2 (30 GPU-years vs 13.5 GPU-years). Thus, it appears, that ~585 GPU years can factor 1024 bit RSA. 2.2^((1024-896)/34)=19.5, expected growth of resources' usage compared to 896 bits factorization, multiplying it by 30 GPU years for 896 bits gives about 585 GPU-years. This will cost about $20M with Cognition AI setup.
- maqp 6d agoThat's a relatively expensive strategy to get your name on Wikipedia.
- sweis 6d agoYep, they ran on some newer GPUs so were able to use fewer. Their implementation was faster than mine on RSA-260. For RSA-896, mine improved the performance a bit and selected a good polynomial. I’ll post more details once I get a chance. I wanted to publish as soon as I had the factors because I was beat by 48 hours last time.
- jgalt212 6d ago> I had Claude port CADO-NFS to run on GPUs. Then it orchestrated a fleet to run on scavenged idle capacity Is it easier to find unused GPUs than unused CPUs?
- deleted 7d ago[deleted]
- tristanj 7d agoIf you've already paid for and reserved a whole cluster of GPUs, any idle capacity is capacity you've already paid for. Using it is effectively free. So might as well use it to solve fun math puzzles. Though, it would make more financial sense to mine crypto.
- ehe78qhe 7d agoOnly if you pay a flat rate for electricity and cooling.
- deleted 7d ago[deleted]
- tristanj 7d agoBut Anthropic isn't paying for the electricity and cooling. They don't run their own data centers, they rent compute from providers who cover those costs. That's entirely why they can blow compute on the fun projects like this. If they had to pay extra for the electricity, they wouldn't do it.
- Barbing 7d agoIs the electricity cost far greater than the marketing value?
- rightnutwingjob 7d agoThe first is a physical quantity that can be written down. The second is approximately no better than astrology.
- ehe78qhe 7d agoThe second point is, sadly, true of quite a lot of aspects of software, including "design" and "quality"
- blackdahlia313 7d agoEnjoy the bounty
- tristanj 7d agoThere is no bounty, RSA labs ended the $75,000 reward in 2007.
- qurren 7d agoThere's about 900 BTC remaining for anyone who breaks these keys: https://privatekeys.pw/puzzles/bitcoin-puzzle-tx https://privatekeys.pw/puzzles/bitcoin-puzzle-tx If you break one though be careful when redeeming it, there are bots set up to pounce and steal the coins when they are transacted because the reduced entropy makes that possible. You need to submit the transaction to a mining pool that will not broadcast it until it is mined.
- DoctorOetker 7d agothats a poorly implemented reward script, if it leaves you exposed to the mining pool with this gentleman's agreement. the script could have been designed 2 phase, so one first submits a hash of the solution & submitter address, so even if miners front-run the submitter, they just helpfully pay the transaction fee!
- LiamPowell 7d agoThere is no script.
- greyface- 7d agoOf course there's a script; every bitcoin tx output has a script. These challenges use the standard P2PKH script, i.e.: scriptPubKey: OP_DUP OP_HASH160 <pubKeyHash> OP_EQUALVERIFY OP_CHECKSIG scriptSig: <sig> <pubKey> https://en.bitcoin.it/wiki/Script https://en.bitcoin.it/wiki/Script
- someguydave 7d agokinda bearish for the data center rollouts if the spare compute can be used to solve math puzzles instead of training LLMs
- redox99 7d agoQuite bearish on Anthropic if they had nothing better to do with 2048 GPUs for 10 days than finding an RSA number with already existing algorithms.
- muglug 6d ago1 engineer != Anthropic
- hinkley 6d agoSomeone allocated those GPUs.
- 0x10ca1h0st 5d agoI think you are missing the "idle capacity" information. The GPUs are not running 24/7, there may be minutes of time in a day where there is not an active job running, the author simply located these inactive GPUs during the downtime and utilized it until another job was queued.
- redox99 5d agoYeah it's a bit ambiguous, but in any case I'd think simply using that idle capacity to generate tokens would be more valuable than finding a basically meaningless number.
- vavkamil 7d agoInteresting. Instagram still publishes a 768-bit RSA DKIM key, so I guess factoring it is now just a weekend GPU project? https://dns.google/resolve?name=pm._domainkey.instagram.com&type=TXT https://dns.google/resolve?name=pm._domainkey.instagram.com&...
- functional_dev 7d agoRSA-768 was already factored in 2009.. cheap now. What surprised me is that RSA keys are much weaker than their size looks. You need 2048 bits to get normal safety, and 768 is far below that. https://vectree.io/c/how-rsa-key-sizes-map-to-real-security-512-to-4096-bits https://vectree.io/c/how-rsa-key-sizes-map-to-real-security-...
- natdempk 6d agoWhat's the cost estimate to factor this?
- gizmodo59 6d agoYou don’t need AI to solve this. Just lots of compute.
- Retr0id 6d agoIf anyone else has spare GPU hours they don't know what to do with, may I recommend partial hash collisions: https://github.com/DavidBuchanan314/birthday_party https://github.com/DavidBuchanan314/birthday_party (The "record" set by me only took about 1 GPU day - easy to beat!)
- gpugreg 6d agoHere's a larger partial hash collision (108 trailing bits): echo 23ca73454a1b981fe51cad0dbd05f4e696795ba67abb28c61aea1a024e5bbeca | xxd -r -p | sha256sum echo a16a8141361ae9834ad171ec28961fc8a951ff1bfc3a9ce0dc2fcdbdfa2ccd35 | xxd -r -p | sha256sum From this post from 6 years ago: https://www.reddit.com/r/crypto/comments/guctw4/finding_sha256_partial_collisions_via_the_bitcoin/ https://www.reddit.com/r/crypto/comments/guctw4/finding_sha2...
- speedgoose 6d agoNice. I will make sure to turn my WiFi box off at night and pee in the shower to compensate the environmental impact of this.
- tptacek 6d agoYou'd be having approximately the same impact on the climate as the factoring work, so, makes sense.
- speedgoose 6d ago30 years of busy GPUs instead of idling GPUs converts to a lot of pee in the shower. I’m not sure I will live long enough.
- singpolyma3 6d agoLiterally no content here
- deleted 6d ago[deleted]
- eugenekolo 6d ago"I work at Anthropic and used idle GPUs running known algorithm to factor a number. I used Claude btw"