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 the FreeCheck.exe program that allows to know a rank (number of linearly independent equations) of a system of polynomial equations over GF(2). U nder windows open cmd.exe, type "cd c:\CurentPathWhereTheseProgramsAre\" and type the following command:

  • FreeCheck.exe [/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 XL algorithm. XL0.exe used witht he same option implements the full XL algorithm and much more, see below.
    • [/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 

Here is the XL0.exe program that allows to solve systems of equations by the famous ElimLin method. 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:

  • XL0.exe [/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.

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

The same XL0.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 xl0.exe as an entry point for playing with SAT solvers and conversion:

Advanced Research and Experimental Tools.

Here is the GTP.exe program.

GTP.exe allows to solve systems of equations by "The Geometric 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) toGF(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 XL0.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.
  • 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.)

Maintained by Nicolas T. Courtois
Last updated in March 2010.