雜湊速度如何根據字元串長度而變化？
令人驚訝的是，我無法在 Google 上找到這個問題的答案。
如果我有一個基於用於密碼生成的任何流行散列算法的函式，當字元串長度增加時速度會改變多少百分比/幅度？假設從函式中檢索鹽。
Function GetHash("CAT") Function GetHash("I like cats, cats are great, I am a longer string")我只尋找最近似的答案，例如差異可能很小（對於較長的字元串，時間增加 <1%），或者它可能慢兩倍（100% 增加），或者可能更多。
與另一個答案相反，我假設雜湊函式是面向密碼的類型；我的回答是：輸入大小對良好實踐中的速度幾乎沒有影響，即使輸入比問題中的輸入長得多。
例如，面向密碼（或熵拉伸、鍵拉伸）的雜湊函式適用於將 ( password , salt ) 對轉換為雜湊，然後將 ( salt , hash ) 儲存在數據庫中，以便稍後檢查( password , salt ) 對，通過重新計算hash並將其與數據庫中的salt進行比較，不允許直接從 ( salt , hash ) 對中提取密碼。
這樣的雜湊實際上有三個輸入：密碼、鹽和一個工作因子，它控制計算**雜湊輸出所需的工作量。所述努力被參數化以使測試（例如）1000萬個最常見的密碼選擇的列表有些昂貴。例如，對於計算一個雜湊值需要在通常使用的 CPU 上 0.1 秒的**工作因子，使用該 CPU 在 12 天內測試 1000 萬個密碼，使用具有許多 CPU 的伺服器需要幾個小時，對於一個井來說可能只需要幾分之一 -使用 ASIC 或 FPGA 裝備對手（例如公開出售）。工作因數的選擇是合法使用努力之間的折衷（轉化為延遲和每次密碼使用所花費的功率，更強大的硬體的資本投資）；和安全性：計算雜湊的工作量越低，從洩露的（鹽，雜湊）對中找到公共密碼的成本就越低。
面向密碼的散列的一個範例是具有 PRF 的PBKDF2和具有（例如）SHA-256 作為散列的 HMAC，由NIST 特別出版物 800-132 標準化。更安全的是Bcrypt。可以說更安全的是帶有 HMAC-SHA-256 的Scrypt，它可以利用合法使用者機器上的多個 CPU 和充足的 RAM，作為在合理的時間範圍內顯著提高並行攻擊所需的投資成本的一種手段。密碼雜湊競賽的結果體現了最新的技術水平。
對於所有這些功能，即使選擇提供最小安全性的工作因子，密碼**和鹽輸入甚至比問題中的數量級還要大，執行時間主要取決於工作因子；對程式碼質量和使用的 CPU 有所了解；並且密碼和鹽的大小非常小（由workfactor控制的每秒執行時間的限制可能為 1MB ）。簡而言之，那是因為密碼和鹽輸入，當很長時（通常：超過大約 64 個字節）只處理一次並減少到固定的小尺寸（使用 SHA-1 或 SHA-256 等雜湊），然後重複處理，重複計數受工作因素控制。
更新：Maarten Bodewes 在評論中指出，對於使用 HMAC-SHA-256 作為 PRF 的常見 PBKDF2，情況可能有所不同。我的分析（如下）是密碼大小的時序依賴性不會發生在提供良好安全性的軟體實現中，但僅適用於那些從安全形度來看次優的約 2 倍或更多。
使用 HMAC-SHA-256 作為 PRF 的 PBKDF2 的大部分執行時間用於迭代 $ m_j=\operatorname{HMAC}(P,m_{j-1}) $ ， 在哪裡 $ P $ 是密碼輸入，並且（與 $ H=\operatorname{SHA-256} $ ):
$$ \operatorname{HMAC}(P,m)=\begin{cases} H((P\oplus\text{opad})|H((P\oplus\text{ipad})|m))&\text{if }|P|\le64\text{ octets}\ \operatorname{HMAC}(H(P),m)&\text{otherwise} \end{cases} $$ 在哪裡 $ x\text{pad} $ 是 64 字節的常數，並且 $ P\oplus x\text{pad} $ 與 $ P $ 用零填充到 64 個八位字節。什麼時候 $ |P|\le64 $ 和 $ |m|=32 $ , 計算 $ \operatorname{HMAC}(P,m) $ 涉及 2 次 SHA-256 呼叫，每次呼叫 96 個八位字節的數據，因此總共 4 次呼叫 SHA-256 的輪函式。 PBKDF2 的良好實現應該最大限度地提高給定執行延遲的安全性，因此應該進行速度優化。因此，使用 HMAC-SHA-256 作為 PRF 的 PBKDF2 的良好實現應該
- 代替 $ P $ 和 $ \operatorname{SHA-256}(P) $ 如果 $ P $ 超過 64 個八位字節；
- 軟墊 $ P $ 通過在右側附加零並預先計算到 64 個八位字節 $ P\oplus\text{ipad} $ 和 $ P\oplus\text{opad} $
- 應用輪函式 $ R $ 的 $ \operatorname{SHA-256} $ 對這些，獲得 32 字節 $ h_\text{in}=R(\text{IV},P\oplus\text{ipad}) $ 和 $ h_\text{out}=R(\text{IV},P\oplus\text{opad}) $
- 在控制執行時間的核心循環中，計算 $ m_j=R(h_\text{out},R(h_\text{in},\operatorname{pad}(m_{j-1}))) $ 使用 2 次呼叫 $ R $ , 並結合 $ m_j $ 異或成一個單獨的 32 字節值。
只有步驟 (1) 和 (2) 可以具有時序依賴性 $ |P| $ . 顯示了可在核心環 4 中移動的 PBKDF2 的所有步驟。
如果實現使用 SHA-256 作為黑盒，但仍然在核心循環之外執行 (1) 和 (2)，則必然有 4 次呼叫 $ R $ 在核心循環中，而不是 2。至少在軟體中這不是最佳實踐，因為它降低了對密碼搜尋的保護大約 2 倍；但它並沒有引入核心循環的執行時間對 $ |P| $ .
如果實現在核心循環中移動（2），而不是（1），它很可能會有一些時間依賴性wrt $ |P| $ 在核心循環中（大約是線性的，一些斜率可能是正數，包括 $ 64 $ 八位字節；然後穩定在獲得的值 $ |P|=32 $ 然後）。然而，將有固定的 4 次呼叫 $ R $ 每個核心循環，以及在使用將支配執行時間的編譯語言的任何半體面的軟體實現中，使時間依賴性wrt $ |P| $ 小的。
如果實現未能在核心循環之外執行 (1)，那麼它的核心循環可能會表現出時間依賴性 wrt $ |P| $ , 邁著僵硬的步伐 $ |P|=65 $ 對應於從 4 到 6 的八位字節 $ R $ ，然後以大約一半的剛度邁出 $ |P|=120+k\cdot64 $ 每個額外的八位字節 $ R $ . 這是一個很強的時間依賴性 $ |P| $ ，但僅適用於從安全形度來看嚴重不足的實現範圍 $ |P| $ 經過考慮的。
為速度優化的雜湊（如 MD5、SHA-1 或 SHA-256）不應單獨用於密碼儲存和驗證，因為它們的速度本身就是一個毀滅性的弱點；更糟糕的是，這種弱點隨著時間的推移而增加，因為即使在今天，摩爾定律也顯著加快了在並行引擎上執行良好的任務。