SOFTWARE BITSLICED IMPLEMENTATION OF KALYNA CIPHER IS ORIENTED TO USE SIMD INSTRUCTIONS FOR MICROPROCESSORS WITH X86-64 ARCHITECTURE
DOI:
https://doi.org/10.28925/2663-4023.2020.7.131152Keywords:
cipher , bitslicing;, vector instructions;, SSE; AVX; AVX-512;, SBox;, x86-64 architecture;, performanceAbstract
The article is devoted to software bitsliced implementation of the Kalyna cipher using vector instructions SSE, AVX, AVX-512 for x86-64 processors. The advantages and disadvantages of different approaches to efficient and secure block cipher software implementation are shown. It is noted that bitslicing technology combines high speed and resistance to time and cache attacks, but its application to the Kalyna cipher is not available at the moment. The basic approaches to data representation and bitsliced encryption operations are considered, special attention is paid to the effective implementation of SubBytes operation, which largely determines the final performance. Existing methods for minimizing logical functions have been shown to either fail to produce the result in bitsliced format in the case of 8-bit non-algebraic SBoxs, or far from optimal. A heuristic algorithm for minimizing logic functions describing Kalyna SBoxes using the operations of AND, OR, XOR, NOT available in the instruction set of low- and high-end processors is proposed. The results show that a bitsliced description of one SBox requires about 520 gates, which is significantly less than other methods. Possible ways to increase performance by regrouping data into bitsliced variables before and after the SubBytes operation are indicated, which results in more efficient use of vector registers. The bitsliced implementations of Kalyna cipher were measured using C++ compilers from Microsoft and GCC for the Intel Xeon Skylake-SP processor. The results of the bitsliced Kalyna implementation can also be transferred to processors that do not support SIMD instructions, including low-end, to increase resistance to attacks through third-party channels. They also enable switching to ASIC or FPGA-based bitsliced implementation of Kalyna.
Downloads
References
Standards Ukraine 2014, DSTU 7624:2014 Information Technologies. Cryptographic Data Security. Symmetric block transformation algorithm. [online] Available: http://ukrndnc.org.ua/downloads/new_view/?i=dstu-7624-2014&pz=%C4%D1%D2%D3+7624%3A2014.
Kuznetsov O., Oliynykov R., Gorbenko Y., Pushkaryov A., Dyrda O., and Gorbenko I., "Requirements justification, construction and analysis of perspective symmetric cryptographical transformations on the base of block cipher codes", Academic Journal of Lviv Polytechnic. Series of Computer Systems and Networks, № 806, pp. 124-140, 2014.
C. Rebeiro, D. Mukhopadhyay, S. Bhattacharya, Timing Channels in Cryptography. A Micro-Architectural Perspective. Cham, Switzerland: Springer, 2015. DOI: https://doi.org/10.1007/978-3-319-12370-7
Q. Ge, Y. Yarom, D. Cock, G. Heiser, "A survey of microarchitectural timing attacks and countermeasures on contemporary hardware", Journal of Cryptographic Engineering, vol. 8, no. 1, pp. 1–27, 2016. DOI: https://doi.org/10.1007/s13389-016-0141-6
D. Kusswurm. Modern x86 Assembly Language Programming 32-bit 64-bit SSE and AVX. N.-Y., USA: Apress, 2014. DOI: https://doi.org/10.1007/978-1-4842-0064-3
E. Biham, "A fast new DES implementation in software". In: Biham E. (eds) Fast Software Encryption. FSE LNCS, vol. 1267, pp. 260-272, 1997. DOI: https://doi.org/10.1007/BFb0052352
E. Käsper, P. Schwabe, "Faster and Timing-Attack Resistant AES-GCM", in Proc. 11th International Workshop Cryptographic Hardware and Embedded Systems, Lausanne, Switzerland, 2009, pp. 1-17. DOI: https://doi.org/10.1007/978-3-642-04138-9_1
R. Oliynikov, I. Gorbenko, O. Kazimirov, V. Ruzhentsev, & Y. Gorbenko, "Design principles and main properties of the new Ukrainian national standard of block encryption", Ukrainian Information Security Research Journal, vol. 17, no. 2, pp. 142-157, 2015. DOI: https://doi.org/10.18372/2410-7840.17.8789
R. Oliynykov, O. Kazymyrov, O. Kachko, R. Mordvinov, et al. Source code for performance estimation of 64-bit optimized implementation of the block ciphers Kalyna, AES, GOST, BelT, Kuznyechik. [online] Available: https://github.com/Roman-Oliynykov /ciphers-speed/.
V. Kovtun, & A. Okhrimenko. Features of construction of a cross-platform library of cryptographic primitives "Cipher+" v2. [online] Available: https://cipher.com.ua/media/%D0%9F%D1%80%D0%BE%D0%B4%D1%83%D0%BA%D1%82%D1%8B/%D0%A8%D0%B8%D1%84%D1%80%2Bv2.1/Presentation_Cipher_Plus.pdf.
cppcrypto library. Encryption performance. [online] Available: http://cppcrypto.sourceforge.net/.
Y. Sovyn, V. Khoma, Y. Nakonechny, & Y. Stakhiv, "Effective implementation and performance comparison of «Kalyna» and GOST 28147-89 ciphers witch the use of vector extensions SSE, AVX and AVX-512", Ukrainian Information Security Research Journal, vol. 21, no. 4, pp. 207-223, 2019. DOI: https://doi.org/10.18372/2410-7840.21.14266
R. Brayton, G. Hachtel, C. McMullen, and A. Sangiovanni-Vincentelli. Logic minimization algorithms for VLSI synthesis. Hingham, USA: Kluwer Academic Publishers, 1984. DOI: https://doi.org/10.1007/978-1-4613-2821-6
D. Canright, "A very compact S-Box for AES", in Proc. 7th International Workshop Cryptographic Hardware and Embedded Systems, Edinburgh, UK, 2005, pp. 441-455. DOI: https://doi.org/10.1007/11545262_32
J. Boyar, and R. Peralta, "A small depth-16 circuit for the AES S-Box", IFIP Advances in Information and Communication Technology, vol. 376, pp. 287–298, 2012. DOI: https://doi.org/10.1007/978-3-642-30436-1_24
A. Reyhani-Masoleh, M. Taha, and D. Ashmawy, "Smashing the implementation records of AES S-Box", IACR Transactions on Cryptographic Hardware and Embedded Systems, no. 2, pp. 298–336, 2018. DOI: https://doi.org/10.13154/tches.v2018.i2.298-336
K. Stoffelen, "Optimizing S-Box Implementations for Several Criteria Using SAT Solvers", in Proc. 23rd International Conference on Fast Software Encryption, Bochum, Germany, 2016, pp. 140-160. DOI: https://doi.org/10.1007/978-3-662-52993-5_8
N. Courtois, T. Mourouzis, and D. Hulme, "Exact logic minimization and multiplicative complexity of concrete algebraic and cryptographic circuits", International Journal On Advances in Intelligent Systems, vol. 6, no. 3 and 4, pp. 165–176, 2013.
R. Oliynykov, I. Gorbenko, O. Kazymyrov et al. "A New Encryption Standard of Ukraine: The Kalyna Block Cipher", in Proc. Norwegian Information Security Conference, Ålesund, Norway, 2015, 113 p.
Intel Intrinsics Guide. [online] Available: https://software.intel.com/sites/landingpage/IntrinsicsGuide/.
"Using the RDTSC Instruction for Performance Monitoring. Application Note", Intel, 1998.
Bitsliced SBox (Kalyna). [online] Available: https://drive.google.com/open?id=1e7iC_uADd8dDwdgaBgmN3OGiW4vyuLrr.
