Improved algebraic cryptanalysis of QUAD, Bivium and Trivium via graph partitioning on equation systems

We present a novel approach for preprocessing systems of polynomial equations via graph partitioning. The 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 tremendous speed-up in computing the solution to the system, but is unlikely to occur either randomly or in applications. However, by deleting certain vertices on the graph, the variable-sharing graph could be disconnected in a balanced fashion, and in turn the system of polynomial equations would be separated into smaller systems of near-equal sizes. In graph theory terms, this process is equivalent to finding balanced vertex partitions with minimum-weight vertex separators. The techniques of finding these vertex partitions are discussed, and experiments are performed to evaluate its practicality for general graphs and systems of polynomial equations. Applications of this approach in algebraic cryptanalysis on symmetric ciphers are presented: For the QUAD family of stream ciphers, we show how a malicious party can manufacture conforming systems that can be easily broken. For the stream ciphers Bivium and Trivium, we nachieve significant speedups in algebraic attacks against them, mainly in a partial key guess scenario. In each of these cases, the systems of polynomial equations involved are well-suited to our graph partitioning method. These results may open a new avenue for evaluating the security of symmetric ciphers against algebraic attacks.

Algebraic Analysis of LEX

LEX is a stream cipher that progressed to Phase 3 of the eSTREAM stream cipher project. In this paper, we show that the security of LEX against algebraic attacks relies on a small equation system not being solvable faster than exhaustive search. We use the byte leakage in LEX to construct a system of 21 equa- tions in 17 variables. This is very close to the require- ment for an efficient attack, i.e. a system containing 16 variables. The system requires only 36 bytes of keystream, which is very low.

Algebraic analysis of small scale LEX-BES

This paper examines the algebraic cryptanalysis of small scale variants of the LEX-BES. LEX-BES is a stream cipher based on the Advanced Encryption Standard (AES) block cipher. LEX is a generic method proposed for constructing a stream cipher from a block cipher, initially introduced by Biryukov at eSTREAM, the ECRYPT Stream Cipher project in 2005. The Big Encryption System (BES) is a block cipher introduced at CRYPTO 2002 which facilitates the algebraic analysis of the AES block cipher. In this paper, experiments were conducted to find solution of the equation system describing small scale LEX-BES using Gröbner Basis computations. This follows a similar approach to the work by Cid, Murphy and Robshaw at FSE 2005 that investigated algebraic cryptanalysis on small scale variants of the BES. The difference between LEX-BES and BES is that due to the way the keystream is extracted, the number of unknowns in LEX-BES equations is fewer than the number in BES. As far as the author knows, this attempt is the first at creating solvable equation systems for stream ciphers based on the LEX method using Gröbner Basis computations.

Algebraic analysis of small Scale LEX-BES

This work examines the algebraic cryptanalysis of small scale variants of the LEX-BES. LEX-BES is a stream cipher based on the Advanced Encryption Standard (AES) block cipher. LEX is a generic method proposed for constructing a stream cipher from a block cipher, initially introduced by Biryukov at eSTREAM, the ECRYPT Stream Cipher project in 2005. The Big Encryption System (BES) is a block cipher introduced at CRYPTO 2002 which facilitates the algebraic analysis of the AES block cipher. In this article, experiments were conducted to find solutions of equation systems describing small scale LEX-BES using Gröbner Basis computations. This follows a similar approach to the work by Cid, Murphy and Robshaw at FSE 2005 that investigated algebraic cryptanalysis on small scale variants of the BES. The difference between LEX-BES and BES is that due to the way the keystream is extracted, the number of unknowns in LEX-BES equations is fewer than the number in BES. As far as the authors know, this attempt is the first at creating solvable equation systems for stream ciphers based on the LEX method using Gröbner Basis computations.

A mass-conservative control volume-finite element method for solving Richards’ equation in heterogeneous porous media

We present a mass-conservative vertex-centred finite volume method for efficiently solving the mixed form of Richards’ equation in heterogeneous porous media. The spatial discretisation is particularly well-suited to heterogeneous media because it produces consistent flux approximations at quadrature points where material properties are continuous. Combined with the method of lines, the spatial discretisation gives a set of differential algebraic equations amenable to solution using higher-order implicit solvers. We investigate the solution of the mixed form using a Jacobian-free inexact Newton solver, which requires the solution of an extra variable for each node in the mesh compared to the pressure-head form. By exploiting the structure of the Jacobian for the mixed form, the size of the preconditioner is reduced to that for the pressure-head form, and there is minimal computational overhead for solving the mixed form. The proposed formulation is tested on two challenging test problems. The solutions from the new formulation offer conservation of mass at least one order of magnitude more accurate than a pressure head formulation, and the higher-order temporal integration significantly improves both the mass balance and computational efficiency of the solution.

