Can a file contain its md5sum inside it?

Question

Just wondering if it is possible to create a file which has its md5sum inside it along with other contents too.

Answer 1

Theoretically? Yes.

Practically, however, since /any/ change to a file's contents, no matter how minute, causes a drastic change in the checksum (which is how md5 checksums work, after all), you'd need to be able to predict how the checksum will change when you alter the file to include the checksum -- for all intents and purposes this isn't much different from being able to break the md5 hashing algorithm.

There's no such thing as "impossible" in cryptography, but the science does acknowledge the concept of "practically undoable" or "statistically improbable" and that's pretty much what you're dealing with here, at the moment.

Answer 2

In the general case, no, since adding the MD5 sum would modify the file itself and thus its MD5 sum, most of the time...

However, for specifically crafted files, it could be possible, using a collision attack.

There is an example of collision attacks where two PostScript files are designed to have the same MD5 sum here (there are paper references too): http://th.informatik.uni-mannheim.de/people/lucks/HashCollisions/

You might be able to use the same approach to generate a second file that would contain the original content, its MD5 sum, and some extra content to make the collision.

Answer 3

You could have something like a wrapper format that have the MD5 in part of the file and the real content in another part of it.

This would useless because if the attacker can change the content then he can also change the MD5 to match the new content.

Answer 4

(Copying my original comment as answer:)

You'd be better off creating a section of the file for the md5 / hash, and a seperate section for content.

On the other hand, since anyone can recreate the hash part, what security value would you get from this?
You could get tamper-protection from a digital signature (or maybe via HMAC), but a plain hash won't help you there.
Or are you trying to do something else?

Answer 5

Consider this: you create a file that contains every member of the set of 16-byte sequences. An MD5 checksum is a 16-byte sequence, so by definition this file contains its own MD5 checksum. Somewhere.

Answer 6

You could do it through use of an Alternate Data Stream, though the information may not transfer properly between certain file systems or OS's. Certain applications may handle (or not handle) these differently also.

In short, Alternate Data Streams are a form of metadata attached to files in some file systems (NTFS is one) which does not appear readily when viewing a directory's contents. Even with the system set to show "hidden files" and those ever-critical "protected operating system files" you still will not see an ADS "file" in most file managers.

Additionally, the "host" file itself will not appear changed at all. The file's size will remain the same, and even the MD5 hash (or any other, for that matter) will be the same. You could even conceivably store an ADS "file" that is larger than its host file - although of course you cannot store one so large that it goes beyond the physical capacity of your drive.

In Windows systems with NTFS, ADS files are most easily accessed via the command line. So, for File1.ext, if you want to store the MD5 hash in an ADS, do the following:

• Calcuate the MD5 of File1.ext with your tool of choice.
• Open a CMD window, and navigate to the folder containing File1.ext
• Run notepad on the file, but add an ADS to the end with a colon separator (no spaces on either side of the colon) like so:
  • notepad File1.ext:MD5.txt
  • (Make sure to do this from the command prompt, and while working in the same folder as the file - or otherwise provide the full file path.)
• Notepad will alert that File1.ext:MD5.txt does not exist. Tell Notepad that yes, you do want to create a new file.
• Paste your MD5 hash into MD5.txt, close and save the file.
• Re-run your MD5 hash against File1.ext to verify it hasn't changed.
• Re-run Notepad as above, to verify presence of the ADS.

Again, ADS's are handled differently by different OS's and file systems. So, they're not likely to traverse the Internet (or even some LANs or sneakernets) very well. But, it is a way of doing what it is you seem to be wanting to do.

For further details, instructions, or utilities, consult Google.

Answer 7

Cryptographically speaking the attack you are describing is actually harder than finding a first preimage, maybe even harder than finding a second preimage.

This is not possible given today's computing power and today's crypto attacks .

