Skip to main content
Erschienen in: Designs, Codes and Cryptography 6/2019

23.08.2018

MILP-aided cube-attack-like cryptanalysis on Keccak Keyed modes

verfasst von: Wenquan Bi, Xiaoyang Dong, Zheng Li, Rui Zong, Xiaoyun Wang

Erschienen in: Designs, Codes and Cryptography | Ausgabe 6/2019

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Cube-attack-like cryptanalysis was proposed by Dinur et al. at EUROCRYPT 2015, which recovers the key of Keccak keyed modes in a divide-and-conquer manner. In their attack, one selects cube variables manually, which leads to more key bits involved in the key-recovery attack, so the complexity is too high unnecessarily. In this paper, we introduce a new MILP model and make the cube attacks better on the Keccak keyed modes. Using this new MILP tool, we find the optimal cube variables for Keccak-MAC, Keyak and Ketje, which makes that a minimum number of key bits are involved in the key-recovery attack. For example, when the capacity is 256, we find a new 32-dimension cube for Keccak-MAC that involves only 18 key bits instead of Dinur et al.’s 64 bits and the complexity of the 6-round attack is reduced to \(2^{42}\) from \(2^{66}\). More impressively, using this new tool, we give the very first 7-round key-recovery attack on Keccak-MAC-512. We get the 8-round key-recovery attacks on Lake Keyak in nonce-respected setting. In addition, we get the best attacks on Ketje Major/Minor. For Ketje Major, when the length of nonce is 9 lanes, we could improve the best previous 6-round attack to 7-round. Our attacks do not threaten the full-round (12) Keyak/Ketje or the full-round (24) Keccak-MAC. When comparing with Huang et al.’s conditional cube attack, the MILP-aided cube-attack-like cryptanalysis has larger effective range and gets the best results on the Keccak keyed variants with relatively smaller number of degrees of freedom.
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
In Keccak-MAC, the capacity is larger, the number of degrees of freedom is smaller; in Keyak and Ketje, the nonce or size of state is smaller, the number of degrees of freedom is smaller.
 
