パスワードの保存に SMD5 (Salted MD5) や SSHA1を使う (MD5 への辞書攻撃とか)

ブログが続かないわけ - MD5は復号できる!?という記事を読んだ。

MD5でハッシュ化されたデータを持っているオンラインデータベースがあって、そこに問い合わせると。。。

MD5 は一方向性ハッシュ関数というもの。詳しくはPKI関連技術に関するコンテンツ - 2.3 セキュアハッシュ関数を参照。 これを使えば8文字のパスワードであっても1GBの動画ファイルであっても、16バイトのバイト列に変換してくれる。 特に、変換後の値から元の値を推測できないことが特徴。 例えば、「hatsunemiku」というパスワードのMD5でのハッシュ値は以下のようになる。

MD5.hexdigest('hatsunemiku')
=> "3523fe5f96966420a1950e514dcc7413"

DBにユーザのパスワードをそのまま保存するのではなくて、ハッシュ値を保存すればいいよねというのが、ブログが続かないわけ - パスワードを平文で管理するのはダメだという話。 もちろん、ハッシュ値から元の値には戻せないので、認証するときにはユーザが入力したパスワードからハッシュ値を生成してDB上のハッシュ値と比較する。

digest = "3523fe5f96966420a1950e514dcc7413"   ← 実際にはDBに格納されている値
password = "hatsunemiku"  ← 実際にはユーザが入力した値

if (MD5.hexdigest(password) == digest) {
  puts "認証成功"
}
else {
  puts "認証失敗"
}

それに対して、id:yappoさんのブクマで「Digest::MD5::Reverseでふくごうかでkiruyo」というコメントがあった。 md5.rednoize.comのようなハッシュ値から元の値を返すようなサービスがあって、Digest::MD5::Reverseはそれを呼び出しているみたい。 ってことで、試しに使ってみた。

#!/usr/bin/env perl
use Digest::MD5::Reverse;
print "Data is ".reverse_md5("3523fe5f96966420a1950e514dcc7413")."\n";

結果は以下のとおり。ハッシュ値から元の値が得られている。

Data is hatsunemiku

仕組みは単純で、よく使われている単語を片っ端からハッシュ値に変換して、両者の対をDBに保管しておくだけ。 こうすればDBに保管されているハッシュ値であれば、元の値に一瞬で変換することができる。 こういう攻撃を辞書攻撃という。 辞書攻撃のツールは過去にもあったんだけど、オンラインで公開することで辞書の単語を増やせるのが新しい。 だから、辞書に登録されていないハッシュ値だと元の値を得ることができない。 試しに"0617aa21677dec3869fdc70f38947cd3"という値 (hatsunemiku2007のハッシュ値) を入れてみたけど、元の値は出力されなかった。 ちなみに、今は元の値を得られると思う。さっき登録したから。

辞書攻撃とパスワードの長さ

辞書攻撃は古くからある攻撃。 うろ覚えだけど、カッコウはコンピュータに卵を産むという本に UNIX パスワードを盗む攻撃としてでていた気がする。 当然、対策もちゃんと考えられている。

セキュリティを考えるときは、「誰から何を守るのか」が大切なので、まずはそこから整理。

• 誰から … DBに格納されている（暗号化もしくはハッシュ化された）パスワードを入手した攻撃者から
• 何を守るか … ユーザのパスワードを特定されることを防ぐ

攻撃側がなぜ事前に辞書を作るかというと、大量のハッシュ値を計算するのに時間がかかるから。 例えば、1秒間に1万種類のハッシュ値を計算できるとしても、小文字だけのアルファベット6桁のパスワード（約1億通り）のハッシュ値を計算するのには1万秒（約3時間弱）かかる。 パスワードに大文字と小文字の両方を使うと組み合わせが増える（約120億通り）ので、計算にもさらに時間がかかる。 だったら事前に計算しておこうって訳。

もちろん、パスワードの桁数が増えれば増えるほど、辞書を作るのにも時間がかかる。 仮にパスワードの桁数が100万桁だとすると、事前にすべての文字の辞書を作ることは実質的に無理になる（時間が足りない）。 100万桁は大げさだけど、どこかに事前に計算できなくなるしきいがあるのは確か。 とはいえ、長いパスワードをユーザが覚えるのは現実的じゃない。

辞書攻撃対策としてのSMD5 (Salted MD5)

ってことで登場するのが salt という仕組み。 聞きなれない言葉かもしれないけど、仕組みはいたって簡単。 パスワードからそのままハッシュ値を計算するんじゃなくて、「パスワード＋ランダムな文字列」からハッシュ値を計算する。以下は salt を使った例。 SMD5 そのものじゃない。

(1) パスワードの登録

salt = "Hscl4BsP" ← ランダムに生成した文字列
digest = MD5.hexdigest(password + salt)  ← パスワード＋saltのハッシュ値

(2) ユーザの認証

salt = "Hscl4BsP" ← (1)で生成した文字列
digest = "545e41d7f85faf3b816321d76ada4c87"  ← 実際にはDBに格納されている値
password = "hatsunemiku"  ← 実際にはユーザが入力した値

if (MD5.hexdigest(password + salt) == digest) {
  puts "認証成功"
}
else {
  puts "認証失敗"
}

