The nonlinear filter model is an old and well understood approach to the design of secure stream ciphers. Extensive research over several decades has shown how to attack stream ciphers based on this model and has identified the security properties required of the Boolean function used as the filtering function to resist such attacks. This led to the problem of constructing Boolean functions which provide adequate security and at the same time are efficient to implement. Unfortunately, over...

As cloud-based quantum computing services, such as those offered by D-Wave, become more popular for practical applications, privacy-preserving methods (such as obfuscation) are essential to address data security, privacy, and legal compliance concerns. Several efficient obfuscation methods have been proposed, which do not increase the time complexity of solving the obfuscated problem, for quantum optimization problems. These include {\em sign reversing}, {\em variable permutation}, and the...

Functional bootstrapping in FHE schemes such as FHEW and TFHE allows the evaluation of a function on an encrypted message, in addition to noise reduction. Implementing programs that directly use functional bootstrapping is challenging and error-prone. In this paper, we propose a heuristic that automatically maps Boolean circuits to functional bootstrapping instructions. Unlike other approaches, our method does not limit the encrypted data plaintext space to a power-of-two size, allowing...

The cube attack extracts the information of secret key bits by recovering the coefficient called superpoly in the output bit with respect to a subset of plaintexts/IV, which is called a cube. While the division property provides an efficient way to detect the structure of the superpoly, superpoly recovery could still be prohibitively costly if the number of rounds is sufficiently high. In particular, Core Monomial Prediction (CMP) was proposed at ASIACRYPT 2022 as a scaled-down version of...

In cube attacks, key filtering is a basic step of identifying the correct key candidates by referring to the truth tables of superpolies. When terms of superpolies get massive, the truth table lookup complexity of key filtering increases significantly. In this paper, we propose the concept of implementation dependency dividing all cube attacks into two categories: implementation dependent and implementation independent. The implementation dependent cube attacks can only be feasible when the...

In this paper, we improve the cube attack by exploiting low-degree factors of the superpoly w.r.t. certain "special" index set of cube (ISoC). This can be viewed as a special case of the correlation cube attack proposed at Eurocrypt 2018, but under our framework more beneficial equations on the key variables can be obtained in the key-recovery phase. To mount our attack, one has two challenging problems: (1) effectively recover algebraic normal form of the superpoly and extract out its...

The key step of the cube attack is to recover the special polynomial, the superpoly, of the target cipher. In particular, the balanced superpoly, in which there exists at least one secret variable as a single monomial and none of the other monomials contain this variable, can be exploited to reveal one-bit information about the key bits. However, as the number of rounds grows, it becomes increasingly difficult to find such balanced superpolies. Consequently, traditional methods of searching...

Masking is a prominent strategy to protect cryptographic implementations against side-channel analysis. Its popularity arises from the exponential security gains that can be achieved for (approximately) quadratic resource utilization. Many variants of the countermeasure tailored for different optimization goals have been proposed. The common denominator among all of them is the implicit demand for robust and high entropy randomness. Simply assuming that uniformly distributed random bits are...

We examine the use of Trivium and Kreyvium as transciphering mechanisms for use with the TFHE FHE scheme. Originally these two ciphers were investigated for FHE transciphering only in the context of the BGV/BFV FHE schemes; this is despite Trivium and Kreyvium being particarly suited to TFHE. Recent work by Dobraunig et al. gave some initial experimental results using TFHE. We show that these two symmetric ciphers have excellent performance when homomorphically evaluated using TFHE. Indeed...

Low energy is an important aspect of hardware implementation. For energy-limited battery-powered devices, low energy stream ciphers can play an important role. In \texttt{IACR ToSC 2021}, Caforio et al. proposed the Perfect Tree energy model for stream cipher that links the structure of combinational logic circuits with state update functions to energy consumption. In addition, a metric given by the model shows a negative correlation with energy consumption, i.e., the higher the balance of...

In this paper we introduce a multistep generalization of the guess-and-determine or hybrid strategy for solving a system of multivariate polynomial equations over a finite field. In particular, we propose performing the exhaustive evaluation of a subset of variables stepwise, that is, by incrementing the size of such subset each time that an evaluation leads to a polynomial system which is possibly unfeasible to solve. The decision about which evaluation to extend is based on a...

