100k sat prize for solving bitcoin seed phrase puzzle twitter.com/asanoha_gold/status/1768551394749944252

1116 sats \ 29 comments \ @Scoresby 16 Mar bitcoin

Puzzle

On Twitter, Asanoha has posted a challenge worth 100k sats to unscramble some letters into a 12 word seed phrase.

It's a little unclear from the first tweet, but he has a couple hints that explain

the weird characters mean nothing.
the letters in the picture are all the letters used in the seed phrase.
it's the BIP-39 seed word list

Method

(I was working on this while feeding three super-hyper kids, so I may have missed some details, but I'm posting what I've done so far in case it's helpful to anyone, because I think I'm not gonna be able to work on it much more.)

I started by looking to see what letters were not present in the puzzle picture. They are

b d k l r v w x z

I downloaded the BIP-39 word list and removed all the words that contained the above letters. This leaves you with 366 words¹

access account accuse acoustic act action again age agent aim among amount ancient announce antenna antique aspect asset assist assume asthma atom auction august aunt auto autumn cactus cage camp can cannon canoe captain case cash casino cat catch caught cause caution cement census champion change chaos chase chat cheap cheese chef chest chief choice choose cinnamon coach coast coconut coffee coin come comic common connect cost cotton couch cousin cup cushion custom cute east echo egg eight emotion enact engage engine enhance enough equip escape essence estate ethics face faint faith fame famous fan fashion fat fatigue fee fence fetch fiction fine finish fish fit fitness foam focus fog foot fun gain game gap gas gasp gate gauge genius genuine ghost giant gift goat goose gossip guess gun hat height hen high hint hip home hope host huge human hunt ice icon image imitate immense immune impact impose inch income infant inject inmate innocent input insane insect intact into issue item jeans join juice jump just machine magic magnet main man manage mango mansion mass match math mean meat mechanic mention menu mesh message mimic minimum minute miss mom moment month moon mosquito motion mountain mouse much muffin museum music must name nation nest net nice night noise nominee nose note nothing notice nut ocean off office often omit once one onion open opinion oppose option output pact page panic pass patch path patient pause peace peanut peasant pen pet phone photo piano picnic piece pig pigeon pipe pitch poem poet point position post potato punch push put quantum question quit quote safe same satoshi sauce sausage scan scene scheme science scout sea season seat section segment sense sentence session setup shaft shift shine ship shoe shoot shop siege sight sign since sing situate smooth snap sniff soap soft someone song soon soup south space spice spin spoon spot staff stage stamp state stem step sting stomach stone stuff success such suggest suit sun sunset suspect sustain tag tape taste tattoo teach team ten tenant tennis tent test that theme then thing this thought time tip tissue toast toe tomato tone tongue tonight tooth top topic toss tuition tuna unique unit upon upset usage use

I'm assuming because some letters are repeated in the puzzle picture, all the letters used in the seed phrase are shown in the picture, meaning the 12 word seed phrase has 46 characters. They are

pqnieoeuoeheisfppspmecsacaosohegntigujgpeiafss

Now, the goal is to take my 366-word list and check it to see if there is some twelve word combination that matches 46 characters and that repeats each character as many times as is shown in the puzzle picture. I'll post a comment if I figure out how to do this.

FractalEncrypt said he got the list of words down to 547 and I'm not at all sure why he got that number of words. He's a pretty smart guy, so I think I may have screwed something up in my reasoning. Nevertheless: onward! ↩

view all related items

102 sats \ 9 replies \ @shafemtol 16 Mar

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.

34 sats \ 5 replies \ @shafemtol 17 Mar

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.

602 sats \ 2 replies \ @shafemtol 18 Mar

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.

10 sats \ 1 reply \ @Scoresby OP 18 Mar

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.

34 sats \ 0 replies \ @shafemtol 18 Mar

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.

0 sats \ 0 replies \ @shafemtol 19 Mar

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.

0 sats \ 0 replies \ @shafemtol 17 Mar

Had to record a video of the output during search.

Still going at 64 million unordered combinations so far, no end in sight.

34 sats \ 1 reply \ @shafemtol 17 Mar

I miscalculated, it's 12 times worse 🤣

For every combination of 12 unique words, there are 479,001,600 permutations, not 39,916,800.

10 sats \ 0 replies \ @Scoresby OP 17 Mar

Also, you are right: he meant that 10 of the words are four letters or longer.

https://twitter.com/asanoha_gold/status/1769146084817809702

0 sats \ 0 replies \ @Scoresby OP 17 Mar

Ouch.

68 sats \ 5 replies \ @shafemtol 16 Mar

Looks like you've made an error when filtering the words. The wordlist first needs to be truncated to the first 4 characters before filtering:

All of the first four, and three, letters of each word are what I have provided.

From that, I get 602 valid words:

SCRAMBLED=pqnieoeuoeheisfppspmecsacaosohegntigujgpeiafss
wget https://raw.githubusercontent.com/bitcoin/bips/master/bip-0039/english.txt
cut -c 1-4 <english.txt | grep -E "^[$SCRAMBLED]+$" | wc
    602     602    2972

