PBKDF1

在密碼學中， **PBKDF1** 和 **PBKDF2** （**基於密碼的金鑰衍生函式 1** 和 **2** ，英語：**Password-Based Key Derivation Function 1** and **2**）是具有可變計算成本的金鑰衍生函式，可以降低面對蠻力攻擊的脆弱性。

PBKDF2 是 RSA 實驗室的公鑰密碼學標準（PKCS）系列的一部分，即 PKCS #5 v2.0，同時也作為網際網路工程任務組的 RFC 2898 發布。它取代了只能生成最長 160 位元衍生金鑰的 PBKDF1。2017 年發布的 RFC 8018（PKCS #5 v2.1）推薦使用 PBKDF2 進行密碼雜湊處理。

## 目的和運作

PBKDF2 將偽隨機函式（例如基於雜湊的訊息身分驗證碼，HMAC）與鹽值一起應用於輸入密碼或密碼詞組，並多次重複該過程以生成**衍生金鑰**，然後可以將其用作後續過程的加密金鑰。增加的計算工作使密碼破解變得更加困難，這被稱為金鑰延伸 。

在 2000 年編寫的標準建議最小迭代次數為 1,000 次，但隨 CPU 效能的提高，該參數會隨著時間的推移而增加。2005 年的 Kerberos 標準推薦 4,096 次迭代；據報導，蘋果公司在 iOS 3 中使用了 2,000 次，在 iOS 4 中使用了 10,000 次；而 LastPass 在 2011 年對 JavaScript 客戶端使用了 5,000 次迭代，對伺服器端雜湊使用了 100,000 次迭代。 2023 年，OWASP 建議 PBKDF2-HMAC-SHA256 使用 600,000 次迭代，PBKDF2-HMAC-SHA512 使用 210,000 次迭代。

在密碼中添加鹽會降低使用預計算的雜湊值（彩虹表）進行攻擊的能力，並且意味著必須單獨測試多個密碼，而不是一次測試所有密碼。該標準建議鹽長度至少為 64 位元。美國國家標準與技術研究所推薦的長度為 128 位元。 

## 金鑰推導過程

PBKDF2 金鑰推導函式有五個輸入參數：

　
: DK = PBKDF2(PRF, Password, Salt, c, dkLen)

其中

* PRF 是一個有兩個輸入參數的偽隨機函式（例如一個有金鑰的 HMAC），輸出長度 hLen
* Password 是主密碼，推導金鑰由它生成
* Salt 是一個位元序列，即鹽
* c 是希望進行的迭代次數
* dkLen 是希望生成推導金鑰的長度（位）
* DK 是生成的推導金鑰

衍生金鑰 DK 的每個 hLen 位的塊 Ti 計算如下（使用 + 表示字串拼接）：

　
: DK = T1 + T2 + ⋯ + Tdklen/hlen

　
: Ti = F(Password, Salt, c, i)

函式 F 是鏈式 PRF 的 _c_ 次迭代的互斥或 ( ^ )。PRF 的第一次迭代使用 _Password_ 作為 PRF 金鑰，並將 _Salt_ 與編碼為大端序 32 位元整數的 i（索引 _i_ 從 1 開始）拼接，作為輸入。 PRF 的後續迭代使用 _Password_ 作為 PRF 金鑰，並將先前 PRF 計算的輸出作為輸入：

　
: F(Password, Salt, c, i) = U1 ^ U2 ^ ⋯ ^ Uc

其中

　
: U1 = PRF(Password, Salt + INT\_32\_BE(i))

　
: U2 = PRF(Password, U1)

　
: ⋮

　
: Uc = PRF(Password, Uc−1)

例如， WPA2 使用：

　
: DK = PBKDF2(HMAC−SHA1, passphrase, ssid, 4096, 256)