The cube attack is one of the most important cryptanalytic techniques against Trivium. As the method of recovering superpolies becomes more and more effective, another problem of cube attacks, i.e., how to select cubes corresponding to balanced superpolies, is attracting more and more attention. It is well-known that a balanced superpoly could be used in both theoretical and practical analyses. In this paper, we present a novel framework to search for valuable cubes whose superpolies have an...

Cube attacks exploit the algebraic properties of symmetric ciphers by recovering a special polynomial, the superpoly, and subsequently the secret key. When the algebraic normal forms of the corresponding Boolean functions are not available, the division property based approach allows to recover the exact superpoly in a clever way. However, the computational cost to recover the superpoly becomes prohibitive as the number of rounds of the cipher increases. For example, the nested monomial...

Energy efficiency is critical in battery-driven devices, and designing energy- optimal symmetric-key ciphers is one of the goals for the use of ciphers in such environments. In the paper by Banik et al. (IACR ToSC 2018), stream ciphers were identified as ideal candidates for low-energy solutions. One of the main conclusions of this paper was that Trivium, when implemented in an unrolled fashion, was by far the most energy-efficient way of encrypting larger quantity of data. In fact, it was...

Determining the exact algebraic structure or some partial information of the superpoly for a given cube is a necessary step in the cube attack -- a generic cryptanalytic technique for symmetric-key primitives with some secret and public tweakable inputs. Currently, the division property based approach is the most powerful tool for exact superpoly recovery. However, as the algebraic normal form (ANF) of the targeted output bit gets increasingly complicated as the number of rounds grows,...

Nonlinear feedback shift registers (NFSRs) are used in many stream ciphers as their main building blocks. In particular, Galois NFSRs with terminal bits are used in the typical stream ciphers Grain and Trivium. One security criterion for the design of stream ciphers is to assure their used NFSRs are nonsingular. The nonsingularity is well solved for Fibonacci NFSRs, whereas it is not for Galois NFSRs. In addition, some types of Galois NFSRs equivalent to Fibonacci ones have been found....

Many recent stream ciphers use Galois NFSRs as their main building blocks, such as the hardware-oriented finalists Grain and Trivium in the eSTREAM project. Previous work has found some types of Galois NFSRs equivalent to Fibonacci ones, including that used in Grain. Based on the observability of an NFSR on [0,N-1], which means any two initial states of an NFSR are distinguishable from their corresponding output sequences of length N, the paper first presents two easily verifiable necessary...

Cube attack has recently been proved as the most effective approach of attacking Trivium. So far, the attack against the highest round-reduced Trivium was given in EUROCRYPT 2020, where key-recovery attacks on 840-, 841-, and 842-round Trivium were presented. By revealing the relation between three-subset division property without unknown subset and the monomials of superpolys, Hu et al. obtained more attacks on 840-, 841-, and 842-round Trivium with lower complexities in ASIACRYPT 2020. In...

AEGIS-128 and Tiaoxin-346 (Tiaoxin for short) are two AES-based primitives submitted to the CAESAR competition. Among them, AEGIS-128 has been selected in the final portfolio for high-performance applications, while Tiaoxin is a third-round candidate. Although both primitives adopt a stream cipher based design, they are quite different from the well-known bit-oriented stream ciphers like Trivium and the Grain family. Their common feature consists in the round update function, where the state...

In this paper, we compare several non-tight degree evaluation methods i.e., Boura and Canteaut's formula, Carlet's formula as well as Liu's numeric mapping and division property proposed by Todo, and hope to find the best one from these methods for practical applications. Specifically, for the substitution-permutation-network (SPN) ciphers, we first deeply explore the relationships between division property of an Sbox and its algebraic properties (e.g., the algebraic degree of its inverse)....

FrodoKEM is a lattice-based key encapsulation mechanism, currently a semi-finalist in NIST’s post-quantum standardization effort. A condition for these candidates is to use NIST standards for sources of randomness (i.e., seed-expanding), and as such most candidates utilize SHAKE, an XOF defined in the SHA-3 standard. However, for many of the candidates, this module is a significant implementation bottleneck. Trivium is a lightweight, ISO standard stream cipher which performs well in hardware...