冒頭の例と比べると分かるけど、パスワードにsaltというランダムな文字列を加えている以外は同じになる。 パスワードだけだと辞書に登録されるとアウトだけど、ランダムなsaltを加えればすべてのsaltを含めた辞書を作るのはとても難しくなる。saltが十分に長ければ現実的に無理。

ポイントは以下のとおり。

• salt はパスワードごとに別に生成する。同じ salt を使いまわさないこと。（saltが固定値ならそのsaltで辞書が作られてしまう）
• salt はハッシュ値と一緒に保存しておく。仮に salt とハッシュ値が攻撃者に盗まれても辞書攻撃「は」受けない。（すべてのsaltに対する辞書を用意できないため。）
  • salt を一緒に保存するのはパスワードの照合時に利用するため

逆にsaltを使っても防げないことがある。

• 利用者が容易に推測できるパスワードを登録した場合。攻撃者はsaltとハッシュ値を知っているので、いくつか目星をつけてパスワード + salt のハッシュ値をその場で計算することが可能になる。（これは辞書攻撃とは違う攻撃）
  • ここまで防ぎたいのであれば、DBを暗号化して、暗号鍵を安全なところに保管するしかないかも。これでもログイン画面から攻撃されたらアウトだけど。

この salt とハッシュ関数を組み合わせる方法として、 SMD5 (Salted MD5) や SSHA1 (Salted SHA1) という。 Ruby での実装は ActiveLdap::UserPasswordがあるし、 PukiWikiでの管理者パスワードの保存にも使われている。ActiveLdap の実装は以下のようになってた。

    def ssha(password, salt=nil)
      if salt and salt.size != 4
        raise ArgumentError.new("salt size must be == 4")
      end
      salt ||= Salt.generate(4)
      sha1_hash_with_salt = "#{SHA1.sha1(password + salt).digest}#{salt}"
      "{SSHA}#{Base64.encode64(sha1_hash_with_salt).chomp}"
    end

その他の参考資料は以下の通り。

• 入門LDAP認証（２） P.137〜 (PDF)
• Password Digest support with Cams … オンラインでのSMD5値の生成サンプル

ちなみに一年前の日記で紹介した tDiary 用フォーム認証プラグインでも、パスワードに salt を付ける実装にしていた。saltが digest plain の前にあるので、今見るとあまりよくない実装だけど。

digest = Digest::MD5.hexdigest(salt + plain)
"#{salt}:#{digest}"

※ 追記 … id:kazuhookuさんより、「saltを攻撃側が指定できないから順番は関係ないんじゃないかな」とのコメントをいただいた。詳しくはハッシュの salt はメッセージの前？後？に書いた。

ちょっと気になること

元のエントリのはてなブックマークを見ていると、ハッシュの「衝突」と話が一緒になっている気がする。

これは復号とは呼ばないけどコリジョンするデータを見つけられるようだ

コリジョンを見つけるのは結構楽ですよという話だよね。

息切れしてきたので、以下箇条書きで。

• ハッシュの衝突は、「違う2つの値」から同じハッシュ値を求めること
• 辞書攻撃は、事前に計算しておいたハッシュ値と元の値のペアのリストを使って、ハッシュ値から元の値を求めること

ちょっと前に話題になった MD5 の衝突発見の話は辞書攻撃とは無関係。 それに、どんなに安全なハッシュ関数 (SHA1, SHA256...) を使ったとしても辞書攻撃を防ぐことはできない。 攻撃者は正規の手順に従って事前にハッシュ値を計算しているだけであって、ハッシュ関数自体の脆弱性に攻撃している訳じゃないから。

話が変わって、以下はいや、復号はできないでしょう : ひろ式めもちょうから引用。

f(a) = f(b) となる別のデータ：b を出してくると（※もちろんa=bの可能性もある）。

辞書攻撃の場合、基本的にはa=bのはず。パスワードに使うような文字列でa!=bってのはない気がする。

秘密の文字列s（漏れないことが前提）を用意して f(a+s) を保存しておくようにすれば、仮にf(a+s)が通信経路などからバレ、汎用のデータベースからf(a+s)=f(b)となるbを抽出して認証に使われたとしても、

・f(b+s)を算出

・f(a+s)≠f(b+s)なので認証失敗

ということになる。

うーん。分かるような分からないような。

• sを漏れないようにできるなら、f(a+s)も漏れないようにできる気がする*1。
• 「f(a+s)=f(b)となるbを抽出」というのも攻撃方法として現実的じゃない。
  • MD5でも弱衝突耐性は破られていない

sじゃなくてf()を単純なMD5でない（MD5以上に信頼できる）関数f'()にしても可。ハッシュの表が用意されていなければいい。

辞書攻撃はハッシュ関数自体への攻撃じゃないので、ハッシュ関数自体の信頼性とは関係ないはず。 それに、MD5以上に信頼できるハッシュ関数なら、おそらく辞書（ハッシュの表）は用意されるんじゃないかな。

これも一つの考え方だと思うけど、SMD5やSSHAのように、sもf(a+s)も漏れる前提で考えたほうが安全じゃないかな。 この考え方は、どちらかというと暗号鍵を使ってデータベースを暗号化する考えに近い気がする。

MD5の復号？

復号というと正規の手順を踏んだものを指すようなので、解読のほうがいいかも。ハックっぽいし。