Comment by posnet | Hacker News Reader

Comment by posnet | Hacker News Reader

Parent Full thread

Just for fun, because it's hard to appreciate how strong a 256bit ECDSA key is.

Base Numbers:

- 2*128 guesses on average

- public state of the art for ECDSA on an FPGA is 1315tps [0]

- retail price of said fpga $10,000 [1]

- total net income for xilinx from advanced FPGAs FY2022 (936M * 0.74 + 879M * 0.72) = 1325M [2]

Ballpark numbers, we'll assume that attacker can buy 10x every FPGA xilinx made in 2022 for a 50% discount and can run them non stop for zero cost.

We'll also assume they have a bunch of secret math geniuses and have a faster ECDSA implementation that can do 1,000,000,000 tps ( or 1,000,000x SOTA)

- (1325,000,000 / 5,000) * 10 = 2,650,000 FPGAs

- 2,650,000 * 100,000,000,000 = 2,650,000,000,000,000tps

- 2*128 / 2,650,000,000,000,000 = 1.28e+23s

- 1.28e+24 / 60 / 60 / 24 / 365 = 4,080,000,000,000,000 years

- ~4 quadrillion years

- or 4x the time until every planet has been ejected from every star system and the sun has cooled to 5K [3]

But why stop there, lets assume that the attacker can use the entire planets GDP to buy chips and has a 1,000,000,000,000,000x faster ECDSA implementation.

- World GDP (2022): 101.3 trillion

- (101,300,000,000,000 / 5000) = 20,260,000,000

- 100,000,000,000,000,000 * 20,260,000,000 = 2.66419e+28tps

- 2*128 / 2.66419e+28 = 12,772,451,173s

- 12,772,451,173 / 60 / 60 / 24 / 365 = 405 years

So even then, we wouldn't see a single BTC key broken within our lifetime.

(Unless you believe that 3 letter agencies have successfully built a quantum computer that practically implement shore's algorithm, in which case you should probably be more worried about the fact that they can break public key encryption globally)

[0]: https://arxiv.org/pdf/2112.02229.pdf

[1]: https://www.colfaxdirect.com/store/pc/viewPrd.asp?idproduct=...

[2]: https://web.archive.org/web/20211203065624/https://investor....

[3]: https://en.wikipedia.org/wiki/Timeline_of_the_far_future

I don't think you understand what I mean. I'm not talking about cracking a key. I'm talking about creating a key from seed 0, then 1, then 2, etc. etc., until you have an index of every possible key.

Then, since you know every possible public key ... it's just a matter of looking up its private key in the index.

HOWEVER, I was off by a few magnitudes on how big the seed numbers get. If you are curious, this is basically the biggest seed number:

904,625,697,166,532,776,746,648,320,380,374,280,100,293,470,930,272,690,489,102,837,043,110,636,675 ...

or 904 trevigintillion (thanks wolfram alpha!)

So, yeah, it's not happening anytime soon, though it doesn't invalidate the premise, just changes the timeline to unachievable with current technology. Technology could improve to the point where it is feasible in a human lifetime.

It would require a break through in quantum stuff, or new laws of physics to produce a 256 bit rainbow table, right?

"Computers made of something other than matter and occupying something other than space"

https://security.stackexchange.com/a/25392

Or ... just generate a few here and there, and eventually, you'll find something. Looks like https://keys.lol is an example of just that.

Where and how do you store your "index"? The number you wrote is multiple orders of magnitude higher than the number of atoms on Earth. It's not simply "not happening any time soon". It's physically impossible.

Good point :)

Edit to add: just found https://keys.lol that does exactly this, but generates a few dozen at a time and doesn't store the results.

This is like saying the Library of Babel[1] contains every book ever written, past present and future. Yes, it's technically true and a fun thought exercise, but it's not a threat to the publishing industry.

[1] https://libraryofbabel.info/

> I'm not talking about cracking a key. I'm talking about creating a key from seed 0, then 1, then 2, etc. etc., until you have an index of every possible key.

Computationally the two are the same: cracking a key generated by a secure algorithm is equivalent to generating all possible keys and checking to see which one matches.

That kind of reminds me of the idea I've heard several times of compression by indexing π. The idea is that every possible finite byte sequence occurs somewhere in π [1] so if you've got some file of N bytes that you want to store you just need to store N and an index to a place in π where that sequence of bytes occurs.

The problem is the the index to the first occurrence of any particular N byte sequence will on average take around N bytes to store so your "compressed" file is about the same size as your input file.

[1] This is not known to be true. A number that has the property that every possible finite sequence of digits in base b occurs in the number's base b expansion is called a "normal number in base b". A number that is normal in base b for all integer bases b ≥ 2 is simply called a "normal number". Almost all real numbers are normal, but it is not known if π is among them.

> Almost all real numbers are normal

Well if we're being picky then I'm going to point out that almost all real numbers cannot be written down.

Of the numbers we can write down in a reasonable way, the computable numbers, we've only proven a relative handful of them to be normal in any base, and barely any normal in all bases.

So if you have an arbitrary irrational number where you can ask if it's normal, then the answer is probably "we don't know, we haven't figured out a proof", rather than "almost certainly". Those overwhelming odds about "almost all real numbers" don't apply to your number, because your number is computable.

> I'm talking about creating a key from seed 0, then 1, then 2, etc. etc., until you have an index of every possible key.

The cracking algorithm talked about earlier is that you create a key from seed 0, 1, 2, etc. until you find a match, and then you can keep going to look for more matches if you so desire. Or you can go in a different order, because the outcome is the same.

The only change in your version is that you don't look for matches until you've finished going through every seed.

That makes your version strictly slower.

It's not invalid, it's just worse, for the use case of cracking existing keys.

And for the use case of cracking keys made after you do most of your computing, you still wouldn't use the "one giant index" method for precomputing things. It's not efficient.

Reply on news.ycombinator.com