Experimental Algebraic Cryptanalysis
of Block Ciphers

page maintained by Nicolas T. Courtois.

Main objective: Bridge the gap between cryptographic research and the reality: build consensus on which systems can be broken by algebraic attacks and how, and which are far from being broken.

Scope:

Devoted to public research in symmetric cryptography. Frequently updated. Open for contribution.

Courtois Toy Cipher (CTC and CTC2)

The CTC cipher (May 2006) had 3-bit S-boxes, can have 1,2,3,4,... S-boxes per round, and the key size equal to the block size. It was designed in order to study algebraic cryptanalysis of block ciphers, not as an encryption tool. The initial (outdated) specification is available here. Later and Dunkelman and Keller have shown that a few bits of the key can be recovered by linear cryptanalysis, which cannot however compromise a security of a larger key. The revised specification is called CTC2 and is available here. The key size is now variable, but if not specified, by default it is the same as the block size.

 
It was recently discovered that CTC2 S-box is an affine equivalent of the inverse-based S-box of AES. So all algebraic attacks on AES and BES can be tried on CTC2. But this works only in one direction: if an attack breaks CTC2, it does NOT mean it will work for AES too. However if an attack can NOT break CTC2 for 7 rounds, there is no hope it will ever break AES.

Here is the windows executable program axel.exe which must always be used with the first parameter being 777. This program allows one to generate equations for CTC2. Usage:

  • axel.exe 777 B Nr /insX [/fixY] [/cp] [/keyZ] [/bes]. Legend:
    • B=number of S-boxes per round,
    • Nr=number of rounds,
    • /insX means use X plaintext/ciphertext pairs,
    • with the option /cp the plaintexts are chosen to be consecutive - it is a counter mode,
    • the option /keyZ modifies the size of the key, default is Z=B*3 which is equal to the block size.
    • /fixY means fix Y first key bits to their values to reduce the key space.
    • /opns uses a new gate-efficent implementation of the S-box.
    • /bes generates additional BES-style equations over GF(8) (in another separate file). With this option GF(8) is defined by polynomials a[3]X^2+a[2]X+a[1] modulo X^3+X+1, and an element is represented by the integer a[3]*4+a[2]*2+a[1]. So for example the inverse S-box in GF(8) is defined as {0,1,5,6,7,2,3,4}.
    • /singular will try it with Singular if installed under cygwin.
    • /magma will convert the equations to Magma format but will not try to call Magma.

Now everybody can generate the equations and try to break CTC2. We encourage the researchers to try to solve these systems by their favorite method. We will post their timings on this page (if they are good). Some reference results can be found here. Currently up to 10 rounds of CTC2 have been broken by algebraic attacks.

Reduced versions of Serpent, Present, Whirlpool etc.
Toy ciphers with 3, 4-bit and 8-bit S-boxes.

For 3-bit S-box, see CTC2 section above.

