Print Page - Math problem regarding recovery seed

Title: Math problem regarding recovery seed
Post by: BldSwtTrs on January 05, 2019, 12:59:41 AM

Hi,

I have a math problem regarding my recovery seed for the Ledger Nano S.

There are 24 words. I have written down the 24 words. But as an encryption method, I have inverted the position of two of these words, two times.

I thought I know eaxctly whose of those words were inverted, but apparently this is not the case because when I enter the words in the order that I thought would be correct, this is not a valid seed.

So you could say I am very stupid, but anyway, let's work with that.

So I have 24 words. 20 words are in the right position, and 4 words are in the wrong position. I don't know which words are in good position and which words are in a bad position.

How many possibilities there are?

Title: Re: Math problem regarding recovery seed
Post by: achow101 on January 05, 2019, 01:36:23 AM

What do you mean by "inverted the position of two of those words, two times"? How exactly you did that will affect the number of possibilities (as some orderings could be ruled out).

The upper bound to this is (24 choose 4) * 4! = 255024. (24 choose 4) is the number of ways you can choose 4 items from a set of 24 elements. 4! is the number of ways you can order those 4 elements. This is a multiplication since for each way you can choose 4 items, there are 4! ways you can rearrange them.

Title: Re: Math problem regarding recovery seed
Post by: BldSwtTrs on January 05, 2019, 02:01:23 AM

Quote from: achow101 on January 05, 2019, 01:36:23 AM

Let's say the seed is:
Word1 Word2 Word3 Word4 Word5 Word6 Word7 Word8 Word9 Word10 Word11 Word12 Word13 Word14 Word15 Word16 Word17 Word18 Word19 Word20 Word21 Word22 Word23 Word24

Well, my "encryption" technique was to write in that order:
Word1 Word23 Word3 Word21 Word5 Word6 Word7 Word8 Word9 Word10 Word11 Word12 Word13 Word14 Word15 Word16 Word17 Word18 Word19 Word20 Word4 Word22 Word2 Word24

So I switched Word2 <> Word23 and Word21 <> Word4

But when I try to revert that, this doesn't work. So I must have screwed up somewhere. My hypothesis is that I have inverted the "wrong" words, but I don't know which ones.
The inversion should have been made in a symetrical position, like in my example.
But since I screw up, maybe I have switched words in a non symetrical position.

Title: Re: Math problem regarding recovery seed
Post by: BldSwtTrs on January 05, 2019, 02:24:02 AM

I am not sure exactly what I did either...

I have 24 words, I am pretty sure there are correct.

I am also pretty sure most of them are in the right position. Only few of them, probably 4, are not in a correct position, because I used to move the position of 4 words for my "encryption" .
But now I don't know which 20 words are in the right position. I think the fact that there is 20 words in the right position, even if we don't know which, allows to greatly reduce the number of combination.

Title: Re: Math problem regarding recovery seed
Post by: pooya87 on January 05, 2019, 04:02:39 AM

Quote from: achow101 on January 05, 2019, 01:36:23 AM

(24 choose 4) is the number of ways you can choose 4 items from a set of 24 elements. 4! is the number of ways you can order those 4 elements.

it can not be 4! because after choosing the 4 words there is no difference between changing the position of (1 with 2) and (2 with 1). the number of possible combinations are 7:
1234
2134
3214
4231
1324
1432
1243

the number of possibilities can be further reduced if we exclude cases like swapping Word5 and word6 (two consecutive words)

Title: Re: Math problem regarding recovery seed
Post by: achow101 on January 05, 2019, 05:23:16 AM

Quote from: pooya87 on January 05, 2019, 04:02:39 AM

it can not be 4! because after choosing the 4 words there is no difference between changing the position of (1 with 2) and (2 with 1). the number of possible combinations are 7:

Indeed. This reduces the number of possibilities to 74382. This is definitely brute forceable in probably a few minutes at most.

Title: Re: Math problem regarding recovery seed
Post by: Coding Enthusiast on January 05, 2019, 05:35:02 AM

Code:

