Given a strict avalanche criterion matrix/dependence matrix for a hash function,how do I calculate the avalanche coefficient for it. I want to calculate a single parameter(value) which represents the amount of avalanche effect for the given hash function.
I have thought of computing mean all over the matrix but am not sure that's the correct thing to do.
The following paper talks about the avalanche coefficient but they haven't mentioned the way they calculate it.
I believe the only way you can do this is to assume you have fixed length inputs to the hash function $f$. Otherwise, it is problematic what probability distribution you'd want to impose on the input set $\{0,1\}^{\ast}$ which is the collection of all finite input strings. In practice, hash functions do have an upper limit on the input string, but that's astronomical, in terms of testing all input strings.
So, let's assume the hash function has security parameter of $k$ bits. This corresponds to the function acting like a random function with outputs of length $n=2k$ bits.
Your testing would generate a large number of random values from a uniform distribution on $\{0,1\}^{m},$ thus treating the hash function as a random function $f:\{0,1\}^m\rightarrow \{0,1\}^n.$ Let this random set of inputs be denoted by $X$. Now define $$ a_{ij}=\#\{x \in X:[f(x\oplus e_i)]_j \neq [f(x)]_j\} $$ for $1\leq i\leq n,1\leq j\leq m,$ where $e_i$ is the vector with a one in the $i^{th}$ position and zeroes everywhere and $[u]_j$ denotes the $j^{th}$ component of vector $u$. $a_{ij}$ counts the number of inputs from $X$ which differ in the $j^{th}$ output bit when the $i^{th}$ input bit is flipped.
You can now define a degree of strict avalanche criterion $D_{SAC}(f)$ as $$ D_{SAC}(f):=1-\frac{\sum_{i=1}^n \sum_{j=1}^n \left|\frac{2a_{ij}}{\#X}-1\right|}{nm}, $$ with the expectation that $D_{SAC}(f)$ should be approximately 1, i.e., the sum of the absolute differences $$\left|\frac{2a_{ij}}{\#X}-1\right|$$ over $i$ and $j$ should be small. One way of expressing this may be to say $E[A_{ij}] \approx (\#X/2)$ if $A_{ij}$ is a random variable representing the $a_{ij}$ with $A_{ij}$ distributed as the binomial variable $Bin(\#X,1/2).$ From here you can then model the overall experiment in terms of chi squared variables, by using the Gaussian approximation to the binomial. So take the properly scaled $nm$ variables as being from a chisquared distribution with $nm-1$ degrees of freedom.
I've done it this way for SHA 512:-
Generate a random number 512 bits long, called O
Randomly flip one bit to generate number F
Compute X = SHA(O) xor SHA(F)
Calculate no. of set bits in X
Coefficient Ksac = X /512 (note)
Rinse and repeat a million times to get a mean for Ksac
(note) Should this be an integer division?
This is the result I got for comparing SHA 512 to a DIY hash function for 100,000 tests:-
P.S. I think that Gupta & Yadav have made up this metric themselves, but it's a good one.
P.P.S Whilst Ksac is a good one, I'm worried at their results. Their Ksac(SHA-256) is 8% out from the expected value. I performed millions of runs as it only takes minutes. Perhaps they only did 100. Or perhaps SHA-256 does not exhibit full avalanche effect and they're really on to something big. Either way, I would have expected discussion of the 8% as that's approaching a 1/10th divergence from expectation. The paper seems quite light, and I suspect that it's a Masters dissertation rather than research.
