Is md5(x)&md5(y&x) secure?

Question

I was wondering if the following hash function

f(x) := md5(x) & md5('abc'&x)

(with & as concatenation operator) is secure.

This schema can be even extended like this:

g(x) := md5(x) & md5('abc'&x) & md5('def'&x)

To find a collission in f(x), following requirements would be met:

f(x)=f(x'), x!=x' <==> md5(x)=md5(x') ^ md5('abc'&x)=md5('abc'&x')

or

g(x)=g(x'), x!=x' <==> md5(x)=md5(x') ^ md5('abc'&x)=md5('abc'&x') ^ md5('def'&x)=md5('def'&x')

Is this realistic that such a condition can be found? I can't imagine that.

[I would be happy to learn more about the math behind it]

Answer 1

Secure against what and for what purpose?

MD5 remains too fast for most human typed passwords. You should use something like bcrypt or PBKDF or sha256crypt where there are a tunable amount of thousands to millions (or more) rounds of hashing to generate each hash. You really don't want to allow users to try several billion hashes per second per GPU.

f(x) := md5(x) ++ md5('abc' ++ x) will be just as vulnerable to preimage attacks as md5 -- that is given some hash f(x) = 5d41402abc4b2a76b9719d911017c592d76051e1dae76d1f309598102df58d84 find x. You simply truncate look at the first 128-bits of the 256-bit hash and it reduces to the problem of md5(x)=5d41402abc4b2a76b9719d911017c592, which you can type into several online md5 reverse lookups (the second half reversed too without me adding it). So you can see this method will not be secure for user chosen passwords (at least for typical users).

Luckily, last I checked (and according to wikipedia), there are no practical publicly known preimage attacks on MD5 for high-entropy strings. There is a MD5 preimage attack that takes 2^123.4 instead of the full expected complexity of 2¹²⁸ for a 128-bit hash, but it will not be practical (about 24 times faster than brute force).

Now md5 is not collision resistant. It is possible to construct pairs of text such that m1 != m2, while md5(m1) == md5(m2). Granted if you found a collision in md5, this collision would not work immediately for f(x) as in general md5('abc' ++ m1) != md5('abc' ++ m2) when md5(m1) == md5(m2). However, the underlying flaws of md5 is that is built on the Merkle-Damgård construction will still be present and probably could still be exploited (things like how md5(m1++x) == md5(m2++x) will always be true if md5(m1) == md5(m2)) and could probably still be exploited (even if its not immediately obvious and would be more complicated than simply combining existing attacks).