International Association for Cryptologic Research

International Association
for Cryptologic Research


Håvard Raddum


Analysis of Multivariate Encryption Schemes: Application to Dob 📺
In this paper, we study the effect of two modifications to multivariate public key encryption schemes: internal perturbation (ip), and Q_+. Focusing on the Dob encryption scheme, a construction utilising these modifications, we accurately predict the number of degree fall polynomials produced in a Gröbner basis attack, up to and including degree five. The predictions remain accurate even when fixing variables. Based on this new theory we design a novel attack on the Dob encryption scheme, which breaks Dob using the parameters suggested by its designers. While our work primarily focuses on the Dob encryption scheme, we also believe that the presented techniques will be of particular interest to the analysis of other big-field schemes.
Solving MRHS linear equations
Håvard Raddum Igor Semaev
A new method for solving algebraic equation systems common in cryptanalysis is proposed. Our method differs from the others in that the equations are not represented as multivariate polynomials, but as a system of Multiple Right Hand Sides linear equations. The method was tested on scaled versions of the AES. The results overcome significantly what was previously achieved with Gr\"{o}bner Basis related algorithms.
An Analysis of the Hermes8 Stream Ciphers
Hermes8 is one of the stream ciphers submitted to the ECRYPT Stream Cipher Project (eSTREAM). In this paper we present an analysis of the Hermes8 stream ciphers. In particular, we show an attack on the latest version of the cipher (Hermes8F), which requires very few known keystream bytes and recovers the cipher secret key in less than a second on a normal PC. Furthermore, we make some remarks on the cipher's key schedule and discuss some properties of ciphers with similar algebraic structure to Hermes8.
New Technique for Solving Sparse Equation Systems
HÃ¥vard Raddum Igor Semaev
Most of the recent cryptanalysis on symmetric key ciphers have focused on algebraic attacks. The cipher being attacked is represented as a non-linear equation system, and various techniques (Buchberger, F4/F5, XL, XSL) can be tried in order to solve the system, thus breaking the cipher. The success of these attacks has been limited so far. In this paper we take a different approach to the problem of solving non-linear equation systems, and propose a new method for solving them. Our method differs from the others in that the equations are not represented as multivariate polynomials, and that the core of the algorithm for finding the solution can be seen as message-passing on a graph. Bounds on the complexities for the main algorithms are presented and they compare favorably with the known bounds. The methods have also been tested on reduced-round versions of DES with good results. This paper was posted on ECRYPT's STVL website on January 16th 2006.
Cryptanalysis of IDEA-X/2
Håvard Raddum

Program Committees

FSE 2009
FSE 2006