帶金鑰的雜湊 • 嚴謹密碼學：現代加密實務入門

第 6 章討論的雜湊函式接收一則訊息、回傳它的雜湊值——通常是 256 或 512 位元的短字串。

由於過程中沒有秘密值參與，任何人都能算出一則訊息的雜湊值、驗證某訊息是否雜湊到某個特定值。但有時候，你並不想讓任何人都能做這件事。

這就是帶金鑰雜湊函式（keyed hash functions）——也就是用秘密金鑰做雜湊——登場的地方。

帶金鑰雜湊構成兩類重要密碼演算法的基礎：
訊息鑑別碼（MAC）：鑑別訊息並保護其完整性。
偽隨機函式（PRF）：產生看起來隨機、雜湊大小的值。

本章脈絡#

訊息鑑別碼（MAC）——偽造、選擇訊息攻擊與重放攻擊。
偽隨機函式（PRF）——為什麼 PRF 比 MAC 更強。
從無金鑰雜湊建構帶金鑰雜湊——秘密前綴、秘密後綴、HMAC。
從區塊密碼建構：CMAC——CBC-MAC 為何不安全，CMAC 如何修正。
專用 MAC 設計——Poly1305 與 SipHash。

常見錯誤#

與密碼和無金鑰雜湊函式一樣，紙上安全的 MAC 與 PRF，在真實環境中面對現實的攻擊者時仍可能出現漏洞。

MAC 驗證的時序攻擊#

旁道攻擊針對的是密碼演算法的實作而非演算法本身。其中時序攻擊利用演算法的執行時間來判定金鑰、明文與秘密隨機值這類秘密資訊。

當遠端系統驗證標籤所花的時間取決於標籤的值時，MAC 就可能受時序攻擊。
攻擊者可以嘗試許多錯誤的標籤，找出耗時最長的那一個，藉此判定正確的訊息標籤。

問題出在伺服器逐位元組依序比較正確標籤與錯誤標籤、直到位元組相異為止。下面的 Python 程式碼就是變動時間的比較——若第一個位元組就不同，函式只比較一次就回傳；若字串 x 與 y 完全相同，函式就會做 n 次比較：

def compare_mac(x, y, n):
    for i in range(n):
        if x[i] != y[i]:
            return False
    return True

實測：下面的程式測量 100,000 次呼叫的執行時間，先用兩個相同的 10 位元組值，再用第三個位元組相異的值：

from time import time

MAC1 = '0123456789abcdef'
MAC2 = '01X3456789abcdef'
TRIALS = 100000

# each call will look at all bytes
start = time()
for i in range(TRIALS):
    compare_mac(MAC1, MAC1, len(MAC1))
end = time()
print("%0.5f" % (end-start))

# each call will look at three bytes
start = time()
for i in range(TRIALS):
    compare_mac(MAC1, MAC2, len(MAC1))
end = time()
print("%0.5f" % (end-start))

在作者的測試環境中，兩者的執行時間分別約為 0.215 秒與 0.095 秒。
這個差距大到足以讓你辨識出演算法內部發生了什麼。把差異移到字串的其他位移，你會觀察到不同的執行時間——若 MAC1 是正確標籤、MAC2 是攻擊者嘗試的標籤，你就能輕易辨識出第一個差異的位置，也就是猜對的位元組數。

解法：若執行時間不依賴秘密，時序攻擊就無效。這正是實作者努力撰寫常數時間實作的原因——不論秘密輸入值為何，程式碼都花完全相同的時間完成。

下面的 C 函式以常數時間比較兩個 size 位元組的緩衝區：暫時變數 result 為非零，若且唯若兩個緩衝區某處有差異：

int cmp_const(const void *a, const void *b, const size_t size)
{
  const unsigned char *_a = (const unsigned char *) a;
  const unsigned char *_b = (const unsigned char *) b;
  unsigned char result = 0;
  size_t i;

  for (i = 0; i < size; i++) {
    result |= _a[i] ^ _b[i];
  }

  return result; /* returns 0 if *a and *b are equal, nonzero otherwise */
}

如你所料，變動時間的字串比較不只在 MAC 驗證中造成漏洞，在許多其他密碼與安全功能中也是。

當海綿洩漏#

SHA-3 與 SipHash 這類基於置換的演算法簡單、易於實作、實作精簡——但它們在面對「能取得系統狀態快照」的旁道攻擊時很脆弱。

例如若某個行程能在任何時候讀取 RAM 與暫存器的值、或讀取記憶體的核心傾印，攻擊者就能判定 MAC 模式下 SHA-3 的內部狀態，或 SipHash 的內部狀態。
接著他們可以計算置換的反函式，還原出初始的秘密狀態，然後為任何訊息偽造標籤，攻破該 MAC 的安全性。

所幸這個攻擊對 HMAC-SHA-256 與帶金鑰 BLAKE2 這類基於壓縮函式的 MAC 無效——因為攻擊者需要的是「金鑰正被使用的那個確切時刻」的記憶體快照。
結論：若你身處「行程記憶體的一部分可能外洩」的環境，就使用基於不可逆變換之壓縮函式的 MAC，而非基於置換的 MAC。

本章脈絡#

常見錯誤#

MAC 驗證的時序攻擊#

當海綿洩漏#

延伸閱讀#