3
$\begingroup$

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]

$\endgroup$

migrated from security.stackexchange.com Oct 24 '15 at 20:58

This question came from our site for information security professionals.

  • 2
    $\begingroup$ I agree with @NeilSmithline. My response, and probably the response of others is going to be "just avoid using MD5 and any constructions using MD5." But crypto.SE can better respond to the math part. $\endgroup$ – HexTitan Oct 24 '15 at 17:06
  • $\begingroup$ For collision resistance, this question reduces to Are there MD5 collisions for inputs of different length? $\endgroup$ – CodesInChaos Oct 24 '15 at 21:57
  • $\begingroup$ @CodesInChaos, how so? Does not seem like different-length collisions would be required (or immediately helpful) for breaking this. $\endgroup$ – otus Oct 25 '15 at 10:59
7
$\begingroup$

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 2123.4 instead of the full expected complexity of 2128 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).

$\endgroup$
  • $\begingroup$ The password hashing part is a bit off topic. If we ask "is <hash function> secure", it usually means whether it is preimage and collision resistant. $\endgroup$ – otus Oct 25 '15 at 13:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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