PBKDF2

**PBKDF2** (**Password-Based Key Derivation Function 2**) は、鍵導出関数である。計算コストを変動させることが可能であり、暗号化する際に、総当たり攻撃に対する脆弱性を軽減することを目的として使用される。

PBKDF2は、導出鍵が160ビット以下に制限されるPBKDF1に続いて、PKCS #5 v2.0 (RSA)、 として規定された。2017年に公開された (PKCS #5 v2.1)は、パスワードのハッシュ化には、PBKDF2を利用することを推奨している。

## 目的
PBKDF2は、HMACなどの疑似乱数関数や、ソルトを付加したパスワードやパスフレーズを用いる。また、鍵導出処理を何度も繰り返して、前回の処理で導出した鍵を次回の処理のパスワードとして用いることで、導出鍵を解読困難にする。この繰り返し処理は、ストレッチングと呼ばれる。

2000年に公開されたPKCS #5 v2.0におけるストレッチングの推奨回数は、最低1,000回であった。しかしながら、CPU処理速度の向上に伴って、ストレッチングの推奨回数も増加しており、2005年に公開されたでの推奨回数は、4,096回である。AppleのiPhone OS 3では2,000回、iOS 4では10,000回のストレッチングを行っており、LastPassは、2011年時点で、サーバ側での100,000回のストレッチングに加えて、クライアント側での5,000回のストレッチングも行っている。OWASPは、PBKDF2-HMAC-SHA256の場合、2021年時点で310,000回、2023年時点で600,000回を推奨している。

ソルトをパスワードに付加することで、攻撃者は複数のパスワードを一度に試行できなくなるため、ハッシュ値の事前計算（レインボーテーブル）の効果を下げることができる。PKCS #5では、ソルトの長さを64ビット以上にすることを推奨しており、アメリカ国立標準技術研究所は、ソルトは128ビット以上が必須としている。

## 鍵導出の処理

鍵導出関数PBKDF2は、5つの引数を持つ。

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

ここで、
* *PRF* は、出力値の長さが*hLen* であり、2つの引数を持つ疑似乱数関数 (HMAC-SHA1など)
* *Password* は、鍵導出のためのマスターパスワード
* *Salt* は、ソルト
* *c* は、ストレッチング回数
* *dkLen* は、導出鍵のビット長
* *DK* は、導出鍵
である。

*hLen* ビットのブロックTiは、次式で求められる。ただし、`+`は、文字列連結を意味する。

 DK = T1 + T2 + ... + Tdklen/hlen
 Ti = F(Password, Salt, c, i)

関数*F* は、PRFの*c* 回のXOR (^) の繰り返しである。

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

最初のPRFは、*Password* を鍵とし、ビッグエンディアンの32ビット整数*i* と連結した*Salt* を入力値とする。ただし、*i* は1始まりとする。次回以降は、*Password* を鍵とし、前回のPRFの出力値を入力値とする。

 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は、PBKDF2より単純な鍵導出関数である。最初の*U* (PBKDF1では*T*とされる) は、`PRF(Password + Salt)`によって生成され、次回以降は、単に`PRF(U<sub>previous</sub>)`である。導出鍵は、最終的に算出されたハッシュ値の最初の*dkLen* ビットとする。このため、PBKDF1の導出鍵の長さは、*hLen* ビット以下に制限される。

## HMACの衝突
PBKDF2は、HMACを疑似乱数関数として用いるとき、導出鍵が衝突する異なるパスワードの組を容易に得ることが可能である。HMACの中で用いられるハッシュ関数のブロック長よりパスワードが長いとき、パスワードをハッシュ化したものをパスワードとして用いる。例えば、疑似乱数関数として、HMAC-SHA1を用いると、

* **パスワード**: ``

は、

* **SHA1** (16進数): `65426b585154667542717027635463617226672a`
* **SHA1** (ASCII): `eBkXQTfuBqp'cTcar&g*`

となる。よって、PBKDF2-HMAC-SHA1は、次の2つの異なるパスワード

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

から、ソルトやストレッチングに関係なく、同じ鍵を導出する。例えば、

* **PRF**: HMAC-SHA1
* **ソルト**: A009C1A485912C6AE630D3E744240B04
* **ストレッチング回数**: 1,000回
* **導出鍵の長さ**: 16バイト

とすると、2つの関数

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

は、同じ導出鍵`17EB4014C8C461C300E9B61518B9A18B`を生成する。ただし、パスワードのハッシュ値を得るためには、パスワードも得る必要があるため、導出鍵の衝突は、PBKDF2やHMACの脆弱性を示唆するものではない。

## PBKDF2の代替
PBKDF2は、ストレッチング回数を調整することで、計算時間を変動させること可能である。しかしながら、短いコード量、少ないメモリ量で実装できるため、ASICやGPUを用いた総当たり攻撃に弱い。パスワードハッシュ関数のbcryptは、計算時間は固定であるものの、計算に多くのメモリ量を必要とするため、PBKDF2より総当たり攻撃に強い。その後に開発された鍵導出関数のscryptは、任意の大きさのメモリ量を使うことができ、ASCIやGPUによる攻撃に対する耐性が高い。

安全なパスワードハッシュ化手法を開発することを目的として、2013年にが開催された。2015年7月20日にパスワードハッシュ関数Argon2の優勝が決まり、他に4つの関数、、yescryptおよびが特別賞として選ばれた。

## 脚注

## 参考文献
* 
* 
* 

## 外部リンク
* - RSAによるPKCS #5 v2.1.
* – HMAC-SHA1を用いたPBKDF2のテストデータ
*NIST Special Publication 800-132 Recommendation for Password-Based Key Derivation