the improvement in the overall time complexity is small: $2^{0.5}$. This application
shows however that our tool can complete in a few seconds a procedure that
would be extremely long by hand. Our tool will be automatically applicable to
any new and valid differential distinguisher that gets presented for this cipher
in the future. More details can be found in Annex E.

# 6 Conclusion and open problems

In this paper, we have proposed a new algorithm (and an automatic tool that implements it) to find efficient key recovery strategies in differential attacks. This permitted us to find efficient key recovery strategies for the attacks on many ciphers. We believe that our tool, which will be publicly available, will be of great help to cryptanalysts, but also to designers, as it will assist them in mounting attacks and in choosing optimal parameters for their construction.

We believe that the proposed tool is the first step towards a fully automated
treatment of differential attacks. Many extensions and improvements can be
considered. Indeed, our tool can for the moment only handle block ciphers with
a bit-permutation linear layer and a linear or almost-linear key schedule. A
natural extension is to adapt the tool such that it applies to ciphers with more
complex linear layers, based for example on an MDS multiplication. Another
improvement would be to adapt the tool to ciphers with non-linear key schedules
as currently, our tool needs the user to either linearise non-linear key schedules
or replace non-linear equations with new variables. Another interesting direction
is to adapt the tool to take into account tree-based key recovery techniques by
exploiting the structure of the involved S-boxes, as those proposed in [13].

Finally, the ultimate goal would be to combine this tool with algorithms that
search for differential distinguishers to propose a complete tool for differential
cryptanalysis that would produce attacks based on differential distinguishers that
are the best adapted for the key recovery. This is a challenging but particularly
important task, as it is known that the best distinguisher does not always lead
to the best attack.

**Acknowledgements.** This research is partially supported through the France 2030 program under grant agreement No. ANR-22-PECY-0010, by the French Agence Nationale de la Recherche through the OREO project under Contract ANR-22-CE39-0015 and the SWAP project under Contract ANR-21-CE39-0012 and it has been partially funded by the European Union (ERC-2023-COG, SoBaSyC, 101125450). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them.

# References

1. Banik, S., Pandey, S.K., Peyrin, T., Sasaki, Y., Sim, S.M., Todo, Y.: GIFT: A small Present - towards reaching the limit of lightweight encryption. In: Fischer,
W., Homma, N. (eds.) CHES 2017. Lecture Notes in Computer Science, vol. 10529, pp. 321–345. Springer (2017)

2. Beierle, C., Broll, M., Canale, F., David, N., Flórez-Gutiérrez, A., Leander, G., Naya-Plasencia, M., Todo, Y.: Improved differential-linear attacks with applications to ARX ciphers. J. Cryptol. 35(4), 29 (2022)

3. Beyne, T., Neyt, A.: Note on the cryptanalysis of speedy. Cryptology ePrint Archive, Paper 2024/262 (2024), https://eprint.iacr.org/2024/262

4. Beyne, T., Rijmen, V.: Differential cryptanalysis in the fixed-key model. In: Dodis, Y., Shrimpton, T. (eds.) CRYPTO 2022, Part III. Lecture Notes in Computer Science, vol. 13509, pp. 687–716. Springer (2022)

5. Biham, E., Shamir, A.: Differential cryptanalysis of DES-like cryptosystems. In: Menezes, A., Vanstone, S.A. (eds.) CRYPTO '90. Lecture Notes in Computer Science, vol. 537, pp. 2–21. Springer (1990)

6. Biham, E., Shamir, A.: Differential cryptanalysis of Feal and N-Hash. In: Davies, D.W. (ed.) EUROCRYPT '91. Lecture Notes in Computer Science, vol. 547, pp. 1–16. Springer (1991)

7. Biham, E., Shamir, A.: Differential cryptanalysis of Snefru, Khafre, REDOC-II, LOKI and Lucifer. In: Feigenbaum, J. (ed.) CRYPTO '91. Lecture Notes in Computer Science, vol. 576, pp. 156–171. Springer (1991)

8. Biham, E., Shamir, A.: Differential cryptanalysis of the full 16-round DES. In: Brickell, E.F. (ed.) CRYPTO '92. Lecture Notes in Computer Science, vol. 740, pp. 487–496. Springer (1992)

9. Bogdanov, A., Knudsen, L.R., Leander, G., Paar, C., Poschmann, A., Robshaw, M.J.B., Seurin, Y., Vikkelsoe, C.: PRESENT: an ultra-lightweight block cipher. In: Paillier, P., Verbauwhede, I. (eds.) CHES 2007. Lecture Notes in Computer Science, vol. 4727, pp. 450–466. Springer (2007)

10. Bouillaguet, C., Derbez, P., Fouque, P.: Automatic search of attacks on round-reduced AES and applications. In: Rogaway, P. (ed.) CRYPTO 2011. Lecture Notes in Computer Science, vol. 6841, pp. 169–187. Springer (2011)

11. Bouillaguet, C., Derbez, P., Fouque, P.: Automatic search of attacks on round-reduced AES and applications. In: Rogaway, P. (ed.) CRYPTO 2011. Lecture Notes in Computer Science, vol. 6841, pp. 169–187. Springer (2011)

12. Boura, C., David, N., Boissier, R.H., Naya-Plasencia, M.: Better steady than speedy: Full break of SPEEDY-7-192. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023, Proceedings, Part IV. Lecture Notes in Computer Science, vol. 14007, pp. 36–66. Springer (2023)

13. Broll, M., Canale, F., Flórez-Gutiérrez, A., Leander, G., Naya-Plasencia, M.: Generic framework for key-guessing improvements. In: Tibouchi, M., Wang, H. (eds.) ASIACRYPT 2021, Part I. Lecture Notes in Computer Science, vol. 13090, pp. 453–483. Springer (2021)

14. Canale, F., Naya-Plasencia, M.: Guessing less and better: Improved attacks on GIFT-64. IACR Cryptol. ePrint Arch. p. 354 (2023), https://eprint.iacr.org/2023/354

15. Canteaut, A., Naya-Plasencia, M., Vayssière, B.: Sieve-in-the-middle: Improved MITM attacks. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part I. Lecture Notes in Computer Science, vol. 8042, pp. 222–240. Springer (2013)

16. Daemen, J., Rijmen, V.: The wide trail design strategy. In: Honary, B. (ed.) IMACC 2001. Lecture Notes in Computer Science, vol. 2260, pp. 222–238. Springer (2001)

17. Derbez, P., Euler, M., Fouque, P., Nguyen, P.H.: Revisiting related-key boomerang attacks on AES using computer-aided tool. In: Agrawal, S., Lin, D. (eds.) ASI-
W., Homma, N. (eds.) CHES 2017. Lecture Notes in Computer Science, vol. 10529, pp. 321–345. Springer (2017)

2. Beierle, C., Broll, M., Canale, F., David, N., Flórez-Gutiérrez, A., Leander, G., Naya-Plasencia, M., Todo, Y.: Improved differential-linear attacks with applications to ARX ciphers. J. Cryptol. 35(4), 29 (2022)

3. Beyne, T., Neyt, A.: Note on the cryptanalysis of speedy. Cryptology ePrint Archive, Paper 2024/262 (2024), https://eprint.iacr.org/2024/262

4. Beyne, T., Rijmen, V.: Differential cryptanalysis in the fixed-key model. In: Dodis, Y., Shrimpton, T. (eds.) CRYPTO 2022, Part III. Lecture Notes in Computer Science, vol. 13509, pp. 687–716. Springer (2022)

5. Biham, E., Shamir, A.: Differential cryptanalysis of DES-like cryptosystems. In: Menezes, A., Vanstone, S.A. (eds.) CRYPTO '90. Lecture Notes in Computer Science, vol. 537, pp. 2–21. Springer (1990)

6. Biham, E., Shamir, A.: Differential cryptanalysis of Feal and N-Hash. In: Davies, D.W. (ed.) EUROCRYPT '91. Lecture Notes in Computer Science, vol. 547, pp. 1–16. Springer (1991)

7. Biham, E., Shamir, A.: Differential cryptanalysis of Snefru, Khafre, REDOC-II, LOKI and Lucifer. In: Feigenbaum, J. (ed.) CRYPTO '91. Lecture Notes in Computer Science, vol. 576, pp. 156–171. Springer (1991)

8. Biham, E., Shamir, A.: Differential cryptanalysis of the full 16-round DES. In: Brickell, E.F. (ed.) CRYPTO '92. Lecture Notes in Computer Science, vol. 740, pp. 487–496. Springer (1992)

9. Bogdanov, A., Knudsen, L.R., Leander, G., Paar, C., Poschmann, A., Robshaw, M.J.B., Seurin, Y., Vikkelsoe, C.: PRESENT: an ultra-lightweight block cipher. In: Paillier, P., Verbauwhede, I. (eds.) CHES 2007. Lecture Notes in Computer Science, vol. 4727, pp. 450–466. Springer (2007)

10. Bouillaguet, C., Derbez, P., Fouque, P.: Automatic search of attacks on round-reduced AES and applications. In: Rogaway, P. (ed.) CRYPTO 2011. Lecture Notes in Computer Science, vol. 6841, pp. 169–187. Springer (2011)

11. Bouillaguet, C., Derbez, P., Fouque, P.: Automatic search of attacks on round-reduced AES and applications. In: Rogaway, P. (ed.) CRYPTO 2011. Lecture Notes in Computer Science, vol. 6841, pp. 169–187. Springer (2011)