The cube attack is one of the most important cryptanalytic techniques against Trivium. Many improvements have been proposed and lots of key-recovery attacks based on cube attacks have been established. However, among these key-recovery attacks, few attacks can recover the 80-bit full key practically. In particular, the previous best practical key-recovery attack was on 784-round Trivium proposed by Fouque and Vannet at FSE 2013 with on-line complexity about $2^{39}$. To mount a practical...

Differential power analysis (DPA) is a form of side-channel analysis (SCA) that performs statistical analysis on the power traces of cryptographic computations. DPA is applicable to many cryptographic primitives, including block ciphers, stream ciphers and even hash-based message authentication code (HMAC). At COSADE 2017, Dobraunig~et~al. presented a DPA on the fresh re-keying scheme Keymill to extract the bit relations of neighbouring bits in its shift registers, reducing the internal...

Since it was proposed in 2015 as a generalization of integral properties, the division property has evolved into a powerful tool for probing the structures of Boolean functions whose algebraic normal forms are not available. We capture the most essential elements for the detection of division properties from a pure algebraic perspective, proposing a technique named as monomial prediction, which can be employed to determine the presence or absence of a monomial in any product of the...

In this paper we present a bitstream modification attack on the Trivium cipher, an international standard under ISO/IEC 29192-3. By changing the content of three LUTs in the bitstream, we reduce the non-linear state updating function of Trivium to a linear one. This makes it possible to recover the key from 288 keystream bits using at most $2^{19.41}$ operations. We also propose a countermeasure against bitstream modification attacks which obfuscates the bitstream using dummy and camouflaged...

A division property is a generic tool to search for integral distinguishers, and automatic tools such as MILP or SAT/SMT allow us to evaluate the propagation efficiently. In the application to stream ciphers, it enables us to estimate the security of cube attacks theoretically, and it leads to the best key-recovery attacks against well-known stream ciphers. However, it was reported that some of the key-recovery attacks based on the division property degenerate to distinguishing attacks due...

Conditional differential attacks were proposed by Knellwolf et al. at ASIACRYPT 2010 which targeted at cryptographic primitives based on non-linear feedback shift registers. The main idea of conditional differential attacks lies in controlling the propagation of a difference through imposing some conditions on public/key variables. In this paper, we improve the conditional differential attack by introducing the mixed integer linear programming (MILP) method to it. Let...

Cube attacks are an important type of key recovery attacks against stream ciphers. In particular, it is shown to be powerful against Trivium-like ciphers. Traditional cube attacks are experimental attacks which could only exploit cubes of size less than 40. At CRYPTO 2017, division property based cube attacks were proposed by Todo et al., and an advantage of introducing the division property to cube attacks is that large cube sizes which are beyond the experimental range could be explored,...

Cube attack is an important cryptanalytic technique against symmetric cryptosystems, especially for stream ciphers. The key step in cube attack is recovering superpoly. However, when cube size is large, the large time complexity of recovering the exact algebraic normal form (ANF) of superpoly confines cube attack. At CRYPTO 2017, Todo et al. applied conventional bit-based division property (CBDP) into cube attack which could exploit large cube sizes. However, CBDP based cube attacks cannot...

The design of modern stream ciphers is strongly influenced by the fact that Time-Memory-Data tradeoff attacks (TMD-TO attacks) reduce their effective key length to $\mathit{SL}/2$, where $\mathit{SL}$ denotes the inner state length. The classical solution, employed, e.g., by eSTREAM portfolio members Trivium and Grain v1, is to design the cipher in accordance with the Large-State-Small-Key construction, which implies that $\mathit{SL}$ is at least twice as large as the session key length...

To deal with message streams, which is required by many symmetric cryptographic functionalities (MAC, AE, HASH), we propose a lightweight round function called Thin Sponge. We give a framework to construct all these functionalities (MAC, AE, and HASH) using the same Thin Sponge round function. Besides the common security assumptions behind traditional symmetric algorithms, the security of our schemes depends on the hardness of problems to find collisions of some states. We give a class of...

Cube attacks are an important type of key recovery attacks against NFSR-based cryptosystems. The key step in cube attacks closely related to key recovery is recovering superpolies. However, in the previous cube attacks including original, division property based, and correlation cube attacks, the algebraic normal form of superpolies could hardly be shown to be exact due to an unavoidable failure probability or a requirement of large time complexity. In this paper, we propose an algebraic...

