Assume we have a secure block cipher $E$ (strong pseudorandom permutation) and a fixed key $k$ which are publicly known. We construct our hash function $H(m)$ as $$ H(m) = E_k(m_1) \oplus \dots \oplus E_k(m_t) $$ where $m = m_1 \mathbin\Vert m_2\mathbin\Vert\dots \mathbin\Vert m_t$. Here all $m_i$ are $128$-bit blocks.

I know that just using XOR is not a secure hash function due to collisions at zero and commutativity. So for even $t$ we could have $m_i = m_j$ for all $i,j \leq t$ which produces collisions at zero which seems to break collision resistance.

Can anyone confirm my example about collision resistance give me some intuition how to break or prove pre-image and second pre-image resistances of this hash function?

  • 3
    $\begingroup$ Your attack on collision resistance is correct. Another possible attack would be to swap any two differing blocks. For preimage resistance consider that you can efficiently invert the block cipher because you have the key. Hint: the attack allows you to choose all but one block arbitrarily. $\endgroup$
    – Maeher
    Apr 23, 2022 at 9:00


Your Answer

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