# differential cryptanalysis cipher for the final round

I have a problem to find the sub-key.

The system is…

For each round, we make the following stage:

1. We add the round key $$K_i$$.

2. Substitution : we have 8 blocks of 4 bits, and an S-box takes each block.

S = [7,3,6,1,13,9,10,11,2,12,0,4,5,15,8,14]

3. Permutation : circular shift of 2 to the right.

I choose the differential $$\Delta(1 \implies 4)$$ because after the permutation the differential trail is $$\Delta(1 \implies 4 \implies 1)$$. I coded in C, the algorithm to find the $$K_5$$, the sub key after 5 rounds.

plainText[m] is a random message and plainText[m+1] is plainText[m] ^ 1(difference).

 0000   0000   0000   0000   0000   0000   0000   0001
------ ------ ------ ------ ------ ------ ------ ------
| S1 | | S2 | | S3 | | S4 | | S5 | | S6 | | S7 | | S8 |
------ ------ ------ ------ ------ ------ ------ ------
0000   0000   0000   0000   0000   0000   0000   0100
\
0000   0000   0000   0000   0000   0000   0000   0001
------ ------ ------ ------ ------ ------ ------ ------
| S1 | | S2 | | S3 | | S4 | | S5 | | S6 | | S7 | | S8 |
------ ------ ------ ------ ------ ------ ------ ------
0000   0000  0000    0000   0000   0000   0000   0100


I tested the function of encryption and decryption, it operates normally. The problem is that I get a uniform array, because when I decrypted message, the differential trail is good for all the keys while normally this should not always be the case for any key for a message.

For example:

plaintText[i]=7584 and plaintText[i+1]=7585(7584 XOR 1).


In my code, for key=0,u=69b900ca and up=645100ca and tmp=2b131dd4 so beta=4. For key=1,u=69b900ca and up=645100cb and beta=4. The problem is that for any key, I get the same beta.

Remark: The round function of your toy cipher is the following.

       |
K ---> +
|
-------
|  S  |
-------
|
>> 2
|


Hence in the last round, the shift and S-box are useless (because invertible hence do not add security) which is why in a SPN scheme the key addition at the end is preferred.

I did a quick check your S-box differentials:

    |   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
---------------------------------------------------------------------
0 |  16
1 |       2           6       2   2           2               2
2 |       4   6                   2   2                   2
3 |               2       2   6   2               2   2
4 |               2               2   2       8       2
5 |                                       2       2   2   4   6
6 |           2           2           4       2   4       2
7 |       2           2                   2           6           4
8 |           2           6   4       2                           2
9 |       4   4   2   2                           2   2
10 |                   4   2       6                       2       2
11 |       2       8       2                   2               2
12 |           2           2                   2       2       2   6
13 |       2                   2       4   2       4           2
14 |               2               2   2                   6   2   2
15 |                   2       2          10       2
0011 => 0110 : 6 / 16
0010 => 0010 : 6 / 16
0101 => 1110 : 6 / 16
0001 => 0100 : 6 / 16
0100 => 1010 : 8 / 16
1100 => 1111 : 6 / 16
0111 => 1100 : 6 / 16
1010 => 0111 : 6 / 16
1011 => 0011 : 8 / 16
1110 => 1101 : 6 / 16
1111 => 1001 : 10 / 16
1000 => 0101 : 6 / 16


Hence the chosen one $\Delta(0001 \implies 0100)$ holds with a probability of $6/16$. However you forgot that you work with a 32bits block cipher: Meaning that with your chosen difference ($1$), will switch of to the next S-box after each round :

 0000   0000   0000   0000   0000   0000   0000   0001
------ ------ ------ ------ ------ ------ ------ ------
| S1 | | S2 | | S3 | | S4 | | S5 | | S6 | | S7 | | S8 |
------ ------ ------ ------ ------ ------ ------ ------
0000   0000   0000   0000   0000   0000   0000   0100
\
\     ROUND 1
0000   0000   0000   0000   0000   0000   0000   0001
------ ------ ------ ------ ------ ------ ------ ------
| S1 | | S2 | | S3 | | S4 | | S5 | | S6 | | S7 | | S8 |
------ ------ ------ ------ ------ ------ ------ ------
0000   0000   0000   0000   0000   0000   0000   0100
\
\     ROUND 2
0000   0000   0000   0000   0000   0000   0000   0001
------ ------ ------ ------ ------ ------ ------ ------
| S1 | | S2 | | S3 | | S4 | | S5 | | S6 | | S7 | | S8 |
------ ------ ------ ------ ------ ------ ------ ------
0000   0000   0000   0000   0000   0000   0000   0100
\
\     ROUND 3
0000   0000   0000   0000   0000   0000   0000   0001
------ ------ ------ ------ ------ ------ ------ ------
| S1 | | S2 | | S3 | | S4 | | S5 | | S6 | | S7 | | S8 |
------ ------ ------ ------ ------ ------ ------ ------
0000   0000   0000   0000   0000   0000   0000   0100
||||   ||||   ||||   ||||   ||||   ||||   ||||   ||||
0000   0000   0000   0000   0000   0000   0000   ????
\                                                \\\\
\\                                                \\\  ROUND 4
??00   0000   0000   0000   0000   0000   0000   00?? <-This is where you attack

------ ------ ------ ------ ------ ------ ------ ------
| S1 | | S2 | | S3 | | S4 | | S5 | | S6 | | S7 | | S8 |
------ ------ ------ ------ ------ ------ ------ ------
????   ????   ????   ????   ????   ????   ????   ????  Round 5


It is also note worthy that this differential holds with a probability of $3^4/8^4 = 81/4096 \approx 2\%$.

I did the attack when the key addition is at the end. I'm trying to make it works when the key addition is at the begining. WIP

• thanks for your help, I had ignored a circular shift in the computation of the output of sbox. But the output should not be like this: 0001 0000 0000 ------ ------ ------ ------ ------ | S1 | | S2 | | S3 | | ------ ------ ------ ------ ------ 0010 0000 0000 0000 1000 0000 Because we shift to the right? May 17, 2016 at 11:06
• Oups yes, I don't know why, I read to the left... But you got the idea. :)
– Biv
May 17, 2016 at 11:07
• I modified my code, but nevertheless I always have the problem of the result because when I decrypt of a round,i obtain well the characteristic but for 16 keys. For example: decrypt (ciphertext [m], 0) =1(characteristic), decrypt (ciphertext [m+1], 1)= 1... I do not understand why for 16 keys, I obtain the same thing May 17, 2016 at 13:29
• Well I guess that is a problem with your code. But unfortunately I can't see where. I would strongly advise you to check all your functions one by one. And by check I mean to tests most of possible inputs.
– Biv
May 17, 2016 at 14:10
• I check my encryption and decryption function is working correctly. I think cel can come to my choice of plaintText that I randomly selects and my second plaintText plaintext = ^ 1. May 18, 2016 at 9:10