Authors S.V. Polikarpov, K.E. Rumyantsev, A.A. Kozhevnikov
Month, Year 05, 2015 @en
Index UDC 004.853
Abstract One of effective ways of neutralization of the whole layer of methods of cryptanalysis of block cryptoalgorithms is application of dynamically changing substitutions. Approach on the basis of pseudo-dynamic substitutions (PD-sbox) allows to combine strengths of the fixed substitutions (high speed of work and efficiency of use of computing resources) and dynamic substitutions (neutralization of statistical methods of cryptanalysis). The purpose of research – to develop a technique of determination of linear properties of pseudo-dynamic substitutions for further confirmation of their target application in block cryptoalgorithms. In the work expressions for determination of linear properties of pseudo-dynamic substitutions (PD-sbox) for two cases are obtained: 1) when values of a condition of S are fixed and are set by a cryptographic key; 2) when values of a condition of S dynamically change under the influence of entropy of entrance information and results of the previous transformations. Primary analysis of expression allowed to draw conclusions, fair for a case of the fixed values of a condition of S: 1) at real application of PD-sbox with parameters of bits and complexity of a problem of obtaining a full matrix of values can exceed complexity of full search of keys of cryptoalgorithm; 2) the complexity of a set of the demanded statistics for determination of values of a condition of S at linear cryptanalysis as the quantity of the entrance combinations given on PD-sbox input is limited to dimension of an input of X and makes against possible conditions of S; 3) partial or complete masking of a contribution of input values X in values matrixes at its calculation. The offered method of calculation of linear properties allows to estimate linear properties of all ensemble of the generated substitutions. This favourably distinguishes this work from most of work on the application of key-depended substitutions and dynamic substitutions in cryptographic algorithms.

Download PDF

