Score:1

Which hash functions provide 128 bit resistance?

bm flag

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)

Score:4
in flag

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.

poncho avatar
my flag
@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...
fgrieu avatar
ng flag
What's the source for 150-bit SHA-1 Second Pre-images?
kelalaka avatar
in flag
@fgrieu nothing than my pure typo :)
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.