For bigger S-boxes, more results to be published. Here are the equations of some S-boxes. (Sets of equations for DES S-boxes are available in the DES section below.

Data Encryption Standard (DES)

We give here some examples of equations for DES, following this paper. There are many ways of writing equations for DES, we have implemented a few inside one single program axel.exe with a number of individual files with extension .eqs, which need to be in the same directory.

  • Example of command line is  axel 9000 6 /ins1 /fix14 /wrong /cubic /sat.
    • This option will generate 1 instance of a cipher with 1 random plaintext. The option /ins2 /cp would use two instances with 2 plaintexts differing by 1 bit only (in general with /cp we get here a sort of chosen plaintext attack in a sort of counter mode). 
    • It writes a system cubic equations with 10 variables per S-box.
    • Due to /fix14 /wrong we have 14 variables fixed, with an incorrect assignment. 
    • Then due to the option /sat it will attempt to solve it with a default conversion method and a default SAT solver.
  • The most basic option is /cubic: write 112 cubic equations per S-box. It is at present time the default method, and in absence of conflicting options it does not need to be specified.
  • The second very important method called /opns is to use an optimised non-standard representation of each S-box with a low gate count based on work by Matthew Kwan (which requires many extra variables but gives equations of degree 2  which are extremely sparse). 
  • An option which can co-exist with several other options is /mono, it adds so called monomial equations which happens to exist but are of high degree (up to 10) .
  • Options /bimono, /trim and /fourmono also add equations with 2, 3 or 4 monomials respectively.
  • The combination /bimono /only will not put the cubic equations with the monomial ones.
  • Another method is called /fourmin, it takes cubic equations and adds a carefully selected set of equations of degree 4, composed only of very simple and sparse ones.
  • Another method is called /inid4, it takes all possible equations of degree 4.
  • Similarly /inid10, takes all possible equations at degree up to 10.
  • Another method is called /exhl, one variable is added for each of the possible states of each S-box.
  • There are many other methods implemented... Not all of them uniquely define the S-box. For example /mono /only doesn't.

Some complete and ready examples of equations for 6, 8 and 16 rounds of DES are also included  in this zip file. Alle these examples can be re-generated with axel.exe and the above options.

ONGOING CHALLENGE: Currently nobody can recover the key for 8 rounds faster than by brute force. A price of 100 US dollars will be offered by Nicolas T. Courtois for anyone that manages to achieve it on a PC with 2 Gigabytes of RAM, in less than 1 week*CPU, and given at most  16 chosen plaintexts. Open problem since 2005.
For people who want to try their software, exact examples of equations to solve for8 rounds and 16 chosen plaintexts, with their actual correct solution included in a separate file, are provided here in two versions: opns and in cubic version.

KeeLoq

We give here three examples of equations for KeeLoq, following this paper.
IT WAS UPDATED w.r.t. the right spec of KeeLoq on 21 October 2007 (previous spec. of KeeLoq found on Wikipedia had mistakes in it, but now is also corrected).

  • Example 1: the system of equations used in Attack 2 of the paper. Download it. This system of equations can be solved in 2 s as explained in the paper (the solution and all the intermediate files when converting to SAT and back can be found inside). Everybody can check how much time a favourite SAT solver will need to solve this .cnf file. MiniSat seems to offer the best performance.
  • Example 2: the system of equations for 256 rounds of KeeLoq with 64 plaintexts in the counter mode. Download it. (the solution seems to appear inside as a comment but in fact due to an innocent bug only half of it is correctly displayed, attackers please check and complete the other half).
  • Example 3: the system of equations for the full KeeLoq with 64 plaintexts in the counter mode. Download it. This system is a real challenge, currently far from being broken otherwise than by brute force. The solution is not given. Solutions obtained by brute force should not be submitted (this is cheating).

And here is the FULL equations generator for the KeeLoq encryption algorithm, however the actual name of the file is KeyLoq.exe, not KeeLoq.exe. Written by Nicolas T. Courtois and Gregory V. Bard. 

    • KeyLoq.exe Nr seed [/q or /c] Nr /insX [/fixY] [/cp] [/xl0 [/sat [/pico]]] [/dnf [/noconv]]. Legend:
      • Nr=number of rounds,
      • seed=seed for the random number generator, one can ignore it and always use seed=0,
      • /c means equations will be cubic (due to the degree of the ANF of the KeeLoq's NLF),
      • /q means equations will be quadratic with some extra variables added though,
      • /insX means use X plaintext/ciphertext pairs,
      • /fixY means fix Y first key bits to their values to reduce the key space.
      • with the option /cp the plaintexts are chosen to be consecutive - it is a counter mode,
      • /xl0 will call the XL0.exe program (contains an implementation of the ElimLin algorithm), a copy of this program has to be in the same directory,
      • /xl0 /sat will call XL0.exe program as an interface for MiniSat 2.0. - requires complex setup will not work on every machine; Actually it requires extra software components at present stage, to be updated later.
      • /xl0 /sat /pico will call XL0.exe program as an interface for PicoSat SAT solver - both XL0.exe and picosat.exe have to be in the same directory.
      • /dnf creates two extra files, XXX.cnf and XXX.dnf. The cnf file is a DIRECT representation of KeeLoq as SAT problem. Without any conversion, done directly. The dnf file is a set of "symbols" separated by double liner breaks, suitable for Semaev Agreeing-Gluing methods. It also generates a helper file .resolve, that contains the dictionnary between the variables names in cnf and dnf files, and their actual text names in other files.
      • /xl0 /sat /dnf /nonconv is the combination that will call MiniSat 2.0. directly on the .cnf file created by /dnf option. There is no conversion from MQ to SAT at all. Can be called 'a logical' attack, ANF representations are never used.
      • /xl0 /sat /dnf /nonconv /pico is the same but with PicoSat, easier to make it work on a Windows PC.
      • /slidXX /kslidYY [[/dnf /nonconv /xl0 /sat]], it is not compatible with the /cp option, it will do a known plaintext attack in which consecutive plaintexts will be shifted by XX rounds, and keys will be shifted by YY rounds.
        For example         KeyLoq.Exe 64 seed /q /slid528 /kslid16 /dnf /nonconv [[/xl0 /sat [/pico]]] will reproduce the Slide-Algebraic Attack 2 by [Courtois-Bard-Wagner FSE'2008] and the resulting .cnf file can be solved directly with any SAT solver.


Random Dense MQ Systems of Equations

These systems are random non-homogenous system of quadratic equations with n equations and n variables (the hard case), with various n, sparse or not, homogenous or not, and they have been chosen at random in such a way that they have a unique solution (by adjusting the constants to a randomly chosen solution and repeated random choice).

See hardproblems.html page.

 

SAT Solving Challenges

We have some examples and challenges for people that work on solving combinatorial and algebraic problems via conversion and SAT solvers. 

See hardproblems.html page.

 

Practical Algebraic attacks on Snow and E0

We have done lots of work on both.
To be published later.


This page is a subspace of the cryptosystem.net/aes/ page.

Maintained by Nicolas T. Courtois
Last updated on 18th of July 2007.