Keccak-MILP

What This is All About

This repository contains the code for creating the MILP model to count the number of active SBoxes in each round of Keccak-p with block size of 400 bits. The constraints are created by mostly following the method proposed by Mouha et. al. and its S-bP extension proposed by Sun et. al.

The "experiment" are the additional constraints on the XOR operation which help increase the accuracy of the predictions but seem to come at a cost. More on this later...

mew.py spits out a .lp file, which I fed into the Gurobi Optimizer to get the values of the optimized objective. keccak.py is my implementation of Keccak which is in no way optimized for anything. I basically used it to check the validity of the results I was getting. The table below shows the results visualised for 1 Round of Keccak-p[400]

x values	y values	z values

Generating the .lp File

python mew.py --r [no. of rounds] > rounds.lp

This will output a file in the LP Format which can be used as input to a suitable solver. I used Gurobi.

Solving the Model using Gurobi

$ gurobi_cl ResultFile='<resultfile.sol>' <modelfile.lp>

Observations

I can see why this is not of much consequence 🤦

Results Table

r	Best Objective	milp_model_1	milp_model_2
1	1	8.33s (c)	7.21s (c)
2	4	250.4s (in)	137.94s (c)
3	10	1121.38s (in)
4	102	940s (in)

_{completed(c), incomplete(in) ▲ The incomplete(in) times are Gurobi run-times}

For model_1 apart from the r=1 run, all other runs were interrupted runs. Looking for some serious computing power 🚀

Update

• Results from milp_model_2_gen.py are wayyy faster than milp_model_1_gen.py as some constraints have been optimized.
• model_3 performance is not upto expectations

---

References

1. https://keccak.team/
2. https://link.springer.com/chapter/10.1007/978-3-642-34704-7_5
3. https://link.springer.com/chapter/10.1007/978-3-662-45611-8_9