Math problem regarding recovery seed

Damian

New member
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?
 

Jair

New member
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.
 

Ahmir

New member
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.
 

Zyon

New member
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.
 

Maxim

New member
(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.
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)
 

Jaxen

New member
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.
 

Howard

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

I would merit you if I could!
 

Jesiah

New member
Coding Enthusiast 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.
 

Ignacio

New member
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:
 

Jermaine

New member
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.
 

Yadiel

New member
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.
 

Seven

New member
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
 

Dhruv

New member
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.
 
Top