«前の日記(2007-10-23 (火)) 最新 次の日記(2007-10-25 (木))»  

まちゅダイアリー


2007-10-24 (水)

SMD5 をもう少し分かりやすく説明してみる (1)

昨日の日記で SMD5 (Salted MD5) を使ったパスワード管理について書いたけど、話が行ったり来たりしている気してきた。 もう少しシンプルに書いてみよう。

パスワードを平文で管理した場合

こうなる。

ユーザパスワードデータベース(平文)
Apasswordpassword
Bmikkumikumikkumiku
Czawazawazawazawa

さすがにこれは論外。 管理者が以下のSQLを実行すれば全ユーザのパスワードが入手できる。 SQLインジェクションで狙われても同様。

> SELECT userid, password FROM users;
|userid|password|
|A|password|
|B|mikkumiku|
|C|zawazawa|

パスワードを暗号化して管理した場合

こうなる。

ユーザパスワードデータベース (暗号化されたパスワード)
Apassword********
Bmikkumiku********
Czawazawa********

※ 暗号鍵はWebアプリ内に保存されている

平文でそのまま管理するよりはマシだけど、復号用の鍵(暗号鍵)は必ずWebアプリが持っている。 なので、暗号鍵と暗号化されたパスワードの両方が手に入れば、全ユーザのパスワードが入手できる。

パスワードを MD5 でハッシュ化して管理した場合

こうなる。

ユーザパスワードデータベース (パスワードのハッシュ値)
Apassword5f4dcc3b5aa765d61d8327deb882cf99
Bmikkumiku035b892e125ccd54e15d412ef9502742
Czawazawaf69778ec833f747464d497f67a90042f

パスワードからハッシュ値は生成できるけど逆はできない。 当然、元に戻す鍵も存在しない。 なので、パスワードのハッシュ値を得られたとしても、そのままではユーザのパスワードは分からない。 と、ここまでが「ブログが続かないわけ - パスワードを平文で管理するのはダメだ」に出てきた話。

ハッシュ化されたパスワードへの攻撃

パスワードのハッシュ値を得られた場合に、そこから元のパスワードを知る方法を考える。 例えば、AさんとBさんが同じパスワードを使っていた場合のデータベースはこうなる。

ユーザパスワードデータベース (パスワードのハッシュ値)
Amikkumiku035b892e125ccd54e15d412ef9502742
Bmikkumiku035b892e125ccd54e15d412ef9502742
Czawazawaf69778ec833f747464d497f67a90042f

パスワードが同じであればハッシュ値も同じになるので、AさんがBさんのハッシュ値を知ることができれば、Bさんのパスワードが自分のパスワードと同じ(mikkumiku)だと分かってしまう。

これを応用する。 ハッシュ値の計算は誰でもできるので、ローカルでハッシュ値を計算してデータベースのハッシュ値と比較すればいい。 必ず成功する方法は、「全ての文字の組み合わせ」に対してハッシュ値を計算してみること。

パスワードの候補ハッシュ値
::
mikkumiki9bf57558c782f555adf429b0d05cf574
mikkumiku035b892e125ccd54e15d412ef9502742
mikkumike4f42579ced52c98d3a501065bce03ae0
::

いつかは「mikkumiku」という文字をハッシュ化して「035b892e125ccd54e15d412ef9502742」を得られるので、ハッシュ値が「035b892e125ccd54e15d412ef9502742」であるユーザBのパスワードが「mikkumiku」だと分かる。 これが総当り攻撃。 でも、パスワードの文字数が長くなると、例えば総当りに10年かかるようになってしまう。 そこで、良く使いそうなパスワードだけを選んでハッシュ値を計算すればより時間が短くなる。これが辞書攻撃*1

さらに、元の値が同じであれば必ず同じハッシュ値になるので、一度計算したハッシュ値を保存しておけば二度と計算する必要が無くなる。 例えば10年かけてひたすらハッシュ値を計算すれば、かなりの数のパスワードとハッシュ値のペアが入手できる。 ハッシュ値の収集をオンラインでやっているのがmd5.rednoize.comのようなサービスで、それをPerlモジュールとして利用できるようにしたのがDigest::MD5::Reverse。 ちなみに、md5.rednoize.comにさっきのハッシュ値を入れてみたら、「password」と「mikkumiku」は取得できた。「zawazawa」のハッシュ値 (f69778ec833f747464d497f67a90042f) は登録されていなかった。

ここまでが「ブログが続かないわけ - MD5は復号できる!?」の話。 この辞書攻撃への対策がSMD5 (Salted MD5) になる。

補足

ハッシュ値の計算に使うアルゴリズムを変える (例えばMD5の代わりにSHA1を使う) と、生成されるハッシュ値は別の値になる。 でも、そのアルゴリズムでハッシュ表を計算されたら、やっぱり辞書攻撃はできてしまう。 なので、「MD5やSHA1の代わりにSHA2を使いましょう」ということと、辞書攻撃を防ぐことは直接的には関係ない話。

Tags: memo security

*1 総当り攻撃や辞書攻撃はハッシュ値への攻撃以外でも使われる。鍵付きZIPの解読とか。