Is the hash function defined in this exercise collision-resistant?

Question

I have this problem:

"Let ${\rm Enc}_k(m)$ a safe block encryption system. We define a hash function $H(m)$ as follows:

1. $m$ will be concatenated with $0$ until $|m|$ is a multiple of len(block);
2. we break the sequence $m$ into $n$ blocks like $m = m_0 \mathop\| m_1 \mathop\| m_2 \mathop\| \dots \mathop\| m_{n-1}$;

3. we apply this algorithm:

   c ← Encm0(m0)
   for i = 1 to n-1 do
     d ← Encm0(mi)
     c ← c NOR d
   end for
   H(m) ← c

Where c NOR d denotes the bitwise operation NOT (c OR d), i.e. (for single bits) 1 NOR 0 = NOT (1 OR 0) = NOT 1 = 0.

Is this $H$ resistant to collisions?

Answer 1

If you got $n$ blocks, then you compute the encryption of each block, and let's look at one bit at position $j$. Let's call this $c_{i,j}= E(m_i)[j]$.

Now what you will get at position $i$ in your output is $(((c_{i,1} \bar{\vee} c_{i,2}) \bar{\vee}c_{i,3}) \bar{\vee} \dots )\bar{\vee}c_{i,n}$.

If we assume that all $c_{i,j}$ are evenly distributed in $\{0,1\}$, then the innermost term will evaluate to $1$ with probability $\frac{1}{4}$. The next term will have a probability to be $1$ of $\frac{3}{4}\times \frac{1}{2}=\frac{3}{8}$. In general, this will approach a probability $p$, s.t. $p=(1-p)\frac{1}{2}\Rightarrow p = \frac{1}{3}$

So, what is the problem with this? Assume we have such a hash value. If in the second to last term evaluates as $1$, then it does not matter what $c_{i,n}$ is, because $1 \bar{\vee} x = 0$ regardless what $x$ is. This will happen for roughly $\frac{1}{3}$ of all positions. So for these positions, it actually doesn't matter what the value of $c_{i,n}$ is. And that means, we just have to modify the last block in a way, that the other $\frac{2}{3}$ of positions don't change. Finding such a partial collision for the encryption function is still challenging, but far easier than actually breaking the encryption scheme. Of course the probability actually depends on the blocksize of the encryption scheme.

Answer 2

The padding scheme isn't collision resistant.

For any message $m$ where $|m| \not\equiv 0 \pmod n$, there will always be a collision between $m$ and $m || 0$.

Answer 3

To build on tylo's answer, here's a practical internal collision attack on this construction, assuming that the block cipher $\rm Enc$ has a 128-bit block size (like AES, for example) or less:

1. Pick an arbitrary initial block $m_0$, and calculate $c_0 = {\rm Enc}_{m_0}(m_0)$. If $c_0$ has less than $n/2 = 64$ bits set, pick a new $m_0$ and repeat. (On average, this step takes less than two iterations.)

   For our collision, we wish to find two additional blocks $m_1 \ne m_1'$ such that the bitstrings $d_1 = {\rm Enc}_{m_0}(m_1)$ and $d_1' = {\rm Enc}_{m_0}(m_1')$ differ only at bits that are set in $c_0$, so that $c_0 \mathop{\bar\lor} d_1 = c_0 \mathop{\bar\lor} d_1'$.

2. To find such a pair, generate a sequence of distinct arbitrary blocks $m_1^i$ and calculate $d_1^i = {\rm Enc}_{m_0}(m_1^i)$ for each of them until you find a pair $i \ne j$ such that $d_1^i$ and $d_1^j$ differ only at bits that are set in $c_0$.

   Since $c_0$ has at most $n/2 = 64$ bits unset, a pair of random $n$-bit blocks has at probability of at least $1/2^{n/2}$ of being identical at all the bits that are unset in $c_0$. Thus, by the birthday theorem, we only need to generate about $2^{n/4+1} = 2^{33}$ random blocks on average to find such a pair.

   As the block cipher $\rm Enc$ is, by assumption, secure, ${\rm Enc}_{m_0}$ is effectively indistinguishable from a random permutation, and thus (by the PRF-PRP switching lemma) also indistinguishable from a random function using less than about $2^{n/2}$ queries. Since we only need about $2^{n/4+1}$ queries to find the collision we want, we're well below this bound, and can thus treat the encrypted blocks $d_1^i$ as random, validating the argument above.

Thus, with only about $2^{33}$ block cipher calls, we can find two messages $m = m_0 \mathop\| m_1$ and $m' = m_0 \mathop\| m_1'$ such that $m \ne m'$ but $H(m) = H(m')$.

Further, since this collision is internal, $H(m \mathop\| x) = H(m' \mathop\| x)$ for any suffix $x$; in particular, this means that this collision will remain even if we add proper length padding to prevent length extension attacks, like the trivial collision attack in squeamish ossifrage's answer.

---

Ps. Of course, we could save some time in step 2 by generating many candidate blocks $m_0$ in step 1, and picking the one for which $c_0 = {\rm Enc}_{m_0}(m_0)$ has the most bits set, but I was too lazy to figure out the optimal number of candidates to try.

Conversely, even for a fixed initial block $m_0$, it's very unlikely for the number of bits set in $c_0$ to be much less than $n/2$, and thus the attack will rarely take more than, say, $2^{40}$ block cipher evaluations.

Also, the same method can also be used to generate collisions in later blocks, if we wish to e.g. select a chosen prefix for our messages.

In fact, the optimal collision-finding method might be to pick a fixed initial block $m_0$, generate $2^{n/8} = 2^{16}$ second blocks $m_1^i$, compute $c_1^i = c_0 \mathop{\bar\lor} {\rm Enc}_{m_0}(m_1^i)$ for each of them, and then try to find a pair of third blocks $m_2^j \ne m_2^k$ such that $c_1^i \mathop{\bar\lor} {\rm Enc}_{m_0}(m_2^j) = c_1^i \mathop{\bar\lor} {\rm Enc}_{m_0}(m_2^k)$ for some $i, j, k$, which should take (very roughly) about $2^{n/8} + 2^{\frac{n/4+1}{n/8}} \approx 2^{n/8 + 1} = 2^{17}$ block cipher calls.

In particular, this modified attack should remain practical even for ciphers with $n = 256$ bit blocks.