How is formal analysis of the strength of a round achieved?

Question

I've been trying to understand how the number of rounds are picked for ciphers. There seems to be a minimum number of rounds that is analyzed for "strength" and then some security margin is added.

M. Luby and C. Rackoff showed that you need only three rounds for a Feistel network if you have sufficiently random keys; however, this is not practical in reality, which is why we have key expansions. This leads me to my questions:

How is the strength of a key schedule formally analyzed?

We have suites for random numbers, such as diehard, but I've not found a reference how key schedule strength is formalized. One could look at series of rounds through diehard, but the keys will obviously be related. Furthermore, in literature, generally it seems that the key schedule is the most ridiculed part of every cipher. I dug into Ph.D. dissertations but I didn't find anything. Any suggestions would be greatly appreciated.

Answer 1

Only addressing the key expansion question:

There is a nice combinatorial property of vector boolean functions $$ f:\mathbb{F}_2^k \rightarrow \mathbb{F}_2^n $$ where $k<n,$ due to Maurer and Massey.

Such a function is an $(k,n,e)-$perfect local randomizer (PLR) if the following holds:

Let $y=(y_1,\ldots, y_n)=f(x_1,\ldots,x_k)=f(x).$ Then if the input $x$ is a vector of i.i.d. uniform binary random variables, so is every possible subcollection of $e$ output coordinates, i.e., $$ (y_{i_1},\ldots, y_{i_e}), $$ with $1\leq i_1<\cdots<i_e\leq n.$ So if you want subkeys that leak minimum information and are made of actual bits of the original key, this may help.

Answer 2

diehard is not the answer you're looking for. diehard is a randomness testing tool. It looks at a sample of ~10MB and checks if that sample is independent and uniformly distributed (IID). It uses simple statistics not implicit cryptographic experience. The output is essentially a binary output in that if some p values = 0.00000 or 1.00000 then the sample is not sufficiently IID. The sequence of p's that you'd get for a sample unequivocally known to be IID is somewhat a matter of interpretation, feelings and guesswork. dieharder, it's successor makes this binary choice much more explicit in outputting PASS, WEAK or FAILs.

You could easily produce a 10MB sample from the first round of a Feistel network such as DES. It would probably fail with a series of 0's after the decimal point. As the round count increases, the p values would start to look reasonable, but not increase any further. You would learn little of security from this exercise other than that the output is IID. So is 10MB of RC4 when analysed with diehard.

Don't be surprised that key expansion inside some of these primitives is weak. AES is weakish. Key expansion is only a part of the entire primitive and their security comes from a sum of the parts.

PS. Colourful language is great, but in this particular instance categorising key expansion algorithms as ridiculous skews the question somewhat. I think that analysts call them weak, rather than ridiculous. "Ridiculous" would transfer all the security responsibilities to the main part of the primitive, and imply that any old expansion like ROT13 could be used.