PSN個人情報流出事件における「パスワードのハッシュ化」ってなんぞ？

プレイステーションネットワーク(PSN)の個人情報流出事件で、

「パスワードは暗号化されていなかったがハッシュ化はされていた」

なる報道があったので、暇つぶしにハッシュについて書いてみる。

「ハッシュ」とは、ハッシュ関数を用いて、データをある一定の値域にマッピングする技術です。（んにゃ？）
えっと、PSNの場合、不可逆（元にに戻せない）なパスワードの要約を得るために使用されています。

例えば、あるアルファベット6文字について、以下のルールを設定します。

「aを0、bを1・・・zを25に置き換えて、そのすべて足す。」

このルールが「ハッシュ関数」となります。

このハッシュ関数を用いれば、すべてのアルファベット6文字は0(aaaaaa)〜150(zzzzzz)のどこかにハマる事になります。
この0〜150が「ハッシュ値」となります。

試しに文字列mogunoに、このハッシュ関数を適用してみます。

12(m) + 14(o) + 6(g) + 20(u) + 13(n) + 14(o) = 79

よって、mogunoのハッシュ値は79となります。

ここまでを押さえておいて、パスワードの暗号化に話をずらします。

PSNみたいなサービスにパスワードを登録する際、サービスはパスワードのハッシュ値を計算して、ハッシュ値のみをサーバに保存します。

サービスにログインする際には、サービスは入力されたパスワードのハッシュ値を計算して、それをサーバに保存していたハッシュ値と比較して、パスワードが妥当かを確認します。

もしもサーバをクラッキングされたとしても、サーバに保存されているハッシュ値はパスワードの「不可逆な要約」なので、そこからパスワードを得ることは出来ません。

しかしながら、このハッシュ値による方法は完ぺきではありません。

第一に、ハッシュ関数がクラッカーにバレてしまうと、総当り攻撃によりパスワードを推測される可能性があります。
例で挙げた6文字のアルファベットの場合、aaaaaa〜zzzzzzの308915776通り（アルファベット26通り^6文字（^は累乗の記号））をハッシュ関数に入力すれば、必ずサーバに保存されたハッシュ値と同じ値になる文字列にたどり着くことが出来ます。
最近の計算機であれば一瞬でしょきっと。

この問題については、「salt」と言うサーバで決めた値をハッシュ関数に加えることで、ある程度対応可能です。

「aを0、bを1・・・zを25に置き換えて、そのすべて足した値にさらにsaltを掛ける。」

これで、ハッシュ関数とsaltの両方が盗まれない限り、パスワードに対応するハッシュ値を求めることは困難になります。

（2012〜2013年に起きたPC遠隔操作連続えん罪事件で使われたウイルスには「saltは必ず8バイト以上」と言うsaltが使われていた様です。バイナリファイルを軽くダンプすればsalt値がこれだとバレバレなので、あんまり意味がないですね。）

第二に、「シノニム（衝突）」の問題があります。
例えばさっきのハッシュ関数では、mogunoとonugomとmmmmmtのハッシュ値は同じ79になります。
この様な異なる元データから同じハッシュ値が得られる現象を「シノニム（衝突）」と呼びます。

仮にこのハッシュ関数をサービスのログインに使用してしまうと、設定したパスワードではないmmmmmtでもログインが成功してしまいます。
また、総当り攻撃でシノニムを含む有効なパスワード文字列を得るまでの時間がぐんと短くなってしまいます。

対策としてはハッシュ値が取りうる範囲が十分大きく、極力シノニムが発生しない関数を採用することです。

まぁ、偉い人達が色々考えてはるので、後はWikipediaとか読んでいただければね。