Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
    
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? –  fgrieu Jun 11 '13 at 10:50
1  
That isn't a length-extension. It's a second-pre-image and totally infeasible (cost above 2^120) –  CodesInChaos Jun 11 '13 at 14:31
add comment

1 Answer 1

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.

share|improve this answer
    
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. –  Paŭlo Ebermann Jun 11 '13 at 19:10
    
@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. –  poncho Jun 11 '13 at 19:34
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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