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!
The slides of my Icebreak talk on Sage and algebraic techniques for (lazy) cryptographers are now available (LaTeX sources here).
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:
- It’s all based on string parsing which has some overhead.
- 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.
- We don’t have access to learnt clauses and conflict clauses.
- 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. Continue reading “SAT Solvers for Sage” →
CIEM – Castro Urdiales, Spain, 11-13 July 2012, http://scc2012.unican.es/
CALL FOR PAPERS
- 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.
Continue reading “Call for Papers: 3nd International Conference on Symbolic Computation and Cryptography” →
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. Continue reading “Summer School on Tools :: Mykonos, Greece :: 28.5 – 1.6.” →
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:
For this code to run you’ll need to apply this patch to Sage:
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!
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.
|HFE 25 matrix 5 (5.1M)
||12307 x 13508
|HFE 30 matrix 5 (16M)
||19907 x 29323
|HFE 35 matrix 5 (37M)
||29969 x 55800
|Mutant matrix (39M)
||26075 x 26407
|random n=24, m=26 matrix 3 (30M)
||37587 x 38483
|random n=24_ m=26 matrix 4 (24M)
||37576 x 32288
|SR(2,2,2,4) compressed, matrix 2 (328K)
||5640 x 14297
|SR(2,2,2,4) compressed, matrix 4 (2.4M)
||13665 x 17394
|SR(2,2,2,4) compressed, matrix 5 (2.8M)
||11606 x 16282
|SR(2,2,2,4) matrix 6 (1.4M)
||13067 x 17511
|SR(2,2,2,4) matrix 7 (1.7M)
||12058 x 16662
|SR(2,2,2,4) matrix 9 (36M)
||115834 x 118589
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.
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:
- Why bother
- Setting up equation systems
- Solving (GBs, SAT solvers, MIP, Cube Testers)
- “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.
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.