2
$\begingroup$

I've been trying to learn why the different stages to the SHA-2 family of algorithms were added - SHA-256 in particular.

Here's the pseudocode for the message schedule:

s0 := (w[i-15] rightrotate  7) xor (w[i-15] rightrotate 18) xor (w[i-15] rightshift  3)
s1 := (w[i-2] rightrotate 17) xor (w[i-2] rightrotate 19) xor (w[i-2] rightshift 10)
w[i] := w[i-16] + s0 + w[i-7] + s1

and here the pseudocode of a round of the compression loop:

S1 := (e rightrotate 6) xor (e rightrotate 11) xor (e rightrotate 25)
ch := (e and f) xor ((not e) and g)
temp1 := h + S1 + ch + k[i] + w[i]
S0 := (a rightrotate 2) xor (a rightrotate 13) xor (a rightrotate 22)
maj := (a and b) xor (a and c) xor (b and c)
temp2 := S0 + maj

From my understanding the bitwise shifts and rotations add diffusion, while the additions add non-linearity (confusion), but what do the choice and majority functions do?

They are linear in nature, but they only influence the output in up to three out of the four possible cases for the other inputs, so at the same time they depend on multiple values. My only guesses are that they enhance the avalanche effect or prevent differential analysis.

$\endgroup$
1
  • 4
    $\begingroup$ "They are linear in nature"; actually, choice and majority are nonlinear - both in terms of bitwise and addition modulo $2^{32}$ $\endgroup$
    – poncho
    Commented May 17 at 22:21

1 Answer 1

2
$\begingroup$

The compression function of SHA-2 is an Unbalanced Feistel network for which one needs a non-linear round function otherwise it will be breakable easily.

SHA-256 has 64 and SHA-512 has 80 rounds and in each round, only one 32-bit block ( and 64 bits, respectively) is modified by the round function, the rest is shifted.

The additions ( $\bmod 2^{32}$ for SHA-256 and $\bmod 2^{64}$ for SHA-512), Ch, and Ma contribute to the non-linearity of the round function. This may seem simple to be insecure, however, what we know from Tiny Encryption Algorithm (TEA) is that a block cipher with a simple round can be made secure if enough round is applied where SHA-256's round function is 64 rounds and currently it seems to be secure.

With more rounds, it can achieve avalanche and differential attack resistance. We already believe that it has the avalanche effect and the attacks are only successful on reduced rounds. Biclique attacked on 52 out of 64 rounds of SHA-256 and 57 out of 80 of SHA-512. Differential attacks, on the other hand, are much less successful than Biclique attacks.

More details

From Wikipedia

As we can see the figure more clearly, Blocks $A,B,C,E,F,G$ are just copied into blocks $B,C,D,F,G,H$.

The block $A$, on the other hand, is modified with

  • $Ch(E,F,G) = (E \wedge F) \oplus (\neg E \wedge G) $; is choice and it is non-linear.
  • $Ma(A,B,C) = (A \wedge B) \oplus (A \wedge C) \oplus (A \wedge C)$ is the majority as non-linear.
  • $\Sigma_0$ and $\Sigma_1$ are just rotates and x-ors.
  • The $\boxplus$'s on the other hand, the addition module $\bmod 2^{32}$ for SHA-256 and $\bmod 2^{64}$ for SHA-512 is non-linear.

$E$ on the other hand, is modified with only $Ch$ and $Ma$

$\endgroup$

Your Answer

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

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