34 sats \ 1 reply \ @shafemtol 16 Mar

From those 602 words, there are some words with too many ms or ts. These can also be filtered, resulting in 574 possible words:

cut -c 1-4 <english.txt | grep -E "^[$SCRAMBLED]+$" | grep -Ev 'm.*m|t.*t' | wc
    574     574    2833

FractalEncrypt said he got the list of words down to 547 and I'm not at all sure why he got that number of words.

I didn't see a mention of 547 in the linked post. Could it have been 574?

0 sats \ 0 replies \ @Scoresby OP 16 Mar

Totally could have been 574.

10 sats \ 2 replies \ @Scoresby OP 16 Mar

Hold up, wait a minute:

I see how you are thinking, but...

There are 10 four letter words and 2 three letter words

Means that all the seed words are 4 letters or less, then I can do it the way I did it.

If it means that 10 of the seed words are 4 letters or more, you are right.

EXPLANATION:

If no seed word contains z, and I filter the whole 2048 list removing all words containing z it will remove the word breeze.

Now, this is a problem if he meant that in his puzzle he only gave us the first four letters of the seed words and some of the seed words are words that are longer than 4 letters.

But, if he meant that none of the seed words were longer than 4 letters, removing breeze is not a problem because it would be removed anyway.

What do you think?

17 sats \ 1 reply \ @shafemtol 16 Mar

There are 10 four letter words and 2 three letter words

That is ambiguous. I do however believe that what is meant is that those words are four letters long only after truncation, from the sentence that follows:

All of the first four, and three, letters of each word are what I have provided.

(emphasis mine)

0 sats \ 0 replies \ @Scoresby OP 16 Mar

Yes that darn first makes it seem like you are right.

But in my ignorance I'm going to see if I can come up with 12 words the way I was doing it. Might get an answer and be wrong, but I think I can do it fairly quickly.

44 sats \ 0 replies \ @WeAreAllSatoshi 16 Mar

These are fun because it proves that even given a considerable amount of information, it’s very difficult to crack a seed phrase

17 sats \ 1 reply \ @frostdragon 17 Mar

This isn’t a puzzle, it’s a brute forcing race. Good luck.

0 sats \ 0 replies \ @Scoresby OP 17 Mar

Yeah, I thought maybe he was making it doable by really shrinking the list, but it is not the case.

17 sats \ 0 replies \ @grayruby 16 Mar

Crowdsource=victory

10 sats \ 4 replies \ @Scoresby OP 16 Mar

There is only 1 j in the puzzle picture.

There are only 6 words on my reduced list that have a j and 2 of these have a t in them.

Now if the one seed word that has a j in it happens to be one of the j-words that also has a t, our word list suddenly goes down to 186 words...

10 sats \ 3 replies \ @Scoresby OP 16 Mar

If the j-word is just the only q-word on the list that works is equip

11 sats \ 2 replies \ @Scoresby OP 16 Mar

UPDATE: 10 of the words are four letters and 2 are 3 letters long. This reduces my list to 126 words, which are:

act age aim atom aunt auto cage camp can case cash cat chat chef coin come cost cup cute east echo egg face fame fan fat fee fine fish fit foam fog foot fun gain game gap gas gasp gate gift goat gun hat hen high hint hip home hope host huge hunt ice icon inch into item join jump just main man mass math mean meat menu mesh miss moon much must name nest net nice nose note nut off once one open pact page pass path pen pet pig pigeon pipe poem poet post push put quit safe same scan sea seat ship shoe shop sign sing snap sniff soap soft song soon soup spin spot stem step such suit sun unit upon use

10 sats \ 1 reply \ @Scoresby OP 16 Mar

Since there is only one q, the q-word is quit

But there is also only one t and we used it up in this word, so the list should remove all other words that have a t

But now I must pay attention to my kids. Hopwle this helps somebody solve it.

0 sats \ 0 replies \ @030e0dca83 16 Mar

I really want you find the answer. It's interesting to read the way you're thinking

10 sats \ 2 replies \ @nitter 16 Mar

Twitter2Nitter

Clearnet: nitter.privacydev.net

Nitter is a free and open source alternative Twitter front-end focused on privacy and performance. Click here for more information.

0 sats \ 1 reply \ @Putrick 16 Mar

Rate limited :/ And here i was, happy, thinking nitter was back...

0 sats \ 0 replies \ @nitter 26 Mar

Sorry, it's dead, I have to remove this automated comment

0 sats \ 0 replies \ @shafemtol 18 Mar

Another hint:

@LaserEyesLeah I assumed no repeated words to make it easier to code. I found 565 sets of words that are scrambles of the given letters. Each of these 565 sets has 479 million possible orders. It is crackable but someone would have to be highly motivated.

@asanoha_gold Replying to @LaserEyesLeah No repeated words! Thank you for checking! What do you think the reward would have to be to make it worth it?

I take this to mean that there are 12 unique words, no duplicates. That seems to reduce the number of unordered combinations by approximately 20 to 40 percent.

Also, someone tell LaserEyesLeah they need to check the truncated forms of longer words as well, blowing the number 565 up by a factor of several million :)

Puzzle

Method

Footnotes