Mathematical Proof for Key independence in Differential Cryptanalysis

Question

How would you construct a proof that XOR difference of two cipher texts cancels the influence of the key?

I started out with a simple cipher defined as follows:

$C = \Phi( S(P\oplus K_{0}) \oplus K_{1})$

Where

• $\Phi$ is a permutation box
• $S$ is a substitution box
• $K_{0}$,$K_{1}$ are the first and second round keys respectively
• $P$ is the plaintext
• $C$ is the cipher-text

In an effort to prove that the XOR difference is independent of the influence of the round keys, I start by constructing an expression for the XOR difference of two cipher-texts :

$C_{0} \oplus C_{1} = \Phi( S(P_{0}\oplus K_{0}) \oplus K_{1}) \oplus \Phi( S(P_{1}\oplus K_{0}) \oplus K_{1})$

Which I've simplified to the following algebraic form:

$\Phi^{-1}( C_{0} \oplus C_{1}) = S(P_{0}\oplus K_{0}) \oplus S(P_{1}\oplus K_{0})$

I'm too paranoid about the non-linearity of the SBOXs to apply straight forward algebraic law to this form.

How do I get rid of the SBOXs and am I even going about this proof the correct way?

Answer 1

The difference between the pair of inputs going into the s-box (consisting of two plaintexts xored with the first round key) is the same as the difference in the plaintexts alone. i.e. $(P_0 \oplus K_0) \oplus (P_1 \oplus K_0) = P_0 \oplus P_1$, because the round key $K_0$ cancels out. Hence, the input difference is independent of the value of the first round key. No matter what value you pick for $K_0$, the difference of the two inputs going directly into the s-box will be the same as the difference between the two plaintexts, with probability 1.

On the contrary, the output difference (difference between the outputs of the two s-boxes) is not independent of the round key. Or to be more precise, if you know $P_0$, $P_1$, and $K_0$ then the output difference just after the s-boxes -- $S(P_0 \oplus K_0) \oplus S(P_1 \oplus K_0)$ -- is fully determined and will vary depending on the precise value of $K_0$.

If, however, you assume that the pair of plaintexts is chosen uniformly at random from all pairs that satisfy some particular difference $\Delta P$, then the probability that the output difference will equal some particular value $\Delta C$ is independent of the precise value of $K_0$. This is because any given value for $K_0$ will simply exchange one pair of plaintexts that xor together to equal $\Delta P$ for another pair that xor together to equal $\Delta P$ (because of the equality in the first paragraph above). As such, the input pair going into the s-box after the roundkey is applied is still a uniformly random pair that xors together to equal $\Delta P$.

So under the assumption that the input difference is fixed but the input pair that xors together to equal that fixed difference is selected uniformly at random**, the probability that the output equals $\Delta C$ is purely a function of the (unkeyed) s-box, as summarized in the difference distribution table for the s-box. Note that this is different for key-dependent s-boxes.

** This assumption is equivalent to the assumption that the input pair is fixed but the roundkey is selected uniformly at random.