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”
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.”
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.
Mate Soos’ CryptoMiniSat won the SATRace 2010. Congratulations Mate! For those who don’t know CryptoMiniSat, it is a fork of MiniSat which supports XOR clauses (Gaussian elimination!) among other things. This makes it particularly suitable for cryptographic problems. I’ll try to make an optional Sage Package for CryptoMiniSat soon-ish.
This is just a quick note to point out two SAT-solving sources relevant for cryptography.