Reading this makes me wonder how probable/improbable it is that this kind of thing has happened / will happen with the seed generation function in one of the popular Bitcoin hardware wallets.
And what the fallout would be.
And what the fallout would be.
Over the last 22 months, Unciphered has been working on a vulnerability which affected BitcoinJS, a popular package for the browser based generation of cryptocurrency wallets, as well as products and projects built from this software. Over a period of years, this vulnerability caused the generation of a significant number of vulnerable cryptocurrency wallets.
But now that pension funds get into Bitcoin, one has to wonder what would happen if a giant like Coinbase turns out to be holding their funds in cold storage but with guessable keys.
As Android wallets were the easiest to use wallets and exchanges routinely robbed people, it mattered a lot even back then.
While Coinbase has a quite good protocol for securing keys, what's scary to me is that so many ETFs are trusting it to be the only key holder instead of using multi-signature wallets between multiple entities (like Fidelity and Unchained capital as the other 2).
I know they state that they do it via a custodian and name it like "Coinbase", but is that really all? All they got is an IOU from Coinbase? Maybe they have more specific setups?
Bitcoin isn’t that safe to hold value in, if you might be targeted by someone with brains and money.
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
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.
"Computers made of something other than matter and occupying something other than space"
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.
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.
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.
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.
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.