如何在無鹽迭代密碼散列的迭代次數中獲得線性加速？
在他們2015 年的論文“更多輪次，更少安全性？”中 Guo、Jean、Mouha 和 Nikolić在第 5.4 節中聲稱可以恢復密碼 $ P $ 給定的雜湊 $ D $ 生成的不同密碼 $ H^k(P) $ 大約 $ T_1=\frac{2^n}{D\cdot k} $ 雜湊評估。
現在我明白了，使用標準原像搜尋，您應該至少找到一個原像 $ 2^n/D $ 對完整迭代雜湊的評估，所以 $ T_2=\frac{k\cdot 2^n}{D} $ 雜湊評估。
給出的理由 $ T_1 $ 是：
現在觀察到時間複雜度可以降低一個因子 $ k $ . 這是因為評估一個密碼猜測需要 $ k $ 內部使用的雜湊函式的評估
$$ the password hash $$，但每一個額外的猜測都只需要一個雜湊函式評估的額外成本。這有效地加速了窮舉搜尋 $ k $ ：給定 $ D $ 密碼雜湊，恢復其中任何一個的時間複雜度為 $ 2^n/(D \cdot k) $ .
我現在的問題是（基於我目前對上述引用的理解）：
鑑於 $ H^{i}(P) $ 為了 $ i\in{1,\ldots,k} $ 僅使用一項評估 $ H $ 一個人如何計算 $ H^k(P’) $ 對於任何 $ P’\neq P $ ?
或者以不同的方式但（希望）等效地問：
在初始評估後的額外檢查僅花費一次雜湊評估的情況下，這種圖像前搜尋加速技巧究竟是如何工作的？
我認為證明這一說法的唯一方法是作者的想法如下，因此不適用於任何 $ P’\neq P, $ 但具體 $ P’ $ 在那條小路上：
計算 $ H^i(P), $ 為了 $ i=1,2,\ldots,k. $ 這給了你雜湊 $ P, $ 叫它 $ H_0. $
現在定義序列 $ P’_i=H^i(P), $ 為了 $ i\geq 1,2,3,\ldots. $
評估 $ H^i(H_0) $ 獲得 $ H(P’_i), $ 為了 $ i\geq 1,2,3,\ldots, $ 每人一次評估的額外費用。當然這些 $ P_i’ $ 幾乎可以肯定是不同的，直到軌跡長度與雜湊輸出空間的平方根相當。