9
$\begingroup$

The SHA-2 hashes in FIPS 180 define $\Sigma$ and $\sigma$ bijections of words, with $\Sigma$ used in the round function, and $\sigma$ used in preparing 48 words of message schedule from 16 words of a message block. For example, in SHA-256 (using 32-bit words) $$\begin{align*} \Sigma_0^{\{256\}}(x)&=\operatorname{ROTR}^{ 2}(x)\oplus\operatorname{ROTR}^{13}(x)\oplus\operatorname{ROTR}^{22}(x)\\ \Sigma_1^{\{256\}}(x)&=\operatorname{ROTR}^{ 6}(x)\oplus\operatorname{ROTR}^{11}(x)\oplus\operatorname{ROTR}^{25}(x)\\ \sigma_0^{\{256\}}(x)&=\operatorname{ROTR}^{ 7}(x)\oplus\operatorname{ROTR}^{18}(x)\oplus\operatorname{SHR}^{ 3}(x)\\ \sigma_1^{\{256\}}(x)&=\operatorname{ROTR}^{17}(x)\oplus\operatorname{ROTR}^{19}(x)\oplus\operatorname{SHR}^{10}(x)\end{align*}$$ with $\sigma$ functions used in $$W_t=\sigma_1^{\{256\}}(W_{t-2})\boxplus W_{t-7}\boxplus \sigma_0^{\{256\}}(W_{t-15})\boxplus W_{t-16}\;\text{ for }16\le t\le63$$ Notations:

  • $\operatorname{ROTR}^k$ is right-rotation by $k$; it could be implemented in the C language as
    uint32_t ROTR(int k, uint32_t x) { return x>>k | x<<(32-k); }
  • $\operatorname{SHR}^k$ is right-shift by $k$ with introduction of as many 0 on the left; in C
    uint32_t SHR(int k, uint32_t x) { return x>>k; }
  • $\oplus$ is bitwise EXclusive-OR (C's operator ^).
  • $\boxplus$ is addition with truncation to word size (C's operator +).

There are similar $\Sigma_i^{\{512\}}$ and $\sigma_i^{\{512\}}$ functions for SHA-512, using 64-bit words and different constants.

Question: Is there a reason for the use of $\operatorname{SHR}$ rather than $\operatorname{ROTR}$ in the $\sigma$ functions of SHA-2?

Note: if we used $\operatorname{ROTR}$ rather than $\operatorname{SHR}$, it would still hold that $\sigma$ functions are bijections.

$\endgroup$
10
  • 3
    $\begingroup$ Here is explanation for Serpent's linear layer: "Notice that if the linear transformation had used only rotates, then every characteristic could have 32 equiprobable rotated variants, with all the data words rotated by the same number of bits. This is the reason that we also use shift instructions, which avoid most of these rotated characteristics." cryptosoft.net/docs/Serpent.pdf $\endgroup$
    – LightBit
    Commented Jun 10, 2015 at 16:43
  • 1
    $\begingroup$ @LightBit: that applies to a linear transformation. In SHA-2, the key schedule is not linear, thanks to the alternation of ⊕ in the σ functions, and ⊞ in the message schedule. Thus I do not think that the reasoning applies, at least to a comparable degree. Something on that tune would indeed apply if we changed ⊞ to ⊕, so perhaps the desire to better guard against an approximation of ⊞ by ⊕ may have been in the mind of the designers. $\;$ Thanks for the contribution! $\endgroup$
    – fgrieu
    Commented Jun 10, 2015 at 17:34
  • 2
    $\begingroup$ @fgrieu actually I think he is spot on, from a paper describing attacks on SHA-1: "the linear code describing the SHA-1 message expansion is invariant with respect to word rotation". The linear code being $\sigma$. $\endgroup$ Commented Jun 11, 2015 at 0:50
  • 2
    $\begingroup$ @Richie Frame: Indeed, the message schedule of SHA-1 is linear:$$W_t=\operatorname{ROTR}^{31}(W_{t-3}\boxplus W_{t-8}\boxplus W_{t-14}\boxplus W_{t-16})\;\text{ for }16\le t\le79$$and further a rotation in input translates to a corresponding rotation of output. Neither weakness holds for the message schedule of SHA-2, including modified to use only $\operatorname{ROTR}$. Still, reducing odds of the second property might be the motivation I'm asking for. $\;$ I guess that should be turned into an answer. $\endgroup$
    – fgrieu
    Commented Jun 11, 2015 at 4:40
  • 4
    $\begingroup$ The question is somewhat answered in this paper. Replacing the third rotation by the shift makes the techniques used for SHA-0 and SHA-1 to build trails not work anymore. Whether this was what the designers intended, we'll probably never know. $\endgroup$ Commented Jun 1, 2017 at 9:39

0

Your Answer

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

Browse other questions tagged or ask your own question.