Post
Topic
Board Electrum
Re: How much entropy is lost by searching for a 1 prefix SHA512 output
by
ThomasV
on 28/01/2017, 11:17:56 UTC
...
Is that a correct assesment?

No that is not correct.

First, we are not talking about 2 but 8 bits. I do not know why you made that statement about 2 bits.

Second, we are not fixing the bits passed to bip32_root. The seed passed to bip32_root is not hashed with "Seed version", but with a different string. That assumption seems to be present in the last part of your reasoning.

Third, and this is the most important point, there is no 'loss' of entropy.

Entropy is a measure of uncertainty in a system. It is relative, not absolute. It makes sense to talk about entropy only if you clearly define what is your prior knowledge of a system. In our case, we need to look at how many bits of uncertainty there is from the point of view of an attacker. In general, in order to crack a n-bits seed, an attacker needs to perform 2^n iterations of public key generation.

If we impose a constraint on the seed, namely that its hash starts with a given prefix of length m bits, this does not reduce the number of iterations an attacker has to perform. The attacker still has to enumerate 2^n seeds and test them. Therefore, it is incorrect to claim that we are reducing entropy. The only thing that changes is that the test function will return faster for invalid seeds (because it does not have key stretching). So, what we are losing is the benefit of key stretching on m bits. But we are not losing m bits of entropy.

To understand that these bits are not lost, consider an extreme case where the seed has 132 bits and the prefix has 64 bits. Would you say that we have lost 64 bits of entropy? no, because it has become incredibly difficult to generate a seed. An attacker still has to go thought these 2^64 iterations, before they can test each of the remaining 2^64 public keys.

Note that it is possible to express the benefit of key stretching in "bits", although that's a bit like adding oranges and apples. Nevertheless, if you consider that key stretching increases the number of "bits" of your seed, you have to understand that it only adds a constant. The strength of a seed increases exponentially with its length, and only linearly with the number of iterations of key stretching. What we are losing is a fraction of this constant.