6

Yes I know this is a horrible idea and not BIP39 compliant, but please help satisfy my curiosity with this "thought experiment" and applied maths exercise.

Two questions, one for 12 words, the other for 24.

Assuming "perfectly random" entropy to start, and yes the final checksum word gets changed with the new ordering, not itself included in the alphabetical sort.

Just how much entropy is lost in the phrase's re-sorting, compared to the original random sort?

I don't need the "show your work" maths, more like practically speaking about current brute-forcing capabilities, "you would lose 70% of your entropy, and 40% respectively"

If not too inconvenient, something ELI5 like, how many supercomputer-years of effort's difference?

2 Answers 2

10

TL;DR: you get around a factor 500 million attack speedup for 12 words, bringing it not quite in the realm of feasible attacks, but it's getting close. For 24 words, the speedup is around a factor half a septillion, but still far beyond the realm of feasible attacks.

Repetition of words or not?

First I need to ask: are words permitted to occur multiple times within the same sorted phrase? If not, Mike D's answer is correct. If they are, the question just got a lot more complicated, at least if you care about the exact numbers.

The difficulty with allowing repetition

Once you allow repetition, the distribution you obtain by sorting uniformly chosen phrases, is no longer uniform. For example the sorted phrase "act act act act act act act act act act act zoo" can be obtained from 12 distinct unsorted phrases ("act ... act zoo", "act ... act zoo act", "act ... act zoo act act", ...). The sorted phrase "mad mad mad mad mad mad mad mad mad mad mad mad" can only be obtained in one way. Thus, if you start with a random unsorted phrase, and sort it, the "act ... act zoo" phrase is 12 times more likely than the "mad ... mad" phrase.

This non-uniformity has a subtle but complicated impact on our question. If the phrases are uniformly distributed, with N possibilities, then it holds that:

  1. The number of distinct phrases is N.
  2. The entropy (in bits) of a sampled phrase is log2(N).
  3. The average number of tries an attacker needs to brute-force guess a sampled phrase is (N + 1) / 2.

When the phrases are not uniform (as would be the case when sorting uniform phrases with repetition), the answer to (2) and (3) cannot be simply expressed anymore as a function of N. It depends on exactly how non-uniform the distribution is. Worse, you can't even compute (3) from (2) or the other way around, because entropy is not a measure for how secure something is, but for how compressible it is. These two are strongly correlated, but not exactly the same, and the difference between the two again will depend on the exact distribution.

This is all to say that the answer to these three questions is distinct, and it depends on what you're interested in:

  1. How many distinct sorted phrases are there?
  2. How much entropy do phrases obtained by sorting uniform unsorted phrases have?
  3. How hard is it for attackers to guess a phrase obtained by sorting a uniform unsorted phrase has?

1. How many distinct sorted phrases are there?

The number of distinct multisets of k elements, drawn from a set of N elements is .

  • For k=12 and N=2048 that is 11737947382912650038702322439680, or ~2103.211.
  • For k=24 and N=2048 that is 54640990776272965318633918350257589558711775320768326400, or ~2185.156

Note that these numbers only differ slightly from the corresponding numbers when repetition is not allowed (2103.118 and 2184.767 respectively)

2. How much entropy do phrases obtained by sorting uniform unsorted phrases have?

The entropy of a distribution is how many bits on average an optimal compression scheme needs per element to encode a (long) list of randomly sampled elements from that distribution. For a discrete distribution taking on possibilities a1, a2, ..., an, with respective probabilities p1, p2, ..., pn, that is . By applying this formula to the probability distribution of sorted phrases exactly, you get:

  • For 12 words: ~103.196 bits
  • For 24 words: ~185.097 bits

3. How hard is it for attackers to guess a phrase obtained by sorting a uniform unsorted phrase has?

The optimal strategy for an attacker that tries to brute force, and who knows the probability distribution, is to try values from most likely to least likely. The expected number of tries under such a strategy is , assuming the pi are sorted from high to low. Applying this formula to the exact probability distribution in question here we get:

  • For 12 words: ~(2103.166 + 1) / 2
  • For 24 words: ~(2184.985 + 1) / 2

In other words, the average time an attacker needs for guessing these sorted phrase distributions is as if they were uniform distributions with ~103.166 resp. ~184.985 bits of entropy (but, as demonstrated in the previous section, that is not exactly the entropy the sorted phrase distributions have).

Summary

The following table summarizes the numbers for all 4 scenarios (repetition allows and not allowed, sorted or not), under all 3 metrics (number of possibilities, entropy, and expected number of tries for an attacker):

12 words # possibilities entropy mean tries
Normal, repetition 2132 132 bits (2132 + 1) / 2
Normal, no repetition ~2131.953 ~131.953 bits ~(2131.953 + 1) / 2
After sorting, repetition (*) ~2103.211 ~103.196 bits ~(2103.166 + 1) / 2
After sorting, no repetition ~2103.118 ~103.118 bits ~(2103.118 + 1) / 2
24 words # possibilities entropy mean tries
Normal, repetition 2264 264 bits (2264 + 1) / 2
Normal, no repetition ~2263.805 ~263.805 bits ~(2263.805 + 1) / 2
After sorting, repetition (*) ~2185.156 ~185.097 bits ~(2184.985 + 1) / 2
After sorting, no repetition ~2184.767 ~184.767 bits ~(2184.767 + 1) / 2

(*) = Note that only the lines for after sorting with repetition have distinct numbers in their expressions for the three columns. For all others, they follow the pattern 2v, v, (2v + 1) / 2 for some value v perfectly, because they induce uniform distributions.

3
  • 2
    Wow, mind blown, what an honor, I am incredulous you put in that level of effort. Thank you! And yes I meant allowing repetition but that seems to not make much difference?
    – HansBKK
    Apr 28 at 7:53
  • @HansBKK Yeah, the numbers differ at most by a few percent between repetition and no repetition. And I may have gotten nerdsniped a bit here... Apr 28 at 15:09
  • Learned a new word today... The world is a better place for the effort you put into it, so glad you deemed it interesting enough.
    – HansBKK
    May 5 at 5:14
6

The number of possible 12 word phrases (disregarding the checksum) is 2048 ^ 12 = 5444517870735015415413993718908291383296

The number of alphabetically ordered 12 word phrases is

= 11005261717918037175659349191168

The second number is smaller by a factor of 500 million or a reduction of 99.9999998% but you measure such large numbers in bits in which case you get an entropy reduction of 29 bits (132 - 103)

7
  • Fantastic, thanks. So for 24 words, the ratio is similar?
    – HansBKK
    Apr 24 at 20:01
  • for 24 words just replace 12 with 24 in the formula above
    – Mike D
    Apr 25 at 11:10
  • Sorry I do not know what the notation means on a computer, only did maths on paper as a boy, and can't figure out how to google that
    – HansBKK
    Apr 26 at 12:11
  • 1
    You are right the correct number is 5444517870735015415413993718908291383296 (same as your calc). For the second number type “2048 choose 12” in google
    – Mike D
    Apr 26 at 18:40
  • 1
    We want order to be ignored when counting ordered groups otherwise we would double count the same 12 words in a different order
    – Mike D
    Apr 27 at 10:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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