12. Boura, C., David, N., Boissier, R.H., Naya-Plasencia, M.: Better steady than speedy: Full break of SPEEDY-7-192. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023, Proceedings, Part IV. Lecture Notes in Computer Science, vol. 14007, pp. 36–66. Springer (2023)

13. Broll, M., Canale, F., Flórez-Gutiérrez, A., Leander, G., Naya-Plasencia, M.: Generic framework for key-guessing improvements. In: Tibouchi, M., Wang, H. (eds.) ASIACRYPT 2021, Part I. Lecture Notes in Computer Science, vol. 13090, pp. 453–483. Springer (2021)

14. Canale, F., Naya-Plasencia, M.: Guessing less and better: Improved attacks on GIFT-64. IACR Cryptol. ePrint Arch. p. 354 (2023), https://eprint.iacr.org/2023/354

15. Canteaut, A., Naya-Plasencia, M., Vayssière, B.: Sieve-in-the-middle: Improved MITM attacks. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part I. Lecture Notes in Computer Science, vol. 8042, pp. 222–240. Springer (2013)

16. Daemen, J., Rijmen, V.: The wide trail design strategy. In: Honary, B. (ed.) IMACC 2001. Lecture Notes in Computer Science, vol. 2260, pp. 222–238. Springer (2001)

17. Derbez, P., Euler, M., Fouque, P., Nguyen, P.H.: Revisiting related-key boomerang attacks on AES using computer-aided tool. In: Agrawal, S., Lin, D. (eds.) ASI-
ACCRYPT 2022, Part III. Lecture Notes in Computer Science, vol. 13793, pp. 68–88.
Springer (2022)

18. Dong, X., Qin, L., Sun, S., Wang, X.: Key guessing strategies for linear key-schedule algorithms in rectangle attacks. In: Dunkelman, O., Dziembowski, S. (eds.) EUROCRYPT 2022, Part III. Lecture Notes in Computer Science, vol. 13277, pp. 3–33.
Springer (2022)

19. Flórez-Gutiérrez, A.: Optimising linear key recovery attacks with affine Walsh transform pruning. In: Agrawal, S., Lin, D. (eds.) ASIACRYPT 2022, Part IV. Lecture Notes in Computer Science, vol. 13794, pp. 447–476. Springer (2022)

20. Flórez-Gutiérrez, A., Naya-Plasencia, M.: Improving key-recovery in linear attacks: Application to 28-round PRESENT. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020, Part I. Lecture Notes in Computer Science, vol. 12105, pp. 221–249.
Springer (2020)

21. Fouque, P., Jean, J., Peyrin, T.: Structural evaluation of AES and chosen-key distinguisher of 9-round AES-128. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part I. Lecture Notes in Computer Science, vol. 8042, pp. 183–203. Springer (2013)

22. Hadipour, H., Sadeghi, S., Eichlseder, M.: Finding the impossible: Automated search for full impossible-differential, zero-correlation, and integral attacks. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023, Part IV. Lecture Notes in Computer Science, vol. 14007, pp. 128–157. Springer (2023)

23. Knellwolf, S., Meier, W., Naya-Plasencia, M.: Conditional differential cryptanalysis of NLFSR-based cryptosystems. In: Abe, M. (ed.) ASIACRYPT 2010. Lecture Notes in Computer Science, vol. 6477, pp. 130–145. Springer (2010)

24. Leander, G., Moos, T., Moradi, A., Rasoolzadeh, S.: The SPEEDY family of block ciphers engineering an ultra low-latency cipher from gate level for secure processor architectures. IACR Trans. Cryptogr. Hardw. Embed. Syst. **2021**(4), 510–545 (2021)

25. Lu, J., Kim, J., Keller, N., Dunkelman, O.: Improving the efficiency of impossible differential cryptanalysis of reduced Camellia and MISTY1. In: Malkin, T. (ed.) CT-RSA 2008. Lecture Notes in Computer Science, vol. 4964, pp. 370–386. Springer (2008)

26. Nageler, M.: Automatic cryptanlysis of block ciphers: Finding efficient key-recovery attacks. Master's thesis, Graz University of Technology (2022). https://doi.org/10.3217/n8ehm-dgj71

27. Naya-Plasencia, M.: How to improve rebound attacks. In: Rogaway, P. (ed.) CRYPTO 2011. Lecture Notes in Computer Science, vol. 6841, pp. 188–205.
Springer (2011)

28. Peyrin, T., Tan, Q.Q.: Mind your path: On (key) dependencies in differential characteristics. IACR Trans. Symmetric Cryptol. **2022**(4), 179–207 (2022)

29. Qiao, K., Hu, L., Sun, S.: Differential security evaluation of Simeck with dynamic key-guessing techniques. In: Camp, O., Furnell, S., Mori, P. (eds.) ICISSP 2016. pp. 74–84. SciTePress (2016)

30. Qin, L., Dong, X., Wang, X., Jia, K., Liu, Y.: Automated search oriented to key recovery on ciphers with linear key schedule applications to boomerangs in SKINNY and ForkSkinny. IACR Trans. Symmetric Cryptol. **2021**(2), 249–291 (2021)

31. Rouquette, L., Gérault, D., Minier, M., Solnon, C.: And Rijndael?: Automatic related-key differential analysis of Rijndael. In: Batina, L., Daemen, J. (eds.) AFRICACRYPT 2022. pp. 150–175. Lecture Notes in Computer Science, Springer Nature Switzerland (2022)
ACCRYPT 2022, Part III. Lecture Notes in Computer Science, vol. 13793, pp. 68–88.
Springer (2022)

18. Dong, X., Qin, L., Sun, S., Wang, X.: Key guessing strategies for linear key-schedule algorithms in rectangle attacks. In: Dunkelman, O., Dziembowski, S. (eds.) EUROCRYPT 2022, Part III. Lecture Notes in Computer Science, vol. 13277, pp. 3–33.
Springer (2022)

19. Flórez-Gutiérrez, A.: Optimising linear key recovery attacks with affine Walsh transform pruning. In: Agrawal, S., Lin, D. (eds.) ASIACRYPT 2022, Part IV. Lecture Notes in Computer Science, vol. 13794, pp. 447–476. Springer (2022)

20. Flórez-Gutiérrez, A., Naya-Plasencia, M.: Improving key-recovery in linear attacks: Application to 28-round PRESENT. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020, Part I. Lecture Notes in Computer Science, vol. 12105, pp. 221–249.
Springer (2020)

21. Fouque, P., Jean, J., Peyrin, T.: Structural evaluation of AES and chosen-key distinguisher of 9-round AES-128. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part I. Lecture Notes in Computer Science, vol. 8042, pp. 183–203. Springer (2013)

22. Hadipour, H., Sadeghi, S., Eichlseder, M.: Finding the impossible: Automated search for full impossible-differential, zero-correlation, and integral attacks. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023, Part IV. Lecture Notes in Computer Science, vol. 14007, pp. 128–157. Springer (2023)

23. Knellwolf, S., Meier, W., Naya-Plasencia, M.: Conditional differential cryptanalysis of NLFSR-based cryptosystems. In: Abe, M. (ed.) ASIACRYPT 2010. Lecture Notes in Computer Science, vol. 6477, pp. 130–145. Springer (2010)

24. Leander, G., Moos, T., Moradi, A., Rasoolzadeh, S.: The SPEEDY family of block ciphers engineering an ultra low-latency cipher from gate level for secure processor architectures. IACR Trans. Cryptogr. Hardw. Embed. Syst. **2021**(4), 510–545 (2021)

25. Lu, J., Kim, J., Keller, N., Dunkelman, O.: Improving the efficiency of impossible differential cryptanalysis of reduced Camellia and MISTY1. In: Malkin, T. (ed.) CT-RSA 2008. Lecture Notes in Computer Science, vol. 4964, pp. 370–386. Springer (2008)

26. Nageler, M.: Automatic cryptanlysis of block ciphers: Finding efficient key-recovery attacks. Master's thesis, Graz University of Technology (2022). https://doi.org/10.3217/n8ehm-dgj71

27. Naya-Plasencia, M.: How to improve rebound attacks. In: Rogaway, P. (ed.) CRYPTO 2011. Lecture Notes in Computer Science, vol. 6841, pp. 188–205.
Springer (2011)

28. Peyrin, T., Tan, Q.Q.: Mind your path: On (key) dependencies in differential characteristics. IACR Trans. Symmetric Cryptol. **2022**(4), 179–207 (2022)

29. Qiao, K., Hu, L., Sun, S.: Differential security evaluation of Simeck with dynamic key-guessing techniques. In: Camp, O., Furnell, S., Mori, P. (eds.) ICISSP 2016. pp. 74–84. SciTePress (2016)

30. Qin, L., Dong, X., Wang, X., Jia, K., Liu, Y.: Automated search oriented to key recovery on ciphers with linear key schedule applications to boomerangs in SKINNY and ForkSkinny. IACR Trans. Symmetric Cryptol. **2021**(2), 249–291 (2021)

31. Rouquette, L., Gérault, D., Minier, M., Solnon, C.: And Rijndael?: Automatic related-key differential analysis of Rijndael. In: Batina, L., Daemen, J. (eds.) AFRICACRYPT 2022. pp. 150–175. Lecture Notes in Computer Science, Springer Nature Switzerland (2022)
DOUTa 3 3 3 3 3 3 3 3 3 3 3 3 3 3

