新的所謂密鑰恢復攻擊預印本對 SIMON 有何影響？
就在最近，發布了針對 SIMON-32/64 的新攻擊，聲稱也適用於其他版本的密碼。該論文現已存檔，標題為A Note on SIMON-32/64 Security，描述了一種新的實用、低成本的密鑰恢復攻擊，它比窮舉搜尋要快得多。不幸的是，與實際描述他們假設的發現相比，作者花更多的時間來描述允許他們拒絕發布他們的分析方法的零知識證明。
**摘要：**本文介紹了一種新方法對 SIMON-32/64（美國國家安全域於 2013 年發布的密碼）進行密碼分析的結果。我們的密碼分析主要考慮了組合屬性。這些屬性使我們能夠在幾小時到幾天的時間內從兩個明文/密文對中恢復密鑰，而計算資源相當有限。
與所有已知的密碼分析（包括密鑰窮舉搜尋）相比，我們的密碼分析技術的效率是不透露所使用的密碼分析技術的理由。我們採用了一種零知識啟發的證明方法，該方法始於
$$ 11 $$.
僅考慮目前已知的情況，這次攻擊的含義是什麼？它是否適用於任何類似 SIMON 的分組密碼，還是適用於大量密碼的通用技術？
**TL;DR：**這篇論文似乎是個玩笑，或者是妄想；“零知識證明”什麼也證明不了。
該報告聲稱已經找到了對小型分組密碼 SIMON-32/64 的有效密碼分析。確切的細節是故意不透露的。然而，為了讓讀者相信該方法確實存在，在第 4 節中介紹了所謂的“零知識證明”（不是通常所說的零知識）。我將在這裡展示的是這個證明沒有顯示任何內容，並且使用具有相同塊大小的任何塊密碼都可以相對實現相同的壯舉。
SIMON是一個分組密碼家族。在這裡，我們討論其中“最小的”SIMON-32/64，它具有 32 位塊和 64 位密鑰。塊大小在這裡很重要：這意味著當文章顯示 64 位明文和密文時，這些確實是明文塊對和密文塊對，以 ECB 模式加密。
**讓我們看看第一種“證明”：**論文展示了一些將明文“YHWHYHWH”加密為密文“YHWHYHWH”的密鑰（兩者都使用 ASCII 編碼）。如上所述，這些確實是將“YHWH”（32 位明文塊）加密為“YHWH”（32 位密文塊）的密鑰；重複只是分散注意力。如果您找到加密給定 32 位塊的密鑰 $ P $ 到給定的 32 位密文塊中 $ C $ ，那麼當然相同的密鑰會加密 $ P\mathbin|P $ 進入 $ C\mathbin|C $ ， 和 $ P\mathbin|P\mathbin|P $ 進入 $ C\mathbin|C\mathbin|C $ ， 等等。這就是歐洲央行模式的意思。
現在，取一個給定的明文塊 $ P $ ，以及給定的密文塊 $ C $ . 找到匹配的密鑰有多難？如果您使用隨機密鑰 $ K $ , 加密 $ P $ 帶鑰匙 $ K $ 產生一個密文塊 $ C’ $ ，其大小為 32 位。因此，擁有的機率 $ C’ = C $ 是關於 $ 2^{-32} $ . 這意味著如果您嘗試隨機鍵，您平均需要嘗試大約 $ 2^{32} $ 鍵來查找匹配項。任何體面的筆記型電腦都應該可以嘗試一下 $ 2^{25} $ 每秒密鑰（我在這裡假設加密一個塊需要 400 個時鐘週期，CPU 執行在 3.2 GHz，並且有四個核心；我們可能會比使用 AVX2 跳馬做得更好，但讓我們專注於愚蠢的、基本的軟體）。因此， $ 2^{32} $ 將在大約兩分鐘內嘗試密鑰。換句話說，如果你讓我找到將“YHWHYHWH”加密為“YHWHYHWH”的密鑰，那麼我應該每兩分鐘找到一個。文章中介紹的六個按鍵代表一台筆記型電腦不到 15 分鐘的工作時間！所有這一切都是使用 SIMON-32/64 作為黑匣子，即假設它是一個完美的、理想的分組密碼。
**現在，讓我們研究第二個“證明”：**作者採用了從 King James Bible 中提取的 64 位消息（塊對）的大型語料庫。在原始 UTF-8 文本中（真的是 ASCII，全是英文，不包含單詞cafe ），這是一個4452069字節的文件。這意味著那裡有 4452062 個 8 字節的序列。讓我們把那個低到 $ 2^{22} $ 使計算更容易。“證明”是它們顯示將這些塊中的一個映射到這些塊中的另一個的鍵；表 6 顯示了 18 個這樣的明文/密文/密鑰三元組（文章正文說“19”，但表中只有 18 個）。
採用 64 位塊的完美理想密碼（這裡我們甚至不會使用 SIMON-32/64 使用 32 位塊和 64 位消息實際上是 32 位塊*對的事實）。*取一個隨機密鑰。加密其中一個 $ 2^{22} $ 明文塊轉換為 64 位塊。輸出 64 位塊是其中之一的機率是多少 $ 2^{22} $ 在列表中？它是 $ 2^{-42} $ （因為有 $ 2^{64} $ 可能的 64 位塊和 $ 2^{22} $ 目標）。這意味著如果你嘗試隨機鍵，你會得到一個匹配 $ 2^{42} $ 平均隨機鍵。在 $ 2^{25} $ 每秒，我們每兩天談論一個鍵；18 個鍵將需要一個多月的時間。作者聲稱需要 120 天，所以他們在這裡有點滯後。同樣，將分組密碼作為理想的黑匣子，基本的野蠻攻擊比密碼分析聲稱的要好。
（有一些細節：這裡的一些基本優化是“攻擊”只會加密一個 32 位塊開始，並且只有在與第一個匹配時才加密第二個；此外，在 RAM 中查找只有當輸出塊是 ASCII 時才可以優化匹配，即如果每個字節的最高位為零，所以我們最終對於每個密鑰：一個 SIMON-32/64 加密，頂部測試輸出字節的位，僅在 1/16 的情況下查找 RAM，並且僅在 1/64 的情況下進行第二次塊加密是在 RAM 中查找；因此，我們可以很容易地將成本近似為“1每次嘗試 SIMON-32/64 加密”。）
所以無論他們在做什麼，它似乎都比與分組密碼的內部結構無關的蠻力更好。
一個懸而未決的問題是，這是否是蓄意的惡作劇、損害 eprint 維護者聲譽的歪曲嘗試，還是自欺欺人。我不試圖回答這個問題。