碰撞阻力是否意味著（或不）第二原像阻力？
我看到了矛盾的結果。有時雜湊函式是抗碰撞的，但不一定是抗第二原像的。我在 Bart Preneel 的論文中看到過這種事情：
（參見“其他域擴展器”一章）。
這怎麼可能？
我們有定理說，如果一個雜湊函式是抗碰撞的，那麼它也是第二個抗原像的：
使用函式的定義 $ F $ 是
- 抗碰撞時$$ computationally bounded $$對手不能$$ with sizable odds $$展示任何 $ (a,b) $ 和 $ a\ne b $ 和 $ F(a)=F(b) $ ;
- 第一原像抗性時，給定 $ f $ 確定為 $ F(a) $ 對於一個未知的隨機 $ a $ ， 一種$$ computationally bounded $$對手不能$$ with sizable odds $$展示任何 $ b $ 和 $ F(b)=f $ ;
- 給定隨機數時，抗第二原像 $ a $ ， 一種$$ computationally bounded $$對手不能$$ with sizable odds $$展示任何 $ b $ 和 $ a\ne b $ 和 $ F(a)=F(b) $
是的，抗碰撞性意味著抗第二原像性。對立證明：假設第二原像抗性不成立。反複選擇一個隨機 $ a $ , 執行攻擊 $ b $ 和 $ a\ne b $ 和 $ F(a)=F(b) $ , 直到成功。根據我們的假設，這需要可行的工作量。一旦展出，那對 $ (a,b) $ 證明抗碰撞性質不成立。
然而，正如 CodesinChaos 在他的評論中指出的那樣，對於將發現碰撞或（分別）原像的難度量化為大致 $ 2^{n/2} $ 或（分別） $ 2^n $ 評估，其中 $ n $ is 是輸出中的位數。
反例證明：對於偶數 $ n $ , 假設一個雜湊函式 $ H:{0,1}^\to{0,1}^n $ 它表現為一個隨機函式。現在構造 $ F:{0,1}^\to{0,1}^n $ 作為
$$ F(x)=\begin{cases}x||x&\text{if }x\text{ has }n/2\text{ bits}\H(x)&\text{otherwise}\end{cases} $$ $ F $ 具有抗碰撞特性（當 $ a $ 和 $ b $ 都是 $ n/2 $ 位， $ a\ne b\implies F(a)\ne F(b) $ ; 當兩者都沒有 $ a $ 也不 $ b $ 是 $ n/2 $ 位，碰撞阻力是 $ H $ ; 當一個 $ a $ 或者 $ b $ 是 $ n/2 $ 位，另一個必須有一個具有兩個相等一半的雜湊，並且它需要大約 $ 2^{n/2} $ 散列來展示這樣的輸入）。然而，下面的算法打破了第二原像電阻屬性 $ F $ 成本相當 $ 2^{n/2} $ 散列，遠低於要求：如果隨機 $ a $ 大小不合適 $ n/2 $ , 計算 $ H(a) $ ，並且如果它的兩半相等（預計發生在 $ 2^{n/2} $ 雜湊），讓 $ b $ 是那個位串 $ n/2 $ 位；它認為 $ a\ne b $ 和 $ F(a)=F(b) $ .
總而言之：函式的第二原像抗性總是至少與其抗碰撞性一樣強；但它不能強多少，而不是二次強，這是理論上的理想。因此，根據定義，抗碰撞意味著第二原像抗性……與否！當我們保持相同的安全級別（對手的努力和成功機率）來評估這兩個屬性時，情況就是如此。當我們期望安全級別與屬性和函式的輸出大小一致時，這是錯誤的。
添加以下評論：該問題連結到 Elena Andreeva、Bart Mennink 和 Bart Preneel Security Properties of Domain Extenders for Cryptographic Hash Functions 的論文。那篇高度技術性的論文考慮了各種提議的擴展方法，以在比核心塊接受的大得多的輸入上迭代雜湊函式的核心建構塊；並且如果該核心的安全屬性在擴展結構中得到保留，則達到可比較的水平（攻擊工作和成功機率）。
正如任何一篇好的論文一樣，該論文給出了具體的定義，對於一些既定的定義，請參考它的參考資料
$$ 15 $$: P. Rogaway & T. Shrimpton Cryptographic Hash-Function Basics: Definitions, Implications, and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision Resistance。所有這些定量定義與經典結果完全一致，即對於任何給定級別（攻擊工作和成功機率），抗碰撞性意味著第二原像抗性。 該論文表明，一些擴展方法明顯（大部分）保持了抗碰撞水平，但沒有明顯（大部分）保持第二原像抗性水平。這完全符合上述規則。
例如，從假設抗碰撞的核心塊開始 $ \mathcal O(2^{n/2}) $ 努力和抗第二原像 $ \mathcal O(2^n) $ 努力，一些擴展器可能會構造一個抗衝突的雜湊 $ \mathcal O(2^{n/2}) $ 努力和抗第二原像 $ \mathcal O(2^{2\cdot n/3}) $ 努力。不完美的擴展器保留了抗碰撞的水平，但沒有保留第二原像抗性的水平。然而，對於使用該擴展器建構的雜湊，對某個努力水平的抗碰撞性仍然意味著對該努力水平的第二原像抗性。