2
$\begingroup$

Suppose we have a $512$-bit (or $512\times n$ bit) message that we'd like to hash using SHA-256. I've looked at the implementation, and from what I understand, after padding, there will be a total of $2$ (or $n+1$) message "blocks" that are fed into the function, with the last block being completely padding. The last message block in this scenario is completely known, it should begin with the "1" bit that marks the beginning of the padding, followed by a bunch of zeros, followed by the message size in bits.

So now, let's say we hash the message. If we follow the chain, the first "hash value" is known, it's the $H_0$ of SHA-256 which is the following (from wikipedia):

h0 = 0x6a09e667   h1 = 0xbb67ae85   h2 = 0x3c6ef372   h3 = 0xa54ff53a
h4 = 0x510e527f   h5 = 0x9b05688c   h6 = 0x1f83d9ab   h7 = 0x5be0cd19

But for every subsequent execution of the compression function, the values above will be changed. My question is, since we know the final message block, can we compute the intermediate hash right before the last hash $H_n$ using just the final message block (which is fully known), and the output final hash $H_{n+1}$?

$\endgroup$
  • 1
    $\begingroup$ Welcome to crypto.SE! Your first question is right on-topic, congratulations. I've polished the notation with some $\LaTeX$ / MathJax (see this or this for how), and trimmed it slightly (we prefer to have only technical matter in a question). I also fixed an off-by-one in the block numbering: when $n=1$, we have two Davies-Meyer compression functions, thus the hash is $H_2$. $\endgroup$ – fgrieu Jun 26 at 5:21
3
$\begingroup$

Can we compute the intermediate hash $H_n$ using just the fully known final message block, and the final hash output $H_{n+1}$?

No, that's computationally infeasible. The only known way to find $H_n$ is when we know all (or enough of) the message, which allows to directly compute $H_n$ in the forward direction (or use brute force search of a small unknown fraction of the message, validating a guess by checking if the final $H_{n+1}$ matches).

The reason we can not compute $H_n$ is that the Davies-Meyer round function $(H_n,M_n)\mapsto H_{n+1}$ restricted to fixed known $M_n$ is computationally difficult to invert.

That follows from its construction as $H_{n+1}\gets E(\text{key}\gets M_n, \text{block}\gets H_n)\boxplus H_n$ where $E$ is a public block cipher and $\boxplus$ is a group operation¹ on $\{0,1\}^{256}$ (256-bit bitstrings).

If some fairy told us the output $X$ of $E(\text{key}\gets M_n, \text{block}\gets H_n)$, and since we know $M_n$ and $H_{n+1}$, we could find $H_n$ in two ways:

  • by using the decryption function $D$ matching $E$, with $H_n\gets D(\text{key}\gets M_n, \text{block}\gets X)$
  • by inverting $X\boxplus H_n\mapsto H_{n+1}$ to find $H_n$ from the known $H_{n+1}$ and the $X$ given by the fairy.

But we have no fairy, and there is no known way out of this chicken-and-egg problem. That's even provable under a model of $E$ as an ideal cipher. That's by design of the Davies-Meyer round function.

Also: it is likely that for a sizable fraction of the final hash $H_{n+1}$ and message size (equivalently, values of $M_n$ ), the known relation $H_{n+1}=E(\text{key}\gets M_n, \text{block}\gets H_n)\boxplus H_n$ leaves several possible values for $H_n$.


¹ $\boxplus$ happens to be addition of 256-bit bitstrings ignoring carry bit between blocks of 32 bits.

| improve this answer | |
$\endgroup$
  • $\begingroup$ It is augmented Davies-Meyer since it uses $\oplus$. Also, Do you mean we know all of the messages instead of we know enough of the message? Here, enough is not measurable. $\endgroup$ – kelalaka Jun 26 at 7:21
  • $\begingroup$ @kelalaka: By this account, straight Davies-Meyer uses $\oplus$, and $\boxplus$ or any group operation on $\{0,1\}^{256}$ does not change the security argument, thus I see no reason for augmented. I meant we know enough of the message to carry a brute-force search of what we do not know. Tried to make that clearer. $\endgroup$ – fgrieu Jun 26 at 7:27
  • $\begingroup$ Thank you so much for this detailed answer! In the case where $X$ is known you said that one of the ways to find $H_n$ would be to use the decryption version of the compression function. Is the decryption function $D$ public/known for the Davies-Meyer compression function? Or does it even exist at all? $\endgroup$ – George T Jun 27 at 6:40
  • $\begingroup$ Yes, it exists $D$ inverting the block cipher $E$ part of the Davies-Meyer construction used in SHA-256. This $D$ is about as simple and efficient as $E$, and not hard to derive. That also holds for MD5, SHA, SHA-1, and SHA-512. Basically, each step is inverted nearly in reverse order of the encryption $E$. Pseudocode for that is there in the case of SHA-256. It turns out to be difficult to make block ciphers where decryption is much harder than encryption, and the SHA family does not use one. $\endgroup$ – fgrieu Jun 27 at 6:52
  • $\begingroup$ This comment is probably better fitted for the question that was linked but I don't have 50 reputation yet so I can't post it there. Anyways, in your answer to the linked question you state that "G is a bijection, fully determined by the 512-bit padded message block". My question is, how do you know that for a given message block M, G (the block cipher) is a bijection? In other words, how do you know that the block cipher won't ever map two inputs to the same output, is there a proof for this? Sorry for the late reply, I had to think about this for a while. $\endgroup$ – George T Jul 30 at 0:29

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.