1
$\begingroup$

Can an SHA-256 plaintext be malleable? For example:

Given $y = hash(x)$ , can an attacker find $z$ so that $z = hash(f(x))$. Here $f()$ might be the addition of a suffix to the message, an XOR operation, or any other mathematical transformation.

I know there is one known malleability weakness shared in Merkle-Damgard constructions:

Given $hash(x)=y$, it is trivial to find $hash(x\mathbin\| s)=y'$ in which $\mathbin\|$ denotes concatenation. The attacker does not need to know what $x$ is. This is also known as a length extension attack.

Are there any other known examples of SHA256 hash malleability aside from the length extension attack? For instance, given $hash(x)=y$, can I find the output of hash($x \oplus s$) without knowing what $x$ is?

EDIT: A fellow contributor provided me with this link: What type of hash functions provides non-malleability of hash digests? But I don't think this answers my question in detail......

$\endgroup$
3
  • $\begingroup$ Does this answer your question? What type of hash functions provides non-malleability of hash digests? $\endgroup$
    – Marc
    Commented Jun 4, 2020 at 6:29
  • $\begingroup$ @Marc Um sorry but no. I was wondering whether there are any malleability weaknesses (aside from the length extension attack) in SHA256, but the link you gave me did not focus on SHA256 in particular. $\endgroup$
    – Anonymous
    Commented Jun 4, 2020 at 6:31
  • 1
    $\begingroup$ No, it is not. You would hear it on the news. Not when one says any other mathematical transformation that includes the hash itself, i.e. rehashing. What is your actual aim? $\endgroup$
    – kelalaka
    Commented Jun 4, 2020 at 6:48

1 Answer 1

1
$\begingroup$

I believe that, if you make a plausible-sounding assumption on the SHA256 hash compression operation, you can show that the only malleability SHA256 has are length extension attacks.

This plausible assumption is that, for a fixed input state, then the mapping between message block and output state acts like a random oracle [1]

With this assumption, suppose we a message $M_0$ which, after SHA-256 padding, is the sequence $N_0$, and a message $M_1 = f(M_0)$, which, after SHA-256 padding, is the sequence $N_1$, and we assume that $M_1$ does not have $M_0$ as a prefix (if it is, then this is a length extension attack).

If $M_0$ does not have $M_1$ as a prefix, then we can show that, after some integral number of SHA-256 blocks, $N_0$ and $N_1$ differ; at this point, the SHA-256 hash compression operation will map their states to random values, and after that point, the latter SHA-256 hash compression operations will continue to map the states to random values, and so the outputs will be effectively random (and hence you cannot compute one from the other).

And, if $M_0$ does have $M_1$ as a prefix (the attempted attack is a "length shortening attack"), then $N_0$ may have $N_1$ as a prefix; if it does, then the intermediate state of $M_0$ processing cannot be determined by the final $M_0$ output value (as it is effectively random), and $N_0$ doesn't have $N_1$ as a prefix, then the previous reasoning applies.

This argument is a bit hand-wavy; I believe that it's essence is valid.

[1]: Note that we cannot make the assumption that the entire hash compression operation acts as a random oracle, because we know how, given a message block $M$ and a delta $\delta$, we can find input and output states $S_0$ and $S_1$ with $S_1 = \text{Compress}( S_0, M )$ and $S_1 = S_0 + \delta$; this shows that the hash compression operation itself is distinguishable from a random oracle.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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