New Insights into Divide-and-Conquer Attacks on the Round-Reduced Keccak-MAC
|
摘要
Keccak is the final winner of SHA-3 competition and it can be used as message authentic codes as well. The basic and balanced divide-and-conquer attacks on Keccak-MAC were proposed by Dinur et al.at Eurocrypt 2015. The idea of cube attacks is used in the two attacks to divide key bits into small portions. By carefully analysing the mappings used in Keccak-MAC, it is found that some cube variables could divide key bits into smaller portions and so better divide-and-conquer attacks are obtained. In order to evaluate the resistance of Keccak-MAC against divide-and-conquer attacks based on cubes, we theoretically analyse the lower bounds of the complexities of divide-and-conquer attacks. It is shown that the lower bounds of the complexities are still not better than those of the conditional cube tester proposed by Senyang Huang et al.. This indicates that KeccakMAC can resist the divide-and-conquer attack better than the conditional cube tester. We hope that these techniques still could provide some new insights on the future cryptanalysis of Keccak.
Keccak is the final winner of SHA-3 competition and it can be used as message authentic codes as well. The basic and balanced divide-and-conquer attacks on Keccak-MAC were proposed by Dinur et al.at Eurocrypt 2015. The idea of cube attacks is used in the two attacks to divide key bits into small portions. By carefully analysing the mappings used in Keccak-MAC, it is found that some cube variables could divide key bits into smaller portions and so better divide-and-conquer attacks are obtained. In order to evaluate the resistance of Keccak-MAC against divide-and-conquer attacks based on cubes, we theoretically analyse the lower bounds of the complexities of divide-and-conquer attacks. It is shown that the lower bounds of the complexities are still not better than those of the conditional cube tester proposed by Senyang Huang et al.. This indicates that KeccakMAC can resist the divide-and-conquer attack better than the conditional cube tester. We hope that these techniques still could provide some new insights on the future cryptanalysis of Keccak.
Keccak is the final winner of SHA-3 competition and it can be used as message authentic codes as well. The basic and balanced divide-and-conquer attacks on Keccak-MAC were proposed by Dinur et al.at Eurocrypt 2015. The idea of cube attacks is used in the two attacks to divide key bits into small portions. By carefully analysing the mappings used in Keccak-MAC, it is found that some cube variables could divide key bits into smaller portions and so better divide-and-conquer attacks are obtained. In order to evaluate the resistance of Keccak-MAC against divide-and-conquer attacks based on cubes, we theoretically analyse the lower bounds of the complexities of divide-and-conquer attacks. It is shown that the lower bounds of the complexities are still not better than those of the conditional cube tester proposed by Senyang Huang et al.. This indicates that KeccakMAC can resist the divide-and-conquer attack better than the conditional cube tester. We hope that these techniques still could provide some new insights on the future cryptanalysis of Keccak.
引文
[1]B.Guido,D.Joan,P.Micha?l,et al.,“Keccak sponge function family main document”,available at http://Keccak.noekeon.org/Keccak-main-2.1.pdf,2018-9-3.
[2]P.Morawiecki and M.Srebrny,et al.,“A SAT-based preimage analysis of reduced Keccak hash functions”,Information Processing Letters,Vol.113,No.10-11,pp.392-397,2013.
[3]D.J.Bernstein,“Second preimages for 6(7(8))rounds of keccak”,https://ehash.iaik.tugraz.at/uploads/6/65/NIST-mailing-list_Bernstein-Daemen.txt,2018-9-3.
[4]M.Naya-Plasencia,A.Rock and W.Meier,“Practical analysis of reduced-round keccak”,Proc.of International Conference on Cryptology in India,Chennai,India,pp.236-254,2011.
[5]I.Dinur,O.Dunkelman and A.Shamir,“Improved practical attacks on round-reduced Keccak”,Journal of Cryptology,Vol.27,No.2,pp.183-209,2014.
[6]K.Qiao,L.Song,M.Liu,et al.,“New collision attacks on round-reduced Keccak”,Proc.of Advances in CryptologyEUROCRYPT 2017,Paris,France,pp.216-243,2017.
[7]L.Song,G.Liao and J.Guo,“Non-full Sbox linearization:Applications to collision attacks on round-Reduced keccak”,Proc.Advances in Cryptology-CRYPTO 2017,Santa Barbara,USA,pp.428-451,2017.
[8]S.Das and W.Meier,“Differential biases in reduced-round keccak”,Proc.of International Conference on Cryptology in Africa,Marrakesh,Morocco,pp.69-87,2014.
[9]C.Boura and A.Canteaut“Zero-Sum distinguishers for iterated permutations and application to Keccak-f and Hamsi-256”,Proc.of Selected Areas in Cryptography,Waterloo,Canada,pp.1-17,2010.
[10]C.Boura,A.Canteaut and C.De Cannire,“Higher-order differential properties of keccak and luffa”,Proc.of Fast Software Encryption 2011,Lyngby,Denmark,pp.252-269,2011.
[11]M.Duan and X.J.Lai,“Improved zero-sum distinguisher for full round Keccak-f permutation”,Chinese Science Bulletin,Vol.57,No.6,pp.694-697,2012.
[12]M.Li and L.Cheng,“Distinguishing property for full round Keccak-f permutation”,Proc.of CISIS-2017,Torino,Italy,pp.639-646,2017.
[13]J.Jean and I.Nikolic,“Internal differential boomerangs:Practical analysis of the round-reduced keccak-f permutation”,Proc.of Fast Software Encryption 2015,Istanbul,Turkey,pp.537-556,2017.
[14]J.Guo,M.Liu and L.Song,“Linear structures:Applications to cryptanalysis of round-reduced Keccak”,Proc.of Advances in Cryptology-ASIACRYPT 2016,Hanoi,Vietnam,pp.249-274,2016.
[15]B.Guido,D.Joan,P.Micha?l,et al.,“Keyak”,http://Keyak.noekeon.org,2018-9-3.
[16]I.Dinur,P.Morawiecki,J.Pieprzyk,et al.,“Cube attacks and cube-attack-like cryptanalysis on the round-reduced keccak sponge function”,Proc.of Advances in CryptologyEUROCRYPT 2015,Sofia,Bulgaria,pp.733-761,2015.
[17]S.Y.Huang,X.Y.Wang,G.W.Xu,et al.,“Conditional cube attack on reduced-round keccak sponge function”,Proc.of Advances in Cryptology-EUROCRYPT 2017,Paris,France,pp.259-288,2017.
[18]I.Dinur and A.Shamir,“Cube attacks on tweakable black box polynomials”,Proc.of Advances in CryptologyEUROCRYPT 2009,Cologne,Germany,pp.278-299,2009.
[2]P.Morawiecki and M.Srebrny,et al.,“A SAT-based preimage analysis of reduced Keccak hash functions”,Information Processing Letters,Vol.113,No.10-11,pp.392-397,2013.
[3]D.J.Bernstein,“Second preimages for 6(7(8))rounds of keccak”,https://ehash.iaik.tugraz.at/uploads/6/65/NIST-mailing-list_Bernstein-Daemen.txt,2018-9-3.
[4]M.Naya-Plasencia,A.Rock and W.Meier,“Practical analysis of reduced-round keccak”,Proc.of International Conference on Cryptology in India,Chennai,India,pp.236-254,2011.
[5]I.Dinur,O.Dunkelman and A.Shamir,“Improved practical attacks on round-reduced Keccak”,Journal of Cryptology,Vol.27,No.2,pp.183-209,2014.
[6]K.Qiao,L.Song,M.Liu,et al.,“New collision attacks on round-reduced Keccak”,Proc.of Advances in CryptologyEUROCRYPT 2017,Paris,France,pp.216-243,2017.
[7]L.Song,G.Liao and J.Guo,“Non-full Sbox linearization:Applications to collision attacks on round-Reduced keccak”,Proc.Advances in Cryptology-CRYPTO 2017,Santa Barbara,USA,pp.428-451,2017.
[8]S.Das and W.Meier,“Differential biases in reduced-round keccak”,Proc.of International Conference on Cryptology in Africa,Marrakesh,Morocco,pp.69-87,2014.
[9]C.Boura and A.Canteaut“Zero-Sum distinguishers for iterated permutations and application to Keccak-f and Hamsi-256”,Proc.of Selected Areas in Cryptography,Waterloo,Canada,pp.1-17,2010.
[10]C.Boura,A.Canteaut and C.De Cannire,“Higher-order differential properties of keccak and luffa”,Proc.of Fast Software Encryption 2011,Lyngby,Denmark,pp.252-269,2011.
[11]M.Duan and X.J.Lai,“Improved zero-sum distinguisher for full round Keccak-f permutation”,Chinese Science Bulletin,Vol.57,No.6,pp.694-697,2012.
[12]M.Li and L.Cheng,“Distinguishing property for full round Keccak-f permutation”,Proc.of CISIS-2017,Torino,Italy,pp.639-646,2017.
[13]J.Jean and I.Nikolic,“Internal differential boomerangs:Practical analysis of the round-reduced keccak-f permutation”,Proc.of Fast Software Encryption 2015,Istanbul,Turkey,pp.537-556,2017.
[14]J.Guo,M.Liu and L.Song,“Linear structures:Applications to cryptanalysis of round-reduced Keccak”,Proc.of Advances in Cryptology-ASIACRYPT 2016,Hanoi,Vietnam,pp.249-274,2016.
[15]B.Guido,D.Joan,P.Micha?l,et al.,“Keyak”,http://Keyak.noekeon.org,2018-9-3.
[16]I.Dinur,P.Morawiecki,J.Pieprzyk,et al.,“Cube attacks and cube-attack-like cryptanalysis on the round-reduced keccak sponge function”,Proc.of Advances in CryptologyEUROCRYPT 2015,Sofia,Bulgaria,pp.733-761,2015.
[17]S.Y.Huang,X.Y.Wang,G.W.Xu,et al.,“Conditional cube attack on reduced-round keccak sponge function”,Proc.of Advances in Cryptology-EUROCRYPT 2017,Paris,France,pp.259-288,2017.
[18]I.Dinur and A.Shamir,“Cube attacks on tweakable black box polynomials”,Proc.of Advances in CryptologyEUROCRYPT 2009,Cologne,Germany,pp.278-299,2009.