缩减轮数的Keccak区分器攻击
|
摘要
2012年,Keccak在SHA-3算法竞赛中脱颖而出成为SHA-3算法标准.自此之后对Keccak算法的分析成为研究热点.本文探究的是对缩减轮Keccak杂凑函数的差分区分器攻击.在已有研究中,Sourav和Meier等提出了一种6轮的Keccak区分器,该区分器基于TDA算法、Double Kernel结构和Keccak内部置换的差分传播特性,得到的区分器复杂度为2~(52).本文在上述结果的基础上,首先改进了Willi Meier等提出的差分路径,得到了一个更优的6轮差分区分器,该结果为目前已知最好的6轮差分区分器,数据复杂度为2~(28);接着文章探究7轮的差分区分器,按照新的差分路径,文章得到了新的7轮差分区分器,但是因为在差分路径中Keccak内部函数的扩散作用,增大了得到该差分路径的数据复杂度.文章通过对于S盒性质的分析,提出了一种S盒控制技术,通过忽略一些对结果中的偏置位没有影响的S盒,能够很好地降低得到该区分器的数据复杂度,从而保证在7轮之后的输出中存在偏置位,得到了一个复杂度为2~(68)的7轮Keccak区分器.
The Keccak hash function is the winner of NIST's SHA-3 competition. The best cryptanalysis result for the differential distinguisher attack on the hash function settings of Keccak is a6 round distinguisher proposed by Sourav Das and Willi Meier, which is based on TDA algorithm,Double Kernel structure and differential propagation characteristics. This paper improves the result and obtains a 6-round distinguisher with the best known complexity of the same kind of distinguishers.Moreover, an S-Box control method is proposed, which finds out the influence of each active S-Box on the output difference. Combing the S-Box control method and the 6-round distinguisher mentioned above, a distinguisher on 7 rounds of Keccak hash function is found with complexity being 2~(68).
The Keccak hash function is the winner of NIST's SHA-3 competition. The best cryptanalysis result for the differential distinguisher attack on the hash function settings of Keccak is a6 round distinguisher proposed by Sourav Das and Willi Meier, which is based on TDA algorithm,Double Kernel structure and differential propagation characteristics. This paper improves the result and obtains a 6-round distinguisher with the best known complexity of the same kind of distinguishers.Moreover, an S-Box control method is proposed, which finds out the influence of each active S-Box on the output difference. Combing the S-Box control method and the 6-round distinguisher mentioned above, a distinguisher on 7 rounds of Keccak hash function is found with complexity being 2~(68).
引文
[1]WANG X,YU H.How to break MD5 and other hash functions[C].In:Annual International Conference on the Theory and Applications of Cryptographic Techniques.Springer Berlin Heidelberg,2005:19-35.
[2]WANG X,YIN Y L,YU H.Finding collisions in the full SHA-1[C].In:Annual International Cryptology Conference.Springer Berlin Heidelberg,2005:17-36.
[3]STEVENS M,BURSZTEIN E,KARPMAN P,et al.The first collision for full SHA-1[J].Cryptology ePrint Archive,Report 2017/190,2017.
[4]ISOBE T,SHIBUTANI K.Preimage attacks on reduced Tiger and SHA-2[C].In:Proceedings of 16th International Workshop on Fast Software Encryption.Springer Berlin Heidelberg,2009:139-155.
[5]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].In:Proceedings of 16th International Conference on the Theory and Application of Cryptology and Information Security.Springer Berlin Heidelberg,2010:56-75.
[6]KHOVRATOVICH D,RECHBERGER C,SAVELIEVA A.Bicliques for preimages:attacks on Skein-512 and the SHA-2 family[C].In:Proceedings of 19th International Workshop on Fast Software Encryption.Springer Berlin Heidelberg,2012:244-263.
[7]MENDEL F,PRAMSTALLER N,RECHBERGER C,et al.Analysis of step-reduced SHA-256[C].In:Proceedings of 13th International Workshop on Fast Software Encryption.Springer Berlin Heidelberg,2006:126-143.
[8]SAN ADHYA S K,SARK AR P.New collision attacks against up to 24-step SHA-2[C].In:Proceedings of 9th International Conference on Cryptology in India,2008.Springer Berlin Heidelberg,2008:91-103.
[9]NIKOLIC I,BIRYUKOY A.Collisions for step-reduced SHA-256[C].In:Proceedings of 15th International Workshop on Fast Software Encryption.Springer Berlin Heidelberg,2008:1-15.
[10]INDESTEEGE S,MENDEL F,PRENEEL B,et al.Collisions and other non-random properties for step-reduced SHA-256[C].In:Proceedings of 15th International Workshop on Selected Areas in Cryptography.Springer Berlin Heidelberg,2008:276-293.
[11]MENDEL F,NAD T,SCHLAFFER M.Finding SHA-2 characteristics:searching through a minefield of contradictions[C].In:Advances in Cryptology-ASIACRYPT 2011.Springer Berlin Heidelberg,2011:288-307.
[12]MENDEL F,NAD T,SCHLAFFER M.Improving local collisions:new attacks on reduced SHA-256[C].In:Annual International Conference on the Theory and Applications of Cryptographic Techniques.Springer Berlin Heidelberg,2013:262-278
[13]BERTONI G,DAEMEN J,PEETERS M,et al.The keccak sha-3 submission[R].submission to NIST(round3)(2011).
[14]DINUR I,DUNKELMAN O,SHAMIR A.New attacks on keccak-224 and keccak-256[C].In:Fast Software Encryption.Springer Berlin Heidelberg,2012:442-461.
[15]DINUR I,DUNKELMAN O,SHAMIR A.Collision attacks on up to 5 rounds of sha-3 using generalized internal differentials[C].In:Fast Software Encryption.Springer Berlin Heidelberg,2013:219-240.
[16]NAVA-PLASENCIA M,R(O|¨)CK A,et al.Practical analysis of reduced-round Keccak[C].In:Bernstein,D.J.,Chatterjee,S.(eds.)INDOCRYPT 2011.Springer Berlin Heidelberg,2011:236-254.
[17]MORAWIECKI P,PIEPRZYK,SREBRNY M.Rotational cryptanalysis of round-reduced Keccak[J].In:International Workshop on Fast Software Encryption.Springer Berlin Heidelberg,2013:241-262.
[18]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.
[19]AUMASSON J P,MEIER W.Zero-sum distinguishers for reduced Keccak-f and for the core functions of Luffa and Hamsi[C].In:Rump Session of Cryptographic Hardware and Embedded Systems—CHES 2009.Springer Berlin Heidelberg,2009:67.
[20]BOURA C,CANTEAUT A.Zero-sum distinguishers for iterated permutations and application to Keccak-f and Hamsi-256[C].In:Proceedings of the 17th International Workshop on Selected Areas in Cryptography 2010.LNCS Springer Press,2010:1-17.
[21]DUAN M,LAI X J.Improved zero-sum distinguisher for full round Keccak-f permutation[J].Chinese Science Bulletin,2012,57(6):694-697.
[22]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.
[23]JEAN J,NIKOLII.Internal Dierential boomerangs:practical analysis of the round-reduced Keccak-f permutation[C].In:Fast Software Encryption—FSE 2015.Springer Berlin Heidelberg,2015:537-556.
[24]NAVA-PLASENCIA M,ROCK A,Willi M.Practical analysis of reduced-round keccak[C].In:Progress in Cryptology—INDOCRYPT 2011.Springer Berlin Heidelberg,2011:236-254.
[25]DAS S,MEIER W.Differential biases in reduced-round keccak[C].In Progress in Cryptology—AFRICACRYPT2014.Springer Berlin Heidelberg,2014:69-87.
[26]DINUR I,MORAWIECKI P,PIEPRZYK J,et al.Cube attacks and cube-attack-like cryptanalysis on the round-reduced Keccak sponge function[C].In:Advances in Cryptology—EUROCRYPT 2015.Springer Berlin Heidelberg,2015:733-761.
[27]HUANG S Y,WANG X,XU G W,et al.Conditional cube attack on reduced-round keccak sponge function[J].Cryptology ePrint Archive,Report 2016/790,2016.
[28]DINUR I,DUNKELMAN O,SHAMIR A.Improved practical attacks on round-reduced Keccak[J].Journal of Cryptology,2014,27(2):183-209.
[2]WANG X,YIN Y L,YU H.Finding collisions in the full SHA-1[C].In:Annual International Cryptology Conference.Springer Berlin Heidelberg,2005:17-36.
[3]STEVENS M,BURSZTEIN E,KARPMAN P,et al.The first collision for full SHA-1[J].Cryptology ePrint Archive,Report 2017/190,2017.
[4]ISOBE T,SHIBUTANI K.Preimage attacks on reduced Tiger and SHA-2[C].In:Proceedings of 16th International Workshop on Fast Software Encryption.Springer Berlin Heidelberg,2009:139-155.
[5]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].In:Proceedings of 16th International Conference on the Theory and Application of Cryptology and Information Security.Springer Berlin Heidelberg,2010:56-75.
[6]KHOVRATOVICH D,RECHBERGER C,SAVELIEVA A.Bicliques for preimages:attacks on Skein-512 and the SHA-2 family[C].In:Proceedings of 19th International Workshop on Fast Software Encryption.Springer Berlin Heidelberg,2012:244-263.
[7]MENDEL F,PRAMSTALLER N,RECHBERGER C,et al.Analysis of step-reduced SHA-256[C].In:Proceedings of 13th International Workshop on Fast Software Encryption.Springer Berlin Heidelberg,2006:126-143.
[8]SAN ADHYA S K,SARK AR P.New collision attacks against up to 24-step SHA-2[C].In:Proceedings of 9th International Conference on Cryptology in India,2008.Springer Berlin Heidelberg,2008:91-103.
[9]NIKOLIC I,BIRYUKOY A.Collisions for step-reduced SHA-256[C].In:Proceedings of 15th International Workshop on Fast Software Encryption.Springer Berlin Heidelberg,2008:1-15.
[10]INDESTEEGE S,MENDEL F,PRENEEL B,et al.Collisions and other non-random properties for step-reduced SHA-256[C].In:Proceedings of 15th International Workshop on Selected Areas in Cryptography.Springer Berlin Heidelberg,2008:276-293.
[11]MENDEL F,NAD T,SCHLAFFER M.Finding SHA-2 characteristics:searching through a minefield of contradictions[C].In:Advances in Cryptology-ASIACRYPT 2011.Springer Berlin Heidelberg,2011:288-307.
[12]MENDEL F,NAD T,SCHLAFFER M.Improving local collisions:new attacks on reduced SHA-256[C].In:Annual International Conference on the Theory and Applications of Cryptographic Techniques.Springer Berlin Heidelberg,2013:262-278
[13]BERTONI G,DAEMEN J,PEETERS M,et al.The keccak sha-3 submission[R].submission to NIST(round3)(2011).
[14]DINUR I,DUNKELMAN O,SHAMIR A.New attacks on keccak-224 and keccak-256[C].In:Fast Software Encryption.Springer Berlin Heidelberg,2012:442-461.
[15]DINUR I,DUNKELMAN O,SHAMIR A.Collision attacks on up to 5 rounds of sha-3 using generalized internal differentials[C].In:Fast Software Encryption.Springer Berlin Heidelberg,2013:219-240.
[16]NAVA-PLASENCIA M,R(O|¨)CK A,et al.Practical analysis of reduced-round Keccak[C].In:Bernstein,D.J.,Chatterjee,S.(eds.)INDOCRYPT 2011.Springer Berlin Heidelberg,2011:236-254.
[17]MORAWIECKI P,PIEPRZYK,SREBRNY M.Rotational cryptanalysis of round-reduced Keccak[J].In:International Workshop on Fast Software Encryption.Springer Berlin Heidelberg,2013:241-262.
[18]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.
[19]AUMASSON J P,MEIER W.Zero-sum distinguishers for reduced Keccak-f and for the core functions of Luffa and Hamsi[C].In:Rump Session of Cryptographic Hardware and Embedded Systems—CHES 2009.Springer Berlin Heidelberg,2009:67.
[20]BOURA C,CANTEAUT A.Zero-sum distinguishers for iterated permutations and application to Keccak-f and Hamsi-256[C].In:Proceedings of the 17th International Workshop on Selected Areas in Cryptography 2010.LNCS Springer Press,2010:1-17.
[21]DUAN M,LAI X J.Improved zero-sum distinguisher for full round Keccak-f permutation[J].Chinese Science Bulletin,2012,57(6):694-697.
[22]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.
[23]JEAN J,NIKOLII.Internal Dierential boomerangs:practical analysis of the round-reduced Keccak-f permutation[C].In:Fast Software Encryption—FSE 2015.Springer Berlin Heidelberg,2015:537-556.
[24]NAVA-PLASENCIA M,ROCK A,Willi M.Practical analysis of reduced-round keccak[C].In:Progress in Cryptology—INDOCRYPT 2011.Springer Berlin Heidelberg,2011:236-254.
[25]DAS S,MEIER W.Differential biases in reduced-round keccak[C].In Progress in Cryptology—AFRICACRYPT2014.Springer Berlin Heidelberg,2014:69-87.
[26]DINUR I,MORAWIECKI P,PIEPRZYK J,et al.Cube attacks and cube-attack-like cryptanalysis on the round-reduced Keccak sponge function[C].In:Advances in Cryptology—EUROCRYPT 2015.Springer Berlin Heidelberg,2015:733-761.
[27]HUANG S Y,WANG X,XU G W,et al.Conditional cube attack on reduced-round keccak sponge function[J].Cryptology ePrint Archive,Report 2016/790,2016.
[28]DINUR I,DUNKELMAN O,SHAMIR A.Improved practical attacks on round-reduced Keccak[J].Journal of Cryptology,2014,27(2):183-209.