16-bit S-box Design Method Based on L-M-NFSR Structure

doi:10.3778/j.issn.1673-9418.2207012

Abstract

Abstract: S-box is an important component for non-linear transformation in symmetric cryptographic algorithm, and the security of S-box determines the security of the cryptographic algorithm. In order to construct 16-bit S-box with strong security, a new L-M-NFSR structure is designed based on the Lai-Massey structure and nonlinear feedback shift register (NFSR) component. In the new structure, 8-bit S-boxes with advanced encryption standard (AES) algorithm S-box affine equivalence are selected as the round function to reduce the complexity of designing and increase the variability of the structure. Two designed NFSR components that can conform to strict avalanche properties with a small number of iterations are placed into two branches of the structure to improve the diffusion effect of the structure. Then, 16-bit S-boxes are constructed by 3-round iteration and traversal search. Furthermore, based on this structure, a large number of new 16-bit S-boxes can be generated by replacing 8-bit S-boxes in the round function with 8-bit S-boxes which are affine equivalent to the AES algorithm S-box. To improve the effici-ency of the evaluation of the properties of the constructed 16-bit S-boxes, parallel computation is performed using graphics processing unit (GPU). The test results show that the newly constructed 16-bit S-boxes have good crypto-graphic properties, which satisfy bijectivity with optimal algebraic number 15, the highest nonlinearity 31992, the lowest differential uniformity 18, and minimum signal-to-noise ratio 146.712, with excellent security against mathematical attacks and differential power analysis.

Key words: S-box, Lai-Massey structure, nonlinear feedback shift register (NFSR), differential uniformity

摘要： S盒是分组密码算法的重要部件，为密码算法提供非线性变换，S盒的安全强度在一定程度上决定着密码算法的安全强度。为构造具有优良密码学性质的16比特S盒，设计一种以Lai-Massey结构和非线性反馈移位寄存器（NFSR）组件相结合的L-M-NFSR新结构。该结构以与高级加密标准（AES）算法S盒仿射等价的8比特S盒作为新结构的轮函数，减少设计的复杂性并提高结构的可变性；左右分支各增加一个迭代少量拍数即可符合严格雪崩特性的NFSR组件用于提高结构的扩散性；通过3轮迭代和遍历生成16比特S盒。进一步地，基于该结构，以AES算法S盒仿射等价新生成的8比特S盒替换轮函数中的8比特S盒，可方便地生成大量新的16比特密码S盒。为提高对所构造16比特S盒性质的评估效率，采用图形处理器（GPU）进行并行计算，测试结果表明，所生成的16比特S盒具有较优的密码学性质，均满足双射性，代数次数为15，非线性度最优为31 992，差分均匀度最低为18，信噪比最低为146.712，具有较好地抵御数学攻击和差分功耗分析的安全性。

关键词: S盒, Lai-Massey结构, 非线性反馈移位寄存器（NFSR）, 差分均匀度

WU Xiaonian, SHU Rui, DOU Daorao, ZHANG Runlian, WEI Yongzhuang. 16-bit S-box Design Method Based on L-M-NFSR Structure[J]. Journal of Frontiers of Computer Science and Technology, 2023, 17(10): 2511-2518.

武小年, 舒瑞, 豆道饶, 张润莲, 韦永壮. 基于L-M-NFSR结构的16比特S盒设计方法[J]. 计算机科学与探索, 2023, 17(10): 2511-2518.

References

