AlPAtH is a software framework to run algebraic attacks on hash functions. It is available here. Please read the following (contents of the README file) before using it. The presentation of this page is to be improved in the future.

This framework is intended to run algebraic attacks on hash functions, but could be extended to any kind of ciphers (block, stream). It provides a framework to generate equations, solve these equations and interpret the results.

This framework can do several things. 1) generate polynomial systems for a preimage attack on hash functions. A solution to this system should give a preimage of the hash of the message "Hello world\n". 2) run solvers on these systems for a given hash function number of round, a given amount of fixed variables, a given method for fixing variables. For instance, you could try to find a preimage on SHA-1 for 48 rounds with 300 message bits fixed at random. 3) produce log on these results, mainly the time needed by the solving. 4) produce plots on the solving time according to number of fixed variables (directly, as png or as tikz). There is 8 ways to fix k variables: - z: message bits 1 to k are fixed to zero - zp: k message bits (randomly picked) are fixed to zero - i: message bits 1 to k are fixed to one - ip: k message bits (randomly picked) are fixed to one - m: message bits 1 to k are fixed to the correct bits - mp: k message bits (randomly picked) are fixed to the correct bits - r: message bits 1 to k are fixed to random values - rp: k message bits (randomly picked) are fixed to random values

- You have to first write the code to generate the equations for each hash functions. Some are already provided: md5, sha1, sha256, sha512, ripemd128 and ripemd160 The way you generate equations does not matter as long as your program respects the interface provided in the file `interface.m'. It contains the only 3 magma functions you should implement. - You have to provide a solving software that take as input a file in ANF format (see the README file of the anf2cnf software). It is also yours to be sure that the solving method is correct, as this framework only cares about the time it takes, not the solution. To read a file in ANF format, you may use the libanf2cnf C library that provide a function to parse such files, and a data structure to handle boolean polynomial systems. Such solvers are already provided: - GBsolve: it uses libanf2cnf to parse the input, and use magma to solve the polynomial system - SATsolve: it uses libanf2cnf to parse the input, propagates some variables at ANF level, and convert the polynomial system into CNF SAT entry. It then use the cryptominisat solver to solve the boolean system. - looping: it does pretty much the same as SATsolve, except that it stops the SAT-solver after some times and reruns the solving after propagating variables at ANF level again.

We give an example to illustrate this point. Let us say that we want to know the time of an algebraic preimage attack on 48 rounds SHA-1 when 500 (over 512) correct message bits (at random positions) are fixed. Let us say that we want to solve the system using `SATsolve'. Then, one has just to run ./SATsolve_do sha1 48 500 mp The program automatically generate the equations for 48 rounds SHA-1 (if they were not already generated) dumped in ANF format. The system is then passed to the SATsolve program which tries to solve the system. After that, you can see that the `sha1/r48' directory has been created and populated. In particular, you can see in the directory `sha1/r48/logmp/SATsolve/' the files 500, 500.out and 500.log which contain respectively the computation time, the computation standard output and the computation error output. If you run the same command again "./SATsolve_do sha1 48 500 mp", the previous files will have extra lines corresponding to the new computation. It could be tedious to run the computation for a large amount of fixed variables. You shall use the `sample' program. For instance, if you want to try fixing variables at random from 510 variables fixed and decreasing this number until 0 or until the computation is manually stop. Just run ./sample SATsolve_do sha1 48 500 rp You can increase the number of trials for each number of fixed variables by affecting correspondingly an environment variable called TRIALS. For instance: export TRIALS=4 ./sample SATsolve_do sha1 48 500 rp After you have done several computations, you may want to plot the graphics corresponding to the computation time in function of the number of fixed variables. This can be automatically generated with the `harvest' and `harvest_to_tikz' programs. Just type ./harvest sha1 and you will the plots of every timinigs you have done so far will be displayed. If you want to generate images in png format, you can run ./harvest png sha1 they will be located in the `out' directory. If you need tikz plots, you shall use the `harvest_to_tikz' program as follows ./harvest_to_tikz sha1 Note that both programs may take several hash functions name as arguments. Finally, you can save all your timings (everything located in a log* directory) with the `save' program. ./save To remove every generated log files, you may use the `clean' program. To remove everything, including the systems generated, you may use the `clean_init' program. Your directory will be just as it was before any modification (except what is contained in the `out' and `data' directories.

This framework is a collection of magma programs, shell scripts and C programs. Here is how the framework is organized. It has several shell scripts - clean: remove log files - clean_init: remove all generated files and directory (including log files) - do_process: this script has to be symlinked to be used properly. It is used to solve one system. It is a wrapper over `process'. Cannot be used directly - generate: usage: ./generate hash_name round_number generates the equations for a hash function, for a given number of rounds it is used by the `process' program if the equations are not already generated - getsystem: usage: ./getsystem hash_name round_number fixed_bits_number fix_method returns the corresponding system in a readable format (magma) - harvest: usage: ./harvest hash_name1 hash_name2 ... plot the graphics corresponding to the given hash functions. With the png option (as first argument), generates png image in the `out' directory - harvest_to_tikz: usage: ./harvest hash_name1 hash_name2 ... similar to harvest, but generates tikz files in the `out' directory - hash: usage: ./hash hash_name [round_number] apply the hash function with the given number of rounds to the standard entry (defaults to the max number of round) - process: usage: ./process hash_name round_number fixed_bits_number fix_method try to solve the corresponding system with the solver in the $SOLVER variable (defaults to SATsolve). - sample: usage: ./sample solver_do hash_name round_number fix_method max_fix calls solver_do with the corresponding parameters from max_fix number of fixed variables to 0 (or when the program is manually stopped) - save: saves anything that has been done (in hash_name/log*) into an archive in the `data' directory. To reuse a previously saved data, juste uncompress a data file when inside the root directory.

- magma: this is a proprietary computational algebra system. More information on this software may be found at http://magma.maths.usyd.edu.au/magma/ - anf2cnf: this a free software. More precisely, only the library libanf2cnf.so shipped with anf2cnf is needed. These can be found at http://www-salsa.lip6.fr/~bettale/anf2cnf.html - cryptominisat: this is a free SAT-solver by Mate Soos. It is available at http://www.msoos.org/cryptominisat2 - bash, gcc, make: free software, probably already installed in your distribution Note that the executables `magma' and `cryptominisat' have to be available in your PATH.

Just create a directory named after the hash function, and put inside a magma file called `main.m'. It should contain at least the 3 functions described in the file `interface.m'. Note that this framework is shipped with 6 hash functions: md5, sha1, sha256, sha512, rmd128 and rmd160.

Your solver has to take as input an ANF file (see the README of anf2cnf). Just put your executable file in the root directory. Assume that it is called `mysolver'. You have to create create a new symlink to `do_process' caled <solver name>_do. For instance: ln -s do_process mysolver_do Note that this framework is shipped with 3 solvers: GBsolve, SATsolve and looping.

AlPAtH is a contraction of Algebraic Preimage Atack on Hash functions. If you think the name sucks, you may suggest a better one.

This framework is free software (GPLv3), but it uses a proprietary program (magma) as a building block.

It is a project to port this framework in Sage. If someone is interested, feel free to do it.

For any question that is not answered here, please feel free to send me your question. Maybe the feature you ask for is already implemented, but not documented (yet).