Automatic Search of Cubes for Attacking Stream Ciphers

Cube attack was proposed by Dinur and Shamir, and it has become an important tool for analyzing stream ciphers. As the problem that how to recover the superpolys accurately was resolved by Hao et al. in EUROCRYPT 2020, another important problem is how to find “good” superpolys, which is equivalent...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autor principal:	Yao Sun
Formato:	article
Lenguaje:	EN
Publicado:	Ruhr-Universität Bochum 2021
Materias:	stream cipher cube attack division property monomial prediction MILP Trivium Computer engineering. Computer hardware TK7885-7895
Acceso en línea:	https://doaj.org/article/49f54c27357a4e619a3b4a3dd87e86a7
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:49f54c27357a4e619a3b4a3dd87e86a7
record_format	dspace
spelling	oai:doaj.org-article:49f54c27357a4e619a3b4a3dd87e86a72021-12-03T14:38:29ZAutomatic Search of Cubes for Attacking Stream Ciphers10.46586/tosc.v2021.i4.100-1232519-173Xhttps://doaj.org/article/49f54c27357a4e619a3b4a3dd87e86a72021-12-01T00:00:00Zhttps://tosc.iacr.org/index.php/ToSC/article/view/9330https://doaj.org/toc/2519-173X Cube attack was proposed by Dinur and Shamir, and it has become an important tool for analyzing stream ciphers. As the problem that how to recover the superpolys accurately was resolved by Hao et al. in EUROCRYPT 2020, another important problem is how to find “good” superpolys, which is equivalent to finding “good” cubes. However, there are two difficulties in finding “good” cubes. Firstly, the number of candidate cubes is enormous and most of the cubes are not “good”. Secondly, it is costly to evaluate whether a cube is “good”. In this paper, we present a new algorithm to search for a kind of “good” cubes, called valuable cubes. A cube is called valuable, if its superpoly has (at least) a balanced secret variable. A valuable cube is “good”, because its superpoly brings in 1 bit of information about the key. More importantly, the superpolys of valuable cubes could be used in both theoretical and practical analyses. To search for valuable cubes, instead of testing a set of cubes one by one, the new algorithm deals with the set of cubes together, such that the common computations can be done only once for all candidate cubes and duplicated computations are avoided. Besides, the new algorithm uses a heuristic method to reject useless cubes efficiently. This heuristic method is based on the divide-and-conquer strategy as well as an observation. For verifications of this new algorithm, we applied it to Trivium and Kreyvium, and obtained three improvements. Firstly, we found two valuable cubes for 843-round Trivium, such that we proposed, as far as we know, the first theoretical key-recovery attack against 843-round Trivium, while the previous highest round of Trivium that can be attacked was 842, given by Hao et al. in EUROCRYPT 2020. Secondly, by finding many small valuable cubes, we presented practical attacks against 806- and 808-round Trivium for the first time, while the previous highest round of Trivium that can be attacked practically was 805. Thirdly, based on the cube used to attack 892-round Kreyvium in EUROCRYPT 2020, we found more valuable cubes and mounted the key-recovery attacks against Kreyvium to 893-round. Yao SunRuhr-Universität Bochumarticlestream ciphercube attackdivision propertymonomial predictionMILPTriviumComputer engineering. Computer hardwareTK7885-7895ENIACR Transactions on Symmetric Cryptology, Vol 2021, Iss 4 (2021)
institution	DOAJ
collection	DOAJ
language	EN
topic	stream cipher cube attack division property monomial prediction MILP Trivium Computer engineering. Computer hardware TK7885-7895
spellingShingle	stream cipher cube attack division property monomial prediction MILP Trivium Computer engineering. Computer hardware TK7885-7895 Yao Sun Automatic Search of Cubes for Attacking Stream Ciphers
description	Cube attack was proposed by Dinur and Shamir, and it has become an important tool for analyzing stream ciphers. As the problem that how to recover the superpolys accurately was resolved by Hao et al. in EUROCRYPT 2020, another important problem is how to find “good” superpolys, which is equivalent to finding “good” cubes. However, there are two difficulties in finding “good” cubes. Firstly, the number of candidate cubes is enormous and most of the cubes are not “good”. Secondly, it is costly to evaluate whether a cube is “good”. In this paper, we present a new algorithm to search for a kind of “good” cubes, called valuable cubes. A cube is called valuable, if its superpoly has (at least) a balanced secret variable. A valuable cube is “good”, because its superpoly brings in 1 bit of information about the key. More importantly, the superpolys of valuable cubes could be used in both theoretical and practical analyses. To search for valuable cubes, instead of testing a set of cubes one by one, the new algorithm deals with the set of cubes together, such that the common computations can be done only once for all candidate cubes and duplicated computations are avoided. Besides, the new algorithm uses a heuristic method to reject useless cubes efficiently. This heuristic method is based on the divide-and-conquer strategy as well as an observation. For verifications of this new algorithm, we applied it to Trivium and Kreyvium, and obtained three improvements. Firstly, we found two valuable cubes for 843-round Trivium, such that we proposed, as far as we know, the first theoretical key-recovery attack against 843-round Trivium, while the previous highest round of Trivium that can be attacked was 842, given by Hao et al. in EUROCRYPT 2020. Secondly, by finding many small valuable cubes, we presented practical attacks against 806- and 808-round Trivium for the first time, while the previous highest round of Trivium that can be attacked practically was 805. Thirdly, based on the cube used to attack 892-round Kreyvium in EUROCRYPT 2020, we found more valuable cubes and mounted the key-recovery attacks against Kreyvium to 893-round.
format	article
author	Yao Sun
author_facet	Yao Sun
author_sort	Yao Sun
title	Automatic Search of Cubes for Attacking Stream Ciphers
title_short	Automatic Search of Cubes for Attacking Stream Ciphers
title_full	Automatic Search of Cubes for Attacking Stream Ciphers
title_fullStr	Automatic Search of Cubes for Attacking Stream Ciphers
title_full_unstemmed	Automatic Search of Cubes for Attacking Stream Ciphers
title_sort	automatic search of cubes for attacking stream ciphers
publisher	Ruhr-Universität Bochum
publishDate	2021
url	https://doaj.org/article/49f54c27357a4e619a3b4a3dd87e86a7
work_keys_str_mv	AT yaosun automaticsearchofcubesforattackingstreamciphers
_version_	1718373143540662272

Automatic Search of Cubes for Attacking Stream Ciphers

Ejemplares similares