Colour by numbers in Excel 2007 : solving algebraic equations without algebra

This is an update of an earlier paper, and is written for Excel 2007. A series of Excel 2007 models is described. The more advanced versions allow solution of f(x)=0 by examining change of sign of function values. The function is graphed and change of sign easily detected by a change of colour. Relevant features of Excel 2007 used are Names, Scatter Chart and Conditional Formatting. Several sample Excel 2007 models are available for download, and the paper is intended to be used as a lesson plan for students having some familiarity with derivatives. For comparison and reference purposes, the paper also presents a brief outline of several common equation-solving strategies as an Appendix.

Algebraic attacks on SOBER-t32 and SOBER-t16 without stuttering

This paper presents algebraic attacks on SOBER-t32 and SOBER-t16 without stuttering. For unstuttered SOBER-t32, two different attacks are implemented. In the first attack, we obtain multivariate equations of degree 10. Then, an algebraic attack is developed using a collection of output bits whose relation to the initial state of the LFSR can be described by low-degree equations. The resulting system of equations contains 2^69 equations and monomials, which can be solved using the Gaussian elimination with the complexity of 2^196.5. For the second attack, we build a multivariate equation of degree 14. We focus on the property of the equation that the monomials which are combined with output bit are linear. By applying the Berlekamp-Massey algorithm, we can obtain a system of linear equations and the initial states of the LFSR can be recovered. The complexity of attack is around O(2^100) with 2^92 keystream observations. The second algebraic attack is applicable to SOBER-t16 without stuttering. The attack takes around O(2^85) CPU clocks with 2^78 keystream observations.

Detailed analysis of a conservative difference approximation for the time fractional diffusion equation

Diffusion equations that use time fractional derivatives are attractive because they describe a wealth of problems involving non-Markovian Random walks. The time fractional diffusion equation (TFDE) is obtained from the standard diffusion equation by replacing the first-order time derivative with a fractional derivative of order α ∈ (0, 1). Developing numerical methods for solving fractional partial differential equations is a new research field and the theoretical analysis of the numerical methods associated with them is not fully developed. In this paper an explicit conservative difference approximation (ECDA) for TFDE is proposed. We give a detailed analysis for this ECDA and generate discrete models of random walk suitable for simulating random variables whose spatial probability density evolves in time according to this fractional diffusion equation. The stability and convergence of the ECDA for TFDE in a bounded domain are discussed. Finally, some numerical examples are presented to show the application of the present technique.

Exploring first-year academic achievement through structural equation modelling

The purpose of this research was to develop and test a multicausal model of the individual characteristics associated with academic success in first-year Australian university students. This model comprised the constructs of: previous academic performance, achievement motivation, self-regulatory learning strategies, and personality traits, with end-of-semester grades the dependent variable of interest. The study involved the distribution of a questionnaire, which assessed motivation, self-regulatory learning strategies and personality traits, to 1193 students at the start of their first year at university. Students' academic records were accessed at the end of their first year of study to ascertain their first and second semester grades. This study established that previous high academic performance, use of self-regulatory learning strategies, and being introverted and agreeable, were indicators of academic success in the first semester of university study. Achievement motivation and the personality trait of conscientiousness were indirectly related to first semester grades, through the influence they had on the students' use of self-regulatory learning strategies. First semester grades were predictive of second semester grades. This research provides valuable information for both educators and students about the factors intrinsic to the individual that are associated with successful performance in the first year at university.

Implicit difference approximation for the time fractional diffusion equation

In this paper, we consider a time fractional diffusion equation on a finite domain. The equation is obtained from the standard diffusion equation by replacing the first-order time derivative by a fractional derivative (of order $0<\alpha<1$ ). We propose a computationally effective implicit difference approximation to solve the time fractional diffusion equation. Stability and convergence of the method are discussed. We prove that the implicit difference approximation (IDA) is unconditionally stable, and the IDA is convergent with $O(\tau+h^2)$, where $\tau$ and $h$ are time and space steps, respectively. Some numerical examples are presented to show the application of the present technique.

A Petrov-Galerkin method for a singularly perturbed ordinary differential equation with non-smooth data

In this paper, a singularly perturbed ordinary differential equation with non-smooth data is considered. The numerical method is generated by means of a Petrov-Galerkin finite element method with the piecewise-exponential test function and the piecewise-linear trial function. At the discontinuous point of the coefficient, a special technique is used. The method is shown to be first-order accurate and singular perturbation parameter uniform convergence. Finally, numerical results are presented, which are in agreement with theoretical results.