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:

Experimental algebraic attacks on block ciphers - experiments on toy ciphers. (What are algebraic attacks on block ciphers ?). The main goal is to publish systems of equations for instances that are already broken, and those that are not far from being broken but remain a challenge to solve.
- Remark 1: We want to encourage different researchers to verify the feasability of certain attacks, try to propose better ones, and to address challenging open problems. The experimentation offers a golden opportunity for researchers to do what no other have ever achieved. This gives a metric of scientific achievement independent from opinions of experts. History shows that experts are typically almost always wrong, and care more about their interests than about being right. (In cryptology they first claim or imply that something is not feasible, after it is demonstrated to be feasible, they either present the results as their own or claim that the result is really excessively trivial and was already known before). Certain cryptosystems will not survive a reality check, other will be reinforced in their good reputation.
- Remark 2: We also consider:
  - certain stream ciphers (only if broken by the same methods and not too weak)
  - generic reference systems of equations with special properties that make them efficiently solvable.
Information about known methods for solving [sparse, structured and overdefined] systems of multivariate polynomial equations: advice, comparison and benchmarks.
- Promote good methods and tools. Both commercial and non-commercial.

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.

In particular use CTC2.exe for all research related to AES. 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. It was also 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. If an attack cannot break CTC2 for 7

Here is the windows executable program CTC2.exe that allows to generate equations. Usage:

CTC2.exe 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.
- /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.

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:

The first called "cubic": write 112 cubic equations per S-box.
The second method called "opns" is to use an optimised non-standard representation of each S-box with a low gate count (which requires many extra variables but gives equations of degree 2 that are extremely sparse).
Another method is called "fourmin" takes cubic equations and adds equations of degree 4 but only very simple and sparse ones.
Another method is called "exhl", one variable is added for each of the possible states of each S-box.
There are many other methods... Some other are described in this paper. Not all of them uniquely define the S-box.

We give here several examples of equations for 6, 8 and 16 rounds of DES packed in one zip file. Individual files for individual S-boxes that allow even more options are also included.

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 Courtois for anyone that manages to achieve it on a PC with 2 Gigabytes of RAM, in less than 1 week*CPU, and given up to 16 chosen plaintexts.

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 XL0.exe program (ElimLin), 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. Up to n=24 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). For higher n, they may have several solutions which should influence the difficulty to find one of them. All systems have at least one solution. They have no trapdoor and no hidden algebraic/combinatorial structure.
We encourage the researchers to solve these systems by their favorite method (one solution is enough, it is not demanded to find all of them). We will post their timings on this page.

Download:

MQ systems to solve.

SAT Solving Challenges

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

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.