New design of linear structure for round-reduced Keccak

doi:10.11772/j.issn.1001-9081.2018030617

Journal of Computer Applications ›› 2018, Vol. 38 ›› Issue (10): 2934-2939.DOI: 10.11772/j.issn.1001-9081.2018030617

Previous Articles Next Articles

New design of linear structure for round-reduced Keccak

LIU Xiaoqiang^1,2, WEI Yongzhuang^2,3, LIU Zhenghong¹

1. Guangxi Key Laboratory of Cryptography and Information Security(Guilin University of Electronic Technology), Guilin Guangxi 541004, China;
2. Guangxi Key Laboratory of Wirekess Wideband Communication and Signal Processing(Guilin University of Electronic Technology), Guilin Guangxi 541004, China;
3. Guangxi Colleges and Universities Key Laboratory of Cloud Computing and Complex Systems(Guilin University of Electronic Technology), Guilin Guangxi 541004, China

Received:2018-03-26 Revised:2018-04-29 Online:2018-10-10 Published:2018-10-13
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61572148), the Project of Guangxi Key Laboratory of Wireless Wideband Communication and Signal Processing (GXKL06160112).

新的低轮Keccak线性结构设计

刘晓强^1,2, 韦永壮^2,3, 刘争红¹

1. 广西密码学与信息安全重点实验室(桂林电子科技大学), 广西桂林 541004;
2. 广西无线宽带通信与信号处理重点实验室(桂林电子科技大学), 广西桂林 541004;
3. 广西高校云计算与复杂系统重点实验室(桂林电子科技大学), 广西桂林 541004

通讯作者: 韦永壮
作者简介:刘晓强(1993-),男,山西大同人,硕士研究生,主要研究方向:对称密码算法分析;韦永壮(1976-),男,广西田阳人,教授,博士,主要研究方向:对称密码算法设计与分析;刘争红(1979-),男,湖北红安人,讲师,硕士,主要研究方向:无线宽带通信、FPGA、GPU并行运算。
基金资助:
国家自然科学基金资助项目（61572148）；广西无线宽带通信与信号处理重点实验室2016年主任基金资助项目（GXKL06160112）。

Abstract

Abstract: Focusing on the linear decomposition of the S-box layer in Keccak algorithm, a new linear structure construction method was proposed based on the algebraic properties of the S-box. Firstly, to ensure the state data was still linear with that after this linear structure, some constraints about input bits of S-box needed to be fixed. Then, as an application of this technique, some new zero-sum distinguishers of round-reduced Keccak were constructed by combining the idea of meet-in-the-middle attack. The results show that a new 15-round distinguisher of Keccak is found, which extends 1-round forward and 1-round backward. This work is consistent with the best known ones and its complexity is reduced to 2²⁵⁷. The new distinguisher, which extends 1-round forward and 2-round backward, has the advantages of more free variables and richer distinging attack combinations.

Key words: Secure Hash Algorithm 3 (SHA-3), Hash algorithm, meet-in-the-middle, zero-sum distinguisher, linear structure

摘要： 针对Keccak算法S盒层线性分解的问题，提出一种新的线性结构构造方法，该方法主要基于Keccak算法S盒代数性质。首先，S盒层的输入比特需要固定部分约束条件，以确保状态数据经过这种线性结构仍具有线性关系；然后再结合中间相遇攻击的思想给出新的低轮Keccak算法零和区分器的构造方法。实验结果表明：新的顺1轮、逆1轮零和区分器可以完成目前理论上最好的15轮Keccak的区分攻击，且复杂度降低至2²⁵⁷；新的顺1轮、逆2轮零和区分器具有自由变量更多、区分攻击的组合方式更丰富等优点。

关键词: SHA-3, Hash算法, 中间相遇, 零和区分器, 线性结构

CLC Number:

TP309

LIU Xiaoqiang, WEI Yongzhuang, LIU Zhenghong. New design of linear structure for round-reduced Keccak[J]. Journal of Computer Applications, 2018, 38(10): 2934-2939.

刘晓强, 韦永壮, 刘争红. 新的低轮Keccak线性结构设计[J]. 计算机应用, 2018, 38(10): 2934-2939.

References

