A Brief Experiment With Keccak

The MILP modelling of Keccak-p[400] using Nicky Mouha’s method and the S-bP extensions as discussed in class.

Keccak SBox

Thus \(\chi\) can be said to be an \([5 \times 5]\) bit SBox acting on each row of the state.

SBox := [0, 5, 10, 11, 20, 17, 22, 23, 9, 12, 3, 2, 13, 8, 15, 14, 18, 21, 24, 27,  6, 1, 4, 7, 26, 29, 16, 19, 30, 25, 28, 31]

MILP Model

Implemented as was done for PRESENT in class

Objective

Each Sbox is represented by a boolean variables. Objective is to minimize the sum of these variables.

Inputs

The 400 bit input difference is given

Constraints

• \(\rho, \pi\) are simple permutations.
• \(\iota\) is addition with a fixed constant, hence we need not worry about it
• Only hassle is with \(\theta\)

Modelling \(\theta\)

$$\theta : A[x,y,z] = A[x,y,z] \oplus \bigoplus_{j=0}^{4}A[x-1,j,z] \oplus A[x+1, j, z-1]$$ So essentially this function is a XOR operation amongst 11 bits.
I tried simplifying it using a parity bit approach i.e.

• Compute the parity bits for each column
• XOR proper parity bits

So now this functions was broken into two sub-functions havin 5 bit and 3 bit XORs respectively.

So now I tried modelling \(\theta\) using Mouha’s method -

• Computing Parity Plane

• Computing $\theta$

Problem

With this formulation of \(\theta\), after formulation of the other functions, Gurobi was giving the optimal solution to be \(0\) I exported the result file using the command - gurobi_cl ResultFile=r1.sol r1.lp

The problem was that Gurobi had assigned all \(x\)’s and \(p\)’s the value \(1\), that is the input difference had all values \(1\). By doing so, the value of all \(y\)’s could be assigned as \(0\) and still satisfy the above constraints. And now, since a zero state was being permuted, the input to the \(\chi\) layer was all zeros. Hence the optimal solution was \(0\)

Solving The Problem

Mouha’s constraints do not model the the XOR function exactly. Example for function \(a \oplus b = c\). Mouha’s constraints are -

The truth table for the above constraints is -

The last row satisfies the constraints, but it invalidates the XOR rule. When the number of elements being XOR’d is greater, the number of such invalid cases also increases.

A possible solution could be to add another constraint

Adding this to the list of constraints started to give out results in the MILP model. \(d_0\) is no longer constrained to be a boolean. Its only constrained to be an integer.

Solution Found By the Gurobi Solver For 1 Round Keccak

Optimal = 1

The picture shows the \(x\)’s and \(y\)’s . \(x\) is the input difference found by gurobi. and \(y = \pi \circ \rho \circ \theta (x)\)

For finding \(x\) (as shown above) I wrote a script to parse the .sol file generated by gurobi that gives out the values of the variables at the optimal. \(y\) was found by applying the proper operations on \(x\)

Problem Resolved The \(y\) values obtained from parsing the file do not match with the \(y\) values obtained from \(x\). The parsed \(y\) values show 2 active SBoxes instead of 1 😕. This is because parsed \(y\) values represent the values obtained immediately after \(\theta\) is applied on \(x\). This has been verified. So need to look into that. For the figure given below, blue bits are active.

$x$ values	$y$ values	$z$ values

The \(x\) values found do lead to \(1\) Active Sbox, but the \(y\) values show otherwise. 😞 Observed that \(y = \theta(x)\) Final values (represented by \(z\) ) show correct number of SBoxes as active

Note

Another observation is that the transition of \(\chi \circ \pi \circ \rho(y) \rightarrow z\) might have a zero probability as the constraints are not tight enough on the SBox. As from the example above, the difference transition is \([0,0,1,1,0] \rightarrow [0,1,1,0,0]\). However this transition is impossible with the SBox (confirmed with the DDT)

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.

Keccak Implementation

Implemented as class Keccak in python3 . Each round is implemented as \(\iota \circ \chi \circ \pi \circ \rho \circ \theta\) Of these functions, \(\iota\) has not been implemented. Implementation verified with the following sources -

1. https://github.com/mgoffin/keccak-python/blob/master/Keccak.py

   The verification was successful only after changing the rotation from a left rotate to a right rotate for \(\rho\) function

2. https://github.com/nickedes/keccak

   Verified successfully

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