29
$\begingroup$

I'm learning about cryptographic hash functions and I have some questions about the functions used in the compression function.

MD5 uses the following functions:

$f_{1}(B,C,D)=(B\wedge C)\lor(D\wedge \lnot B)$

$f_{2}(B,C,D)=(B\wedge D)\lor(C\wedge\lnot D)$

$f_{3}(B,C,D)=B\oplus C\oplus D$

$f_{4}(B,C,D)=C\oplus(B\lor\lnot D)$

SHA-1 uses these functions:

$f_{1}(B,C,D)=(B\wedge C)\lor(D\wedge \lnot B)$

$f_{2}(B,C,D)=B\oplus C\oplus D$

$f_{3}(B,C,D)=(B\wedge C)\lor(B\wedge D)\lor(C\wedge D)$

$f_{4}(B,C,D)=B\oplus C\oplus D$

SHA-2 uses these functions:

$f_{1}(B,C,D)=(B\wedge C)\lor(D\wedge \lnot B)$

$f_{2}(B,C,D)=(B\wedge C)\oplus(B\wedge D)\oplus(C\wedge D)$

I am wondering how these functions were chosen.

I know that XOR is very effective at mixing the bits of input, but I don't know why a function like $(B\wedge C)\oplus(B\wedge D)\oplus(C\wedge D)$ (SHA-2) is more effective than $(B\wedge C)\lor(B\wedge D)\lor(C\wedge D)$ (SHA-1).

Could someone clarify why certain functions perform better? And how the specific functions were chosen.

$\endgroup$
35
$\begingroup$

The functions considered are binary functions of 3 bits to 1 bit (extended to bit vectors, that is bitwise functions). There are $2^{(2^3)}=256$ such functions.

All the functions considered are balanced; that is, there is an equal number of input combinations for which the function outputs 0 and for which the function outputs 1. That reduces the number of functions to $8!/(4!)^2=70$.

Aggregating balanced functions identical within the $3!=6$ orders and the $2^3=8$ polarities of the $3$ inputs leaves only $6$ classes (see final section); keeping the lexicographically first function in each class:

    z   y   x           g0      g1      g2      g3      g4      g5
    0   0   0           0       0       0       0       0       0
    0   0   1           0       0       0       0       0       1
    0   1   0           0       0       0       0       1       1
    0   1   1           0       1       1       1       1       0
    1   0   0           1       0       1       1       1       1
    1   0   1           1       1       0       1       1       0
    1   1   0           1       1       1       1       0       0
    1   1   1           1       1       1       0       0       1

Of these, it is excluded g0 and g4 since at least one of their input has no influence on the output. The other four functions exhibit properties that tend to be good for diffusion:

  • for any of their input fixed to either polarity, the output is non-constant when we vary the other inputs;
  • any of their input influences the output for at least two of the four combinations of the other inputs.

These surviving functions are:

  • g1 Majority, used for $f_3$ of SHA-1 and $f_2$ of SHA-2 (which turn out to be identical)
  • g2 Choice, used for $f_1$ and $f_2$ of MD5, $f_1$ of SHA-1, $f_1$ of SHA-2; this function is also called Select, or Digital Multiplexer (input x being 1 or 0 chooses which of y or z is the output);
  • g3, used (within order and inversion of inputs) for $f_4$ of MD5; as noted in comment, that function $(x\wedge y)\oplus z$ is also the Toffoli gate's third output;
  • g5 Parity, used for $f_3$ of MD5, $f_2$ and $f_4$ of SHA-1.

Addition per comment: g1 and g2 additionally have the property that any of their input influences the output for at most three of the four combinations of the other inputs; or, in other words, are not fully linear w.r.t. any of their input. This is desirable in some sense, as too much linearity opens to some differential attacks. This might be why g1 and g2 are preferred to g3 and g5 in SHA-2.


A comment asks for the derivation of classes of balanced functions of 3 bits to 1 identical within order and polarity of inputs. We'll represent a function by an 8-bit value $b_{000}\,b_{001}\,b_{010}\,b_{011}\,b_{100}\,b_{101}\,b_{110}\,b_{111}$ giving the output $b_{zyx}$ for the 8 combinations of the 3 inputs $z\,y\,x$.

Balanced functions have $b_{000}+b_{001}+b_{010}+b_{011}+b_{100}+b_{101}+b_{110}+b_{111}=4$. We scan them in lexicographic order (equivalently, numerical order when using big-endian convention); if not excluded, that's the function representative of a new class, and we exclude the functions obtainable from that by permutation of inputs, or changing the polarity of inputs. We can do this by considering any of the 6 following transformations applied, or not (there's some redundancy in applying the 64 combinations and many functions are excluded multiple times, but it does not harm):

  • turning output to $b_{000}\,b_{010}\,b_{001}\,b_{011}\,b_{100}\,b_{110}\,b_{101}\,b_{111}$ (exchanging $x$ and $y$)
  • turning output to $b_{000}\,b_{001}\,b_{100}\,b_{101}\,b_{010}\,b_{011}\,b_{110}\,b_{111}$ (exchanging $y$ and $z$)
  • turning output to $b_{000}\,b_{100}\,b_{010}\,b_{110}\,b_{001}\,b_{101}\,b_{011}\,b_{111}$ (exchanging $z$ and $x$)
  • turning output to $b_{001}\,b_{000}\,b_{011}\,b_{010}\,b_{101}\,b_{100}\,b_{111}\,b_{110}$ (complementing $x$)
  • turning output to $b_{010}\,b_{011}\,b_{000}\,b_{001}\,b_{110}\,b_{111}\,b_{100}\,b_{101}$ (complementing $y$)
  • turning output to $b_{100}\,b_{101}\,b_{110}\,b_{111}\,b_{000}\,b_{001}\,b_{010}\,b_{011}$ (complementing $z$)

We first get 00001111 = g0, and exclude 00110011, 01010101, 10101010, 11001100, 11110000; then get 00010111 = g1, and exclude 00101011, 01001101, 01110001, 10001110, 10110010, 11010100, 11101000; and so on. In the end, there are only 6 classes.

$\endgroup$
  • $\begingroup$ Thanks! Do you know of a source where these 4 possible functions are derived or explained? I can find the parity function here, the majority function here, but I can't find anything about the choice and last function. And shouldn't "choice, used for ..., $f_{2}$ of SHA-1", be "choice, used for ..., $f_{1}$ of SHA-1"? $\endgroup$ – Cartman123 Nov 6 '16 at 19:06
  • 2
    $\begingroup$ You mention that any of their input influences the output for at least two of the four combinations of the other inputs, but I believe there is also an advantage to have that any of their input influences the output for at most three of the four combinations of the other inputs. Otherwise the function could be rewritten as one input XOR'ed with an unbalanced or linear function of the other two inputs. (I don't know for sure, but I guess that's why parity is not used for SHA-2). $\endgroup$ – kasperd Nov 6 '16 at 21:28
  • 1
    $\begingroup$ MD5's $f_4 = C\oplus(B\lor\lnot D)$ is somewhat similar to the Toffoli gate's third output of $C\oplus(B\land A)$ $\endgroup$ – Nayuki Nov 7 '16 at 6:53
  • 1
    $\begingroup$ Could you show in more detail how you aggregated the identical functions, leaving only $6$ classes? That's the last thing I don't comprehend. $\endgroup$ – Cartman123 Nov 8 '16 at 18:35

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.