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

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?

• With NOR it's going to tend to 2/3 of the bits being zero, so that will reduce the collision resistance. May 19, 2015 at 8:08
• Generally, the point of homework exercises is to give you some practice in applying the methods you've learned, and to help you notice any gaps in your skillset. Thus, to get the full benefit from the exercises, you should first try to solve them as far as you can on your own, and only then turn to others for help. In particular, when asking for help with homework on Stack Exchange, it helps a lot if you mention how far you've got on your own (even if it's "I tried X and Y and Z, but none of them work because..."), and where specifically (you think) you're stuck. May 19, 2015 at 12:34
• The key to this is recognizing that pairs of message blocks (with identical contents) will only clear bits in the hash at that stage (wherever the corresponding bit is set in the encrypted block). This lets you insert any number of additional repeated pairs of such blocks without changing the hash value. It also lets you easily set the hash back to zero. May 19, 2015 at 17:04

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.

• No, it's very unlikely you'd get all zeroes. Any position that's zero will get turned into a one if the mixed input is zero (which you'd expect 50% of the time). The probability approaches 1/3 that any bit will be a one (2/3 chance of being 0 times 50% chance of being 0 yields 1/3 chance of resulting in 1, 2/3 chance of 0). May 19, 2015 at 10:11
• You're right. I adapted the answer to make up for my earlier error.
– tylo
May 19, 2015 at 10:48

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$.

• This is true (and should certainly be counted as a correct answer), but it's probably not the answer the author of the exercise was looking for. (If it was, why bother with all the extra details about the internals of the hashing algorithm?) May 19, 2015 at 12:37
• It's likely part of the answer, though, else the padding scheme wouldn't have been part of the problem. The padding, the use of NOR, and the use of the first block as the key for encrypting all the blocks (allowing pairs of encrypted blocks) are the three glaring problems with the hash. May 19, 2015 at 17:17

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.