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?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Define "extend a file with a given hash". Is it a requirement that the original and extended file have the same hash? Or something else, like that two different extensions of the original file give the same hash, irrespective of the original's hash? Is it allowable that the (end of) the original is crafted by the attacker to make the task easier? $\endgroup$– fgrieu ♦Jun 11, 2013 at 10:50
-
1$\begingroup$ That isn't a length-extension. It's a second-pre-image and totally infeasible (cost above 2^120) $\endgroup$– CodesInChaosJun 11, 2013 at 14:31
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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 (now known as SHA-3) among them.
-
$\begingroup$ This string $B$ usually contains some zero bytes, which might make the resulting string $A||B||C$ a non-"text"-file, depending of your definition of text file. $\endgroup$ Jun 11, 2013 at 19:10
-
$\begingroup$ @PaŭloEbermann: actually, it'll always contain at least one zero byte unless A is at least 8 Petabytes long. So, yes, if you can't live with zero bytes in your byte strings, this observation isn't likely to be greatly useful to you. $\endgroup$– ponchoJun 11, 2013 at 19:34