# Differential or Truncated Differential Attack On Small Cipher

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


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?

• regarding differential, i calculated the dp of the given sbox and i have mentioned it in the question. and how is it compulsory for a cipher to have more than one rounds to make DC practical? if it is so, can you suggest how to make DC on 2 rounds of similar cipher, where 2nd round will be similar to the above, just add one more layer of Sbox, Matrix and Xor with key K2, and assume k2 is similar to k1? Commented May 10, 2017 at 18:21
• @Raza: sorry, I missed it where you computed the DP. As for more than one rounds, the problem here is that there are so much easier ways to attack this one round cipher. As for a two round version, the straight-forward approach would look the best; inject a series of vectors with delta (01,00), and see 20 or so should be plenty; that give you several pairs where the after the first round is predictable. Then, look for second round K0 values that, for several of the pairs, make it work (hint: you don't need to cycle through all the bits of K0) Commented May 10, 2017 at 18:42
• I am able to run DC even for one round and find K1, but effort required is 2^16(trying all possible values of K1, where as i want to try attacking it in parts, like guessing only 1st bytes of K1 with effort around 2^8 or 2^10. and then solving for the 2nd byte Commented May 10, 2017 at 18:51
• @Raza: for one round, if you inject a (01, 00) differential, and if the sbox preserves the differential, then you know how the differential will flow through the rest of the system (second sbox, the MDS matrix). In that case, you know that the input to the first sbox was one of the forms the preserved the differential. How could you use that? Commented May 11, 2017 at 17:44
• I am exactly doing that, passing differential of {0x01,0x00}, but while doing backtrack, I need to guess both key bytes of k1 and try all possible combination of two bytes to correctly pass values from invP. Actually i want to avoid 2^16 guessing of both the key bytes of k1. Commented May 12, 2017 at 6:52