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.
Although there are proven theoretical ways to construct a function which satisfies the SAC @cite_16 , there is no way (apart from exhaustive testing) to verify that an existing function satisfies the SAC. By contrast, useful cryptographic properties such as non-degeneracy @cite_4 or bentness @cite_3 are verifiable without having to resort to exhaustive testing. However, the SAC metric is no worse in this regard than the correlation immunity and balance @cite_9 metrics which also require exhaustive testing.
@cite_9 @cite_16 @cite_4 @cite_3
2154271831 2787662955 1605416950 2090432705
Pseudonoise generators for cryptographic applications consisting of several linear feedback shift registers with a nonlinear combining function have been proposed as running key generators in stream ciphers. These running key generators eau sometimes be broken by (ciphertext-only) correlation attacks on individual subsequences. A new class of combining functions is presented, which provides better security against such attacks. The security is quantified by the smallest number m + 1 of subsequences that must be simultaneously considered in a correlation attack. A necessary condition for such m th-order correlation-immunity is proved. A recursive construction is given that permits the construction of an m th-order immune combining function for n subsequences for any m and n with 1 m . Finally, the trade-off between the length of the linear equivalent of the nonlinear generator and the order m of its immunity against correlation attacks is considered. We study the notion of linear structure of a function defined from ^m to ^n, and in particular of a Boolean function. We characterize the existence of linear structures by means of the Fourier transform of the function. For Boolean functions, this characterization can be stated in a simpler way. Finally, we give some constructions of resilient Boolean functions which have no linear structure. Abstract Let P ( x ) be a function from GF (2 n ) to GF (2). P ( x ) is called “bent” if all Fourier coefficients of (−1) P(x) are ±1. The polynomial degree of a bent function P ( x ) is studied, as are the properties of the Fourier transform of (−1) P(x) , and a connection with Hadamard matrices.