17
$\begingroup$

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

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

$\endgroup$
  • $\begingroup$ Check these 1 2 3 $\endgroup$ – kelalaka Jan 9 at 22:33
  • 1
    $\begingroup$ Thanks for the good links. My question is different from "Why cant we reverse hashes", since I dont want to reverse a hash, merely curious about, if any, mathematical foundations for "security" of hash functions, as opposed to confusion and obfuscation. Seems the compression f in SHA256 is not provably secure, just hard. $\endgroup$ – rapadura Jan 9 at 22:51
  • 1
    $\begingroup$ It's worth noting that RSA and ECDSA are currently also not provably secure. We believe factoring and DLP are hard because no one we know of has found a way to do it efficiently. But we have no proof of their hardness, and perhaps we never will. $\endgroup$ – marcelm Jan 10 at 21:00
14
$\begingroup$

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(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;

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

$\endgroup$
  • 1
    $\begingroup$ @rapadura Did you try looking for SHA-256 on GitHub? For example, B-Con/crypto-algorithms. $\endgroup$ – forest Jan 10 at 8:46
  • 1
    $\begingroup$ I would have listed "Collision resistance" first, in that it is a weaker condition than "Second Pre-image resistant". (If we can break second pre-image resistance, then we can trivially break collision resistance by choosing a random $a$ as $m_1$, and then using the second pre-image algorithm to calculate $b$. OTOH if we have an algorithm to find collisions, that doesn't allow us to find second pre-images) $\endgroup$ – Martin Bonner Jan 10 at 10:09
  • 1
    $\begingroup$ "avalanche effect, i.e. every output bit depends on every input bit" Is that right? I could be misremembering, but I thought the ideal avalanche effect was when each input bit affected half of the output bits. $\endgroup$ – a CVn Jan 10 at 12:00
  • 2
    $\begingroup$ @aCVn When you flip a single bit in the input roughly 50% of the output bit should get flipped. Note however that if you flip bit at index 0 for different inputs the output bits that get flipped will change and you want all possible subsets to be possible. So in that sense all output bits depend on every single bit, while comparing two input whose difference is just one bit should give roughly 50% of difference. $\endgroup$ – Bakuriu Jan 10 at 19:35
  • 1
    $\begingroup$ Will accept this answer, despite both being really good answers. Learned a lot, thank you guys. $\endgroup$ – rapadura Jan 11 at 14:47
18
$\begingroup$

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.

$\endgroup$

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.