DKEY 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0

nrR 9

KS
k0[2]
k0[3]
k0[6]
k0[7]
k0[10]
k0[11]
k0[14]
k0[15]

## B Comparison with previous work

The tool we propose in this work has certain similarities with a previous tool proposed in [11] by Bouillaguet et al. to optimize a different type of attacks. We discuss in this section the similarities that method has with our tool and explain the advantages of our approach. The aim of the automatic tool presented in [11] was to search for meet-in-the-middle attacks on a large variety of block ciphers. More precisely, the authors described in this article a generic framework to solve a system of AES-like equations, i.e. equations of the form:

$$ \sum \alpha_i x_i + \sum \beta_i S(x_i) = \gamma, $$

where $S$ is an S-box, and $\alpha_i$, $\beta_i$ and $\gamma$ are constant values in $\mathbb{F}_{2^n}$. Since such equations are separable, i.e. $f(X \cup Y) = 0$ can always be rewritten as $\{g(X) = h(Y), g_X(X) = 0, h_Y(Y) = 0\}$ for any set of variables $X$ and any set of variables $Y$, their main idea was to solve a system of such equations by using a divide-and-conquer approach in which, given an algorithm $A_X$ solving the equation $g_X(X) = 0$ as well as an algorithm $A_Y$ solving the equation $h_Y(Y) = 0$, we can combine them into a new algorithm $A_{X \cup Y}$ solving $f(X \cup Y) = 0$. Furthermore,
the time complexity of this new algorithm can be easily computed as:

$$T(\mathcal{A}_{X \cup Y}) = T(\mathcal{A}_X) + T(\mathcal{A}_Y) + \text{number of solutions of } f(X \cup Y) = 0.$$

We refer the reader to [11] for more details on the topic.

While this approach gave very good results, especially regarding low data complexity attacks on the AES, it has many limitations. First the properties of the S-box are not taken into account since the S-box is seen as a black box. Second, they only consider the case in which the system is word-oriented, meaning that the S-box depends on only one variable. Third, the only freedom for the user is to declare some variables of the system as known variables (for instance the plaintext and the ciphertext can be set as known) but it is not possible to emulate the situation of the key-recovery process of a differential attack. Finally, the merge between the various sub-algorithms occurring in the problem one wants to solve are performed randomly, making it difficult to solve big instances, especially when we want to ensure the optimality of the solution.

Our work was inspired by this tool but our goal was to provide a solution in the specific case of differential attacks for SPN ciphers with a bit-permutation as linear layer, by overcoming the weaknesses of [11]. Our contributions include a natural modelization of the problem as a graph to limit the number of merges to be performed through the execution of our tool as well as taking into account filters at the input of each S-box leading to a much better granularity of the number of solutions at each step of the process and thus to a more accurate overall complexity of the key recovery attack.

## C Specifications and differential properties of RECTANGLE

We provide in this section the specifications of the S-box (Table 7) and of the bit-permutation (Table 8) used in RECTANGLE. For completeness, we also provide the Difference Distribution Table (DDT) of the S-box in Table 9.

<table><caption>**Table 7.** The S-box of RECTANGLE</caption><thead><tr><th>x</th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>10</th><th>11</th><th>12</th><th>13</th><th>14</th><th>15</th></tr></thead><tbody><tr><th>S(x)</th><td>6</td><td>5</td><td>12</td><td>10</td><td>1</td><td>14</td><td>7</td><td>9</td><td>11</td><td>0</td><td>3</td><td>13</td><td>8</td><td>15</td><td>4</td><td>2</td></tr></tbody></table>

## D Specifications and differential properties of PRESENT

We provide here the specifications of the S-box (Table 10) and of the bit-permutation layer (Table 11) used in PRESENT. For completeness, we also provide the Difference Distribution Table (DDT) of the S-box in Table 12.
the time complexity of this new algorithm can be easily computed as:

$$T(\mathcal{A}_{X \cup Y}) = T(\mathcal{A}_X) + T(\mathcal{A}_Y) + \text{number of solutions of } f(X \cup Y) = 0.$$

We refer the reader to [11] for more details on the topic.

While this approach gave very good results, especially regarding low data complexity attacks on the AES, it has many limitations. First the properties of the S-box are not taken into account since the S-box is seen as a black box. Second, they only consider the case in which the system is word-oriented, meaning that the S-box depends on only one variable. Third, the only freedom for the user is to declare some variables of the system as known variables (for instance the plaintext and the ciphertext can be set as known) but it is not possible to emulate the situation of the key-recovery process of a differential attack. Finally, the merge between the various sub-algorithms occurring in the problem one wants to solve are performed randomly, making it difficult to solve big instances, especially when we want to ensure the optimality of the solution.

Our work was inspired by this tool but our goal was to provide a solution in the specific case of differential attacks for SPN ciphers with a bit-permutation as linear layer, by overcoming the weaknesses of [11]. Our contributions include a natural modelization of the problem as a graph to limit the number of merges to be performed through the execution of our tool as well as taking into account filters at the input of each S-box leading to a much better granularity of the number of solutions at each step of the process and thus to a more accurate overall complexity of the key recovery attack.

## C Specifications and differential properties of RECTANGLE

We provide in this section the specifications of the S-box (Table 7) and of the bit-permutation (Table 8) used in RECTANGLE. For completeness, we also provide the Difference Distribution Table (DDT) of the S-box in Table 9.

<table><caption>**Table 7.** The S-box of RECTANGLE</caption><thead><tr><th>x</th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>10</th><th>11</th><th>12</th><th>13</th><th>14</th><th>15</th></tr></thead><tbody><tr><th>S(x)</th><td>6</td><td>5</td><td>12</td><td>10</td><td>1</td><td>14</td><td>7</td><td>9</td><td>11</td><td>0</td><td>3</td><td>13</td><td>8</td><td>15</td><td>4</td><td>2</td></tr></tbody></table>

## D Specifications and differential properties of PRESENT

We provide here the specifications of the S-box (Table 10) and of the bit-permutation layer (Table 11) used in PRESENT. For completeness, we also provide the Difference Distribution Table (DDT) of the S-box in Table 12.
<table><caption>**Table 8.** The bit-permutation of RECTANGLE</caption><thead><tr><th></th><th>i</th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>10</th><th>11</th><th>12</th><th>13</th><th>14</th><th>15</th></tr></thead><tbody><tr><td>P(i)</td><td>0</td><td>5</td><td>50</td><td>55</td><td>4</td><td>9</td><td>54</td><td>59</td><td>8</td><td>13</td><td>58</td><td>63</td><td>12</td><td>17</td><td>62</td><td>3</td></tr><tr><td>i</td><td>16</td><td>17</td><td>18</td><td>19</td><td>20</td><td>21</td><td>22</td><td>23</td><td>24</td><td>25</td><td>26</td><td>27</td><td>28</td><td>29</td><td>30</td><td>31</td></tr><tr><td>P(i)</td><td>16</td><td>21</td><td>2</td><td>7</td><td>20</td><td>25</td><td>6</td><td>11</td><td>24</td><td>29</td><td>10</td><td>15</td><td>28</td><td>33</td><td>14</td><td>19</td></tr><tr><td>i</td><td>32</td><td>33</td><td>34</td><td>35</td><td>36</td><td>37</td><td>38</td><td>39</td><td>40</td><td>41</td><td>42</td><td>43</td><td>44</td><td>45</td><td>46</td><td>47</td></tr><tr><td>P(i)</td><td>32</td><td>37</td><td>18</td><td>23</td><td>36</td><td>41</td><td>22</td><td>27</td><td>40</td><td>45</td><td>26</td><td>31</td><td>44</td><td>49</td><td>30</td><td>35</td></tr><tr><td>i</td><td>48</td><td>49</td><td>50</td><td>51</td><td>52</td><td>53</td><td>54</td><td>55</td><td>56</td><td>57</td><td>58</td><td>59</td><td>60</td><td>61</td><td>62</td><td>63</td></tr><tr><td>P(i)</td><td>48</td><td>53</td><td>34</td><td>39</td><td>52</td><td>57</td><td>38</td><td>43</td><td>56</td><td>61</td><td>42</td><td>47</td><td>60</td><td>1</td><td>46</td><td>51</td></tr></tbody></table>

