前面我們看到如何回收利用雜湊函式與區塊密碼來建構 PRF——只要底層的雜湊或密碼安全，這些 PRF 就安全。HMAC 與 CMAC 這類方案只是把現成的雜湊函式或區塊密碼組合起來。

重複利用現成演算法很方便，但這是最有效率的做法嗎？

直覺上，PRF 與 MAC 要達到安全所需的工作量，應該比無金鑰雜湊函式更少：

  • 它們使用秘密金鑰，攻擊者因為沒有金鑰而無法把玩演算法。
  • 它們只向攻擊者暴露一個短標籤，不像區塊密碼會暴露與訊息等長的密文。

因此 PRF 與 MAC 不需要雜湊函式或區塊密碼的全部威力——這正是專用設計（dedicated design）的重點：純粹為了充當 PRF 與／或 MAC 而創造的演算法。

以下聚焦兩個廣泛使用的演算法：Poly1305 與 SipHash。

Poly1305#

Poly1305（唸作 poly-thirteen-o-five）於 2005 年由 Daniel J. Bernstein 設計（他也是第 5 章 Salsa20 串流密碼的創造者，以及啟發 BLAKE 與 BLAKE2 之 ChaCha 密碼的作者）。

Poly1305 針對現代 CPU 最佳化到極快。本書寫作時，Google 用它保護 HTTPS 連線，OpenSSH 等眾多應用也在用它。

與 Salsa20 不同，Poly1305 的設計建立在可追溯到 1970 年代的技術上——通用雜湊函式與 Wegman–Carter 建構。

通用雜湊函式#

Poly1305 內部使用一個通用雜湊函式（universal hash function），它比密碼學雜湊函式弱得多，但也快得多。例如通用雜湊不必具備碰撞抗性，這表示達成其安全目標所需的工作更少。

與 PRF 一樣，通用雜湊由秘密金鑰參數化：給定訊息 M 與金鑰 K，我們寫成 UH(K, M)。

通用雜湊函式只有一個安全要求：對任意兩則訊息 M₁ 與 M₂，在隨機金鑰 K 下 UH(K, M₁) = UH(K, M₂) 的機率必須可忽略。

與 PRF 不同，通用雜湊不需要是偽隨機的；只要不存在某一對 (M₁, M₂) 對許多不同金鑰都給出相同雜湊即可。

因為安全要求較容易滿足，所需運算更少，所以通用雜湊函式比 PRF 快上不少。

多項式求值雜湊#

Poly1305 所用的通用雜湊稱為多項式求值雜湊（polynomial-evaluation hash）。它由一個質數 p 參數化，接收由 [1, p] 範圍內兩個數 R 與 K 組成的金鑰，以及由 n 個區塊 (M₁, M₂, ..., Mn) 組成的訊息 M：

UH(R, K, M) = R + M₁K + M₂K² + M₃K³ + ... + MnKⁿ  mod p

其中 + 是正整數加法，Kⁱ 是 K 的 i 次方，mod p 是把結果對 p 取模（除以 p 的餘數；例如 12 mod 10 = 2）。

因為我們希望雜湊越快越好，基於通用雜湊的 MAC 常使用 128 位元訊息區塊，以及一個略大於 2^128 的質數 p（例如 2^128 + 51）。

128 位元的寬度能有效利用常見 CPU 的 32 與 64 位元算術單元，實作起來非常快。

弱點：只能安全鑑別一則訊息#

通用雜湊有一個弱點：它只能安全地鑑別一則訊息。攻擊者只要請求兩則訊息的標籤，就能攻破上述的多項式求值 MAC：

  1. 請求 M₁ = M₂ = ... = 0 這則訊息的標籤——其標籤就是 UH(R, K, 0) = R，直接洩漏了 R。
  2. 請求 M₁ = 1 且 M₂ = M₃ = ... = 0 這則訊息的標籤——其標籤是 T = R + K，把 T 減去 R 就得到 K。

現在攻擊者掌握了整把金鑰 (R, K)，能為任何訊息偽造 MAC。

所幸有辦法從「單訊息安全」走到「多訊息安全」。

Wegman–Carter MAC#

用通用雜湊函式鑑別多則訊息的訣竅，來自 IBM 研究者 Wegman 與 Carter 於 1981 年的論文〈New Hash Functions and Their Use in Authentication and Set Equality〉。

Wegman–Carter 建構用一個通用雜湊函式與一個 PRF、兩把金鑰 K₁ 與 K₂ 建構 MAC：

MAC(K₁, K₂, N, M) = UH(K₁, M) + PRF(K₂, N)

其中 N 是一個對每把金鑰 K₂ 都應唯一的 nonce，而 PRF 的輸出與通用雜湊函式 UH 的輸出等長。

把這兩個值相加，PRF 強大的偽隨機輸出遮蔽了 UH 的密碼學弱點。

你可以把它看成對通用雜湊結果的加密——PRF 扮演串流密碼的角色，讓「用同一把 K₁ 鑑別多則訊息」成為可能，從而防止了前述攻擊。

Wegman–Carter 建構在以下假設成立時給出安全的 MAC：

  • UH 是安全的通用雜湊。
  • PRF 是安全的 PRF。
  • 每個 nonce N 對每把金鑰 K₂ 只使用一次。
  • UH 與 PRF 的輸出值夠長，以確保足夠高的安全性。

Poly1305-AES#

