6
$\begingroup$

In this answer and discussion, it is considered a distributable hash

$$\tilde H(m)\ =\ H\Bigl(\bigl(H(m_1\mathbin\| 1)\oplus H(m_2\mathbin\|2)\oplus\dots\oplus H(m_n\mathbin\|n)\bigr)\mathbin\|n\Bigr)$$

where the $m_i$ are $n$ segments (say of fixed size) of message $m$, and $H$ is a cryptographic hash (say of $b$-bit and assumed secure in the ROM).

What can we say about the collision-resistance of $\tilde H$ as a function of $b$ ?

$\endgroup$
  • 1
    $\begingroup$ Thanks for questioning my handrolled crypto! Whoops! Although IIUC it is still a valid answer, just weaker than I realised. $\endgroup$ – cypherfox Mar 15 '18 at 17:56
10
$\begingroup$

What can we say about the collision-resistance of $\tilde H$ as a function of $b$ ?

That it is effectively nonexistent; it is easy to generate collisions (and second preimages).

You can generate a second preimage by selecting two blocks $m'_i, m''_i$ to correspond to each original block $m_i$; you compute $H(m'_i \mathbin\| i), H(m''_i \mathbin\| i)$, and then use linear algebra (e.g. Gaussian Elimination) to see which combination of $m'_i, m''_i$ all xor the same as the original sequence of $m_i$; that combination hashes to the same value. As long as the original message is at least $b$ blocks long (that is, $n \ge b$), such a combination exists with good probability.

Once you can create second preimages, you can generate collisions by picking a message and generating a second preimage for it.

$\endgroup$
  • $\begingroup$ Would this not imply an attack against PMAC? Or does the keyed-PRP defend against this? What about if we fix the key? $\endgroup$ – cypherfox Mar 15 '18 at 17:43
  • 2
    $\begingroup$ @cypherfox: it doesn't apply to PMAC, because in PMAC, the $H$ function (using the above terminology) uses a secret key (and hence the attacker can't compute it directly). If you fix the key, well yes, PMAC rather falls apart (as do a bunch of other MACs); MACs (in general) have no guaranteed security properties if the attacker knows the key $\endgroup$ – poncho Mar 15 '18 at 17:46
  • $\begingroup$ Well that is unfortunate. :/ $\endgroup$ – cypherfox Mar 15 '18 at 17:48
  • $\begingroup$ Updated my answer. $\endgroup$ – cypherfox Mar 15 '18 at 17:49
  • 1
    $\begingroup$ Reference: M. Bellare and D. Micciancio, ‘A New Paradigm for collision-free hashing: Incrementality at reduced cost’, In W. Fumy, ed., Advances in Cryptology—EUROCRYPT'97, Springer LNCS 1233, 1997. Full paper, where it is called XHASH with details on poncho's answer in Appendix A, and related work. $\endgroup$ – Squeamish Ossifrage Mar 16 '18 at 1:17
4
$\begingroup$

While the other answer is correct, I want to point out that the construction is theoretically collision-resistant when $n$ is a fixed constant (independent of the security parameter) and $H$ is modeled as a random oracle.

Specifically, to find a collision, the adversary would (with overwhelming probability) have to find a structure like $H(m_1 \| 1) \oplus \cdots \oplus H(m_n \| n) = H(m'_1 \| 1) \oplus \cdots \oplus H(m'_n \| n) $. For a random oracle with $b$ output bits, and an adversary who makes $q$ queries, the probability of any subset of the queries satisfying such a relation is at most $q^{2n}/2^b$.

$q^{2n}/2^b$ is technically a negligible function, which makes this construction technically collision resistant in the asymptotic sense. But it's really bad/impractical, since in practice your parameters should satisfy $b\ge 256n$.

$\endgroup$
  • 1
    $\begingroup$ Limited to the case $n = 4$, this is the basic conceit of Rumba, which may be worth citing here. $\endgroup$ – Squeamish Ossifrage Mar 16 '18 at 1:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.