Geodesic
Constructing algebraic attacks on lightweight symmetric ciphers using functions with small number of output bits
Prikladnaya Diskretnaya Matematika. Supplement, no. 17 (2024), pp. 57-63.

Voir la notice de l'article provenant de la source Math-Net.Ru

We propose a new class of algebraic attacks on lightweight cryptographic functions. The main idea is based on the use of special functions that produce significantly fewer output bits than the original functions specified by the ciphers under consideration (hereafter referred to as standard functions). Examples of similar functions can be found in the so-called cube attacks. The inversion of such special functions is much simpler compared to the inversion of standard ones, but the image of a special function has more than one preimage. To achieve uniqueness, a cloning procedure is proposed: several special functions are constructed for different fragments of the plaintext and a common secret key, and then they are combined into a new function for which the inversion problem has a unique solution. The cloning is performed using the And-Inverter Graphs (AIGs) representing the considered special functions. In addition, we use the well-known AIG minimization algorithms to reduce the size of the resulting representations. The combined application of the mentioned techniques made it possible to construct new algebraic attacks which turned out to be more efficient compared to standard SAT-based attacks for some well-known lightweight stream ciphers with truncated initialization phase.
Mots-clés : algebraic cryptanalysis
Keywords: lightweight cryptography, SAT solvers, Boolean schemes. 
@article{PDMA_2024_17_a13,
     author = {K. V. Antonov and A. A. Semenov and I. V. Otpushchennikov and A. L. Pavlenko},
     title = {Constructing algebraic attacks on lightweight symmetric ciphers using functions with small number of output bits},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {57--63},
     publisher = {mathdoc},
     number = {17},
     year = {2024},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2024_17_a13/}
}
TY  - JOUR
AU  - K. V. Antonov
AU  - A. A. Semenov
AU  - I. V. Otpushchennikov
AU  - A. L. Pavlenko
TI  - Constructing algebraic attacks on lightweight symmetric ciphers using functions with small number of output bits
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2024
SP  - 57
EP  - 63
IS  - 17
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2024_17_a13/
LA  - ru
ID  - PDMA_2024_17_a13
ER  - 
%0 Journal Article
%A K. V. Antonov
%A A. A. Semenov
%A I. V. Otpushchennikov
%A A. L. Pavlenko
%T Constructing algebraic attacks on lightweight symmetric ciphers using functions with small number of output bits
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2024
%P 57-63
%N 17
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2024_17_a13/
%G ru
%F PDMA_2024_17_a13
K. V. Antonov; A. A. Semenov; I. V. Otpushchennikov; A. L. Pavlenko. Constructing algebraic attacks on lightweight symmetric ciphers using functions with small number of output bits. Prikladnaya Diskretnaya Matematika. Supplement, no. 17 (2024), pp. 57-63. http://geodesic.mathdoc.fr/item/PDMA_2024_17_a13/

[1] Fischer S., Khazaei S., Meier W., “Chosen IV statistical analysis for key recovery attacks on stream ciphers”, LNCS, 5023, 2008, 236–245 | MR | Zbl

[2] Dinur I., Shamir A., “Cube attacks on tweakable black box polynomials”, LNCS, 5479, 2009, 278–299 | MR | Zbl

[3] De Canniere C., “Trivium: a stream cipher construction inspired by block cipher design principles”, LNCS, 4176, 2006, 171–186 | Zbl

[4] Bard G., Algebraic Cryptanalysis, Springer, 2009 | MR | Zbl

[5] Semenov A., Zaikin O., Otpuschennikov I., et al., “On cryptographic attacks using backdoors for SAT”, Proc. AAAI (Palo Alto, USA), 2018, 6641–6648

[6] Otpuschennikov I., Semenov A., Gribanova I., et al., “Encoding cryptographic functions to SAT using Transalg system”, Proc. ECAI (Hague, Netherlands), 2016, 1594–1595

[7] Semenov A., Otpuschennikov I., Gribanova I., et al., “Translation of algorithmic descriptions of discrete functions to SAT with applications to cryptanalysis problems”, Logical Methods Computer Sci., 16:1 (2020), 29:1–29:42 | MR | Zbl

[8] Tseitin G. S., “O slozhnosti vyvoda v ischislenii vyskazyvanii”, Zapiski nauchnykh seminarov LOMI, 8, 1968, 234–259 | MR

[9] Yablonskii S. V., Vvedenie v diskretnuyu matematiku, Nauka, M., 1986 | MR

[10] Chen Ch., Li R., Matematicheskaya logika i avtomaticheskoe dokazatelstvo teorem, Nauka, M., 1983

[11] Williams R., Gomes C., Selman B., “Backdoors to typical case complexity”, Proc. IJCAI'03 (Acapulco, Mexico), 2003, 1173–1178

[12] Bryton R., Mishchenko A., “ABC: An academic industrial-strength verification tool”, LNCS, 6174, 2010, 24–40 | MR

[13] Kuehlmann A. Paruthi V., Krohm F., Ganai M., “Robust Boolean reasoning for equivalence checking and functional property verification”, IEEE Trans. Computer-Aided Des. Integr. Circuits Systems, 21:12 (2002), 1377–1394 | DOI

[14] Hell M., Johansson T., Meier W., “Grain: a stream cipher for constrained environments”, Intern. J. Wireless Mobile Computing, 2:1 (2007), 86–93 | DOI

[15] Beaulieu R., Shors D., Smith J., et al., “The Simon and Speck lightweight block ciphers”, 52nd Ann. Design Automation Conf. (San Francisco, USA), 2015, 175:1–175:6

[16] Semenov A., Antonov K., Otpuschennikov I., Pavlenko A., “Using linearizing sets to solve multivariate quadratic equations in algebraic cryptanalysis”, IEEE Access, 11 (2023), 120319–120333 | DOI

[17] Biere A., Fazekas K., Fleury M., and Heisinger M., “CaDiCaL, Kissat, Paracooba, Plingeling and Treengeling entering the SAT Competition 2020”, Proc. SAT Competition (Helsinki), 2020, 50–53

[18] Irkutskii superkompyuternyi tsentr, https://hpc.icc.ru/hardware/index.html