0
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ So the "independence" can be argued on the basis that the mapping $\Delta_{P} \rightarrow \Delta_{C}$ under the SBox holds strongly regardless of the value of $K_{0}$? $\endgroup$
    – k3170makan
    Commented Mar 2, 2016 at 12:40
  • $\begingroup$ I guess I don't understand what exactly you want to show is independent of the key. Trivially, the (xor) difference of two plaintexts (or two ciphertexts) is the same before and after the application of a (xored) roundkey. But if you want to show that $\Pr[\Delta P \rightarrow \Delta C \;|\; K_0 = \alpha] = \Pr[\Delta P \rightarrow \Delta C]$ for any particular $\alpha$, then that is only the case if the pairs that support $\Delta P$ are selected uniformly at random (for e.g. think about what happens if the pairs are selected according to some non-uniform distribution). $\endgroup$
    – J.D.
    Commented Mar 2, 2016 at 14:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.