SHA-3 (SHAKE128) 的基準（雜湊率）
為了估計暴力攻擊的時間，我們需要計算密鑰空間大小除以雜湊率，其中雜湊率（雜湊/秒）根據電腦的能力而變化。
網站https://bench.cr.yp.to/results-hash.html顯示了不同電腦的雜湊率。你能解釋一下以下兩個令人困惑的現象嗎？
- 雜湊率隨著消息大小的增加而降低。
- 對於 SHAKE128，Core i3 的雜湊率高於 Core i7。
雜湊率隨著消息大小的增加而降低。
基準引用的內容隨消息大小而減小。但這不是“雜湊率”，至少在 OP 認為的某台電腦上每單位時間的雜湊值中。單位是每字節的周期數，因此更高的值意味著所花費的周期數、花費的時間和執行的雜湊值更少（所有其他更重要的事情都是相同的）。
假設電腦已使用其全部計算能力進行散列，總共有 $ u $ CPU(s)，每個都有 $ n $ 執行頻率的核心 $ f $ （以赫茲為單位），總時間 $ t $ （以秒為單位），散列 $ m $ 每個消息 $ b $ -byte，產生的每個雜湊都需要 $ c $ 一個 CPU 的一個核心的一個執行執行緒的周期。它認為
$$ u\cdot n\cdot f\cdot t=m\cdot c $$ 推導：左邊是所有循環的次數 $ u\cdot n $ 核心，與 $ f\cdot t $ 給定頻率和時間的每個核心的周期。右邊是循環數 $ m\cdot c $ 考慮到有多少消息，以及每個散列需要多少個週期，對消息進行散列是必要的。它們是相等的，因為假設“使用了它們的全部計算能力”，當 $ m\gg u\cdot n $ 通過在核心之間平均分配消息。
連結的基準報價是什麼 $ c/b $ 以每字節週期數為單位，其中周期數是一個執行緒實際使用的周期數，該執行緒執行計算雜湊的順序程式碼。這個數量 $ c/b $ 很大程度上取決於算法、CPU 架構和程式碼質量（包括對 CPU 的適應性、編譯器……）；關於價值 $ b $ ，尤其是在低時（見下文），這就是為什麼 $ c/b $ 給出了幾個值 $ b $ ; 很少在其餘部分。
注意：在核心上執行的執行緒必須共享該核心的 $ f\cdot t $ 循環。我對引用的基準的理解是，每個核心的執行緒數被認為是 CPU 架構的一部分；如果可以調整，例如在啟動時調整為 1 或 2，則將有單獨的基準測試或/和 $ c/b $ 引用的將是最高的。
注意：引用的基準和目前的答案堅持固定的雜湊輸出大小，例如 32 字節。SHAKE128 具有可變大小的輸出，這可能是一個額外的參數。 最實用的散列（包括 SHA-3/SHAKE）將字節（填充後）組合成固定大小的塊 $ B $ -字節（ $ B=136 $ 對於 SHA3-256/SHAKE128），並具有按順序處理塊的迭代結構。它遵循 $ c $ 與成長 $ b $ 大約為
$$ c=c_0+c_1\lceil(b+b_0)/B\rceil $$ （忽略記憶體和其他影響），其中 $ 0\le b_0<B $ 是以字節為單位的填充大小 ( $ b_0=1 $ 對於所有 SHA-3)， $ c_0 $ 是循環中的固定成本， $ c_1 $ 是散列額外塊的額外周期數（與 $ c_1<c_0 $ 對於 SHA-3), $ \lceil x\rceil $ 是理性的 $ x $ 四捨五入到下一個整數。數量 $ c/b $ 基準報告的是：
- 對於小消息（最多 $ B-b_0 $ -字節），大約 $ (c_0+c_1)/b $ , 迅速下降 $ b $ ;
- 對於大型消息（ $ b\gg B) $ ， 大約 $ c_1/B $ , 很大程度上獨立於 $ b $ .
全面的 $ c/b $ 大多降低為 $ b $ 增加（收斂到某個常數），但最初會出現明顯的鋸齒狀跳躍。
在較早的問題和對另一個的評論中，OP 提到想要散列 40 位消息，並想知道在多大程度上容易受到消息的暴力搜尋。讓我們評估一下散列（占主導地位）需要多少時間來覆蓋整個消息空間。
消息是 $ \lceil40/8\rceil=5 $ -byte，因此引用基準的適當列用於 $ b=8 $ -byte 消息（給出相同的 $ \lceil(b+b_0)/B\rceil=1 $ ）。配備Intel Core i7-7800X $ n=6 $ 執行的核心 $ f=3.5\text{GHz} $ ，它的時間為 SHAKE128，中位數為 $ c/b=112.25 $ 每個字節的周期。因此與 $ u=1 $ 這樣的CPU，是時候hash all $ m=2^{40} $ 消息是：
$$ t=\frac{m\cdot(c/b)\cdot b}{u\cdot n\cdot f}\approx\frac{2^{40}\cdot112\cdot8}{1\cdot6\cdot3.5\cdot10^9}\approx47000\text{s}\approx13\text{h} $$ 注意：在這個計算中，我們使用了 $ b=8 $ 的基準，而不是 $ b=5 $ 對於散列的字節數，因為我們正在嘗試計算 $ c $ 作為 $ (c/b)\cdot b $ 在這種情況下 $ c $ 大約獨立於 $ b $ . 如果我們散列一條長消息，我們會使用低得多的 $ c/b $ 以該條件為基準，並且 $ b $ 對於散列的消息，因為我們會處於以下情況 $ c $ 大約與 $ b $ . 在這之間，我們可以計算 $ (c/b)\cdot b $ 引用尺寸最接近的兩個基準，推導出兩個對應的 $ c $ , 並為我們的 $ b $ 至 $ c=c_0+c_1\lceil(b+b_0)/B\rceil $ 模型。
注意：“基礎”值 $ f $ 重要的是而不是更高的“Turbo”，因為後者不能支持多核，至少在製造商規格範圍內。 對於擁有一台電腦的個人來說，這種搜尋很容易實現。此外，彩虹表只允許進行一次計算，然後在幾秒鐘內案例如行動電話反轉 40 位消息的任何散列。
這項任務非常簡單，使用 CPU 就足夠了（它們最容易程式）。對於更大規模的攻擊，經過初始編碼工作後，GPU 在速度或/和成本和能量方面會更有效（它們的卓越性能來自 $ n $ 每個 GPU 有數百個）。FPGA 和最終的 ASIC 甚至更勝一籌（它們有可能降低 $ c $ 以及通過針對任務精確定制電路來增加散列容量的額外投資）。這就是比特幣礦工的總算力如何超過 $ 2^{82} $ 每天 SHA-256 雜湊（2018 年 5 月，根據該來源報告 SHA256d 雜湊包含兩個 SHA-256）。
對於 SHAKE128，Core i3 的雜湊率高於 Core i7
在註意到雜湊率以周期/字節為單位後，該觀察結果相當於：在比較中，在英特爾行銷名稱中的“Core i”之後具有更高數字的 CPU 核心恰好具有需要更少時鐘週期的**理想特性比另一個。
這遠非一般規則，因為（對於 Intel x86 系列） $ c/b $ 更多地取決於CPU的最新程度。所述差異主要歸因於架構改進，在 2011 年第一季度引入了引用的Core i3和引用了Core i7的 2017 年第二季度之間增加了IPC。
的價值觀 $ b $ , $ u $ , $ n $ 和 $ f $ 對電腦的雜湊性能有更本質的影響，即 $ m/t=u\cdot n\cdot f/c $ 每秒雜湊，與 $ c $ 成正比 $ b $ 對於大 $ b $ .
