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.
It is worth noting that the original definition, as per Webster & Tavares @cite_21 , is slightly ambiguous. They state that the probability that each bit in @math is equal to 1 should over the set of all possible plaintext vectors @math and @math ''; however, they also state that to satisfy the strict avalanche criterion, every element must have a value '' (emphasis mine). Under Lloyd's interpretation, the SAC is only satisfied when an element changes with a probability of precisely 0.5. This is an unnecessarily binary criterion, as it seems to be more useful (and more in line with the original definition) to understand how far a particular sample from the SAC. Therefore, this paper regards the SAC as a continuum but takes Lloyd's formulation as the definition of what it means to meet'' the SAC.
@cite_21
1670558497
The ideas of completeness and the avalanche effect were first introduced by Kam and Davida [1] and Feistel [2], respectively. If a cryptographic transformation is complete, then each ciphertext bit must depend on all of the plaintext bits. Thus, if it were possible to find the simplest Boolean expression for each ciphertext bit in terms of the plaintext bits, each of those expressions would have to contain all of the plaintext bits if the function was complete. Alternatively, if there is at least one pair of n-bit plaintext vectors X and Xi that differ only in bit i, and f(X) and f(Xi) differ at least in bit j for all @math then the function f must be complete.