9
$\begingroup$

I know that these functions are there to actually make the program work. What I want to know is why they made the functions one way but not another. For example, why did they pick

F1(B, C, D) = (B & C) | (~B & D)

as their first function instead of another function like

F1(B, C, D) = (B & D) | (C ^ (D & ~B))

Improve this question
$\endgroup$
4
  • $\begingroup$ As a plus, if you have source for this reasoning, that would be greatly appreciated. Thanks! $\endgroup$
    – BonBon
    Commented Aug 27, 2015 at 1:35
  • 5
    $\begingroup$ Well, one obvious distinction between their F1 and yours is that their F1 has evenly distributed output (assuming the inputs are evenly distributed); yours has a distinct bias towards 1 bits. $\endgroup$
    – poncho
    Commented Aug 27, 2015 at 3:28
  • $\begingroup$ I just used that as an example, but thanks for your reply. $\endgroup$
    – BonBon
    Commented Aug 27, 2015 at 4:02
  • $\begingroup$ These functions were also used in MD4 and MD5, which predate SHA-1. So I guess the best person to ask would be Ron Rivest. I think one of the biggest factors was performance. The F1 function above can be evaluated by a single "select bits" instruction on processors that have one, as F1 can be interpreted as "if B then C else D". $\endgroup$
    – user13741
    Commented Aug 27, 2015 at 19:52

1 Answer 1

Reset to default
12
$\begingroup$

What choice did they have?

F1 is a bitwise function with three inputs and one output. There are $2^8 = 256$ such functions. Only 70 of them are "unbiased" (i.e. have as many 0 and 1 outputs in their image). If you further require that each input, as well as the order of inputs, matters for the output, you are left with only 36.

However, those 36 are all basically equivalent. If you change the order of arguments for F1 and/or add some initial negations to any of the arguments, you will be able to construct them all. So they could have added some initial not-operations (making it more complex) or changed the argument order, but that's it.

The only other options they had were biased functions like the one in the question, ones where some input doesn't matter (so they are actually one or two input functions), and ones where the argument order doesn't matter, like B ^ C ^ D.

Improve this answer
$\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.