On algorithmic implementation of 16-bit s-bo-xes with arx and butterfly structures

Implementations of nonlinear mappings of vector space V_n (s-boxes n x n) as lookup-tables are memory intensive. It requires n2ⁿ bits to store n-bit s-box. That is why the existing block ciphers use s-boxes of relatively small size (8x8 bit - AES, Kuznyechik, 6x4 bit - DES). New constructions of 16-bit algorithmically implementable s-boxes with improved performance and cryptographic properties (in comparison with the existing methods) are proposed. The first method is based on ARX (Add-Rotate-XOR) structure, using low-cost computations in software and hardware. The second method is based on butterfly structure, using 8-bit precomputed s-boxes to build 16 x 16 ones. Maximum expected differential probability, maximum expected linear probability and minimum nonlinear order over all linear combinations of the components of proposed s-boxes with ARX structure are 18/2¹⁶, 764/2¹⁵ and 15, respectively and of suggested s-boxes with Butterfly structure are 10/2¹⁶, 512/2¹⁵ and 15, respectively. It is established that the use of the proposed 16-bit s-boxes in the round substitutions of AES and Kuznyechik block ciphers significantly lowers the upper bounds of differential and linear probabilities for two and four rounds of these algorithms.

Keywords

Authors

References