namespace SeedCracker
{
    class Program
    {
        static void Main(string[] args)
        {
            string origin = "adjust concert sun teach sting ivory dentist increase hammer snake abandon loyal poem write tiger manage earth win slot weird rapid flat believe rhythm";
            string[] words = origin.Split(' ');

            for (int i = 0; i < words.Length; i++)
            {
                for (int j = i + 1; j < words.Length; j++)
                {
                    string[] clone1 = (string[])words.Clone();
                    string temp = clone1[i];
                    clone1[i] = clone1[j];
                    clone1[j] = temp;

                    for (int k = i + 1; k < words.Length; k++)
                    {
                        if (k == j)
                        {
                            continue;
                        }
                        for (int m = k + 1; m < words.Length; m++)
                        {
                            if (m == j)
                            {
                                continue;
                            }
                            string[] clone2 = (string[])clone1.Clone();
                            string temp2 = clone2[k];
                            clone2[k] = clone2[m];
                            clone2[m] = temp2;

                            string origNew = string.Join(' ', clone2);

                            // Pass origNew to your BIP39 to get the BIP32 out of it
                            // Use m/44'/0'/0' as path
                            // Check the privatekey/publickey/address of index 0,1,2... (depending on what you have) against the result
                            // Print seed if equal and break out of the loop. 
                        }
                    }
                }
            }
            Console.ReadLine();
        }
    }
}

