The article is devoted to the issues of increasing the security and efficiency of software implementation for the symmetric block ciphers. For the implementation of cryptoalgorithms on low-end CPUs (8/16/32-bit microcontrollers), it is important to provide increased resistance to power consumption analysis attacks. With regard to the implementation of ciphers on high-end CPUs (x86, ARM Cortex-A), it is important to eliminate the vulnerability primarily to timing and cache attacks. The authors used a bitslice approach to securely implement block ciphers, which has potential advantages such as high speed and low computing resources. However, the known bitsliced methods have a significant limitation, since they work with deterministic S-Boxes or arbitrary S-Boxes of smaller sizes. The paper proposes a new heuristic method for bitsliced representation of cryptographic 8×8 S-Boxes containing randomly generated values. These values defy description using algebraic expressions. The method is based on the decomposition of the truth table, which describes the S-Box, into two parts. One part of the table forms logical masks, and the other is split into bit vectors. To find a logical description of these vectors an exhaustive search is used. After finding the description of all vectors, these two parts of the table are combined into one using logical operations. The use of this method oriented on software implementation in the logical basis {AND, OR, XOR, NOT} ensures the minimization of arbitrary 8×8 S-Boxes. The proposed method can be implemented using standard logical instructions on any 8/16/32/64-bit processors. It is also possible to use logical SIMD instructions from the SSE, AVX, AVX-512 extensions for x86-64 processors, which provides high performance due to the use of long registers. The corresponding software has been developed that implements the method of searching for bitsliced representations of a given S-Box, and also automatically generates C++ code for it based on SSE, AVX and AVX-512 instructions. The effectiveness of the method on the S-Box of known block ciphers, in particular the Ukrainian encryption standard "Kalyna", has been investigated. It was found that the developed algorithm requires almost half as many gates for the bitsliced description of an arbitrary S-Box than the best of known algorithm (370 gates versus 680, respectively). For ciphers that use two or four S-Box tables, joint minimization can yield up to 330 or 300 gates per table, respectively.
- Avraamova, O., Fomin, D., Serov, V., Smirnov, A., & Shokov, V. (2021). A compact bit-sliced representation of Kuznyechik S-box. Mathematical Aspects of Cryptography, 12(2), 21–38. https://doi.org/10.4213/mvk354
- Biham, E. (1997). A fast new DES implementation in software. In: Biham E. (Eds.) Fast Software Encryption. FSE 1997. Lecture Notes in Computer Science, 1267, 260–272. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0052352
- Biryukov, A., Perrin, L., & Udovenko, A. (2016) Reverse-Engineering the S-Box of Streebog, Kuznyechik and STRIBOBr1. In: Fischlin M., Coron JS. (Eds.) Advances in Cryptology – EUROCRYPT 2016. Lecture Notes in Computer Science, Vol. 9665, 372–402. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-49890-3_15
- Borisenko, N., Vasinev, D., & Khoang, D. (2016). Method of forming s-blocks with minimum number of logic elements (RU Patent No. 2572423). Federal service for intellectual property. Retrieved from https://patents.google.com/patent/RU2572423C2/enhttps://patents.google.com/patent/RU2014112547A/en
- Boyar, J., & Peralta, R. (2012). A Small Depth-16 Circuit for the AES S-Box. In: Gritzalis D., Furnell S., Theoharidou M. (Eds.) Information Security and Privacy Research. SEC 2012. IFIP Advances in Information and Communication Technology, Vol. 376, 287–298. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-30436-1_24
- Brayton, R., Hachtel, G., McMullen, C., & Sangiovanni-Vincentelli, A. (1984). Logic Minimization Algorithms for VLSI Synthesis. Kluwer Academic Publishers, Hingham, USA. https://doi.org/10.1007/978-1-4613-2821-6
- Canright, D. (2005). A Very Compact S-Box for AES. In: Rao J. R., Sunar B. (Eds.) Cryptographic Hardware and Embedded Systems – CHES 2005. CHES 2005. Lecture Notes in Computer Science, Vol. 3659, 441–455. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11545262_32
- Intel. (2021). Intel Intrinsics Guide. Retrieved from https://software.intel.com/sites/landingpage/IntrinsicsGuide/
- Käsper, E., & Schwabe, P. (2009). Faster and Timing-Attack Resistant AES-GCM. In: Clavier C., Gaj K. (Eds.) Cryptographic Hardware and Embedded Systems – CHES 2009. CHES 2009. Lecture Notes in Computer Science, 5747, 1–17. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-04138-9_1
- Maximov, A., & Ekdahl, P. (2019). New Circuit Minimization Techniques for Smaller and Faster AES SBoxes. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2(4), 91–125. https://doi.org/10.13154/tches.v2019.i4.91-125
- Oliynykov, R., et al. (2015). A New Encryption Standard of Ukraine: The Kalyna Block Cipher. IACR Cryptology ePrint Archive, 2(650). Retrieved from https://eprint.iacr.org/2015/650.pdf
- Raghuraman, S. (2019). Efficiency of Logic Minimization Techniques for Cryptographic Hardware Implementation. Masters Thesis, Virginia Polytechnic Institute and State University.
- Reyhani-Masoleh, A., Taha, M., & Ashmawy, D. (2018). Smashing the Implementation Records of AES S-box. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2(2), 298–336. https://doi.org/10.13154/tches.v2018.i2.298-336
- Sovyn, Y., & Khoma, V. (2021). Bitsliced S-Box. Retrieved from https://drive.google.com/drive/folders/1yotZ4Hu5d3u0A4SoQnSS__BrcNZDOKYh? usp=sharing
- Stoffelen, K. (2016). Optimizing S-Box Implementations for Several Criteria Using SAT Solvers. In: Peyrin T. (Eds.) Fast Software Encryption. FSE 2016. Lecture Notes in Computer Science, Vol. 9783, 140–160. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-52993-5_8