Tools for Experimental Algebraic Cryptanalysis

public web page by Nicolas T. Courtois and his collaborators.

The content of this page is provided without any warranty. It is subject to copyright and does contain some efficient and innovative algorithms and data structures that were never published but are fully [or sometimes tentatively] implemented. Third-party tools will also be published here. 

P.S. Support can not be guaranteed.


Basic Tools.

Here is our AX64.exe  program that allows to know a rank (number of linearly independent equations) of a system of polynomial equations over GF(2). Under windows open cmd.exe, type "cd c:\CurentPathWhereTheseProgramsAre\" and type the following command:

  • AX64.exe 417 [/deg2] Filename.extension [/quiet] [/up3] . Legend:
    • /degX means the degree of the equations is X. Faster code is used for lower degrees.
    • /upY is applied to systems of degree 2 : they are expanded by XL to degree Y before their rank is computed.
      This can be used for studying the ElimLin and XL algorithms. "ax64.exe 4000" can be used to replace "
      XL64.exe" (previously known as "XL0.exe" which was discontinued) used with the same option /upY implements the full XL algorithm and much more, see below.
    • [/quiet] makes it more discrete, and in particular avoids pop-up windows.

Now to do the same modulo P, we use the following command:
  • AX64.exe 47717 Filename.extension [/quiet] .
    This can be slow. The first line of the file should be like "modulo 67". Legend:
    • [/quiet] makes it more discrete, and in particular avoids pop-up windows.

About Programs Provided Here.

Some tools found here are fairly simple, some are more complex. All have been implemented to handle very large but quite sparse  systems of Boolean polynomial equations on a PC with insufficient memory. Most computer algebra systems are actually totally incapable of manipulating systems of equations with comparable type and size on a PC. Not to say solving them.
These programs will only work if some Microsoft ms*.dll files are present on your PC. These files are not provided here but can be found on most PCs, they can copied by hand to your windows/system32/ directory, but really the simplest way to install them all at once it to install Microsoft Visual Studio.
Programs are experimental versions with no guarantee nor support. They produce a lot of spare intermediate and log files, that can be discarded later. They generate pop-up windows if they find a solution, the option /quiet disables it. If this notepad solution window is not closed, this will prevent other programs from running in the same directory. Programs use heavily the CPU, as well as the OS core, and in order to manage memory that is never sufficient, they continuously use the disk drives of the computer. They may use much more RAM than showed by Windows task manager, the showings of the Windows task manager are simply not accurate. The system should have at least 1 Gigabyte of RAM per running process (e.g. 4 Giga for a quad-core PC). They will work better if a particularly fast extra hard drive (or two) are attached to the computer with a special letter that could be i: or x: or y: or all of these:. Backup your data regularly: some disk drives will develop faults after a few months of intensive usage.

These tools are a mix of various code developed by Nicolas T. Courtois at various occasions. To the best of our knowledge they are free of any third party intellectual property rights. The exe files (closed-source code programs) can be used freely if the user acknowledges that they use ready tools developed by Nicolas T. Courtois AND links to this page. Source code is a private property of the author and is not intended to be made public ever.

Basic Equation Solving Toolbox - ElimLin over GF(P) 

Here is the AX64.exe and also AXEL.exe program that allows to solve systems of equations by the famous ElimLin method. Both programs work more or less the same, except that AXEL is for 32-bit windows version and it can allocate less memory. The first line of the file should be like "modulo 67" or start with comments like "//P=hex encoding of 67". Command line reference:

  • AX64.exe 47747 [/maxmpz256] [/up3 /up4 /xsl] [/maxmpz256] Filename.extension [/quiet] . Legend:
    • /quiet makes it more discrete, and in particular it avoids pop-up windows.
    • /up3 expands to degree 3, only if quadratic initially.
    • /xsl expands monomials XSL-style to degree 4, only if quadratic initially.
    • /maxmpz256 faster code for integers up to 256 bits, less malloc calls.

Basic Equation Solving Toolbox - ElimLin over GF(2^n) 

We use the same AX64.exe The first line of the file should be like "//P=ireeducible polynomial" for example "//P=0x020000000000000000000000000201" which has 113 bits. Command line reference:

  • AX64.exe 47742 [/maxmpz256] [/up3 /up4 /xsl] [/maxmpz256] [/skipnormal] Filename.extension [/quiet] . Legend:
    • /quiet makes it more discrete, and in particular it avoids pop-up windows.
    • /up3 expands to degree 3, only if quadratic initially.
    • /xsl expands monomials XSL-style to degree 4, only if quadratic initially.
    • /maxmpz256 faster code for integers up to 256 bits, less malloc calls.

