Father lost his Electrum wallet, and remembers some of the words in the seed

[ileikmath]

Hello all, and thanks to any who are able to help, my father remembers most of the words (say m=10 for example), and I'm fairly certain it was a 12 word seed.

Correct me if i'm wrong, but a 12 word seed has 12 factorial (479001600) possibilities, and since i'm missing two of those words, that leaves the dictionary size squared as roughly 4 million times factor.

I'm familiar with python, and thankfully electrum uses a pretty capable python console. But just generating all permutations killed my program. I redid it in Haskell (NOT A PRO AT HASKELL tho I love what little I know) and was able to generate ~~50GB  list of all permutations in 33 minutes, but still need the 4 million substitutions of words in the dictionary so my plan of just having a text file containing all possible phrase ideas and having python run through that is seemingly less feasible.

I'm familiar with multithreading, tho in C, not python. and have access to a large computer cluster if need be (~~44 CPU cores in one node, 24 cores in the GPU node w/ 4xTesla, and another 48 cores on an AMD node)

Before I go any further, I wanted to check if there was a smarter way of doing this kind of dictionary recovery attack.

Please and thank you for any time spent helping

[1715509850]

1715509850

[1715509850]

1715509850

[1715509850]

1715509850

[1715509850]

1715509850

[o_e_l_e_o]

Does your father know the location of the two missing words? That would cut down the search time massively.

Does your father know the master public key or some of the early addresses which were generated by the seed phrase? If he does, then the quickest way to do this is going to be to use this piece of software: https://github.com/3rdIteration/btcrecover/

It also has multi-device support, so you can split the work across all your available cores.

[NotATether]

Specifically, you need the seedrecover.py script included in this repo. Follow the instructions at https://github.com/3rdIteration/btcrecover/blob/master/docs/Seedrecover_Quick_Start_Guide.md . Make sure you also pip install groestlcoin-hash, and apt install python3-pyopencl for GPU support. If the clusters are running Windows I think you can just install numpy and pyopencl from pip. Then pass --enable-opencl as an argument to seedrecover.py to use the GPUs.

Then give seedrecover.py an address (and how deep it was listed in the electrum window which they call "how many addresses were generated before it"). If you have the master public key use that instead because it's quicker.

Then insert all the words in the seed phrase you remember, in the correct order. You should probably run this on the Tesla node if it's the fastest one.

It also has multi-device support, so you can split the work across all your available cores.

How is this activated? I couldn't find any command line option for specifying IP addresses or servers except for --worker, and that doesn't look like you can pass different server IPs to it.

Correct me if i'm wrong, but a 12 word seed has 12 factorial (479001600) possibilities, and since i'm missing two of those words, that leaves the dictionary size squared as roughly 4 million times factor.

Unfortunately, you are wrong... a 12 word seed has 2048^12 possibilities => 5444517870735015415413993718908291383296 total possibilities (the actual number of valid possibilities is a bit less due to the checksum requirements etc).

But the number of combinations for a twelve word seed with two missing words is 2048**2 = 4194304, but depending on which words were forgotten (they could be in the middle of the phrase, not necessarily at the end, or next to each other), we have to multiply this by 12 nCr 2 = 66, so there are actually 276824064 ways to insert two missing words into a 10 word phrase.

Of course this number is less because of checksums, and even less if the last word is one of the words forgotten, maybe OP can clarify if this is the case.

[HCP]

Correct me if i'm wrong, but a 12 word seed has 12 factorial (479001600) possibilities, and since i'm missing two of those words, that leaves the dictionary size squared as roughly 4 million times factor.

Unfortunately, you are wrong... a 12 word seed has 2048^12 possibilities => 5444517870735015415413993718908291383296 total possibilities (the actual number of valid possibilities is a bit less due to the checksum requirements etc).

It also has multi-device support, so you can split the work across all your available cores.

How is this activated? I couldn't find any command line option for specifying IP addresses or servers except for --worker, and that doesn't look like you can pass different server IPs to it.

The multiple devices don't talk to each other... you provide the --worker argument as "n/m" (ie. --worker 1/5) on each worker and it will divide the password search space up into "m" chunks and assign chunk "n" to that particular worker.

If you watch the demo of using Vast.ai with multiple instances here: https://www.youtube.com/watch?v=8Zqc-2Te3zQ&list=PL7rfJxwogDzmd1IanPrmlTg3ewAIq-BZJ&index=13&t=1220s

