Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

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

share|improve this question

migrated from unix.stackexchange.com May 16 '11 at 7:05

This question came from our site for users of Linux, FreeBSD and other Un*x-like operating systems..

    
My reasoning here is that it would be logically possible to do this but it wouldn't be all that easy to figure out. Would it not just be a very long game of trial and error? I'm interested to know if it is indeed possible. –  boehj May 16 '11 at 5:55
2  
You'd be better off creating a section of the file for the md5, and a 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? –  AviD May 16 '11 at 10:21
1  
@AviD is right, HMAC is exactly intended for situations like this. –  Marcin May 16 '11 at 11:31
1  
I've just tried to change the tag from "encryption" to "hashing". MD5 is about hashing, or perhaps signing if it's protected (as @AviD was saying). It's not really about encryption, especially when it's about files (which presumably you'd want to be able to decipher at some point). The main form of "encryption" with MD5 is the one-way storage of passwords. –  Bruno May 16 '11 at 12:19
3  
Possibly related question: cstheory.stackexchange.com/questions/4609/…. –  Sadeq Dousti May 21 '11 at 6:17
show 3 more comments

10 Answers

up vote 21 down vote accepted

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.

share|improve this answer
    
I'd like to read up on the theoretical proof. Do you have one? –  Nam Nguyen May 16 '11 at 10:40
3  
I meant theoretically as in "It's theoretically possible to create a file containing among other things, a 33-byte string that just happens to be the exact same value as the MD5 checksum of the file". Your odds at doing it by accident are slightly worse than those of winning the lottery with last week's ticket. –  Shadur May 16 '11 at 11:11
    
Thanks for the clarification. –  Nam Nguyen May 16 '11 at 12:41
    
The odds are probably way worse than winning last week's lottery ticket. You should probably be thinking more along the lines of a TSP style/NP hard problem across 128 bits of the parent and child file you're trying to generate (assuming you ignore weakness in md5). –  Jon Bringhurst May 18 '11 at 3:53
add comment

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.

share|improve this answer
2  
Nice one. Not really an answer, but funny. –  Iszi May 16 '11 at 14:53
3  
@Iszi: I disagree. It's an answer, in that it's solution to the proposed problem. It may not be useful, but that was never in the spec :-) –  user185 May 16 '11 at 15:25
2  
That's a large file. :) –  Jakob Borg May 17 '11 at 14:00
    
@Jakob yes :). But it's probably (just about) small enough to fit in a file on a ZFS filesystem, although you'd need a hard disk with a surface area around the size of land area on the planet. –  user185 May 17 '11 at 14:30
3  
@Graham: According to my calculations, assuming you could fit data onto a platter with a density of 10 TB per square inch (around the highest prototypical density around today), and assuming there was an ideal method to save MD5 sums onto a disk (without compression), such a disk would be approximately 47 million square kilometers in surface area, approximately 1/3 of the land area of the Earth. (assuming there was a flat land mass large enough) –  Hello71 Jul 26 '11 at 2:32
show 3 more comments

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.

share|improve this answer
1  
I like everything but your last sentence. I'm no expert, but from what I remember from the experts, the science of hashing is significantly behind even the science of e.g. encryption, and is not sufficiently advanced to say a lot with confidence. And remember, the singularity is near.... –  nealmcb May 18 '11 at 0:10
    
You are right, it's a pretty bold statement and I should avoid those. I'm no expert either, although I have studied cryptography. If we talk specifically about MD5, a point that can be made is that a preimage attack (reversing the hash) is so hard, that probably will take so long that by that time, noone will be still using MD5, even in our lifetimes. Also, I think quantum computing is nearer than singularity... ;) –  john May 18 '11 at 0:42
add comment

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 2119 MD5 elementary evaluation. An elementary evaluation of MD5 uses a few hundred clock cycles on a recent CPU, and 2119 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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

(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?

share|improve this answer
add comment

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.

share|improve this answer
1  
this doesn't look right to me. I think you're confusing collision attacks with preimage attacks. There are collision attacks on MD5, but no known preimage attacks on MD5. To find a file that contains its own hash, you probably need some kind of preimage attack (I don't see any way that a collision-finding attack would do it). –  D.W. May 17 '11 at 9:44
    
@D.W. You're right, my wording was probably a bit strong. I was merely suggesting that a similar approach might work, since the problems are similar to a degree, but I must admit I haven't looked into it more than that. –  Bruno May 17 '11 at 14:00
add comment

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.

share|improve this answer
    
That's why you subsequently encrypt the MD5 checksum hash with your private key -- since only you can have been the one to encrypt that checksum, if the checksum matches the message, it's reasonably safe to assume that you're the one who signed the message (and thus, who wrote it) –  Shadur May 17 '11 at 12:16
    
@Shadur, just a detail, but you sign (not encrypt) with the private key. –  Bruno May 17 '11 at 15:38
    
@bruno To be precise, said "signing" is in fact a hash digest - MD5 or otherwise - of your message encrypted with the private key. –  Shadur May 17 '11 at 16:55
    
@Shadur, signing a message indeed refers to signing its digest, but you don't encrypt it (i.e. make it unreadable). "Scrambling" doesn't mean encrypting. It simply doesn't make sense to use the verb encrypt with a private key (which is for deciphering/decrypting and signing). There's no secret in the signature and its digest. –  Bruno May 17 '11 at 17:18
add comment

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.

share|improve this answer
    
Er, minor point in your reasoning, perhaps, but there is no function f where f(md5(X)) yields X. MD5 is strictly one-way. –  Shadur Aug 4 '11 at 7:28
    
@Shadur: Yes, there is no function f such that, for each and every value X, f(md5(X)) yields X. However, there are many functions f such that, for at least one value X, f(md5(X)) yields X (the fixedpoint) -- CesarB already gives one example. –  David Cary Jun 22 '12 at 13:30
    
@CesarB: Could you edit your answer to emphasize that it is almost certainly possible to "create a file that contains its md5sum inside it" -- for any one postfix, we have a 63% probability that one "merely" iterates through all possible postfixes (of where there are an infinite number) –  David Cary Jun 22 '12 at 13:37
    
@CesarB: Could you edit your answer to emphasize that it is almost certainly theoretically possible to "create a file that contains its md5sum inside it", even though it is practically impossible with today's technology? For any one given postfix, we have a 63% probability that such file is possible; for any 7 different given postfixes, we have a 99.9% probability that such a file is possible for at least one of those postfixes. Since there are an infinite number of possible postfixes, it's almost certain that millions of different postfixes have at least one md5 fixed point. –  David Cary Jun 22 '12 at 14:04
add comment

From my understanding of hashing this is totally impossible. In order to calculate the hash the entirety of the data is ingested. This is then used to generate the hash, this data would then have to be appended to the file thus changing the data and also the hash.

[http://www.forensicswiki.org/wiki/Hashing this might be of some use to you]

share|improve this answer
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.