How much entropy is lost if 1 character is fixed in HMAC SHA-512?

Question

We have an entropy source called “Entropy”. We encode this entropy with HMAC-SHA512 using a “Key”. The Key is public, but the Entropy is secret. We are then testing for the HMAC-SHA512 output in order to start with 1.

So, how much entropy is lost in the process, by encoding the secret Entropy with a public Key, and making sure that the output starts with 1?

For example:

Entropy     = random 132 bit integer
Public Key  = Test
HMAC-SHA512 = 1f042a41f2a940c38e64146823abd7926acb9d26cf02ee50f637dd5fb37c60c4d582603abe789138fa51a0496a6840b6e03e9b38d886e6bc6fd337f284a1052f

In our case we would search for a random integer until the HMAC-SHA512 output of it encoded with Test will start with 1 like 1f042a41f…

So in our case the final "not so random number" is:

467315884026680443925332907127019473008

How much entropy is lost in this process?

Answer 1

I'll assume the hash function is "good", i.e., equidistributed and partial-preimage-resistant.

If the input length $n$ is fixed and you fix $k$ bits of the output hash, you're losing roughly $k$ bits of information-theoretical entropy. This is easy to see: Without constraining the output, the entropy is $n$ bits, but forcing the value of $k$ bits means throwing away (on average) all but one out of $2^k$ of those preimages, therefore the resulting value is really sampled from (roughly) $2^{n-k}$ inputs rather than $2^n$.

However, computationally, this doesn't matter: Unless the hash function is severely broken, an attacker trying to recover your secret cannot "carve out" the subset of inputs whose hash values satisfy a specific constraint. (Note: If this were possible, they could just do it for any instance, not just one where you brute-forced those bits!) Thus, the computational search space for an attacker is still $2^n$ instead of $2^{n-k}$, since they have to use basically the same method as you did.

These considerations are related to the conjecture that Bitcoin works and an indication that vanity keys such as Facebook's Tor Hidden Service address facebookcorewwwi.onion are not insecure even though their private key contains (information-theoretically) less entropy than other keys.