# If I concatenate two colliding SHA-256 messages with the same prefix and suffix, will the resulting hash output still collide with each other?

So let's say that there are two messages, $$x_1$$ and $$x_2$$, which hash to the same output. In other words, these two messages collide with each other:

$$\operatorname{SHA256}(x_1)=\operatorname{SHA256}(x_2)$$

Questions:

1. Now, let's say I append identical prefixes and/or suffixes to both $$x_1$$ and $$x_2$$:

$$\operatorname{SHA256}(p\mathbin\|x_1\mathbin\|s)\text{ and }\operatorname{SHA256}(p\mathbin\|x_2\mathbin\|s)$$

Now, will $$\operatorname{SHA256}(p\mathbin\|x_1\mathbin\|s)=\operatorname{SHA256} (p\mathbin\|x_2\mathbin\|s)$$ as well?

2. Considering another slightly different scenario here - a partial collision rather than a full collision.

Let's say $$\operatorname{SHA256}(x_1)$$ collides with $$\operatorname{SHA256}(x_2)$$ in the first 80 bits.

Now, if I add identical prefixes and suffixes to $$x_1$$ and $$x_2$$:

$$\operatorname{SHA256}(p\mathbin\|x_1\mathbin\|s)\text{ and }\operatorname{SHA256}(p\mathbin\|x_2\mathbin\|s)$$

Will $$\operatorname{SHA256}(p\mathbin\|x_1\mathbin\|s)$$ still collide with $$\operatorname{SHA256}(p\mathbin\|x_2\mathbin\|s)$$ in the first 80 bits as well?

The Generic Collision attack

Finding a collision with the generic collision attack for SHA256 requires $$2^{128}$$ computations with %50 probability of success. This bound is given by the birthday attack. There is no attack on SHA256 better than a generic collision attack yet practical. Assume that you have luckily found one; $$\operatorname{SHA256}(x_1) = \operatorname{SHA256}(x_2)$$

Let's remember the SHA256 padding that uses 512 block size with the message length added to the end with 64-bit. NIST 180-4 page 13

Suppose that the length of the message, $$M$$, is $$\ell$$ bits. Append the bit $$1$$ to the end of the message, followed by $$k$$ zero bits, where $$k$$ is the smallest, non-negative solution to the equation $$\ell - 1 - k \equiv 448 \pmod{512}.$$ Then append the 64-bit block that is equal to the number $$\ell$$ expressed using a binary representation.

1. Now, will $$\operatorname{SHA256} (p\mathbin\|x_1\mathbin\|s)=\operatorname{SHA256} (p\mathbin\|x_2\mathbin\|s)$$ as well?

If $$len(p)$$ is a multiple of the 512 then the result of $$\operatorname{SHA256} (p\mathbin\|x_1) = \operatorname{SHA256} (p\mathbin\|x_2)$$ will be same, this is like an extension attack on $$p$$. Otherwise the you have $$1/2^{256}$$ probability to hit the collision with one try.

What about the suffix $$s$$. This is not like the length extension attack since we have to consider the padding of $$x_1$$ and $$x_2$$ in $$\operatorname{SHA256}(x_1)$$ and $$\operatorname{SHA256}(x_2)$$, repectively. If one choose $$s$$'s beginning as the padding of $$x_1$$ and $$x_2$$ then it can be extension attack as long as the $$len(x_1) = len(x_2)$$. Otherwise, the collision is random collision.

As a result; the combination $$(p\mathbin\|x_i\mathbin\|s)$$ requires so much condition about the $$p,x_1,x_2,s$$ to have the collision with $$1/2^{256}$$ probability to hit the collision with one try.

In short, NO.

1. Will $$\operatorname{SHA256} (p\mathbin\|x_1\mathbin\|s)$$ still collide with $$\operatorname{SHA256} (p\mathbin\|x_2\mathbin\|s)$$ in the first 80 bits as well?

No. Even you have the collision the value will be different.

• So if x1 and x2 collide in the first 80 bits, and I perform a length extension attack to produce H(s∥x1) and H(s∥x2) - then H(s∥x1) and H(s∥x2) won't collide in the first 80 bits either? I'm wondering why this would be the case........ Mar 15, 2020 at 15:58
• If you consider how the SHA256 operates, that will be more clear. Since the new inputs are different the hash value will be different. Mar 15, 2020 at 16:34