Assuming I have single-key Even-Mansour with single $2n$-bit permutation in wide-pipe Merkle-Damgård specifically with Matyas-Meyer-Oseas mode outputting $n$-bit hash.

What security can I expect against collisions and preimages?

Am I wrong to expect $2^\frac{n}{2}$ for both?

  • 1
    $\begingroup$ Does this mean the recurrence is $H_{i+1}:=E(M_i\oplus H_i)\oplus M_i\oplus H_i$ with each quantity $2n$-bit, where $M_i$ is one of $k$ padded message block(s), $H_0$ an arbitrary constant, and a certain half of $H_k$ is the final $n$-bit hash? $\endgroup$
    – fgrieu
    Jul 6 at 17:17
  • $\begingroup$ @fgrieu-onstrike Yes. $\endgroup$
    – LightBit
    Jul 6 at 17:32
  • $\begingroup$ I don't immediately see a preimage attack with cost $\mathcal O(2^{n/2})$. Do you? $\endgroup$
    – fgrieu
    Jul 6 at 18:02
  • 1
    $\begingroup$ See §3 of Luo-Lai $\endgroup$ Jul 7 at 1:06
  • 1
    $\begingroup$ In §2.3, Knudsen points out the issue when both $L_1$ and $L_2$ are the identity. That is, if $h_i \oplus m_i = h_i' \oplus m_i'$ you get a collision. $\endgroup$ Jul 7 at 18:00


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.