# How can one detect if a hash function doesn't have a full image?

Suppose we have a hash function $H: \{0,1\}^* \mapsto \{0,1\}^n$, that doesn't get all the $n$ length
bitstrings as a value for any input, but is otherwise secure. Can that fact be detected?

For example, let $H$ be a secure $n$-bit hash function. You are given a black box function $F$ and told it's either $H$ or $H\hspace{-0.04 in}\circ \hspace{-0.04 in}H$, the latter of which lacks an expected ~37% ($1/e$) of the image when $n$ is large.

Can you determine which it is without knowing $H$? In a tractable time,
when $n$ is large enough for $H$ to have collision resistance?

• Isn't this easy to prove that this cannot always be detected? You choose a random bit string of size n, that is not a known output, and you exclude it from all the possible outputs. Then determining that this output cannot be generated would be at least as hard as finding a collision. – Maarten Bodewes Jun 9 '14 at 21:16
• The only information you get is based on collisions, so it takes ~2^n/2 calls before you get any information. For n large enough, that means you can't tell. Otherwise, it's an exercise in estimating size based on collision rate and figuring out when you have achieved statistical significance. – bmm6o Jun 9 '14 at 21:56

No, you can't tell whether $H$ has a full image or not in a reasonable amount of time, if $n$ is large (say, $n\ge 160$). Distinguishing the case where its image is of size $2^n$ vs of size $2^n-1$ would require on the order of $2^n$ evaluations of $H$, which is infeasible for normal values of $n$.
No, you can't distinguish $H$ from $H \circ H$ in a reasonable amount of time, if $n$ is large (say $n\ge 160$) and you have no information on $H$. Distinguishing the two requires on the order of $2^{n/2}$ evaluations of the black box ($F$), which is infeasible for normal values of $n$.
The technical fine print: I am assuming you are asking about generic attacks, i.e., black-box attacks, where we can only evaluate the function at points of our choice but are not given any information about its internal structure. If you know the internal structure of $H$, you might be able to prove something, but this requires more than a black-box attack (more than simply evaluating $H$ on some values of your choice and looking at the output). For instance, it is easy to distinguish $\text{SHA256}$ from $\text{SHA256} \circ \text{SHA256}$ in a single query, for trivial reasons: send the input x to your black box, and if you get back 2d7116..81, you're dealing with $\text{SHA256}$, otherwise you're dealing with $\text{SHA256} \circ \text{SHA256}$. But this is not the kind of attack you are talking about.