Literatur
4.
Zurück zum Zitat Bertoni G., Daemen J., Peeters M., Assche G.V.: Duplexing the sponge: singlepass authenticated encryption and other applications. In: SAC 2011, pp. 320–337 (2011). Bertoni G., Daemen J., Peeters M., Assche G.V.: Duplexing the sponge: singlepass authenticated encryption and other applications. In: SAC 2011, pp. 320–337 (2011).
5.
Zurück zum Zitat Bi W., Li Z., Dong X., Li L., Wang X.: Conditional cube attack on roundreduced river keyak. Des. Codes Cryptogr. 86, 1295–1310 (2017).CrossRefMATH Bi W., Li Z., Dong X., Li L., Wang X.: Conditional cube attack on roundreduced river keyak. Des. Codes Cryptogr. 86, 1295–1310 (2017).CrossRefMATH
6.
Zurück zum Zitat Cui T., Jia K., Fu K., Chen S., Wang M.: New automatic search tool for impossible differentials and zero-correlation linear approximations. In: IACR Cryptology ePrint Archive, 2016/689 (2016). Cui T., Jia K., Fu K., Chen S., Wang M.: New automatic search tool for impossible differentials and zero-correlation linear approximations. In: IACR Cryptology ePrint Archive, 2016/689 (2016).
7.
Zurück zum Zitat Daemen J., Van Assche G.: Differential propagation analysis of Keccak. In: FSE 2012, vol. 7549, pp. 422–441. Springer, New York (2012). Daemen J., Van Assche G.: Differential propagation analysis of Keccak. In: FSE 2012, vol. 7549, pp. 422–441. Springer, New York (2012).
8.
Zurück zum Zitat Dinur I., Shamir A.: Cube attacks on tweakable black box polynomials. In: EUROCRYPT 2009, pp. 278–299 (2009). Dinur I., Shamir A.: Cube attacks on tweakable black box polynomials. In: EUROCRYPT 2009, pp. 278–299 (2009).
9.
Zurück zum Zitat Dinur I., Dunkelman O., Shamir A.: New attacks on Keccak-224 and Keccak-256. In: FSE 2012. pp. 442–461. Springer, New York (2012). Dinur I., Dunkelman O., Shamir A.: New attacks on Keccak-224 and Keccak-256. In: FSE 2012. pp. 442–461. Springer, New York (2012).
10.
Zurück zum Zitat Dinur I., Dunkelman O., Shamir A.: Collision attacks on up to 5 rounds of SHA-3 using generalized internal differentials. In: FSE 2013. pp. 219–240. Springer, New York (2013). Dinur I., Dunkelman O., Shamir A.: Collision attacks on up to 5 rounds of SHA-3 using generalized internal differentials. In: FSE 2013. pp. 219–240. Springer, New York (2013).
11.
Zurück zum Zitat Dinur I., Morawiecki P., Pieprzyk J., Srebrny M., Straus M.: Cube attacks and cube-attack-like cryptanalysis on the round-reduced Keccak sponge function. In: EUROCRYPT 2015, pp. 733–761 (2015). Dinur I., Morawiecki P., Pieprzyk J., Srebrny M., Straus M.: Cube attacks and cube-attack-like cryptanalysis on the round-reduced Keccak sponge function. In: EUROCRYPT 2015, pp. 733–761 (2015).
12.
Zurück zum Zitat Dobraunig C., Eichlseder M., Mendel F.: Heuristic tool for linear cryptanalysis with applications to CAESAR candidates. In: ASIACRYPT 2015, pp. 490–509 (2015). Dobraunig C., Eichlseder M., Mendel F.: Heuristic tool for linear cryptanalysis with applications to CAESAR candidates. In: ASIACRYPT 2015, pp. 490–509 (2015).
13.
Zurück zum Zitat Dobraunig C., Eichlseder M., Mendel F., Schläffer M.: Cryptanalysis of Ascon. In: CT-RSA 2015, pp. 371–387 (2015). Dobraunig C., Eichlseder M., Mendel F., Schläffer M.: Cryptanalysis of Ascon. In: CT-RSA 2015, pp. 371–387 (2015).
14.
Zurück zum Zitat Dobraunig C., Eichlseder M., Mendel F., Schläffer M.: Ascon v1. 2. Submission to the CAESAR Competition (2016). Dobraunig C., Eichlseder M., Mendel F., Schläffer M.: Ascon v1. 2. Submission to the CAESAR Competition (2016).
15.
Zurück zum Zitat Dong X., Li Z., Wang X., Qin L.: Cube-like attack on round-reduced initialization of Ketje Sr. IACR Trans. Symmetric Cryptol. 2017, 259–280 (2017). Dong X., Li Z., Wang X., Qin L.: Cube-like attack on round-reduced initialization of Ketje Sr. IACR Trans. Symmetric Cryptol. 2017, 259–280 (2017).
16.
Zurück zum Zitat Duc A., Guo J., Peyrin T., Wei L.: Unaligned rebound attack: application to Keccak. In: FSE 2012. pp. 402–421. Springer, New York (2012). Duc A., Guo J., Peyrin T., Wei L.: Unaligned rebound attack: application to Keccak. In: FSE 2012. pp. 402–421. Springer, New York (2012).
17.
Zurück zum Zitat Guo J., Liu M., Song L.: Linear structures: applications to cryptanalysis of round-reduced Keccak. In: ASIACRYPT 2016, Part I. pp. 249–274. Springer, New York (2016). Guo J., Liu M., Song L.: Linear structures: applications to cryptanalysis of round-reduced Keccak. In: ASIACRYPT 2016, Part I. pp. 249–274. Springer, New York (2016).
19.
Zurück zum Zitat Huang S., Wang X., Xu G., Wang M., Zhao J.: Conditional cube attack on reduced-round Keccak sponge function. In: EUROCRYPT 2017, pp. 259–288 (2017). Huang S., Wang X., Xu G., Wang M., Zhao J.: Conditional cube attack on reduced-round Keccak sponge function. In: EUROCRYPT 2017, pp. 259–288 (2017).
21.
Zurück zum Zitat Li Z., Dong X., Wang X.: Conditional cube attack on round-reduced ASCON. IACR Trans. Symmetric Cryptol. 2017(1), 175–202 (2017). Li Z., Dong X., Wang X.: Conditional cube attack on round-reduced ASCON. IACR Trans. Symmetric Cryptol. 2017(1), 175–202 (2017).
23.
Zurück zum Zitat Morawiecki P., Pieprzyk J., Srebrny M.: Rotational cryptanalysis of roundreduced Keccak. In: FSE2013. pp. 241–262. Springer, New York (2013). Morawiecki P., Pieprzyk J., Srebrny M.: Rotational cryptanalysis of roundreduced Keccak. In: FSE2013. pp. 241–262. Springer, New York (2013).
24.
Zurück zum Zitat Mouha N., Wang Q., Gu D., Preneel B.: Differential and linear cryptanalysis using mixed-integer linear programming. In: Inscrypt 2011. pp. 57–76. Springer, New York (2011). Mouha N., Wang Q., Gu D., Preneel B.: Differential and linear cryptanalysis using mixed-integer linear programming. In: Inscrypt 2011. pp. 57–76. Springer, New York (2011).
25.
Zurück zum Zitat Qiao K., Song L., Liu M., Guo J.: New collision attacks on round-reduced Keccak. In: EUROCRYPT 2017. pp. 216–243. Springer, New York (2017). Qiao K., Song L., Liu M., Guo J.: New collision attacks on round-reduced Keccak. In: EUROCRYPT 2017. pp. 216–243. Springer, New York (2017).
26.
Zurück zum Zitat Sasaki Y., Todo Y.: New impossible differential search tool from design and cryptanalysis aspects—revealing structural properties of several ciphers. In: EUROCRYPT 2017, Part III. pp. 185–215 (2017). Sasaki Y., Todo Y.: New impossible differential search tool from design and cryptanalysis aspects—revealing structural properties of several ciphers. In: EUROCRYPT 2017, Part III. pp. 185–215 (2017).
27.
Zurück zum Zitat Song L., Liao G., Guo J.: Non-full sbox linearization: applications to collision attacks on round-reduced Keccak. In: CRYPTO 2017. pp. 428–451. Springer, New York (2017). Song L., Liao G., Guo J.: Non-full sbox linearization: applications to collision attacks on round-reduced Keccak. In: CRYPTO 2017. pp. 428–451. Springer, New York (2017).
29.
Zurück zum Zitat Sun S., Hu L., Wang P., Qiao K., Ma X., Song L.: Automatic security evaluation and (related-key) differential characteristic search: application to SIMON, PRESENT, LBlock, DES(L) and other bit-oriented block ciphers. In: ASIACRYPT 2014. pp. 158–178. Springer, New York (2014). Sun S., Hu L., Wang P., Qiao K., Ma X., Song L.: Automatic security evaluation and (related-key) differential characteristic search: application to SIMON, PRESENT, LBlock, DES(L) and other bit-oriented block ciphers. In: ASIACRYPT 2014. pp. 158–178. Springer, New York (2014).
30.
Zurück zum Zitat Wang X., Yu H.: How to break MD5 and other hash functions. In: EUROCRYPT 2005. pp. 19–35. Springer, New York (2005). Wang X., Yu H.: How to break MD5 and other hash functions. In: EUROCRYPT 2005. pp. 19–35. Springer, New York (2005).
31.
Zurück zum Zitat Wang X., Yin Y.L., Yu H.: Finding Collisions in the Full SHA-1. In: CRYPTO 2005. pp. 17–36. Springer, New York (2005). Wang X., Yin Y.L., Yu H.: Finding Collisions in the Full SHA-1. In: CRYPTO 2005. pp. 17–36. Springer, New York (2005).
32.
Zurück zum Zitat Xiang Z., Zhang W., Bao Z., Lin D.: Applying milp method to searching integral distinguishers based on division property for 6 lightweight block ciphers. In: ASIACRYPT 2016, Part I. pp. 648–678. Springer, New York (2016). Xiang Z., Zhang W., Bao Z., Lin D.: Applying milp method to searching integral distinguishers based on division property for 6 lightweight block ciphers. In: ASIACRYPT 2016, Part I. pp. 648–678. Springer, New York (2016).
Metadaten
Titel
MILP-aided cube-attack-like cryptanalysis on Keccak Keyed modes
verfasst von
Wenquan Bi
Xiaoyang Dong
Zheng Li
Rui Zong
Xiaoyun Wang
Publikationsdatum
23.08.2018
Verlag
Springer US
Erschienen in
Designs, Codes and Cryptography / Ausgabe 6/2019
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI
https://doi.org/10.1007/s10623-018-0526-x

Weitere Artikel der Ausgabe 6/2019

Designs, Codes and Cryptography 6/2019 Zur Ausgabe