We can consider Merkle-Damgard(MD) based hash functions like MD4, MD5, SHA-1, SHA-256, SHA-512, and derivatives as a rotated block cipher, where the key is the message and the input is the previous state.
A bit more formally, for SHA-1, there is a block cipher, named SHACAL, that takes a 512-bit key and 160-bit block as the input. Then the MD construction uses this block cipher in an iterated mode where the initial values are fixed.
We can also consider this internal block cipher a compression function;
$$c:\{1,0\}^{160}\times\{1,0\}^{512} \to\{1,0\}^{160}$$ As you can see the naming is quite clear, the input space is larger than the output space. Therefore one cannot figure out the actual input message (here the key) without some external knowledge since some of the information is lost.
Also from the hash functions, we also require that
- Bit dependency: each bit of the output is dependent on every bit of input.
- Avalanching: a single bit change in the input must change ≈ half of the bits randomly.
- Non-linearity: prevent from attacking linear systems solving techniques.
- What makes it hard to "back-calculate"?
Consider the last iteration of the internal block cipher for the hash calculation, then given a hash value, and even if the other 160-bit input, you have to find the 512-bit. In other words, you need to break the block cipher. Obviously, you cannot go for the search 512-bit. Even you find some weakness, your problem will be the compression. The compression is not simply a trimming, it requires arithmetic decisions that must be considered carefully. So in short, the non-linearity and compression.
This is also known as the pre-image attack
- given a hash value $h$ find a message $m$ such that $h=\operatorname{Hash}(m)$
and requires $\mathcal{O}(2^n)$ for n-bit output hash functions.
- What about those steps make it collision resistant?
In collision resistance, it should be hard to find two distinct message $m$ and $m'$ such that $\operatorname{Hash}(m) = \operatorname{Hash}(m)$ for computationally bounded adversaries.
Hash collisions are inevitable due to the pigeonhole principle. With Birthday Paradox, we will find a collision with 50% after $\sqrt{n}$ tries. Classical collision attack has $\mathcal{O}(2^{n/2})$ complexity.
Therefore, one of the necessary conditions is the output size, bit dependency, avalanching, and non-linearity are some of the other necessary conditions. We can say there is no sufficient condition since there is no limit on the attack types.
And, it turns out that SHA-1 has identical-prefix collision attack
- Why is the process...what it is? Why not some other "random mathematical operations"?
Cryptographic constructions do not rely on random processes or selection. We need to evaluate the provided security. We need to analyze the construction according to security requirements. And, the reverse has already shown by examples.
For example; after years of debate on NSA's modification on DES S-Boxes, with carefully crafted researches by Coppersmith we know that we cannot make the DES more secure by choosing the S-boxes, actually, it will become less secure or broken.
“One-Wayness” of SHA 1
A small note for this one;
We know that if there is a one-way function then $\mathcal{P}\neq \mathcal{NP}$. So, the researchers either fail to show one yet or it doesn't exist at all.