You can see him say "they don't communicate at all" and some of the other workers are still running, even when one had found the password.

The written instructions for this demo is here: https://github.com/3rdIteration/btcrecover/blob/master/docs/Usage_Examples/2020-10-06_Multi-GPU_with_vastai/Multi-GPU_with_vastai.md

[bitmover]

Before I go any further, I wanted to check if there was a smarter way of doing this kind of dictionary recovery attack.

Unfortunately, you are wrong... a 12 word seed has 2048^12 possibilities => 5444517870735015415413993718908291383296 total possibilities (the actual number of valid possibilities is a bit less due to the checksum requirements etc).

Is it possible to reduce the dictionary attack range by  brute forcing only combinations that would pass the checksum requirements? Maybe someone already made a program to do that?
It would narrow a bit the possibilities.

[NotATether]

Unfortunately, you are wrong... a 12 word seed has 2048^12 possibilities => 5444517870735015415413993718908291383296 total possibilities (the actual number of valid possibilities is a bit less due to the checksum requirements etc).

Is it possible to reduce the dictionary attack range by  brute forcing only combinations that would pass the checksum requirements? Maybe someone already made a program to do that?
It would narrow a bit the possibilities.

It's a 12 word phrase so there are 4 bits of checksum at the end, that means only 512 * 2048 * 66 valid combinations to search in if the last word is the one lost. The remaining 4 bits can be derived by constructing the checksum.

If the last word is known, you still have to pass the mnemonic through PBKDF2 and then get the first 32 bytes of the SHA256 hash of each BIP39 seed (entropy) of the 2048*2048*66 combinations I mentioned in my previous post, because there is no way to see if the checksum is correct without knowing the SHA256 hash. You can however skip the heavy computation that comes after it for invalid phrases, namely looking for its master public key or address given as input.

[ileikmath]

Thanks so much for the help so far everyone!

Does your father know the location of the two missing words? That would cut down the search time massively.

Probably not, I asked a few hours ago but he still hasn't responded. I doubt it

Does your father know the master public key or some of the early addresses which were generated by the seed phrase?

I doubt it, what's the relation to a master public key to an address? Just finished cross referencing electrum statements with emails and texts, I found the address I believe he owns. It still has an unspent txo fortunately. I'll get started on that soon.

...so there are actually 276824064 ways to insert two missing words into a 10 word phrase.

Ahh, probability theory has humbled me again... Thanks!

My dad gave 5 words with extreme certainty were part of the seed, he gave me 5 more words he said were probably in the seed. I made no assumptions as to which index those words should be placed in the seed. That leaves 2 wild cards still, up to 7 (scary case, haha)

Again, thanks to everyone who has helped, I think I have enough information now to run the btcrecover tool. I'll update if it works

[HCP]

Obviously, the total number of possibilities with 2 missing words is a lot less than the total search space of 12 word seeds... I was simply pointing out that "12 factorial" was not the correct starting point.

Is it possible to reduce the dictionary attack range by  brute forcing only combinations that would pass the checksum requirements? Maybe someone already made a program to do that?
It would narrow a bit the possibilities.

Most of the utilities simply create the combinations dynamically, rather than generating a dictionary of every possible combination first... which is rather wasteful, given it might take only a relatively small number to find the correct one.

So basically, the idea is that you create a given combination, calculate if the checksum is valid and discard the seed mnemonic if it fails... otherwise move on to the more computationally intensive task of actually deriving keys/addresses etc.


At the end of the day... trying to find 2 missing words is actually relatively trivial, regardless of whether the position of the missing words is known, but only if the 10 you already have are in the correct order. A script should be able to find the correct combination of 12 words in a relatively short amount of time.

However, 7 words is going to be, for all intents and purposes, "impossible"... you'd be looking at a timeframe measured in centuries or thousands of years

[pooya87]

My dad gave 5 words with extreme certainty were part of the seed, he gave me 5 more words he said were probably in the seed. I made no assumptions as to which index those words should be placed in the seed. That leaves 2 wild cards still, up to 7 (scary case, haha)

it sounds like the order and position of the 10 words you have is also unknown, which means the number of combinations to check is even larger than initially speculated and it makes it impossible to recover.
do you know how he is recovering these words? for example is it from memory or was it written down or is it a file? there could be other options to recover in different cases which may be easier to look into than trying to brute force what you have at this stage.

[o_e_l_e_o]

