Weak and strong uniformity of cryptographic hash functions

Question

For any $n\in\mathbb{N}$, let $\{0,1\}^n$ denote the set of $\{0,1\}$-strings of length $n$. For $n\in\mathbb{N}$ let $$\{0,1\}^* = \bigcup_{k\in\mathbb{N}}\{0,1\}^k \text{ and } \{0,1\}^{\leq n} = \bigcup_{k\leq n}\{0,1\}^k.$$

Note that $|\{0,1\}^{\leq n}| = 2^{n+1} -1$.

Cryptographic functions $h$ map $\{0,1\}^*$ to $\{0,1\}^n$ for some fixed $n\in\mathbb{N}$. Note that in general, for a cryptographic hash function $h:\{0,1\}^*\to \{0,1\}^n$ it is not known whether $\text{im}(h) = \{0,1\}^n$ where $\text{im}(h) = \{h(x): x\in\{0,1\}^*\}$ is the image of $h$.

1. A cryptographic hash function $h:\{0,1\}^*\to \{0,1\}^n$ is said to be weakly uniform if for every hash value there are infinitely many collisions, i.e. $h^{-1}(\{h(x)\})$ is infinite for every $x\in\{0,1\}^*$. (The pidgeonhole principle only implies the existence of one $x\in\{0,1\}^*$ such that $h^{-1}(\{h(x)\})$ is infinite.)

2. A cryptographic hash function $h:\{0,1\}^*\to \{0,1\}^n$ is said to be strongly uniform if the number of pre-images for each possible hash value approaches $1/|\text{im(h)}|$ as the input length grows longer, or, formally, if for every $x\in \{0,1\}^*$ we have: $$\lim \sup_{n\to\infty} \frac{|h^{-1}(\{h(x)\})\cap \{0,1\}^{\leq n}|}{2^{n+1}-1} =\frac{1}{|\text{im}(h)|}.$$

Question. Of all the hash functions known to be cryptographically secure, is there one of which we know whether it is weakly, or even strongly, uniform?

Answer 1

For the usual suspects (MD family, SHA family etc.) none are known to be weakly uniform (to be picky, they also aren't known to be cryptographically secure). To demonstrate uniformity in a constructive way would give a collision attack; to do it in a non-constructive way would be an existence proof that would generally use some sort of mathematical structure and the functions are not really designed in that way.

If we look at more mathematically structured hash functions which use ideas from public key cryptography such as the Chaum-van Heijst-Pfitzmann Hash Function (see section 7.4 of Stinson Cryptography: Theory and Practice), we can reduce the output modulo $2^n$ and have weak uniformity by the surjectivity of powers of primitive roots. Moreover, if $p-1$ is divisible by $2^n$ then we will have strong uniformity.

Note that the cost of collision finding in Chaim-van Heijst-Pfitzmann is the same as the cost of solving a discrete logarithm which is below the birthday bound and so larger parameters are required for collision resistance.