102 sats \ 9 replies \ @shafemtol 16 Mar \ on: 100k sat prize for solving bitcoin seed phrase puzzle bitcoin
I've managed to enumerate all possible word combinations (unordered) of the reduced set of the 3- and 4-letter (not truncated) words. There are apparently 1110 of them. Each one of these then needs to be tested for all its permutations (there are 39916800 for each of the combinations with no duplicate words). So from these there are up to ~40 thousand million seeds to test. Of these, 1 in 16 will pass the 4-bit checksum and need a more expensive test to match it against the published address.
I do still believe, however, that the actual seed includes longer words, in which case the possible word combinations (unordered) are possibly hundreds of thousands.
After optimizing the search function to achieve a speedup of several orders of magnitude, I'm currently running it against the full wordlist.
It's even worse than I thought. So far it's found more than 20 million possible unordered combinations, and there's a lot more to go. It's crazy to watch all the results scrolling across the screen.
reply
So far I've found ~1000 million matching unordered combinations, still far from complete. Search is returning about 1 million new combinations per minute.
There was a new hint published giving what is presumably the master public key:
zpub6rW2NmPTbNjFkng8Do79zp4zkstGtaCont5drCZCbPfNuQsVU6N8Qguf8PmoYKaDoJtgH8Dehvk6ukGbBzHKyEYrZUeuS1zvn8BNcGEH6tj
Currently I'd estimate an exhaustive search of all permutations of all possible word combinations to take at least 2^67 SHA-512 operations. The expected number of operations needed to find the correct seed would be half that, i.e. at least 2^66 operations.
For comparison, mining a single Bitcoin block currently takes about 2^78 SHA-256 operations. That's up to 4000 times as many operations. That's with specialized hardware, and SHA-256 might take a little less work compared to SHA-512, and the prize is higher, currently at least 6.25 BTC.
So finding the seed is probably doable, but not cost-effective at a 100k sat prize.
reply
You are a beast. It's amazing that there are so many combinations even with 5 or 6 letters of the alphabet removed.
He probably should have come up with a seed phrase that didn't have any e's and a couple other popular letters. Might have made it doable.
Looks like we should take up mining instead of random puzzles on twitter.
reply
One potentially real case would be one in which a Cryptosteel or equivalent has broken apart and scattered the individual letters, leaving only a few initial letters from each row still intact. That would result in a much smaller search space.
reply
I modified the search function to search a random, representative subset of the search space, so that the total number of valid 12-word sets can be accurately estimated without an exhaustive search.
In 133 CPU-minutes I searched 1/10,000 of the space. My original goal of an exhaustive search would thus have taken 924 CPU-days, so I'm not going to attempt that.
The search returned got 67,672,354 unique 12-word sets that match the scrambled letters. That means the total number of unique matching 12-word sets is about 677 thousand million. Each one of these sets has 479 million possible permutations. That gives a total of 324 million million million possible word sequences. Of these, 1 in 16 will pass the 4-bit SHA-256 checksum, making a valid mnemonic. Each valid mnemonic must have its master private key derived, which involves 2048 iterations of HMAC-SHA512.
The expected number of SHA-512 operations required to find the correct private key is around 21 thousand million million million, or 2^74. That is comparable to the work currently required to mine a Bitcoin block, about 2^78 SHA-256 operations.
For comparison, given 24 unique words of a 24-word mnemonic in random order, the expected number of SHA-512 operations required to find the correct private key is 2^85, i.e. 2000 times higher.
So my conclusion remains: Finding the seed is probably doable with specialized hardware, but it is nowhere near cost-effective at a 100k sat prize even discounting the hardware cost.
reply
Had to record a video of the output during search.
Still going at 64 million unordered combinations so far, no end in sight.
reply
I miscalculated, it's 12 times worse 🤣
For every combination of 12 unique words, there are 479,001,600 permutations, not 39,916,800.
reply
Also, you are right: he meant that 10 of the words are four letters or longer.
reply
Ouch.
reply