SHA512的有限纖維

讓 $ {0,1}^* $ 是有限的集合 $ {0,1} $ -字元串。那麼SHA512可以看成一張圖 $ s: {0,1}^*\to {0,1}^{512} $ .

皮江洞原理意味著存在 $ y\in {0,1}^{512} $ 這樣 $ s^{-1}({y}) $ 是無限的。

在那兒 $ y\in{0,1}^{512} $ 和 $ \emptyset \neq s^{-1}({y}) $ 和 $ s^{-1}({y}) $ 是有限的？

在那兒 $ y\in{0,1}^{512} $ 和 $ \emptyset \neq s^{-1}({y}) $ 和 $ s^{-1}({y}) $ 是有限的？

對於實際定義的 SHA-512，很簡單，因為輸入大小限制為 $ 2^{128}-1 $ 少量。這使得 $ s^{-1}({y}) $ 對任何人都是正確的 $ y\in{0,1}^{512} $ . 和 $ y $ 空位串的雜湊滿足條件 $ \emptyset \neq s^{-1}({y}) $ . 下面我們假設這個 $ 2^{128}-1 $ 位限制被刪除。

我敢打賭，這個命題現在是錯誤的，通過以下論點（不是證明）。

1. 對於一些最多 895 位的消息（需要單輪的最大塊對齊消息），SHA-512 達到每個 512 位雜湊似乎是合理的。論據：在理想的分組密碼模型下，在 SHA-512 輪的核心分組密碼，此類消息的每個散列都是隨機且獨立的 $ {0,1}^{512} $ . 受到優惠券收集器的約束，我們期望在粗略之後得到所有的值。 $ 2^{520.5} $ 繪製，並且尾部估計基本上排除了（機率 $ <2^{-(2^{384})} $ ）我們不會得到他們所有之後 $ 2^{896}-1 $ 嘗試。如果我們的模型非常糟糕，那實際上只會失敗。
2. 對於最多 1919 位的消息（需要兩輪的最大塊對齊消息），SHA-512 達到每個 512 位散列更加合理，因為在兩輪中，第一輪中可能輸入的數量達到 $ 2^{1024} $ ，使其（根據論點 1）可能接近 $ 2^{512} $ 值可以達到第二輪的512位狀態輸入；我們得到 $ 2^{896}-1 $ 消息輸入塊與第一輪一樣。因此，我們甚至超越了優惠券收集器的界限，更重要的是，由於我們還有 512 個不同的輸入位，因此我們的模型似乎更不可能那麼糟糕。
3. 第二輪的這個推理可以重複任何更多的輪數，從而得出結論，每個值 $ {0,1}^{512} $ 最多可能達到一輪。
4. 更令人驚訝的是，當我們讓消息長度取模時 $ 2^{128} $ 取所有可能的值，任何 $ 2^{512} $ 沒有消息達到值 $ 2^{128} $ 至 $ 2^{129-1} $ 位：我們有近乎額外的 128 位輸入，可以變化。
5. 然後由於允許消息長度無限增長，我們得到那個可能性，任何 $ y $ 有無限 $ s^{-1}({y}) $ .
6. 這 $ \emptyset \neq s^{-1}({y}) $ 該命題的一部分使其成立的可能性大大降低。假設在 之後（內部）再次達到SHA-512 的 512 位初始值 $ 2^{119} $ 至少一輪（比如說 $ w $ ） 的 $ 2^{(2^{129})} $ 不同的消息開始 $ 2^{129} $ 位，這可能是上述 3 的略微修改版本（我們對每個 $ 2^{119} $ 1024 位輸入塊 $ w $ ）。現在如果某個 $ y\in{0,1}^{512} $ 是 $ \operatorname{SHA-512}(x) $ ，那麼它也是 $ \operatorname{SHA-512}(w\mathbin|x) $ 更一般地說 $ \operatorname{SHA-512}(w\mathbin|\ldots\mathbin|w\mathbin|x) $ 從而建設性地反駁了這個命題。

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