Keywords Linear cryptanalysis; dynamic substitution; pseudo-dynamic substitution PD-sbox.
References 1. Preneel B., Biryukov A., C. De Canniere et al. Final report of European project number IST-1999-12324, named New European Schemes for Signatures, Integrity, and Encryption, Berlin Heidelberg NewYork London Paris Tokyo Hong Kong Barcelona Budapest: Springer-Verlag, 2004.
2. Matsui Mitsuru. Linear Cryptoanalysis Method for DES Cipher, Advances in Cryptology - EUROCRYPT ’93, Workshop on the Theory and Application of of Cryptographic Techniques, Lofthus, Norway, May 23-27, 1993. Proceedings, 1993, pp. 386-397. Available at:
3. Biham Eli, Shamir Adi. Differential Cryptanalysis of DES-like Cryptosystems, J. Cryptology, 1991, Vol. 4, No. 1, pp. 3-72. Available at:
4. Dolgov V.I., Kuznetsov A.A., Isaev S.A. Differentsial'nye svoystva blochnykh simmetrichnykh shifrov [Differential properties of block symmetric ciphers], Elektronnoe modelirovanie [Electronic Modeling], 2011, Vol. 33, No. 6, pp. 81-99.
5. Gorbenko I.D., Dolgov V.I., Lisitskaya I.V., Oleynikov R.V. Novaya ideologiya otsenki stoykosti blochnykh simmetrichnykh shifrov k atakam differentsial'nogo i lineynogo kriptoanaliza [A new ideology to assess the persistence of block symmetric ciphers to attacks, differential and linear cryptanalysis], Prikladnaya radioelektronika [Applied Radio Electronics], 2010, Vol. 9, No. 3, pp. 312-320.
6. Kazymyrov O., Oliynykov R. Application of vectorial Boolean functions for substitutions generation used in symmetric cryptographic transformation, In Systems of information processing, 2012, Vol. 6, No. 104, pp. 97-102.
7. Logachev O.A., Sal'nikov A.A., Yashchenko V.V. Bulevy funktsii v teorii kodirovaniya i kriptologii [Boolean functions in coding theory and cryptology]. Moscow: Moskovskiy tsentr nepreryvnogo matematicheskogo obrazovaniya, 2004, 470 p.
8. GOST 28147-89. Sistemy obrabotki informatsii. Zashchita kriptograficheskaya. Algoritm kriptograficheskogo preobrazovaniya [State Standard 28147-89]. IPK Izdatel'stvo standartov, 1996, 28 p. Available at:
9. Standards Federal Information Processing. Advanced Encryption Standard (AES). Publication 197, November 26 – 2001.
10. Ivanov Georgi, Nikolov Nikolay, Nikova Svetla. Reversed Genetic Algorithms for Generation of Bijective S-boxes with Good Cryptographic Properties, IACR Cryptology ePrint Archive, 2014, Vol. 2014, pp. 801. Available at:
11. Beelen Peter, Leander Gregor. A new construction of highly nonlinear S-boxes, Cryptography and Communications, 2012, Vol. 4, No. 1, pp. 65-77. Available at: 10.1007/s12095-011-0052-4.
12. Kazymyrov Oleksandr, Kazymyrova Valentyna, Oliynykov Roman. A Method For Generation Of High-Nonlinear S-Boxes Based On Gradient Descent, IACR Cryptology ePrint Archive, 2013, Vol. 2013, pp. 578. Available at:
13. Tokareva N.N. Generalizations of bent functions. A survey, Diskretn. Anal. Issled. Oper, 2010, Vol. 17, No. 1, pp. 34-64.
14. Ahmad Musheer, Khan Parvez Mahmood, Ansari Mohd. Zeeshan. A Simple and Efficient Key-Dependent S-Box Design Using Fisher-Yates Shuffle Technique, Recent Trends in Computer Networks and Distributed Systems Security - Second International Conference, SNDS 2014, Trivandrum, India, March 13-14, 2014, Proceedings, 2014, pp. 540-550. Available at:
15. Pradeep L.N. Bhattacharjya Aniruddha. Random Key and Key Dependent S-box Generation for AES Cipher to Overcome Known Attacks, Security in Computing and Communications - International Symposium, SSCC 2013, Mysore, India, August 22-24, 2013. Proceedings, 2013, pp. 63-69. Available at:
16. Hosseinkhani Razi, Haj H., Javadi Seyyed et al. Using Cipher Key to Generate Dynamic S-Box in AES Cipher System, 2012.
17. Schneier Bruce. Description of a New Variable-Length Key, 64-bit Block Cipher (Blowfish), Fast Software Encryption, Cambridge Security Workshop. London, UK, UK: Springer-Verlag, 1994, pp. 191-204. Available at:
18. Kuznetsov A.A., Sergienko R.V., Nausko A.A. Simmetrichnyy kriptograficheskiy algoritm ADE (Algorithm of Dynamic Encryption) [Symmetric cryptographic algorithm ADE (Algorithm of Dynamic Encryption)], Prikladnaya radioelektronika [Applied Radio Electronics], 2007, Vol. 6, No. 2, pp. 241-249.
19. Bogdanov A., Knudsen L.R., Leander G. et al. PRESENT: An Ultra-Lightweight Block Cipher, Proceedings of the 9th International Workshop on Cryptographic Hardware and Embedded Systems. CHES ’07. Berlin, Heidelberg: Springer-Verlag, 2007, pp. 450-466. Available at:
20. Julia Borghoff, Lars R. Knudsen, Gregor Leander, Søren S. Thomsen. Cryptanalysis of PRESENT-Like Ciphers with Secret S-Boxes, FSE, Under ed. by Antoine Joux, Vol. 6733 of Lecture Notes in Computer Science. Springer, 2011, pp. 270-289.
21. Schneier B. Applied Cryptography: Protocols, Algorithms, and Source Code in C, Second Edition. New York: John Wiley and Sons, 1996.
22. Nadhem J. AlFardan, Daniel J. Bernstein, Kenneth G. Paterson et al. On the Security of RC4 in TLS, Proceedings of the 22th USENIX Security Symposium, Washington, DC, USA, August 14-16, 2013, pp. 305-320. – Available at: usenixsecurity13/technical-sessions/paper/alFardan.
23. Lv Jing, Zhang Bin, Lin Dongdai. Distinguishing Attacks on RC4 and A New Improvement of the Cipher, IACR Cryptology ePrint Archive, 2013, Vol. 2013, pp. 176. Available at:
24. Security Advisory 2868725: Recommendation to disable RC4. Security Research and Defense Blog. Available at:
25. Polikarpov S.V., Rumyantsev K.E., Kozhevnikov A.A. Psevdo-dinamicheskie tablitsy podstanovki: osnova sovremennykh simmetrichnykh kriptoalgoritmov [Pseudo-dynamic lookup table: the basis of modern symmetric cryptographic algorithms], Nauchnoe obozrenie [Scientific Review], 2014, No. 12, pp. 162-166.
26. Polikarpov S.V., Rumyantsev K.E., Kozhevnikov A.A. Psevdo-dinamicheskie tablitsy podstanovki: issledovanie differentsial'nykh kharakteristik [Pseudo-dynamic lookup table: study the differential characteristics of], Fiziko-matematicheskie metody i informatsionnye tekhnologii v estestvoznanii, tekhnike i gumanitarnykh naukakh: Cbornik materialov mezhdunarodnogo nauchnogo e-simpoziuma. Rossiya, g. Moskva, 27-28 dekabrya 2014 g [Physico-mathematical methods and informational technologies in science, technology and the Humanities: proceedings of the international scientific e-Symposium. Russia, Moscow, 27-28 December 2014]. Kirov: MTsNIP, 2015, pp 77-89. Available at:

Comments are closed.