Haoran Li, Shichang Wang, Meicheng Liu, Willi Meier, Dongdai Lin

Cube Attacks with Elimination Strategy: Key Recovery Attacks on Trivium

Introduction

Cube attacks with elimination strategy: key recovery attacks on trivium. Discover a novel cube attack framework with elimination strategy. This paper presents practical key recovery attacks on Trivium (840-855 rounds) using advanced techniques.

Abstract

In this paper, we present a novel framework for cube attacks named cube attacks with elimination strategy. The core idea is to find specific key conditions and cubes such that their superpolies under these key conditions can be efficiently computed. By recovering these conditional superpolies, we can solve the corresponding equation system and thereby retrieve key information. If a sufficient number of such key conditions can be found, the attack can be extended to a larger key space. To apply this framework in practical attacks, we propose the following techniques.First, we propose a nested coefficient solver that combines variable substitution and symbolic computation to efficiently recover superpolies, and present the conditional monomial prediction technique to rapidly recover conditional superpolies. Second, by combining numeric mapping with monomial prediction techniques, we propose an automated cube search algorithm that is capable of generating a large number of good cubes for attacks. Finally, we develop two kinds of testing methods, which are used to efficiently extract substantial key information from large-scale equation systems.To illustrate the power of our techniques, we apply them to Trivium. As a result, for 840 rounds of Trivium, a practical key recovery attack is mounted with complexity below 255 and a success rate 77.8%. For 845 rounds, we present a practical key recovery attack with complexity below 256 and a success rate 98.1% for 280 x 59.1% keys. For 855 rounds, we present a theoretical weak-key recovery attack for 274 keys. To the best of our knowledge, these are the best practical and theoretical attacks on Trivium. The improvements in the number of rounds reached are 13 for practical attacks and 4 for theoretical attacks, respectively.

Review

This paper introduces an innovative cryptanalytic framework termed "cube attacks with elimination strategy," specifically targeting the Trivium stream cipher. The central premise revolves around identifying particular key conditions and corresponding cubes that enable the efficient computation of their superpolies. By recovering these conditional superpolies, the authors aim to construct solvable equation systems from which key information can be extracted. A significant aspect of this strategy is its potential to scale attacks to a broader key space, contingent on the discovery of a sufficient number of such exploitable key conditions. This approach represents a notable advancement in algebraic attacks, offering a systematic method for leveraging partial key information to enhance the attack's scope and efficiency. To operationalize this novel framework, the authors propose several sophisticated techniques. Firstly, a nested coefficient solver, which integrates variable substitution with symbolic computation, is introduced for the efficient recovery of superpolies, complemented by a conditional monomial prediction technique for rapid recovery of conditional superpolies. Secondly, an automated cube search algorithm is presented, leveraging numeric mapping combined with monomial prediction to generate a substantial number of effective cubes for attacks. Finally, two distinct testing methodologies are developed, designed to efficiently extract crucial key information from the potentially large-scale equation systems that arise during the attack. These methodological contributions collectively aim to overcome the computational challenges often associated with high-round algebraic attacks. The efficacy and power of these techniques are compellingly demonstrated through their application to Trivium. The paper reports several impressive results, including a practical key recovery attack on 840 rounds with a complexity below 2^55 and a 77.8% success rate. For 845 rounds, a practical attack with complexity below 2^56 is presented, achieving a 98.1% success rate for 2^80 * 59.1% of keys. Furthermore, a theoretical weak-key recovery attack is outlined for 855 rounds, targeting 2^74 keys. These results are claimed to represent the best practical and theoretical attacks on Trivium to date, demonstrating an improvement of 13 rounds for practical attacks and 4 rounds for theoretical attacks. This work significantly pushes the cryptanalytic boundaries for Trivium, underscoring the potential of the cube attack with elimination strategy as a powerful tool in stream cipher cryptanalysis.

Full Text

Comments

You need to be logged in to post a comment.