At CRYPTO 2018, we proposed a method to reduce the Boolean polynomial of 855-round Trivium. By multiplying a polynomial reduction factor, the output Boolean polynomial is simplified. Based on this method, a 855-round key-recovery attack on Trivium is introduced. In addition, we also give a practical attack on 721-round Trivium to show some rationality and evidence. However, Yonglin Hao et al. find some errors in the 721-round attack recently. As a correction, we propose some new right...

Recently, another kind of dynamic cube attack is proposed by Fu et al. With some key guesses and a transformation in the output bit, they claim that, when the key guesses are correct, the degree of the transformed output bit can drop so significantly that the cubes of lower dimension can not exist, making the output bit vulnerable to the zero-sum cube tester using slightly higher dimensional cubes. They applied their method to 855-round TRIVIUM. In order to verify the correctness of their...

In this paper, we propose a key-recovery attack on Trivium reduced to 855 rounds. As the output is a complex Boolean polynomial over secret key and IV bits and it is hard to find the solution of the secret keys, we propose a novel nullification technique of the Boolean polynomial to reduce the output Boolean polynomial of 855-round Trivium. Then we determine the degree upper bound of the reduced nonlinear boolean polynomial and detect the right keys. These techniques can be applicable to...

In this paper, we study experimental cube attacks against Trivium-like ciphers and we focus on improving nonlinear superpolies recovery. We first present a general framework in cube attacks to test nonlinear superpolies, by exploiting a kind of linearization technique. It worth noting that, in the new framework, the complexities of testing and recovering nonlinear superpolies are almost the same as those of testing and recovering linear superpolies. To demonstrate the effectiveness of our...

In this paper, we describe a new variant of cube attacks called correlation cube attack. The new attack recovers the secret key of a cryptosystem by exploiting conditional correlation properties between the superpoly of a cube and a specific set of low-degree polynomials that we call a basis, which satisfies that the superpoly is a zero constant when all the polynomials in the basis are zeros. We present a detailed procedure of correlation cube attack for the general case, including how to...

Time-memory-data tradeoff (TMD-TO) attacks limit the security level of many classical stream ciphers (like $E_0$, A5/1, Trivium, Grain) to $n/2$, where $n$ denotes the inner state length of the underlying keystream generator. This implies that to withstand TMD tradeoff attacks, the state size should be at least double the key size. In 2015, Armknecht and Mikhalev introduced a new line of research, which pursues the goal of reducing the inner state size of lightweight stream ciphers below...

The cube attack is an important technique for the cryptanalysis of symmetric key primitives, especially for stream ciphers. Aiming at recovering some secret key bits, the adversary reconstructs a superpoly with the secret key bits involved, by summing over a set of the plaintexts/IV which is called a cube. Traditional cube attack only exploits linear/quadratic superpolies. Moreover, for a long time after its proposal, the size of the cubes has been largely confined to an experimental range,...

A growing number of connected objects, with their high performance and low-resources constraints, are embedding lightweight ciphers for protecting the confidentiality of the data they manipulate or store. Since those objects are easily accessible, they are prone to a whole range of physical attacks, one of which are fault attacks against for which countermeasures are usually expensive to implement, especially on off-the-shelf devices. For such devices, we propose a new generic software...

Time-memory-data (TMD) tradeoff attacks limit the security level of many classical stream ciphers (like $E_0$, A5/1, Trivium, Grain) to $\frac{1}{2}n$, where $n$ denotes the inner state length of the underlying keystream generator. This implies that to withstand TMD tradeoff attacks, the state size should be at least double the key size. In 2015, Armknecht and Mikhalev introduced a new line of research, which pursues the goal of reducing the inner state size of lightweight stream ciphers...

The cube attack is a powerful cryptanalytic technique and is especially powerful against stream ciphers. Since we need to analyze the complicated structure of a stream cipher in the cube attack, the cube attack basically analyzes it by regarding it as a blackbox. Therefore, the cube attack is an experimental attack, and we cannot evaluate the security when the size of cube exceeds an experimental range, e.g., 40. In this paper, we propose cube attacks on non-blackbox polynomials. Our attacks...

Time-Memory-Data tradeoff attacks (TMD-attacks) like those of Babbage, Biryukov and Shamir, and Dunkelman and Keller reduce the security level of keystream generator based-stream ciphers to $L/2$, where $L$ denotes the inner state length. This is one of the reasons why stream ciphers like Trivium and Grain use a session key length $n$ of at most $L/2$. In this paper, we deal with the question if this small-key-large-state design principle really provides the maximal possible security of...

