«前の日記(2007-10-24 (水)) 最新 次の日記(2007-10-26 (金))»  

まちゅダイアリー


2007-10-25 (木)

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

さっきの日記の続き。 ハッシュ値を使ってパスワードを管理する場合は、事前にパスワードとハッシュ値のペアを計算しておくという辞書攻撃ができた。 これは、同じパスワードから同じハッシュ値が得られることを利用している。 なので、同じパスワードから違うハッシュ値が得られれば辞書攻撃への対策になる。 この目的で使うのが SMD5 (Salted MD5) や SSHA1 (Salted SHA1) などの salt 付きハッシュ関数。

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

データベースはこうなる。(長くなったので折り返して表示してる)

ユーザパスワードデータベース(ハッシュ値)データベース(salt)
Amikkumiku75cebe1fab49726d
b7b3fcd1664c572b
b5f44b8ac1c701b2b0ee
0baed4701fba403877a8
Bmikkumiku335902b9ea85629d
fdcd4fd21790e9c6
132e55aa5f41f2b87212
450aa32b4d5c357c5417
Czawazawa15fe2ab7ce4fa5f0
ca02b3d564b92756
78422f62841b2fcb916c
512c86465c048e93361c

AとBは同じパスワードを使っているのに、ハッシュ値が別の値になっていることに注意。 これは、パスワードからそのままハッシュ値を計算するのではなく、パスワードとランダムに生成したバイト列を繋げてからハッシュ値を計算しているから。

  • MD5 … パスワード → ハッシュ値 (同じ値になる)
  • SMD5 … パスワード+ランダム値 (salt) → ハッシュ値 (ランダム値が変われば別の値になる)

ランダムなバイト列を加えることで元の値が変わるので、生成されるハッシュ値も変わるという訳。 このランダムに生成したバイト列のことを salt (塩) という。 そして、 salt と MD5 を組み合わせることを SMD5 (Salted MD5) という。

ここでのポイントは2点。

  1. salt はハッシュ値と一緒にデータベースに保存する (パスワードとハッシュ値の比較にはsaltが必要なため)
  2. salt はユーザごとに別の値を使う (同じ値を使うとハッシュ値も同じになる)

ちなみに、cafesoft.comでパスワードから salt 付きハッシュ値の計算ができる。 何度か同じパスワードを入れても違う salt とハッシュ値が出てくるので、試してみるといいかな。

SMD5 でハッシュ化したパスワードへの攻撃

攻撃する人がデータベースからハッシュ値と salt を取得できたとする。 さっきのハッシュ化したパスワードへの攻撃と同じように、全てのパスワードと全ての salt の組み合わせを計算すれば、同じようにハッシュ値からパスワードを推測することができる。 でも、 salt を使わない場合とは異なり、 md5.rednoize.com のように事前にパスワードとハッシュ値のペアを収集するためには、1つのパスワードに対して全ての salt の組み合わせを計算する必要がある。

この、「全ての salt の組み合わせ」というのがとてもやっかい。 例えば「mikkumiku」というパスワードのハッシュ値を計算する場合に、 salt が無ければ1回ですむ計算が salt の数だけ計算しないといけない。 さっきの例では salt の長さが20バイト (160bit) なので、1つのパスワードに対して2の160乗回の計算が必要になる。

別の言い方をすると、 SMD5 を使うことの本質は、「時間稼ぎ」に過ぎないってことになる。

でも、「時間稼ぎ」というのは防御の上でとっても大切な考え。 ドアや自転車に鍵を2つ付けるのも「時間稼ぎ」のためだからね。 パスワードの解読に1000年かかるのなら、実質的に安全と考えていい。

そして一番大切なことは…

SMD5などの鍵付きハッシュを使うことで、「ハッシュ値からパスワードを知る」ことが難しくなる。 でも、だからと言って安心しちゃいけない。

一番大切なのは、「安易なパスワード」を使わないということ(これが一番難しいんだけど)。 今回の例に挙げた「hatsunemiku」のような安易なパスワードを使っているんだったら、わざわざハッシュ値から計算するまでもなく、正規のログイン画面にIDとパスワードを入れてログインできるかどうかを試せばいいんだから。

追記

salt が入手できた場合でも「パスワードと全ての salt の組み合わせの計算」が必要と記述していた誤りを修正しました。 id:ihagさん、id:kazutanakaさんご指摘ありがとうございます。

Tags: security memo