<table><caption>**Table 9.** The Difference Distribution Table (DDT) of the RECTANGLE S-box</caption><thead><tr><th></th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>a</th><th>b</th><th>c</th><th>d</th><th>e</th><th>f</th></tr></thead><tbody><tr><td>0</td><td>16</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>1</td><td>0</td><td>0</td><td>0</td><td>2</td><td>0</td><td>0</td><td>4</td><td>2</td><td>0</td><td>0</td><td>0</td><td>2</td><td>0</td><td>0</td><td>4</td><td>2</td></tr><tr><td>2</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>2</td><td>2</td><td>2</td><td>0</td><td>2</td><td>0</td><td>2</td><td>4</td><td>0</td><td>2</td><td>0</td></tr><tr><td>3</td><td>0</td><td>0</td><td>0</td><td>2</td><td>0</td><td>0</td><td>2</td><td>0</td><td>2</td><td>4</td><td>2</td><td>2</td><td>2</td><td>0</td><td>0</td><td>0</td></tr><tr><td>4</td><td>0</td><td>0</td><td>0</td><td>4</td><td>0</td><td>0</td><td>0</td><td>4</td><td>0</td><td>0</td><td>0</td><td>4</td><td>0</td><td>0</td><td>0</td><td>4</td></tr><tr><td>5</td><td>0</td><td>2</td><td>0</td><td>0</td><td>4</td><td>2</td><td>0</td><td>0</td><td>4</td><td>2</td><td>0</td><td>0</td><td>2</td><td>0</td><td>0</td><td>0</td></tr><tr><td>6</td><td>0</td><td>2</td><td>4</td><td>0</td><td>2</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>2</td><td>2</td><td>2</td><td>0</td><td>2</td><td>0</td></tr><tr><td>7</td><td>0</td><td>0</td><td>4</td><td>0</td><td>2</td><td>2</td><td>0</td><td>0</td><td>0</td><td>2</td><td>0</td><td>2</td><td>2</td><td>0</td><td>0</td><td>2</td></tr><tr><td>8</td><td>0</td><td>2</td><td>0</td><td>2</td><td>0</td><td>2</td><td>0</td><td>2</td><td>0</td><td>2</td><td>0</td><td>2</td><td>0</td><td>2</td><td>0</td><td>2</td></tr><tr><td>9</td><td>0</td><td>2</td><td>0</td><td>0</td><td>0</td><td>2</td><td>4</td><td>0</td><td>0</td><td>2</td><td>0</td><td>0</td><td>0</td><td>2</td><td>4</td><td>0</td></tr><tr><td>a</td><td>0</td><td>0</td><td>0</td><td>0</td><td>4</td><td>2</td><td>2</td><td>2</td><td>0</td><td>2</td><td>0</td><td>2</td><td>0</td><td>0</td><td>2</td><td>0</td></tr><tr><td>b</td><td>0</td><td>4</td><td>0</td><td>2</td><td>0</td><td>0</td><td>2</td><td>0</td><td>2</td><td>0</td><td>2</td><td>2</td><td>2</td><td>0</td><td>0</td><td>0</td></tr><tr><td>c</td><td>0</td><td>0</td><td>0</td><td>0</td><td>4</td><td>0</td><td>0</td><td>0</td><td>4</td><td>0</td><td>4</td><td>0</td><td>0</td><td>0</td><td>4</td><td>0</td></tr><tr><td>d</td><td>0</td><td>2</td><td>0</td><td>0</td><td>0</td><td>2</td><td>0</td><td>0</td><td>0</td><td>2</td><td>4</td><td>0</td><td>0</td><td>2</td><td>4</td><td>0</td></tr><tr><td>e</td><td>0</td><td>0</td><td>4</td><td>2</td><td>2</td><td>2</td><td>0</td><td>2</td><td>0</td><td>2</td><td>0</td><td>0</td><td>2</td><td>0</td><td>0</td><td>0</td></tr><tr><td>f</td><td>0</td><td>2</td><td>4</td><td>2</td><td>2</td><td>0</td><td>0</td><td>2</td><td>0</td><td>0</td><td>0</td><td>0</td><td>2</td><td>2</td><td>0</td><td>0</td></tr></tbody></table>

<table><caption>**Table 10.** The S-box of PRESENT</caption><thead><tr><th>x</th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>10</th><th>11</th><th>12</th><th>13</th><th>14</th><th>15</th></tr></thead><tbody><tr><td>S(x)</td><td>12</td><td>5</td><td>6</td><td>11</td><td>9</td><td>0</td><td>10</td><td>13</td><td>3</td><td>14</td><td>15</td><td>8</td><td>4</td><td>7</td><td>1</td><td>2</td></tr></tbody></table>

Key schedule for PRESENT-80. The master key is stored in a register K and is represented as k<sub>79</sub>k<sub>78</sub>...k<sub>0</sub>. At round i, the round key K<sub>i</sub> consists of the 64 leftmost bits of the current content of the register K:

$$K_i = k_{79}k_{78}...k_{16}.$$

Once the round key has been extracted, the register K is updated as follows:
<table><caption>**Table 8.** The bit-permutation of RECTANGLE</caption><thead><tr><th></th><th>i</th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>10</th><th>11</th><th>12</th><th>13</th><th>14</th><th>15</th></tr></thead><tbody><tr><td>P(i)</td><td>0</td><td>5</td><td>50</td><td>55</td><td>4</td><td>9</td><td>54</td><td>59</td><td>8</td><td>13</td><td>58</td><td>63</td><td>12</td><td>17</td><td>62</td><td>3</td></tr><tr><td>i</td><td>16</td><td>17</td><td>18</td><td>19</td><td>20</td><td>21</td><td>22</td><td>23</td><td>24</td><td>25</td><td>26</td><td>27</td><td>28</td><td>29</td><td>30</td><td>31</td></tr><tr><td>P(i)</td><td>16</td><td>21</td><td>2</td><td>7</td><td>20</td><td>25</td><td>6</td><td>11</td><td>24</td><td>29</td><td>10</td><td>15</td><td>28</td><td>33</td><td>14</td><td>19</td></tr><tr><td>i</td><td>32</td><td>33</td><td>34</td><td>35</td><td>36</td><td>37</td><td>38</td><td>39</td><td>40</td><td>41</td><td>42</td><td>43</td><td>44</td><td>45</td><td>46</td><td>47</td></tr><tr><td>P(i)</td><td>32</td><td>37</td><td>18</td><td>23</td><td>36</td><td>41</td><td>22</td><td>27</td><td>40</td><td>45</td><td>26</td><td>31</td><td>44</td><td>49</td><td>30</td><td>35</td></tr><tr><td>i</td><td>48</td><td>49</td><td>50</td><td>51</td><td>52</td><td>53</td><td>54</td><td>55</td><td>56</td><td>57</td><td>58</td><td>59</td><td>60</td><td>61</td><td>62</td><td>63</td></tr><tr><td>P(i)</td><td>48</td><td>53</td><td>34</td><td>39</td><td>52</td><td>57</td><td>38</td><td>43</td><td>56</td><td>61</td><td>42</td><td>47</td><td>60</td><td>1</td><td>46</td><td>51</td></tr></tbody></table>

<table><caption>**Table 9.** The Difference Distribution Table (DDT) of the RECTANGLE S-box</caption><thead><tr><th></th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>a</th><th>b</th><th>c</th><th>d</th><th>e</th><th>f</th></tr></thead><tbody><tr><td>0</td><td>16</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>1</td><td>0</td><td>0</td><td>0</td><td>2</td><td>0</td><td>0</td><td>4</td><td>2</td><td>0</td><td>0</td><td>0</td><td>2</td><td>0</td><td>0</td><td>4</td><td>2</td></tr><tr><td>2</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>2</td><td>2</td><td>2</td><td>0</td><td>2</td><td>0</td><td>2</td><td>4</td><td>0</td><td>2</td></tr><tr><td>3</td><td>0</td><td>0</td><td>0</td><td>2</td><td>0</td><td>0</td><td>2</td><td>0</td><td>2</td><td>4</td><td>2</td><td>2</td><td>2</td><td>0</td><td>0</td><td>0</td></tr><tr><td>4</td><td>0</td><td>0</td><td>0</td><td>4</td><td>0</td><td>0</td><td>0</td><td>4</td><td>0</td><td>0</td><td>0</td><td>4</td><td>0</td><td>0</td><td>0</td><td>4</td></tr><tr><td>5</td><td>0</td><td>2</td><td>0</td><td>0</td><td>4</td><td>2</td><td>0</td><td>0</td><td>4</td><td>2</td><td>0</td><td>0</td><td>2</td><td>0</td><td>0</td><td>0</td></tr><tr><td>6</td><td>0</td><td>2</td><td>4</td><td>0</td><td>2</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>2</td><td>2</td><td>2</td><td>0</td><td>2</td></tr><tr><td>7</td><td>0</td><td>0</td><td>4</td><td>0</td><td>2</td><td>2</td><td>0</td><td>0</td><td>0</td><td>2</td><td>0</td><td>2</td><td>2</td><td>0</td><td>0</td><td>2</td></tr><tr><td>8</td><td>0</td><td>2</td><td>0</td><td>2</td><td>0</td><td>2</td><td>0</td><td>2</td><td>0</td><td>2</td><td>0</td><td>2</td><td>0</td><td>2</td><td>0</td><td>2</td></tr><tr><td>9</td><td>0</td><td>2</td><td>0</td><td>0</td><td>0</td><td>2</td><td>4</td><td>0</td><td>0</td><td>2</td><td>0</td><td>0</td><td>0</td><td>2</td><td>4</td><td>0</td></tr><tr><td>a</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>4</td><td>2</td><td>2</td><td>2</td><td>0</td><td>2</td><td>0</td><td>2</td><td>0</td><td>0</td><td>2</td></tr><tr><td>b</td><td>0</td><td>4</td><td>0</td><td>2</td><td>0</td><td>0</td><td>2</td><td>0</td><td>2</td><td>0</td><td>2</td><td>2</td><td>2</td><td>0</td><td>0</td><td>0</td></tr><tr><td>c</td><td>0</td><td>0</td><td>0</td><td>0</td><td>4</td><td>0</td><td>0</td><td>0</td><td>4</td><td>0</td><td>4</td><td>0</td><td>0</td><td>0</td><td>4</td><td>0</td></tr><tr><td>d</td><td>0</td><td>2</td><td>0</td><td>0</td><td>0</td><td>2</td><td>0</td><td>0</td><td>0</td><td>2</td><td>4</td><td>0</td><td>0</td><td>2</td><td>4</td><td>0</td></tr><tr><td>e</td><td>0</td><td>0</td><td>4</td><td>2</td><td>2</td><td>2</td><td>0</td><td>2</td><td>0</td><td>2</td><td>0</td><td>0</td><td>2</td><td>0</td><td>0</td><td>0</td></tr><tr><td>f</td><td>0</td><td>2</td><td>4</td><td>2</td><td>2</td><td>0</td><td>0</td><td>2</td><td>0</td><td>0</td><td>0</td><td>0</td><td>2</td><td>2</td><td>0</td><td>0</td></tr></tbody></table>

