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 $\mathbb{F}_2$ . 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 $\mathbb{F}_2$ 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” →

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. Continue reading “Summer School on Tools :: Mykonos, Greece :: 28.5 – 1.6.” →

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:

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.

CryptoMiniSat 2.5 won the SATRace 2010

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.

SAT Solving Pointers

This is just a quick note to point out two SAT-solving sources relevant for cryptography.

Michael Brickenstein provides an alternative approach for ANF to CNF conversion in his PolyBoRi scripts collection.
Mate Soos makes his changes to MiniSat available on his website. Those changes are meant to make it more suitable for cryptographic applications, hence the name CryptoMiniSat.

Have fun.

Algebraic Attacks and CNF

Since the seminal papers [1] and [2] by Bard, Courtois and Jefferson it seems accepted wisdom that the right thing to do for constructing a CNF representation of a block cipher is to construct an algebraic system of equations first (cf. [3]). This system of equations is then converted to CNF using some ANF to CNF converted (e.g. [4]) which deals with the negative impact of the XORs just introduced via the ANF. On the other hand, it is straight forward to compute some CNF for a given S-Box directly by considering its truth table. Sage now contains code which does this for you:

sage: sr = mq.SR(1,1,1,4,gf2=True,polybori=True)
sage: S = sr.sbox()
sage: print S.cnf()

[(1, 2, 3, 4, –5), (1, 2, 3, 4, 6), (1, 2, 3, 4, 7), (1, 2, 3, 4, –8), (1, 2, 3, –4, 5), (1, 2, 3, –4, –6), (1, 2, 3, –4, 7), (1, 2, 3, –4, 8), (1, 2, –3, 4, –5), (1, 2, –3, 4, 6), (1, 2, –3, 4, –7),(1, 2, –3, 4, 8), (1, 2, –3, –4, –5), (1, 2, –3, –4, 6), (1, 2, –3, –4, –7), (1, 2, –3, –4, –8), (1, –2, 3, 4, –5), (1, –2, 3, 4, –6), (1, –2, 3, 4, 7), (1, –2, 3, 4, –8), (1, –2, 3, –4, 5), (1, –2, 3, –4, 6), (1, –2, 3, –4, 7), (1, –2, 3, –4, –8), (1, –2, –3, 4, –5), (1, –2, –3, 4, 6), (1, –2, –3,4, 7), (1, –2, –3, 4, 8), (1, –2, –3, –4, 5), (1, –2, –3, –4, –6), (1, –2, –3, –4, 7), (1, –2, –3, –4, –8), (–1, 2, 3, 4, 5), (–1, 2, 3, 4, –6), (–1, 2, 3, 4, –7), (–1, 2, 3, 4, 8), (–1, 2, 3, –4, 5), (–1, 2, 3, –4, 6), (–1, 2, 3, –4, –7), (–1, 2, 3, –4, 8), (–1, 2, –3, 4, 5), (–1, 2, –3, 4, 6), (–1, 2, –3, 4, 7), (–1, 2, –3, 4, 8), (–1, 2, –3, –4, 5), (–1, 2, –3, –4, 6), (–1, 2, –3, –4, –7), (–1, 2, –3, –4, –8), (–1, –2, 3, 4, –5), (–1, –2, 3, 4, –6), (–1, –2, 3, 4, 7), (–1, –2, 3, 4, 8), (–1,–2, 3, –4, –5), (–1, –2, 3, –4, –6), (–1, –2, 3, –4, –7), (–1, –2, 3, –4, 8), (–1, –2, –3, 4, –5), (–1, –2, –3, 4, –6), (–1, –2, –3, 4, –7), (–1, –2, –3, 4, –8), (–1, –2, –3, –4, 5), (–1, –2, –3, –4,–6), (–1, –2, –3, –4, –7), (–1, –2, –3, –4, –8)]

I am not claiming that this naive approach produces an optimal representation, it seems more compact than what ANF to CNF converters produce, though.