綜觀密碼學史，MAC 與 PRF 很少從頭設計，而多半是從既有演算法（通常是雜湊函式或區塊密碼）建構而成。

一個看似顯而易見的做法，是把金鑰與訊息一起餵給一個（無金鑰的）雜湊函式——但這說起來容易，做起來難。

秘密前綴建構#

秘密前綴建構（secret-prefix construction）把金鑰接在訊息前面，回傳 Hash(K ‖ M)。

這個做法不總是錯的，但在兩種情況下會不安全。

問題一：長度延伸攻擊#

回想第 6 章：SHA-2 家族的雜湊函式允許攻擊者在拿到某訊息較短版本的雜湊時，算出部分未知訊息的雜湊。

形式上說，長度延伸攻擊讓攻擊者只憑 Hash(K ‖ M₁)（既不知道 M₁ 也不知道 K）就能算出 Hash(K ‖ M₁ ‖ M₂)。

這等於讓攻擊者免費偽造有效的 MAC 標籤——他們本來不該能只憑 M₁ 的 MAC 就猜出 M₁ ‖ M₂ 的 MAC。

因此秘密前綴建構搭配 SHA-256 或 SHA-512 使用時，作為 MAC 與 PRF 都是不安全的。

允許長度延伸攻擊是 Merkle–Damgård 的弱點，SHA-3 決選者沒有一個有這個問題——能挫敗長度延伸攻擊是 SHA-3 徵件的強制要求。

問題二：不同長度的金鑰#

秘密前綴建構在允許使用不同長度的金鑰時也不安全：

K = 123abc（24 位元），M = def00      → K ‖ M = 123abcdef00
K = 123a  （16 位元），M = bcdef000   → K ‖ M = 123abcdef00

兩把不同的金鑰，Hash(K ‖ M) 的結果完全相同。

這個問題與底層雜湊無關，可以藉由「把金鑰長度與金鑰、訊息一起雜湊」來修正——例如把金鑰的位元長度編碼成 16 位元整數 L，再雜湊 Hash(L ‖ K ‖ M)。

但你不該需要自己做這件事。

BLAKE2 與 SHA-3 這類現代雜湊函式內建了帶金鑰模式（keyed mode），避開了這些陷阱，直接產出一個安全的 PRF，因而也是一個安全的 MAC。

秘密後綴建構#

與其把金鑰雜湊在訊息之前，我們也可以放在之後。這正是秘密後綴建構（secret-suffix construction）的做法：Hash(M ‖ K)。

好處：擋住長度延伸#

把金鑰放在最後造成了相當大的差異。對秘密前綴 MAC 有效的長度延伸攻擊，對秘密後綴無效：

把長度延伸套用到秘密後綴 MAC，你會從 Hash(M₁ ‖ K) 得到 Hash(M₁ ‖ K ‖ M₂)——但那不是有效的攻擊，因為 Hash(M₁ ‖ K ‖ M₂) 不是一個有效的秘密後綴 MAC；金鑰必須在最後。

但對另一類攻擊更弱#

假設你有雜湊的碰撞 Hash(M₁) = Hash(M₂)，其中 M₁ 與 M₂ 是兩則相異訊息（大小可能不同）。

對 SHA-256 這類雜湊函式而言，這意味著 Hash(M₁ ‖ K) 與 Hash(M₂ ‖ K) 也會相等——因為在內部，K 是基於先前雜湊過的資料（也就是相等的 Hash(M₁) 與 Hash(M₂)）被處理的。

因此無論 K 的值是什麼，把 K 雜湊在 M₁ 之後或 M₂ 之後，都會得到相同的雜湊值。

攻擊者利用這個性質的步驟：

1. 找出兩則會碰撞的訊息 M₁ 與 M₂。
2. 請求 M₁ 的 MAC 標籤 Hash(M₁ ‖ K)。
3. 猜測 Hash(M₂ ‖ K) 相同——藉此偽造出有效標籤，攻破該 MAC 的安全性。

HMAC 建構#

HMAC（hash-based MAC）建構讓我們能從雜湊函式建構出比秘密前綴或秘密後綴都更安全的 MAC。

只要底層雜湊具碰撞抗性，HMAC 就產出一個安全的 PRF。

而即使雜湊不具碰撞抗性，只要該雜湊的壓縮函式是一個 PRF，HMAC 仍然產出安全的 PRF。

IPSec、SSH 與 TLS 這些安全通訊協定都用過 HMAC。（HMAC 的規格見 NIST FIPS 198-1 標準與 RFC 2104。）

公式#

HMAC(K, M) = Hash( (K ⊕ opad) ‖ Hash( (K ⊕ ipad) ‖ M ) )

• opad（outer padding，外層填充）：一個與 Hash 區塊大小等長的字串 5c5c5c...5c。金鑰 K 通常比一個區塊短，會用 00 位元組補滿再與 opad 做 XOR。K ⊕ opad 是外層 Hash 呼叫處理的第一個區塊。
• ipad（inner padding，內層填充）：一個與 Hash 區塊大小等長的字串 363636...36，同樣以 00 位元組補完。所得區塊是內層 Hash 呼叫處理的第一個區塊。

例如若 K 是 1 位元組的字串 00，則 K ⊕ opad = opad。（K 是任何不超過一個區塊長度的全零字串時亦然。）

若用 SHA-256 當作 Hash，我們就稱這個 HMAC 實例為 HMAC-SHA-256。更一般地，HMAC-Hash 表示使用雜湊函式 Hash 的 HMAC 實例。

這意味著若有人要你「用 HMAC」，你應該永遠反問一句：「用哪個雜湊函式？」

還有一種比秘密前綴與秘密後綴更安全的建構：信封法（envelope method），表示為 Hash(K ‖ M ‖ K)，稱為三明治 MAC（sandwich MAC）。但它在理論上仍不如 HMAC 安全。

對雜湊式 MAC 的通用攻擊#

有一個攻擊對所有基於迭代雜湊函式的 MAC 都有效。

回想秘密後綴建構中「用雜湊碰撞取得 MAC 碰撞」的攻擊——同樣的策略可以用來攻擊秘密前綴 MAC 或 HMAC，只是後果沒那麼毀滅性。

以秘密前綴 MAC Hash(K ‖ M) 為例。若摘要是 n 位元：

1. 向持有金鑰的系統請求約 2^(n/2) 個 MAC 標籤，你就能找到兩則訊息 M₁、M₂ 使得 Hash(K ‖ M₁) = Hash(K ‖ M₂)（回想第 6 章的生日攻擊）。
2. 若該雜湊像 SHA-256 一樣容許長度延伸，你就能用 M₁ 與 M₂ 偽造 MAC：選一段任意資料 M₃，向 MAC 預言機查詢 Hash(K ‖ M₁ ‖ M₃)——這是訊息 M₁ ‖ M₃ 的 MAC。
3. 而這同時也是訊息 M₂ ‖ M₃ 的 MAC，因為 M₁ 與 M₃ 以及 M₂ 與 M₃ 所對應的雜湊內部狀態相同——你成功偽造了一個 MAC 標籤。

這個攻擊即使雜湊函式不易受長度延伸攻擊也有效，對 HMAC 也有效。

攻擊成本同時取決於鏈接值的大小與 MAC 的長度：若 MAC 的鏈接值是 512 位元、標籤是 128 位元，2^64 的計算能找到一個 MAC 碰撞，但大概找不到內部狀態的碰撞——因為那平均需要 2^(512/2) = 2^256 次運算。

當 n 成長到超過（比方說）128 位元時，這個攻擊就變得不可行。