Searching for a differential characteristic (differential cryptanalysis)

Question

Currently I am doing some research on differential cryptanalysis. In general I got a good idea about the attack and how it is done.

I am currently talking about ciphers with multiple rounds. It seems that the success of a attack is depending on a good differential characteristic through the cipher. There are way which have good statistical values and some more which have not. In the paper there is often a good differential characteristic shown which works very well. But there is never a talk about how to find them. For sure I read about some heuristics like "look for differential characteristics with small amount of active sboxes" or something like that.

So my Question: How can I find a good differential or lets say, all? I am looking for a algorithm or a good description which I could implement on my own.

Answer 1

Finding differential characteristic means analyzing the structure of the given cipher(substitution and permutation elements). This analyzing means, we should track the input differentials(Δi) through the different elements of the cipher and produce related output differential(Δo).

Δx = X' xor X'' =>

                Δx=[ΔX1,ΔX2,ΔX3,....ΔXn]

                 =[X'1 xor X''1, X'2 xor X''2, X'3 xor X''3,...,X'n xor X''n]

We repeat this to round - 1. Each of these paths are called "Differential characteristic" and each of them has its own happening chance(probability).

As mentioned, in the paces of tracking Δi to Δo, we should consider that cipher structure is made of different confusion and diffusion elements which these elements effect the path in each round and leads to activating some SBoxes(called Active SBoxes). But the most important factor is finding the probability of each differential path(differential characteristic) and choosing the highest one(or ones) among them. The rout with the highest probability is the objection of the analyzer.

In order to find these differential characteristics we can use one of these three methods( It is general recommendation but not exact!!!):

• choose each differential characteristic in the cipher structure visually and calculate probability for them. However we should mention that this method is not applicable for the most variety of ciphers in that the number of input to the cipher is big( at least 16 bit) and if we want to have a precise estimation of differential status of the cipher,nearly we should test 2^16 input differentials and calculate the probability for each round. In the most situations this way is impossible.

• ** Use Sage S-box MILP toolkit ** which is developed and intended to calculate the differential characteristics for well-known block ciphers which have Substitution and permutation structure in them. This toolkit can be found in: http://www.swmath.org/?term=differential%20cryptanalysis and in this paper: https://www.esat.kuleuven.be/cosic/publications/article-2080.pdf the way of using them is explained.(I should remark that in the given toolkit, you should make some modifications in order to use them like changing the "coin solver"). This method is a very good way to finding the number of active SBoxes and calculating the differential characteristic of the cipher.

  -Implementation on our own code in order to find the differential characteristics with the highest probability among all input differentials. It is not hard and possible. We firstly should define all input differentials (states) and then calculate the probability of each state by considering these two factors:

            -Each SBox has differential property and should  affect in 
             each round in the differential characteristic when it is 
             activated.
  
            -Multiply calculated probabilities by the prior probability in 
             order to finding  rounds differential characteristics.  
  

  A good reference: https://www.engr.mun.ca/~howard/PAPERS/ldc_tutorial.pdf

---

But I should mention that finding differential characteristic for Feistel structures have a different story and a good reference is in: http://www.cs.haifa.ac.il/~orrd/BlockCipherSeminar/Lecture2-Differential.pdf

Answer 2

The details depend on the exact cipher design. However what you need to optimize (maximize) is the probability $$ \prod_{S_i ~\mathrm{active~in~differential~trail}} P(\Delta_{in},\Delta_{out},S_i), $$ where the deltas are the input and output differences to Sbox $S_i,$ and the differential trail is usually chosen to cover $r-1$ rounds for an $r$ round cipher.

In the case of SPN networks with wire crossing permutation layer, as in the Heys tutorial in the comment, you should look for an output differential with low Hamming weight to minimize the number of active Sboxes in the next round.