Optimal bit-change-probability of the avalanche effect for hashes Avalanche effect:


  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&lt;m$ and $0\le i&lt;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&lt;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.