Current attacks on MD5 don't even come close to finding preimages - we are talking about something completely different than the various collisions attacks that have been demonstrated (and are the reason MD5 is considered somewhat insecure). The attack that would be required to create a file with it's MD5 in it has nothing to do with collisions.

I would say that such attack, because as I mentioned is even harder than a preimage attack, is very unlikely in our lifetimes.

Answer 8

Let's assume that MD5 is a "perfect" hash function which can be modeled as a random oracle. A random oracle is a function for which you know nothing of the output for a given input before trying it once. For a random oracle, the best method to achieve what you are looking for is hope: you try random input messages until you find one which contains its own hash. The question is then: what size of input messages should you use ?

MD5 processes data by adding some bits of padding (at least 65, at most 576) so that the length is a multiple of 512; then data is split into 512-bit blocks. The cost of hashing a message is directly proportional to the number of such blocks. I.e. for a n-bit message, the cost is ceil((n+65)/512). A n-bit message, on the other hand, offers n-127 subsequences of 128 bits. Longer messages make it more probable to succeed at each message (in a linear way) but cost more to process (linearly too). So message length is mostly neutral, except that the overhead implied by the padding is larger when using short messages. Overall, with large enough random messages (e.g. 8 kB), you will find a message which contains its own MD5 in average cost about 2¹¹⁹ MD5 elementary evaluation. An elementary evaluation of MD5 uses a few hundred clock cycles on a recent CPU, and 2¹¹⁹ is totally unachievable with today's technology (and tomorrow's technology, too).

(The "big file with all 128-bit sequence" that Graham Lee is talking about is just a special case of this generic method, with a single very large message.)

Now MD5 is widely known to not be a random oracle -- if only because collisions on MD5 can be computed efficiently, something which is not possible with a random oracle. So it is conceivable that shortcuts exploiting weaknesses in MD5 structure exist. However, I am not aware of any attack leading to a message containing its own MD5; this looks like a problem close to preimage resistance, something which is viewed as substantially more difficult than collisions.

Answer 9

What you are asking about is the existence of a fixpoint of the composition of two functions: the md5 function, and a function (let's call it f, and let's call the set of all such functions F) which takes a md5 and outputs your file. That is, X = f(md5(X)).

As the Wikipedia article says, not all functions have a fixpoint.

For some trivial functions in F, the answer is yes. For instance, a function which always discards the input and always outputs a zero-byte file will obviously cause its composition with md5 to have a fixpoint. Obviously, these cases are not what you want — you cannot say with a straight face that it "contains its md5sum inside it". So, let's refine our definition.

Let's for now restrict our set F to all functions which output the concatenation of a prefix, the input, and a postfix. That is, f(X) = pre∥X∥post. With this, the whole md5sum has to appear somewhere within the file, intact, in binary, and exactly once. This is much more restrictive than your definition (which would allow the md5sum as text, broken into parts, repeated, or even spoken as a .wav file!), but it avoids the degenerate functions which do not include the md5sum or include only part of it.

It is also easy to see that, if f(md5(X)) has a fixpoint, md5(f(X)) also has a fixpoint, and vice versa.

Now take a look at this stackoverflow question: Is there an MD5 Fixed Point where md5(x) == x?. In particular, take a look at Adam Rosenfield's answer. In it, we can see that there is a 63.21% probability of md5(X) having a fixed point (of course, the fixpoint either does or does not exist; this is a Bayesian probability, which measures our belief that it exists).

The same argument used in that answer can be applied to md5(f(X)), and thus to f(md5(X)). So there is 63.21% probability that, for a given prefix and postfix (that is, for a given function f), a file containing its own md5sum inside it exists, and 36.79% of probability that no such file exists. Again, this is Bayesian probability.

It is easy to see, as mentioned on that answer, that the same argument will also apply to any file which depends on enough of its md5 output. For files which depend on only a couple of bits of the md5 output, or do not depend on it at all (including the one on @Graham Lee's answer, which depends on 0 bits of the md5 output), the answer will be different.