Does it make sense to hash a 22 byte secret (which may not have full entropy since it is chosen by the user) into a 512 bit hash (using Keccak-512)?

More precisely, will the 512 bit hash have full entropy even though the input is only 22 bytes?

  • 4
    $\begingroup$ If you're only going to input $22*8=176$ bits of entropy (at best, assuming the users 'secrets' are perfect) surely you can't expect to reach $512$ bits of entropy within the hash? $\endgroup$ – Cryptographeur Jan 21 '14 at 13:00
  • 1
    $\begingroup$ I guess using a Keccak with 224 bit or 256 bit output would make slightly more sense (and would alter expectations towards the actual amount of entropy in the secret), but if you are ok with the 512 bit output size then there is nothing wrong with that. $\endgroup$ – Maarten Bodewes Jan 21 '14 at 13:44

Yes, the 512-bit hash (using Keccak-512 or the like) of 22 bytes (176 bits) entered by a user (or from whatever source) has the full entropy of the input (that is: at most, 176 bits of entropy; much, much less for a user-specified 22-character string) for any practical purpose; and not as much entropy as there are bits in the hash's output. Argument that there is no reduction of the original entropy: odds that among the $2^{176}$ 176-bit strings, any two hash to the same value, are only $\approx 2^{-161}$, making the operation theoretically reversible (including for every input) with overwhelming odds. Arguments that entropy is not increased to the hash's width: the number of possible outcomes is no more than $2^{176}$ 512-bit values, which are fully determined by the specification of the 512-bit hash; and no deterministic process can increase entropy.

In fact the reduction in output entropy compared to input entropy remains mostly negligible for input of 63 bytes (or less); or more generally for input of at most $n-1$ bytes for an $n$-byte hash. Argument: even though the transformation is no longer reversible for every input, it still is expected to be reversible for a large majority of inputs.

This justify Owlstead's suggestion of using a narrower hash, such as SHA-224 or SHA-256, since the output will be smaller but have almost the same entropy.

However it makes only limited sense to hash a user-specified string: since the input is chosen by a user, it is vulnerable to guessing, and replacing that input by its hash won't solve that issue. For this purpose it should be used a key stretching mechanism, such a scrypt (or the more common but much weaker PKBDF2). Key stretching does not increase entropy, but greatly increases the difficulty of brute-force search (about: by the ratio of effort spent for stretching, to the effort necessary to decide is the stretched key is correct; that can be $2^{30}$ in some realistic situations, like a password-protected document).

| improve this answer | |
  • 4
    $\begingroup$ From my read of the original question, the author believes "full entropy" to be the 512 bits of output by SHA-3. You are correct that there will (at most) be only the original 22 bytes of entropy, but you may want to change the first word to "No" to avoid confusion. :) $\endgroup$ – Stephen Touset Jan 21 '14 at 23: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.