[1] KAYSER R F. Announcing request for candidate algorithm nominations for a new cryptographic hash algorithm (SHA-3) family[J]. Federal Register, 2007, 72(212):62.
[2] National Institute of Standards and Technology. SHA-3 competition[EB/OL].[2012-02-10].https://csrc.nist.gov/projects/hash-functions/sha-3-project.
[3] BERTONI G, DAEMEN J, PEETERS M, et al. Keccak[C]//EUROCRYPT 2013:Proceedings of the 2013 Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin:Springer, 2013:313-314.
[4] DWORKIN M J. SHA-3 standard:permutation-based hash and extendable-output functions[EB/OL].[2018-01-10]. https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.202.pdf.
[5] BERTONI G, DAEMEN J, PEETERS M, et al. Cryptographic sponge functions[EB/OL].[2017-04-10]. https://keccak.team/files/CSF-0.1.pdf.
[6] BERTONI G, DAEMEN J, PEETERS M, et al. Team Keccak[EB/OL].[2017-08-22]. https://keccak.team/index.html.
[7] DINUR I, DUNKELMAN O, SHAMIR A. New attacks on Keccak-224 and Keccak-256[C]//FSE 2012:Proceedings of the 2012 International Workshop on Fast Software Encryption. Berlin:Springer, 2012:442-461.
[8] QIAO K, SONG L, LIU M, et al. New collision attacks on round-reduced Keccak[C]//EUROCRYPT 2017:Proceedings of the 2017 Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin:Springer, 2017:216-243.
[9] BERTONI G, DAEMEN J, PEETERS M, et al. The Keccak crunchy crypto collision and pre-image contest[EB/OL].[2017-05-16]. https://keccak.team/crunchy_contest.html.
[10] SONG L, LIAO G, GUO J. Non-full sbox linearization:applications to collision attacks on round-reduced Keccak[C]//CRYPTO 2017:Proceedings of the 2017 Annual International Cryptology Conference. Berlin:Springer, 2017:428-451.
[11] JEAN J, NIKOLIC I. Internal differential boomerangs:practical analysis of the round-reduced Keccak-f permutation[C]//FSE 2015:Proceedings of the 2015 International Workshop on Fast Software Encryption. Berlin:Springer, 2015:537-556.
[12] AUMASSON J P, MEIER W. Zero-sum distinguishers for reduced Keccak-f and for the core functions of Luffa and Hamsi[EB/OL].[2018-01-10]. https://131002.net/data/papers/AM09.pdf.
[13] GUO J, LIU M, SONG L. Linear structures:applications to cryptanalysis of round-reduced Keccak[C]//ASIACRYPT 2016:Proceedings of the 2016 International Conference on the Theory and Application of Cryptology and Information Security. Berlin:Springer, 2016:249-274.
[14] HUANG S, WANG X, XU G, et al. Conditional cube attack on reduced-round Keccak sponge function[C]//EUROCRYPT 2017:Proceedings of the 2017 Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin:Springer, 2017:259-288.
[15] 董晓阳.几个重要对称密码和通用密码结构的分析[D]. 济南:山东大学, 2017:25-45. (DONG X Y. Gryptanalysis of several symmetric ciphers and generic structures[D]. Jinan:Shandong University, 2017:25-45.)
[16] GUO J, LING S, RECHBERGER C, et al. Advanced meet-in-the-middle preimage attacks:first results on full tiger and improved results on MD4 and SHA-2[C]//ASIACRYPT 2010:Proceedings of the 2010 International Conference on the Theory and Application of Cryptology and Information Security. Berlin:Springer, 2010:56-75.
[17] BERTONI G, DAEMEN J, PEETERS M, et al. The Keccak reference V3.0[EB/OL].[2017-05-17]. https://keccak.team/files/Keccak-reference-3.0.pdf.

New design of linear structure for round-reduced Keccak

新的低轮Keccak线性结构设计

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 12

Recommended Articles

Metrics

[1]	YANG Su, OUYANG Zhi, DU Nisuo. Unsupervised parallel hash image retrieval based on correlation distance [J]. Journal of Computer Applications, 2021, 41(7): 1902-1907.
[2]	WANG Yafang, LIU Dongsheng, HOU Min. Clone code detection based on image similarity [J]. Journal of Computer Applications, 2019, 39(7): 2074-2080.
[3]	YANG Ping, ZHAO Bing, SHU Hui. Malicious code detection method based on icon similarity analysis [J]. Journal of Computer Applications, 2019, 39(6): 1728-1734.
[4]	LIU Zhusong, YANG Zhangjie. Efficient and secure deduplication cloud storage scheme based on proof of ownership by Bloom filter [J]. Journal of Computer Applications, 2017, 37(3): 766-770.
[5]	LI Lingchen, WEI Yongzhuang, ZHU Jialiang. Meet-in-the-middle attack on 11-round reduced 3D block cipher [J]. Journal of Computer Applications, 2015, 35(3): 700-703.
[6]	LU Ting, FANG Jun, QIAO Yanke. HBase-based real-time storage system for traffic stream data [J]. Journal of Computer Applications, 2015, 35(1): 103-107.
[7]	WEI Hongru ZHEN Yafei WANG Xinyu. Biclique cryptanalysis of ARIRANG-256 [J]. Journal of Computer Applications, 2014, 34(1): 69-72.
[8]	WU Wu-fei WANG Yi LI Ren-fa. Reconfigurable Keccak algorithm and its implementation on FPGA platform [J]. Journal of Computer Applications, 2012, 32(03): 864-866.
[9]	. One-way hash algorithm based on chaotic coupled dynamic parameters [J]. Journal of Computer Applications, 2010, 30(9): 2398-2400.
[10]	Jing-zhong WANG Fei DU. Research of matrix bloom filter in virus filtering firewall [J]. Journal of Computer Applications, 2009, 29(11): 2939-2941.
[11]	Yong-Yan QIANG Geng Yang. Research and design of Chinese-spam's phrase segmentation based on indexing [J]. Journal of Computer Applications, 2007, 27(9): 2334-2336.
[12]	;;. Research of IPv6 neighbor discovery protocol security mechanism [J]. Journal of Computer Applications, 2006, 26(4): 938-941.