Avalanche effect sample size

With a fixed key size – key has 128 bits, while block size is 8 byte – how do I calculate how many different keys and texts I have to test for an cryptanalytic statistics study?

Differently worded: I am planning to encrypt multiple samples and see how many bits have changed, compared to the input block. Finally I plan to create a Histogram and get conclusions. If the cypher algorithm is good, half of the bits should have changed (50%).

The problem is that I do not know how many samples I have encrypt to gain a good statistical foundation. How many blocks do I have to (or should I) encrypt, and what formula should I be using?

-

You can use the Frequency test of the NIST statistical random number test suite. ( see http://csrc.nist.gov/groups/ST/toolkit/rng/documents/SP800-22rev1a.pdf, chapter 2.2).
In that chapter is also stated the recommended sample size.

I would propose to encrypt a block of zeroes with different randomly selected keys.

Another test would be to fix the key and use random plaintexts $t$, encrypt it $c= enc(t)$ and fit $t \oplus c$ to the frequency test.

-
"It is recommended that each sequence to be tested consist of a minimum of 100 bits (i.e., n ≥ 100)." "It is recommended that each sequence to be tested consist of a minimum of 100 bits (i.e., n ≥ 100). Note: that n ≥ MN. The block size M should be selected such that M ≥ 20, M > .01n and N < 100" @Cryptostasis All that works to check that the resultant encrypted blocks are random, but I don't see anywhere how many encryptions I have to perform. Can you give me more details, please ? Do I have to use the χ2 distribution to calculate the sample size? – jmb95 Oct 11 '15 at 12:29
I suposse I have to use χ2 with 1/2 proportion to calculate the sample size. – jmb95 Oct 11 '15 at 12:50
You cannot do a thorough cryptanalysis by statistic tests only. The Frequency test with fixed key and some random plaintext data will only show you that with this specific key the algorithm flips half of the bits. But maybe you have millions of bad keys which don't behave in this way. This cannot be found by statistical methods. – Cryptostasis Oct 11 '15 at 13:54
Maybe you have to be a bit more specific. Do you want to know the following? "If I choose a key randomly, then the probability of getting a key, which doesn't flip half of the bits, shall be less then, say, 0.000001" – Cryptostasis Oct 11 '15 at 14:02
(Paper "If the computed P-value is < 0.01, then conclude that the sequence is non-random. Otherwise, conclude that the sequence is random.") @Cryptostasis I would say, choosing a random key with a random input block the probability of getting a encrypted block that does not flip half of the bits shall be less than 0.01. What formula for sample size do I use for that statment ? I think I'm getting a bit frustated and confused with statistics. – jmb95 Oct 11 '15 at 14:08