1
$\begingroup$

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?

| improve this question | | | | |
$\endgroup$
1
$\begingroup$

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.

  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.

| improve this answer | | | | |
$\endgroup$
  • $\begingroup$ 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........ $\endgroup$ – Biology nerd Mar 15 at 15:58
  • 1
    $\begingroup$ If you consider how the SHA256 operates, that will be more clear. Since the new inputs are different the hash value will be different. $\endgroup$ – kelalaka Mar 15 at 16:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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