當一個攻擊被發現時，你最想知道的第一件事，是它在理論上有多有效率、在實務上又有多可行（如果可行的話）。反過來，給定一個號稱安全的密碼，你會想知道它能承受多大的計算量。

用位元衡量安全性#

談計算安全性時，我們說一個密碼是 t-安全的，若一次成功的攻擊至少需要 t 次運算。這樣就避開了不直觀的 (t, ε) 記法——我們假設成功機率 ε 接近 1，也就是實務上真正在意的情況。

於是安全性以位元表示：「n 位元安全性」意味著需要大約 2^n 次運算才能危及某個特定的安全概念。

若你大致知道破解一個密碼要多少次運算，就能取二進位對數得出它的安全等級：若需要 1,000,000 次運算，安全等級就是 log₂(1000000)，約 20 位元（1,000,000 ≈ 2^20）。

金鑰長度只是上界#

回想一把 n 位元的金鑰最多提供 n 位元的安全性，因為試遍全部 2^n 把可能金鑰的暴力攻擊必定成功。

但金鑰長度不總是等於安全等級——它只給出一個上界，也就是最高可能的安全等級。

安全等級可能小於金鑰長度，原因有二：

  • 有攻擊以少於預期的運算次數破解了該密碼——例如某種方法不必試遍 2^n 把金鑰，只需試其中一個子集就能還原金鑰。
  • 該密碼的安全等級刻意不同於其金鑰長度，多數公鑰演算法都是如此。例如採用 2048 位元秘密金鑰的 RSA 演算法，提供的安全性不到 100 位元。

位元安全性的侷限#

位元安全性在比較密碼的安全等級時很有用，但它沒有提供足夠的資訊來說明攻擊的實際成本。

它有時是過於簡化的抽象，因為它只假設一個 n 位元安全的密碼需要 2^n 次運算才能破解，卻不論這些運算究竟是什麼。兩個位元安全等級相同的密碼，一旦把攻擊者的實際成本納入考量，真實世界的安全等級可能天差地遠。

假設有兩個密碼，各有 128 位元金鑰與 128 位元安全性，都必須被求值 2^128 次才能破解，但第二個密碼比第一個慢 100 倍。

求值第二個密碼 2^128 次所花的時間，等同於求值第一個密碼 100 × 2^128 ≈ 2^134.64 次。若以第一個（快的）密碼為計數單位，破解慢的那個要 2^134.64 次運算；若以第二個（慢的）為單位，就只要 2^128 次。

那麼第二個密碼比第一個強嗎？原則上是的——但我們很少在常用密碼之間看到這種百倍的效能差距。

「運算」定義的不一致，在比較攻擊效率時會製造更多困難。有些攻擊宣稱降低了某密碼的安全性，因為它們執行 2^120 次某種運算而非 2^128 次密碼求值——但分析中往往漏掉了每種運算的速度。2^120 次運算的攻擊不一定比 2^128 次的暴力攻擊更快。

儘管如此，只要「運算」被合理地定義（意即速度大約等同於一次密碼求值），位元安全性仍是有用的概念。畢竟在現實中，判斷一個安全等級是否足夠，只需要看數量級。

攻擊的完整成本#

位元安全性藉由估計最快攻擊所需運算次數的數量級，表達了攻擊成本。但還有其他因素會影響攻擊成本，在估計實際安全等級時必須納入考量。主要有四項。

平行性#

第一個因素是計算的平行性（parallelism）。

考慮兩個各需 2^56 次運算的攻擊，差別在於第二個可平行化而第一個不行：

  • 第一個攻擊執行 2^56 次循序相依的運算，例如 x(i+1) = f(i)(x(i))。
  • 第二個攻擊執行 2^56 次獨立的運算，例如 x(i) = f(i)(x)，可以平行執行。

平行處理可以比循序處理快上數個數量級。例如若你有 2^16 = 65536 個處理器可用，就能把可平行攻擊的工作量拆成 2^16 個獨立任務，每個執行 2^56 / 2^16 = 2^40 次運算。

第一個攻擊卻無法從多核心中受益，因為每次運算都依賴前一次運算的結果。因此平行攻擊會比循序攻擊快 65536 倍，儘管兩者執行的運算次數相同。

當有 N 個核心可用時攻擊速度就快 N 倍的演算法，稱為易平行（embarrassingly parallel），我們說它們的執行時間相對於運算核心數呈線性變化。

記憶體#

第二個因素是記憶體。密碼分析攻擊應該就其時間與空間的使用來評估：

  • 隨時間執行了多少次運算？
  • 消耗多少記憶體或空間？
  • 如何使用它所消耗的空間？
  • 可用記憶體的速度為何？

遺憾的是，位元安全性只關心執行攻擊所需的時間。

