Thread

RSA-896

226 points · 90 comments · madars

Loading the complete thread in the background. This saved snapshot is available now. Refresh

madars · 1789870773 · focus · HN ↗
More details: <a href="https://x.com/sweis/status/2101484464807596264" rel="nofollow">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.
```
1. sjs382 · 1789875754 · focus · HN ↗
  <a href="https://xxcancel.com/sweis/status/2101484464807596264" rel="nofollow">https://xxcancel.com/sweis/status/2101484464807596264
2. wslh · 1789875789 · focus · HN ↗
  > It’s still exponential
  It's actually subexponential: <a href="https://en.wikipedia.org/wiki/General_number_field_sieve?wprov=sfti1#Method" rel="nofollow">https://en.wikipedia.org/wiki/General_number_field_sieve?wpr...
  1. cwillu · 1789881027 · focus · HN ↗
    …but super-polynomial.
    schoen · 1789885246 · focus · HN ↗
    Like in the song!
    <a href="https://www.metzdowd.com/pipermail/cryptography/2004-June/007114.html" rel="nofollow">https://www.metzdowd.com/pipermail/cryptography/2004-June/00...
    aidenn0 · 1789885537 · focus · HN ↗
    When's the coming age of crypto-anarchy?
    schoen · 1789886116 · focus · HN ↗
    Not sure! It sounded more imminent back in 2000 when I heard Eric Hughes perform the song.
    homosapien97 · 1789915086 · focus · HN ↗
    Thanks for sharing, that brightened my day
  2. sweis · 1789882440 · focus · HN ↗
    [delayed]
3. inopinatus · 1789875921 · focus · HN ↗
  [delayed]
4. DavideNL · 1789883029 · focus · HN ↗
  More details: <a href="https://archive.li/20260920025515/https://x.com/sweis/status/2101484464807596264" rel="nofollow">https://archive.li/20260920025515/https://x.com/sweis/status...
5. whizzter · 1789889147 · focus · HN ↗
  10 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)
  1. walrus01 · 1789890147 · focus · HN ↗
    A 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.
    <a href="https://en.wikipedia.org/wiki/Utah_Data_Center" rel="nofollow">https://en.wikipedia.org/wiki/Utah_Data_Center
    maqp · 1789925914 · focus · HN ↗
    Except 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 <a href="https://top500.org/" rel="nofollow">https://top500.org/
  2. ErroneousBosh · 1789893163 · focus · HN ↗
    > 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.
  3. gpugreg · 1789912549 · focus · HN ↗
    > 1024 bit keys with recordings of not too old data can probably be found
    I think GitHub might turn into a scary vector of supply chain attacks in the foreseeable future. There is a five digit number of users still running around with 1024 bit RSA keys.
  4. upofadown · 1789914515 · focus · HN ↗
    Hard to judge. The bottleneck is the phase of the algorithm where a really big linear system needs to be solved. That takes a lot of communication between nodes. The breakthrough in using GPUs is that there is good communication between nodes[1]. At the scale of 1024 bit RSA the communication might become a bottleneck again.
    [1] <a href="https://cognition.com/blog/factoring-rsa-260" rel="nofollow">https://cognition.com/blog/factoring-rsa-260
6. fodkodrasz · 1789891251 · focus · HN ↗
  If you create a blog post, putting this info there, or to be hones, at least any info would make sense. Didn't Claude give some advice on that also?
7. weinzierl · 1789896857 · focus · HN ↗
  What does "scavenged idle capacity" mean here?
  1. JoshTriplett · 1789898182 · focus · HN ↗
    The author works at Anthropic, so probably idle capacity in Anthropic's datacenters.
    bradfa · 1789905537 · focus · HN ↗
    If 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 · 1789915625 · focus · HN ↗
    "idle capacity" - aka subtle advertisement
  2. dgacmu · 1789910732 · focus · HN ↗
    If 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.
8. charlieyu1 · 1789906247 · focus · HN ↗
  I'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.
  1. saidnooneever · 1789908777 · focus · HN ↗
    but 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?
  2. timcobb · 1789911633 · focus · HN ↗
    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...?
  3. hughw · 1789912871 · focus · HN ↗
    I 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.
9. bertonvv · 1789906506 · focus · HN ↗
  It seems that Eric Lu at Cognition AI, a competitor to Anthropic, used the exact same strategy on fewer GPUs to factor RSA-260 a couple weeks ago: <a href="https://cognition.com/blog/factoring-rsa-260" rel="nofollow">https://cognition.com/blog/factoring-rsa-260
  Devin 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.
  1. thesz · 1789924585 · focus · HN ↗
    34 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 · 1789926084 · focus · HN ↗
    That's a relatively expensive strategy to get your name on Wikipedia.
  2. sweis · 1789938487 · focus · HN ↗
    Yep, 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.
10. jgalt212 · 1789909847 · focus · HN ↗
  > 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?
tristanj · 1789872527 · focus · HN ↗
If these GPUs are already reserved and prepaid by the hour, any idle compute is already paid for. So using it is essentially free. Might as well use it to solve fun math puzzles.
tristanj · 1789872737 · focus · HN ↗
If 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.
1. ehe78qhe · 1789874037 · focus · HN ↗
  Only if you pay a flat rate for electricity and cooling.
  1. tristanj · 1789874224 · focus · HN ↗
    But they're not paying for the electricity and cooling, it's included in the rental contract.
    Free electricity and cooling is the entire reason why this result was possible.
  2. tristanj · 1789874747 · focus · HN ↗
    But 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 · 1789875765 · focus · HN ↗
    Is the electricity cost far greater than the marketing value?
    rightnutwingjob · 1789877097 · focus · HN ↗
    The first is a physical quantity that can be written down.
    The second is approximately no better than astrology.
    ehe78qhe · 1789877746 · focus · HN ↗
    The second point is, sadly, true of quite a lot of aspects of software, including "design" and "quality"
    nullsanity · 1789882579 · focus · HN ↗
    [dead]
    adastra22 · 1789882364 · focus · HN ↗
    The marginal electricity cost is zero.
    lazide · 1789887710 · focus · HN ↗
    Or specifically, electricity was already paid for with the pre-paid capacity.
    Not using it would not save them any money, they already paid for it.
    Barbing · 1789935516 · focus · HN ↗
    I was thinking if they owned their own data centers, how expensive might this project have been.
    londons_explore · 1789890625 · focus · HN ↗
    But training LLM's is also a task one can do whenever you have a spare GPU-minutes.
    I wonder why they don't have some kind of scheduler which makes sure there are never any idle minutes. One would imagine they at least would have autoscaling on their production serving workload and use the freed compute capacity for model training for example.
    esseph · 1789892447 · focus · HN ↗
    [delayed]
  3. odo1242 · 1789879569 · focus · HN ↗
    Most of the GPU cost is in the GPUs themselves. Electricity is a small fraction
    toast0 · 1789880876 · focus · HN ↗
    > Electricity is a small fraction, and it's not like datacenters are just going to shut down their servers when they're not in use.
    I don't have any insight on modern GPU datacenters, but in decades past, some owned and operated datacenters didn put effort into making sure power management worked because the cost savings were worth it. I'm pretty sure I saw plans to shed load and power off servers if a utility made a demand response request or in case of loss of cooling. I wouldn't be surprised if some owned and operated data centers do regular full shutdowns at off peak... WOL, IPMI or RTC wakeup can bring them back when needed and if you already have a dynamic service orchestrator and setup times are acceptable, why not shut down if there's no actual priority work and there's also no idle priority opportunistic load either...
    huslage · 1789891121 · focus · HN ↗
    No one does this. There is zero value, economic or otherwise, in turning off machines.
    esseph · 1789892505 · focus · HN ↗
    I've never heard of anybody shitting a DC down off peak. Been around 30yr or so.
    > why not shut down if there's no actual priority work and there's also no idle priority opportunistic load either...
    Full shutdown and startup often kills capacitors and used to be dangerous for rotational HDD.
    Sometimes once you turn things off, they simply don't come back on. It happens.
    esseph · 1789950377 · focus · HN ↗
    [delayed]
2. logicallee · 1789878903 · focus · HN ↗
  How much crypto do you think the mentioned 30 GPU years would have produced at current exchange rates? They're not as efficient as ASICs but GPU's can still mine a lot...
  1. monster_truck · 1789882447 · focus · HN ↗
    wouldn't even cover the cost of power and cooling otherwise everyone would still be doin it
3. qurren · 1789879263 · focus · HN ↗
  > it would make more financial sense to mine crypto
  GPUs are power-inefficient for mining most crypto so not necessarily. You may end up paying more in electricity than you are able to mine.
  Most crypto mining is on ASICs now.
  1. aidenn0 · 1789885624 · focus · HN ↗
    You missed the part where they have already pre-paid for the GPU-hours and they pay the same regardless of he electricity used.
    Also, even if they were paying for electricity, they would lose less money mining crypto than factoring RSA numbers.
    schoen · 1789895273 · focus · HN ↗
    Except for the prize money for the RSA challenge contest! Although they'll also need to have Claude invent a time machine.
    upofadown · 1789901092 · focus · HN ↗
    Is someone providing prize money again? RSA ended the contest in 2007.
    schoen · 1789934902 · focus · HN ↗
    Hence the time machine!
4. charlieyu1 · 1789906292 · focus · HN ↗
  Except you can do it with CPUs as well for much cheaper.
blackdahlia313 · 1789876660 · focus · HN ↗
Enjoy the bounty
1. tristanj · 1789877341 · focus · HN ↗
  There is no bounty, RSA labs ended the $75,000 reward in 2007.
  1. qurren · 1789879683 · focus · HN ↗
    There's about 900 BTC remaining for anyone who breaks these keys:
    <a href="https://privatekeys.pw/puzzles/bitcoin-puzzle-tx" rel="nofollow">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 · 1789880473 · focus · HN ↗
    thats 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 · 1789881291 · focus · HN ↗
    There is no script.
    greyface- · 1789884063 · focus · HN ↗
    Of 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>
    <a href="https://en.bitcoin.it/wiki/Script" rel="nofollow">https://en.bitcoin.it/wiki/Script
    tromp · 1789889640 · focus · HN ↗
    Not every bitcoin tx output.
    With taproot (P2TR), scripts are optional, and outputs can be based solely on Schnorr signatures.
    greyface- · 1789890510 · focus · HN ↗
    P2TR outputs have a script that always starts with OP_1. That script may or may not commit to a tapscript.
    LiamPowell · 1789900991 · focus · HN ↗
    You know what I mean, there's no clever on-chain reward script.
    schoen · 1789885584 · focus · HN ↗
    I've recently been working on this exact problem due to my desire to create puzzle challenges for Simplicity, the smart contract programming environment that I work on for my job.
    Since Simplicity runs on Bitcoin-like blockchains, someone can swipe the witness data from the legitimate winner's proposed transaction, and create a new transaction (perhaps with a higher fee) using the same claim data and sending the prize to a different address.
    Anyway, I ended up implementing a two-phase commit mechanism in which you pay a deposit to temporarily lock the prize so that it can only be paid out to your address. If you then make a valid claim, the prize can be paid to you; if you don't, you forfeit your deposit.
    <a href="https://community.simplicity-lang.org/t/running-prize-contests-without-witness-swiping/35/10" rel="nofollow">https://community.simplicity-lang.org/t/running-prize-contes...
    (I think this was suggested by Russell O'Connor, the inventor of Simplicity, but it may have been a widespread idea in the smart contracts world. I don't know whether there's a straightforward way to implement it with Bitcoin Script, which is what this older prize would have needed.)
    zephen · 1789920954 · focus · HN ↗
    I don't claim to know the nuance of what you're trying to address with this.
    Wouldn't it be simpler to simply protect a bitcoin private key with the encryption that you are challenging people to break?
    Off the top of my head, the only downside I can see is that someone could drain the wallet without publishing the key, but people like to brag, so it seems unlikely to be a problem in practice.
    schoen · 1789935195 · focus · HN ↗
    That would work if you were only demonstrating encryption or creating challenges related to encryption, but some challenges don't map very easily to a cipher (though you might be able to get them to map to a cipher key).
    In Simplicity (and in a sense in Bitcoin Script) there's a broader concept of "if you show you know information X, you're entitled to this money", but it has this specific issue that if the information or the entitlement to receive money for knowing it isn't unique to a specific recipient, there will automatically be a witness swiping or front-running risk for architectural reasons.
    gautamcgoel · 1789886580 · focus · HN ↗
    Just to confirm: these puzzles are unrelated to RSA, correct?
    azatom · 1789900617 · focus · HN ↗
    rsa is prime factorization, bitcoin is elliptic curve
    raverbashing · 1789888158 · focus · HN ↗
    Interesting
    I guess it would be "trivial" to have a bounty on each of the future numbers, since you could encrypt a bitcoin private key with it (it would probably make sense to do RSA -> AES key that encodes the BTC private key)
someguydave · 1789877561 · focus · HN ↗
kinda bearish for the data center rollouts if the spare compute can be used to solve math puzzles instead of training LLMs
redox99 · 1789896129 · focus · HN ↗
Quite 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.
1. muglug · 1789909946 · focus · HN ↗
  1 engineer != Anthropic
  1. hinkley · 1789921208 · focus · HN ↗
    [delayed]
2. 0x10ca1h0st · 1789991560 · focus · HN ↗
  I 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.
  1. redox99 · 1789998261 · focus · HN ↗
    Yeah 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.
    treszkai · 1789998871 · focus · HN ↗
    Except customer demand doesn't follow the fixed supply of GPU compute that any company has, so they either a) rent compute on demand, b) sell their excess compute, c) let it sit idle and maybe an employee claims it.
    redox99 · 1790002976 · focus · HN ↗
    I mean tokens for internal use.
vavkamil · 1789897657 · focus · HN ↗
Interesting. Instagram still publishes a 768-bit RSA DKIM key, so I guess factoring it is now just a weekend GPU project?
<a href="https://dns.google/resolve?name=pm._domainkey.instagram.com&type=TXT" rel="nofollow">https://dns.google/resolve?name=pm._domainkey.instagram.com&...
1. functional_dev · 1789902192 · focus · HN ↗
  RSA-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.
  <a href="https://vectree.io/c/how-rsa-key-sizes-map-to-real-security-512-to-4096-bits" rel="nofollow">https://vectree.io/c/how-rsa-key-sizes-map-to-real-security-...
2. natdempk · 1789919477 · focus · HN ↗
  What's the cost estimate to factor this?
gizmodo59 · 1789903496 · focus · HN ↗
You don’t need AI to solve this. Just lots of compute.
Retr0id · 1789904561 · focus · HN ↗
If anyone else has spare GPU hours they don't know what to do with, may I recommend partial hash collisions: <a href="https://github.com/DavidBuchanan314/birthday_party" rel="nofollow">https://github.com/DavidBuchanan314/birthday_party
(The "record" set by me only took about 1 GPU day - easy to beat!)
1. gpugreg · 1789906076 · focus · HN ↗
  Here'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: <a href="https://www.reddit.com/r/crypto/comments/guctw4/finding_sha256_partial_collisions_via_the_bitcoin/" rel="nofollow">https://www.reddit.com/r/crypto/comments/guctw4/finding_sha2...
  1. Retr0id · 1789906403 · focus · HN ↗
    True, I forgot about that! It's more fun when the inputs are printable ascii, though :P
    It should also be easy to beat with just a few GPU weeks.
    gpugreg · 1789913105 · focus · HN ↗
    I agree that ASCII is definitely cooler, for example when personalizing the hashed data as in your example.
speedgoose · 1789904704 · focus · HN ↗
Nice. I will make sure to turn my WiFi box off at night and pee in the shower to compensate the environmental impact of this.
1. tptacek · 1789921039 · focus · HN ↗
  You'd be having approximately the same impact on the climate as the factoring work, so, makes sense.
  1. speedgoose · 1789929617 · focus · HN ↗
    30 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 · 1789915644 · focus · HN ↗
Literally no content here
cmovq · 1789922073 · focus · HN ↗
If anyone is thinking “didn’t someone do RSA-260 a couple weeks ago, that seems like quite a jump”
RSA-260 has 260 digits (862 bits) and RSA-896 has 270 digits.
eugenekolo · 1789924955 · focus · HN ↗
"I work at Anthropic and used idle GPUs running known algorithm to factor a number. I used Claude btw"

Open on Hacker News to reply ↗

Unofficial Hacker News client; not affiliated with Y Combinator.