Linear Cryptanalysis of hash function

Question

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.

Answer 1

As @MaartenBodewes stated in the comments, just one method of cryptanalysis cannot show a hash function is secure.

Your question

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

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.

In terms of more general analysis, there are obviously many other techniques, differential cryptanalysis, looking for collisions, looking for inverse images, etc. the latter two being directly related to hash function goals.