The length extension attack and security on length shortening of a hashed message by one byte

Question

MD5, SHA1, SHA2 are vulnerable to length extension attacks Wikipedia:Length extension attack.

Could is also be possible to generate $H(\text{message}[1..n-1])$ from $H(\text{message}[1..n])$ if I know the last byte?

It's essentially the same question as md5: is reverse length-extension attack possible?

Might it become possible, when I just want to shorten the message by just one byte in any of MD5, SHA1 or SHA2? Or could I at least reduce the computational cost of a brute force attack?

Answer 1

Could is also be possible to generate $H(\text{message}[1..n-1])$ from $H(\text{message}[1..n])$ if I know the last byte?

No, the length extension attacks are not working exactly like that. Let see how MD5 operates;

MD5 divides a message into 512-bit blocks to operate¹ in Merkle–Damgård fashion way. Every message is padded. The messages are padded with 1 and following many zeroes so that the padded message size is multiple of 512 with the message length appended at the end represented in 64 bits. In a minimum way with always 1 is added the number of zeroes can be zero.

More formally, add bit 1 than add as many as required bit 0 until message length in bits $\equiv 448 \pmod{512}$ then add the message length in 64 bits. This also limits the file size that can be hashed with MD5.

So the $message[1..n-1]$ is calculated with $message[1..n-1] \mathbin\| padding$. After the padded message one can execute the length extension attack. The extended message with padding is;

$$\text{message}[1..n-1] \mathbin\| \text{padding} \mathbin\| \text{extension}\mathbin\|\text{padding}$$

To execute a length extension attack, one replaces the initial value of the target hash function with the hash. After this calculate the extended hash as usual hashing. Formally

• let $\text{MD5}'(m,\text{MD5IV}) = \text{MD5}(m)$. I.e. $\text{MD5}'$ enables to control of the IV of the MD5.
• let $h = MD5(m)$ of a message $m$.
• then $h' = MD5'(m', h) = MD5(m\mathbin\|pad_1\mathbin\|m'\mathbin\|pad_2)$ where the $pad_1$ is the padding of $m$ when hashed with MD5 and $pad_2$ is the padding of $m\mathbin\|pad_1\mathbin\|m'$

The $h'$ is the length extended hash.

Might it become possible, when I just want to shorten the message by just one byte in any of MD5, SHA1 or SHA2? Or could I at least reduce the computational cost of a brute force attack?

After SHA3, there are variants of SHA2 like SHA512-256 that calculates a hash of output size 512 bits then truncates to 256. That almost eradicate the length extension attack's possibility. The SHA512-256 has a different initial value from SHA512-512 that separates the domains. In other words, they are different random oracles.

Of course, the pre-image resistance and secondary pre-image resistance and the collision resistance are weakened by $2^8$, $2^8$, and $\sqrt{2^8}$, respectively.

---

_{¹The dividing is not specific to MD5 and dividing size may change with each hash function like SHA512 uses 1024 bit block sizes}

Answer 2

No, currently not even MD5 is broken enough for this.

MD5 and SHA-1/2 all use a simple Merkle-Damgard construction. In an MD construction basically what you get is (for a message split into two message blocks):

$$H(M) = H'(H'(C, B'_1), B'_2)$$

where $C$ is a known constant and $B_i$ consists of the message blocks, with a padded last block.

Now if $H'$ was reversible then a (internally padded) single block message would also be reversible. Every output bit of $H'$ depends on all the input bits. So to generate a new hash you need to know all the input bits, even the ones produced before.

It would be easier if the messages could have any data other than that one of the messages must be one byte shorter. That translates into a collision search with a restriction that the last block has different input data. I don't think this is feasible at the moment either, but it would give some advantage to an adversary as it at least depends on collision resistance, which is broken for SHA-1 and destroyed for MD5.