3
$\begingroup$

I have seen this question on MD5 replacement for 128 bit digests. It is said numerous times that having a 128 bit digest is impossible today because finding a collision would only require $2^{64}$ operations, which is in the means of big organisations nowadays. However, I think that these answers miss a fairly important point.

The time to bruteforce a hash function does not only depend on the number of security bits of its digest, but it also depends on the time needed to compute a single hash. This is why slow hashing functions such as bcrypt (184 bit) can afford to have a shorter digest size compared to fast hashing ones such as SHA-256 (256 bit).

In this case, would it not be possible to have a collision-resistant 128-bit slow-hashing function to replace MD5?

Thank you for your help.

$\endgroup$
2
  • $\begingroup$ First of all, don't use any hashes that aren't collision resistant in creating the slow hash; if you want to have fewer bits, you crop the hash after all computations are done. Strengthening doesn't add too many bits to the security - it's just linear after all, and the problem with creating a generic hash function is that once a collision is found it can be reused. $\endgroup$ Apr 20, 2021 at 10:20
  • $\begingroup$ Thank you for your answer. What do you call strengthening? Besides, let's consider a 128 bit fast random oracle $o$ (not MD5 as it has weaknesses, maybe the first 128 bits of SHA-256). Could this slow hashing function with $n$ rounds be considered secure: h=msg; for i in 1..n: h=o(h || i); endfor; return h;? Is it still possible to reuse collisions in this case? And as I said in the comment of kelalaka's answer, I don't think reiterating the same fast hash function multiple times is the only way of creating a slow hash function. $\endgroup$ Apr 20, 2021 at 11:47

2 Answers 2

3
$\begingroup$

Would it not be possible to have a collision-resistant 128-bit slow-hashing function to replace MD5?

That's possible.

We could use Argon2 parameterized for 128-bit output and (say) 10 ms computation on a Raspberry Pi 3. If something could speed this up a hundredfold, and we parallelize on 1 million units, there's <40% chance of finding a collision with $2^{128/2}/10^{10}/86400/365.25\approx58$ years of computation.

That would replace MD5 in some applications where it's 128-bit size matters, collision-resistance is essential, but not speed for small inputs nor 512-bit block size (e.g. HMAC-MD5, but this one is not broken as far as we know).

Not coincidentally, that's current best practice for password hashing.

Note: I have simplified this answer after discovering Argon2 version 0x13 already includes a fast hash as the first step, namely Blake2b.

$\endgroup$
1
  • $\begingroup$ Yes, using slow hashes designed for passwords will be the solution for the OP. $\endgroup$
    – kelalaka
    Apr 20, 2021 at 17:54
2
$\begingroup$

Bcrypt is a password hashing function likes PBKDf2, Scrypt, and, Argon, where in the password hashing the collision is not important, pre-images are important.

If you just iterate the $\operatorname{MD5^n}(x)=\operatorname{MD5}(\operatorname{MD5}(...(\operatorname{MD5}(x)...))$ n-times then we will have an already well-known problem. A collision in the inner MD5 is a collision for the $\operatorname{MD5^n}$ therefore simple iteration is not secure only slows the collision finding, really? Just find a collision for $\operatorname{MD5(x)}$ then you have a collision. In other words, the cost of finding collusion is not affected!

An easy fix is for the case $n=2$ is $\operatorname{MD5^2}(x)=\operatorname{MD5}(\operatorname{MD5}(x)||x))$ or similar approaches.

We don't need doubling MD5 or SHA-1 to improve security, we just need new hash functions like SHA3 and the very fast one Blake2b.

Finally, we want cryptographic hash functions to be secure and fast, not slow. Slowness is required in password hashing.


update for the comment

It turns out that hashing with MD5 is required for the identification. In this case, the pre-image attack is more important if the public keys are considered to be kept secret. In the pre-image attack, given a hash value $h$ we are looking for an $x'$ such that $h = \operatorname{MD5}(x')$. The $x'$ may be the original $x$ such that $h = \operatorname{MD5}(x)$ or not. If the attackers seek the original they need to search more. MD5 has only one pre-image attack that its practical cost is not faster than the generic pre-images search that has $2^{128}$-time.

The collision here is only relevant for you since you don't have two or more users who have the same identity.

So you can use a modern hash function with trimmed instead of MD5.

$\endgroup$
7
  • $\begingroup$ Thank you for your answer. Yes, finding a collision for one of the inner $\operatorname{MD5}$ would result in a collision for $\operatorname{MD5^n}$, but iterating a fast hashing function is not the only way to construct a slow hashing function, you gave an example yourself. SHA3 and Blake2b have a digest size at least equal to 256 bit, I was wondering if we could construct a secure 128 bit hash function by today's standards, I don't really care about the speed. $\endgroup$ Apr 20, 2021 at 10:14
  • $\begingroup$ In theory, you can have one, however, still, the cost of finding collision with generic birthday attack is $2^{64}$ with %50 probability. Why do you need 128-bit output? $\endgroup$
    – kelalaka
    Apr 20, 2021 at 10:44
  • $\begingroup$ I would like a 128 bit output because user public keys of my system will be hashed to get their identifier, and I want the shortest identifiers possible. Ideally, I would like identifiers to be remembered by humans. Of course, it would not be the raw bit string that would be remembered, but maybe a hex or b64 encoding of it, or a hash visualization. Yes, a birthday attack would only need $2^{64}$ operations on average, but as it will be slow hashing, it would still be computationally infeasible for large entities to break the hash. $\endgroup$ Apr 20, 2021 at 10:46
  • $\begingroup$ Aren't public-keys are public? Anyway, what you seek is not collision, it is pre-image so that one can extract $x$ from $MD5(x)$. The pre-image attack in MD5 in practice not faster than the generic attack that have cost $2^{128}$. $\endgroup$
    – kelalaka
    Apr 20, 2021 at 10:53
  • 1
    $\begingroup$ Nope! collision is finding arbitrary $x$ and $y$ such that $H(x)=H(y)$. What you describe is a multi-preimage attack. In this case, the parallelized rainbow table is the key to find one. To mitigate just use a random salt per password. $\endgroup$
    – kelalaka
    Apr 20, 2021 at 11:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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