We show how short cycles in the state space of a cryptographic algorithm can be used to mount a fault attack on its implementation which results in a full secret key recovery. The attack is based on the assumption that an attacker can inject a transient fault at a precise location and time of his/her choice and more than once. We present an algorithm which uses a SAT-based bounded model checking for finding all short cycles of a given length. The existing Boolean Decision Diagram (BDD) based...

Time-memory-data (TMD) tradeoff attacks limit the security level of many classical stream ciphers (like $E_0$, A5/1, Trivium, Grain) to $\frac{1}{2}n$, where $n$ denotes the inner state length of the underlying keystream generator. In this paper, we present LIZARD, a lightweight stream cipher for power-constrained devices like passive RFID tags. Its hardware efficiency results from combining a Grain-like design with the $FP(1)$-mode, a recently suggested construction principle for the state...

We generalise the cube attack of Dinur and Shamir (and the similar AIDA attack of Vielhaber) to a more general higher order differentiation attack, by summing over an arbitrary subspace of the space of initialisation vectors. The Moebius transform can be used for efficiently examining all the subspaces of a big space, similar to the method used by Fouque and Vannet for the usual cube attack. Secondly we propose replacing the Generalised Linearity Test proposed by Dinur and Shamir...

Most stream ciphers used in practice are vulnerable against generic collision attacks, which allow to compute the secret initial state on the basis of O(2^{n/2}) keystream bits in time and space O(2^{n/2}), where n denotes the inner state length of the underlying keystream generator. This implies the well-known rule that for reaching n-bit security, the inner state length should be at least 2n. Corresponding to this, the inner state length of recent proposals for practically used stream...

We propose and analyze the LIZARD-construction, a way to construct keystream generator (KSG) based stream ciphers with provable $\frac{2}{3} n$-security with respect to generic time-memory-data tradeoff attacks. Note that for the vast majority of known practical KSG-based stream ciphers such attacks reduce the effective key length to the birthday bound $n/2$, where $n$ denotes the inner state length of the underlying KSG. This implies that practical stream ciphers have to have a...

In this paper, we propose a new hardware friendly authen- ticated encryption (AE) scheme TriviA based on (i) a stream cipher for generating keys for the ciphertext and the tag, and (ii) a pairwise in- dependent hash to compute the tag. We have adopted one of the ISO- standardized stream ciphers for lightweight cryptography, namely Triv- ium, to obtain our underlying stream cipher. This new stream cipher has a state that is a little larger than the state of Trivium to accommodate a 128-bit...

Differential Fault Attack (DFA) has received serious attention in cryptographic literature and very recently such attacks have been mounted against several popular stream ciphers for example Grain v1, MICKEY 2.0 and Trivium, that are parts of the eStream hardware profile. The basic idea of the fault attacks consider injection of faults and the most general set-up should consider faults at random location and random time. Then one should identify the exact location and the exact timing of the...

Dinur and Shamir have described cube attacks at EUROCRYPT ’09 and they have shown how efficient they are on the stream cipher Trivium up to 767 rounds. These attacks have been extended to distinguishers but since this seminal work, no better results on the complexity of key recovery attacks on Trivium have been presented. It appears that the time complexity to compute cubes is expensive and the discovery of linear superpoly also requires the computation of many cubes. In this paper, we...

The demand for more efficient ciphers is a likely to sharpen with new generation of products and applications. Previous cipher designs typically focused on optimizing only one of the two parameters - hardware size or speed, for a given security level. In this paper, we present a methodology for designing a class of stream ciphers which takes into account both parameters simultaneously. We combine the advantage of the Galois configuration of NLFSRs, short propagation delay, with the advantage...

