Hmac

生日攻擊對 HMAC 的影響是什麼?

  • July 23, 2015

大約收集後 $ 2^{n/2} $ 可以觀察到消息標籤對發生衝突。因此,兩條不同的消息(m1m2)將具有相同的標籤。

該論文指出:

然後,對於任何字元串x, ( m1 , x ) 和 ( m2 , x ) 具有相同的標籤(在 HMAC 的情況下具有很高的機率,在 CMAC 的情況下具有確定性)。然後攻擊者可以請求(m1x)的標籤,從而也獲得標籤if(m2x)。

這是否意味著可以在m1上附加任何字元串****x並且它的標籤將與附加到m2的****x的標籤相同?

如果我的假設是真的,這是否可以被視為長度擴展攻擊?

這就像在說 $ H(C_1|m_1|x|C_2) = H(C_1|m_2|x|C_2) $ 如果 $ H(C_1|m_1|C_2) = H(C_1|m_2|C_2) $ 為 HMAC。

這可能是正確的**,如果** $ H $ 是基於Merkle-Damgård 構造的雜湊函式(例如 SHA-1 和 SHA-2),如果 $ m_1 $ 和 $ m_2 $ 結束於塊邊界。

$ H(C_1|m_1|C_2) = H(C_1|m_2|C_2) $ 表示散列後的狀態 $ C_1 $ 和 $ m_1 $ 與散列相同 $ C_1 $ 和 $ m_2 $ . 因此,將任何數據添加到任何一個都將導致相同的雜湊值。

然而如果 $ m $ 不會在塊邊界上結束,然後更改後面的數據 $ m $ 在區塊被散列後仍會改變狀態;結果極不可能是相同的 $ m_1 $ 和 $ m_2 $ (如果 $ m_1 $ 和 $ m_2 $ 當然最後一塊不同)。如果 $ m_1 $ 和 $ m_2 $ 可以自由選擇,就可以避免這種情況。


CMAC(和 CBC-MAC)的情況或多或少是相同的。然而,CBC 是明確的,而 Merkle-Damgård 不是。所以這對於 CMAC 來說似乎確實更正確。


如果我的假設是真的,這是否可以被視為長度擴展攻擊?

您可以將其稱為長度擴展攻擊,它至少與一種非常相似。隨著附加數據的出現,它更像是一種插入攻擊,但原理是一樣的。

請注意,這僅適用於插入 $ x $ ,而不是其餘的攻擊。

這是否意味著可以在 m1 上附加任何字元串 x 並且它的標籤將與附加到 m2 的 x 的標籤相同?

是的。如果使用 HMAC,那麼 (m1, x) 上的標籤很有可能與 (m2, x) 上的標籤相同。使用 CMAC,攻擊以機率 1 起作用。

如果我的假設是真的,這是否可以被視為長度擴展攻擊?

我不會稱其為長度擴展攻擊。在討論以下形式的 MAC 時,通常會看到長度擴展攻擊 $ H(k||m) $ . 由於某些散列函式的執行方式,計算這種形式的 MAC 可以讓攻擊者在消息上獲得有效的 MAC $ m||m’ $ .

所以這裡有一些長度擴展和這種生日式攻擊之間的區別:

  1. 長度擴展攻擊只需要一個來自壞 MAC 函式的查詢。生日式的攻擊需要很多。因此,即使對於一個安全的散列函式,傳統的長度擴展也可以工作,但這種攻擊對於一個好的散列函式是不可行的。
  2. 長度擴展適用於機率 1;這種攻擊對 HMAC 的“高機率”有效,但小於 1。
  3. 在初始查詢之後,長度擴展攻擊不需要額外的查詢。在最初的碰撞之後,這種攻擊需要一個額外的查詢。

引用自:https://crypto.stackexchange.com/questions/27105