5
$\begingroup$

I recently started learning about Hash Functions for my first time, and I've gone through and have tried to understand the SHA1 process.

Brilliant does an excellent job of explaining it step by step.

https://brilliant.org/wiki/secure-hashing-algorithms/

As far as I've understood, hash functions are meant to be collision-resistant and really hard to back-calculate, even if one knows the exact process.

Although I can see the process, to me who doesn't know much about cryptography yet, the process seems extremely random - as if a drunk person was asked to perform mathematical operations on a bunch of bits.

I can't really see the motivation for the precise steps taken in SHA 1...

  • What about those steps make it collision resistant?
  • What makes it hard to "back-calculate"?
  • Why is the process...what it is? Why not some other "random mathematical operations"?
$\endgroup$
1
  • 1
    $\begingroup$ There's plenty of answers here on Crypto.SE and elsewhere. The keyword you might want to search for are: "Merkle-Damgaard construct" and "cryptographic compression function". These 2 keywords apply to older hash functions designed by RSA Inc and NSA. The keywords for other modern hash functions include "HAIFA construct", "Sponge function", etc. After learning about these, you might want to answer your own question to get some good reputation points. $\endgroup$
    – DannyNiu
    Dec 19, 2019 at 4:29

2 Answers 2

6
$\begingroup$

SHA-1, like the earlier MD5 and SHA(-0), and the later SHA-2, is built per a carefully devised hierarchical design:

  • Merkle-Damgård at the outer, building a collision+preimage-resistant hash with a security argument based on a fixed-width compression function.
  • Davies-Meyer to build that compression function, with a security argument based on a block cipher with strong related-keys security (message blocks are the key).
  • Iteration of unbalanced Feistel rounds to build that block cipher.
  • Sort of an Add/Rotate/Xor (ARX) strategy with Shift/AND selectively added to implement the necessary non-linear round functions of the block cipher and of its key schedule.

The only distinctly haphazard aspect is the multiple non-linear functions changing after 20 rounds. That's an idea inherited from MD5, and it did not much help SHA(-0) or SHA-1. It was dropped in SHA-2, in favor of a uniform round function combining several non-linear functions. That was a reasonable move.

$\endgroup$
7
  • $\begingroup$ Very elegant summary, straight to the point! $\endgroup$
    – Kris
    Dec 19, 2019 at 21:50
  • 3
    $\begingroup$ Saying it was carefully devised kind of oversells SHA-1. Saying it is multi-layered implies that the design strategy was defense-in-depth. That's not at all the case. It's layered in the sense that it uses functional composition. $\endgroup$ Dec 20, 2019 at 0:30
  • $\begingroup$ Also, we have the benefit of hindsight to criticize even the individual components. We would design an algorithm differently with the knowledge we have now. The pure form of Merkle-Damgård has multiple issues. We would use a modified form if we didn't use some other construction. $\endgroup$ Dec 20, 2019 at 0:40
  • $\begingroup$ We would not use the same block cipher design. It's not ARX. If it were then 80 rounds ARX would have made the algorithm more robust, even if the choice of rotation distances weren't great. (I know some people have different opinions on what counts as ARX. For me, it means a function that makes almost exclusive use of those three operations and has a mix network that looks similar to what you see with ThreeFish. Pretty much every symmetric algorithm uses XOR and rotations. If you include anything with modular addition then ARX would be too broad a category.) $\endgroup$ Dec 20, 2019 at 0:49
  • 1
    $\begingroup$ It's compression function's block operation is much closer to an unbalanced Feistel cipher. It just happens to use addition instead of XOR to mix a 32 bit value dependent on the other 128 bits. That also wouldn't be used now in new algorithms. Only a fraction of the bits are updated each round, making rounds slower and requiring more rounds because just a few bits get updated each round. $\endgroup$ Dec 20, 2019 at 0:55
5
$\begingroup$

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.

$\endgroup$

Your Answer

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

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