1
$\begingroup$

I was wondering out of the functions (MD5, SHA-1, SHA-256, and SHA-512), do all provide 128-bit pre-image resistance and 128-bit second-image resistance?

Also, out of these hash functions, do only SHA-256 and SHA-512 provide 128-bit collision resistance? (Due to $l/2$ bits of security)

$\endgroup$

1 Answer 1

4
$\begingroup$

Let first a table on the bit security.

Hash Rel. Year Pre-images Second Pre-images Collision Resistance Status
MD5 1992 128-bit 128-bit immediately broken compromised
SHA-1 1995 160-bit 160-bit broken compromised
SHA-256 2001 256-bit 256-bit 128-bit secure
SHA-512 2001 512-bit 512-bit 256-bit secure

While there is an attack on the pre-image of MD5 slightly less than the 128-bit that is given as $~2^{123.4}$, the actual cost is larger than the generic pre-image attack, so the pre-image is still non-broken. The collision resistance, on the other hand, is ultra fast, less than 5 minutes.

Remember that the multi-target attack on the pre-images makes any 128-bit output insecure.

SHA-1's collision resistance has been shuttered in practice and should not be used in practice anymore. Use at least 256-bit output hash functions like SHA-256, SHA3-256, Blake2b, or Shake series. This will help you secure from both classical and quantum attacks.

  • 23 February 2017, the Google team shuttered SHA-1 with $2^{63.1}$ SHA-1 evaluations and managed to produce two PDFs has the same SHA-1 hashes. This is an identical-prefix collision attack.

  • 24 April 2019, chosen-prefix collisions in approximately $~2^{68}$ SHA-1 evaluations by Leurent and Peyrin

The attack on SHA2-x is currently only possible on reduced rounds in which the researchers exhibit the power of their attack by reducing the rounds of the compression function.

For example; Bicliques for Preimages: Attacks on Skein-512 and the SHA-2 family works on 45 out of 64 with the complexity $2^{255.5}$ for pre-image attack on SHA-256. This means that if SHA-256 was designed as 45 rounds instead of 64, its pre-image resistance was broken with this attack. Fortunately, the standard doesn't reduce the rounds of SHAx series we always use them as full rounds.

$\endgroup$
3
  • 1
    $\begingroup$ @CryptoGuru: "The attack on SHA2-x is currently on possible in reduced rounds." means 'attacks on deliberately weakened variants of SHA2-x that we don't actually use in practice'. kelalaka knows this; however being more explicit in explaining what this means might not be a bad idea... $\endgroup$
    – poncho
    Oct 26, 2022 at 15:44
  • 1
    $\begingroup$ What's the source for 150-bit SHA-1 Second Pre-images? $\endgroup$
    – fgrieu
    Oct 26, 2022 at 16:50
  • 1
    $\begingroup$ @fgrieu nothing than my pure typo :) $\endgroup$
    – kelalaka
    Oct 26, 2022 at 16:51

Your Answer

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

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