多次散列會比一次散列更多、更少或類似安全嗎

多次散列會比一次散列更多、更少或類似安全嗎？

沖洗掉這個問題：

• 我看到了這個說法：

  • 列表項： Don't do this: hash = sha512(password + salt); for (i = 0; i < 1000; i++) { hash = sha512(hash); // <-- Do NOT do this! }但是，如果您要雙重雜湊，請執行此操作hash = sha512(password + salt); for (i = 0; i < 1000; i++) { hash = sha512(hash + password + salt); }
  • 請參閱： https ://stackoverflow.com/questions/4948322/fundamental-difference-between-hashing-and-encryption-algorithms/4948393#4948393

• 對我來說，您在重新散列中嘗試做的似乎是減慢蠻力攻擊。

• 儘管生日問題可能適用於多重散列，但它似乎同樣適用於第一個範例（該人標記為“不要這樣做”），至於第二個範例（該人感覺更舒服）。

• 在任一範例中，一旦發現衝突，則在該點重新散列是沒有意義的（因為它將在散列及其衝突之間重現相同的結果）。

• 這個問題的具體情況是：我在上面的問題中給出的那個人的例子在他們的斷言中是否正確 - 例子2會減少碰撞，機率說，發生的頻率更低？

我在一個答案中尋找什麼：

• 這不是我的專業領域（這就是我在這裡問它的原因，你的專業在哪裡）。請隨時糾正我的誤解和有問題的假設。

• 我對詳細的技術解釋感興趣，只要它附有外行對步驟的解釋，尤其是結論（重點是外行的解釋）。

• 我在理論上詢問所有單向散列函式（如果散列算法的廣泛類別之間存在區別，請隨意指出這些，同時理解您的答案的含義實際上將應用於我的部分散列算法類似SHA-2、SHA-3 或 bcrypt）。

• 我查看了 10 個不同的 crypto.stackexchange.com 問題和答案，這些問題和答案似乎與這個問題非常相似，但要麼他們處理了形成案例答案的特定案例，要麼他們給出了理論證明而沒有外行解釋用他們的證明實際上在做什麼以及外行對他們的答案的結論。

  • 出於這個問題的目的，假設我的微積分沒有達到標準，我通常也沒有閱讀密碼學中使用的數學變數，但假設我可以遵循代數並且如果你告訴我變數是什麼，我可以塵埃落定我的微積分代表（或連結到他們的解釋）。

提前感謝您對這個問題的幫助。

我在上面的問題中給出的那個人的例子在他們的斷言中是否正確 - 例子 2 會使碰撞，機率說，發生的頻率降低？

那裡有幾個斷言：

一種斷言是，yield 的函式1定義為password + salt``hash

hash = sha512(password + salt); 
for (i = 0; i < 1000; i++) {
   hash = sha512(hash); // <-- Do NOT do this!
}

比定義的屈服函式2更容易發生碰撞password + salt``hash

hash = sha512(password + salt);
for (i = 0; i < 1000; i++) {
   hash = sha512(hash + password + salt);
}

這在理論上是正確的，並且在實踐中對於窄散列（例如 80 位）是可以觀察到的。

一種看待它的方法是

• 固定隨機函式的輸出集H $ H $ 迭代的n $ n $ 時間趨於縮小n $ n $ 增長（參數：它永遠不會增加n $ n $ 確實如此，並且迭代雜湊的衝突導致了一些縮小結果，這裡是 SHA-512）；
• 兩個隨機不同輸入的隨機函式的碰撞機率是其輸出集大小的倒數。

因此這是可以理解的（即使迭代隨機函式n $ n $ 時間可能不會完全產生一個隨機函式超過輸出集的剩餘部分），即碰撞機率Hn(X) $ H^n(x) $ 對於兩個隨機不同X $ x $ 隨著增加n $ n $ .

這限制了for循環迭代的函式 1 的抗碰撞性H:H↦小號H一個-512(H) $ H: h\mapsto\operatorname{SHA-512}(h) $ . 而在 2 中，迭代的函式會隨著輸入的password + salt變化而變化，因此輸出集隨著n $ n $ 取決於那個輸入。在雜湊作為隨機函式的模型下，2 也是一個可能達到全集的隨機函式，並且不同輸入的衝突機率password + salt不會增加，因為n $ n $ 做。

---

也有人斷言，出於這個原因，我們應該在實踐中使用 2 而不是 1，這是不正確的，原因有很多：