Basic Equation Solving Toolbox - ElimLin in GF(2) 

Here is the same AX64.exe which can also handle ElimLin over GF(2). This has a lot more useful options. If and after it stops working the option /gtp is called by default, see below. Some options will only work if extra files are present on the PC. Command line reference:

  • AX64.exe 4000 [/degX] Filename.extension [/quiet] [/up3][/dense] [/alt] [/alt2] [/retract] [/inert] [/fullg] [/xsl or /xsm or /xsn] . Legend:
    • /degX means the degree of the equations is X . Memory-efficient up to degree 4 . Works for any degree.
    • /upY is applied to systems of degree2: they are expanded by XL to degreeY before ElimLin. This can be applied to any system of degree 2 and implements a powerful version of the XL algorithm, which should be called XL-ElimLin-GTP algorithm, where Elimlin and it it fails, the "geometric generalised T' method over GF(2) ", do replace the final step of the XL algorithm by something, as it seems, much more powerful than any other known version of the XL algorithm. 
    • /quiet makes it more discrete, and in particular it avoids pop-up windows.
    • /dense is another very different implementation, for dense systems.
    • /alt is an STL implementation, works for any degree but VERY bad in RAM usage.
    • /alt2 is a new implementation, slow but also works over fields like GF(2^n) , well almost.
    • /retract is a normal verison but does retract from all the substitutions and at the end write the initial system plus all the linear equations it could find.
    • /inert is an implementation close in the spirit to F4 algorithm, with substituion being replaced by adding suitable products of linear equations by monomials [but it avoids doing it for all monomials in a somewhat intelligent way, so in presence of sparsity it could still be actually better than standard F4].
    • /fullg is a basic implementation, though the default version [without /fullg] is in fact faster due to a trick that we do not describe here.
    • /singular will convert any system of equations to singular format and will try to call Singular if properly installed under cygwin.
    • /magma will convert any system of equations to Magma format but will not try to call Magma.
    • /xsl /deg2 this the [in-]famous XSL algorithm. Works only for degree 2 and expands to degree 4. Then it does apply ElimLin. It is a bad algorithm, but whoever told you it doesn't work, they lied to you. There are two other versions /xsm and /xsn that apply ElimLin first.
    • /tp is a simple but generalized T' method, don't use it, /gtp is better. 
    • /gtp is the default option, no need to call it,  geometric generalised T' method over GF(2), a slow but clever and powerful algorithm, never published, and which is called through GTP.exe that must be in the same directory. Has effect only after ElimLin stops working and called afterwards.
    • /gugtf is a sort of guess and determine, simple and slow, generalized but not geometric T' method. Not so good except for rare systems that collapse after a few guesses.
    • /gtpl8 is a dedicated generalized T' method with lifting from GF(2) to GF(8) , or even to any of  GF(2^Z) with option /gtplZ. Another very interesting algorithm, never published.



Java tool for DEEP INSPECTION of equations generated with ElimLin over GF(2)
in Cryptalanalysis of Block Ciphers

Here is the program DeepElimlin-1.5-SNAPSHOT.jar.
It is a Java tool developed by Guangyan Song [and Nicolas Courtois].


Command line reference:
  • java.exe  -jar   DeepElimlin-1.5-SNAPSHOT.jar   Filename.extension 
Inside the file it expects a list of linear equations with spaces between sections generated as stages r0,r1 etc of ElimLin. Currently it makes strong assumptions about variable numbering, and was designed for Simon block cipher primarily.

Here is one example how to use it for block cipher Simon: 

  • We need Simon.exe file which is doumented hereWe also need to make sure that ax64.exe and  DeepElimlin-1.4-SNAPSHOT.jar are in the same directory. 
  • Then we type in Windows command prompt: 
  • Simon.exe 8 /fixk40 /ins4 /xl0  [/cp]
  • Finally we type: 
  • java.exe  -jar    DeepElimlin-1.5-SNAPSHOT.jar   accumulated_lin.txt 8

BTW. if the java installation directory was the same as ours = C:\\Program Files\\Java\\jre1.8.0_91\\bin\\java.exe, this will actually happen automatically. 

Requirements: Sun Java must be installed on a PC under Windows x64. 
Java.exe should be accessible through system path. 

Remarks:
Another way to invoke this tool is to run
ax64.exe 4040 8 after some ElimLin run. It will automatically import the results. 

