What is the rationale for including addition in SHA-256?

Question

Short Version: SHA-256 uses addition alongside a variety of bit-wise operations. What's up with that?

I was reading a description of how SHA-256 worked and it included a description of the various internal operations that take place on the blocks of bits while the algorithm does its work.

Most of them made sense to me as the familiar "bit wise" operators I'm used to. ROTATE, AND, XOR, etc. But one stood out to me. One of these things is not like the other.

The algorithm also used ADD. There was an arithmetic operator in with the bit-wise operators. (The very last carry is discarded so the output has the same size as the inputs.)

This seemed very odd to me. All throughout the process, we were dealing with blocks of bits, each bit having equal significance. Suddenly, these blocks of bits became numbers. Bits have significance and if both bits are 1, then a carry takes place. Bits can influence their neighbours but only in one direction.

I had initially thought that all bits going in and coming out of SHA-256 were equally important and had equal ability to influence the result. Now I'm wondering if some bits have a greater ability to influence the output than others.

What's going on?

Answer 1

SHA-256 is an ARX-like algorithm. ARX stands for addition, rotate, and xor, which describes the operations used in the algorithm. (I say ARX-like because SHA-256 also uses right shifts, which are not ARX.)

ARX approaches are popular because typically the bitwise operations are linear in one field and the additions are linear in a different field, but they are each non-linear in the other. This allows using these operations, which typically are very fast (on many systems, a single cycle) to provide an algorithm which is resistant to both linear and differential cryptanalysis. Other algorithms using this approach include the stream cipher ChaCha and the permutation SPARKLE.

SHA-256 is believed to have the avalanche effect, where each input bit influences each output bit. While it's true that the carry is only in one direction, there are rotates, which means higher bits can then influence lower bits later on in the operation. SHA-256 uses constants to prevent fixed points at zero and these also provide 1 bits that affect the behaviour of the additions later on.

So while this is a natural question to ask, ARX-based approaches are reasonably well studied and can be used securely, such as in SHA-256.