寫給開發人員的實用密碼學（三）—— MAC 與密鑰派生函數 KDF

2022 年 3 月 14 日
筆記
演算法

一、MAC 消息認證碼
- MAC 與哈希函數、數字簽名的區別
- MAC 的應用
二、KDF 密鑰派生函數
參考

本文主要翻譯自 Practical-Cryptography-for-Developers-Book，但是筆者也補充了 HMAC 的 Python 實現以及 scrypt 使用示例。

《寫給開發人員的實用密碼學》系列文章目錄：

一、MAC 消息認證碼

MAC 消息認證碼，即 Message Authentication Code，是用於驗證消息的一小段資訊。
換句話說，能用它確認消息的真實性——消息來自指定的發件人並且沒有被篡改。

MAC 值通過允許驗證者（也擁有密鑰）檢測消息內容的任何更改來保護消息的數據完整性及其真實性。

一個安全的 MAC 函數，跟加密哈希函數非常類似，也擁有如下特性：

快速：計算速度要足夠快
確定性：對同樣的消息跟密鑰，應該總是產生同樣的輸出
難以分析：對消息或密鑰的任何微小改動，都應該使輸出完全發生變化
不可逆：從 MAC 值逆向演算出消息跟密鑰應該是不可行的。
無碰撞：找到具有相同哈希的兩條不同消息應該非常困難（或幾乎不可能）

但是 MAC 演算法比加密哈希函數多一個輸入值：密鑰，因此也被稱為 keyed hash functions，即「加密鑰的哈希函數」。

如下 Python 程式碼使用 key 跟消息計算出對應的 HMAC-SHA256 值：

import hashlib, hmac, binascii

key = b"key"
msg = b"some msg"

mac = hmac.new(key, msg, hashlib.sha256).digest()

print(f"HMAC-SHA256({key}, {msg})", binascii.hexlify(mac).decode('utf8'))

# => HMAC-SHA256(b'key', b'some msg') = 32885b49c8a1009e6d66662f8462e7dd5df769a7b725d1d546574e6d5d6e76ad

HMAC 的演算法實際上非常簡單，我參考 wiki/HMAC 給出的偽碼，編寫了下面這個 Python 實現，沒幾行程式碼，但是完全 work：

import hashlib, binascii

def xor_bytes(b1, b2):
  return bytes(a ^ c for a, c in zip(b1, b2))

def my_hmac(key, msg, hash_name):
  # hash => (block_size, output_size)
  # 單位是 bytes，數據來源於 //en.wikipedia.org/wiki/HMAC
  hash_size_dict = {
    "md5": (64, 16),
    "sha1": (64, 20),
    "sha224": (64, 28),
    "sha256": (64, 32),
    # "sha512/224": (128, 28),  # 這倆演算法暫時不清楚在 hashlib 里叫啥名
    # "sha512/256": (128, 32),
    "sha_384": (128, 48),
    "sha_512": (128, 64),
    "sha3_224": (144, 28),
    "sha3_256": (136, 32),
    "sha3_384": (104, 48),
    "sha3_512": (72, 64),
  }
  if hash_name not in hash_size_dict:
    raise ValueError("unknown hash_name")

  block_size, output_size = hash_size_dict[hash_name]
  hash_ = getattr(hashlib, hash_name)

  # 確保 key 的長度為 block_size
  block_sized_key = key
  if len(key) > block_size:
    block_sized_key = hash_(key).digest()  # 用 hash 函數進行壓縮
  if len(key) < block_size:
    block_sized_key += b'\x00' * (block_size - len(key))  # 末尾補 0
  
  o_key_pad = xor_bytes(block_sized_key, (b"\x5c" * block_size))  # Outer padded key
  i_key_pad = xor_bytes(block_sized_key, (b"\x36" * block_size))  # Inner padded key

  return hash_(o_key_pad + hash_(i_key_pad + msg).digest()).digest()


# 下面驗證下
key = b"key"
msg = b"some msg"

mac_ = my_hmac(key, msg, "sha256")
print(f"HMAC-SHA256({key}, {msg})", binascii.hexlify(mac_).decode('utf8'))

# 輸出跟標準庫完全一致：
# => HMAC-SHA256(b'key', b'some msg') = 32885b49c8a1009e6d66662f8462e7dd5df769a7b725d1d546574e6d5d6e76ad

MAC 與哈希函數、數字簽名的區別

上一篇文章提到過，哈希函數只負責生成哈希值，不負責哈希值的可靠傳遞。

而數字簽名呢，跟 MAC 非常相似，但是數字簽名使用的是非對稱加密系統，更複雜，計算速度也更慢。

MAC 的功能跟數字簽名一致，都是驗證消息的真實性（authenticity）、完整性（integrity）、不可否認性（non-repudiation），但是 MAC 使用哈希函數或者對稱密碼系統來做這件事情，速度要更快，演算法也更簡單。

MAC 的應用

1. 驗證消息的真實性、完整性

