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.

Simon Cipher in Algebraic Cryptanalysis Setting
Simon cipher is a special gift by the NSA for algebraic cryptanalysts: this is because it has an EXCEPTIONALLY LOW multiplicative complexity [see 2013/633 paper]. For decades algebraic cryptanalysts have conjectured, tried to break and have to a large extent broken ALL ciphers with such characteristics if not too complex; or if they are 'simple enough'; for example if the do NOT have too many rounds. No other block cipher in block cipher research community have ever yet been proposed which has so little complexity in one round. In our new paper to appear in SECRYPT 2016 we show that the per-round security of Simon is a LOT less than for CTC2 even though CTC2 was specifically designed to be broken by algebraic attacks.
The only thing which makes this cipher secure is if it has a sufficiently large number of rounds.
Now how larger is
'sufficiently large'? Simon is very popular, a very nice object to study for cryptanalysts and new attacks are invented every month.

For example the ElimLin algorithm [invented by Courtois c. 2006 and first used in a serious attack on a real-life cipher DES by Courtois and Bard cf. eprint 2006/402] breaks up to 16 rounds of Simon, see recent paper by Raddum and this is just the beginning. Nobody was so far able to predict the bahaviour of ElimLin, so we don't know if it stops at 16 rounds and 17 rounds is infeasible to break, or it could be that we just need to try harder with a larger computer.  

We have developed a starter project for students to experiment with algebraic cryptanalysis of Simon: see here. Ready executable can be found 
here. This program requires ax64.exe to present in the same directory.
Usage:  Additionnal tools:
The command line is, for example: ax64.exe 9051777 32 128 8 2 1 /cp. It is quite fast and memory-efficient. For now only the "forward" direction is implemented [ignores a lot of equations which depend on the ciphertext]. Results will be very similar as running Simon.exe with /relaxC option but not identical as some equations really depend on the plaintext choice. Morevoer this technique is sometimes more powerful than ElimLin: it finds more equations than ElimLin [cf. Petr Susil EPFL PhD thesis and this paper].


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 (obsolete 32-bit) or rather ax64.exe which is a 64-bit version, which must always be used with the first parameter being 777. This program allows one to generate equations for CTC2. Usage: 

  • ax64.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,
    • /ins0 means use a binary tree-like method with ever increasing number of plaintext/ciphertext pairs and progressive aggregation,
    • 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.
    • /sat option will use a sat solver, by default this file should be present in the current dir.

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.

GOST

Most of our unique software remains confidential/proprietary. However, some more or less advanced S-box optimizations are available to download and use for experiments in software cryptanalysis.
More files for advanced attacks and advanced options [no documentation at this moment].
 

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 ax64.exe with a number of individual files with extension .eqs, which need to be in the same directory.

  • Example of command line is  ax64 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.
  • There exist many ways to fix key variables. Option /fix14 is a specif way to fix 14 variables but there is a possibility to influence the key in various ways. For example /fk0-2,5,14-56 will fix a specific subset. 
  • Moreover /kSeedX where X is a number allows the vary the key in a pseudo-random deterministic way. Similarly /SeedY where Y is a number allows the vary the data/plaintext.ciphertext in a pseudo-random deterministic way.
  • 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 ax64.exe and the above options.

ONGOING CHALLENGE: Currently nobody can recover the key for 8 rounds faster than by brute force. A price of  10 ETH or equivalent in 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 for
8 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.