散列 - 數字簽名和簡單的拉伸

兩個非常基本的問題：

1. 數字簽名

---

為什麼不能簡單地替換請求中的雜湊值？

例子：

- Mallory creates two different documents A and B, that have an
  identical hash value (collision).
- Mallory then sends document A to Alice, who agrees to what the
  document says, signs its hash and sends it back to Mallory.
- Mallory copies the signature sent by Alice from document A to
  document B. Then she sends document B to Bob, claiming that Alice
  signed the other document (document B).
- Because the digital signature matches the document hash, Bob's
  software is unable to detect the modification.

參考：http ://en.wikipedia.org/wiki/Collision_attack

它沒有被傳輸，一個秘密，同時你最終只是發送雜湊？這是怎麼回事？

散列函式也非常適合簽署數據。例如，如果您使用 HMAC，您可以通過將數據與已知**但未傳輸的值（秘密值）**連接起來的雜湊值來簽署數據。 所以你發送純文字和 hmac hash。然後，接收方簡單地用已知值對送出的數據進行雜湊處理，並檢查它是否與傳輸的 hmac 匹配。如果相同，您就知道它沒有被沒有秘密值的一方篡改。這通常用於 HTTP 框架的安全 cookie 系統，以及通過 HTTP 進行數據的消息傳輸，您希望數據具有一定的有效性。

參考：https ://stackoverflow.com/questions/4948322/fundamental-difference-between-hashing-and-encryption-algorithms

2. 數字簽名

---

我不明白為什麼這段程式碼產生的 colitions 比第二個少 一旦你與兩個輸入發生衝突，它如何幫助為下一個遞歸循環附加相同的兩個值？

不建議：

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);
}

我把那部分讀了五遍，雖然有點道理，但我很難完全理解它。

現在，hash1 的碰撞機率為 0.001%。但是當我們執行下一個 hash2 = sha1(hash1); 時，所有 hash1 的衝突都會自動變成 hash2 的衝突。所以現在，我們將 hash1 的比率設為 0.001%，第二次 sha1 呼叫增加了這一點。

參考：https ://stackoverflow.com/questions/4948322/fundamental-difference-between-hashing-and-encryption-algorithms

對問題 2 的回應：

**算法1：**把算法改成這樣，會更容易解釋

hash1 = sha512(password + salt1); 
hash2 = sha512(password + salt2); 
for (i = 0; i < 1000; i++) {
   hash1 = sha512(hash1); // <-- Do NOT do this!
   hash2 = sha512(hash2); // <-- Do NOT do this!
}

對於 2 個不同的輸入 hash1 和 hash2，如果在第 10 次迭代中發生衝突，那麼接下來的 990 次迭代將處理相同的工作並輸出相同的 hash1 和 hash2。

您散列的越多，您可以在迭代 12、15、20、100、101、314 時創建的中間衝突就越多……。每次額外的迭代都會增加衝突的機率。

如果 Bob 執行這段程式碼（前一個循環的一半）

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

如果 Alice 執行這段程式碼（前一個循環的一半）

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

根據之前的評論，安全性降低了，因為 Bob 和 Alice 可以因為碰撞機率增加而互相冒充。當算法完成時

P(hash1 == hash2) > 1000 * P(sha512(password + salt2) == sha512(password + salt1) )

如果有超過 Bob 和 Alice、John、Joe、Jack 和 Jeremy 在執行這個循環，那麼“生日悖論”的破壞性影響仍然會增加碰撞的機率。

**算法2：**每次迭代都有一些不同，這是很大的不同。

hash1 = sha512(password + salt1);
hash2 = sha512(password + salt2);
for (i = 0; i < 1000; i++) {
   hash1 = sha512(hash + password + salt1);
   hash2 = sha512(hash + password + salt2);
}

如果在迭代 i 處發生碰撞，則下一次迭代 i+1 很可能會產生非碰撞。**當提供不同的輸入時，**每次迭代都可以證明 sha512 的碰撞機率非常低。當算法完成時，在 Bob 和 Alice 之間拆分算法

P(hash1 == hash2) == P( sha512(password + salt2) == sha512(password + salt1) )

注意：正如參考頁面所建議的那樣，每次迭代可能有不同的鹽值。

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