What makes SHA-256 secure?

Question

For example, RSA relies on a mathematically hard problem, factoring, while ECDSA or similar rely on discrete logarithm problem.

What makes SHA-256 and similar hash functions, of the same family, secure against pre-image and collision attacks? What's the math behind it?

Answer 1

It's worth pointing out that in the case of SHA2 and most other hashes the compression function has a block cipher (keyed permutation) as its core.

Basically what you are asking is identical to asking how can block ciphers be resistant to known-plaintext attacks and chosen-plaintext attacks (arguably doesn't apply to SHA2 specifically because an attacker doesn't control that aspect) and even related-key attacks in the case of SHA2 (because it uses a Davies-Meyer construction where the attacker has control over what gets fed into the key schedule).

There is no proof that this methodology is reducible to something that is proven secure. It is believed to be secure due to diffusion and confusion properties which as far as is known allow no efficient backtracking. You can think of it as extreme sensitivity-to-initial-conditions in a discrete non-continuous domain.

Edit: The reason I went to block ciphers is because hash security is provably reducible to the security of the core keyed permutation (or even unkeyed if you look at SHA3) - that's how hashes are designed to begin with. Which I believe is the spirit of your inquiry. But the buck stops there, no security proof for those exists.

Answer 2

The design and security of SHA-256 rely on two cryptographic structures; one-way compression function which is based on Davies–Meyer structure which uses SHACAL-2 block cipher and on the top the Merkle–Damgård structure that uses the Davies–Meyer structure.

A little deeper;

• Compression function: transforms $2n$-bit input into $n$-bit. The transformation performed in a way that it achieves avalanche effect, i.e. whenever one bit complemented from the input, each of the output bits changes with 50% probability.

• One-way function: Easy to compute hard to invert.

• One way compression function should have these properties;

  1. Easy to compute: the calculation of the output is easy for a given input.
  2. Pre-image resistant: given a hash value $h$ find a message $m$ such that $h=Hash(m)$. Consider storing the hashes of passwords on the server. Eg. an attacker will try to find a valid password to your account.
  3. Second Pre-image resistant: given a message $m_1$ is should be computationally infeasible to find another message $m_2$ such that $m_1 \neq m_2$ and $Hash(m_1)=Hash(m_2)$. Producing a forgery of a given message.
  4. Collision resistance : if it is hard to find two inputs that hash to the same output $a$ and $b$ such that $H(a)= H(b)$, $a \neq b.$

Collision resistance implies second pre-image resistance. If the attacker is able to find second pre-images then he chooses arbitrary $m_1$ then computes the second pre-image $m_2$ to obtain a collision. But Collision resistance doesn't imply pre-image resistance. See, more at Rogaway et. al paper.

(SHA256 Compression function, from Wikipedia )

Middle level;

• Davies–Meyer structure is a one-way compression function based on a block cipher. Security of this construction is in the Ideal Cipher Model. However, there is a property of this construction; even the underlying block cipher is secure it is possible to find fixed points.

• The block cipher of SHA-256 is called SHA-CAL-2. In Lu et. al presented a related-Key rectangle attack for 42 Rounds of SHACAL-2 by Lu et. al. Later, Lu et. al presented another attack Using Related-Key Rectangle Cryptanalysis] for 44-round of SHACAL-2.

Top layer;

• Merkle–Damgård structure (MD) uses a compression function. MD is collision resistant if the compression function is collision resistant one-way compression function.. MD constructions have length extension attack that SHA-256 is also prone to this attack. It is recommended to switch SHA-3.

Note: There is a pre-image resistance attack for 52 out of 64 rounds of SHA-256.