In this paper we experiment with cube testers on reduced round Trivium that can act as a distinguisher. Using heuristics, we obtain several distinguishers for Trivium running more than 800 rounds (maximum 829) with cube sizes not exceeding 27. In the process, we also exploit state biases that has not been explored before. Further, we apply our techniques to analyse Trivia-SC, a stream cipher proposed by modifying the parameters of Trivium and used as a building block for TriviA-ck (an AEAD...

In typical applications of homomorphic encryption, the first step consists for Alice to encrypt some plaintext m under Bob’s public key pk and to send the ciphertext c = HE_pk(m) to some third-party evaluator Charlie. This paper specifically considers that first step, i.e. the problem of transmitting c as efficiently as possible from Alice to Charlie. As previously noted, a form of compression is achieved using hybrid encryption. Given a symmetric encryption scheme E, Alice picks a random...

This paper presents an algebraic attack against Trivium that breaks 625 rounds using only $4096$ bits of output in an overall time complexity of $2^{42.2}$ Trivium computations. While other attacks can do better in terms of rounds ($799$), this is a practical attack with a very low data usage (down from $2^{40}$ output bits) and low computation time (down from $2^{62}$). From another angle, our attack can be seen as a proof of concept: how far can algebraic attacks can be pushed when...

Scan chains, a design for testability (DFT) feature, are included in most modern-day ICs. But, it opens a side channel for attacking cryptographic chips. We propose a methodology by which we can recover internal states of any stream cipher using scan chains without knowledge of its design. We consider conven- tional scan-chain design which is normally not scram- bled or protected in any other way. In this scenario the challenge of the adversary is to obtain the corre- spondence of output of...

Basing on the original Cube attack, this paper proposes an improved method of Cube attack on stream ciphers, which makes improvement on the pre-processing phase of the original attack. The new method can induce maxterms of higher-order from those of lower-order by the trade-off between time and space, thus recovering more key bits and reducing the search complexity on higher-dimension. In this paper, the improved attack is applied to Lili-128 algorithm and reduced variants of Trivium...

The first output bit of TRIVIUM can be considered to be a boolean function of 80 key and 80 IV variables. Choose $n$ ($n\leq 30$) of the key variables and set the other variables to constant values. This gives an $n$-variable boolean function. In this work, we experimentally find examples of such boolean functions which deviate from a uniform random $n$-variable boolean function in a statistically significant manner. This improves upon the previously reported experimental `non-randomness'...

The Fibonacci-to-Galois transformation is useful for reducing the propagation delay of feedback shift register-based stream ciphers and hash functions. In this paper, we extend it to handle Galois-to-Galois case as well as feedforward connections. This makes possible transforming Trivium stream cipher and increasing its keystream data rate by 27\% without any penalty in area. The presented transformation might open new possibilities for cryptanalysis of Trivium, since it induces a class of...

Cube attacks can be used to analyse and break cryptographic primitives that have an easy algebraic description. One example for such a primitive is the stream cipher /Trivium. In this article we give a new framework for cubes that are useful in the cryptanalytic context. In addition, we show how algebraic modelling of a cipher can greatly be improved when taking both cubes and linear equivalences between variables into account. When taking many instances of Trivium, we empirically show a...

Related-key and chosen IV attacks are well known cryptanalytic tools in cryptanalysis of stream ciphers. Though the related-key model is considered to be much more unrealistic scenario than the chosen IV model we show that under certain circumstances the attack assumptions may become equivalent. We show that the key differentiation method induces a generic attack in a related-key model whose time complexity in the on-line phase is less than the exhaustive key search. The case of formal...

The problem of securing data present on USB memories and SD cards has not been adequately addressed in the cryptography literature. While the formal notion of a tweakable enciphering scheme (TES) is well accepted as the proper primitive for secure data storage, the real challenge is to design a low cost TES which can perform at the data rates of the targeted memory devices. In this work, we provide the first answer to this problem. Our solution, called STES, combines a stream cipher with a...

In this paper, we focus on a novel technique called cube-linear attack, which is obtained by combining the cube and linear attacks together, is first proposed to deal with the probabilistic polynomial, aiming to furthermore mine the available secret information. Based on different combination ways of the two attacks, moreover, two cube-linear schemes are discussed. Naturally, we can use cube-linear attack as an unordinary trick in linear cryptanalysis, which has never been considered by the...

Trivium is a bit-based stream cipher in the final portfolio of the eSTREAM project. In this paper, we apply the approach of Berbain et al. to Trivium-like ciphers and perform new algebraic analyses on them, namely Trivium and its reduced versions: Trivium-N, Bivium-A and Bivium-B. In doing so, we answer an open question in the literature. We demonstrate a new algebraic attack on Bivium-A. This attack requires less time and memory than previous techniques which use the F4 algorithm to...

In this paper we present a rather new approach to apply mixed-integer optimization to the cryptanalysis of cryptographic primitives. We focus on the stream cipher Trivium, that has been recommended by the eSTREAM stream cipher project, and the lightweight block cipher Ktantan. Using these examples we explain how the problem of solving a non-linear multivariate Boolean equation system can be formulated as a mixed-integer linear programming problem. Our main focus is the formulation of the...

In 2008 I. Dinur and A. Shamir presented a new type of algebraic attack on symmetric ciphers named cube attack. The method has been applied to reduced variants of stream ciphers Trivium and Grain- 128, reduced variants of the block ciphers Serpent and CTC and to a reduced version of the keyed hash function MD6. Independently a very similar attack named AIDA was introduced by M. Vielhaber. In this paper we develop quadraticity tests within the cube attack and apply them to a variant of stream...

Recently, various cryptanalysis methods related to Cube Attack have attracted a lot of interest. We designed a practical platform to perform such cryptanalysis attacks. We also developed a web-based application at \url{http://cube-attack.appspot.com/}, which is open to public for simple testing and verification. In this paper, we focus on linearity testing and try to verify the data provided in several papers. Some interesting results produced in our work indicate certain improper...

In 2008 I. Dinur and A. Shamir presented a new type of algebraic attack on symmetric ciphers named cube attack. The method has been applied to reduced variants of stream ciphers Trivium and Grain- 128, reduced variants of the block ciphers Serpent and CTC and to a reduced version of the keyed hash function MD6. Independently a very similar attack named AIDA was introduced by M. Vielhaber. In this paper we develop quadraticity tests within the cube attack and apply them to a variant of stream...

We present a novel approach for solving systems of polynomial equations via graph partitioning. The concept of a variable-sharing graph of a system of polynomial equations is defined. If such graph is disconnected, then the corresponding system of equations can be split into smaller ones that can be solved individually. This can provide a significant speed-up in computing the solution to the system, but is unlikely to occur either randomly or in applications. However, by deleting a certain...

Abstract. The cube attack has been introduced by Itai Dinur and Adi Shamir [8] as a known plaintext attack on symmetric primitives. The attack has been applied to reduced variants of the stream ciphers Trivium [3, 8] and Grain-128 [2], reduced to three rounds variant of the block cipher Serpent [9] and reduced version of the hash function MD6 [3]. In the special case the attack has appeared in the M. Vielhaber ePrint articles [13, 14], where it has been named AIDA (Algebraic Initial...

eSTREAM called for new stream ciphers designed for niche areas such as exceptional performance in software and hardware where resources are restricted. This project provides an open platform to discuss these ciphers. Trivium is one of the promising new ciphers submitted to it. Until now, no attack has been successfully applied to it. This paper illustrates new design principles of stream ciphers based on the structure of Trivium and introduces the definition of k-order primitive polynomials....

The stream cipher BIVIUM (both BIVIUM-A and BIVIUM-B), a modification of the eSTREAM finalist TRIVIUM, can be broken completely by the Algebraic IV Differential Attack, AIDA, using $2^{27.5}$ simulations or one minute of dual core processing. AIDA uses the subspaces of two 32-dimensional vector spaces over subsets of IV bits to recover 56 of the 80 key bits. The remaining 24 key bits are most easily determined by brute force search. We applied the Fast Reed-Muller Transform to speed up...

We present a novel approach for solving systems of polynomial equations via graph partitioning. The concept of a variable-sharing graph of a system of polynomial equations is defined. If such graph is disconnected, then the system of equations is actually two separate systems that can be solved individually. This can provide a significant speed-up in computing the solution to the system, but is unlikely to occur either randomly or in applications. However, by deleting a small number of...

Fault analysis is a powerful attack to stream ciphers. Up to now, the major idea of fault analysis is to simplify the cipher system by injecting some soft faults. We call it soft fault analysis. As a hardware--oriented stream cipher, Trivium is weak under soft fault analysis. In this paper we consider another type of fault analysis of stream cipher, which is to simplify the cipher system by injecting some hard faults. We call it hard fault analysis. We present the following results about...

Inner state of a stream cipher is said to be as large as necessary but at the same time as small as possible. Trivium, a hardware oriented stream cipher, has been selected for the final portfolio of the eSTREAM project. It offers a security level of 80 bits while it has 288 internal state bits. Owing to its simple algebraic structure, it has been proved experimentally that Trivium can provide only a marginal security level of 80 bits. This article presents some modified versions of Trivium...

Trivium is a hardware-oriented stream cipher, and one of the finally chosen ciphers by eSTREAM project. Michal Hojsik and Bohuslav Rudolf presented an effective attack to Trivium, named floating fault analysis, at INDOCRYPT 2008. Their attack makes use of the fault injection and the fault float. In this paper, we present an improvement of this attack. Our attack is under following weaker and more practical assumptions.The fault injection can be made for the state at a random time.The...

This paper discusses the Cube attacks proposed by Dinur and Shamir applied to Trivium. Independent verification of the equations given in Dinur and Shamir's paper were carried out. Experimentation showed that the precomputed equations were not general. They are correct when applied to the class of IVs for which they were computed - where IV bits at locations other than those corresponding to the cube are fixed at 0. When these IV bits are fixed at some other values, the relations do not...

In this paper the applicability of differential cryptanalytic tool to stream ciphers is elaborated using the algebraic representation similar to early Shannon's postulates regarding the concept of confusion. In 2007, Biham and Dunkelman \cite{BihDunk} have formally introduced the concept of differential cryptanalysis in stream ciphers by addressing the three different scenarios of interest. Here we mainly consider the first scenario where the key difference and/or IV difference influence...

The stream ciphers Salsa20 and Trivium are two of the finalists of the eSTREAM project which are in the final portfolio of new promising stream ciphers. In this paper we show that initialization and key-stream generation of these ciphers is {\em slidable}, i.e. one can find distinct (Key, IV) pairs that produce identical (or closely related) key-streams. There are $2^{256}$ and more then $2^{39}$ such pairs in Salsa20 and Trivium respectively. We write out and solve the non-linear equations...

Almost any cryptographic scheme can be described by \emph{tweakable polynomials} over $GF(2)$, which contain both secret variables (e.g., key bits) and public variables (e.g., plaintext bits or IV bits). The cryptanalyst is allowed to tweak the polynomials by choosing arbitrary values for the public variables, and his goal is to solve the resultant system of polynomial equations in terms of their common secret variables. In this paper we develop a new technique (called a \emph{cube attack})...

The eStream cipher proposal TRIVIUM outputs an XOR sum of six internal state bits. These in turn are obtained from 18 bits linearly, plus six ANDings of two bits each. We show that 4 of the 18 linear terms cancel between themselves.

We show, how to break TRIVIUM with a setup of 576 (instead of 1152) clock cycles, with an effort of 2^6 chosen IV resynchronisations up to cycle 625 for each of the 47 recovered key bits.

Trivium is a stream cipher candidate of the eStream project. It has successfully moved into phase three of the selection process under the hardware category. No attacks faster than the exhaustive search have so far been reported on Trivium. Bivium-A and Bivium-B are simplified versions of Trivium that are built on the same design principles but with two registers. The simplified design is useful in investigating Trivium type ciphers with a reduced complexity and provides insight into...

Shannon is a synchronous stream cipher with message authentication functionality, designed according to the ECrypt NoE call for stream cipher primitives, profile 1A (but well after the call). Shannon is named in memory of Claude E. Shannon[20] of Bell Labs and MIT, founder of Information Theory. Shannon is an entirely new design, influenced by members of the SOBER family of stream ciphers, Helix/Phelix, Trivium, Scream, and SHA-256. It consists of a single 32-bit wide, 16-element nonlinear...

Trivium is a stream cipher designed in 2005 by C. De Cannière and B. Preneel for the European project eSTREAM. It has successfully passed the first phase of the project and has been selected for a special focus in the second phase for the hardware portfolio of the project. Trivium has an internal state of size 288 bits and the key of length 80 bits. Although the design has a simple and elegant structure, no attack on it has been found yet. In this paper we study a class of Trivium-like...

Grain and Trivium are two hardware oriented synchronous stream ciphers proposed as the simplest candidates to the ECRYPT Stream Cipher Project, both dealing with 80-bit secret keys. In this paper we apply the linear sequential circuit approximation method to evaluate the strength of these stream ciphers against distinguishing attack. In this approximation method which was initially introduced by Golic in 1994, linear models are effectively determined for autonomous finite-state machines. We...