libFES : Fast Exhaustive Search for Polynomial Systems over F2

Charles Bouillaguet set up a nice shiny website for libFES the library for exhaustive search on polynomial systems over . The library has a Sage interface, so it’s easy to get started. It’s also integrated in Charles’ upcoming one-stop boolean system solving patch.

He calls his benchmarketing “bragging rights” … and boy has he earned those rights! Check it out, libFES is fast!

Slides of Talk on Sage & Algebraic Techniques

The slides of my Icebreak talk on Sage and algebraic techniques for (lazy) cryptographers are now available (LaTeX sources here).

SAT Solvers for Sage

One of the most efficient techniques for solving polynomial systems over is to convert the problem to a satisfiability problem and to use a standard SAT solver. In the past, I have used CryptoMiniSat and either my own ANF to CNF converter scripts based on Gregory Bard’s ideas or PolyBoRi’s script.

However, this setup leaves much to be desired:

1. It’s all based on string parsing which has some overhead.
2. Usually the instances produced using PolyBoRi’s conversion method are faster to solve. However, as the number of variables per equation increase this method becomes essentially exponentially more expensive. Hence, a compromise between the two techniques is needed.
3. We don’t have access to learnt clauses and conflict clauses.
4. It all feels a bit duct taped and fragile, partly because the code is not shipped with Sage.

At #418 I just finished a much nicer interface to various SAT solvers. Here are some features.

Call for Papers: 3nd International Conference on Symbolic Computation and Cryptography

CIEM – Castro Urdiales, Spain, 11-13 July 2012, http://scc2012.unican.es/

CALL FOR PAPERS

IMPORTANT DATES

• Deadline for submission: April 28, 2012
• Notification of acceptance or rejection: May 18, 2012
• Deadline for final version: May 30, 2012
• Deadline for registration: June 12, 2012
• Deadline for special issue JSC: September 30, 2012

