Rad HAZU, Matematičke znanosti, Vol. 25 (2021), 33-49.

A NEW REPRESENTATION OF S-BOXES FOR ALGEBRAIC DIFFERENTIAL CRYPTANALYSIS

Alena Bednáriková and Pavol Zajac

Abstract.   Algebraic cryptanalysis can be used to break (small versions of) block ciphers with small data complexity. If we have access to a large number of P-C pairs, algebraic cryptanalysis can be combined with differential techniques. Differential characteristic produces extra linear equations, which can be used to augment the original algebraic system. In our experiments with algebraic differential cryptanalysis, we have developed a different technique to represent the system. In our new method, we model a single P-C pair based encryption, but we use the differential to restrict the equations that model active S-boxes. An algebraic system created with our new model is smaller, and can theoretically be solved faster. Our experiments show that the advantage depends on the overall number of P-C pairs available and whether the chosen differential characteristic is correctly estimated. One of the advantages of the new method is that it can use partial information from the differential and still determine a correct solution faster than both the standard algebraic attack and the standard algebraic-differential attack.

2020 Mathematics Subject Classification.   94A60, 14G50.

Key words and phrases.   Algebraic differential cryptanalysis, S-boxes.

DOI: https://doi.org/10.21857/yvjrdcl0ey

References:

1. M. Albrecht and C. Cid, Algebraic techniques in differential cryptanalysis, in: International Workshop on Fast Software Encryption, Lecture Notes in Comput. Sci. 5665, Springer, Berlin, 2009, pp. 193-208.
   CrossRef

2. M. Andrzejczak and W. Dudzic, SAT attacks on ARX ciphers with automated equations generation, Infocommunications 9(4) (2019), 2-7.
   CrossRef

3. N. T. Courtois and G. V. Bard, Algebraic cryptanalysis of the data encryption standard, in: Cryptography and coding, Lecture Notes in Comput. Sci. 4887, Springer, Berlin, 2007, pp. 152-169.
   MathSciNet     CrossRef

4. N. T. Courtois and J. Pieprzyk, Cryptanalysis of block ciphers with overdefined systems of equations, in: Advances in Cryptology - ASIACRYPT 2002, Lecture Notes in Comput. Sci. 2501, Springer, Berlin, pp. 267-287.
   MathSciNet     CrossRef

5. J.-C. Faugère, L. Perret and P.-J. Spaenlehauer, Algebraic-differential cryptanalysis of DES, in: Western European Workshop on Research in Cryptology-WEWoRC, Graz, 2009, pp. 1-5.

6. H. M. Heys, A tutorial on linear and differential cryptanalysis, Cryptologia 26 (2002), 189-221.
   CrossRef

7. V. Hromada, L. Öllös and P. Zajac, Using SAT solvers in large scale distributed algebraic attacks against low entropy keys, Tatra Mt. Math. Publ. 64 (2015), 187-203.
   MathSciNet     CrossRef

8. M. Soos, K. Nohl and C. Castelluccia, Extending SAT solvers to cryptographic problems, in: Theory and Applications of Satisfiability Testing - SAT 2009, Lecture Notes in Comput. Sci. 5584, Springer, Berlin, 2009, pp. 244-257.
   MathSciNet     CrossRef

9. The Sage Developers, SageMath, the Sage Mathematics Software System (Version 9.0), 2020, https://www.sagemath.org.

10. M. Wang, Y. Sun, N. Mouha and B. Preneel, Algebraic techniques in differential cryptanalysis revisited, in: Australasian Conference on Information Security and Privacy, Lecture Notes in Comput. Sci. 6812, Springer, Berlin, 2011, pp. 120-141.
    CrossRef