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

Question

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?

Answer 1

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

The SHA256 padding

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.

back to your questions;

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.

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