コンテンツにスキップ

英文维基 | 中文维基 | 日文维基 | 草榴社区

「利用者:Wdqh/sandbox」の版間の差分

削除された内容 追加された内容
Wdqh (会話 | 投稿記録)
PBKDF2
タグ: 差し戻し済み
Wdqh (会話 | 投稿記録)
PBKDF2
タグ: 差し戻し済み
3行目: 3行目:
'''PBKDF2''' ('''Password-Based Key Derivation Function 2''') は、[[鍵導出関数]]である。計算コストを変動させることが可能であり、[[暗号]]化する際に、[[総当たり攻撃]]に対する[[脆弱性]]を軽減することを目的として使用される。
'''PBKDF2''' ('''Password-Based Key Derivation Function 2''') は、[[鍵導出関数]]である。計算コストを変動させることが可能であり、[[暗号]]化する際に、[[総当たり攻撃]]に対する[[脆弱性]]を軽減することを目的として使用される。


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


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


2000年に公開されたPKCS #5 v2.0におけるストレッチングの推奨回数は、最低1000回であった。しかし、[[CPU]]処理速度の向上に伴って、ストレッチングの推奨回数も増加しており、2005年に公開されたRFC 4120での推奨回数は、4096回である。[[Apple]]の[[iOS (アップル)|iOS]] 3では2000回、iOS 4では10,000回のストレッチング行っており、[[LastPass]] は、2011年時点で、[[サーバ]]側での100,000回のストレッチングに加えて、[[クライアント (コンピュータ)|クライアント]]側での5000回のストレッチングも行っている。
2000年に公開されたPKCS #5 v2.0におけるストレッチングの推奨回数は、最低1000回であった。しかしながら、[[CPU]]処理速度の向上に伴って、ストレッチングの推奨回数も増加しており、2005年に公開されたRFC 4120での推奨回数は、4096回である。[[Apple]]の[[iOS (アップル)|iOS]] 3では2000回、iOS 4では10,000回のストレッチング行っており、[[LastPass]]は、2011年時点で、[[サーバ]]側での100,000回のストレッチングに加えて、[[クライアント (コンピュータ)|クライアント]]側での5000回のストレッチングも行っている。


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


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


48行目: 48行目:
を用いている。
を用いている。


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


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


* '''Password:''' <code>{{not a typo|plnlrtfpijpuhqylxbgqiiyipieyxvfsavzgxbbcfusqkozwpngsyejqlmjsytrmd}}</code>
* '''Password:''' <code>{{not a typo|plnlrtfpijpuhqylxbgqiiyipieyxvfsavzgxbbcfusqkozwpngsyejqlmjsytrmd}}</code>
60行目: 60行目:
* '''SHA1''' (ASCII): <code>eBkXQTfuBqp'cTcar&g*</code>
* '''SHA1''' (ASCII): <code>eBkXQTfuBqp'cTcar&g*</code>


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


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


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


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


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

2020年3月31日 (火) 15:20時点における版

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

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

目的と効果 

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

2000年に公開されたPKCS #5 v2.0におけるストレッチングの推奨回数は、最低1000回であった。しかしながら、CPU処理速度の向上に伴って、ストレッチングの推奨回数も増加しており、2005年に公開されたRFC 4120での推奨回数は、4096回である。AppleiOS 3では2000回、iOS 4では10,000回のストレッチングを行っており、LastPassは、2011年時点で、サーバ側での100,000回のストレッチングに加えて、クライアント側での5000回のストレッチングも行っている。

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

鍵導出の処理 

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

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

ここで、

  • PRF は、出力値の長さがhLen であり、2つの引数を持つ疑似乱数関数 (HMACなど)
  • 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(Uprevious)である。導出鍵は、最終的に算出されたハッシュ値の最初のdkLen ビットとする。このため、PBKDF1の導出鍵の長さは、hLen ビット以下に制限される。

HMACの衝突

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

  • Password: plnlrtfpijpuhqylxbgqiiyipieyxvfsavzgxbbcfusqkozwpngsyejqlmjsytrmd

は、

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

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

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

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

  • PRF: HMAC-SHA1
  • Salt: A009C1A485912C6AE630D3E744240B04
  • Iterations: 1,000
  • Derived key length: 16 bytes

とすると、2つの関数

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

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

PBKDF2の代替

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

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

');