<table><caption>**Table 10.** The S-box of PRESENT</caption><thead><tr><th>x</th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>10</th><th>11</th><th>12</th><th>13</th><th>14</th><th>15</th></tr></thead><tbody><tr><td>S(x)</td><td>12</td><td>5</td><td>6</td><td>11</td><td>9</td><td>0</td><td>10</td><td>13</td><td>3</td><td>14</td><td>15</td><td>8</td><td>4</td><td>7</td><td>1</td><td>2</td></tr></tbody></table>

Key schedule for PRESENT-80. The master key is stored in a register K and is represented as k<sub>79</sub>k<sub>78</sub>...k<sub>0</sub>. At round i, the round key K<sub>i</sub> consists of the 64 leftmost bits of the current content of the register K:

$$K_i = k_{79}k_{78}...k_{16}.$$

Once the round key has been extracted, the register K is updated as follows:
<table><caption>Table 11. The bit-permutation of PRESENT</caption><thead><tr><th>i</th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>10</th><th>11</th><th>12</th><th>13</th><th>14</th><th>15</th></tr></thead><tbody><tr><td>P(i)</td><td>0</td><td>16</td><td>32</td><td>48</td><td>1</td><td>17</td><td>33</td><td>49</td><td>2</td><td>18</td><td>34</td><td>50</td><td>3</td><td>19</td><td>35</td><td>51</td></tr><tr><td>i</td><td>16</td><td>17</td><td>18</td><td>19</td><td>20</td><td>21</td><td>22</td><td>23</td><td>24</td><td>25</td><td>26</td><td>27</td><td>28</td><td>29</td><td>30</td><td>31</td></tr><tr><td>P(i)</td><td>4</td><td>20</td><td>36</td><td>52</td><td>5</td><td>21</td><td>37</td><td>53</td><td>6</td><td>22</td><td>38</td><td>54</td><td>7</td><td>23</td><td>39</td><td>55</td></tr><tr><td>i</td><td>32</td><td>33</td><td>34</td><td>35</td><td>36</td><td>37</td><td>38</td><td>39</td><td>40</td><td>41</td><td>42</td><td>43</td><td>44</td><td>45</td><td>46</td><td>47</td></tr><tr><td>P(i)</td><td>8</td><td>24</td><td>40</td><td>56</td><td>9</td><td>25</td><td>41</td><td>57</td><td>10</td><td>26</td><td>42</td><td>58</td><td>11</td><td>27</td><td>43</td><td>59</td></tr><tr><td>i</td><td>48</td><td>49</td><td>50</td><td>51</td><td>52</td><td>53</td><td>54</td><td>55</td><td>56</td><td>57</td><td>58</td><td>59</td><td>60</td><td>61</td><td>62</td><td>63</td></tr><tr><td>P(i)</td><td>12</td><td>28</td><td>44</td><td>60</td><td>13</td><td>29</td><td>45</td><td>61</td><td>14</td><td>30</td><td>46</td><td>62</td><td>15</td><td>31</td><td>47</td><td>63</td></tr></tbody></table>

<table><caption>Table 12. The Difference Distribution Table (DDT) of the PRESENT S-box</caption><thead><tr><th></th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>a</th><th>b</th><th>c</th><th>d</th><th>e</th><th>f</th></tr></thead><tbody><tr><th>0</th><td>16</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><th>1</th><td>0</td><td>0</td><td>0</td><td>4</td><td>0</td><td>0</td><td>0</td><td>4</td><td>0</td><td>4</td><td>0</td><td>0</td><td>0</td><td>4</td><td>0</td><td>0</td></tr><tr><th>2</th><td>0</td><td>0</td><td>0</td><td>2</td><td>0</td><td>4</td><td>2</td><td>0</td><td>0</td><td>0</td><td>2</td><td>0</td><td>2</td><td>2</td><td>2</td><td>0</td></tr><tr><th>3</th><td>0</td><td>2</td><td>0</td><td>2</td><td>2</td><td>0</td><td>4</td><td>2</td><td>0</td><td>0</td><td>2</td><td>2</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><th>4</th><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>4</td><td>2</td><td>2</td><td>0</td><td>2</td><td>2</td><td>0</td><td>2</td><td>0</td><td>2</td><td>0</td></tr><tr><th>5</th><td>0</td><td>2</td><td>0</td><td>0</td><td>2</td><td>0</td><td>0</td><td>0</td><td>0</td><td>2</td><td>2</td><td>2</td><td>4</td><td>2</td><td>0</td><td>0</td></tr><tr><th>6</th><td>0</td><td>0</td><td>2</td><td>0</td><td>0</td><td>0</td><td>2</td><td>0</td><td>2</td><td>0</td><td>0</td><td>4</td><td>2</td><td>0</td><td>0</td><td>4</td></tr><tr><th>7</th><td>0</td><td>4</td><td>2</td><td>0</td><td>0</td><td>0</td><td>2</td><td>0</td><td>2</td><td>0</td><td>0</td><td>0</td><td>2</td><td>0</td><td>0</td><td>4</td></tr><tr><th>8</th><td>0</td><td>0</td><td>0</td><td>2</td><td>0</td><td>0</td><td>0</td><td>2</td><td>0</td><td>2</td><td>0</td><td>4</td><td>0</td><td>2</td><td>0</td><td>4</td></tr><tr><th>9</th><td>0</td><td>0</td><td>2</td><td>0</td><td>4</td><td>0</td><td>2</td><td>0</td><td>2</td><td>0</td><td>0</td><td>0</td><td>2</td><td>0</td><td>4</td><td>0</td></tr><tr><th>a</th><td>0</td><td>0</td><td>2</td><td>2</td><td>0</td><td>4</td><td>0</td><td>0</td><td>2</td><td>0</td><td>2</td><td>0</td><td>0</td><td>2</td><td>2</td><td>0</td></tr><tr><th>b</th><td>0</td><td>2</td><td>0</td><td>0</td><td>2</td><td>0</td><td>0</td><td>0</td><td>4</td><td>2</td><td>2</td><td>2</td><td>0</td><td>2</td><td>0</td><td>0</td></tr><tr><th>c</th><td>0</td><td>0</td><td>2</td><td>0</td><td>0</td><td>4</td><td>0</td><td>2</td><td>2</td><td>2</td><td>2</td><td>0</td><td>0</td><td>0</td><td>2</td><td>0</td></tr><tr><th>d</th><td>0</td><td>2</td><td>4</td><td>2</td><td>2</td><td>0</td><td>0</td><td>2</td><td>0</td><td>0</td><td>2</td><td>2</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><th>e</th><td>0</td><td>0</td><td>2</td><td>2</td><td>0</td><td>0</td><td>2</td><td>2</td><td>2</td><td>2</td><td>0</td><td>0</td><td>2</td><td>2</td><td>0</td><td>0</td></tr><tr><th>f</th><td>0</td><td>4</td><td>0</td><td>0</td><td>4</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>4</td><td>4</td></tr></tbody></table>

$$ \begin{align*} [k_{79}k_{78}\dots k_{1}k_{0}] &= [k_{18}k_{17}\dots k_{20}k_{19}] \\ [k_{79}k_{78}k_{77}k_{76}] &= S[k_{79}k_{78}k_{77}k_{76}] \\ [k_{19}k_{18}k_{17}k_{16}k_{15}] &= [k_{19}k_{18}k_{17}k_{16}k_{15}] \oplus \text{round\_counter.} \end{align*} $$

We refer the reader to [9] for the description of the key schedule of the 128-bit version.

## E Application to SPEEDY-7-192

