The Strict Avalanche Criterion (SAC) is a measure of both confusion and diffusion, which are key properties of a cryptographic hash function. This work provides a working definition of the SAC, describes an experimental methodology that can be used to statistically evaluate whether a cryptographic hash meets the SAC, and uses this to investigate the degree to which compression function of the SHA-1 hash meets the SAC. The results ( @math ) are heartening: SHA-1 closely tracks the SAC after the first 24 rounds, and demonstrates excellent properties of confusion and diffusion throughout.
A simple example clarifies the difference. Babbage @cite_18 uses Lloyd's @cite_5 definition of the SAC and defines a SAC-compliant function:
@cite_5 @cite_18
2231898687 1997281127
The strict avalanche criterion was introduced by Webster and Tavares [3] in order to combine the ideas of completeness and the avalanche effect. A cryptographic transformation is complete if each output bit depends on all the input bits, and it exhibits the avalanche effect if an average of one half of the output bits change whenever a single input bit is complemented. To fulfil the strict avalanche criterion, each output bit should change with probability one half whenever a single input bit is complemented. This means, in particular, that there is no good lower order (fewer bits) approximation to the function. This is clearly a desirable cryptographic property since such an approximation would enable a corresponding reduction in the amount of work needed for an exhaustive search. Some recent work concerning the strict avalanche criterion for a Boolean function has been motivated by the claim that a certain cryptographically useful property will be true of any function satisfying the criterion. In the letter it is observed that not only is this claim untrue, but that possession of the property in question is in fact precluded by satisfaction of the strict avalanche criterion.