Calculate the Number of active s boxes

Question

I really want to learn how to calculate the number of active s _boxes for block cipher cryptographic algorithms. I want to do that manually after running each round of an algorithm such as LED algorithm, what should I notice or compare in order to calculate the number of active s_boxes ? I read that definition ".You run the algorithm with two different plaintexts (whose difference is usually small – just a few bits, everything else being equal).

Wherever these plaintexts lead to different inputs to an S-box (in any layer/round of the algorithm), we call this S-Box “active” (since the other S-boxes produce the same result for both plaintexts, they are called “passive” and are not considered further)"", and want to learn how to calculate the number of differential active s_boxes?

Answer 1

If you want to do this manually as stated in your question the approach would be similar to this:

• choose an input difference $\alpha$ compute the active input sboxes $n_0$ as the number of sboxes that have a non-zero input difference, when $\alpha$ is the input difference
• choose an plaintext $p_0$ and $p_1 = p_0 \oplus \alpha$
  • compute one round of encryption to get $t^1_0$, and $t^1_1$
  • compute $\gamma_1 = t^1_0 \oplus t^1_1$, which is the output difference after one encryption round.
  • compute the active sboxes after one round $n_1$ as the number of sboxes that have a non-zero input difference, regarding $\gamma_1$
  • repeat for number of rounds $r$ you want to cover
• the number of active sboxes for input difference $\alpha$ is $n(\alpha) = \sum_i n_i$
• repeat the full procedure for every possible $\alpha$
• the minimum number of active sboxes is $\min_\alpha n(\alpha)$.

Of course, there are more sophisticated ways than this, but if you want to do this manually, it might be a good start to understand the concept.

Answer 2

Here is a suggestion, you can start by reading the tutorial called A Tutorial on Differential and Linear Cryptanalysis by Heys, which is available on his webpage.

He goes through the active Sbox stuff in great detail, for the case of bit permutation of mixing layers.

For the case of AES style mixing layers designed by using MDS codes, have a look at the answer to the following question: here. A deep understanding of coding theory is not needed, the branch number is precisely the minimum number of active S-boxes for AES in two consecutive rounds.

Answer 3

For counting active S-boxes in an algorithm, you should find a number of Linear or differential characteristics with high probability and then do the cryptanalysis the algorithm with these characteristics during that, observe which S-boxes are transferring linear of differential characteristics and count them in each round. for a limited number of rounds, it can be possible, but we do with tools like "sage_sbox_milp" and that tools count it for a different number of rounds.