新的低轮Keccak线性结构设计
|
摘要
针对Keccak算法S盒层线性分解的问题,提出一种新的线性结构构造方法,该方法主要基于Keccak算法S盒代数性质。首先,S盒层的输入比特需要固定部分约束条件,以确保状态数据经过这种线性结构仍具有线性关系;然后再结合中间相遇攻击的思想给出新的低轮Keccak算法零和区分器的构造方法。实验结果表明:新的顺1轮、逆1轮零和区分器可以完成目前理论上最好的15轮Keccak的区分攻击,且复杂度降低至2257;新的顺1轮、逆2轮零和区分器具有自由变量更多、区分攻击的组合方式更丰富等优点。
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 2257.The new distinguisher, which extends 1-round forward and 2-round backward, has the advantages of more free variables and richer distinging attack combinations.
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 2257.The new distinguisher, which extends 1-round forward and 2-round backward, has the advantages of more free variables and richer distinging attack combinations.
引文
[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/hashfunctions/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 roundreduced Keccak[C]//EUROCRYPT 2017:Proceedings of the2017 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]//CRYPTO2017: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]//FSE2015: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-themiddle 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.
[2]National Institute of Standards and Technology.SHA-3 competition[EB/OL].[2012-02-10].https://csrc.nist.gov/projects/hashfunctions/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 roundreduced Keccak[C]//EUROCRYPT 2017:Proceedings of the2017 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]//CRYPTO2017: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]//FSE2015: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-themiddle 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.