Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

What happens to entropy after hashing?

Suppose you have a key with entropy $k$. Can entropy $k$ be increased by hashing the key?

share|improve this question
    
Hmm ... do you mean any "hashing" (e.g. how about $H(k) = 0$), do you mean entropy of $k$ or $H(k)$, do you mean increase or decrease? –  Drux Dec 21 '13 at 8:10
    
@Drux I meant the entropy of H(K). I want to increase. –  user10988 Dec 21 '13 at 8:50

2 Answers 2

up vote 11 down vote accepted

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.

share|improve this answer
    
Oh dear information theory... [+1] (and thanks for correcting me) –  e-sushi Dec 21 '13 at 11:23

If the hash function is collision resistant, hashing does not change the entropy of the key. It will be $k$ after hashing.

share|improve this answer
    
This is not correct. Consider a completely random 2n-bit key, i.e., it has min-entropy 2n. And consider a hash function of the form $\{0,1\}^{2n}\rightarrow \{0,1\}^n$. Even if the hash function is a perfect random function. The result has just n-bits of entropy. –  acerberus Dec 21 '13 at 11:32
1  
@acerberus In that case what you are saying is true. I did not consider that case. thank you for pointing out that. –  deltaaruna Dec 21 '13 at 11:59
1  
even for a random transformation of n bits to n bits, there will probably be some collisions. but the entropy won't decrease significantly. It does tend to decrease a little bit, however. –  sellibitze Jan 25 at 20:47

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.