Differential or Truncated Differential Attack On Small Cipher

Question

The cipher given below is a 16-bit toy cipher which uses 8-bit sbox and 2x2 byte Matrix. The Key $k_0$ and $k_1$ are $\oplus$ with the data. The multiplication with matrix is performed in $GF(2^8)$ with irreducible polynomial of $x^8+x^4+x^3+x+1$

The differential probability (DP) of the sbox for input difference of $0x01$ and output difference of $0x01$ is $40/256$.

For simplicity, it is assumed that $k_0$ and $k_1$ both are same, so guessing $k_1$ is enough.

A Brute force attack will take an effort of $2^{16}$ keys to be tested. How differential attack can be mounted with effort less than brute force.

I tried to mount attack differential attack with input pairs which has a difference of {$0x01$,$0x00$} but this required doing an effort of $2^{16}$. I did following

1. Get ciphertext of 256 chosen plaintext pairs which has difference of {$0x01$,$0x00$}.
2. For all values of $k_1$ , Xor $k_1$ with Ciphertext pair, run it through invMatrix, pass it to inv of sbox and then Compare the difference
3. If difference if equal to {$0x01$,$0x00$}, increment the count for this value of K1
4. The Key with highest increment is valid value of $k_1$

The content of Sbox is

6A, 3F, BF, 3D, BA, 2F, 91, B3, 1A, 52, F4, DE, 9B, D4, 7D, 7A,
72, 5A, 11, 36, A7, F5, E0, A0, E4, AC, 08, 1B, 50, F3, DC, 9A,
D7, 8B, AB, 09, 1D, 54, FE, FC, F8, EB, C9, 68, 44, CE, 78, 73,
62, 31, 98, D3, 87, A1, EC, C8, 67, 47, E2, AE, 16, 46, DD, A3,
FB, F6, E7, BE, 51, 0A, 20, 5E, 29, 81, 8E, BB, 42, D2, 8C, B7,
39, B9, 40, CD, 7B, 83, 9C, ED, CA, 6F, 66, 4E, 07, 1E, 5C, 27,
80, 90, C0, 49, EF, D1, 85, A4, 02, 0B, 1C, 57, 15, 43, D9, 95,
CF, 7C, 89, AF, 1F, 58, 18, 4D, FF, 00, 01, 03, 04, 05, 06, 0C,
0D, 0E, 0F, 10, 12, 13, 14, 17, 19, 21, 22, 23, 24, 25, 26, 28,
2A, 2B, 2C, 2D, 2E, 30, 32, 33, 34, 35, 37, 38, 3A, 3B, 3C, 3E,
41, 45, 48, 4A, 4B, 4C, 4F, 53, 55, 56, 59, 5B, 5D, 5F, 60, 61,
63, 64, 65, 69, 6B, 6C, 6D, 6E, 70, 71, 74, 75, 76, 77, 79, 7E,
7F, 82, 84, 86, 88, 8A, 8D, 8F, 92, 93, 94, 96, 97, 99, 9D, 9E,
9F, A2, A5, A6, A8, A9, AA, AD, B0, B1, B2, B4, B5, B6, B8, BC,
BD, C1, C2, C3, C4, C5, C6, C7, CB, CC, D0, D5, D6, D8, DA, DB,
DF, E1, E3, E5, E6, E8, E9, EA, EE, F0, F1, F2, F7, F9, FA, FD

Answer 1

How differential attack can be mounted with effort less than brute force.

Was the homework specifically to use a differential attack against this cipher?

Well, part of the problem you're having is that the cipher is, in some sense, too simple to use differential cryptanalysis against; the standard approach of "use DC to find a distinguisher in $N-1$ rounds, and then use that distinguisher to recover the subkey for the last round" doesn't apply.

The other issue is that you're still learning how to use differential cryptanalysis, and it certainly doesn't help that the standard approaches to use DC against this cipher doesn't work.

If you have to use DC, the first thing to do is look for high-probability differentials through the sbox; that is, values $\delta_i, \delta_o$ such that $sbox(x) \oplus sbox(x \oplus \delta_i) = \delta_o$ happen for lots of different values $x$; eyeballing the sbox, it would appear you can find such values which this happens far more often than a well-chosen sbox.

On the other hand, if you don't have to use DC, well, there's an easier approach to attack this cipher. To start, we note that MDS matrices are bit-wise linear, and bit-wise linear functions have this property:

$$MDS(x \oplus y) = MDS(x) \oplus MDS(y)$$

for all values $x, y$.

Hint: how can you use this relation against the cipher? How will this drastically reduce the work involved with attacking it?