通過密碼散列函式保存熵
背景
首先，在稍微研究 MinEntropy 時，我遇到了 NIST 的一篇論文，“DRAFT SP 800-90B（第二稿）”，它建議將加密雜湊函式的底層塊的熵“兩倍”用作輸入，以便具有具有完全飽和熵容量的輸出雜湊。這對我來說似乎沒有必要，因為在我的業餘研究中，我之前已經了解到，人們可以假設——儘管顯然不能假設，因為據我所知，滿射還沒有被證明——一個密碼散列函式應該在輸出中保留輸入的每個熵位，直到輸出的位長度。
從這裡的類似問題，我想我應該問一個新問題而不是回复，我聽說它聲稱使用散列函式 - 讓我們說 SHA256 為了對話 - 散列輸入字元串具有 N < 257 位的熵，可能會產生 - 特別是由於碰撞 - 輸出的熵少於 N 位。
問題
我理解，如果你有一組 2^64 個元素，並認為這個集合構成 64 位熵，因為它本質上是一個具有這麼多狀態的狀態機，如果你要將這個域子集的每個元素散列到它對應的 codomain 子集，由於衝突，您最終可能在 codomain 子集中得到少於 2^64 個元素，這是肯定的，因為鴿巢原理 - 密碼散列函式是非內射的。
但是，如果您有一個任意的單個輸入，而不是一組輸入，例如，一個包含 64 位熵的字元串，它似乎與一組 2^64 個元素不同。顯然，2 ^ 64 個元素可能並非每個都映射到單獨的共域元素，在這種情況下，我看到了碰撞如何減少熵，特別是當輸入集大小向 2 ^ 256 增加時，在 SHA256 的情況下。但是，對於從具有 64 或 256 位熵的單個輸入產生的輸出的熵，這真正說明了什麼？
我可以想像我應該從試圖破解 256 位對稱算法的密鑰或密碼的攻擊者的角度來思考。因此，使用者有一個密碼，例如 256 位熵，並使用 SHA256 對其進行雜湊處理以使其大小合適（或出於任何原因）。我的想法是這將導致輸出雜湊中的熵為 256 位，但似乎很多人認為，由於具有這樣的熵：output_bit_count 比率（此處為 1，但即使接近 1），輸出雜湊也會有由於碰撞，其中的熵少於輸入到函式中的熵。
好吧，當然嘗試猜測使用者的密碼 - 直接 - 將需要 2^256 次操作才能確定成功。因此將嘗試直接猜測雜湊輸出，但它會因為是未知的 256 位字元串而忽略輸入熵。嘗試通過正確猜測密碼來間接猜測雜湊輸出將需要 2^256 次操作，就像猜測密碼一樣，除了有效密碼以外的其他猜測可能會因為衝突而產生相同的輸出雜湊，並且目標是在猜測雜湊，而不是輸入本身。
因此，如果我知道有 2^256 個潛在密碼（並且不夠聰明，無法直接攻擊密鑰），我可能不需要通過它們找到正確的密碼，而只需找到與它。
但這真的是碰撞 - 缺乏內射 - 導致熵損失，還是因為從 2^256 域子集到 2^256 共域，缺乏內射性意味著缺乏主觀性？因為兩個輸入到一個輸出，所以它不是單射的。但是因為（子集）域與共域的元素計數相同，所以缺乏 1:1 保證了缺乏滿射性。
我已經知道，非滿射的加密雜湊函式無法將熵保持在比特長度以內。它不能產生比它自己的狀態空間更多的熵的輸出，所以如果它不能覆蓋codomain，它只能將熵保留在log2（狀態空間）中，它可以覆蓋比特，而不是完整的輸出比特長度，只有在狀態空間是 2^bit_length_out 是滿射的情況下才成立。
我認為重要的是要知道它是否真的是減少熵的碰撞，或者當限制在域的一個子集時缺乏滿射性。因為域比餘域大得多，所以實際上有很多方法可以在域中表示 256 位熵，但在餘域中只有 2^256 種方式。
如果確實是因為缺乏內射性，那麼在 2^256 元素（子集）域/（完整）共域關係中缺乏 1:1 的事實意味著什麼，如果有的話，意味著缺乏也是滿射的嗎？碰撞導致的輸出熵損失是否等於或什至等於缺乏滿射性導致的熵損失？
我沒有回答所有問題，但讓我們舉一個小例子。認為 $ X $ 均勻分佈在 $ {1,2,3} $ ， 以便 $ \Pr[X = x] = 1/3 $ 對於任何 $ x \in {1,2,3} $ . 如果我們定義
$$ \begin{equation*} f(1) = 2, \qquad f(2) = 3, \qquad f(3) = 2, \end{equation*} $$
那麼我們有
$$ \begin{align*} \Pr[f(X) = 1] &= 0, \ \Pr[f(X) = 2] &= \Pr[X = 1] + \Pr[X = 3] = 2/3, \ \Pr[f(X) = 3] &= \Pr[X = 2] = 1/3. \end{align*} $$
最小熵 $ X $ 是 $ -\log \max_{x\in{1,2,3}} \Pr[X = x] = \log 3 $ ，而最小熵 $ f(X) $ 是 $ -\log \max_{y\in{1,2,3}} \Pr[f(X) = y] = \log 1.5 $ .
一般來說，熵 $ f(X) $ 與熵有關 $ X $ 經過 $ H[f(X)] \leq H[X] $ , 等式成立當且僅當 $ f $ 是內射的。當域和共域 $ f $ 是一樣的，那麼它就這樣發生了 $ f $ 是單射的當且僅當 $ f $ 是主觀的。
那麼SHA-256呢？好吧，任何發行版都支持少於 $ 2^{256} $ 不同的值不能有 256 位的熵。如果我們將 SHA-256 建模為均勻隨機函式 $ F $ ，那麼在任何一組輸入上，都有一個非零機率 $ F $ 不是 256 位字元串的外延；上 $ 2^{256 + k} $ 不同的輸入，不同輸出的預期分數約為 $ 1 - e^{-2^k} $ ，它迅速接近 $ 1 $ .
這並不能完全回答熵 $ \operatorname{SHA-256}(X) $ 是，但它給出了一個可通過以下方式獲得的熵的粗略代理 $ \operatorname{SHA-256}(X) $ 就熵而言 $ X $ ，這就是為什麼 NIST 建議為 ‘full entropy’ 選擇雙倍大小的輸入。
注意：這只是關於注入性和碰撞。“Surjectivity”是一條紅鯡魚。你可以採取任何投機 $ f\colon A \to B $ 並通過人為地擴大其共域並稱其為 $ f’\colon A \to (B \cup C) $ ，但熵 $ f(X) $ 和 $ f’(X) $ 即使是完全一樣的 $ f $ 從技術上講是一個投影並且 $ f’ $ 不是。同樣，您可以採用 SHA-256，並附加一個 256 個零位的字元串： $ F(x) := \operatorname{SHA-256}(x) \mathbin| 0^{256} $ ; 然後 $ F(X) $ 具有完全相同的熵 $ \operatorname{SHA-256}(X) $ ， 雖然 $ F(X) $ 是一個 512 位的字元串，並且 $ \operatorname{SHA-256}(X) $ 是一個 256 位的字元串。