What happens to entropy after hashing?
Suppose you have a key with entropy $k$. Can entropy $k$ be increased by hashing the key?
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this communityWhat happens to entropy after hashing?
Suppose you have a key with entropy $k$. Can entropy $k$ be increased by hashing the key?
The answer rather depends on what you mean by 'entropy'; if you mean 'Shannon Entropy', then no, a deterministic function cannot increase entropy.
For example, if the unhashed password has only 7 different possible values, then the hashed version of the password will also have (at most) 7 different possible values; you've made things look more obscure, but you haven't actually changed anything as far as entropy is concerned.
The standard definition of Shannon entropy is:
$H(X) = \sum -p_i\ log_2 p_i$
Where $p_i$ is the probability of the $i$th possible sample value. That is, the Shannon entropy is defined solely in terms of probability distribution, and not how that probability distribution appears.
If we have a Hash function $SHA$ which doesn't have any collisions, then it has no effect on entropy; that is, $H(X) = H(SHA(X))$; that's because the probabilities involved in the probability distributions are precisely the same; if a specific password $x_i$ had a certain probability, then the hashed form of that password $SHA(x_i)$ will appear with that exact probability in the hashed distribution.
And, if the Hash function $SHA$ does have a collision, that is, if $SHA(x_i) = SHA(x_j)$, then (assuming both $x_i$ and $x_j$ have nonzero probability), then $SHA$ will actually reduce the entropy. And, this is not a violation of collision resistance; collision resistance only states that it is hard to find such a collision, not that one does not exist.
This is easier to see in the extreme case; suppose we have two possible passwords ("Mary" and "Susan"), and both of those passwords have probability $0.5$; this means that the entropy of the password is 1 bit; an attacker can perform go through all possible values by checking on two different passwords. If you hash the password, you may come up with two images (39e74b4e80ba656f773669ed60315a and 98e15403b2b1ea5022fc42b3490cc76e in hex) that look different, however there are still only two possible values, and so the effort an attacker would have in trying those two values in unchanged.
If the hash function is collision resistant, hashing does not change the entropy of the key. It will be $k$ after hashing.