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

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?
-
I think the generic attack doesn't involve that. $\;$ – Ricky Demer May 11 '14 at 17:46
@RickyDemer Parallel brute force is still brute force, though, isn't it? Doesn't a method have to be faster than brute force before the method itself is regarded as an attack? – jthill May 11 '14 at 17:59
Even if so, the paper I linked to gives a method that I think doesn't use any metric as you described. $\hspace{.36 in}$ – Ricky Demer May 11 '14 at 18:11
"exhaustive search" $\: \mapsto \:$ "[generic collision search](http://people.scs.carleton.ca/~paulv/papers/JoC97.pdf)" $\hspace{1.8 in}$ – Ricky Demer May 11 '14 at 21:31
Hm. Always assuming I'm reading this right (I think I understand...) -- although this does get much better performance than a naive exhaustive search by being massively parallelizable and clever with its iteration and sequencing, it's still exhaustive search of the hash result space -- $g$ in both sect. 4.1 and sect. 5.2 iterates on $R$, the hash result (edit: the cleverness in sequencing not improving the likelihood of encountering a collision early, only enabling the parallelism). Is this incorrect or otherwise irrelevant here? – jthill May 11 '14 at 23:53

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.

-
Near as I can tell, the Joux construction is built on a (reasonably) posited machine to produce collisions on $f(IV,B_n)$. But that machine is useless with $\mathcal H$ as above, as there are at least two IVs for each block, all but one of them completely unpredictable. Am I missing something fundamental here? From Kelsey and Schneier's paper, "In Joux's technique, a sequence of single-message-block collisions is found, and then pasted together to provide a large number of different messages of equal length that lead to the same hash value." -- and that's what I believe just won't work here. – jthill May 13 '14 at 1:59
@jthill, you're right. I don't have a working attack with Joux multicollisions. I'm still skeptical. Without a proof, I don't know how we could be confident that this construction adds any security (Joux multicollisions are an example of something that showed simple intuitions regarding techniques for strengthening hashes can be very wrong). I'm not at all confident that this construction cannot be attacked -- maybe it does have nice security properties, but I think we'd need a proof before we could trust that it does. – D.W. May 13 '14 at 5:52
Thank you. I see your point about the speed, to add a 40-bit buffer against parallel search, the most efficient way would be to switch to an 80-bit-longer hashcode. Re proof, this am I ran across "we are unable to prove that, perhaps tomorrow, some novel and devastating attack will not show it to be critically insecure. Every hash function will necessarily contain such a component, at least until a proof that P!=NP is found, and possibly long after that." ... "will necessarily"? – jthill May 13 '14 at 15:17
That said, though, and acknowledging (the obvious,) that I'm a complete tyro at this, isn't it enough to say that $\mathcal H^\prime$ is trivially at least as secure as the underlying hash function $H$, and is additionally immune to any attack based on finding single-block collisions with a known IV? I think it's reasonable to presume a block function "sufﬁciently complex that it behaves like a random mapping" – jthill May 13 '14 at 16:16
Well, it appears I may have just reinvented HMAC with feedback-derived password. Might as well just use that. – jthill May 14 '14 at 23:54