5
$\begingroup$

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.

$\endgroup$

1 Answer 1

4
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$
    – Shiryo
    May 17, 2016 at 11:06
  • $\begingroup$ Oups yes, I don't know why, I read to the left... But you got the idea. :) $\endgroup$
    – Biv
    May 17, 2016 at 11:07
  • $\begingroup$ 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 $\endgroup$
    – Shiryo
    May 17, 2016 at 13:29
  • $\begingroup$ 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. $\endgroup$
    – Biv
    May 17, 2016 at 14:10
  • $\begingroup$ 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. $\endgroup$
    – Shiryo
    May 18, 2016 at 9:10

Your Answer

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

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