基于不可能差分的SHA3-512约减轮区分攻击
|
摘要
Keccak算法是一族具有海绵结构的杂凑函数,由Bertoni等人设计,是SHA3标准征集活动的最终获选算法,对该算法的分析主要分为三类,分别是对约减轮压缩函数的分析、对消息认证码和认证加密方案的分析以及对置换函数的区分攻击.本文研究了Keccak算法的不可能差分性质,给出了基于不可能差分特征的区分攻击方法.我们发现在轮函数运算过程中,位于同一列的两比特在经过线性层θ时异或值保持不变,基于此性质我们构造了4轮置换函数的不可能差分特征.考虑到不同版本中消息和摘要的长度各不相同,并且会影响输入输出差分的选择,我们筛选出了符合SHA3-512版本约束条件的不可能差分特征.最后,利用在非线性层χ的逆运算中,当输入值满足一定条件时,某些比特的输出差分与输入差分相等这一性质,我们给出了4轮SHA3-512不可能差分区分攻击.当数据量达到2~(8.21)个消息时,将SHA3-512与随机函数区分开的成功率达到99%,对应的时间复杂度为2~(8.21)次压缩.我们以SHA-512作为随机函数,实验验证了上述理论结果.同等轮数下,我们的攻击复杂度优于其他方法.
Keccak is a family of Hash functions with sponge construction, which was designed by Bertoni et al., and selected as the winner of the SHA3 competition. The security analysis of Keccak can be divided into three parts, which are the analyses of Keccak in the context of hashing,the analyses on Keccak-MAC and authenticated encryption schemes, and the distinguish attacks on Keccak-f permutations. This paper studies the impossible differential property of Keccak, and presents a distinguish attack based on it. It is found that the XOR of two bits in a column remains unchanged after the linear operation θ in the round function. Based on this property, a 4-round impossible differential characteristic of Keccak function can be constructed. Considering that the sizes of the message and the digest are different in each version and will affect the choice of the input and output differentials, an impossible differential characteristic is selected that conforms to SHA3-512. Then we develop a property of the non-linear operation x~(-1),which shows that when the input pairs satisfy some constraints, the output difference and the input difference should be equal. Finally, Based on the characteristic and the property, an impossible differential distinguish attack on 4-round SHA3-512 is performed. The success rate of this attack is 99%, where the data complexity is 2~(8.21) messages and the corresponding time complexity is 2~(8.21). We did some experiments to verify the above theoretical results by taking SHA-512 as the random function, and it shows that the complexity of our attack is better than other methods in the same number of rounds.
Keccak is a family of Hash functions with sponge construction, which was designed by Bertoni et al., and selected as the winner of the SHA3 competition. The security analysis of Keccak can be divided into three parts, which are the analyses of Keccak in the context of hashing,the analyses on Keccak-MAC and authenticated encryption schemes, and the distinguish attacks on Keccak-f permutations. This paper studies the impossible differential property of Keccak, and presents a distinguish attack based on it. It is found that the XOR of two bits in a column remains unchanged after the linear operation θ in the round function. Based on this property, a 4-round impossible differential characteristic of Keccak function can be constructed. Considering that the sizes of the message and the digest are different in each version and will affect the choice of the input and output differentials, an impossible differential characteristic is selected that conforms to SHA3-512. Then we develop a property of the non-linear operation x~(-1),which shows that when the input pairs satisfy some constraints, the output difference and the input difference should be equal. Finally, Based on the characteristic and the property, an impossible differential distinguish attack on 4-round SHA3-512 is performed. The success rate of this attack is 99%, where the data complexity is 2~(8.21) messages and the corresponding time complexity is 2~(8.21). We did some experiments to verify the above theoretical results by taking SHA-512 as the random function, and it shows that the complexity of our attack is better than other methods in the same number of rounds.
引文
[1]BERTONI G,DAEMEN J,PEETERS M,et al.The Keccak reference[J].Submission to NIST(Round 3),2011,13:14-15.
[2]DINUR I,DUNKELMAN O,SHAMIR A.New attacks on Keccak-224 and Keccak-256[C].In:International Workshop on Fast Software Encryption—FSE 2012.Springer Berlin Heidelberg,2012:442-461.
[3]DINUR I,DUNKELMAN O,SHAMIR A.Collision attacks on up to 5 rounds of SHA-3 using generalized internal differentials[C].In:International Workshop on Fast Software Encryption—FSE 2013.Springer Berlin Heidelberg,2013:219-240.
[4]K(O)LBL S,MENDEL F,NAD T,et al.Differential cryptanalysis of Keccak variants[C].In:IMA International Conference on Cryptography and Coding-IMACC 2013.Springer Berlin Heidelberg,2013:141-157.
[5]QIAO K,SONG L,LIU M,et.al.New collision attacks on round-reduced Keccak[C].In:Advances in Cryptology-EUROCHYPT 2017.Springer Cham,2017:216-243.
[6]MORAWIECKI P,SREBRNY M.A SAT-based preimage analysis of reduced Keccak hash functions[J].Information Processing Letters,2013,113(10-11):392-397.
[7]MORAWIECKI P,PIEPRZYK J,SREBRNY M.Rotational cryptanalysis of round-reduced Keccak[C].In:International Workshop on Fast Software Encryption—FSE 2013.Springer Berlin Heidelberg,2013:241 262.
[8]MORAWIECKI P,PIEPRZYK J,SREBRNY M,et al.Preimage attacks on the round-reduced Keccak with the aid of differential cryptanalysis[J].IACR Cryptology ePrint Archive,2013,2013:561.
[9]GUO J,LIU M,SONG L.Linear structures:Applications to cryptanalysis of round-reduced Keccak[C].In:Advances in Cryptology—ASIACRYPT 2016.Springer Berlin Heidelberg,2016:249-274.
[10]AMY M,DI MATTEO O,GHEORGHIU V,et.al.Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3[J].arXiv preprint.arXiv,2016:1603.09383.
[11]BERNSTEIN D J.Second preimages for 6/7/8 rounds of Keccak[J].NIST Mailing List,2010.
[12]NAYA-PLASENCIA M,ROCK A,MEIER W.Practical analysis of reduced-round Keccak[C].In:Progress in Cryptology—INDOCRYPT 2011.Springer Berlin Heidelberg,2011:236-254.
[13]DAS S,MEIER W.Differential biases in reduced-round Keccak[C].In:Progress in Cryptology—AFRICACRYPT2014.Springer Cham,2014:69 87.
[14]SAHA D,KUILA S,CHOWDHURY D R.SymSum:Symmetric-sum distinguishers against round reduced SHA3[J].IACR Transactions on Symmetric Cryptology,2017,2017(1):240-258.
[15]HUANG S,WANG X,XU G,et al.Conditional cube attack on reduced-round Keccak sponge function[C].In:Advances in Cryptology-EUROCRYPT 2017,PartⅡ.Springer Cham,2017:259-288.
[16]DINUR I,MORAWIECKI P,PIEPRZYK J,et al.Practical complexity cube attacks on round-reduced Keccak sponge function[J].IACR Cryptology ePrint Archive,2014,2014:259.
[17]DINUR I,MORAWIECKI P,PIEPRZYK J,et al.Cube attacks and cube-attack-like cryptanalysis on the roundreduced Keccak sponge function[C].In:Advances in Cryptology—EUROCRYPT 2015,Part I.Springer Berlin Heidelberg,2015:733-761.
[18]DONG X,LI Z,WANG X,et al.Cube-like attack on round-reduced initialization of Ketje Sr[J].IACR Transactions on Symmetric Cryptology,2017,2017(1):259-280.
[19]AUMASSON J P,MEIER W.Zero-sum distinguishers for reduced Keccak-f and for the core functions of Luffa and Hamsi[J].Rump Session of Cryptographic Hardware and Embedded Systems-CHES,2009.Springer Berlin Heidelberg,2009:67.
[20]BOURA C,CANTEAUT A.A zero-sum property for the Keccak-f permutation with 18 rounds[C].In:International Symposium on Information Theory—ISIT 2010.IEEE,2010:2488-2492.
[21]BOURA C,CANTEAUT A.Zero-sum distinguishers for iterated permutations and application to Keccak-f and Hamsi-256[C].In:Selected Areas in Cryptography-SAC 2010.Springer Berlin Heidelberg,2010:1-17.
[22]BOURA C,CANTEAUT A,DE CANNIERE C.Higher-order differential properties of Keccak and Luffa[C].In:Fast Software Encryption—FSE 2011.Springer Berlin Heidelberg,2011:252-269.
[23]DUAN M,LAI X J.Improved zero-sum distinguisher for full round Keccak-f permutation[J].Chinese Science Bulletin,2012,57(6):694-697.
[24]DUC A,GUO.J,PEYRIN T,et al.Unaligned rebound attack:Application to Keccak[C].In:Fast Software Encryption—FSE 2012.Springer Berlin Heidelberg,2012:402-421.
[25]JEAN J,NIKOLIC I.Internal differential boomerangs:Practical analysis of the round-reduced Keccak-f permutation[C].In:Fast Software Encryption—FSE 2015.Springer Berlin Heidelberg,2015:537-556.
[26]KUILA S,SAHA D,PAL M,et al.Practical distinguishers against 6-round Keccak-f exploiting self-symmetry[C].In:Progress in Cryptology—AFRICACRYPT 2014.Springer Cham,2014:88-108.
[27]DWORKIN M J.SHA-3 standard:Permutation-based hash and extendable-output functions[J].Federal Information Processing Standards Publication,2015:(NIST FIPS)-202.
[28]K(U|¨)HN U.Improved cryptanalysis of MISTY1[C].In:Fast Software Encryption—FSE 2002.Springer Berlin Heidelberg,2002:61-75.
[2]DINUR I,DUNKELMAN O,SHAMIR A.New attacks on Keccak-224 and Keccak-256[C].In:International Workshop on Fast Software Encryption—FSE 2012.Springer Berlin Heidelberg,2012:442-461.
[3]DINUR I,DUNKELMAN O,SHAMIR A.Collision attacks on up to 5 rounds of SHA-3 using generalized internal differentials[C].In:International Workshop on Fast Software Encryption—FSE 2013.Springer Berlin Heidelberg,2013:219-240.
[4]K(O)LBL S,MENDEL F,NAD T,et al.Differential cryptanalysis of Keccak variants[C].In:IMA International Conference on Cryptography and Coding-IMACC 2013.Springer Berlin Heidelberg,2013:141-157.
[5]QIAO K,SONG L,LIU M,et.al.New collision attacks on round-reduced Keccak[C].In:Advances in Cryptology-EUROCHYPT 2017.Springer Cham,2017:216-243.
[6]MORAWIECKI P,SREBRNY M.A SAT-based preimage analysis of reduced Keccak hash functions[J].Information Processing Letters,2013,113(10-11):392-397.
[7]MORAWIECKI P,PIEPRZYK J,SREBRNY M.Rotational cryptanalysis of round-reduced Keccak[C].In:International Workshop on Fast Software Encryption—FSE 2013.Springer Berlin Heidelberg,2013:241 262.
[8]MORAWIECKI P,PIEPRZYK J,SREBRNY M,et al.Preimage attacks on the round-reduced Keccak with the aid of differential cryptanalysis[J].IACR Cryptology ePrint Archive,2013,2013:561.
[9]GUO J,LIU M,SONG L.Linear structures:Applications to cryptanalysis of round-reduced Keccak[C].In:Advances in Cryptology—ASIACRYPT 2016.Springer Berlin Heidelberg,2016:249-274.
[10]AMY M,DI MATTEO O,GHEORGHIU V,et.al.Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3[J].arXiv preprint.arXiv,2016:1603.09383.
[11]BERNSTEIN D J.Second preimages for 6/7/8 rounds of Keccak[J].NIST Mailing List,2010.
[12]NAYA-PLASENCIA M,ROCK A,MEIER W.Practical analysis of reduced-round Keccak[C].In:Progress in Cryptology—INDOCRYPT 2011.Springer Berlin Heidelberg,2011:236-254.
[13]DAS S,MEIER W.Differential biases in reduced-round Keccak[C].In:Progress in Cryptology—AFRICACRYPT2014.Springer Cham,2014:69 87.
[14]SAHA D,KUILA S,CHOWDHURY D R.SymSum:Symmetric-sum distinguishers against round reduced SHA3[J].IACR Transactions on Symmetric Cryptology,2017,2017(1):240-258.
[15]HUANG S,WANG X,XU G,et al.Conditional cube attack on reduced-round Keccak sponge function[C].In:Advances in Cryptology-EUROCRYPT 2017,PartⅡ.Springer Cham,2017:259-288.
[16]DINUR I,MORAWIECKI P,PIEPRZYK J,et al.Practical complexity cube attacks on round-reduced Keccak sponge function[J].IACR Cryptology ePrint Archive,2014,2014:259.
[17]DINUR I,MORAWIECKI P,PIEPRZYK J,et al.Cube attacks and cube-attack-like cryptanalysis on the roundreduced Keccak sponge function[C].In:Advances in Cryptology—EUROCRYPT 2015,Part I.Springer Berlin Heidelberg,2015:733-761.
[18]DONG X,LI Z,WANG X,et al.Cube-like attack on round-reduced initialization of Ketje Sr[J].IACR Transactions on Symmetric Cryptology,2017,2017(1):259-280.
[19]AUMASSON J P,MEIER W.Zero-sum distinguishers for reduced Keccak-f and for the core functions of Luffa and Hamsi[J].Rump Session of Cryptographic Hardware and Embedded Systems-CHES,2009.Springer Berlin Heidelberg,2009:67.
[20]BOURA C,CANTEAUT A.A zero-sum property for the Keccak-f permutation with 18 rounds[C].In:International Symposium on Information Theory—ISIT 2010.IEEE,2010:2488-2492.
[21]BOURA C,CANTEAUT A.Zero-sum distinguishers for iterated permutations and application to Keccak-f and Hamsi-256[C].In:Selected Areas in Cryptography-SAC 2010.Springer Berlin Heidelberg,2010:1-17.
[22]BOURA C,CANTEAUT A,DE CANNIERE C.Higher-order differential properties of Keccak and Luffa[C].In:Fast Software Encryption—FSE 2011.Springer Berlin Heidelberg,2011:252-269.
[23]DUAN M,LAI X J.Improved zero-sum distinguisher for full round Keccak-f permutation[J].Chinese Science Bulletin,2012,57(6):694-697.
[24]DUC A,GUO.J,PEYRIN T,et al.Unaligned rebound attack:Application to Keccak[C].In:Fast Software Encryption—FSE 2012.Springer Berlin Heidelberg,2012:402-421.
[25]JEAN J,NIKOLIC I.Internal differential boomerangs:Practical analysis of the round-reduced Keccak-f permutation[C].In:Fast Software Encryption—FSE 2015.Springer Berlin Heidelberg,2015:537-556.
[26]KUILA S,SAHA D,PAL M,et al.Practical distinguishers against 6-round Keccak-f exploiting self-symmetry[C].In:Progress in Cryptology—AFRICACRYPT 2014.Springer Cham,2014:88-108.
[27]DWORKIN M J.SHA-3 standard:Permutation-based hash and extendable-output functions[J].Federal Information Processing Standards Publication,2015:(NIST FIPS)-202.
[28]K(U|¨)HN U.Improved cryptanalysis of MISTY1[C].In:Fast Software Encryption—FSE 2002.Springer Berlin Heidelberg,2002:61-75.