2
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The output is fixed, to 512 bits, and the input is conforming to that. The attacker knows how the algorithm works, and the Public key too. He doesn't know the input, but he knows that the first character of the output will be "1". Then what? My question is, what is the "k" in this scenario, given that the attacker knows that the output will start with "1" $\endgroup$ – cryptonoob400 Jan 24 '17 at 9:54
  • $\begingroup$ But I would like the answer to my particular question. The attacker knows the public key, and he knows that the output will start with "1", how much entropy is lost this way? I speculate that it's 4 bits given that in a 512bit string 1 character is 4 bits, and the first character is known. Is this true? $\endgroup$ – cryptonoob400 Jan 24 '17 at 10:07
  • $\begingroup$ @cryptonoob400 Yes, a hexadecimal digit encodes $4$ bits. $\endgroup$ – yyyyyyy Jan 24 '17 at 14:31

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.