PuzzlePuzzle
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
MethodMethod
(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[1]
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! ↩
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.
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:
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.
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.
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.
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.
Had to record a video of the output during search.
Still going at 64 million unordered combinations so far, no end in sight.
I miscalculated, it's 12 times worse 🤣
For every combination of 12 unique words, there are 479,001,600 permutations, not 39,916,800.
Also, you are right: he meant that 10 of the words are four letters or longer.
view on twitter.comOuch.
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:
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 2972From those 602 words, there are some words with too many
ms orts. 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 2833I didn't see a mention of 547 in the linked post. Could it have been 574?
Totally could have been 574.
Hold up, wait a minute:
I see how you are thinking, but...
If
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 containingzit will remove the wordbreeze.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
breezeis not a problem because it would be removed anyway.What do you think?
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:
(emphasis mine)
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.
These are fun because it proves that even given a considerable amount of information, it’s very difficult to crack a seed phrase
This isn’t a puzzle, it’s a brute forcing race. Good luck.
Yeah, I thought maybe he was making it doable by really shrinking the list, but it is not the case.
Crowdsource=victory
There is only 1
jin the puzzle picture.There are only 6 words on my reduced list that have a
jand 2 of these have atin them.Now if the one seed word that has a
jin it happens to be one of the j-words that also has at, our word list suddenly goes down to 186 words...If the j-word is
justthe only q-word on the list that works isequipUPDATE: 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 useSince there is only one
q, the q-word isquitBut there is also only one
tand we used it up in this word, so the list should remove all other words that have atBut now I must pay attention to my kids. Hopwle this helps somebody solve it.
I really want you find the answer. It's interesting to read the way you're thinking
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.
Rate limited :/ And here i was, happy, thinking nitter was back...
Sorry, it's dead, I have to remove this automated comment
Another hint:
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 :)