在兩個輸出相同之前，可以使用 HKDF 導出多少個不同的密鑰？
在兩個輸出相同之前，可以使用 HKDF 導出多少個不同的密鑰？
這個問題是關於抗碰撞性的，而不是關於生成具有不同參數的不同密鑰（例如不同的鹽/資訊參數）。
對於使用 SHA-256 的 HKDF 會是 $ 2^{128} $ 因為 HMAC-SHA-256 的抗碰撞性是 128 位？
我已經看過幾次了，所以我想指出一些普遍的誤解。人們經常認為，對於密鑰派生，不重複是非常重要的，因為那是一個休息。然而，這實際上是非常不正確的，反之亦然。我會解釋。
“理想情況”是只選擇鍵，真正隨機。在這種情況下，如果我使用 128 位密鑰，生日悖論仍然成立。因此，生成後 $ 2^{64} $ 真正隨機的鍵，它們會重複。這根本不是問題。相反，它保證即使您看到了所有先前生成的密鑰，您也沒有關於下一個密鑰的資訊。此外，所有（對稱）加密都使用 IV，因此您需要隨機 IV 和密鑰發生衝突，以便能夠檢測到兩個不同的人/案例正在使用相同的密鑰。
人們會認為最好有目的地選擇鍵，以免它們重複。但這意味著密鑰的隨機性越來越小，並且隨著時間的推移熵越來越低。特別是，給定過去的密鑰，已知新密鑰不等於其中任何一個。所以，我們實際上不想這樣做。
只是為了強調這一點，直接使用 AES 進行密鑰派生（例如，在 CTR 模式下），當您接近生日界限時，密鑰派生的質量會下降，因為密鑰不能重複。因此，由於密鑰不能重複，這意味著密鑰看起來不像是隨機的。我知道這與大多數人的直覺相反，這就是為什麼我覺得指出這一點很重要。
目前的答案是為了回答一個可以回答的問題，以及碰撞實際上很重要的情況：比如，它們被觀察到，我們想排除它是偶然的；或者某些權威規定每個藍精靈必須有一個唯一的密鑰，並且缺乏令人信服的論據來區分橡皮圖章和文書工作。請參閱Yehuda Lindell 的回答，了解為什麼密鑰派生函式輸出處的衝突實際上不會損害使用派生密鑰進行加密的安全性。
我們將使用 HKDF 的定義和RFC 5869的符號。
在兩個輸出相同之前，可以使用 HKDF 導出多少個不同的密鑰？
在標准假設下 $ \mathtt{Hash} $ 使用，假設輸入的組合 $ \mathtt{IKM} $ ¹ 和 $ \mathtt{salt} $ 不重複，固定 $ \mathtt{info} $ ，並且無意在輸入的選擇中產生碰撞²，碰撞前的世代數主要取決於：
- $ \mathtt{L} $ , HKDF 輸出的字節大小（生成的密鑰通常是 $ 8\mathtt{L} $ -少量）
- $ \mathtt{HashLen} $ , 輸出的字節大小 $ \mathtt{Hash} $ ，即 SHA-256 為 32。
一個有用的近似值是 $ 16^{\min(\mathtt{L},\mathtt{HashLen})} $ 或等效地 $ 2^{4\min(\mathtt{L},\mathtt{HashLen})} $ , 剩餘碰撞機率約為 39% 時 $ \mathtt{L}\ne\mathtt{HashLen} $ , 63% 時 $ \mathtt{L}=\mathtt{HashLen} $ .
當我們對低機率感興趣時 $ \epsilon $ 碰撞，這樣 $ \sqrt{2,\epsilon},2^{4\min(\mathtt{L},\mathtt{HashLen})} $ 什麼時候 $ \mathtt{L}\ne\mathtt{HashLen} $ ， 或者 $ \sqrt{\epsilon},2^{4\mathtt{L}} $ 什麼時候 $ \mathtt{L}=\mathtt{HashLen} $ .
例如，對於 SHA-256，如果我們想要剩餘的碰撞機率 $ 2^{-20} $ （不到百萬分之一）和 256 位生成的密鑰（ $ \mathtt{L}=32 $ ）， 那是 $ 2^{118} $ 用途。對於 128 位密鑰，這是“下降”到 $ 2^{54.5} $ 用途。
這種一階近似認為碰撞可能發生在 HKDF 的提取步驟中，每個生日界限的機率由下式控制 $ \mathtt{HashLen} $ ，或在擴展步驟中由 $ \mathtt{L} $ .
¹ 更準確地說，重要的是主密鑰的價值 $ \mathtt{IKM} $ 在用它的雜湊替換任何值之後 $ \mathtt{IKM} $ 長於塊大小 $ \mathtt{Hash} $ ，即 SHA-256 為 64 個字節。請注意，這種替換使得為兩個值生成 HKDF 的衝突變得微不足道 $ \mathtt{IKM} $ （一個在塊大小內，另一個更大）和相同 $ \mathtt{salt} $ 和 $ \mathtt{info} $ .
² 製造碰撞的意圖很重要，例如 $ \mathtt{L}=16 $ （即 128 位生成的密鑰）或更低，並且攻擊者可以編寫程式碼選擇 $ \mathtt{salt} $ 或者 $ \mathtt{info} $ ，那段程式碼知道 $ \mathtt{IKM} $ .