If I have a hash of some string in the form: hash(UNK + "known"), Is there a way to calculate the hash of (UNK + "known" + "append"), given the hash of the original value?

Specifically I'm asking about the sha512 algorithm.

Basically, I'm asking if the algorithm works by hashing the old hash + new input, or if it only hashes the input by itself.

Thanks!

New contributor
Brandon Overall is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
up vote 5 down vote accepted

What you are looking for is called a length extension attack. A length extension attack is, when an attacker given and $h = H(m)$ is capable to compute $h' = H(m\|m')$ for some $m'$ without knowing $m$.

Hash functions constructed using the Merkle-Damgård construction are generally susceptible to length extension attacks and SHA512 is not an exception.

The reason is the structure of a Merkle-Damgård hash function, which operates by iterating a compression function $$f : \{0,1\}^\ell \times \{0,1\}^\ell \to \{0,1\}^\ell.$$ Essentially it takes a message $m$ that must be a multiple of the block size $\ell$ ($\ell=512$ bits for SHA512), splits it into blocks $m_1,\dots m_L$ (for a total message length of $|m|=L\cdot\ell$), sets $$h_0 := IV$$ and for $1\leq i\leq L$ computes $$h_i := f(h_{i-1},m_i).$$ Finally it outputs $h_L$.

From this description you can easily infer, that given $h=h_L$, I can easily choose a new block $m'$ and compute $h_{i+1} = f(h,m')=H(m\|m')$ giving you a length extension attack.

However, as most things it's not quite that simple. I said above, that $| m|$ needs to be a multiple of the block size. This is in general not the case, so some padding needs to take place to bring the message length up to the next multiple of the block length. For SHA512 the padding works like this:

Let $m$ be a message of length $|m|=b$ bits. Then we append a single bit $1$ and $k$ $0$ bits, where $k$ is the smallest number, such that $b+1+k+64$ is a multiple of $512$. Finally $b$ encoded as a $64$ bit integer is appended. And this message is then fed into the construction outlined above.

What does this mean for a length extension attack? Mainly two things: First, in addition to $h_i$, we also need to know the length $|m|$ of the original message to compute the new padding. Second, we will not be able to freely choose $m'$.

If we run the length extension attack we will end up with a hash for the message $$m\|1\underbrace{0\dots0}_k\|b\|m',$$ which depending on context may or may not be sufficient for whatever an attacker is trying to do.

Your Answer

Brandon Overall is a new contributor. Be nice, and check out our Code of Conduct.

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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