2
$\begingroup$

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!

$\endgroup$
5
$\begingroup$

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'}$$ that maps an $\ell'$ bit intermediate hash-value and an $\ell$ bit message block to a new $\ell'$ bit intermediate hash-value. (For SHA-512, $\ell=1024$ and $\ell'=512$). Essentially it takes a message $m$ that must be a multiple of the block size $\ell$, splits it into blocks $m_1,\dots m_L$ (for a total message length of $|m|=L\cdot\ell$), sets $$h_0 := IV \in \{0,1\}^{\ell'}$$ 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$ you can 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 SHA-512 the padding works like this:

Let $m$ be a message of length $|m|=b$ bits. Then we append a single $1$ bit and $k$ $0$ bits, where $k$ is the smallest number, such that $b+1+k+128$ is a multiple of $1024$. Finally $b$ encoded as a $128$ bit integer is appended. This padded 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.

$\endgroup$

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.