# XOR-Cascade of weak hash secure?

I have following theoretical question:

Let `H(X)` be a hash function which is considered as weak because collissions can be produced (e.g. SHA1, MD5).

I wonder if following functions:

``````H2(X) = H(H(X)) xor H(X)
H3(X) = H(H(H(X))) xor H(H(X)) xor H(X)
H4(X) = ...
``````

can be considered as safe, if `H(X)` is considered as unsafe. If the attacker could find a collission in `H(X)`, he would need to additionally find a collission in `H(H(X))` too, to be able to have a collission in `H2(X) = H(H(X)) xor H(X)`. Or is it still not secure? (Why?)

I am aware that such a cascade is not performant in comparison to a newer hash function like SHA256 or SHA3.

No. A collision for H is a pair of inputs m and m' such that m ≠ m' but H(m) = H(m'). It follows that H(H(m)) = H(H(m')), and also H(H(m)) xor H(m) = H(H(m')) xor H(m') , and so on.

Thus, any collision for H is also a collision for all your functions H2, H3, H4... These functions are thus in no way more secure than H when considering resistance to collisions. They may very well be less secure, even, since your premise is wrong:

If the attacker could find a collission in H(X), he would need to additionally find a collission in H(H(X)) too, to be able to have a collission in H2(X) = H(H(X)) xor H(X).

This is not true. If an attacker finds a collision for H that also collides for H(H), then he gets a collision for H2. But that does not work the other way round: there is no absolute requirement for a collision on H2 to be such that it is a collision on both H and H(H).

Thus, all collisions for H are collisions for H2 (and H3, H4...) but H2 can have collisions of its own that are not collisions for H. Finding collisions on H2 can thus only be easier than finding collisions on H.

No, generally not. Iterating hashes does increase the collision risk, since iterating from H(000...128...000) to H(111...128...111) - assuming H does have 128 bit output, is not guranteed to output 000...128...000 to 111...128...111. Instead, by using such thing, you actually decrease the collision resistance.

Iterating hash functions should only be done as a key strengthening factor, eg if you want to generate a strong encryption key out of a unsafe password. A key strengthening factor will then slow down the attacker enough to make bruteforcing the password be unfavorable than bruteforcing the key itself. Then any collisions does not matter since it will take the attacker a longer time to find a collision in a key strengthening function than to directly attack the encryption key.

Note that the attacker does have the hash function, so the attacker can easly run tests against the hash function to find any collisions, and then execute that test result on your real data.

Instead, do change the hash function in your system to a new hash function, like SHA512.