Topic: Bruteforce partial electrum seed words (Read 378 times)

Yes, I have prepared a new release: https://github.com/PawelGorny/lostword/releases/tag/v0.8.0
Now it works with a candidates on the given positions, for example:

FWIW if I comment out the mnemonic to BIP32 seed part and just validate the checksums of each permutation in FinderOuter, it can perform ~7.2 million checks per second on my corei3 CPU.

---

I should point out that the reason why the overall mnemonic recovery option is slow is because the algorithm that comes after checksum validation is expensive (to derive the child keys), and also there is an issue with my implementation of Elliptic Curve Cryptography that puts a lot of pressure on GC slowing down the process.

I couldn't understand the problem. Say you have 7.txt with 10 seed words. You just need two more words to make 12 word seed. After lotta combination and permutations and filtering bad seeds and getting final address and looking up on blockchain for utxo. Is that what you are doing?

There are couple of questions
1. Is each file corresponds to one wallet?
2. Do you know the positions of missing seed words in each file?
3. Are these 12 word mnemonic seeds or 15 or 24? (If they are 15 words or more and your answer to 2 is no then you can lose all hopes to crack them, most probably.)

If you can answer that, they it's kinda easy to comeup with bruteforce solutions...

OOPS... I had accidentally left in the "to_seed()" call... which takes the mnemonic and generates the actual seed... including the computationally expensive code:

If I comment that part out... it runs "a little bit" faster


~3secs for 10,000... or ~200,000/minute... just goes to show how "expensive" the "ENT to seed" process can be!

That's the problem with using a library to brute force, they are not designed to be the most efficient. They are just optimized to perform one operation in reasonable time. From a quick look this part is being repeated pointlessly and it has obvious expensive processes such as the memory lookup even if it is a binary search, the conversion between the words and bits, working with strings, unnecessary checks,...
https://github.com/trezor/python-mnemonic/blob/master/mnemonic/mnemonic.py#L126-L156

What you want to do is to first convert all your words to their binary representation without having any memory issues.
13 file * 10 word each * 4 byte to hold bits = 520 byte total
Now you create the permutation of these bits and compute their hashes. Working with integers is significantly faster than working with strings.

Which would probably be true if you had a pre-existing list of all the seed word permutations and/or seed value...

But I ran into memory issues attempting to pre-compute everything, so it has to generate each permutation, then attempt to convert it to a seed while checking the checksum etc... I'm sure the way the algorithm is generating the seed permuations is probably pretty poor. It's basically just iterating some lists.

The "library" I'm using for testing the validity of the mnemonic itself should not be too bad, it's the "to_entropy()" function from the Trezor "python-mnemonic" code: https://github.com/trezor/python-mnemonic/blob/master/mnemonic/mnemonic.py#L125

But I'm sure there are probably ways to make that more efficient.


For what it's worth... the script finished overnight:
21hrs and "found" 1,049,432 valid seeds


interestingly... the last 12.5 million or so seed permutations didn't create any valid seeds:
I guess the limited number of words available in position 12 just didn't make any valid checksums with the other available words!

Did you have time to do that?
Thanks!

The seed is 13 words from the English dictionary of electrum 2.0.3 version.

It could also be a BIP39 seed with a one-word BIP38 password.  OP did not clarify if each file corresponds to a word in the seed so it's possible that the order is also unknown and this is no different from having one file full of words.

Actually, we don't even know which wordlist is used which makes a big difference if the seed phrase is for a custom wordlist (otherwise I would not see the point of having a file full of BIP39 or Electrum words  )
 

Ultra modern processors (AMD Ryzen/ anything using Zen microarchitecture and Intel ice lake 10xxx and later) have hardware accelerated SHA256 instructions which you can call from C using the __asm__ keyword: SHA256RNDS2, SHA256MSG1 and SHA256MSG2.

If you are ONLY validating the checksum of each permutation then your speed must be in the millions per second rate. 10k is way too low for that because essentially you are just computing SHA256 (for BIP39) or SHA512 (for Electrum) and your CPU is capable of computing millions per second of these hashes. Translating your code to C shouldn't change much about its speed because the slowness is most probably in the algorithm you are using not the language.

If I'm understanding what you're writing... you have something like:

- possible_word1(list of ~4-10 words)
- possible_word2(list of ~4-10 words)
- possible_word3(list of ~4-10 words)
...
- possible_word12(list of ~4-10 words)

and from the sounds of it, you actually 13 words? so, this is the "old" electrum seed format?

Anyway, assuming just 12 words for now, your possible seed combinations are: #word1_words * #word2_words * #word3_words * ... * #word12_words. Doesn't sound like much, until you do the math... even with "best case" of just 4 possible words in each position... that's 4^12 or 16,777,216 permutations.

Rough experience tells me that around ~6% of those will be "valid" (ie. the checksum matches)... so you're looking at something like ~1,006,632 "valid" seeds that you'd need to check for a match against your public address.


Anyway, I wrote a quick python script that takes in 12 files named 1.txt, 2.txt, 3.txt, ..., 12.txt (for my demo, each file has only 4 words) and then just iterates through the words in each position... it generates over 10,000 seeds/minute... and is finding (as expected) slightly more than 6% of those to be "valid".

So, at ~10k seeds/minute... maybe ~1677 minutes to go through the full search space (only 4 words per slot, 12 slots)... which is around 28hours.

The main slow downs will be:
- More words in a given position... that's going to ramp up the total search space
- Actually generating private keys/addresses to check, as these are computationally a lot slower than just checking if a seed is valid.

With some optimisation, and maybe porting to C or something faster than Python, you'd probably gain some performance benefits... I'm sure it's in the realms of reality to be able to do it within a matter of days? It really depends on how big your search space is... what are the exact number of words you have in each position?

The option is found under "Missing mnemonic" and you have to select the "Electrum" type from the second drop  down on the right, then select the wallet type that Electrum was using from the drop down that appears after that. Make sure to enter the correct BIP32 path. Example 6 and 7 are Electrum mnemonics missing 1 and 2 words respectively.


A couple of points:
* Electrum mnemonics are 12 words by default
* You have to know the position of the missing word. But if it is only 1 word you can manually change the position from start to end and click Find 12 times, it should all take 12 seconds.
* You have to know a derived child from that wallet (it can be a child private key, public key or an address)
* Setting the path correctly is very important. When setting the wallet type (Electrum mnemonic type) FinderOuter automatically sets the correct path for that type but you have to enter the index of the child key you entered (eg. if you entered the 10th address you have to add 9 to the end of the path)

OK, I will try to do this tomorrow.

Yes, I know the public address.

Do you know the addresses you are looking for?
I think I could change my https://github.com/PawelGorny/lostword to implement solver of your problem, but it all makes no sense if you do not know what you are looking for.

Well you could do it in Linux but i'm using JavaScript mostly.
You can also use NodeJS or Python.
Node is build on Chrome's V8 JavaScript engine. 

You can also just type the words into a hardcoded array that would be the easiest way so you can omit the filereader.
Then you can use a library like bitcoinjs or jsbtc either one will work.
All the functions are readily available.

Here are some examples for bitcoinjs-lib: https://github.com/bitcoinjs/bip39 <--- i prefer this one
You can see here some examples for jsbtc: https://github.com/bitaps-com/jsbtc/blob/master/test/jsbtc.test.js

I thought about doing that, but I don't know how to do it (newbie in Linux..).
1. How to make a combined text to be checked? note that I have 13 text files, each text file has a different word list.
2. How to check the text with all the possible seeds?