As a toy model for a difference attack in my Cipher Systems course, I used the block cipher with plaintext and ciphertexts , key space and encryption functions defined by

where is the pseudo-inverse function from AES. Thus is defined by identifying with the finite field and then inverting non-zero elements. The zero word is the unique fixed point of .

Suppose you know a single plaintext/ciphertext pair . For each guessed first key there is a unique such that , namely

Thus a single known plaintext/ciphertext pair does not reveal either component of the key. To motivate the attack in this post, let us consider what two pairs and reveal. To save space, write for . Suppose that is a possible key:

A little thought shows that another possible key is :

Observe that the differences of top and bottom are in both cases

This illustrates the critical point that differences are invariant under key addition, but typically changed by non-linear functions such as . By the lemma below, for any non-zero *input difference* , the *output difference*

can be of the elements of . This is usually taken as a sign of the cryptographic strength of . But here it means that one can (apart from in one case) determine the pair from and . For the toy cipher, this pair is , and so we determine , leaving exactly two possible keys.

#### Differences through pseudo-inverse.

**Lemma.** Let . If then the equation has exactly zero or two solutions.

*Proof.* If then

We may therefore assume that and so and . Now if and only if . This is a quadratic equation in not having a repeated root. .

(In the exceptional case , there are four solutions, namely , , and the two roots of lying in . In fact, since has roots if and only if , which is a co-dimension subspace of , there are exactly output differences for each non-zero input difference , each except arising from exactly two inputs .)

In my course I spent an entire lecture on the difference attack, simplifying the lemma by only considering , corresponding to , and omitting the parenthetical paragraph entirely. Still I’m fairly sure no-one except the keenest M.Sc. students got the idea. Probably I will scrap it next year, and instead give an example from a different toy block cipher with a more easily defined -box. Or maybe, since there is no chance of universal comprehension, I should just leave it to a problem sheet, with a hint that the lemma above follows from Hilbert’s Theorem 90. (Joke.)

#### Variations on pseudo-inverse

*only*see the exceptional case (and even more embarrassingly, the pseudo-inverse function is linear), while over , defined by , the output differences for input difference are ; these are the (no-longer-so) exceptional , and the reciprocals of the non-zero elements in the subspace

for . Quadratic equations are now more easily understood: we can just complete the square to see that exactly of the elements are output differences; again the output difference has double the probability of the others.

*less*suitable for the attack. The situation for even input differences is somewhat messy. Clearly this is a non-starter for my course.

so as seen above, there is a affine codimension subspace of output differences. Unfortunately cubing is only invertible if is odd; this is the case when the subspace is properly affine and rules out .