SCC 2012 is the third edition of a new series of conferences where  research and development in symbolic computation and cryptography may be presented and discussed. It is organized in response to the growing  interest in applying and developing methods, techniques, and software  tools of symbolic computation for cryptography. The use of Lattice  Reduction algorithms in cryptology and the application of Groebner  bases in the context of algebraic attacks are typical examples of  explored applications. The SCC 2012 conference is co-located with  third Workshop on Mathematical Cryptology (WMC 2012, http://wmc2012.unican.es/) , an event also organized by research group Algorithmic Mathematics  And Cryptography (AMAC), which will be held on 9-11 July 2012.

Summer School on Tools :: Mykonos, Greece :: 28.5 – 1.6.

Slightly redacted announcement for the 2012 Summer School on Tools below.

Following the success of the ECRYPT Workshop on Tools for Cryptanalysis 2010,the ECRYPT II Symmetric Techniques Virtual Lab (SymLab) is pleased to announce the 2012 Summer School on Tools. Covering selected topics in both symmetric and asymmetric cryptography, this summer school will provide a thorough overview of some of the most important cryptographic tools that emerged in recent years. While the summer school is aimed primarily at postgraduate students, attendance is open to all.

Coldboot Code Available

After receiving two inquiries about the coldboot attack paper which were best answered by looking at the code or by comparing with our code, I figured it was about time I put it online. So here it is:

https://bitbucket.org/malb/algebraic_attacks/src/1af75effcc7d/coldboot

For this code to run you’ll need to apply this patch to Sage:

http://trac.sagemath.org/sage_trac/ticket/10879

which adds an interface to SCIP. Unfortunately, this patch crashes on OSX and I didn’t figure out yet why. Anybody willing to help, please step forward 🙂

Also, I assume the code on bitbucket needs some patching to work with the most recent version of Sage. Patches very welcome!

Challenge matrices

Now, that we have a decent PNG reader/writer in M4RI, it’s much easier to get some challenge matrices out of the library. Below, I list and link a few such matrices as they appear during Gröbner basis computations.

file	matrix dimensions	density	PLE	M4RI	GB
HFE 25 matrix 5 (5.1M)	12307 x 13508	0.07600	1.03	0.59	0.81
HFE 30 matrix 5 (16M)	19907 x 29323	0.06731	4.79	2.70	4.76
HFE 35 matrix 5 (37M)	29969 x 55800	0.05949	19.33	9.28	19.51
Mutant matrix (39M)	26075 x 26407	0.18497	5.71	3.98	2.10
random n=24, m=26 matrix 3 (30M)	37587 x 38483	0.03832	20.69	21.08	19.36
random n=24_ m=26 matrix 4 (24M)	37576 x 32288	0.04073	18.65	28.44	17.05
SR(2,2,2,4) compressed, matrix 2 (328K)	5640 x 14297	0.00333	0.40	0.29	0.18
SR(2,2,2,4) compressed, matrix 4 (2.4M)	13665 x 17394	0.01376	2.18	3.04	2.04
SR(2,2,2,4) compressed, matrix 5 (2.8M)	11606 x 16282	0.03532	1.94	4.46	1.59
SR(2,2,2,4) matrix 6 (1.4M)	13067 x 17511	0.00892	1.90	2.09	1.38
SR(2,2,2,4) matrix 7 (1.7M)	12058 x 16662	0.01536	1.53	1.93	1.66
SR(2,2,2,4) matrix 9 (36M)	115834 x 118589	0.00376	528.21	578.54	522.98

The first three rows are from GB computations for the hidden field equations cryptosystem (those matrices were provided by Michael Brickenstein). The “mutant” row is a matrix as it appears during a run of the MXL2 algorithm on a random system (I believe). It was contributed by Wael Said. The rows “random n=25,m=26” are matrices as they appear during a GB computation with PolyBoRi for a random system of equations in 24 variables and 26 equations. The remaining rows are matrices from PolyBoRi computations on small scale AES instances. Those rows which have “compressed” in their description correspond to systems where “linear variables” were eliminate before running the Gröbner basis algorithm.

The last three columns give running times (quite rough ones!) for computing an echelon form (not reduced) using (a) the M4RI algorithm, (b) PLE decomposition and (c) a first implementation of the TRSM for trivial pivots trick. As you can see, currently it’s not straight-forward to pick which strategy to use to eliminate matrices appearing during Gröbner basis computations: the best algorithm to pick varies between different problems and the differences can be dramatic.

Slides: Introduction to Algebraic Techniques in Block Cipher Cryptanalysis

This morning I delivered my talk titled “Algebraic Techniques in Cryptanlysis (of block ciphers with a bias towards Gröbner bases)” at the ECrypt PhD Summerschool here in Albena, Bulgaria. I covered:

1. Why bother
2. Setting up equation systems
3. Solving (GBs, SAT solvers, MIP, Cube Testers)
4. “Advanced” Techniques

Well, here are the slides, which perhaps spend too much time explaining F4.

PS: This is as good as any opportunity to point to the paper “Algebraic Techniques in Differential Cryptanalysis Revisited” by Meiqin Wang, Yue Sun, Nicky Mouha and Bart Preneel accepted at ACISP 2011. I don’t agree with every statement in the paper – which revisits techniques Carlos and I proposed in 2009 – but our FSE 2009 paper does deserve a good whipping, i.e., we were way too optimistic about our attack.

Postdoc Position at LIP6

My team is hiring:

One-year post-doctoral position announcement

A 12-month postdoctoral position is available at the INRIA/LIP6/UPMC SALSA team on Campus Jussieu (located in the “Quartier Latin” of Paris, France). We are seeking candidates to apply for this position. The postdoc will work in the joint ANR/NSFC EXACTA project on polynomial system solving and its applications in cryptography, computational geometry, and biology.

On the Relation Between the Mutant Strategy and the Normal Selection Strategy in Gröbner Basis Algorithms

We finally (sorry for the delay!) finished our paper on the Mutant strategy. Here’s the abstract:

The computation of Gröbner bases remains one of the most powerful methods for tackling the Polynomial System Solving (PoSSo) problem. The most efficient known algorithms reduce the Gröbner basis computation to Gaussian eliminations on several matrices. However, several degrees of freedom are available to generate these matrices. It is well known that the particular strategies used can drastically affect the efficiency of the computations.
In this work we investigate a recently-proposed strategy, the so-called Mutant strategy, on which a new family of algorithms is based (MXL, MXL2 and MXL3). By studying and describing the algorithms based on Gröbner basis concepts, we demonstrate that the Mutant strategy can be understood to be equivalent to the classical Normal Selection strategy currently used in Gröbner basis algorithms. Furthermore, we show that the partial enlargement technique can be understood as a strategy for restricting the number of S-polynomials considered in an iteration of the F4 Gröbner basis algorithm, while the new termination criterion used in MXL3 does not lead to termination at a lower degree than the classical Gebauer-Möller installation of Buchberger’s criteria.
We claim that our results map all novel concepts from the MXL family of algorithms to their well-known Gröbner basis equivalents. Using previous results that had shown the relation between the original XL algorithm and F4, we conclude that the MXL family of algorithms can be fundamentally reduced to redundant variants of F4.