Poly1305 最初以 Poly1305-AES 的形式提出，把 Poly1305 通用雜湊與 AES 區塊密碼結合。

Poly1305-AES 比基於 HMAC 的 MAC、甚至比 CMAC 都快得多——因為它只計算一個 AES 區塊，並透過一連串簡單的算術運算平行處理訊息。

給定 128 位元的 K₁、K₂、N 與訊息 M，Poly1305-AES 回傳：

Poly1305(K₁, M) + AES(K₂, N)  mod 2^128

mod 2^128 確保結果放得進 128 位元。

訊息如何被解析：M 被解析成一連串 128 位元區塊 (M₁, M₂, ..., Mn)，並在每個區塊的最高位元後附加第 129 個位元，讓所有區塊都是 129 位元長。（若最後一個區塊小於 16 位元組，會先補一個 1 位元與若干 0 位元，再加上最後那第 129 個位元。）

接著 Poly1305 求值該多項式：

Poly1305(K₁, M) = M₁K₁ⁿ + M₂K₁ⁿ⁻¹ + ... + MnK₁  mod (2^130 − 5)

這個式子的結果是一個至多 129 位元長的整數。與 128 位元的 AES(K₂, N) 相加後，結果對 2^128 取模，產生 128 位元的 MAC。

AES 不是 PRF，而是偽隨機置換（PRP）。但這在此無關緊要，因為 Wegman–Carter 建構對 PRP 與 PRF 都適用——若只看函式的輸出值，很難判定它是 PRF 還是 PRP。

Poly1305-AES 的安全性分析顯示：只要 AES 是安全的區塊密碼（當然，也要一切都正確實作），Poly1305-AES 就是 128 位元安全的。

Poly1305 通用雜湊也能與 AES 以外的演算法結合。例如它曾與串流密碼 ChaCha 一起使用（見 RFC 7539，〈ChaCha20 and Poly1305 for IETF Protocols〉）。毫無疑問，只要需要快速的 MAC，Poly1305 就會繼續被使用。

SipHash#

Poly1305 雖然又快又安全，但有幾個缺點：

  • 多項式求值難以有效率地實作，對不熟悉相關數學概念的人尤其如此。
  • 單獨使用時只對一則訊息安全，除非搭配 Wegman–Carter 建構——但那就需要 nonce，而 nonce 一旦重複，演算法就不安全。
  • 為長訊息最佳化，若你只處理小訊息（比方說少於 128 位元組），它就殺雞用牛刀。

這些情況下，SipHash 才是解答。

本書作者於 2012 年與 Dan Bernstein 共同設計 SipHash，最初是為了解決一個非密碼學問題：對雜湊表的阻斷服務攻擊。

雜湊表是程式語言中用來有效率地儲存元素的資料結構。在 SipHash 出現之前，雜湊表依賴的是碰撞容易被找到的非密碼學帶金鑰雜湊函式，因此很容易透過拖慢遠端系統來對使用雜湊表的系統發動阻斷服務攻擊。

我們判定 PRF 能解決這個問題，於是著手設計了適用於雜湊表的 PRF——SipHash。由於雜湊表處理的多半是短輸入，SipHash 為短訊息最佳化。但它不只能用於雜湊表：它是一個完整的 PRF 與 MAC，在多數輸入都很短的場合大放異彩。

運作方式#

SipHash 使用一個讓它比基本海綿函式更安全的技巧：訊息區塊不是只在置換之前 XOR 一次，而是在置換前後都 XOR。

流程：

  1. SipHash 的 128 位元金鑰被視為兩個 64 位元字 K₁ 與 K₂，與一個視為四個 64 位元字的 256 位元固定初始狀態做 XOR。
  2. 接著丟棄金鑰，計算 SipHash 歸結為迭代一個稱為 SipRound 的核心函式，並 XOR 訊息片段以修改這個四字的內部狀態。
  3. 最後把四個狀態字 XOR 在一起，回傳一個 64 位元的標籤。

圖 7-5：SipHash-2-4 處理一則 15 位元組的訊息

SipRound#

SipRound 用一堆 XOR 加上加法與字旋轉來確保函式的安全性。它由上而下對四個 64 位元字 (a, b, c, d) 的狀態執行下列運算——左右兩欄的運算彼此獨立，可以平行執行：

a += b            c += d
b <<<= 13         d <<<= 16
b ⊕= a            d ⊕= c
a <<<= 32
c += b            a += d
b <<<= 17         d <<<= 21
b ⊕= c            d ⊕= a
c <<<= 32

其中 a += b 是 a = a + b 的簡寫，b <<<= 13 是 b = b <<< 13（64 位元字 b 左旋 13 位元）的簡寫。

這些對 64 位元字的簡單運算，幾乎就是實作 SipHash 所需的全部——不過你不必自己實作。C、Go、Java、JavaScript、Python 等多數語言都有現成的實作。

版本命名#

我們把 SipHash 版本寫成 SipHash-x-y：在每次訊息區塊注入之間做 x 次 SipRound，最後再做 y 次。

輪數越多，運算越多，速度越慢，但安全性也越高。

預設版本是 SipHash-2-4（就簡稱 SipHash），至今抵抗住了密碼分析。不過你若想保守一些，可以選 SipHash-4-8——輪數加倍，速度也慢一倍。

Backward 從區塊密碼建構：CMAC 鑑別式加密 Forward