[1] LEANDER G, POSCHMANN A. On the classification of 4 bit s-boxes[C]//LNCS 4547: Proceedings of the 1st Intern-ational Workshop on Arithmetic of Finite Fields, Madrid, Jun 21-22, 2007. Berlin, Heidelberg: Springer, 2007: 159-176.
[2] SAARINEN M. Cryptographic analysis of all 4×4-bit S-boxes[C]//LNCS 7118: Proceedings of the 2011 Interna-tional Workshop on Selected Areas in Cryptography, Toronto, Aug 11-12, 2011. Berlin, Heidelberg: Springer, 2011: 118-133.
[3] ULLRICH M, CANNIERE C, INDESTEEGE S, et al. Find-ing optimal bitsliced implementations of 4×4-bit S-boxes[C]//Proceedings of the 2011 Symmetric Key Encryption Workshop, Copenhagen， Feb 17, 2011: 16-17.
[4] CANTEAUT A, DUVAL S, LEURENT G. Construction of lightweight S-boxes using feistel and MISTY structures[C]//LNCS 9566: Proceedings of the 22nd International Confer-ence on Selected Areas in Cryptography, Sackville, Aug 12-14, 2015. Cham: Springer, 2015: 373-393.
[5] CHENG L, ZHANG W, XIANG Z. A new cryptographic analysis of 4-bit S-boxes[C]//LNCS 9589: Proceedings of the 11th International Conference on Information Security and Cryptology, Beijing, Nov 1-3, 2015. Cham: Springer, 2016: 144-164.
[6] PERRIN L, UDOVENKO A, BIRYUKOV A. Cryptanaly-sis of a theorem: decomposing the only known solution to the big APN problem[C]//LNCS 9815: Proceedings of the 36th Annual International Cryptology Conference on Advances in Cryptology, Santa Barbara, Aug 14-18, 2016. Cham: Spr-inger, 2016: 93-122.
[7] KAPU?CI?SKI T, NOWICKI R K, NAPOLI C. Compar-ison of effectiveness of multi-objective genetic algorithms in optimization of invertible S-boxes[C]//LNCS 10246: Proceedings of the 16th International Conference on Arti-ficial Intelligence and Soft Computing, Zakopane, Jun 11-15, 2017. Cham: Springer, 2017: 466-476.
[8] GHOSHAL A, SADHUKHAN R, PATRANABIS S, et al. Lightweight and side-channel secure 4×4 S-boxes from cellular automata rules[J]. IACR Transactions on Symme-tric Cryptology, 2018(3): 311-334.
[9] MISHRA G, MURTHY S K, PAL S K. Neural network based analysis of lightweight block cipher PRESENT[C]// Proceedings of the 4th International Conference on Harmony Search, Soft Computing and Applications, Gurgaon, Feb 7-9, 2018. Cham: Springer, 2019: 969-978.
[10] ZAHID A H, ARSHAD M J. An innovative design of substitution-boxes using cubic polynomial mapping[J]. Sym-metry, 2019, 11(3): 437.
[11] 张润莲, 孙亚平, 韦永壮, 等. 密码S盒的一种新自动搜索方法[J]. 计算机研究与发展, 2020, 57(7): 1415-1423.
ZHANG R L, SUN Y P, WEI Y Z, et al. A new automatic search method for cryptographic S-Box[J]. Journal of Com-puter Research and Development, 2020, 57(7): 1415-1423.
[12] 黄俊君, 关杰. 基于元胞自动机的S盒的性质与神经网络实现研究[J]. 电子学报, 2020, 48(12): 2462-2468.
HUANG J J, GUAN J. Research on properties and neural networks implementation of cellular automata based S-boxes[J]. Acta Electronica Sinica, 2020, 48(12): 2462-2468.
[13] WANG Y, ZHANG Z Q, ZHANG L Y, et al. A genetic algorithm for constructing bijective substitution boxes with high nonlinearity[J]. Information Sciences, 2020, 523: 152-166.
[14] KIM H, JEON Y, KIM G, et al. A new method for designing lightweight S-boxes with high differential and linear branch numbers, and its application[J]. IEEE Access, 2021, 9: 150592-150607.
[15] SHIBUTANI K, ISOBE T, HIWATARI H, et al. Piccolo: an ultra lightweight blockcipher[C]//LNCS 6917: Proceedings of the 13th International Workshop on Cryptographic Hard-ware and Embedded Systems, Nara, Sep 28-Oct 1, 2011.Berlin, Heidelberg: Springer, 2011: 342-357.
[16] CANTEAUT A, DUVAL S, LEURENT G, et al. Saturnin: a suite of lightweight symmetric algorithms for post-quantum security[J]. IACR Transactions on Symmetric Cryptology, 2020(S1): 160-207.
[17] 徐洪, 段明, 谭林, 等. NBC算法[J]. 密码学报, 2019, 6(6): 760-767.
XU H, DUAN M, TAN L, et al. On the NBC algorithm[J]. Journal of Cryptologic Research, 2019, 6(6): 760-767.
[18] 田甜, 戚文峰, 叶晨东, 等. 基于NFSR的分组密码算法SPRING[J]. 密码学报, 2019, 6(6): 815-834.
TIAN T, QI W F, YE C D, et al. SPRING: a family of small hardware-oriented block ciphers based on NFSRs[J]. Journal of Cryptologic Research, 2019, 6(6): 815-834.
[19] BEIERLE C, BIRYUKOV A, SANTOS L C D, et al. Alzette: a 64-bit ARX-box[C]//LNCS 12172: Proceedings of the 40th Annual International Cryptology Conference on Advances in Cryptology, Santa Barbara, Aug 17-21, 2020. Cham: Springer, 2020: 419-448.
[20] VAUDENAY S. On the Lai-Massey scheme[C]//LNCS 1716: Proceedings of the 1999 International Conference on the Theory and Applications of Cryptology and Information Security, Singapore, Nov 14-18, 1999. Berlin, Heidelberg: Springer, 1999: 8-19.
[21] LUO Y Y, LAI X J, GONG Z. Pseudorandomness analysis of the (extended) Lai-Massey scheme[J]. Information Pro-cessing Letters, 2010, 111(2): 90-96.
[22] GUILLEY S, HOOGVORST P, PACALET R. Differential power analysis model and some results[C]//Proceedings of the IFIP 18th World Computer Congress-Smart Card Research and Advanced Applications VI, Toulouse, Aug 22-27, 2004. Berlin, Heidelberg: Springer, 2004: 127-142.