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 axel.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.