README

This project contains the code for generating practical results for 3-Round Keccak-256 and 4-Round Keccak[r=640, c=160]. The seed has been set to the one leading to the solution quickly.

Prerequisites

• gcc/g++: Tested with version 9.2.0
• Python: Tested with version 3.7.6
• Gurobi Optimizer: Tested with version 9.1.2 build v9.1.2rc0 (win64)

Since only basic features are being used, both newer and older versions are likely to work.

Compilation

To compile the code for each step, use the following command:

g++ [step*_filename].cpp -o [program_name_for_step*] -O2 -Wl,-stack=4000000000 -std=c++11

Running

After compilation, you can run the programs and Python scripts as follows:

[program_name_for_step*].exe
python [step*_filename].py

File Structure

The project is organized as follows:

│  README.md
│
└─code
    ├─3-round Keccak-256
    │      EQU.h
    │      SHA3.h
    │      step1.exe
    │      step1_get_equation_system.cpp          // generate step2_equ.txt, which is the equation system we need to solve
    │      step2.exe
    │      step2_equ.txt
    │      step2_test.cpp          // based on step2_equ.txt, print some log and generate step3_m26.txt, which is the last message block of step3_msg.txt
    │      step3.exe
    │      step3_msg.txt
    │      step3_msg26.txt
    │      step3_verify.cpp          // based on step3_msg.txt, print the digest (256-bit '0')
    │
    └─4-round Keccak[r=640, c=160, l=80]
      EQU.h
      SHA3.h
      step1.exe
      step1_generate_milp_code.cpp          // based on step1_mat.txt and step1_prob.txt, generate step2_milp.py
      step1_mat.txt
      step1_prob.txt
      step2_milp.py          // based on Gurobi Optimization, generate step3_milp_res.txt (the process can be terminated when the solution with objective=33 is found with around a minute, but it costs around an hour to verify that it is the best solution)
      step3.exe
      step3_analyse_milp_result.cpp          // based on step3_milp_res.txt, print the strategy of linearization (Table 7 in the paper)
      step3_milp_res.txt
      step4.exe
      step4_test.cpp          // print some log and generate step5_msg.txt
      step5.exe
      step5_msg.txt
      step5_verify.cpp          // based on step5_msg.txt, print the required digest (75 1a 16 e5 ...)