My dad gave 5 words with extreme certainty were part of the seed, he gave me 5 more words he said were probably in the seed. I made no assumptions as to which index those words should be placed in the seed. That leaves 2 wild cards still, up to 7 (scary case, haha)

This is probably an impossible task, then, if your father does not know the order of the words.

Unscrambling a 12 word seed phrase in which all the words are known has 12! possibilities = 479,001,600
However, at least two of your words are unknown, so there are 2,048 possibilities for each of those 2 words.
This would put the number of possibilities at 12!*2048*2048 = 2,009,078,326,886,400.

Even splitting this work up between all your available core, best case scenario you are still looking at several years of non-stop computing to crack the seed phrase. If there is any doubt as to the 5 "probable" words, then there is no point in even trying.

If the last word is known, you still have to pass the mnemonic through PBKDF2 and then get the first 32 bytes of the SHA256 hash of each BIP39 seed (entropy) of the 2048*2048*66 combinations I mentioned in my previous post, because there is no way to see if the checksum is correct without knowing the SHA256 hash.

You don't need to use PBKDF2 for this. A single SHA256 hash is all that is needed to calculate the checksum. PBKDF2 is only used on the whole seed phrase as the first step towards generating private keys.

[pooya87]

You don't need to use PBKDF2 for this. A single SHA256 hash is all that is needed to calculate the checksum. PBKDF2 is only used on the whole seed phrase as the first step towards generating private keys.

correct but checksum for Electrum mnemonics are a bit different from BIP39.
the checksum requires computation of HMAC-SHA512 of the mnemonic, if it is using English and is 12 words and since the HMAC key is a small one then it is technically two SHA512 compressions (1x inner pad + mneminic, 1x outer pad + hash of previous round).

[ileikmath]

Even splitting this work up between all your available core, best case scenario you are still looking at several years of non-stop computing to crack the seed phrase. If there is any doubt as to the 5 "probable" words, then there is no point in even trying.

Well.... shit haha. Guess i'm really counting on my father's memory here... never thought I'd be praying on his (probably our (and I mean this as a compliment)) autistic memory.

I just ran seedrecovry.py, thanks for helping me get this far folks, even if it doesn't work. Who knows, maybe I'll get lucky. If it cracks the seed I'm buying everyone here a round, from my man to yall

[o_e_l_e_o]

Well.... shit haha. Guess i'm really counting on my father's memory here... never thought I'd be praying on his (probably our (and I mean this as a compliment)) autistic memory.

He definitely did not write the words down or save them anywhere? He only committed them to memory? And he definitely doesn't have a back up of the wallet file somewhere? An external hard drive? A system image? Make sure you double check, as any of these possibilities are far more likely than recovering the seed from the information you currently have.

Who knows, maybe I'll get lucky.

There's always the possibility that you get lucky and hit the right combination near the start of your search, but similarly there's also the possibility that I pick 12 words at random and they happen to be your father's. I wish you luck, but unfortunately the odds are that you'll spend years looking unless you can narrow down the possibilities with some more info.

[HCP]

Well.... shit haha. Guess i'm really counting on my father's memory here... never thought I'd be praying on his (probably our (and I mean this as a compliment)) autistic memory.

Best of luck to you, but unfortunately, I don't see this having a happy ending

This case is a prime example of why an offline, "physical" backup (ie. writing it down or using a "cryptosteel"-type solution) is the recommended method to backup a 12/24 word seed mnemonic. Hopefully, it might save someone else from the same fate by convincing them that relying on "memory" alone is a "Bad Idea"™

[keychainX]

Hello all, and thanks to any who are able to help, my father remembers most of the words (say m=10 for example), and I'm fairly certain it was a 12 word seed.

Correct me if i'm wrong, but a 12 word seed has 12 factorial (479001600) possibilities, and since i'm missing two of those words, that leaves the dictionary size squared as roughly 4 million times factor.

I'm familiar with python, and thankfully electrum uses a pretty capable python console. But just generating all permutations killed my program. I redid it in Haskell (NOT A PRO AT HASKELL tho I love what little I know) and was able to generate ~~50GB  list of all permutations in 33 minutes, but still need the 4 million substitutions of words in the dictionary so my plan of just having a text file containing all possible phrase ideas and having python run through that is seemingly less feasible.

I'm familiar with multithreading, tho in C, not python. and have access to a large computer cluster if need be (~~44 CPU cores in one node, 24 cores in the GPU node w/ 4xTesla, and another 48 cores on an AMD node)

Before I go any further, I wanted to check if there was a smarter way of doing this kind of dictionary recovery attack.