• 至少對於任何抗衝突的雜湊，如 SHA-512，我們根本不需要擔心衝突或循環。
• 在上下文（密碼散列應用程序）中，整個迭代函式的抗碰撞性不是問題。原像電阻是。甚至對於不抗碰撞的 SHA-1，以及任何現實的n $ n $ ，我們不必擔心破壞 1 所需的雜湊評估比破壞 2 需要的雜湊值要少得多，包括實際的預計算。

---

2 的一個優點是：在硬體中實現稍微困難一些，因為硬體需要在每次迭代時使用密碼和鹽，因此必須儲存。因此，加速 2 的 ASIC 將比 1 更複雜。這是我認為 2 在實踐中不如 1 糟糕的唯一原因。它仍然很糟糕，因為n=1000 $ n=1000 $ 面對 ASIC 或 GPU 進行密碼搜尋，迭代速度不夠慢；並且因為整個事情並沒有使用記憶體，因此失去了現代記憶體硬密碼雜湊（如scrypt或Argon2）提供的針對暴力密碼搜尋的額外保護。

---

多次散列是否比一次散列更安全

這主要取決於目標，它決定了要使用的散列

• 如果我們出於密鑰拉伸的目的進行雜湊處理，通常是在對密碼或密碼進行雜湊處理時，是的：針對暴力搜尋的安全性隨著輪數的增加呈線性增長。但同樣，我們應該使用記憶硬密碼散列。花費相同的時間，即使是過時的bcrypt也將提供比純粹迭代雜湊的構造更高的安全性，例如PBKDF2或函式 1 和 2，在 ASIC、FPGA 和 GPU 的密碼破解時代，這些顯然是不推薦的。
• 如果我們不止一次地散列以加強一些具有缺陷的加密散列函式（比如它的抗碰撞性被破壞），可能是的。例如，函式 2（password + salt替換為要散列的消息）將修復MD5或SHA-1除了它們的輸出寬度之外的所有已知安全缺陷，即使我們只多做一輪而不是 1000 輪。然而，這是在性能和可用性，因為我們需要對消息進行兩次雜湊處理，因此在某些情況下儲存它。
• 對於其他加密目的，包括使用現代雜湊從寬密鑰派生簽名和密鑰，沒有。為了這些目的，我們可以使用 SHA-2 或 SHA-3（在問題中命名）。迭代散列不是必需的，甚至可以稍微降低碰撞阻力（如果按照 1 執行），但有一個例外：如果散列具有長度擴展屬性（如 SHA-2 具有，但不是 SHA-3），並且如果這是不可取的，一旦散列的輸出重新散列是合理的（這不需要儲存消息兩次）。

這是一個直覺（相對於嚴格）的解釋：

散列函式看起來是隨機的，但實際上並沒有給結果添加任何熵。實際上，它通過許多輸入可能導致相同輸出的屬性來消除熵。（只有一對一和 on 函式可以保留熵。）因此，雜湊對其自己的輸出的每次應用都會刪除熵，直到它收斂到可能遠小於欄位大小的順序的重複循環（有限組）。我不知道 LSR 雜湊組的順序有任何界限證明。

第二個範例通過添加密碼和鹽來刷新每個應用程序的熵。因為它是不同的操作，所以它具有每輪切換到不同循環（陪集）的效果。

因此，向後工作，我們從直覺開始，將雜湊函式視為一組許多循環，而不是完全隨機化的映射。一個理想的散列函式應該是一個大循環，在那個函式中，第一個例子就可以了。

如果我們要對一個更簡單的代數域做一個非常粗略的類比，我們可能會認為我們正在查看一個複合域，該複合域由通過應用散列函式定義的核群的許多陪集組成，而只有素數域才有最大命令。

還有一件事，因為我一直在混合循環和熵損失的概念。LSR 的熵容量有限，並且在每一輪中都會損失一部分多餘的部分。這意味著任何輸入可能最終進入的所有循環集的並集組成一個比輸入本身小得多的欄位。將這些概念放在一起，重複應用會慢慢地將所有輸入放入少量的小循環中，這意味著您將大大增加碰撞的機會。

顯而易見，更大的衝突機會意味著更大的機會猜測將雜湊到與密碼相同的值的輸入，從而授予訪問權限。請記住，密碼本身是無關緊要的，只是能夠提供一個雜湊值與密碼相同的值。

希望有人可以更嚴格地使用抽象代數定理和 LSR 雜湊組的屬性來證明這一點。期待它。謝謝你的問題。

引用自：https://crypto.stackexchange.com/questions/98969