Hash

為什麼需要(幾乎)與蠻力一樣多的工作的程序被認為是對雜湊函式的“攻擊”?

  • September 11, 2017

在關於攻擊雜湊函式的文獻中,我經常遇到需要 $ 2^n $ 被描述為對雜湊函式的原像或碰撞“攻擊”的工作僅略多於 $ n $ 輸出位 $ ^1 $ .

我是否嚴重誤解了這裡的術語?

如果攻擊的結果是 $ n $ -位值然後蠻力採取 $ 2^n $ 嘗試;比這稍微好一點的東西怎麼能被認為是有意義的足以值得發表的“攻擊”呢?

它似乎使文章標題幾乎毫無用處;在知名出版物中發表的一篇題為“針對 ​​AES 的攻擊”的經過同行評議的文章,其後果可能從無關緊要到災難性的網際網路崩潰。

以下是Salsa20的 Wikipedia 頁面中的範例:

2007 年,Tsunoo 等人。宣布對 Salsa20 進行密碼分析,打破 20 輪中的 8 輪以恢復 256 位密鑰 $ 2^{255} $

  1. 或密鑰恢復對對稱密碼的“攻擊”僅略多於 $ n $ 一些密鑰,儘管我最近閱讀的主要是散列函式論文。

這只是一個術語問題,(在數學和相關學科中經常如此)可能與您對單詞的直覺解釋不符。

  • 攻擊是比“顯而易見的”蠻力算法執行得更好的任何算法。密碼原語被設計成不會比通用攻擊更好地承認任何攻擊,因此任何證明此目標未達到的證據都對理論家構成了突破(但可能不是*完全突破)。*對於更注重實際的人,它展示了可能有助於建構更有效算法的攻擊向量和技術。
  • 如果攻擊有效地破壞了系統的實際密鑰大小,它通常被稱為實際攻擊。(如果他們的攻擊表現如此出色,人們通常會自豪地將這個術語放在他們的論文標題中。)對於經過充分研究的原語,幸運的是這種情況並不經常發生。
  • 一些論文描述了針對密碼的減少輪數的變體的攻擊:這再次作為攻擊技術的展示,並且(就像任何其他類型的密碼分析一樣)是密碼設計的重要步驟,因為它提供了對輪數的估計密碼應該有。論文應該(並且通常會)清楚地指出他們正在攻擊非標準變體。

當然,不幸的是,有些人(如果不是很多)傾向於誇大他們的結果——你無能為力,但上述內容應該有助於過濾你感興趣的攻擊類型。

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