SPEEDY-7-192 is a 192-bit cipher, whose state is seen as a (32 × 6)-bit array. The round function consists of the following operations: An AddRoundKey($A_{k_r}$)
<table><caption>Table 11. The bit-permutation of PRESENT</caption><thead><tr><th>i</th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>10</th><th>11</th><th>12</th><th>13</th><th>14</th><th>15</th></tr></thead><tbody><tr><th>P(i)</th><td>0</td><td>16</td><td>32</td><td>48</td><td>1</td><td>17</td><td>33</td><td>49</td><td>2</td><td>18</td><td>34</td><td>50</td><td>3</td><td>19</td><td>35</td><td>51</td></tr><tr><th>i</th><td>16</td><td>17</td><td>18</td><td>19</td><td>20</td><td>21</td><td>22</td><td>23</td><td>24</td><td>25</td><td>26</td><td>27</td><td>28</td><td>29</td><td>30</td><td>31</td></tr><tr><th>P(i)</th><td>4</td><td>20</td><td>36</td><td>52</td><td>5</td><td>21</td><td>37</td><td>53</td><td>6</td><td>22</td><td>38</td><td>54</td><td>7</td><td>23</td><td>39</td><td>55</td></tr><tr><th>i</th><td>32</td><td>33</td><td>34</td><td>35</td><td>36</td><td>37</td><td>38</td><td>39</td><td>40</td><td>41</td><td>42</td><td>43</td><td>44</td><td>45</td><td>46</td><td>47</td></tr><tr><th>P(i)</th><td>8</td><td>24</td><td>40</td><td>56</td><td>9</td><td>25</td><td>41</td><td>57</td><td>10</td><td>26</td><td>42</td><td>58</td><td>11</td><td>27</td><td>43</td><td>59</td></tr><tr><th>i</th><td>48</td><td>49</td><td>50</td><td>51</td><td>52</td><td>53</td><td>54</td><td>55</td><td>56</td><td>57</td><td>58</td><td>59</td><td>60</td><td>61</td><td>62</td><td>63</td></tr><tr><th>P(i)</th><td>12</td><td>28</td><td>44</td><td>60</td><td>13</td><td>29</td><td>45</td><td>61</td><td>14</td><td>30</td><td>46</td><td>62</td><td>15</td><td>31</td><td>47</td><td>63</td></tr></tbody></table>

<table><caption>Table 12. The Difference Distribution Table (DDT) of the PRESENT S-box</caption><thead><tr><th></th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>a</th><th>b</th><th>c</th><th>d</th><th>e</th><th>f</th></tr></thead><tbody><tr><th>0</th><td>16</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><th>1</th><td>0</td><td>0</td><td>0</td><td>4</td><td>0</td><td>0</td><td>0</td><td>4</td><td>0</td><td>4</td><td>0</td><td>0</td><td>0</td><td>4</td><td>0</td><td>0</td></tr><tr><th>2</th><td>0</td><td>0</td><td>0</td><td>2</td><td>0</td><td>4</td><td>2</td><td>0</td><td>0</td><td>0</td><td>2</td><td>0</td><td>2</td><td>2</td><td>2</td><td>0</td></tr><tr><th>3</th><td>0</td><td>2</td><td>0</td><td>2</td><td>2</td><td>0</td><td>4</td><td>2</td><td>0</td><td>0</td><td>2</td><td>2</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><th>4</th><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>4</td><td>2</td><td>2</td><td>0</td><td>2</td><td>2</td><td>0</td><td>2</td><td>0</td><td>2</td><td>0</td></tr><tr><th>5</th><td>0</td><td>2</td><td>0</td><td>0</td><td>2</td><td>0</td><td>0</td><td>0</td><td>0</td><td>2</td><td>2</td><td>2</td><td>4</td><td>2</td><td>0</td><td>0</td></tr><tr><th>6</th><td>0</td><td>0</td><td>2</td><td>0</td><td>0</td><td>0</td><td>2</td><td>0</td><td>2</td><td>0</td><td>0</td><td>4</td><td>2</td><td>0</td><td>0</td><td>4</td></tr><tr><th>7</th><td>0</td><td>4</td><td>2</td><td>0</td><td>0</td><td>0</td><td>2</td><td>0</td><td>2</td><td>0</td><td>0</td><td>0</td><td>2</td><td>0</td><td>0</td><td>4</td></tr><tr><th>8</th><td>0</td><td>0</td><td>0</td><td>2</td><td>0</td><td>0</td><td>0</td><td>2</td><td>0</td><td>2</td><td>0</td><td>4</td><td>0</td><td>2</td><td>0</td><td>4</td></tr><tr><th>9</th><td>0</td><td>0</td><td>2</td><td>0</td><td>4</td><td>0</td><td>2</td><td>0</td><td>2</td><td>0</td><td>0</td><td>0</td><td>2</td><td>0</td><td>4</td><td>0</td></tr><tr><th>a</th><td>0</td><td>0</td><td>2</td><td>2</td><td>0</td><td>4</td><td>0</td><td>0</td><td>2</td><td>0</td><td>2</td><td>0</td><td>0</td><td>2</td><td>2</td><td>0</td></tr><tr><th>b</th><td>0</td><td>2</td><td>0</td><td>0</td><td>2</td><td>0</td><td>0</td><td>0</td><td>4</td><td>2</td><td>2</td><td>2</td><td>0</td><td>2</td><td>0</td><td>0</td></tr><tr><th>c</th><td>0</td><td>0</td><td>2</td><td>0</td><td>0</td><td>4</td><td>0</td><td>2</td><td>2</td><td>2</td><td>2</td><td>0</td><td>0</td><td>0</td><td>2</td><td>0</td></tr><tr><th>d</th><td>0</td><td>2</td><td>4</td><td>2</td><td>2</td><td>0</td><td>0</td><td>2</td><td>0</td><td>0</td><td>2</td><td>2</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><th>e</th><td>0</td><td>0</td><td>2</td><td>2</td><td>0</td><td>0</td><td>2</td><td>2</td><td>2</td><td>2</td><td>0</td><td>0</td><td>2</td><td>2</td><td>0</td><td>0</td></tr><tr><th>f</th><td>0</td><td>4</td><td>0</td><td>0</td><td>4</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>4</td><td>4</td></tr></tbody></table>

$$ \begin{align*} [k_{79}k_{78}\dots k_{1}k_{0}] &= [k_{18}k_{17}\dots k_{20}k_{19}] \\ [k_{79}k_{78}k_{77}k_{76}] &= S[k_{79}k_{78}k_{77}k_{76}] \\ [k_{19}k_{18}k_{17}k_{16}k_{15}] &= [k_{19}k_{18}k_{17}k_{16}k_{15}] \oplus \text{round\_counter}. \end{align*} $$

We refer the reader to [9] for the description of the key schedule of the 128-bit version.

## E Application to SPEEDY-7-192

SPEEDY-7-192 is a 192-bit cipher, whose state is seen as a (32 × 6)-bit array. The round function consists of the following operations: An AddRoundKey($A_{k_r}$)
operation that XORs a subkey $k_r$ to the state. Then, **SubBox**(*SB*) applies a 6-bit
*S-box* to the rows in parallel. Follows the **ShiftColumns**(*SC*) operation that ro-
tates each column of the state by a different offset. The *SB* and the *SC* operation
are repeated twice inside a round. Then, the **MixColumns**(*MC*) operation multi-
plies each column of the state by a binary matrix. We omit here the constant
addition operation (**AC**) that is of no interest to us. For **SPEEDY-7-192** the round
function is iterated 7 times, but in the last round the **SC**, **MC** and **AC** operations
are omitted. The round function of this cipher is depicted in Figure 4.

<figure><img src="image_5.png" /><figcaption>**Fig. 4.** The round function of SPEEDY-7-192 for the first 6 rounds (left) and the last round (right).</figcaption></figure>

Finally, the key schedule is a simple bit-permutation of the 192-bit master
key. This permutation can be found in [24].

**The differential attack of [12]** Recently, an attack on the full version of SPEEDY-7-192 using a differential attack was published [12], even if the validity of the distinguisher used was recently questioned in [3] due to the existence of quasidifferentials cancelling the probability. This attack exploited a 5.5-round differential of probability $2^{-p} = 2^{-183.59}$ that was extended to one round backwards and half a round forwards. The data, time and memory complexities of this attack were $\mathcal{D} = 2^{187.28}$, $\mathcal{T} = 2^{187.84}$ and $2^{42}$ respectively. In particular the complexity of the key recovery was $N \cdot 2^{2.83}$. This attack can be depicted in Figure 5.

The key recovery in [12] was done by hand, requiring a particularly tedious
procedure. We decided to launch our tool on this cipher in order to see if the
key recovery complexity could be improved. This application required some sub-
tleties regarding its implementation. Indeed, in a first approach the round func-
tion could seem to be too sophisticated for our framework since it features two
**SubBox**(SB) layers as well as a **MixColumns**(MC) operation. However we can ob-
serve that the **MC** operation does not appear in the key recovery depicted in
Figure 5, hence we do not need to consider it. Handling the double SB appli-
cation, is also easy. For this, we just need to split the round function into two
parts: $R_1 \circ R_0$ where $R_0 = \text{SC} \circ \text{SB} \circ \text{A}_{k_r}$ and $R_1 = \text{SC} \circ \text{SB} \circ \text{A}_0$ where $A_0$ corresponds
to an artificial XOR with an all-0 round key.
operation that XORs a subkey $k_r$ to the state. Then, **SubBox**(SB) applies a 6-bit S-box to the rows in parallel. Follows the **ShiftColumns**(SC) operation that rotates each column of the state by a different offset. The SB and the SC operation are repeated twice inside a round. Then, the **MixColumns**(MC) operation multiplies each column of the state by a binary matrix. We omit here the constant addition operation (AC) that is of no interest to us. For **SPEEDY-7-192** the round function is iterated 7 times, but in the last round the SC, MC and AC operations are omitted. The round function of this cipher is depicted in Figure 4.

<figure><img src="image_5.png" /><figcaption>Fig. 4. The round function of SPEEDY-7-192 for the first 6 rounds (left) and the last round (right).</figcaption></figure>

Finally, the key schedule is a simple bit-permutation of the 192-bit master key. This permutation can be found in [24].

