Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
The strict avalanche criterion (SAC) is a formalization of the avalanche effect. It is satisfied if, whenever a single input bit is complemented, each of the output bits changes with a 50% probability.
My questions are:
Is a 50% bit-change-probability optimal for any hash or is it just the minimal value so satify the strict avalanche criterion?
What if a hash-algorithm had a 100% bit-change-probability?
Consider a function $H:\{0,1\}^m\to\{0,1\}^h$ (that is, from the set of $m$-bit bistrings to the set of $h$-bit bitstrings). Define $D_n=0^n\mathbin\|1\mathbin\|0^{m-n-1}$ (that is, the $m$-bit "disturbance" bitstring with only bit $n$ set).
By a possible definition, $H$ satisfies the Strict Avalanche Criterion when for each of the $m\cdot h$ pairs $(n,i)$ with $0\le n<m$ and $0\le i<h$, the arithmetic sum of bit $i$ of $H(M\oplus D_n)\oplus H(M)$ computed for all $M$ in $\{0,1\}^m$ is $2^{m-1}$ (that is, exactly 50% of the number of terms summed).
That can be extended to functions with variable-size input (such as usual hashes) by stating that for each input size $m\ge2$ supported, the function satisfies the SAC (Note: when $m<2$ and $h\ne0$, no function satisfies the SAC).
Is a 50% bit-change-probability optimal for any hash or is it just the minimal value to satisfy the strict avalanche criterion?
Neither.
50% is not the minimal value to satisfy the strict avalanche criterion. For the SAC to hold, the probability that a 1-bit change in input changes any particular bit of output must be exactly 50%, where that probability is computed over the $2^m$ inputs.
The optimal for a cryptographic hash is to behave like a random function, and a random function is extremely unlikely to satisfy the SAC (for $m=2$ that has probability $2^{-h}$, and that goes further down very fast when $m$ grows). If a practical cryptographic hash ($h\ge128$) satisfies the SAC for some $m$ with $2\le m\le50$, that's easily detectable and a weakness in some possible applications. For large $m$ and practical secure hashes, it is computationally impossible to test if $H$ satisfies the SAC or not. Otherwise said, for large messages, a practical secure hash behaves as if it met the SAC for all computational purposes, even though it most likely does not.
Mildly interesting problem: up to what $m$ is it possible to get experimental evidence that a practical hash does not meet the SAC?
What if a hash-algorithm had a 100% bit-change-probability?
Such function must produce the XOR of its $m$ input bit(s), repeated $h$ times to form a $h$-bit vector, then XORed with a $h$-bit arbitrary value dependent only on $m$. It is not a secure cryptographic hash by any measure. Independently, it does not meet the SAC.
What if a hash-algorithm had a 100% bit-change-probability?
Well, it wouldn't be a hash. You might call it an oscillator or something, but certainly not a pseudo random function. One of the principal characteristics of a cryptographic hash is that the output appears pseudo random, given any input.
You're suggesting a behaviour like $f(b) = f'(a)$ as you'd have to maintain a memory of all of the previous output bits. There would be no randomness and no independence between the outputs. You'd then simply oscillate between the two outputs. It would be useless as a hash and no better than a quasi NOT operator.
The 50% bit-change-probability is not optimal. It's one of the fundamental requirements. But you'll also find that this will occur naturally with the construction of any good hash. A natural relationship between an output collision rate of $1/e$ and a 50% overall bit change emerges given enough internal bit mangling.
Be careful though. The avalanche effect and the strict avalanche effect are not the same, and folks tend to use them interchangeably. They're not and your wiki quote isn't explicitly correct. One is not simply the formalisation of the other. There's a succinct answer @ https://crypto.stackexchange.com/a/42471/23115 explaining this.