關於空間的使用方式，重要的考量包括：攻擊過程需要多少次記憶體查找、記憶體存取的速度（讀與寫可能不同）、被存取資料的大小、存取樣式（連續或隨機的記憶體位址），以及資料在記憶體中如何組織。

在今天的通用 CPU 上：

  • 從暫存器讀取約需 1 個週期。
  • 從 CPU 快取讀取約需 20 個週期（L3 快取）。
  • 從 DRAM 讀取通常至少需 100 個週期。

100 倍的差距，可能就是一天與三個月的差別。

預先計算#

預先計算（precomputation）指那些只需執行一次、之後每次攻擊都能重複使用的運算，有時稱為攻擊的離線階段（offline stage）。

以時間—記憶體權衡攻擊為例：攻擊者先執行一次龐大的計算，產生大型查找表並儲存起來，之後重複使用來執行實際攻擊。

一個針對 2G 行動加密的攻擊，花了兩個月建立 2TB 的表；有了這些表，破解 2G 加密並還原一把秘密工作階段金鑰只需要幾秒鐘。

目標數量#

最後是攻擊目標的數量。目標越多，攻擊面越大，攻擊者能學到的關於目標金鑰的資訊也越多。

以暴力金鑰搜尋為例：

  • 若你只針對單一的 n 位元金鑰，要確定找到正確金鑰需要 2^n 次嘗試。
  • 若你針對 M 把 n 位元金鑰，且對同一段 P 你握有 M 段相異的密文（C = E(K, P)，對應你想要的 M 把金鑰），要找出每一把金鑰仍需各 2^n 次嘗試。
  • 但若你只在乎至少破解其中一把，平均只需 2^n / M 次嘗試就會成功。

例如要從 2^16 = 65536 把目標金鑰中破解出一把 128 位元金鑰，平均只需 2^(128−16) = 2^112 次密碼求值。

也就是說：攻擊的成本隨目標數量增加而下降（速度則上升）。

選擇與評估安全等級#

選擇安全等級通常是在 128 位元與 256 位元之間做取捨，因為多數標準密碼演算法與實作都提供這兩種等級之一。128 位元以下你會找到 64 或 80 位元安全性的方案，但這些一般對真實世界的使用來說不夠安全。

128 位元有多大#

128 位元安全性意味著你需要執行約 2^128 次運算才能破解該密碼系統。

給你一點尺度感：宇宙的年齡約為 2^88 奈秒（一秒有十億奈秒）。

由於以今日技術測試一把金鑰不會少於一奈秒，若測一把金鑰恰好花一奈秒，一次成功的攻擊需要數倍於宇宙年齡的時間——精確地說是 2^40 倍。

平行化與多目標能否大幅縮短時間？ 並不盡然。假設你想破解一百萬個目標中的任何一個，而且有一百萬個平行核心可用，搜尋時間從 2^128 降到：

(2^128 / 2^20) / 2^20 = 2^88

這仍然相當於一整個宇宙的壽命。

技術演進的影響#

評估安全等級時另一個要考慮的是技術的演進。摩爾定律（Moore’s law）主張運算效率大約每兩年翻倍。我們可以把這想成每兩年損失一位元的安全性。

若今天 1000 美元的預算能讓你在一小時內破解一把 40 位元金鑰，摩爾定律說兩年後同樣的 1000 美元能在一小時內破解 41 位元金鑰（這裡是簡化說法）。

由此外推：80 年後我們會比今天少 40 位元的安全性。換句話說，80 年後執行 2^128 次運算的成本，可能等同於今天執行 2^88 次運算。再把前述的平行化與多目標算進去，就降到 2^48 奈秒的計算量，約三天。

但這個外推極不精確，因為摩爾定律不會、也不可能延伸那麼久。不過你抓到重點了：今天看似不可行的事，一個世紀後可能相當實際。

何時可以用低於 128 位元#

有時低於 128 位元的安全等級是合理的——例如你只需要短時間的安全性，而且實作更高安全等級會對系統的成本或可用性造成負面影響。

真實世界的例子是付費電視系統，其加密金鑰只有 48 或 64 位元。這聽起來低得離譜，但這是足夠的安全等級，因為金鑰每 5 或 10 秒就更新一次。

長期安全該選什麼#

要確保長期安全，你應該選擇 256 位元安全性或略低。

即使在最壞情況下——量子電腦成真（見第 14 章）——一個 256 位元安全的方案在可預見的未來也不太可能被破解。

超過 256 位元的安全性在實務上並無必要，除非是拿來當行銷手段。

NIST 密碼學家 John Kelsey 說過：「80 位元與 128 位元金鑰搜尋之間的差別，就像去火星的任務與去半人馬座 α 星的任務之間的差別。就我所見，192 位元與 256 位元金鑰在實際暴力攻擊上並無有意義的差異；不可能就是不可能。」

Backward 定義不可能 達成安全性 Forward