資訊安全基礎
對於輸出為256位元的理想雜湊函數，以暴力法攻擊時所需計算次數的大致數量，在「找出能產生指定雜湊值的輸入（原像攻擊）」與「找出任意兩個雜湊值相同的不同輸入（碰撞攻擊）」兩種情況下，正確的組合是哪一項？
- A原像攻擊約2^256次，碰撞攻擊約2^128次
- B原像攻擊約2^128次，碰撞攻擊約2^256次
- C原像攻擊與碰撞攻擊都約2^256次
查看答案與解析
正確答案：A. 原像攻擊約2^256次，碰撞攻擊約2^128次
輸出為n位元的理想雜湊函數共有 2^n 種雜湊值，每嘗試一個輸入，與指定雜湊值一致的機率為 1/2^n。因此原像攻擊約需 2^n 次計算，n = 256 時約為2^256次。另一方面，碰撞攻擊中任何兩個輸入一致都可以，因此嘗試k個輸入時，可比較的組合增加到約 k^2/2 種。當 k^2/2 接近 2^n，也就是k約為 2^(n/2) 時，就很可能找到碰撞，n = 256 時約為2^128次。這與「23人中有兩人同一天生日的機率超過50%」的生日悖論是同樣的想法，稱為生日攻擊。因此雜湊函數抵抗碰撞的強度估計為輸出位元數的一半，若要求相當於128位元的強度，就需要256位元的輸出。
- A. 正確。原像攻擊約需2^256次，碰撞攻擊因生日攻擊約需2^128次。
- B. 把兩者弄反了。任何兩個一致都可以的碰撞攻擊所需次數較少。
- C. 碰撞攻擊中，嘗試過的輸入之間任何一組一致都可以，因此約2^128次即可，遠少於原像攻擊。