5 輪 Fides AE 密碼的活動 S-box 數是多少？
在論文“Fides: Lightweight Authenticated Cipher with Side-Channel Resistance for Constrained Hardware”中提到，Fides密碼的活動 S-box 數量在 5 輪中為 22，但我的結果顯示它是 25((9-3- 1-3-9)) 使用midori 中使用的相同概念（幾乎相同的MDS 矩陣）來建構MILP 模型。
Q. 有沒有人得到和我一樣的結果？如果沒有，除了詳盡的搜尋之外，我應該採取什麼步驟來找到正確的答案？
您的結果是準確的：25 個活動 S-box 是您在 5 輪跟踪中可以做到的最好的。這是 5 位 S-box 變體的範例，尊重 S-box 約束（並假設我正確閱讀了規範）： $$ \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} $$
那麼 22 是從哪裡來的呢？好吧，對 S-box 和線性層進行精確建模可能會很昂貴。相反，我們可以用單個位表示每個半字節並使用分支號 $ 4 $ 幾乎 MDS 層，以獲得活動 S-box 的下限。也就是說，對於 MixColumns 中狀態的每一列，我們有 $$ \begin{align*} \sum (x_i + y_i) &\ge 4d \ d &\ge x_i \ d &\ge y_i ,, \end{align*} $$ 對於虛擬變數 $ d $ , 輸入和輸出變數 $ x_i $ 和 $ y_i $ . 因為這是一個幾乎 MDS 矩陣，我們還需要額外確保如果輸入為非零（如這裡所述）： $$ \begin{align*} 4\sum y_i - \sum x_i &\ge 0 \ 4\sum x_i - \sum y_i &\ge 0 ,. \end{align*} $$
然而，當一個人這樣做時，它會導致更寬鬆的界限 $ \ge 18 $ 超過 5 輪的有效 S-box，而不是 22 輪！因此，22的來源仍然是個謎。相同的觀察結果也適用於 6 輪，甚至更多。