2019/12/29 追記: いまでもこの記事が時々参照されています。Googleなどからこの記事へとやってきた方は、パスワードか何か重要な情報をどう保存するか？ということを考えておられるかもしれません。もしそうであれば、ぜひこの記事のコメントも記事を読んだあとに参照していただきたいと思います。徳丸さんをはじめとして僕よりもはるかに知見のある方の考えなどもあります。ハッシュ化されたパスワードは、もしかしたら今これを読もうとしておられる方が作っているアプリケーションよりも長きにわたって利用されるかもしれません。少々の時間をいただきますが、そういう理由でぜひコメントのディスカッションも参考にしたうえで今できる最良のセキュリティーを実装していってください

はじめに

この記事ではパスワードを保存する際によく用いられるソルトとハッシュ関数を使うやり方について、なぜそれが微妙であるかを解説した後に、それを解決する方法を紹介する。
もし記事の中に何か誤りがあれば、気軽に指摘して欲しいと思う。

ハッシュ関数とソルトを用いたパスワードの保存

例えば次のような変数と関数があるとする。

変数	意味
$m$	パスワード（メッセージ¹）
$k$	ソルト
$H$	ハッシュ関数
$a \mid\mid b$	文字列$a$と$b$の結合

すると、次のようなコードでパスワードからハッシュ値を求めてデータベースなどに保存するケースが多いと思う。

hp = H(k \mid\mid m)

しかし、使うハッシュ関数によっては、このようなコードであると問題が起きる。

前からソルトを付与する方法と伸長攻撃

ハッシュ関数によっては、伸長攻撃と呼ばれる次のような攻撃が可能なものがある。

$m$と$k$によるハッシュ値$H(k \mid\mid m)$が分かると、$m$に適当な文字列を追加した文字列$m'$について、$k$を知ることなく$H(k \mid\mid m')$を求めることができる

例えばSHA1やSHA2、MD5などはこのような特徴を持つ。従って、攻撃者はあらかじめ、1文字のパスワードなど短いパスワードのハッシュ値を入手した後、長い文字列をパスワードにした場合のハッシュ値を計算することができる。よって、この方法はやや危険であると言える。

後ろからソルトを付与する方法

では、$H(m \mid\mid k)$のように後ろからソルトを付与すればよいのかもしれない。確かにこの方法で伸長攻撃はできなくなるが、この方法を用いると、ハッシュ関数が脆弱になった場合に問題が発生する。
ハッシュ関数には次のような性質がある。

弱衝突耐性: あるメッセージ$m$と等しいハッシュ値を持つような$m'$を求めるのが困難である性質
強衝突耐性: 任意のハッシュ値について、$H(m) = H(m')$となる$m$と$m'$の組を見つけるのが困難である性質

今、パスワードを次のような方法でハッシュ化し、データベースに保存しているとする。

hp = H(m \mid\mid k)

弱衝突耐性が破られているとして、攻撃者はまず既知のメッセージ$m$についてハッシュ値が等しくなる$H(m)=H(m')$となる$m′$を得ることができる。$m \ne m′$であったとしても、$H(m)=H(m′)$であるとハッシュ関数の内部状態が$k$までで同じになってしまうので、$H(m \mid\mid k)=H(m′ \mid\mid k)$となり、パスワードが異なるにも関わらず意図しない認証をしてしまう可能性がある。

メッセージ認証コードとHMAC

これらの対策として、最終的にはHMACと呼ばれる方法を用いるのがよいとされている。HMACは、鍵（ソルト）を$k$、メッセージ（パスワード）を$m$、ハッシュ関数を$H$とした時に次のような関数である。なお、$\oplus$は排他的論理和を表し、$ipad$と$opad$は定数である。

\begin{align}
HMAC &= \\
  &\text{val}\, ikey = k \oplus ipad \\
  &\text{val}\, okey = k \oplus opad \\
  &H(okey \mid\mid H(ikey \mid\mid m))
\end{align}

このように、2回ハッシュ関数に入れることで、ハッシュ関数に伸長攻撃があったり強衝突耐性が破れていたとしてもHMACが直ちに危険になることはない。

まとめ

ソルトを前や後ろから付与してパスワードをハッシュ化するのはよくないので、特に理由がなければHMACを使う方がよいと思われる。

謝辞

後ろからソルトを付けた際に危険になる場合については、@herumiさんから情報を頂いた。

例えば衝突困難性が破られたMD5でH(m||k)を使うと意図しない認証をしてしまう可能性（https://t.co/wuQ8adA83I）がありますがHMAC-MD5なら今のところまだ大丈夫（なはずhttps://t.co/NYePTKpaJu）という違いがあります。@_yyu_
— herumi (@herumi) 2016年3月3日

参考文献

この記事でのメッセージとは、適当な文字列という意味である。 ↩

ソルトとハッシュ関数だけでパスワードをハッシュ化するのが微妙な理由