Authors S.V. Polikarpov, A.A. Kozhevnikov
Month, Year 08, 2015 @en
Index UDC 004.853
Abstract Use of the pseudo-dynamic substitutions PD-sbox in symmetric cryptoalgorithms allows to combine the strengths of the fixed substitutions (high speed and efficient use of computational resources) and dynamic substitutions (neutralization of statistical methods of cryptanalysis). For optimal use of the pseudo-dynamic substitutions is necessary a detailed investigation and study of cryptographic properties. The purpose of the study – an approximate determination of the linear properties of full-size pseudo-dynamic substitutions based on the extrapolation of the linear properties of small pseudo-dynamic substitutions. Linear properties for small-sized pseudo-dynamic substitutions (that are generated randomly) are investigated. For this were determined the maximum values for the bias of probability approximation of investigated substitutions by linear functions. To simplify the analysis of the results were determined average values of the maxima for bias. This allowed to determine a simple relationship between the parameters of PD-sbox and the probability of obtaining maximum values for bias. The revealed dependence allowed to extrapolate linear properties of small-size pseudo-dynamic substitutions to linear properties of full-size pseudo-dynamic substitutions. The evaluation of the complexity of linear cryptanalysis, defined in the amount of required pairs of "plaintext – ciphertext", showed that there is potential for the synthesis of symmetric block encryption algorithms with extremely low values of bias, for which can be proved the lower threshold of the complexity of linear cryptanalysis.

Download PDF

Keywords Linear cryptanalysis; dynamic substitution; pseudo-dynamic substitution PD-sbox.
References 1. Preneel B., Biryukov A., De C. 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 symmetric block 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 of assessing resistance block symmetric ciphers to attacks of 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. System of information processing. Cryptographic protection. Cryptographic transformation algorithm]. Moscow: Izd-vo standartov IPK, 1996, 28 p. Available at: document.aspx?control=7&id=139177.
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:
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. Borghoff Julia, LarsR. Knudsen, Leander Gregor, Sшren S. Thomsen. Cryptanalysis of PRESENT-Like Ciphers with Secret S-Boxes, FSE, 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:
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 Foundation 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: a study of differential characteristics], Fizikomatematicheskie metody i informatsionnye tekhnologii v estestvoznanii, tekhnike i gumanitarnykh naukakh: sbornik 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:
27. Polikarpov S.V., Rumyantsev K.E., Kozhevnikov A.A. Issledovanie lineynykh kharakteristik psevdodinamicheskikh podstanovok [Research of linear characteristics of pseudo-dynamic substitutions], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2015, No. 5 (166), pp. 111-123.

Comments are closed.