Re: How much entropy is lost by searching for a 1 prefix SHA512 output

Quote from: ThomasV on January 27, 2017, 09:09:32 AM

The seed has 132 bits and the length of the prefix is 8 bits. Therefore, 8 bits are "lost" by imposing the 0x01 prefix.

However, there is no way to enumerate seeds that hash with the desired prefix, other than brute force. Therefore, from a security point of view, these bits are not "lost"; an attacker still needs to use brute force in order to find valid seeds, just like they need to use brute force in order to attack the remaining bits.

There is still a weakening of the seed that results from the imposed prefix, because no key stretching is required in order to generate the prefix.
But it is wrong to express it in terms of "bits lost"; all you can say is that these 8 bits are easier to enumerate than the remaining 124 bits.

I am just an amateur, but I have analyzed the code.

There are 2 use cases of the SHA512, where the the HMAC is encoding it with:

"Seed version" in is_new_seed in the Mnemonic.py
And with "Bitcoin seed" in the Bitcoin.py in bip32_root function to generate the xpriv key

Now I assume that signing with different messages doesnt leak information, after all this is the point of the hash function.

So we are left with the Mnemonic.py is_new_seed function, where 2 bits of the prefix is fixed:

Code:

SEED_PREFIX = '01'

(via version.py)

Now I have experimentally tested, the relationship with the input and output of the SHA512 function, and asked some cryptographers about it as well.

And it looks to me that by fixing 2 output bits, you lose 2 input bits (on average, it converges towards 2 bits +/- some variance at certain inputs). Or in general terms the input loss = the output loss, on average

And since the test is happening in hex

Code:

s = hmac_sha_512("Seed version", x.encode('utf8')).encode('hex')
return s.startswith(str(prefix))

1 hex char is 4 bits, therefore you have 2 bits * 4 bits = 8 bits.

So if the seed is <520 bits long, then its easier to crack the seed, than the SHA512
If the seed is 520 bits, then it's the same as SHA512
If the seed is >520 bits, then it's easier to crack SHA512

Is that a correct assesment?