1
$\begingroup$

I should be able to find a collision for a vulnerable hash function which uses AES ECB given a prefix, but I am unable to find a reasonable solution (besides brute-force attack).

The hash function is really simple, it uses AES ECB with a known IV with all 1's. The result is then bitwise XORed and used as key for next ciphering block (if any). More formally:
$$S_0=1^{128}, S_i=\operatorname{AES}_{S_{i-1}\parallel S_{i-1}}(M_i)\oplus S_{i-1}$$ with $M_i$ being the current 128-bit message block, AES using a 256-bit key and the $S_i$ of the last message block being the output.

I have been reading about the Chosen-prefix collision attack, but my case is slightly different (and even easier) because what I search are two words $w_1$ and $w_2$ that, given a known prefix $p$, $\operatorname{hash}(p \| m_1) = \operatorname{hash}(p \| m_2)$ with $w_1 = p \| m_1$ and $w_2 = p \| m_2$ and $w_1 \neq w_2.$

Improve this question
$\endgroup$
1
  • $\begingroup$ There's a paper from CRYPTO '93 that covers this hash function though it only notes an "obvious" direct attack, namely given $S_i$ and $S_{i-1}$ (which eg happens when you hash a 1 block message), you can easily find the pre-image. $\endgroup$
    – SEJPM
    Nov 12, 2018 at 15:30

1 Answer 1

Reset to default
1
$\begingroup$

but my case is slightly different (and even easier) because what I search are two words $w_1$ and $w_2$ that, given a known prefix $p$, $\operatorname{hash}(p \| m_1) = \operatorname{hash}(p \| m_2)$ with $w_1 = p \| m_1$ and $w_2 = p \| m_2$ and $w_1 \neq w_2.$

Actually, if two messages differ only in the last 128 bit block, they will always hash to different values (and hence they will be no such collision).

That is because, when processing the common prefix, the two messages will have identical $S_{i-1}$ values; the resulting hashes will be:

$$AES_{S_{i-1} || S_{i-1}}( M_i ) \oplus S_{i-1}$$

$$AES_{S_{i-1} || S_{i-1}}( M'_i ) \oplus S_{i-1}$$

These will be the same only if $AES_{S_{i-1} || S_{i-1}}( M_i ) = AES_{S_{i-1} || S_{i-1}}( M'_i )$, and because $AES_{S_{i-1} || S_{i-1}}$ is a permutation, that'd happen only if $M_i = M'_i$ (and hence we're hashing the same message, hence not a collision).

Now, if we are allowed to modify the problem (for example, if the two messages have different prefixes, if the 'word' inserted at the end is longer than 128 bits, or alternatively if the resulting hash is truncated to smaller than 128 bits), then it becomes easy. However, as stated, it is impossible (not infeasible, but logically impossible).

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for your answer. I understand your point, two messages of 128 bits processed with the same key can only have the same hash if they are the same message. In theory the words $w1$ and $w2$ can be longer than 128 bits, although they should always have the same prefix $p$. In fact, $p$ should be able to have a variable length, even greater than 128 bits. $\endgroup$
    – DMP
    Nov 12, 2018 at 18:28

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.

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