PBKDF1 過程更簡單：初始 _U_ （在這個版本中稱為 _T_ ）由 PRF(Password + Salt) 建立，後面只是將上一輪的 _U_ 作為下一輪 PRF 的輸入，即 PRF(Uprevious) 。最後提取最終雜湊的前 _dkLen_ 位作為金鑰。因此 PBKDF1 存在大小限制。

## HMAC 衝突

當使用 HMAC 作為其偽隨機函式時，PBKDF2 有一個有趣的特性。可以簡單地構造任意數量的不同密碼對，並且每對密碼對都存在衝突。如果提供的密碼長於底層 HMAC 雜湊函式的塊大小，則密碼首先被預雜湊為摘要，然後該摘要用作密碼。例如，以下密碼太長：

* **密碼：** `plnlrtfpijpuhqylxbgqiiyipieyxvfsavzgxbbcfusqkozwpngsyejqlmjsytrmd`

因此，在使用 HMAC-SHA1 時，使用 SHA-1 將其預雜湊為：

* **SHA1** （十六進位）： `65426b585154667542717027635463617226672a`

可以用 ASCII 表示為：

* **SHA1** （ASCII）： `eBkXQTfuBqp'cTcar&g*`

這意味著無論鹽或迭代次數如何，PBKDF2-HMAC-SHA1 都會為下列密碼生成相同的金鑰位元組：

* "plnlrtfpijpuhqylxbgqiiyipieyxvfsavzgxbbcfusqkozwpngsyejqlmjsytrmd"
* "eBkXQTfuBqp'cTcar&g\*"

例如，使用：

* **PRF** : HMAC-SHA1
* **鹽：** A009C1A485912C6AE630D3E744240B04
* **迭代次數：** 1,000
* **衍生金鑰長度：** 16 位元組

下面兩個函式呼叫：

```
PBKDF2-HMAC-SHA1("plnlrtfpijpuhqylxbgqiiyipieyxvfsavzgxbbcfusqkozwpngsyejqlmjsytrmd", ...)
PBKDF2-HMAC-SHA1("eBkXQTfuBqp'cTcar&g*", ...) 
```

將生成相同的衍生金鑰位元組 ( `17EB4014C8C461C300E9B61518B9A18B` )。這些衍生金鑰衝突並不代表存在安全漏洞，因為仍然必須知道原始密碼才能生成密碼的雜湊值。利用這一性質，對於一些 ZIP 格式的加密壓縮檔案，可能存在兩個可行的密碼。

## PBKDF2 的替代演算法

PBKDF2 的一個缺點是，儘管可以通過改變迭代次數來任意調整所需的計算時間，但它可以用一個小電路和很少的 RAM 來實現，這使得使用特殊應用積體電路（ASIC）或圖形處理器（GPU）進行暴力攻擊相對低廉。Bcrypt 密碼雜湊函式需要更大的 RAM（但仍然不能單獨調整，由給定的 CPU 時間決定）並且對此類攻擊的抵抗力稍強， 而更現代的 Scrypt 金鑰衍生函式可以任意使用大量記憶體，因此更能抵抗 ASIC 和 GPU 攻擊。

2013 年舉行的密碼雜湊競賽（PHC）鼓勵開發一種更具抵抗力的密碼雜湊方法。2015 年 7 月 20 日，Argon2 被選為最終的獲勝者，PHC 還特別表彰了其他四種密碼雜湊方案：Catena、Lyra2、yescrypt 和 Makwa。另一種替代方法是氣球雜湊，這是 NIST 密碼指南中推薦的方法。

## 參見

* PBKDF2 實現列表

## 參考資料

## 外部連結

* PKCS #5 v2.1 (PDF). RSA Laboratories. （原始內容 (PDF) 存檔於 2017-04-11）.
* RFC 2898 – Specification of PKCS #5 v2.0.
* RFC 6070 – Test vectors for PBKDF2 with HMAC-SHA1.
* NIST Special Publication 800-132 Recommendation for Password-Based Key Derivation