Research Library

open-access-imgOpen AccessAutomatic Search of Cubes for Attacking Stream Ciphers
Author(s)
Yao Sun
Publication year2021
Publication title
iacr transaction on symmetric cryptology
Resource typeJournals
PublisherUniversitatsbibliothek der Ruhr-Universitat Bochum
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.
Subject(s)algorithm , artificial intelligence , combinatorics , computation , computer science , computer security , cube (algebra) , data cube , data mining , heuristic , key (lock) , mathematics , programming language , set (abstract data type)
Language(s)English
SCImago Journal Rank0.715
H-Index10
ISSN2519-173X
DOI10.46586/tosc.v2021.i4.100-123

Seeing content that should not be on Zendy? Contact us.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.
Having issues? You can contact us here