這是最簡單的一個應用場景，在通訊雙向都持有一個預共享密鑰的前提下，通訊時都附帶上消息的 MAC 碼。
接收方也使用「收到的消息+預共享密鑰」計算出 MAC 碼，如果跟收到的一致，就說明消息真實無誤。

注意這種應用場景中，消息是不保密的！

2. AE 認證加密 – Authenticated encryption

常用的加密方法只能保證數據的保密性，並不能保證數據的完整性。

而這裡介紹的 MAC 演算法，或者還未介紹的基於非對稱加密的數字簽名，都只能保證數據的真實性、完整性，不能保證數據被安全傳輸。

而認證加密，就是將加密演算法與 MAC 演算法結合使用的一種加密方案。

在確保 MAC 碼「強不可偽造」的前提下，首先對數據進行加密，然後計算密文的 MAC 碼，再同時傳輸密文與 MAC 碼，就能同時保證數據的保密性、完整性、真實性，這種方法叫 Encrypt-then-MAC, 縮寫做 EtM. 接收方在解密前先計算密文的 MAC 碼與收到的對比，就能驗證密文的完整性與真實性。

AE 有一種更安全的變體——帶有關聯數據的認證加密 (authenticated encryption with associated data，AEAD)。
AEAD 將「關聯數據(Associated Data, AD)」——也稱為「附加驗證數據（Additional Authenticated Data, AAD）」——綁定到密文和它應該出現的上下文，以便可以檢測和拒絕將有效密文「剪切並粘貼」到不同上下文的嘗試。 AEAD 用於加密和未加密數據一起使用的場景（例如，在加密的網路協議中），並確保整個數據流經過身份驗證和完整性保護。
換句話說，AEAD 增加了檢查某些內容的完整性和真實性的能力。

我們會在第六章「對稱加密演算法」中看到如何通過 Python 使用 AEAD 加密方案 AES-256-GCM.

3. 基於 MAC 的偽隨機數生成器

MAC 碼的另一個用途就是偽隨機數生成函數，相比直接使用熵+哈希函數的進行偽隨機數計算，MAC 碼因為多引入了一個變數 key，理論上它會更安全。

這種場景下，我們稱 MAC 使用的密鑰為 salt，即鹽。

next_seed = MAC(salt, seed)

二、KDF 密鑰派生函數

我們都更喜歡使用密碼來保護自己的數據而不是二進位的密鑰，因為相比之下二進位密鑰太難記憶了，字元形式的密碼才是符合人類思維習慣的東西。

可對電腦而言就剛好相反了，現代密碼學的很多演算法都要求輸入是一個大的數字，二進位的密鑰就是這樣一個大的數字。
因此顯然我們需要一個將字元密碼（Password）轉換成密鑰（Key）的函數，這就是密鑰派生函數 Key Derivation Function.

直接使用 SHA256 之類的加密哈希函數來生成密鑰是不安全的，因為為了方便記憶，通常密碼並不會很長，絕大多數人的密碼長度估計都不超過 15 位。
甚至很多人都在使用非常常見的弱密碼，如 123456 admin 生日等等。
這就導致如果直接使用 SHA256 之類的演算法，許多密碼將很容易被暴力破解、字典攻擊、彩虹表攻擊等手段猜測出來！

KDF 目前主要從如下三個維度提升 hash 碰撞難度：

時間複雜度：對應 CPU/GPU 計算資源
空間複雜度：對應 Memory 記憶體資源
並行維度：使用無法分解的演算法，鎖定只允許單執行緒運算

主要手段是加鹽，以及多次迭代。這種設計方法被稱為「密鑰拉伸 Key stretching」。

因為它的獨特屬性，KDF 也被稱作慢哈希演算法。

目前比較著名的 KDF 演算法主要有如下幾個：

PBKDF2：這是一個非常簡單的加密 KDF 演算法，目前已經不推薦使用。
Bcrypt：安全性在下降，用得越來越少了。不建議使用。
Scrypt：可以靈活地設定使用的記憶體大小，在 argon2 不可用時，可使用它。
Argon2：目前最強的密碼 Hash 演算法，在 2015 年贏得了密碼 Hash 競賽。

如果你正在開發一個新的程式，需要使用到 KDF，建議選用 argon2/scrypt.

Python 中最流行的加密庫是 cryptography，requests/flask 底層就使用了它，下面我們使用這個庫來演示下 Scrypt 演算法的使用：

# pip install cryptography==36.0.1
import os
from cryptography.hazmat.primitives.kdf.scrypt import Scrypt

salt = os.urandom(16)

# derive
kdf = Scrypt(
    salt=salt,
    length=32,
    n=2**14,
    r=8,
    p=1,
)
key = kdf.derive(b"my great password")

# verify
kdf = Scrypt(
    salt=salt,
    length=32,
    n=2**14,
    r=8,
    p=1,
)
kdf.verify(b"my great password", key)

參考

Tags: 演算法