Improvement of Preimage Attack on 4-Round Keccak-256 by Solving Algebraic Systems

doi:10.3778/j.issn.1002-8331.2010-0315

Abstract

Abstract: Keccak Hash function is the third generation secure Hash function with provable security and excellent implementation performance. In this paper, 4-round Keccak-256 preimage attack by solving algebraic system is discussed, which improves the existing 4-round Keccak-256 preimage attack and effectively reduces the theoretical complexity. At present, the theoretical complexity of 4-round Keccak-256 preimage attack is at least 2239. This paper makes full use of the relationships among the factors of the quadratic bits, and linearizes more quadratic bits with the same degree of freedom, reducing the theoretical complexity to 2216.

Key words: cryptanalysis, Keccak Hash function, preimage attack, algebraic system

摘要： Keccak哈希函数是第三代安全哈希函数，具有可证明的安全性与良好的实现性能。讨论基于代数系统求解的4轮Keccak-256原像攻击，对已有的4轮原像攻击方法进行了完善，有效降低了理论复杂度。目前，4轮Keccak-256原像攻击的理论复杂度最低为2239，通过充分利用二次比特的因式之间的关系，在自由度相同的情况下，线性化更多的二次比特，将理论复杂度降低至2216。

关键词: 密码分析, Keccak哈希函数, 原像攻击, 代数系统

PEI Junling, CHEN Lusheng. Improvement of Preimage Attack on 4-Round Keccak-256 by Solving Algebraic Systems[J]. Computer Engineering and Applications, 2022, 58(5): 119-123.

裴君翎, 陈鲁生. 代数系统求解4轮Keccak-256原像攻击的完善[J]. 计算机工程与应用, 2022, 58(5): 119-123.

References

[1] BERTONI G，DAEMEN J，PEETERS M，et al.The Keccak reference，version 3.0[EB/OL].（2011-01-14）[2020-09-29].https：//keccak.team/files/Keccak-reference-3.0.pdf.
[2] National Institute of Standards and Technology.SHA-3 competition[EB/OL].（2007-11-02）[2020-09-29].https：//csrc.nist.gov/projects/hash-functions/sha-3-project.
[3] DINUR I，MORAWIECKI P，PIEPRZYK J，et al.Cube attacks and cube-attack-like cryptanalysis on the round-reduced Keccak sponge function[C]//Proceedings of 34th International Conference on the Theory and Application of Cryptology Techniques，Sofia，Apr26-30，2015.Berlin，Heidelberg：Springer，2015：733-761.
[4] DAS S，MEIER W.Differential biases in reduced-round Keccak[C]//Proceedings of 7th International Conference on Cryptology in Africa，Marrakesh，May 28-30，2014.Cham：Springer，2014：69-87.
[5] LIU F K，CAO Z F，WANG G L.Finding ordinary cube variables for Keccak-MAC with greedy algorithm[C]//Proceedings of 14th International Workshop on Security，Tokyo，Aug 28-30，2019.Cham：Springer，2019：287-305.
[6] NAYA-PLASENCIA M，R?CK A，MEIER W.Practical analysis of reduced-round Keccak[C]//Proceedings of 12th International Conference on Cryptology in India，Chennai，Dec 11-14，2011.Berlin，Heidelberg：Springer，2011：236-254.
[7] MORAWIECKI P，SREBRNY M.A SAT-based preimage analysis of reduced Keccak hash functions[J].Information Processing Letters，2013，113：392-397.
[8] MORAWIECKI P，PIEPRZYK J，SREBRNY M.Rotational cryptanalysis of round-reduced Keccak[C]//Proceedings of 20th International Workshop on Fast Software Encryption，Singapore，Mar 11-13，2013.Berlin，Heidelberg：Springer，2013：241-262.
[9] BERNSTEIN D J.Second preimages for 6 or 7 or 8 rounds of Keccak[EB/OL].（2010-11-27）[2020-09-29].http：//cr.yp.to/hash/keccak-20101127.txt.
[10] CHANG D H，KUMAR A，MORAWIECKI P，et al.1st and 2nd preimage attacks on7，8 and 9 rounds of Keccak-224，256，384，512[EB/OL].（2014-08-22）[2020-09-29].https：//csrc.nist.gov/events/2014/sha-3-2014-workshop.
[11] GUO J，LIU M C，SONG L.Linear structures：applications to cryptanalysis of round-reduced Keccak[C]//Proceedings of 22th International Conference on the Theory and Application of Cryptology and Information Security，Hanoi，Dec 4-8，2016.Cham：Springer，2016：249-274.
[12] LI T，SUN Y，LIAO M D，et al.Preimage attacks on the round-reduced Keccak with cross-linear structures[J].IACR Transactions on Symmetric Cryptology，2017，4：39-57.
[13] LI T，SUN Y.Preimage attacks on round-reduced Keccak-224/256 via an allocating approach[C]//Proceedings of 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques，Darmstadt，May 19-23，2019.Cham：Springer，2019：556-584.
[14] RAJASREE M S.Cryptanalysis of round-reduced Keccak using non-linear structures[C]//Proceedings of 20th International Conference on Cryptology in India，Hyderabad，Dec 15-18，2019.Cham：Springer，2019：175-192.
[15] BERTONI G，DAEMEN J，PEETERS M，et al.Cryptographic sponge functions[EB/OL].（2011-01-14）[2021-03-16].https：//keccak.team/files/CSF-0.1.pdf.