發現差異和空間複雜度
在Biham 和 Shamir的 DES-like Cryptosystems的差分密碼分析中，他們提供了使用差分輸入的範例，例如 $ \Omega_p = 00\ 80\ 82\ 00\ 60\ 00\ 00\ 00_x $ . 大部分文章是關於差分密碼分析的，並介紹了通用方法，即查找子密鑰的方法。但是我找不到關於如何找到範例中使用的差異的明確解釋。
我確實想到了提供一個 S-box 以檢索差異，但是這些 S-box 只有 6 位輸入用於 4 位輸出（在 DES 中）。所以進行這種分析所需的記憶體空間是 $ 2^6 \times 2^4 = 1024 $ 整數 $ \approx 4\ Ko $ . 這可以很容易地放在 RAM 中。該方法由 Christopher Swenson 在Modern Cryptanalysis（2008，Wiley Publishing；第 4 章，第 122-145 頁）中介紹。
然而，給定一個具有更大輸入的 S-box，例如 FEAL-X 中使用的 S-box（但仍處於損壞狀態），我們需要一個具有以下給定大小的表： $ 2^{32} \times 2^{32} = 2^{64} $ 整數 $ \approx 2^{32}\times 16\ Go $ . 這樣的東西太大了，無法儲存在當今的一台電腦上。
因此我的問題是：如何在沒有此分析的大小限制的情況下為更大的輸入輪函式找到正確的微分。
如果要分析如此大的沒有結構的 Sbox，您會將分析視為一次性預計算。
僅以經典的差分密碼分析為例，在預計算之後，您只需要跟踪最高機率差分，因為如果將高機率差分與低機率差分結合起來，您已經失去了相當多的優勢回合你的攻擊將失敗。
至於 FEAL，在 32x32 圓形功能中有很多結構，分而治之是要走的路。
如果有一個隨機選擇的巨大Sbox，生活會很困難，但對於設計師來說也很難證明他/她隨機選擇的Sbox的實力，有任何保證。例如，依賴於鍵的 Blowfish Sbox 只有 8x32（感謝@JD），這有助於限制需要考慮的輸入差異的數量。