**The differential attack of [12]** Recently, an attack on the full version of SPEEDY-7-192 using a differential attack was published [12], even if the validity of the distinguisher used was recently questioned in [3] due to the existence of quasidifferentials cancelling the probability. This attack exploited a 5.5-round differential of probability $2^{-p} = 2^{-183.59}$ that was extended to one round backwards and half a round forwards. The data, time and memory complexities of this attack were $D = 2^{187.28}$, $T = 2^{187.84}$ and $2^{42}$ respectively. In particular the complexity of the key recovery was $N \cdot 2^{2.83}$. This attack can be depicted in Figure 5.

The key recovery in [12] was done by hand, requiring a particularly tedious procedure. We decided to launch our tool on this cipher in order to see if the key recovery complexity could be improved. This application required some subtleties regarding its implementation. Indeed, in a first approach the round function could seem to be too sophisticated for our framework since it features two **SubBox**(SB) layers as well as a **MixColumns**(MC) operation. However we can observe that the MC operation does not appear in the key recovery depicted in Figure 5, hence we do not need to consider it. Handling the double SB application, is also easy. For this, we just need to split the round function into two parts: $R_1 \circ R_0$ where $R_0 = SC \circ SB \circ A_{k_r}$ and $R_1 = SC \circ SB \circ A_0$ where $A_0$ corresponds to an artificial XOR with an all-0 round key.
<figure><img src="image_6.png" /><figcaption>Fig. 5. The differential attack of [12] on full SPEEDY-7-192. Blue cells correspond to active bits and grey cells to bits with an unknown difference. Finally the pink part of the state corresponds to rows among which only 3 will be active in an attack scenario.</figcaption></figure>

**Application of our tool to the differential of [12]** We applied our tool to SPEEDY-7-192 by keeping the exact attack parameters as in [12]. The key recovery rounds depicted in Figure 5 feature patterns (represented in pink) that allowed a complexity tradeoff in the first steps of the attack. However, this pink part could not be used in the original attack, as it would have implied to propose a key recovery for each different pattern. This would have meant a huge amount of work given the tedious procedure, and the authors preferred to propose a method for recovering first the key of the other rounds, and at the end the one associated to the pink part in a cheap step that did not need to be detailed. In order to fairly compare our results, we have not considered the pink part either. Hence we implemented our tool with the pink part as inactive and not allowing to filter. Our tool outputted a complexity for the key recovery phase equal to N improving thus by a factor of $2^{2.83}$ the complexity of the key recovery attack given in [12]. As this was not the bottleneck of the attack, the factor of improvement is small $2^{0.5}$, but this application shows how our tool can solve complex procedures automatically and even provides better results that the previous procedures.

## F Specifications and differential properties of GIFT-64

We give the specifications of the S-box (Table 13) and of the bit-permutation (Table 14) used in GIFT-64. We also provide the Difference Distribution Table (DDT) of the S-box in Table 15. Finally, we describe the GIFT-64 key schedule.

*The key schedule of GIFT-64.* The 128-bit master key can be seen as eight 16-bit words stored in a register $K = k_7 \parallel k_6 \cdots \parallel k_1 \parallel k_0$. At each iteration, first the 32-bit round key is extracted:

$$k_r = k_1 \parallel k_0,$$
<figure><img src="image_6.png" /><figcaption>Fig. 5. The differential attack of [12] on full SPEEDY-7-192. Blue cells correspond to active bits and grey cells to bits with an unknown difference. Finally the pink part of the state corresponds to rows among which only 3 will be active in an attack scenario.</figcaption></figure>

**Application of our tool to the differential of [12]** We applied our tool to SPEEDY-7-192 by keeping the exact attack parameters as in [12]. The key recovery rounds depicted in Figure 5 feature patterns (represented in pink) that allowed a complexity tradeoff in the first steps of the attack. However, this pink part could not be used in the original attack, as it would have implied to propose a key recovery for each different pattern. This would have meant a huge amount of work given the tedious procedure, and the authors preferred to propose a method for recovering first the key of the other rounds, and at the end the one associated to the pink part in a cheap step that did not need to be detailed. In order to fairly compare our results, we have not considered the pink part either. Hence we implemented our tool with the pink part as inactive and not allowing to filter. Our tool outputted a complexity for the key recovery phase equal to N improving thus by a factor of $2^{2.83}$ the complexity of the key recovery attack given in [12]. As this was not the bottleneck of the attack, the factor of improvement is small $2^{0.5}$, but this application shows how our tool can solve complex procedures automatically and even provides better results that the previous procedures.

# F Specifications and differential properties of GIFT-64

We give the specifications of the S-box (Table 13) and of the bit-permutation (Table 14) used in GIFT-64. We also provide the Difference Distribution Table (DDT) of the S-box in Table 15. Finally, we describe the GIFT-64 key schedule.

The key schedule of GIFT-64. The 128-bit master key can be seen as eight 16-bit words stored in a register $K = k_7 \parallel k_6 \cdots \parallel k_1 \parallel k_0$. At each iteration, first the 32-bit round key is extracted:

$$k_r = k_1 \parallel k_0,$$
<table><caption>**Table 13.** The S-box of GIFT</caption><thead><tr><th>x</th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>10</th><th>11</th><th>12</th><th>13</th><th>14</th><th>15</th></tr></thead><tbody><tr><th>S(x)</th><td>1</td><td>10</td><td>4</td><td>12</td><td>6</td><td>15</td><td>3</td><td>9</td><td>2</td><td>13</td><td>11</td><td>7</td><td>5</td><td>0</td><td>8</td><td>14</td></tr></tbody></table>

<table><caption>**Table 14.** The bit-permutation of GIFT-64</caption><thead><tr><th>i</th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>10</th><th>11</th><th>12</th><th>13</th><th>14</th><th>15</th></tr></thead><tbody><tr><th>P(i)</th><td>0</td><td>17</td><td>34</td><td>51</td><td>48</td><td>1</td><td>18</td><td>35</td><td>32</td><td>49</td><td>2</td><td>19</td><td>16</td><td>33</td><td>50</td><td>3</td></tr><tr><th>i</th><td>16</td><td>17</td><td>18</td><td>19</td><td>20</td><td>21</td><td>22</td><td>23</td><td>24</td><td>25</td><td>26</td><td>27</td><td>28</td><td>29</td><td>30</td><td>31</td></tr><tr><th>P(i)</th><td>4</td><td>21</td><td>38</td><td>55</td><td>52</td><td>5</td><td>22</td><td>39</td><td>36</td><td>53</td><td>6</td><td>23</td><td>20</td><td>37</td><td>54</td><td>7</td></tr><tr><th>i</th><td>32</td><td>33</td><td>34</td><td>35</td><td>36</td><td>37</td><td>38</td><td>39</td><td>40</td><td>41</td><td>42</td><td>43</td><td>44</td><td>45</td><td>46</td><td>47</td></tr><tr><th>P(i)</th><td>8</td><td>25</td><td>42</td><td>59</td><td>56</td><td>9</td><td>26</td><td>43</td><td>40</td><td>57</td><td>10</td><td>27</td><td>24</td><td>41</td><td>58</td><td>11</td></tr><tr><th>i</th><td>48</td><td>49</td><td>50</td><td>51</td><td>52</td><td>53</td><td>54</td><td>55</td><td>56</td><td>57</td><td>58</td><td>59</td><td>60</td><td>61</td><td>62</td><td>63</td></tr><tr><th>P(i)</th><td>12</td><td>29</td><td>46</td><td>63</td><td>60</td><td>13</td><td>30</td><td>47</td><td>44</td><td>61</td><td>14</td><td>31</td><td>28</td><td>45</td><td>62</td><td>15</td></tr></tbody></table>

