Bruteforcing A 12 Word Seed Based On Certain Criteria

[thunter287]

  So I just read a story written by John Cantrell on how he won a Bitcoin in 2020 by searching over 1 trillion mnemonics in 30 hours. Based on what he has written and discussed in that story here are my questions.

   Here is what's known:

    An Electrum wallet was made in April of 2012.
    The public address of the wallet is known.
    6 of the 12 seed words are known (but not the order).
    4 of the remaining seed words are a possible match.

  Given his approach how long would it take if only 6 of the words match, 7 match, 8 match, 9 match or 10 match?

  How much have speeds of the GPU's he used increased since his attempt in 2020?

  What kind of computing power could you realistically rent if you wanted to and how much quicker would the computations be with that rented power?

  What would the cost of what he rented be today? Cost for 10x faster, 100x faster etc...?


   Thanks to everyone for taking the time to read this and help with your replies.  

[hosseinimr93]

Take note that a 12 word seed phrase is safe enough if generated truely randomly.
John Cantrell rented several graphic cards and brute-forced a seed phrase which 8 out of its 12 words were known and only 4 words were missing.

If you know 8 words of a seed phrase with correct places and 4 words are missing, there would be around 1.8 * 10¹³ possible combinations. The number would reduce to around 1.1*10¹², if the seed phrase is BIP39.
If you know 7 words of a seed phrase with correct places and 5 words are missing, there would be around 3.6 * 10¹⁶ possible combinations. The number would reduce to around 2.3 * 10¹⁵, if the seed phrase is BIP39.
If you know 6 words of a seed phrase with correct places and 6 words are missing, there would be around 7.4 * 10¹⁹ possible combinations. The number would reduce to around 4.6 * 10¹⁸, if the seed phrase is BIP39.

Therefore, if John Cantrell knew only one word less (7 words instead of 8 words), it would take around 20000 times more time to brute-force the seed phrase and if he knew two words less (6 words instead of 8 words), it would take around 4.2 million times more time to brute-force the seed phrase.

I think now it should be clear that a 12 word seed phrase is safe enough, if you keep it securely and what you want to acheive is impossible.

[thunter287]

 Is it impossible because the words are out of order? What if 2,3 or 4 of the possible words were correct? What if you rented 10x, 100x, 1,000x the computing power?

[hosseinimr93]

Is it impossible because the words are out of order?

That's impossible, if you know the correct position of those 6 words, let alone without knowing their position.

Is it impossible because the words are out of order? What if 2,3 or 4 of the possible words were correct?

If I got you correctly, you are talking about the case of having 8 to 10 words without knowing their correct position.
If you know 10 words out of 12 words of a BIP39 seed phrase without knowing their position, there would be around 6*10¹³ possible combinations which is around 50 times more than Cantrell's case.

[philipma1957]

Is it impossible because the words are out of order?

That's impossible, if you know the correct position of those 6 words, let alone without knowing their position.

Is it impossible because the words are out of order? What if 2,3 or 4 of the possible words were correct?

If I got you correctly, you are talking about the case of having 8 to 10 words without knowing their correct position.
If you know 10 words out of 12 words of a BIP39 seed phrase without knowing their position, there would be around 6*10¹³ possible combinations which is around 50 times more than Cantrell's case.

Which would mean likely under 3 months time to crack it. With the same power as Cantrell.

So if the wallet had a decent amount of coin in it. say 10 coins or 660,000 usd. Spending 1,000 a day for ninety days makes sense.

But if I read the op correctly he only knows 6 for sure and 4 maybe.

By the way electrum can add extra words and not be 12 it can be 13

I have an electrum with 13 words and the last word is not a standard word from the list.

[ranochigo]

Quick Math:

Total number of permutations without knowing the exact position for 6 letters:

6!*2048^6 = 5.32 x 10^22 before precomputing the valid seeds when respecting the checksum.

You should be able to do a quick estimation for how much longer it would need; by the formula of keys/rate per sec = seconds. GPUs have gotten better at their compute capabilities and they're becoming cheaper but definitely not 10, 100, or a 1000 times. Even if they were to be cheaper and faster, I don't think we would be able to bruteforce it anytime soon.

The rate and the speed depends on how optimized and how small you can narrow your search space.

[NotATether]

Total number of permutations without knowing the exact position for 6 letters:

6!*2048^6 = 5.32 x 10^22 before precomputing the valid seeds when respecting the checksum.

My napkin math is telling me that it would still take months if GPUs could run through 10^6 keys per second (very optimistic estimate) and you had 100 of them, you'd still be at over 10^14 seconds for brute forcing which seems to be in light-years time.

I don't think anyone would be able to afford thousands of the latest GPUs, unless they are an AI company or something.

[nc50lc]

Based on what he has written and discussed in that story here are my questions.

   Here is what's known:

    An Electrum wallet was made in April of 2012.
    The public address of the wallet is known.
    6 of the 12 seed words are known (but not the order).
    4 of the remaining seed words are a possible match.

  Given his approach how long would it take if only 6 of the words match, 7 match, 8 match, 9 match or 10 match?  

The approach would be slightly different.
First of all, the article that you read is about BIP39 seed phase which is different from old Electrum seed before v2.0.
The striking difference is the 1626 wordlist which is a lot smaller than BIP39's 2048 words.

Next is the derivation path which is shorter with "master_private_key/receiving or change/address_index" (e.g.: m/0/0 = 1st address)
than BIP39 which commonly uses either BIP44, 49, 84, etc. which is longer so it requires more HMAC-SHA512 hashes to get to the address_index (e.g.: m/44'/0'/0'/0/0 = 1st address)

So overall, it may be easier than the article only if the factors are the same.
However, with 6 out of 12 words, that could still take a long time depending if the other 4 words are correct.
(I'll leave the math to others)