The original seed that I changed was (randomly generated using https://iancoleman.io/bip39/):

Code:

adjust concert sun rapid sting ivory dentist increase write snake abandon loyal poem hammer tiger manage earth win slot weird teach flat believe rhythm

The total count of this loop is 31878 and the correct seed was found after 16729 iterations.
It takes about 20 minutes to find the correct answer but it may be reduced if the code was optimized (which mine isn't).
The commented part above is like this:

Code:

using CryptoCurrency.Net;
using CryptoCurrency.Net.BIPs;
using CryptoCurrency.Net.Coins;
using CryptoCurrency.Net.Cryptography.Hashing;
/**snipped***/
using (BIP0039 bip39 = new BIP0039(origNew, coin: new Bitcoin())
{
   using (BIP0032 bip32 = bip39.ToBip32())
   {
        BIP0032Path path = new BIP0032Path("m/44'/0'/0'");
        PrivateKey[] pks = bip32.GetPrivateKeys(path, startIndex:0, count:1, step:1);
        if (pks[0].ToBytes() == pkBytesThatUserEnteredInTheBeginning)
        {
            Console.WriteLine($"Your correct seed is: {origNew}");
        }
        pk.Dispose();
        break;
   }
}

I took this part out because it is using my own library (CryptoCurrency.Net) which I have not released yet so you wouldn't be able to use it. But the first part should give you the idea of how to do it with any library or in any programming language.
The bottlenecks are the following:
- The PBDK inside of BIP39 (mine is optimized so it is fast)
- The calculations inside BIP32:
* If it is based on one private key they are only BigInteger math so can be pretty fast (mine is fast)
* If it is based on public key then they are based on modular asthmatics that is used for EC multiplication which can be slow (here is the slowest part).
* If it is based on address then it is limited by the speed of encoding (base58 or bech32)

Title: Re: Math problem regarding recovery seed
Post by: dlystyr on January 05, 2019, 06:56:05 AM

Thanks for the useful post Coding Enthusiast, I look forward to the Net library release.

I would merit you if I could!

Title: Re: Math problem regarding recovery seed
Post by: khaled0111 on January 05, 2019, 04:41:20 PM

Coding Enthusiast (https://bitcointalk.org/index.php?action=profile;u=879277) can you explain more, please, how did you find that there are 31878 possibilitie!

Here is what I got:
number of possible combinations: 24!/(24-4)! = 10626

for each combination there is 4 possibilities to find the right order:
10626*4 = 42504
what you got is:
10626*3 = 31878

Did I miss something!!

Edit: I got it ,sorry, since the first order we have in each combination should be removed then remains only 3 permutation possibilities.
Thank you for the code.

Title: Re: Math problem regarding recovery seed
Post by: KingZee on January 07, 2019, 06:28:49 PM

Quote from: BldSwtTrs on January 05, 2019, 02:01:23 AM

Quote from: achow101 on January 05, 2019, 01:36:23 AM

I know I'm late to the party with Coding Enthusiast showered with merits. I hope he helped you get your key back, because if he didn't :

I don't see how there are that many combinations unless he bruteforced every possible permutation of 4 from 24, which is roughly 331776 possibilities (minus repetitions I guess.)

If I strictly follow the way you switched up your words :

You swap every word with its symmetrical other word.
You swap exactly 2 words.

This will HUGELY reduce the number of possibilities, but don't take my word for it :

http://jsfiddle.net/gu2809ht/

I wrote this in 5 minutes and didn't bother to make an output in html (sorry), so press run and open your console and you'll see the output :

Code:

Word24 Word23 Word3 Word4 Word5 Word6 Word7 Word8 Word9 Word10 Word11 Word12 Word13 Word14 Word15 Word16 Word17 Word18 Word19 Word20 Word21 Word22 Word2 Word1
Word24 Word2 Word22 Word4 Word5 Word6 Word7 Word8 Word9 Word10 Word11 Word12 Word13 Word14 Word15 Word16 Word17 Word18 Word19 Word20 Word21 Word3 Word23 Word1
Word24 Word2 Word3 Word21 Word5 Word6 Word7 Word8 Word9 Word10 Word11 Word12 Word13 Word14 Word15 Word16 Word17 Word18 Word19 Word20 Word4 Word22 Word23 Word1
Word24 Word2 Word3 Word4 Word20 Word6 Word7 Word8 Word9 Word10 Word11 Word12 Word13 Word14 Word15 Word16 Word17 Word18 Word19 Word5 Word21 Word22 Word23 Word1
Word24 Word2 Word3 Word4 Word5 Word19 Word7 Word8 Word9 Word10 Word11 Word12 Word13 Word14 Word15 Word16 Word17 Word18 Word6 Word20 Word21 Word22 Word23 Word1
Word24 Word2 Word3 Word4 Word5 Word6 Word18 Word8 Word9 Word10 Word11 Word12 Word13 Word14 Word15 Word16 Word17 Word7 Word19 Word20 Word21 Word22 Word23 Word1
Word24 Word2 Word3 Word4 Word5 Word6 Word7 Word17 Word9 Word10 Word11 Word12 Word13 Word14 Word15 Word16 Word8 Word18 Word19 Word20 Word21 Word22 Word23 Word1
Word24 Word2 Word3 Word4 Word5 Word6 Word7 Word8 Word16 Word10 Word11 Word12 Word13 Word14 Word15 Word9 Word17 Word18 Word19 Word20 Word21 Word22 Word23 Word1
Word24 Word2 Word3 Word4 Word5 Word6 Word7 Word8 Word9 Word15 Word11 Word12 Word13 Word14 Word10 Word16 Word17 Word18 Word19 Word20 Word21 Word22 Word23 Word1
Word24 Word2 Word3 Word4 Word5 Word6 Word7 Word8 Word9 Word10 Word14 Word12 Word13 Word11 Word15 Word16 Word17 Word18 Word19 Word20 Word21 Word22 Word23 Word1
Word24 Word2 Word3 Word4 Word5 Word6 Word7 Word8 Word9 Word10 Word11 Word13 Word12 Word14 Word15 Word16 Word17 Word18 Word19 Word20 Word21 Word22 Word23 Word1
Word1 Word23 Word22 Word4 Word5 Word6 Word7 Word8 Word9 Word10 Word11 Word12 Word13 Word14 Word15 Word16 Word17 Word18 Word19 Word20 Word21 Word3 Word2 Word24
Word1 Word23 Word3 Word21 Word5 Word6 Word7 Word8 Word9 Word10 Word11 Word12 Word13 Word14 Word15 Word16 Word17 Word18 Word19 Word20 Word4 Word22 Word2 Word24 
Word1 Word23 Word3 Word4 Word20 Word6 Word7 Word8 Word9 Word10 Word11 Word12 Word13 Word14 Word15 Word16 Word17 Word18 Word19 Word5 Word21 Word22 Word2 Word24
Word1 Word23 Word3 Word4 Word5 Word19 Word7 Word8 Word9 Word10 Word11 Word12 Word13 Word14 Word15 Word16 Word17 Word18 Word6 Word20 Word21 Word22 Word2 Word24
Word1 Word23 Word3 Word4 Word5 Word6 Word18 Word8 Word9 Word10 Word11 Word12 Word13 Word14 Word15 Word16 Word17 Word7 Word19 Word20 Word21 Word22 Word2 Word24
Word1 Word23 Word3 Word4 Word5 Word6 Word7 Word17 Word9 Word10 Word11 Word12 Word13 Word14 Word15 Word16 Word8 Word18 Word19 Word20 Word21 Word22 Word2 Word24
Word1 Word23 Word3 Word4 Word5 Word6 Word7 Word8 Word16 Word10 Word11 Word12 Word13 Word14 Word15 Word9 Word17 Word18 Word19 Word20 Word21 Word22 Word2 Word24
Word1 Word23 Word3 Word4 Word5 Word6 Word7 Word8 Word9 Word15 Word11 Word12 Word13 Word14 Word10 Word16 Word17 Word18 Word19 Word20 Word21 Word22 Word2 Word24
Word1 Word23 Word3 Word4 Word5 Word6 Word7 Word8 Word9 Word10 Word14 Word12 Word13 Word11 Word15 Word16 Word17 Word18 Word19 Word20 Word21 Word22 Word2 Word24 
Word1 Word23 Word3 Word4 Word5 Word6 Word7 Word8 Word9 Word10 Word11 Word13 Word12 Word14 Word15 Word16 Word17 Word18 Word19 Word20 Word21 Word22 Word2 Word24
Word1 Word2 Word22 Word21 Word5 Word6 Word7 Word8 Word9 Word10 Word11 Word12 Word13 Word14 Word15 Word16 Word17 Word18 Word19 Word20 Word4 Word3 Word23 Word24
Word1 Word2 Word22 Word4 Word20 Word6 Word7 Word8 Word9 Word10 Word11 Word12 Word13 Word14 Word15 Word16 Word17 Word18 Word19 Word5 Word21 Word3 Word23 Word24
Word1 Word2 Word22 Word4 Word5 Word19 Word7 Word8 Word9 Word10 Word11 Word12 Word13 Word14 Word15 Word16 Word17 Word18 Word6 Word20 Word21 Word3 Word23 Word24
Word1 Word2 Word22 Word4 Word5 Word6 Word18 Word8 Word9 Word10 Word11 Word12 Word13 Word14 Word15 Word16 Word17 Word7 Word19 Word20 Word21 Word3 Word23 Word24 
Word1 Word2 Word22 Word4 Word5 Word6 Word7 Word17 Word9 Word10 Word11 Word12 Word13 Word14 Word15 Word16 Word8 Word18 Word19 Word20 Word21 Word3 Word23 Word24
Word1 Word2 Word22 Word4 Word5 Word6 Word7 Word8 Word16 Word10 Word11 Word12 Word13 Word14 Word15 Word9 Word17 Word18 Word19 Word20 Word21 Word3 Word23 Word24
Word1 Word2 Word22 Word4 Word5 Word6 Word7 Word8 Word9 Word15 Word11 Word12 Word13 Word14 Word10 Word16 Word17 Word18 Word19 Word20 Word21 Word3 Word23 Word24
Word1 Word2 Word22 Word4 Word5 Word6 Word7 Word8 Word9 Word10 Word14 Word12 Word13 Word11 Word15 Word16 Word17 Word18 Word19 Word20 Word21 Word3 Word23 Word24
Word1 Word2 Word22 Word4 Word5 Word6 Word7 Word8 Word9 Word10 Word11 Word13 Word12 Word14 Word15 Word16 Word17 Word18 Word19 Word20 Word21 Word3 Word23 Word24
Word1 Word2 Word3 Word21 Word20 Word6 Word7 Word8 Word9 Word10 Word11 Word12 Word13 Word14 Word15 Word16 Word17 Word18 Word19 Word5 Word4 Word22 Word23 Word24
Word1 Word2 Word3 Word21 Word5 Word19 Word7 Word8 Word9 Word10 Word11 Word12 Word13 Word14 Word15 Word16 Word17 Word18 Word6 Word20 Word4 Word22 Word23 Word24
Word1 Word2 Word3 Word21 Word5 Word6 Word18 Word8 Word9 Word10 Word11 Word12 Word13 Word14 Word15 Word16 Word17 Word7 Word19 Word20 Word4 Word22 Word23 Word24
Word1 Word2 Word3 Word21 Word5 Word6 Word7 Word17 Word9 Word10 Word11 Word12 Word13 Word14 Word15 Word16 Word8 Word18 Word19 Word20 Word4 Word22 Word23 Word24
Word1 Word2 Word3 Word21 Word5 Word6 Word7 Word8 Word16 Word10 Word11 Word12 Word13 Word14 Word15 Word9 Word17 Word18 Word19 Word20 Word4 Word22 Word23 Word24
Word1 Word2 Word3 Word21 Word5 Word6 Word7 Word8 Word9 Word15 Word11 Word12 Word13 Word14 Word10 Word16 Word17 Word18 Word19 Word20 Word4 Word22 Word23 Word24
Word1 Word2 Word3 Word21 Word5 Word6 Word7 Word8 Word9 Word10 Word14 Word12 Word13 Word11 Word15 Word16 Word17 Word18 Word19 Word20 Word4 Word22 Word23 Word24
Word1 Word2 Word3 Word21 Word5 Word6 Word7 Word8 Word9 Word10 Word11 Word13 Word12 Word14 Word15 Word16 Word17 Word18 Word19 Word20 Word4 Word22 Word23 Word24
Word1 Word2 Word3 Word4 Word20 Word19 Word7 Word8 Word9 Word10 Word11 Word12 Word13 Word14 Word15 Word16 Word17 Word18 Word6 Word5 Word21 Word22 Word23 Word24
Word1 Word2 Word3 Word4 Word20 Word6 Word18 Word8 Word9 Word10 Word11 Word12 Word13 Word14 Word15 Word16 Word17 Word7 Word19 Word5 Word21 Word22 Word23 Word24
Word1 Word2 Word3 Word4 Word20 Word6 Word7 Word17 Word9 Word10 Word11 Word12 Word13 Word14 Word15 Word16 Word8 Word18 Word19 Word5 Word21 Word22 Word23 Word24
Word1 Word2 Word3 Word4 Word20 Word6 Word7 Word8 Word16 Word10 Word11 Word12 Word13 Word14 Word15 Word9 Word17 Word18 Word19 Word5 Word21 Word22 Word23 Word24
Word1 Word2 Word3 Word4 Word20 Word6 Word7 Word8 Word9 Word15 Word11 Word12 Word13 Word14 Word10 Word16 Word17 Word18 Word19 Word5 Word21 Word22 Word23 Word24
Word1 Word2 Word3 Word4 Word20 Word6 Word7 Word8 Word9 Word10 Word14 Word12 Word13 Word11 Word15 Word16 Word17 Word18 Word19 Word5 Word21 Word22 Word23 Word24
Word1 Word2 Word3 Word4 Word20 Word6 Word7 Word8 Word9 Word10 Word11 Word13 Word12 Word14 Word15 Word16 Word17 Word18 Word19 Word5 Word21 Word22 Word23 Word24
Word1 Word2 Word3 Word4 Word5 Word19 Word18 Word8 Word9 Word10 Word11 Word12 Word13 Word14 Word15 Word16 Word17 Word7 Word6 Word20 Word21 Word22 Word23 Word24
Word1 Word2 Word3 Word4 Word5 Word19 Word7 Word17 Word9 Word10 Word11 Word12 Word13 Word14 Word15 Word16 Word8 Word18 Word6 Word20 Word21 Word22 Word23 Word24
Word1 Word2 Word3 Word4 Word5 Word19 Word7 Word8 Word16 Word10 Word11 Word12 Word13 Word14 Word15 Word9 Word17 Word18 Word6 Word20 Word21 Word22 Word23 Word24
Word1 Word2 Word3 Word4 Word5 Word19 Word7 Word8 Word9 Word15 Word11 Word12 Word13 Word14 Word10 Word16 Word17 Word18 Word6 Word20 Word21 Word22 Word23 Word24
Word1 Word2 Word3 Word4 Word5 Word19 Word7 Word8 Word9 Word10 Word14 Word12 Word13 Word11 Word15 Word16 Word17 Word18 Word6 Word20 Word21 Word22 Word23 Word24
Word1 Word2 Word3 Word4 Word5 Word19 Word7 Word8 Word9 Word10 Word11 Word13 Word12 Word14 Word15 Word16 Word17 Word18 Word6 Word20 Word21 Word22 Word23 Word24
Word1 Word2 Word3 Word4 Word5 Word6 Word18 Word17 Word9 Word10 Word11 Word12 Word13 Word14 Word15 Word16 Word8 Word7 Word19 Word20 Word21 Word22 Word23 Word24
Word1 Word2 Word3 Word4 Word5 Word6 Word18 Word8 Word16 Word10 Word11 Word12 Word13 Word14 Word15 Word9 Word17 Word7 Word19 Word20 Word21 Word22 Word23 Word24
Word1 Word2 Word3 Word4 Word5 Word6 Word18 Word8 Word9 Word15 Word11 Word12 Word13 Word14 Word10 Word16 Word17 Word7 Word19 Word20 Word21 Word22 Word23 Word24
Word1 Word2 Word3 Word4 Word5 Word6 Word18 Word8 Word9 Word10 Word14 Word12 Word13 Word11 Word15 Word16 Word17 Word7 Word19 Word20 Word21 Word22 Word23 Word24
Word1 Word2 Word3 Word4 Word5 Word6 Word18 Word8 Word9 Word10 Word11 Word13 Word12 Word14 Word15 Word16 Word17 Word7 Word19 Word20 Word21 Word22 Word23 Word24
Word1 Word2 Word3 Word4 Word5 Word6 Word7 Word17 Word16 Word10 Word11 Word12 Word13 Word14 Word15 Word9 Word8 Word18 Word19 Word20 Word21 Word22 Word23 Word24
Word1 Word2 Word3 Word4 Word5 Word6 Word7 Word17 Word9 Word15 Word11 Word12 Word13 Word14 Word10 Word16 Word8 Word18 Word19 Word20 Word21 Word22 Word23 Word24
Word1 Word2 Word3 Word4 Word5 Word6 Word7 Word17 Word9 Word10 Word14 Word12 Word13 Word11 Word15 Word16 Word8 Word18 Word19 Word20 Word21 Word22 Word23 Word24
Word1 Word2 Word3 Word4 Word5 Word6 Word7 Word17 Word9 Word10 Word11 Word13 Word12 Word14 Word15 Word16 Word8 Word18 Word19 Word20 Word21 Word22 Word23 Word24
Word1 Word2 Word3 Word4 Word5 Word6 Word7 Word8 Word16 Word15 Word11 Word12 Word13 Word14 Word10 Word9 Word17 Word18 Word19 Word20 Word21 Word22 Word23 Word24
Word1 Word2 Word3 Word4 Word5 Word6 Word7 Word8 Word16 Word10 Word14 Word12 Word13 Word11 Word15 Word9 Word17 Word18 Word19 Word20 Word21 Word22 Word23 Word24
Word1 Word2 Word3 Word4 Word5 Word6 Word7 Word8 Word16 Word10 Word11 Word13 Word12 Word14 Word15 Word9 Word17 Word18 Word19 Word20 Word21 Word22 Word23 Word24
Word1 Word2 Word3 Word4 Word5 Word6 Word7 Word8 Word9 Word15 Word14 Word12 Word13 Word11 Word10 Word16 Word17 Word18 Word19 Word20 Word21 Word22 Word23 Word24
Word1 Word2 Word3 Word4 Word5 Word6 Word7 Word8 Word9 Word15 Word11 Word13 Word12 Word14 Word10 Word16 Word17 Word18 Word19 Word20 Word21 Word22 Word23 Word24
Word1 Word2 Word3 Word4 Word5 Word6 Word7 Word8 Word9 Word10 Word14 Word13 Word12 Word11 Word15 Word16 Word17 Word18 Word19 Word20 Word21 Word22 Word23 Word24

The number is so small because symmetrical swapping reduces in half the number of permutation, (1<>24 is the same as 24<>1). The list above is exhaustive of every possible way you can permute using your special technique.

I just couldn't help comment in case you still didn't try to import/test the 30 thousand possibilities, I hope you don't have to :)

In case you're not sure you swapped them symmetrically of course, you can expand the search radius, but there are a few steps before trying the full 30k solutions. (Like if the 2 words you swapped were neighbors, or far away by n words, etc.. which are also much less)

I'm also as jealous as a middleschool schoolgirl because this is a really easy problem.. Right place at the right time I guess :-\

Title: Re: Math problem regarding recovery seed
Post by: khaled0111 on January 07, 2019, 09:58:25 PM

Thank you for pointing this out, symetric swapping will reduce the number of possibilities to 66.

Now, we will work only on 2 words out of 12 words and swap them against their symeyric from the other 12 words.

n!/(n-r)! * 1/r! gives us 12!/(12-10)! *1/2! = 66
gave you +2 for this (wish I got many of them, you deserve much more)

Title: Re: Math problem regarding recovery seed
Post by: Coding Enthusiast on January 08, 2019, 03:06:37 AM

Quote from: KingZee on January 07, 2019, 06:28:49 PM

I don't see how there are that many combinations unless he bruteforced every possible permutation of 4 from 24, which is roughly 331776 possibilities (minus repetitions I guess.)

I didn't brute force all the possible permutations, actually I am skipping a lot (eg. w1-w5 and w5-w1, also w1-w5 and w5-w10 since w5 was already swapped) which is why the total is 31878 instead of 255024. Additionally I stuck to this part of OP's comment:

Quote from: BldSwtTrs on January 05, 2019, 02:01:23 AM

But since I screw up, maybe I have switched words in a non symetrical position.

Title: Re: Math problem regarding recovery seed
Post by: birr on January 08, 2019, 05:01:19 AM

Not all combos are valid, because of the checksum, amirite?

Title: Re: Math problem regarding recovery seed
Post by: HeRetiK on January 08, 2019, 01:11:48 PM

Quote from: birr on January 08, 2019, 05:01:19 AM

Not all combos are valid, because of the checksum, amirite?

Yes. I think actually most combos won't be valid. However there's little to be done besides brute forcing the available combinations and then 1) checking whether the checksum is correct, and if the checksum is correct 2) whether it's associated with any transactions.

Title: Re: Math problem regarding recovery seed
Post by: birr on January 09, 2019, 03:55:04 AM

So in terms of saving time, there's the question of which is quicker: validating the checksum or looking for transactions?
If it takes less time to validate the checksum than it does to look for transactions, then it's worth it to validate checksums.
On the other hand, if validating a checksum takes longer than looking for transactions, then checksum validation isn't worth the trouble.
I don't have enough experience with this stuff to say for sure one way or the other, but my guess is that checksum validation, because it's done locally, takes less time than searching for transactions.
And since checksum validation will eliminate 99.99% of the seeds, the time savings of not having to do all those searches for transactions really adds up.

Title: Re: Math problem regarding recovery seed
Post by: pooya87 on January 09, 2019, 04:11:17 AM

Quote from: birr on January 09, 2019, 03:55:04 AM

since checksum is a simple SHA256 hash of the bytes that the seed phrase gives you then it is so much faster than doing anything else. not to mention that you should already return a "fail" in first step meaning when you convert the set of words into a byte array and not even move to turning anything into keys > addresses > transaction checking!

Title: Re: Math problem regarding recovery seed
Post by: birr on January 09, 2019, 03:59:24 PM

Quote from: pooya87 on January 09, 2019, 04:11:17 AM

Quote from: birr on January 09, 2019, 03:55:04 AM

yup

Title: Re: Math problem regarding recovery seed
Post by: wingsuit on July 17, 2020, 12:30:47 AM

What was the eventual outcome of this? Did OP recover his funds?

Title: Re: Math problem regarding recovery seed
Post by: birr on September 25, 2020, 07:53:03 PM

Haha, interesting that this thread has been resurrected from the dead, and yes it would be nice to know if anything came of it.
Anyway, I would like to make a couple of comments.

First: as for verifying the checksum, this github page lays out how bip39 works
https://github.com/bitcoin/bips/blob/master/bip-0039.mediawiki
There's just one bit of critical information missing from that page: the precise syntax of the hash command.
It says you generate the checksum by hashing the initial entropy of ENT bits and using the first ENT/32 bits of the result as the checksum
The hash command for this operation is
echo -n '***************' | xxd -r -p | sha256sum -b
where the asterisks are your initial entropy (supposedly 256 bits for a 24 word phrase)

Second: don't know why I wrote "searching for transactions"
What I meant was testing the seed

Title: Re: Math problem regarding recovery seed
Post by: HCP on September 26, 2020, 12:10:26 AM

Quote from: birr on September 25, 2020, 07:53:03 PM

First: as for verifying the checksum, this github page lays out how bip39 works
https://github.com/bitcoin/bips/blob/master/bip-0039.mediawiki
There's just one bit of critical information missing from that page: the precise syntax of the hash command.

Probably because there isn't just one command for creating the hash... it's just a SHA256 hash output of the initial entropy "ENT", so you are free to get this output in any way you seem fit... commandline shell tools, Python script, C++/C# libraries, Javascript, online website etc... It all comes down to how you are implementing/using the BIP39 process.

Title: Re: Math problem regarding recovery seed
Post by: birr on September 29, 2020, 05:43:45 PM

Quote from: HCP on September 26, 2020, 12:10:26 AM

there isn't just one command for creating the hash

Maybe OP has the chops to roll his own bip39 in c or python or whatever, but why bother. He should just use the bash command.

Title: Re: Math problem regarding recovery seed
Post by: HCP on September 30, 2020, 12:27:25 AM

That's kinda my point, you don't need to "roll your own" anything... there are already libraries in most of the popular languages that do it all for you and they're all linked in the BIP39 spec: https://github.com/bitcoin/bips/blob/master/bip-0039.mediawiki#other-implementations

And what if the OP doesn't use Linux? ;)

All joking aside, the BIP39 spec isn't really there to provide implementation specific commands etc, but more of a high level description of the process involved. It's left up to the user to decide how they actually want to go about implementing the spec.

It's all specific use-case dependent.

Title: Re: Math problem regarding recovery seed
Post by: birr on October 10, 2020, 07:18:02 PM

The use case is to test a 24 word mnemonic for checksum validity

refer to the bip 39 wordlist, which can be found here
https://github.com/bitcoin/bips/blob/master/bip-0039/english.txt
but it is numbered 1 through 2048, which is wrong, and will give wrong results if you use it.
Change the numbering to 0 through 2047. That's 11 bits.
Then look up each of your 24 words in that list, and record each word as an 11 bit binary number (include leading zeros) and concatenate them in a 264 bit string.
Divide the string into a 256 bit string and an 8 bit string. The 256 bit string is ENT. The 8 bits is the checksum, which might be right or wrong.
Do a sha256 hash of ENT, using the specified syntax. Compare the first 8 bits of the hash to the 8 bits you took from the end of the 264 bit mnemonic binary.

Title: Re: Math problem regarding recovery seed
Post by: pooya87 on October 11, 2020, 02:50:05 AM

Quote from: birr on October 10, 2020, 07:18:02 PM

but it is numbered 1 through 2048, which is wrong, and will give wrong results if you use it.

it is not numbered (https://raw.githubusercontent.com/bitcoin/bips/master/bip-0039/english.txt). and you shouldn't be using the list by hand anyways.
the numbers you see is the default line numbers that GitHub adds to all the files and they start from 1. here is some random "code" file where you can see the line numbers: https://github.com/bitcoin/bitcoin/blob/master/src/script/interpreter.cpp

Quote from: birr on September 29, 2020, 05:43:45 PM

Maybe OP has the chops to roll his own bip39 in c or python or whatever, but why bother. He should just use the bash command.

using bash would be super slow for OP's case (ignoring the fact that the topic is more than a year old). additionally just finding the correct checksum is not enough, you'll still be left with tens of thousands of mnemonics that you'd have to use to derive key(s) from and check those too.

Bitcoin Forum

Bitcoin => Bitcoin Technical Support => Topic started by: BldSwtTrs on January 05, 2019, 12:59:41 AM