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.

Suppose $h_1$ is collision resistant, and $h_2$ isn't.

Will $h(x)=h_2(h_1(x))$ always be collision resistant?

[Edited:] the output of h2 must be uniformly distributed

share|improve this question
    
Not always, but in practice it will often be even for relatively weak hashes $h_2$. The most important property required of $h_2$ is that preserves at least $2n$ bits of entropy, where $n$ is the target security level. (even that's not sufficient in pathological cases) –  CodesInChaos Dec 3 '13 at 13:07
    
"Uniformly distributed" over what? $f(x)=0$ is uniformly distributed over its image of $\{0\}$. –  figlesquidge Dec 3 '13 at 13:24
add comment

2 Answers 2

Will they always be collision resistant? No

For example, let $h_2(x)=0$. Then, $h(x)=h_2(h_1(x))=0$, which certainly isn't collision resistant.


Can it be collision resistant? Yes

For example, suppose we define $h_1(x)=\mathrm{SHA256}(x)$ and

$$ h_2(x)=\begin{cases} 0 & |x|=1 \\ \mathrm{SHA256}(x) & \mathrm{else} \end{cases} $$

Then, since the output of $|h_1(x)|=256$, the composition will leave: $$h(x)=\mathrm{SHA256}(\mathrm{SHA256}(x))$$ Which is believed to be collision resistant from the collision resistance of Sha256.


But what if $h_2$ is uniformly distributed across a 'sensible' codomain? As before

I add the requirement that it must be uniformly distributed across a sensible codomain since I assume this clarification wishes to prohibit hash functions for which the target space is too small to possibly be secure)

We can trivially create two examples that demonstrate the above properties. Let $W=\{0,1\}^{256}$. Then, as before let $h_1$ be a cryptographically secure hash function, with $h_1 \colon \{0,1\}^* \to W$ (eg SHA256 as above). Define $h_2(x) = h_1(\mathrm{MSB_{256}}(x))$.

Then $h_2$ is not collision resistant (since for any $x\in W$ and $y\in\{0,1\}^*$ we have $h_2(x)=h_2(x||y)$), but as before $h(x)=h_1(h_1((x))$.

Defining $h_2(x) = h_1(\mathrm{LSB_{256}}(\mathrm{MSB}_{512}(x))$ (ie we extract bits 256->511) we get the composition $h(x)=0$ which is not collision resistant.

A slight issue here might be justifying $h_2$ is uniformly distributed, but this comes down to how you attach a distribution to the set of all random strings - ie the distribution taken by $\{0,1\}^*$

share|improve this answer
add comment

Obviously not. For example, the function $h2(x) = 0$ is not collision resistant, $h2(h1(x))$ shares that property.

This remains true even in less trivial cases; if $h2$ is not collision resistant because its output is too short (it has an $n$-bit output, with $2^{n/2}$ being small enough to do a search over), then $h2(h1(x))$ will also be too short

share|improve this answer
    
Ironically, $H_2(x)$ is collision resistant if you assume the appropriate security claim for the output domain: $1$. –  nightcracker Dec 3 '13 at 15:38
add comment

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.