2
$\begingroup$

It is mention in the paper " Fides: Lightweight Authenticated Cipher with Side-Channel Resistance for Constrained Hardware" , the number of active S-boxes of Fides cipher is 22 over 5 rounds but my result shows it is 25((9-3-1-3-9))using the same concept used in midori (same almost MDS matrix) to construct MILP model.

Q. Is anyone else got same results as mine? if not , is there any steps should i take to find the correct answer other than exhaustive search?

$\endgroup$
  • $\begingroup$ How did you get the result? $\endgroup$ – xxx--- Oct 2 '18 at 18:50
  • $\begingroup$ as mentioned in the question, I extended in the MILP model used in Midori to include 8 columns Not 4 and changed the shift rows values. $\endgroup$ – hardyrama Oct 3 '18 at 6:17
  • $\begingroup$ Just curious, can you share the MILP code? $\endgroup$ – xxx--- Oct 4 '18 at 20:15
  • $\begingroup$ very large number of equations to post it here $\endgroup$ – hardyrama Oct 13 '18 at 5:05
  • $\begingroup$ Post it on Github and link here (may be) :-) $\endgroup$ – xxx--- Oct 15 '18 at 5:29
3
$\begingroup$

Your result is accurate: 25 active S-boxes is the best you can do in a 5-round trail. Here's an example for the 5-bit S-box variant, respecting the S-box constraints (and assuming I read the specification correctly): $$ \begin{bmatrix} \mathtt{19} & \mathtt{00} & \mathtt{1c} & \mathtt{1b} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{1c} & \mathtt{00} & \mathtt{00} & \mathtt{1e} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{00} & \mathtt{0c} & \mathtt{00} & \mathtt{1b} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{1b} & \mathtt{04} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \end{bmatrix} $$ $$ \xrightarrow{SB} \begin{bmatrix} \mathtt{11} & \mathtt{00} & \mathtt{04} & \mathtt{10} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{11} & \mathtt{00} & \mathtt{00} & \mathtt{10} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{00} & \mathtt{11} & \mathtt{00} & \mathtt{04} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{04} & \mathtt{10} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \end{bmatrix} \xrightarrow{SR} \begin{bmatrix} \mathtt{11} & \mathtt{00} & \mathtt{04} & \mathtt{10} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{11} & \mathtt{00} & \mathtt{00} & \mathtt{10} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{11} & \mathtt{00} & \mathtt{04} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{00} & \mathtt{04} & \mathtt{10} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \end{bmatrix} \xrightarrow{MC} \begin{bmatrix} \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{00} & \mathtt{04} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{10} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{11} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \end{bmatrix} $$ $$ \xrightarrow{SB} \begin{bmatrix} \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{00} & \mathtt{0f} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{0f} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{0f} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \end{bmatrix} \xrightarrow{SR} \begin{bmatrix} \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{0f} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{0f} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{0f} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \end{bmatrix} \xrightarrow{MC} \begin{bmatrix} \mathtt{00} & \mathtt{0f} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \end{bmatrix} $$ $$ \xrightarrow{SB} \begin{bmatrix} \mathtt{00} & \mathtt{11} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \end{bmatrix} \xrightarrow{SR} \begin{bmatrix} \mathtt{00} & \mathtt{11} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \end{bmatrix} \xrightarrow{MC} \begin{bmatrix} \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{11} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{11} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{11} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \end{bmatrix} $$ $$ \xrightarrow{SB} \begin{bmatrix} \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{02} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{08} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{04} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \end{bmatrix} \xrightarrow{SR} \begin{bmatrix} \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{02} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{08} \\ \mathtt{00} & \mathtt{00} & \mathtt{04} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \end{bmatrix} \xrightarrow{MC} \begin{bmatrix} \mathtt{02} & \mathtt{00} & \mathtt{04} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{08} \\ \mathtt{00} & \mathtt{00} & \mathtt{04} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{08} \\ \mathtt{02} & \mathtt{00} & \mathtt{04} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{02} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{08} \\ \end{bmatrix} $$ $$ \xrightarrow{SB} \begin{bmatrix} \mathtt{06} & \mathtt{00} & \mathtt{0b} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{1d} \\ \mathtt{00} & \mathtt{00} & \mathtt{0c} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{1b} \\ \mathtt{01} & \mathtt{00} & \mathtt{02} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{03} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{03} \\ \end{bmatrix} \xrightarrow{SR} \begin{bmatrix} \mathtt{06} & \mathtt{00} & \mathtt{0b} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{1d} \\ \mathtt{00} & \mathtt{0c} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{1b} & \mathtt{00} \\ \mathtt{02} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{01} & \mathtt{00} \\ \mathtt{03} & \mathtt{03} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \end{bmatrix} \xrightarrow{MC} \begin{bmatrix} \mathtt{01} & \mathtt{0f} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{1a} & \mathtt{00} \\ \mathtt{07} & \mathtt{03} & \mathtt{0b} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{01} & \mathtt{1d} \\ \mathtt{05} & \mathtt{0f} & \mathtt{0b} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{1b} & \mathtt{1d} \\ \mathtt{04} & \mathtt{0c} & \mathtt{0b} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{1a} & \mathtt{1d} \\ \end{bmatrix} $$

So where does the 22 come from? Well, modeling the S-box and the linear layer exactly can be costly. Instead, we can represent each nibble by a single bit and use the branch number $4$ of the almost-MDS layer to obtain a lower bound of active S-boxes. That is, for each column of the state in MixColumns, we have $$ \begin{align*} \sum (x_i + y_i) &\ge 4d \\ d &\ge x_i \\ d &\ge y_i \,, \end{align*} $$ for dummy variable $d$, input and output variables $x_i$ and $y_i$. Because this is an almost-MDS matrix, we also need to additionally ensure that the output is nonzero if the input is (as described here): $$ \begin{align*} 4\sum y_i - \sum x_i &\ge 0 \\ 4\sum x_i - \sum y_i &\ge 0 \,. \end{align*} $$

However, when one does this, it results in the looser bound of $\ge 18$ active S-boxes over 5 rounds, not 22! So it remains a mystery where the 22 came from. The same observations also apply to 6 rounds, and possibly above.

$\endgroup$
  • $\begingroup$ Very thankful for your answer $\endgroup$ – hardyrama May 24 at 7:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.