What can this tool do?

  • It will produce XX new files which show what happens inside ElimLin algorithm. 
  • It will also attempt to simulate what happens for K<4 (less instances), e.g. K=2 4 6 8 etc... 
  • This tool was primarily designed for deep inspection of equations generated during ElimLin attack on Simon.
  • It recognizes automatically from the variable names where round inside the cipher they belong to. 
  • It should work for other ciphers but it may be necessary to rename variables so that the tool can parse the round number correctly [e.g. a number 1..8 encoded as sth_001_005 for example which means variable 5 in round 1]. 
  • The tool pays special attention to variables which occur in the middle of encryption and less attention to those from the first or final round. 

Basic Equation Solving Toolbox - Conversion to SAT Techniques (and Semaev Algorithms) 

The same AX64.exe and also AXEL.exe program allows to solve systems of equations with SAT solvers if and only if the option /sat  is specified. A plethora of solving and conversion methods are implemented.
Command line reference for using ax64.exe as an entry point for playing with SAT solvers and conversion:

A Tool for Sillicon Optimization / Multiplicative Complexity for S-boxes

This is a unique piece of software which has no equivalent elsewhere. It takes as input an S-box and outputs circuit with low multiplicative complexity or a silicon optimization.

Done with our ax64.exe program. 

Input = truth table of the S-box, for example {12,5,6,11,9,0,10,13,3,14,15,8,4,7,1,2} 

ax64.exe 11117777 target  {12,5,6,11,9,0,10,13,3,14,15,8,4,7,1,2}     [/cryptominisat64292] [/freedomXX]  [[/goX /depY /timeoutZZ]].
Legend: 

References:

Tools for T-310 Cipher


Advanced Research and Experimental Tools.

Here is an old GTP.exe program (may use AX64 4161 instead).

GTP.exe allows to solve systems of equations by "The G

eometric Generalised T' Method" by Courtois. This is an advanced geometric algorithm, never published, for finding extra linearly independent equations at a given degree, which would normally be found by Gröbner bases techniques, but at a higher degree(!) with much higher memory and with much higher complexity. So in practice, this algorithm has no competitors in producing such equations on current computers. It somewhat an amazing tool albeit, the current implementation is very slow, waiting to be improved later. It should be considered as a research prototype for an early detection of exploitable algebraic vulnerabilities, and is a very powerful tool in this respect (the number of linearly independent equations typically grows and grows).
An additional second advanced T' method (but not yet in a 'geometric flavour', so less advanced) is also included. It starts by lifting of arbitrary equations over GF(2) to
GF(2^k) . See option /gtplX option described below. 

Command line reference for GTP:


 

Examples of Systems of Equations to Solve.

Some are publicly available already: see www.cryptosystem.net/aes/hardproblems.html .

How to Write the Equations.

Some hints:

  • Write variable names like A_3_5_2 or maybe like BC[4][1] which is not the preferred form but should work too.
  • Always use * sign, for example A_3_5_2*A_1_2_1.
  • Use line breaks to signify a new equation.
  • Use k_XXX where XXX is a number of key variables. Variables with such names should have special treatment and will be the last to be eliminated, but this only possible if they are distinguished by their names starting by k.
  • Avoid variable names starting with the letter "l".
  • Do not hesitate to add extra variables if this makes the equations more sparse or improves clarity, for example instead of writing
    X_2_4=1+k_34, write X_2_4=P_2_4+k_34 and P_2_4=1, where P_2_4 is a bit of the plaintext.
  • Try to make ALL equations of low degree, preferably 2, 3 or 4, avoid having the slighest monomial of degree more than 4. The algebraic degree of arbitrary Boolean functions can be easily reduced by introducing extra variables.
  • When converting files with polynomial algebraic equations (ANF) to SAT problems (CNF) with ax64.exe, native OR clauses are also allowed in the source text file, for example one can write a line of the form: OR x23  A_3_5_2   1+A_1_2_1. They are not coverted but just copied to the file.
  • For coding of S-boxes see these examples for GOST and other ciphers. Here iare our slides about Multiplicative Complexity and our paper on MC. 
  • In a sperate file write the assignments of ALL the variables, for debugging and guess-then-algebraic attacks.

(To see some examples of equations, run CTC2.exe or KeyLoq.exe or look here for DES . )

Tool For Point Splitting and Experimentation on EC Codes.

Here is our ec2decomp.exe  program. 

  • ec2decomp.exe ... . Some desciption can be found here
    • /sub23cubic is a special option which mixes MQ2 and MQ3 equations...
    • /cubic is applied to systems of degree 2 : they are expanded by XL to degree Y before their rank is computed.

Maintained by Nicolas T. Courtois
Last updated in July 2016.