Reversing SHA1 (don't know the correct term)

Given sha1(pad(A) || pad(B)), where B is known, can I calculate sha1(pad(A))? pad(A) means its length is exactly 1 block (64 bytes for SHA-1)

If yes, for which other hash functions it will work too?

Would it work vice versa when A is known?

Why do I think it's possible?

If you take a look on SHA-1 source, 16 ints block is expanded to 80 ints and then during 80 rounds one int is added using invertible operations. When you have the block in plaintext, you can calculate the expanded block and revert the hash round by round until you'll get the IV of the block, i.e. the hash of the last block. Do you understand what I mean?

-
This sounds like a homework question. Also, what do you mean by 'pad(A)'? –  pg1989 May 30 '13 at 19:28
pad(X) means it has length of 1 block (20 bytes in case of SHA1). "This sounds like a homework question." - even if, is that bad? –  Smit Johnth May 30 '13 at 19:33
@SmitJohnth: I personally don't have problems with homework questions, but I think it is common courtesy to specify if it is, e.g. with the [homework] tag. –  Reid May 30 '13 at 19:36
@SmitJohnth: Some people prefer to give hints to homework questions instead of full-blown answers; this is extremely common on math.se, for instance. Others might consider it dishonest to ask a site like this a homework question without advance notice. I'm ambivalent on the whole matter, personally. –  Reid May 31 '13 at 0:59
@Smit Johnth: with current block data, here pad(B), yes you can "generate expanded buffer"; but, even knowing the final hash, your intuition that you can "reverse the hash generation to beginning of the block" seems wrong to me, based on the fact that the round function $S_{j+1}=F(S_j,M_j)$ has the structure $F(S,M)=E_M(S)\boxplus S$ where $E$ is a block cipher, and $\boxplus$ is some hybrid between addition and XOR. –  fgrieu May 31 '13 at 5:02

To answer your question, you have to know how SHA1 works (in the broad strokes at least). For brevity, $H$ below means SHA1.

First, a message is padded with a 1 bit, a bunch of zero bits, and the length. This is done to make it a multiple of 512 bits, since that's the block size. Even if the message is already a multiple of 512 bits, this padding happens anyways. So, in the case of $H(a||b)$, where $a$ and $b$ are both 512 bits, there will be three blocks.

SHA1 has an "internal state" consisting of five 32-bit integers. These internal state variables are initialized to known constants at the beginning of the computation.

Then, for each block $m$, $m$ is expanded (the details aren't terribly important). Once it's expanded, the expanded message is ran through a compression function, which takes the current hash state, copies it over into a new set of 32-bit integers (often $a$ through $e$) and then "compresses" the message through a series of 80 rounds, constantly modifying $a$ through $e$ in the process. At the end of the 80 rounds, the global hash state is updated by adding $a$ through $e$ back into the five "global" 32-bit integers.

After the last block, the output of the hash is the hash state, usually (but not always) encoded in hex. But that's just a matter of style.

The answer to your first question, whether or not you can find $H(a)$ given $H(a||b)$ and $b$ where $a$, $b$ are the block size of the hash, is no. I've been back and forth on this issue, but I see no way to do this.

The issue is that at the end of each block, the output of $f(m)$ is added to the input state of $f(m)$. So in the case of $H(a||b)$, the output of that hash is the result of $f(p)$ (where $p$ is the padding block) plus the input state to $f(p)$. If the output were just the last round of the compression function, then you could use the fact that you know the message to reverse the rounds of the compression function and arrive at the original input state. From there, you could do the same for the the $b$ block and arrive at the result of $f(a)$. Then you repad the message and arrive at $H(a)$. But since you don't know the input state for the last block, you don't know the output of the last round.

I see no way to get around this. As I said, I've been back and forth on this issue, but my intuition has been that this should not have been possible. For more details, see the edit history of this post. I explain all of my logic in excruciating detail.

As for the second part of your question, if you know $a$, then one could compute $f(a)$ and use that as the internal state for the computation of $f(b)$. So, you know the beginning state of the compression function, but you don't know the message being used. So, to figure out $f(b)$, you'd need to know the message. Can you reverse the rounds if you know the internal state? No, because $H(x)$ is one-way (preimage resistant), even when $x$'s size is a block size or less. We know the starting constants for the algorithm and it still isn't broken.

Indeed, there is a secret-suffix MAC, defined as $\operatorname{MAC}(k, m) = H(m||k)$. This construction is somewhat secure so long as $H$ is collision resistant. But this requirement is difficult to satisfy, so the secret-suffice MAC is generally recommended against. At any rate, if it were possible to to find $H(b)$ in this case, it would be a serious break in the secret-suffix MAC where the key's length is the same as the block size. So, I don't think this is possible, but I've been wrong before. :)

-
Perhaps I will get this answer correct eventually! –  Reid May 31 '13 at 4:52
Afaik output of compression function = output of hash function, since opposing to MD5 SHA-1 doesn't have finalisation. –  Smit Johnth May 31 '13 at 9:06
Would you probably write a short summary of your post? It's hard to read. –  Smit Johnth May 31 '13 at 9:15
@SmitJohnth: Agreed! I didn't realize just how long it had gotten. I've now summarized the key points of my previous post, and I think the result is much better. It actually fits on one screen now. –  Reid May 31 '13 at 13:37
Well, I overlooked this addition. Seems SHA-1 is resistant against this type of attack, but is it really so? –  Smit Johnth May 31 '13 at 19:57

SHA-1's compression function (as well as MD5 and SHA-2) is build from a (custom-made) block cipher in the Davis-meyer construction. (These are the "invertible operations" you describe in the question.)

The basic idea is to use the message block as the key for the cipher to "encrypt" the previous state:

                    message block
|
↓
.---------.
previous state ----> | Encrypt | ----> new state
'---------'


If this would be the only thing to do, then we actually could (knowing a block of the message and the new state) revert the cipher to calculate the previous state, just like you sketched in your question.

A compression function with this property is not what we call a "one-way" compression function, and would not be a good thing to use as a compression function for a hash function. Therefore this is not what is actually done, the Davis-meyer construction has one more step:

                    message block
|
↓
.---------.
previous state ----> | Encrypt | --⊕---> new state
\   '---------'   ↑
\                /
\--------------/


This XORing of the "ciphertext" with the "plaintext" has the effect that we don't know the ciphertext output of the block cipher, and can't do our backtracing. This is actually enough to make the compression function one-way, if the block cipher is secure (for some formal notations of one-way and secure).

If yes, for which other hash functions it will work too?

As explained, no hash function with your trackback property can be deemed secure, so we can conclude that no modern hash function should have this property.

Would it work vice versa when A is known?

If A is known, you also know sha1(pad(A)), e.g. the state after hashing the first block, e.g. the input to the second block.

Looking at the diagram above, we now know both the plain text input as well as the cipher text output of the block cipher. From this deriving the (or any) used key is known as a known-plain text key retrieval attack (or chosen-plaintext, if the attacker can actually influence A and see hash(pad(A)||pad(B))). If the block cipher is any good, it should not feasible to retrieve any useful information about the key pad(B) (other than by trying examples, i.e. brute forcing).

-