# Linear Cryptanalysis of hash function

I've studied linear cryptanalysis, but i don't think I have it very clear. I've the following doubt: I've constructed a "cryptographic" hash function for an exercise, and now i want to show summarily that is secure from "linear cryptanalysis".

My idea was simply to create a linear approximation like this:

X_1 XOR X_2 XOR ... X_n XOR Y_1 XOR Y_2 XOR ... Y_m


which involves the input and the output (whose bits X_i, Y_j respectively, are XOR together) of my hash function, and for a very large set of random input (about 1000000), to count how many times the result of this operation was 0, and how many time was 1. Then if the number of 0 does not differ much from the number of 1 (i.e. with probability about 0.5 the result is 1, and with probability about 0.5 the result is 0), my function it's ok, otherwise it's not secure.

My doubt is: Is this method right? What bits of the input and output i have to include in the linear approximation, all?

PS: I don't have to do linear cryptanalysis but only a very general analysis based on it.

• You have a very simple test that tests - to some extend - if your function behaves as a pseudo random function. If it fails (and you expect the result to be pseudo random - it's a hash not an Random Bit Generator) then there is something wrong with your algorithm / implementation. But you cannot state the opposite: you cannot test the security of a hash by performing a single test for pseudo-randomness. Mar 19, 2017 at 13:14

has the following answer. In general, while doing linear cryptanalysis we try all possible subsets of input and output bits and look for biases in the resulting expressions. Thus there is a total of $2^{n+m}-1$ possible expressions to check.
Let $(a_1,\ldots,a_n) \in \{0,1\}^n,$ and $(b_1,\ldots,b_m)\in \{0,1\}^m.$ Then except for the case $(b_1,\ldots,b_n)=(0,\ldots,0)$ all the following expressions $$a_1 x_1 \oplus a_2 x_2 \oplus \cdots \oplus a_n x_n \oplus b_1 y_1\oplus \cdots \oplus b_m y_m$$ need to be computed and their biases tested. We rule out $(b_1,\ldots,b_n)$ being zero since then then we're not computing anything interesting about the output of the hash function, but it is OK to let $(a_1,\ldots,a_n)$ zero since that tests the overall balance of the function, regardless of input.