Please and thank you for any time spent helping

if you have 7 out of 12 words, it will take approximately 1 year on a 10x 1080TI rig to find the missing five (from own experience)

So if the wallet is big enough its worth it. If you are missing 4 or 3 words or less, then its a piece of cake.
/KX

[o_e_l_e_o]

if you have 7 out of 12 words, it will take approximately 1 year on a 10x 1080TI rig to find the missing five (from own experience)

Genuine question: Are GTX 1080 Tis actually that fast? 5 missing words gives 2048^5 combinations, which would work out at checking 114 million possibilities per second per graphics card. I appreciate that many of those will have an invalid checksum and can immediately be discarded, but with even only 1/16th with a valid checksum, that's still 7.125 million seed phrases that it has to pass through PBKDF2 and derive an address for.

I suppose you could half all those numbers if you are looking at the 50% solved average benchmark, but even then, that seems a bit fast to me.

Still, that all rests on the fact that you know the order of the words. In OP's case, where he doesn't know the order of the words, then everything becomes significantly more difficult, to the point of impossibility.

[NotATether]

if you have 7 out of 12 words, it will take approximately 1 year on a 10x 1080TI rig to find the missing five (from own experience)

Genuine question: Are GTX 1080 Tis actually that fast?

As btcrecover uses OpenCL for GPU acceleration, OpenCL benchmarks show that a single 1080 Ti has a Geekbench score of 60898. (https://browser.geekbench.com/opencl-benchmarks) It says that a Core i3-8100 running the same tests would get a score of 1000, so however long the key searching operations take on that Core i3, are about 60.898x faster on a 1080 Ti. So e.g. while slightly faster than an i3-8100, a single thread in my Xeon E31240 searches 2183867 combinations in 128 seconds. So, it wouldn't be unreasonable to expect a 1080 Ti to search that amount in 128/60.898 = 2.1 seconds.

By contrast, an RTX 3090 has a score of 203093. That makes it 3.335x faster than the 1080 Ti. For the same number of combinations it'll take about 0.63 seconds.

Clustering more GPUs together of course only speeds up the search linearly, and you can only cluster so many under a budget.

[o_e_l_e_o]

So, it wouldn't be unreasonable to expect a 1080 Ti to search that amount in 128/60.898 = 2.1 seconds.

When you say "search", do you mean simply generate 2 million combinations, do you mean generate 2 million combinations and derive the first address for the ones with a correct checksum, or do you mean generate millions more combinations and derive the first address for the 2 million or so with the correct checksum?

And even if you mean the last case (i.e. the most efficient case), that is still only deriving the first address for 1 million combinations per second, whereas when looking at keychainX's numbers you would need to be over 7 times faster than that.

[NotATether]

So, it wouldn't be unreasonable to expect a 1080 Ti to search that amount in 128/60.898 = 2.1 seconds.

When you say "search", do you mean simply generate 2 million combinations, do you mean generate 2 million combinations and derive the first address for the ones with a correct checksum, or do you mean generate millions more combinations and derive the first address for the 2 million or so with the correct checksum?

And even if you mean the last case (i.e. the most efficient case), that is still only deriving the first address for 1 million combinations per second, whereas when looking at keychainX's numbers you would need to be over 7 times faster than that.

My numbers are for when btcrecovery generates 2 million combinations and then derives the first address for the ones with the correct checksum (the first case).

I don't know how btcrevocery works internally but I assume for each "phase" with a progress bar, it only checks the checksum and derives the first address for the number of combinations listed at the left. My 2 million figure was pulled from one such phrase for a seed with two words omitted similar to the OP's.

[keychainX]

if you have 7 out of 12 words, it will take approximately 1 year on a 10x 1080TI rig to find the missing five (from own experience)

Genuine question: Are GTX 1080 Tis actually that fast? 5 missing words gives 2048^5 combinations, which would work out at checking 114 million possibilities per second per graphics card. I appreciate that many of those will have an invalid checksum and can immediately be discarded, but with even only 1/16th with a valid checksum, that's still 7.125 million seed phrases that it has to pass through PBKDF2 and derive an address for.

I suppose you could half all those numbers if you are looking at the 50% solved average benchmark, but even then, that seems a bit fast to me.

Still, that all rests on the fact that you know the order of the words. In OP's case, where he doesn't know the order of the words, then everything becomes significantly more difficult, to the point of impossibility.

Its a custom c code, no python github lib repo...