4
$\begingroup$

I am studying the SHA-256 algorithm, and I am wondering something about it. How were the values used inside of the algorithm determined?

Take a look for example at how the 16-64th Words are generated. (in Java language)

    for (int j = 16; j < 64; ++j) {
        int s0 = Integer.rotateRight(words[j - 15], 7) ^
                Integer.rotateRight(words[j - 15], 18) ^
                (words[j - 15] >>> 3);

        int s1 = Integer.rotateRight(words[j - 2], 17) ^
                Integer.rotateRight(words[j - 2], 19) ^
                (words[j - 2] >>> 10);

        words[j] = words[j - 16] + s0 + words[j - 7] + s1;
    }

Just why were the values such as 15, 7, 18, 3, 2, 17, 19, 10, 16, and 7 chosen? Are these just arbitrary values that were randomly chosen for no reason? Or were these each chosen so that the algorithm is as difficult to reverse as possible.

    registers[7] = registers[6];
    registers[6] = registers[5];
    registers[5] = registers[4];
    registers[4] = registers[3] + temp1;
    registers[3] = registers[2];
    registers[2] = registers[1];
    registers[1] = registers[0];
    registers[0] = temp1 + temp2;

Also, in the main iteration loop (snippet shown above), why is the temp1 added to register[3]? Is that also just arbitrary or was it chosen for a particular reason?

Edit: To rephrase the question without code and with equations, I'll put it this way. In the equations to determine $W_t$ (for 16 <= t <= 63), you use the equation $$W_t = \sigma_1 (W_{t-2})+W_{t-7}+\sigma_0 (W_{t-15})+W_{t-16}$$ Where $$\sigma_0(x) = {ROTR}^{7}(x) \oplus {ROTR}^{18}(x) \oplus {SHR}^3(x)$$ $$\sigma_1(x) = {ROTR}^{17}(x) \oplus {ROTR}^{19}(x) \oplus {SHR}^{10}(x)$$ (according to FIPS PUB 180-4)

So, my question is, why were the arbitrary numbers in these equations chosen? The displacement of the word index by 2, 7, 15, and 16 appears to be random, but is there a reason to it? For the definition of $\sigma_0$ and $\sigma_1$, why were the arbitrary numbers 7, 18, 3, 17, 19, and 10 chosen?

The same question could also be asked about the main iteration loop, where $\Sigma_0$ and $\Sigma_1$ are used, which have just as arbitrary values in them.

As for the other question, it asks, why is it that $e = d + T_1$ in the loop from t=0 to t=63. It could have been placed in any of the other 6 working variables, was it randomly chosen that $d$ would be the variable that has $T_1$ added to it?

$\endgroup$
2
$\begingroup$

In $W_t = \sigma_1 (W_{t-2})+W_{t-7}+\sigma_0 (W_{t-15})+W_{t-16}$

  • The $16$ is the number of 32-bit words in a SHA-256 block. It is here so that, when we consider $W$ as an array of $16$ rather than $64$ words (as most hardware and many software implementations do), the equation become adding to $W_{t\bmod 16}$ a feedback term $\sigma_1 (W_{t-2\bmod 16})+W_{t-7\bmod 16}+\sigma_0 (W_{t-15\bmod 16})$.
  • The $-2$, $-7$, $-15$ controls how far back in the formerly produced values of $W$ the feedback terms are taken from.
    • The $-15$ is as far back as it can go, given the $-16$. That maximizes the memory involved in the feedback.
    • The $-2$ indexes into a recently produced word (second only to what $-1$ would give), which promotes fast diffusion, and splits short-term feedback into two flows (even and odd indexes); also $-1$ could be a bottleneck to parallelization.
    • The $-7$ indexes somewhere else near the middle of the 16-word array, is odd so as to mix said two flows faster that $-15$ would ultimately do, and is slightly biased towards recent production, perhaps to promote faster diffusion.
      Note: That later terms does not go thru a $\sigma$ function, contrary to the other two; that alternates XOR and addition (modulo the wordsize) in the feedback loop.

The shifts values are more difficult to justify. The pattern gives good diffusion, much better than a haphazard choice would do. But many other choices would be possible, and I can't pinpoint a selection process such that the choice made would be optimal.

$\endgroup$
  • $\begingroup$ Selecting as accepted answer, but if anyone else wants, feel free to make another answer if you feel it better answers the question. $\endgroup$ – Synchronic Oct 8 at 20:05

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.