Hash collision resistance of $\mathcal H^\prime(m) = \mathcal H(\mathcal H(m)|m)$

Question

So far as I can find, every method better at producing hash collisions in cryptographic hashes than generic collision search involves finding some metric for the distance between two messages' hashes and calculating alterations to each that will iteratively reduce that distance.

And further, unless I'm misreading it, none of the existing attacks is a "forgery" attack, allowing the attacker to converge on a known hash; they all work by iteratively altering multiple messages, eventually arriving at a set that all have some shared but unpredictable result.

Are these true? If so,

• wouldn't $\mathcal H^\prime(m) = \mathcal H(\mathcal H(m)|m)$ be completely immune to current attacks (at the cost of giving up on one-pass hashing)?

---

@RickyDemer pointed out in comments that available parallelism makes even random-walk search formidable, and it does seem to me that while appending the full hash forces full recalculation at each iteration, stripping that advantage isn't on average going to claw back more than say eight bits of strength.... though I suppose recursing the construction until at least a certain number of hash blocks have been processed could slow down attackers arbitrarily.

So, just for fun, $$\mathcal H^0_H(m) = H(m)$$ $$ \mathcal H^n_H(m) = H(\mathcal H^{n-1}_H(m)|m)$$ $$|\mathcal H^n_H(m)|=1+n\cdot|m|$$ (with $|m|$ expressed in units of $H$'s block size) $$ \mathcal{\bar H}^e_H(m)=\mathcal H^n_H(m): \log_2|\mathcal H^{n-1}_H(m)| <e \le \log_2 |\mathcal H^n_H(m)|$$

So $\mathcal {\bar H}^{16}_{\rm SHA1}$ would be $\mathcal H^n_{\rm SHA1}$, $n$ large enough that at least $2^{16}$ additional blocks were hashed.

Leaving the question after accounting for his observation:

• would $\mathcal {\bar H}^e_H$ be immune to current attacks (at the cost of giving up on one-pass hashing) even in the face of an attacker willing to throw $2^e$ parallel devices at it?

Answer 1

Your scheme is twice as slow as the original hash function. If you were going to accept such a huge performance penalty, you'd be better off just picking a new hash function that (you trust) isn't broken.

Also, it's not clear to me how much security your construction actually adds. I don't immediately see a proof that it is secure even if the compression function has some problems. I'm not even sure how one would formalize this. We'd have to assume something about the compression function, as you can't get something from nothing; but it's not clear what minimal assumptions about the compression function are sufficient to ensure that your construction is secure.

Answer 2

This is sometimes called hash-twice in the literature. Obviously it can't do better than $n$-bit (second-)preimage resistance and $n/2$-bit collision resistance, but it can do worse. It has long been a folklore construction; it seems to have been first formally analyzed in

Elena Andreeva, Charles Bouillaguet, Orr Dunkelman, and John Kelsey, ‘Herding, Second Preimage and Trojan Message Attacks beyond Merkle-Damgård’, in Michael J. Jacobson, Jr., Vincent Rijmen, and Reihaneh Safavi-Naini, eds., Selected Areas in Cryptography—SAC 2009, Springer LNCS 5867, pp. 393–414,

and generic attacks on the construction were improved in

Zhenzhen Bao, Itai Dinur, Jian Guo, Gaëtan Leurent, and Lei Wang, ‘Generic Attacks on Hash Combiners’, Journal of Cryptology 145, 2019, pp. 1–82 (preprint).

Maybe it thwarts MD5 collision attacks, but if you can replace the hash function, you're probably better off switching to an unbroken hash rather than this generic construction which isn't as good.