How much computing time on a typical desktop computer would it take to find a new length and new data to extend a text file of about 10K Bytes with a given MD5 hash?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
First of all, let us explore what a "length extension attack" is; it might not be exactly what you assumed it was.
Suppose we were given the MD5 hash of a bytestring we'll call $A$; we may have no idea what the string $A$ consists of, but we do know its length.
Then, we can create a bytestring $B$ (which depends on the length of $A$, but not any of its contents; it'll be between 9 and 73 bytes long), so that, for any string $C$ we pick, we can compute the value:
$MD5(A || B || C)$
This value will generally not be the same as the original $MD5(A)$ value; so if you're looking to create second preimages, this doesn't help you. However, you're looking for (say) a way to attack the use of MD5 as a Message Authentication Code, this might.
As for the time taken to compute the value $B$, and the value $MD5(A || B || C)$, well, that's essentially trivial; $B$ can be computed directly from the length, and the time taken to compute the hash is essentially the time it takes to compute $MD5(C)$.
A number of other hash functions share this observation; SHA-1, SHA-256, SHA-512. There are also other hash functions for which this is not true: SHA-384 and AHS among them.