2
$\begingroup$

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 - 8) = 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 - 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

$\endgroup$
9
  • $\begingroup$ I am sorry, but 2^47 combinations which then have to be passed into further SHA512 and THEN this has to be converted into BTC address which has to be checked on the actual blockchain to see if such address is actually valid - this is a no-no. If you had the last word, it would severely simplify the problem. But this is unrealistic $\endgroup$
    – michnovka
    Apr 26, 2019 at 22:46
  • $\begingroup$ @michnovka If you read the entire post, I have the BTC address so it would not have to be checked on the "actual blockchain". It would be helpful if you could provide the reasons you think this is the case (e.g. my math is wrong). Thanks. $\endgroup$
    – JGoodwin10
    Apr 27, 2019 at 19:44
  • $\begingroup$ ok, so assuming you have the public BTC address: the 2^47 combinations is true. This many times you will need to calculate SHA256 to get the checksum 8 bits. Then lookup this many times the words from dictionary, since BIP0039 works with the string, not bytes. After you have this, then you do SHA512 with 2048 iterations - but problem is you are hashing the UTF-8 "sentence", so the hashes/seconds is sth you will have to figure out experimentally. But after that, you will also have to do BIP0032 to get the actual BTC address and this I believe is another SHA512. $\endgroup$
    – michnovka
    Apr 27, 2019 at 19:59
  • $\begingroup$ @michnovka I appreciate your help, however I think I need someone with more experience/expertise to answer my question. Do you have any suggestions for who I could contact? $\endgroup$
    – JGoodwin10
    Apr 27, 2019 at 20:46
  • 1
    $\begingroup$ no matter who you ask for help, the problem is that ASIC sha512 is not where your journey ends. as I said, first you need sha256 to get checksum 8 bits. then lookup to translate bip0039 to words. even tho simple task, there is no ASIC for that. then sha512 to get seed. and then another sha512 to get the final private/public keypair. The main issue will be connecting the 4 tasks and this is where I see potential bottleneck. and while my experience/expertise may be low, I can guarantee you will not get anywhere near 10GH/s with 30k USD budget. Good luck. I feel the despair with you $\endgroup$
    – michnovka
    Apr 27, 2019 at 21:26

3 Answers 3

3
$\begingroup$

When you say that you have lost the last 5 words, are they completely gone or just difficult to read or invalid?

If you use a 48 vCPU Linode VPN, you can use BTCRecover can be used to recover 3 completely missing words in 6 hours, 4 missing words in about a 1.5 years. 24th word is actually just a checksum, so it isn't really missing...

I have a YouTube video on how to use BTCRecover and will be releasing one in the future that looks at the limits for 3-4 missing words, etc.

BTCRecover doesn't currently support using a GPU, but if that were implemented, that could easily speed things up by a factor of 10 and bring a 4 word recovery into a manageable time frame.

Either way moore's law in on your side, so you may just have an enforced 10 year HODL. Don't throw out the 24 word seed and keep the public addresses and their derivation paths that you know about. (keeping an xpub for a known account is even better)

$\endgroup$
1
  • $\begingroup$ As correctly stated in the Q, 8 bits of the 24th word are checksum, but the other 3 aren't. Also you probably meant VPS not VPN -- a VPN wouldn't be much help in computing lots of hashes. $\endgroup$ May 10 at 1:29
3
$\begingroup$

My understanding is that a BIP39 seed is created by applying a PBKDF2 function where the 24 word mnemonic is the password (in UTF8 format), the salt is the string "mnemonic" again in UTF8, iteration count is 2048, 512 bit key and hash is SHA512.

Using the random example of "nation west blush exhibit elbow knee bubble strong imitate romance frown enter garlic solution life wall copper van orchard doctor vicious vocal similar climb" I get a seed of ec5c51803e36768e1b37be744ca7d0b7f18f3a64f8d6323e149b5331a92bb3aa13c04034a3753b6957c014d7e0da6a2ca26d97471fa59f4ccc201f75d6a23c8b (I used the PBKDF2 option in CyberChef to generate this). You can verify this is the correct application of BIP39 by trying it on an online BIP39 generator (e.g. https://bip49.com/)

I would then suggest you use either hashcat or JohntheRipper to generate PBKDF2 hashes. I haven't tried JohntheRipper but it's definitely an option on hashcat. You would need to set up some sort of rule using the 19 words that you have as a fixed input for the password and then appending every permutation of the other 5 words from a customised wordlist being the BIP39 wordlist. I believe hashcat can do this with the right rule but haven't tried it myself.

Your question suggests you are only looking for a way to generate all the possible hashes, which I think the above should do.

You will of course need to check each hash against whatever information you already have. I believe BIP32 prescribes how to turn that seed into all the public addresses etc. Hashcat won't help you with this but there is source code in GitHub for BIP32 so it shouldn't be too difficult to build an engine that will generate whatever address you need to generate from all of those hashes and then test that against the address that you have.

I hope that helps and good luck!

$\endgroup$
3
$\begingroup$

Your back of the napkin calculation of the number of required sha-512 is correct, but you're missing a crucial point : To verify if your seed matches your address you also need :

  • An Eliptic curve multiplication, which you will not be able to do with ASICs/FPGA, only GPU.
  • A Sha256
  • A Ripemd160

In one line : address = ripemd160(sha256(ec_mult(pbkdf2_sha512_2048("utf8 seed"))))

I work on proprietary seed phrase recovery tool running on GPU farms so I can give you a few additional data points :

  • The max speed you can reach while bruteforcing seeds on a 4090 is ~350M/sec (of which you actually only run ~1.5M because only 1/256 seeds is checksum valid on 24 words) - This is with custom assembly code squeezing the most out of the GPU on both the sha-512 and the EC multiply phase.
  • With that speed, bruteforcing the full range costs around 4.5k USD.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.