19 out of 24 words of BIP39 passphrase (brute-force last 5?)

[JGoodwin10]

I have managed to lose 5 words of my 24 word Ledger Nano S recovery phrase. I have words 1-19 but I am missing words 20-24.
I have significant holdings on the wallet so would very much like to recover it if possible.
The passphrase is a BIP39 mnemonic (see https://github.com/bitcoin/bips/blob/master/bip-0039.mediawiki).
I have the bitcoin and ethereum public addresses for this mnemonic. I am wondering if it's feasible to brute force the passphrase.

Each word is 11 bits (2^11 = 2048 possible words).
The last (24th) word of the passphrase is of the following form [3 random bits][8 bit checksum].
Therefore I only have to check 2^(55 - = 2^47 = 1.4x10^14 combinations.
I would have to compute SHA-512-HMAC with an iteration count of 2048.
As far as I understand, that means I'd have to compute 1.4*10^14 * 2048 = 2.87*10^17 hashes in total.

Is there any hardware out there designed for this? I am aware of ASICs that compute sha-256 hashes but not sha-512 hashes.
Perhaps I could tweak one to work with sha-512 since they are very similar.

Assuming a fairly typical ASIC hashrate of 1TH/s (10^12 hashes per second), I could exhaust the search space in 2.87*10^5 = 287000 seconds = 3.3 days. I'd probably get there sooner, of course (expected 1.65 days). Time is not something I am worried about. Even if I have to wait months, I don't mind - so if I can get 10GH/s at a reasonable price, that would be great.

I would really appreciate any help/information you could provide to help me out and make sure I haven't missed anything.
I could also use GPUs for this (I calculate I can run them at roughly $1/10TH/s - so it would cost me $28.7k to exhaust the search space, which I will do if there are no cheaper options).

Many thanks,
James

[NotFuzzyWarm]

Is there any hardware out there designed for this? I am aware of ASICs that compute sha-256 hashes but not sha-512 hashes.
Perhaps I could tweak one to work with sha-512 since they are very similar.

No tweaks are possible with an ASIC-based miner because the SHA256D algo is hard coded into the chips and cannot be changed.

Oh and fyi these days 'typical' ASIC-based BTC miners run well over 13THs and the latest run over 70THs.

[JGoodwin10]

Is there any hardware out there designed for this? I am aware of ASICs that compute sha-256 hashes but not sha-512 hashes.
Perhaps I could tweak one to work with sha-512 since they are very similar.

No tweaks are possible with an ASIC-based miner because the SHA256D algo is hard coded into the chips and cannot be changed.

Oh and fyi these days 'typical' ASIC-based BTC miners run well over 13THs and the latest run over 70THs.

Thanks very much for the info. Do you know if there are any ASICs that compute SHA512 hashes?
Good to know typical miners run so fast! I wonder how these chips are designed and if one could be 3d-printed.

[gt_addict]

Is there any hardware out there designed for this? I am aware of ASICs that compute sha-256 hashes but not sha-512 hashes.
Perhaps I could tweak one to work with sha-512 since they are very similar.

No tweaks are possible with an ASIC-based miner because the SHA256D algo is hard coded into the chips and cannot be changed.

Oh and fyi these days 'typical' ASIC-based BTC miners run well over 13THs and the latest run over 70THs.

Thanks very much for the info. Do you know if there are any ASICs that compute SHA512 hashes?
Good to know typical miners run so fast! I wonder how these chips are designed and if one could be 3d-printed.

You want to 3d print a silicon chip? 

[JGoodwin10]

Is there any hardware out there designed for this? I am aware of ASICs that compute sha-256 hashes but not sha-512 hashes.
Perhaps I could tweak one to work with sha-512 since they are very similar.

No tweaks are possible with an ASIC-based miner because the SHA256D algo is hard coded into the chips and cannot be changed.

Oh and fyi these days 'typical' ASIC-based BTC miners run well over 13THs and the latest run over 70THs.

Thanks very much for the info. Do you know if there are any ASICs that compute SHA512 hashes?
Good to know typical miners run so fast! I wonder how these chips are designed and if one could be 3d-printed.

You want to 3d print a silicon chip? 

Just looking for a solution, whatever that may be

[Lucius]

JGoodwin10, just for info, are you the same person who asked this question 2 years ago?

I know that some users manage to find / brute force one or two missing words from seed, but I am not sure is it possible to get 5 missing words. Maybe fact that you know the exact sequence of words and that you have your public address can make the job easier, but you should wait for answer from a technically experienced user (HCP).

Did you try to do anything with : https://github.com/gurnec/btcrecover

[JGoodwin10]

JGoodwin10, just for info, are you the same person who asked this question 2 years ago?

I know that some users manage to find / brute force one or two missing words from seed, but I am not sure is it possible to get 5 missing words. Maybe fact that you know the exact sequence of words and that you have your public address can make the job easier, but you should wait for answer from a technically experienced user (HCP).

Did you try to do anything with : https://github.com/gurnec/btcrecover

No I am not. This individual seems to have had only 5 words, whereas I have 19 words and I am missing 5. I haven't tried btcrecover yet since based on the math I've done, it doesn't seem like a feasible option.

It would be great if a technically experienced user could provide some insight. Do you have any suggestions for who would be a good person for this?

[Lucius]

I asked about this link because this user is also have in mind to divide his seed in identical way as you do, 19+5 words. You are unfortunately lost 5 words from your seed, so it seems that you use similar backup - but in case of such sensitive information one backup is never enough.

I write that some more technically experienced user maybe can give you some better advice, and I mentioned user HCP. He is usually active in this part of the forum, so it is only a matter of time when he will notice this thread.

[o_e_l_e_o]

-snip-

Correct me if I'm wrong, but if he knows his master public key he could simply compare the generated key to his known key and stop after step 2. Similarly, if he knew the first address this wallet generated, he wouldn't need steps 4 or 5, as he could simply generate the address and check it against the entered address without having to perform a check for balance or continue down n more addresses.

[HCP]

I think the original calcuation of "1.4x10^14 combinations" is probably about right.

As the OP correctly identified a large percentage of combinations are invalid, because the mnemonic checksum will fail before you even get as far as calculating keys. That is to say, for a given set of 23 words... it seems that only around 8 (3 bits) out of the 2048 words in the BIP39 word list will actually be a "valid" 24th word.

The 'btcrecover' script can probably be leveraged as a starting point... although from memory I think it will only find up to 2 or 3 missing words at the most. If OP is sure that they have the first 19 words and needs to "only" find the final 5... well, it'll still take a "long" time. 3 missing words and I would have said you might have been "OK"... 4 and you'd be looking at a time measured in months if not years.

I dug up my old hacky script (find_missing_seed_word.py) that allows you to specify the words you know and put an 'x' in for missing words. On my system it seems to be able to "find" valid seeds (not even generating keys etc) at a rate of around 1,000,000 in 7-8 minutes... Granted, it probably isn't the most optimised script (it has file writes for logging etc) as my python skills are pretty poor, but it should be "ballpark"

Given the total possible number of valid seeds to find when missing 5 words is around 1.4*10^14... I think it'll take "quite a while"^[1] at that rate to go through all the valid seeds



[1] Some rough maths suggests that will be something like ~1864 years.

[JGoodwin10]

I think the original calcuation of "1.4x10^14 combinations" is probably about right.

As the OP correctly identified a large percentage of combinations are invalid, because the mnemonic checksum will fail before you even get as far as calculating keys. That is to say, for a given set of 23 words... it seems that only around 8 (3 bits) out of the 2048 words in the BIP39 word list will actually be a "valid" 24th word.

The 'btcrecover' script can probably be leveraged as a starting point... although from memory I think it will only find up to 2 or 3 missing words at the most. If OP is sure that they have the first 19 words and needs to "only" find the final 5... well, it'll still take a "long" time. 3 missing words and I would have said you might have been "OK"... 4 and you'd be looking at a time measured in months if not years.

I dug up my old hacky script (find_missing_seed_word.py) that allows you to specify the words you know and put an 'x' in for missing words. On my system it seems to be able to "find" valid seeds (not even generating keys etc) at a rate of around 1,000,000 in 7-8 minutes... Granted, it probably isn't the most optimised script (it has file writes for logging etc) as my python skills are pretty poor, but it should be "ballpark"

Given the total possible number of valid seeds to find when missing 5 words is around 1.4*10^14... I think it'll take "quite a while"^[1] at that rate to go through all the valid seeds



[1] Some rough maths suggests that will be something like ~1864 years.

Thanks for the insightful response. I guess I would have to wait for hardware to get significantly better for it to be feasible. Maybe in 10 years time I guess it's the ultimate HODL.

[ABCbits]

-snip-

Correct me if I'm wrong, but if he knows his master public key he could simply compare the generated key to his known key and stop after step 2. Similarly, if he knew the first address this wallet generated, he wouldn't need steps 4 or 5, as he could simply generate the address and check it against the entered address without having to perform a check for balance or continue down n more addresses.

You're right, but normally people don't store his master public key. Generate address might be needed if he never send Bitcoin (which means none of public key never revealed).

But if he store any of address generated by Ledger Nano S, he can skip step 4 which significantly reduce required time (since you don't need to wait for API reply from bitcoind or blockchain explorer.

[HCP]

But if he store any of address generated by Ledger Nano S, he can skip step 4 which significantly reduce required time (since you don't need to wait for API reply from bitcoind or blockchain explorer.

As per the OP:

I have the bitcoin and ethereum public addresses for this mnemonic.

No need for blockchain lookups or API calls...

[Lucius]

I guess I would have to wait for hardware to get significantly better for it to be feasible. Maybe in 10 years time I guess it's the ultimate HODL.

Is there any chance that you find the lost words without brute-force them? I know you say that you lost them, but are you sure they are irretrievably lost or you can not find them right now? If you do not mind to share where / how you store this backup? Maybe somebody can help you with advice, and may also help someone else to not make the same mistake.

[JGoodwin10]

I guess I would have to wait for hardware to get significantly better for it to be feasible. Maybe in 10 years time I guess it's the ultimate HODL.

Is there any chance that you find the lost words without brute-force them? I know you say that you lost them, but are you sure they are irretrievably lost or you can not find them right now? If you do not mind to share where / how you store this backup? Maybe somebody can help you with advice, and may also help someone else to not make the same mistake.

They are irretrievably lost. The details are not important.

[Coding Enthusiast]

I dug up my old hacky script (find_missing_seed_word.py) that allows you to specify the words you know and put an 'x' in for missing words. On my system it seems to be able to "find" valid seeds (not even generating keys etc) at a rate of around 1,000,000 in 7-8 minutes... Granted, it probably isn't the most optimised script (it has file writes for logging etc) as my python skills are pretty poor, but it should be "ballpark"

If all you do is check if a set of words is a valid BIP-39 seed then it should not take more than half a minute* for 1 million keys not 7-8 minutes even without optimization. You are basically doing a SHA256 on a 264 bit input (entropy) so it is only 1 rounds of block mixing under the hood.
* The value is based on my test on 1 CPU core on a corei3 CPU with c# code of my own writing. With some SHA256 optimization, with parallelization (using all the cores) and some other optimization of the code the time can be reduced to less than 5 seconds for 1 million variations.

[HCP]

Like I said... not very optimised! 

It's a python script... that builds up a 24 word mnemonic (from a given pattern of form "word1 word2 word3 ... word 19 x x x x x")... it then attempts to check that it is a valid mnemonic. If no exception is thrown by that function, it assumes it is a valid mnemonic.. and writes the mnemonic to a file.

I would expect that there is some significant savings to be made if custom coding and just doing the checksum calculation etc as opposed to using library functions that actually do the full conversion to a hex seed and relying on exception catching... and of course the writing out to a file is technically unnecessary at this point, but I was modifying existing code as opposed to starting from scratch... and well... #lazy 

Indeed, by cutting out a lot of the unnecessary and "time expensive" code (and without trying to custom write the checksum code), I got it down to under 2 minutes for 1,000,000 mnemonics... not too bad for a lazy "weekend warrior" coder  


Still even at 5 seconds for 1,000,000 mnemonics... you're going to be looking at ~20 years just to find the valid mnemonics... and then you have the conversion to hex seed + address generation/checking

Not outside the realms of possibility... so, I'd guess it's "a loong time"... rather than "a loooooooong time"

[Bram24732]

JGoodwin10 - I tried to contact you via message but you have an anti spam filter on, so I'll post this here.

I do have the software and GPU access to bruteforce a 19/24 mnemonic for about 4.5k USD of resource usage (I run a seed recovery business) - So let me know if this is something that might be of interest to you.
Happy to demo the tool and it's speed on a 20/24, for instance.

[hZti]

JGoodwin10 - I tried to contact you via message but you have an anti spam filter on, so I'll post this here.

I do have the software and GPU access to bruteforce a 19/24 mnemonic for about 4.5k USD of resource usage (I run a seed recovery business) - So let me know if this is something that might be of interest to you.
Happy to demo the tool and it's speed on a 20/24, for instance.

And for to tell that you created a new account?

To me it seems like you dont want to post this reply with your real forum account simply because you will use any opportunity to scam the OP if he does really give you the first 19 words of his seed. If you really want to be helpful you can just explain how it is possible to brute force the seed. The computing power that is needed can then simply be rented by the OP and therefore he will be at no risk at all of losing his funds.

[Bram24732]

JGoodwin10 - I tried to contact you via message but you have an anti spam filter on, so I'll post this here.

I do have the software and GPU access to bruteforce a 19/24 mnemonic for about 4.5k USD of resource usage (I run a seed recovery business) - So let me know if this is something that might be of interest to you.
Happy to demo the tool and it's speed on a 20/24, for instance.

And for to tell that you created a new account?

To me it seems like you dont want to post this reply with your real forum account simply because you will use any opportunity to scam the OP if he does really give you the first 19 words of his seed. If you really want to be helpful you can just explain how it is possible to brute force the seed. The computing power that is needed can then simply be rented by the OP and therefore he will be at no risk at all of losing his funds.

The reason it's a new account is simply because I never posted here before - I don't have a "main" account.

As I said, I run a seed related business and part of that business consists in writing highly optimized code for those use cases, which I monetize. I know by experience that trust is paramount, which is why one of the first things I do when I talk to a potential customer is dox myself - I'm somewhat traceable so it helps with credibility.
Of course I could tell OP how to solve his problem but he seems to already know what needs to be done to bruteforce the five remaining words. If he did not solve it by himself already given the monetary incentive to do so, it means he might need help. I happen to have the optimized code and the resources to do it, so I'm offering it.

I know the crypto space is filled with scams, so caution is warranted. That's why I was proposing to show I'm legit.