2
$\begingroup$

Of course this is a question with an answer that is due to evolve.

A 2002 paper about TWIRL stated that the cost would be around 10M\$ and an other 10M\$ to manufacture the device. A later 2007 paper claimed to have improved the design and created an actual FPGA, though at that time they were still used special bus rather than PCIe.

After that, RSA laboratories stopped their bounties, and research slowed, and no serious paper later seems to have explored the cost of factoring a 1024‒bits RSA modulus in the last 15 years.

Even if you can today rent 500,000 PCIe Xilinx on AWS, I’m noticing all the latest records for RSA numbers were performed on pure CPU implementations with the latest 1 being on CADO-NFS. Their creators stated that GPUs wouldn’t be of help in any parts because it would break it’s capacities to abort early on unnecessary cases.

Question :

What would be the price to factor something like

0xdc4e445b69fe9483216d0fa85492b4656287bfb2fb4da5b65f0b86cc2c073f3ee24a038d3d0e88c78b722b466c5ca1c89792c368ed182a5a13df919cac7fe335173cd04f23769d5ef027290f34a86e8fcab014f1a19d395b0662c5c52424a38796dd6f2394047d716abb6f48cc46abee6e2be3168348b456d5878cbec0b57d0f

today in order to forge signatures without considering labor designs costs outside the case of the ASIC ?

And with which setup (pure CPU or FPGA or ASIC) would be the less costly to achieve it if rented ?

Disclaimer :

I was just offered a 10% of damage bounty that I agree to share by a casino should I prove with details the feasibility to break the modulus above in the span of a few months.

$\endgroup$
8
  • $\begingroup$ 10% of stolable funds represent 20Ethers worth currently 60,000$ but they state the contrary that it’s 1 ETH. In details, they thought they would still be protected by changing their 1024‑bits ᴠʀꜰ keys/contracts every 4/6 months or so and they will now upgrade their key length. But they will only pay on serious demonstration that attacking them for predicting bets within the given timeframe and for less than ~240Ether would be possible (no need however to actually do it). $\endgroup$ Commented Feb 19 at 1:11
  • 2
    $\begingroup$ Do you have a source for the "500,000", or/and other brand of FPGAs for rent at AWS or other? I think your question is interesting, and on topic when formulated as e.g. how could a 1024-bit RSA modulus be most economically factored using existing hardware publicly available for rent? Again I'm less comfortable with the designated modulus and the bounty aspect, whatever exactly it is; and stating your motivation or putting a disclaimer in the body of the Q is not needed. But so far, nobody voted to close your Q. $\endgroup$
    – fgrieu
    Commented Feb 19 at 8:28
  • 1
    $\begingroup$ @fgrieu based on an article only available in my language fr.wikipedia.org/wiki/…. Of course you d have to stack up several pc like servers, but the true is today fpgas can be rented like gpus at many locations/providers (I recall to had see a 12 fpgas per server). I m also interested in the non publicly available asic case should manufacturing costs with running costs appears to be the cheapest solution. The casino is disputing it** but my point with rental hardware is the cost to use more available fpgas≈cost to use use less fpgas for longer. $\endgroup$ Commented Feb 19 at 8:46
  • $\begingroup$ @fgrieu though, there appears to exists reasons about why all the latest/largest records were obtained on cpus only implementations so that fpgas might be a slower and costly case than using gpus. $\endgroup$ Commented Feb 19 at 8:54
  • $\begingroup$ Well, I did a small test a while ago, however, I did not account the memory. When the $n$ increases the memory requirement is also increased to increase the success. This is why you may not see GPUS and standard FPGAs. I need to test further. $\endgroup$
    – kelalaka
    Commented Feb 19 at 20:36

1 Answer 1

2
$\begingroup$

No serious paper later seems to have explored the cost of factoring a 1024‒bits RSA modulus in the last 15 years.

There are at least two things you would probably be interested in.

The Factoring as a Service paper explores your exact question, but for 512-bit RSA keys. In particular, they found in 2015 that this could be done in 4 hours using \$75 worth of cloud compute. Importantly, this paper includes code, that you could perhaps tinker with to try to get some estimate for 1024-bit RSA.

The second is the factorization of RSA-250. This is only 829 bits, and was performed in 2700 core years (on Intel Xeon Gold 6130 CPUs). Some set (potentially all, I have not checked) of the participants of that distributed computation wrote this paper. Section 1.4 is probably of interest to you. I'll (selectively) quote

it is widely accepted that 1024-bit factoring and discrete logarithm are feasible now, with hardware and software that currently exist. A ballpark estimate is that factoring a 1024-bit key would be about 200 times harder than RSA-250, or around 500,000 core-years of computation.

Nobody has done such a computation yet in public, since academic research teams don’t have access to that much computing power. From an academic standpoint, carrying out such a computation would not surprise the research community.

I'll leave for you to optimize the following estimate, but applying the above ballpark to the cost of rental of Xeon Gold 6130's from this random site gives me an estimate of $\approx$ $\\\$3.5$ billion to do the factorization. So well within the capabilities of a nation state, but much larger than the (conjectural) cost of a few dozen tens of millions for Twirl. That being said, the above estimate (and progress on integer factorization records) has been relative to hardware that actually exists, so may be a more reliable estimate. I'm the wrong person to say though.

$\endgroup$
1
  • $\begingroup$ But such numbers arre only for ᴄᴘᴜ and place the costs well above those of twirl (20 milliions) even when adjusted for Inflation. Do you mean twirl was wrong 22 years ago ? $\endgroup$ Commented May 18 at 11:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.