<table><caption>**Table 15.** The Difference Distribution Table (DDT) of the GIFT S-box</caption><thead><tr><th></th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>a</th><th>b</th><th>c</th><th>d</th><th>e</th><th>f</th></tr></thead><tbody><tr><th>0</th><td>16</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><th>1</th><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>2</td><td>2</td><td>0</td><td>2</td><td>2</td><td>2</td><td>2</td><td>0</td><td>0</td><td>2</td><td>0</td></tr><tr><th>2</th><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>4</td><td>4</td><td>0</td><td>0</td><td>2</td><td>2</td><td>0</td><td>0</td><td>2</td><td>2</td><td>0</td></tr><tr><th>3</th><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>2</td><td>2</td><td>0</td><td>2</td><td>0</td><td>0</td><td>2</td><td>2</td><td>2</td><td>2</td><td>2</td></tr><tr><th>4</th><td>0</td><td>0</td><td>0</td><td>2</td><td>0</td><td>4</td><td>0</td><td>6</td><td>0</td><td>2</td><td>0</td><td>0</td><td>0</td><td>2</td><td>0</td><td>0</td></tr><tr><th>5</th><td>0</td><td>0</td><td>2</td><td>0</td><td>0</td><td>2</td><td>0</td><td>0</td><td>2</td><td>0</td><td>0</td><td>0</td><td>2</td><td>2</td><td>2</td><td>4</td></tr><tr><th>6</th><td>0</td><td>0</td><td>4</td><td>6</td><td>0</td><td>0</td><td>0</td><td>2</td><td>0</td><td>0</td><td>2</td><td>0</td><td>0</td><td>0</td><td>2</td><td>0</td></tr><tr><th>7</th><td>0</td><td>0</td><td>2</td><td>0</td><td>0</td><td>2</td><td>0</td><td>0</td><td>2</td><td>2</td><td>2</td><td>4</td><td>2</td><td>0</td><td>0</td><td>0</td></tr><tr><th>8</th><td>0</td><td>0</td><td>0</td><td>4</td><td>0</td><td>0</td><td>0</td><td>4</td><td>0</td><td>0</td><td>0</td><td>4</td><td>0</td><td>0</td><td>0</td><td>4</td></tr><tr><th>9</th><td>0</td><td>2</td><td>0</td><td>2</td><td>0</td><td>0</td><td>2</td><td>2</td><td>2</td><td>0</td><td>2</td><td>0</td><td>2</td><td>2</td><td>0</td><td>0</td></tr><tr><th>a</th><td>0</td><td>4</td><td>0</td><td>0</td><td>0</td><td>4</td><td>0</td><td>0</td><td>2</td><td>2</td><td>0</td><td>0</td><td>2</td><td>2</td><td>0</td><td>0</td></tr><tr><th>b</th><td>0</td><td>2</td><td>0</td><td>2</td><td>0</td><td>0</td><td>2</td><td>2</td><td>2</td><td>2</td><td>0</td><td>0</td><td>2</td><td>0</td><td>2</td><td>0</td></tr><tr><th>c</th><td>0</td><td>0</td><td>4</td><td>0</td><td>4</td><td>0</td><td>0</td><td>0</td><td>2</td><td>0</td><td>2</td><td>0</td><td>2</td><td>0</td><td>2</td><td>0</td></tr><tr><th>d</th><td>0</td><td>2</td><td>2</td><td>0</td><td>4</td><td>0</td><td>0</td><td>0</td><td>0</td><td>2</td><td>2</td><td>0</td><td>2</td><td>0</td><td>2</td><td>0</td></tr><tr><th>e</th><td>0</td><td>4</td><td>0</td><td>0</td><td>4</td><td>0</td><td>0</td><td>0</td><td>2</td><td>2</td><td>0</td><td>0</td><td>2</td><td>2</td><td>0</td><td>0</td></tr><tr><th>f</th><td>0</td><td>2</td><td>2</td><td>0</td><td>4</td><td>0</td><td>0</td><td>0</td><td>0</td><td>2</td><td>0</td><td>2</td><td>0</td><td>0</td><td>2</td><td>2</td></tr></tbody></table>

then the register *K* is updated:

$$k_7 \parallel k_6 \cdots \parallel k_1 \parallel k_0 \leftarrow k_1 \gg 2 \parallel k_0 \gg 12 \cdots \parallel k_3 \parallel k_2.$$
<table><caption>**Table 13.** The S-box of GIFT</caption><thead><tr><th>x</th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>10</th><th>11</th><th>12</th><th>13</th><th>14</th><th>15</th></tr></thead><tbody><tr><th>S(x)</th><td>1</td><td>10</td><td>4</td><td>12</td><td>6</td><td>15</td><td>3</td><td>9</td><td>2</td><td>13</td><td>11</td><td>7</td><td>5</td><td>0</td><td>8</td><td>14</td></tr></tbody></table>

<table><caption>**Table 14.** The bit-permutation of GIFT-64</caption><thead><tr><th>i</th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>10</th><th>11</th><th>12</th><th>13</th><th>14</th><th>15</th></tr></thead><tbody><tr><th>P(i)</th><td>0</td><td>17</td><td>34</td><td>51</td><td>48</td><td>1</td><td>18</td><td>35</td><td>32</td><td>49</td><td>2</td><td>19</td><td>16</td><td>33</td><td>50</td><td>3</td></tr><tr><th>i</th><td>16</td><td>17</td><td>18</td><td>19</td><td>20</td><td>21</td><td>22</td><td>23</td><td>24</td><td>25</td><td>26</td><td>27</td><td>28</td><td>29</td><td>30</td><td>31</td></tr><tr><th>P(i)</th><td>4</td><td>21</td><td>38</td><td>55</td><td>52</td><td>5</td><td>22</td><td>39</td><td>36</td><td>53</td><td>6</td><td>23</td><td>20</td><td>37</td><td>54</td><td>7</td></tr><tr><th>i</th><td>32</td><td>33</td><td>34</td><td>35</td><td>36</td><td>37</td><td>38</td><td>39</td><td>40</td><td>41</td><td>42</td><td>43</td><td>44</td><td>45</td><td>46</td><td>47</td></tr><tr><th>P(i)</th><td>8</td><td>25</td><td>42</td><td>59</td><td>56</td><td>9</td><td>26</td><td>43</td><td>40</td><td>57</td><td>10</td><td>27</td><td>24</td><td>41</td><td>58</td><td>11</td></tr><tr><th>i</th><td>48</td><td>49</td><td>50</td><td>51</td><td>52</td><td>53</td><td>54</td><td>55</td><td>56</td><td>57</td><td>58</td><td>59</td><td>60</td><td>61</td><td>62</td><td>63</td></tr><tr><th>P(i)</th><td>12</td><td>29</td><td>46</td><td>63</td><td>60</td><td>13</td><td>30</td><td>47</td><td>44</td><td>61</td><td>14</td><td>31</td><td>28</td><td>45</td><td>62</td><td>15</td></tr></tbody></table>

<table><caption>**Table 15.** The Difference Distribution Table (DDT) of the GIFT S-box</caption><thead><tr><th></th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>a</th><th>b</th><th>c</th><th>d</th><th>e</th><th>f</th></tr></thead><tbody><tr><th>0</th><td>16</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><th>1</th><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>2</td><td>2</td><td>0</td><td>2</td><td>2</td><td>2</td><td>2</td><td>0</td><td>0</td><td>2</td><td>0</td></tr><tr><th>2</th><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>4</td><td>4</td><td>0</td><td>0</td><td>2</td><td>2</td><td>0</td><td>0</td><td>2</td><td>2</td><td>0</td></tr><tr><th>3</th><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>2</td><td>2</td><td>0</td><td>2</td><td>0</td><td>0</td><td>2</td><td>2</td><td>2</td><td>2</td><td>2</td></tr><tr><th>4</th><td>0</td><td>0</td><td>0</td><td>2</td><td>0</td><td>4</td><td>0</td><td>6</td><td>0</td><td>2</td><td>0</td><td>0</td><td>0</td><td>2</td><td>0</td><td>0</td></tr><tr><th>5</th><td>0</td><td>0</td><td>2</td><td>0</td><td>0</td><td>2</td><td>0</td><td>0</td><td>2</td><td>0</td><td>0</td><td>0</td><td>2</td><td>2</td><td>2</td><td>4</td></tr><tr><th>6</th><td>0</td><td>0</td><td>4</td><td>6</td><td>0</td><td>0</td><td>0</td><td>2</td><td>0</td><td>0</td><td>2</td><td>0</td><td>0</td><td>0</td><td>2</td><td>0</td></tr><tr><th>7</th><td>0</td><td>0</td><td>2</td><td>0</td><td>0</td><td>2</td><td>0</td><td>0</td><td>2</td><td>2</td><td>2</td><td>4</td><td>2</td><td>0</td><td>0</td><td>0</td></tr><tr><th>8</th><td>0</td><td>0</td><td>0</td><td>4</td><td>0</td><td>0</td><td>0</td><td>4</td><td>0</td><td>0</td><td>0</td><td>4</td><td>0</td><td>0</td><td>0</td><td>4</td></tr><tr><th>9</th><td>0</td><td>2</td><td>0</td><td>2</td><td>0</td><td>0</td><td>2</td><td>2</td><td>2</td><td>0</td><td>2</td><td>0</td><td>2</td><td>2</td><td>0</td><td>0</td></tr><tr><th>a</th><td>0</td><td>4</td><td>0</td><td>0</td><td>0</td><td>4</td><td>0</td><td>0</td><td>2</td><td>2</td><td>0</td><td>0</td><td>2</td><td>2</td><td>0</td><td>0</td></tr><tr><th>b</th><td>0</td><td>2</td><td>0</td><td>2</td><td>0</td><td>0</td><td>2</td><td>2</td><td>2</td><td>2</td><td>0</td><td>0</td><td>2</td><td>0</td><td>2</td><td>0</td></tr><tr><th>c</th><td>0</td><td>0</td><td>4</td><td>0</td><td>4</td><td>0</td><td>0</td><td>0</td><td>2</td><td>0</td><td>2</td><td>0</td><td>2</td><td>0</td><td>2</td><td>0</td></tr><tr><th>d</th><td>0</td><td>2</td><td>2</td><td>0</td><td>4</td><td>0</td><td>0</td><td>0</td><td>0</td><td>2</td><td>2</td><td>0</td><td>2</td><td>0</td><td>2</td><td>0</td></tr><tr><th>e</th><td>0</td><td>4</td><td>0</td><td>0</td><td>4</td><td>0</td><td>0</td><td>0</td><td>2</td><td>2</td><td>0</td><td>0</td><td>2</td><td>2</td><td>0</td><td>0</td></tr><tr><th>f</th><td>0</td><td>2</td><td>2</td><td>0</td><td>4</td><td>0</td><td>0</td><td>0</td><td>0</td><td>2</td><td>0</td><td>2</td><td>0</td><td>0</td><td>2</td><td>2</td></tr></tbody></table>

then the register *K* is updated:

$$k_7 \parallel k_6 \cdots \parallel k_1 \parallel k_0 \leftarrow k_1 \gg 2 \parallel k_0 \gg 12 \cdots \parallel k_3 \parallel k_2.$$