2

I always take the uniformity of hash output as a given and didn't think much of it. Now I am kind of curious, how does good hash function like sha guarantees output uniformity.

Intuitively, given 1:1 input cardinality to output cardinality, the same amount distribution that has high entropy (uniform) in hash output must be equal to the amount of distribution that has low entropy in hash output.

So that means approximately 50% of the possible input distribution will experience less uniformity after hashing.

This cannot be right, can someone point out where my logic is wrong? And guide me on the how good hash function output uniformity for any random distribution?

Edit:

I realize my question is a bit ambiguous, so I think I should try to clarify.

For simplification assuming sha1 is a function that map Integer 2^64 -> Integer 2^64

My question is that given a stream of n random number where n << 2^62, the uniformity property of good hash function (eg. sha1) will redistribute these n number uniformly on a number line [0, 2^k] such that the space between each number is roughly equal (uniformly distributed on a number line).

My first impression is that its not always possible.

If you conduct this experiment multiples times (say m times) where each experiment is to supply n random number and calculate how uniformly distributed the output is on the number line. You will see approximately 50% (or m/2 ) of the experiment to be less uniform and 50% of experiment to be more uniform.

I think my intuition is wrong, but I don't know where is it wrong.

Glorfindel
  • 3,955
Jal
  • 121
  • Are you essentially asking how a hash function provides confusion and diffusion? – forest Aug 15 '18 at 00:18
  • @forest Are you writing up an answer? I'll take a stab at it, but yours will probably be better. – Mike Ounsworth Aug 15 '18 at 00:22
  • @MikeOunsworth I'm thinking of writing one up, but I'm trying to fully understand what OP is asking first. I don't want to write an answer explaining how the avalanche effect works just to find out that it doesn't answer the question. In particular, OP's comment on the now-deleted answer confused me. – forest Aug 15 '18 at 00:23
  • lol yup, I have wikipedia/avalanche_effect open, and was about to brush up on the SHA3 spec. I'll leave this one to you! – Mike Ounsworth Aug 15 '18 at 00:24
  • OP, can you rephrase your question? I'm not sure if you're asking about permutation cycle length (i.e. chaining a single hash function a massive number of times), or how the uniformity in the digest is achieved. I can explain the properties of a hash (and how it differs from a random oracle), and perhaps that will allow you to find the answer? Otherwise this may be more of a mathematical question. – forest Aug 15 '18 at 00:26
  • In particular, a random oracle is perfectly surjective. A hash function attempts to be as close to a random oracle as possible, but there is always some of the output space which cannot be reached (and we cannot tell exactly which outputs cannot be reached for a hash of sufficient size). I'm not sure if you're asking what the mathematical implications of this are, or if you're asking how this is achieved. – forest Aug 15 '18 at 00:29
  • apologize for the ambiguity, I am not well verse in cryptography, my motivation for this question is basically to understand hyperloglog, In the HyperLogLog algorithm, a hash function is applied to each element in the original multiset to obtain a multiset of uniformly distributed random numbers with the same cardinality as the original multiset. The cardinality of this randomly distributed set can then be estimated using the algorithm above. I don't understand how is it possible for the above statement to be always true. – Jal Aug 15 '18 at 00:32
  • I would guess its true 50% of the time. That is for a good hash function any streams of n random integer will always be more uniform 50% of the time. – Jal Aug 15 '18 at 00:33
  • @Jal I think this question would be a better fit on [math.se], since it seems to be about the mathematical implications or properties of a given function and not on the implications of that function in information security or the cryptographic design of a particular function. I know nothing of the HyperLogLog algorithm, but I assume it is referring to hash as a purely mathematical construct, not specifically as a cryptographically secure hash like SHA-3 or BLAKE2. – forest Aug 15 '18 at 00:35
  • @forest I would migrate to crypto.SE; the core question seems to boil down to whether cryptographic hash functions guarantee uniformly distributed outputs. ie does uniformity follow from avalanche? Great question! – Mike Ounsworth Aug 15 '18 at 00:40
  • @MikeOunsworth I don't think it seems specific to cryptography, given the previous comment. I don't see anything about the security or cryptographic properties of hash functions, just a relation to a hash in a mathematical sense (which is off-topic in [crypto.se]). – forest Aug 15 '18 at 00:46
  • yeah ... from a quick scan of wiki/hyperloglog it looks like the algorithm hinges on the assumption that the underlying hash function is uniformly distributed. So the question "Is it?" seems fairly crypto-related. – Mike Ounsworth Aug 15 '18 at 00:48
  • @MikeOunsworth Uniform distribution doesn't imply cryptographic properties. Does the algorithm rely on collision resistance or 1st/2nd preimage against a computationally-bounded adversary? According to this site, HLL does not use cryptography. They use MurmurHash3 (which is off-topic at Crypto.SE) which has sufficient mathematical properties. This is why I believe the migration would be rejected. – forest Aug 15 '18 at 00:49
  • AH, if it's using a non-cryptographic hash, then agreed! (... but the question specifically mentions SHA ...). I maintain that "Are cryptographic hash functions uniformly distributed?" is an interesting question :P – Mike Ounsworth Aug 15 '18 at 00:57
  • Honestly I'm still very confused by "the uniformity property of good hash function (eg. sha1) will redistribute these n number uniformly on a number line [0, 2^k] such that the space between each number is roughly equal"... –  Aug 15 '18 at 01:02
  • What is the purpose of using a hashing algorithm? You should first consider that. I do not recall an application where it is useful to apply a hash to perfectly random input. – David K Aug 16 '18 at 14:01

0 Answers0