什麼是生日攻擊

利用「23人中有兩人同一天生日的機率超過50%」的生日悖論來尋找碰撞的攻擊。隨機產生n位元的值時,約產生 2^(n/2) 個後,出現相同值之配對的機率就變得不可忽視。因此,n位元雜湊函數抵抗碰撞的強度約為 n/2 位元。區塊長度64位元的區塊加密,以同一把金鑰加密約 2^32 個區塊(32 GiB)後,就會開始出現相同的密文區塊,這也是使用區塊長度128位元之AES的原因之一。隨機選擇nonce時的使用次數上限,也是根據相同的想法。

日文名稱: 誕生日攻撃

「生日攻擊」出現在2領域的2道練習題中(密碼學基礎與應用, 資訊安全基礎等)。

這個名詞所屬的領域: 密碼學基礎與應用

練習生日攻擊的題目

設 1 GiB = 2³⁰ 位元組、1 EiB = 2⁶⁰ 位元組。以CBC模式使用區塊長度64位元的區塊加密(3DES等),用同一把金鑰加密大量資料。把密文區塊視為隨機的64位元值時,根據生日悖論,出現相同密文區塊之配對的機率變得不可忽視的資料量參考值為下列何者?

  1. A約4 GiB
  2. B約32 GiB
  3. C約128 EiB
查看答案與解析

正確答案:B. 約32 GiB

64位元區塊的值有 2⁶⁴ 種,根據生日悖論,加密約 2^(64/2) = 2³² 個區塊後,出現相同值之配對的機率就變得不可忽視(2³² 個時約39%)。1個區塊為8位元組,因此資料量為 2³² × 8 = 2³⁵ 位元組 = 32 GiB。在CBC模式中,若密文區塊一致,就會得知對應的兩個明文區塊的XOR,2016年公開的Sweet32攻擊顯示,可以從以3DES保護的長時間HTTPS通訊中取出Cookie。區塊長度為128位元的AES,參考值則擴大到 2⁶⁴ 個區塊。

解析中的「生日攻擊」

出現「生日攻擊」的題目(2題)

  1. 設 1 GiB = 2³⁰ 位元組、1 EiB = 2⁶⁰ 位元組。以CBC模式使用區塊長度64位元的區塊加密(3DES等),用同一把金鑰加密大量資料。把密文區塊視為隨機的64位元值時,根據生日悖論,出現相同密文區塊之配對的機率變得不可忽視的資料量參考值為下列何者?
  2. 對於輸出為256位元的理想雜湊函數,以暴力法攻擊時所需計算次數的大致數量,在「找出能產生指定雜湊值的輸入(原像攻擊)」與「找出任意兩個雜湊值相同的不同輸入(碰撞攻擊)」兩種情況下,正確的組合是哪一項?

相關名詞

區塊加密操作模式 Cookie AES(進階加密標準) 雜湊函數 信封加密 前向保密 迪菲-赫爾曼金鑰交換 密碼敏捷性 硬體安全模組(HSM) 憑證機構

前往名詞解釋列表