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.
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 ax64.exe which is 32-bit or ax64.exe whcih 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:
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 ax64.exe with a number of individual files with extension .eqs, which need to be in the same directory.
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
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).
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.
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.
Practical Algebraic attacks on NSA block cipher Simon
See our source code
This page is a subspace of the
cryptosystem.net/aes/
page.
Maintained by Nicolas T. Courtois
Last updated on 18th of July 2007.