CODEWITHSUNDEEP
securityhashcryptographytime-complexity
atx
atx

Reputation: 5079

Time complexity of a brute-force embedded MD5sum

A question I've been meaning to have answered for a long time - What would be the time complexity of finding an MD5sum of a compiled binary that contains that same MD5 statically embedded in it, say, as a string?

Edit: If this wasn't already clear. I am looking for an answer with the time complexity and an explanation of it.

Upvotes: 5

Views: 995

Answers (6)

Jeremy Powell
Jeremy Powell

Reputation: 3486

This can be solved in constant time.

The file that contains all possible MD5 digests contains the digest of that file.

Upvotes: 1

rook
rook

Reputation: 67039

In order to accomplish this you must find a collision. This can be done using the prefixing attack against md5. Keep in mind this is only possible because md5 is very broken. This attack has a time complexity of 2^24.1, which is within reach of a modern desktop.

Upvotes: 0

flolo
flolo

Reputation: 15526

That also depends on the circumstands. If the binary is given, and just the md5 must be inserted at some place, the answer can be: 0. Because it may be possible (and I would assume it maybe in almost all cases like this) that there is no md5 which inserted yields the same md5.

In case you have the possibility to modify more of the binary (e.g. by having padding space which you can fill with arbitrary numbers), the only feasible approach is brute force.

Upvotes: 0

Thomas Mueller
Thomas Mueller

Reputation: 50127

What you want to do would require a flaw in the hash algorithm. And in fact, MD5 isn't very secure, so it might be possible. But I don't see how any of the known weaknesses could help in what you want to do. Even a preimage attack wouldn't help, it would need to be a 'chosen prefix preimage attack'.

So I guess the only feasible way (today) would be to use brute force.

If you are looking a way to 'add security' to a binary, truncate the hash, and then use brute force.

Upvotes: 0

orlp
orlp

Reputation: 117771

It is really hard since MD5 has a good distribution. Your best bet by bruteforcing is adding some hash to your file and appending meaningless data to the end of the binary until the binary has the same hash as the one embedded.

On the other hand if you want to check whether your binary is intact and unmodified you'd be better off by splitting your binary in 3 parts: The part of the binary before the hash, the hash itself and the part after the hash. Concatenate the first and the last part, compute the md5 hash and embed it into the binary.

Like this (example):

foo098f6bcd4621d373cade4e832627b4f6bar
foo | 098f6bcd4621d373cade4e832627b4f6 | bar
md5(foo+bar) = 3858f62230ac3c915f300c664312c63f
foo3858f62230ac3c915f300c664312c63fbar

Upvotes: 0

Piskvor left the building
Piskvor left the building

Reputation: 92792

Pretty much the same as brute force: computing a md5sum is trivial, but making a file to match a known md5sum is hard.

You are, in the best case, looking for a preimage that will give you a known hash (possibly by adding data into the binary).

Upvotes: 0

Related Questions