K.Maebashi's BBS

PHPとMySQLで掲示板を作る / 削除 / 削除系ソース の hash_user_password() ですが、"秘密" は、 UNIX パスワードなどで使われている salt の やり方にするのはどうですか？ つまり、"秘密" はソース埋め込みにせず、メッ セージごとに乱数で生成することにし、salt 自体も message表に記録しておくわけです。 今のやり方だと、仮に異なるユーザが同一のパス ワードを利用していた場合、その事実を管理者は 知ることができるわけですが、salt を使えばその 心配もありません。 また、仮に "秘密" や salt が洩れた場合に、辞書 攻撃への耐性が若干高くなります。(salt があると、 同じ辞書は一つのメッセージにしか使えないため、 探索空間が広くなる)

>つまり、"秘密" はソース埋め込みにせず、メッ >セージごとに乱数で生成することにし、salt 自体も >message表に記録しておくわけです。 毎度ながらご指摘ありがとうございます。 掲示板のパスワードとしてどこまでの仕様が必要であるかはさておき、 この記事を読んで「パスワードの暗号化はこうすれば万全なんだ」と思ってしまう人が いるとまずいので、取り急ぎ注釈をつけました。

すみません、風呂の中で考えてたらちょっとわからなくなりました。 >今のやり方だと、仮に異なるユーザが同一のパス >ワードを利用していた場合、その事実を管理者は >知ることができるわけですが、salt を使えばその >心配もありません。 これはその通りだと思います。また、クラッカーにD/Bを継続的に監視されて いる場合、いろいろなパスワードで書き込んでみることで、パスワードを 推測することもできることになります。 >また、仮に "秘密" や salt が洩れた場合に、辞書 >攻撃への耐性が若干高くなります。(salt があると、 >同じ辞書は一つのメッセージにしか使えないため、 >探索空間が広くなる) これですが、辞書攻撃を、Webで稼動中の掲示板に対して行うことを想定して いますでしょうか。それとも、既にテーブル内容が流出していることを 前提に、辞書攻撃でパスワードを解析しよう、というお話でしょうか。 前者だとすると、"秘密"やsaltが漏れていようがいまいが関係なさそうですし (そもそもレンタルサーバ業者にプロセス止められそうですが)、 後者だとすると、テーブルが流出した時点でsaltはだだ漏れです。 別の場所に置いてあるだけ"秘密"の方がまだマシかも。 >同じ辞書は一つのメッセージにしか使えないため、 >探索空間が広くなる) これは、ひとつのパスワードがばれても、同じハッシュになっている他の パスワードが芋づる式にばれることはない、ということでしょうか? しかし、実際問題こんな掲示板の投稿が消されてもさしたる実害はないわけで、 問題は「お金が絡むようなところと共通のパスワードを使う人がいたケース」だと 思っています。 そんなユーザは投稿ごとにパスワードを変えたりしそうにないですし(そんな ユーザに限らずともそうなんじゃないかと思いますが)、同一ハンドルの人は 1回しか調べない、程度のことで、同時間で、ほぼ同数のパスワードが抜かれて しまいそうに思うのですが。 どちらが安全か、という問題以前に、まず私の認識は合ってますでしょうか?

> これですが、辞書攻撃を、Webで稼動中の掲示板に対して行うことを想定して > いますでしょうか。それとも、既にテーブル内容が流出していることを > 前提に、辞書攻撃でパスワードを解析しよう、というお話でしょうか。 テーブル内容が流出していることを前提にしています。 > 後者だとすると、テーブルが流出した時点でsaltはだだ漏れです。 そうです。 > これは、ひとつのパスワードがばれても、同じハッシュになっている他の > パスワードが芋づる式にばれることはない、ということでしょうか? 違います。辞書攻撃に必要な計算量が増えるという意味です。 > 同時間で、ほぼ同数のパスワードが抜かれてしまいそうに思う > のですが。 salt があると、探索空間が salt のビット数分広がるため、 辞書攻撃に要する時間が長くなります。以下のページにも、 同様な示唆があります。 http://www.itmedia.co.jp/enterprise/0307/24/epn09.html http://www.microsoft.com/japan/msdn/library/ja/f_and_m/html/vxconprotectingpasswordcredentials.asp データベース中には複数のMD5化されたパスワードが存在する わけですが、salt がないと、単一の辞書を使って、全ての パスワードに対する試行を行うことができます。これに対し、 salt があると、2 の salt のビット数乗 の辞書が必要になる わけです。 > 別の場所に置いてあるだけ"秘密"の方がまだマシかも。 これを気にするのであれば、salt とプログラム埋め込みのsecret の両方を使うのが良いと思います。どちらか片方だけであれば、 salt の方を選ぶのが良い習慣だと思います。

なんだかすごく初心者な発言をしている気がしますが、聞くは一時の恥ということで。 >データベース中には複数のMD5化されたパスワードが存在する >わけですが、salt がないと、単一の辞書を使って、全ての >パスワードに対する試行を行うことができます。これに対し、 >salt があると、2 の salt のビット数乗 の辞書が必要になる >わけです。 つまりこういうことでしょうか。 ・パスワード候補となりうる文字列に「秘密」を連結し、MD5ハッシュ値を算出する。 　大量の文字列に対してこれを行い、辞書を作る。 ・辞書が何らかの記憶媒体に載るとしたら、ハッシュ値がばれればパスワードもばれる。 　ハッシュ値の方から逆引きできるようなしかけにしておけば一瞬。 ・辞書を作るにはひとつのパスワードを抜くのと同じ計算量が必要だけど、 　「秘密」方式では、その計算量で、全てのパスワードがばれる。 うーん、でも、 >salt があると、探索空間が salt のビット数分広がるため、 saltがばれてる状態では、「探索空間が salt のビット数分広がる」ことはない ように思いますが…まだ何か勘違いしてますでしょうか。 >これを気にするのであれば、salt とプログラム埋め込みのsecret >の両方を使うのが良いと思います。どちらか片方だけであれば、 >salt の方を選ぶのが良い習慣だと思います。 両方使うようにして、今までの分はsaltを空文字にしておけば、 今までの投稿については、以前のパスワードが変わらず使えるかなあ、と 一瞬考えたのですが、D/B流出の時にパスワードがばれる危険性を考えて いるのだからそれじゃ本末転倒ですね (^^; 今までの投稿が削除できなくなってもおそらく誰も困らないでしょうから (いまさら「しくじったので書き直し」はないでしょうから)、今度時間が できたときに修正しておきます。

> saltがばれてる状態では、「探索空間が salt のビット数分広がる」 > ことはないように思いますが…まだ何か勘違いしてますでしょうか。 D: 辞書のサイズ S: salt のビット数 N: ユーザ数 M: メッセージ数 とします。 ここで、一つのMD5ハッシュ値から辞書を引いてパスワードを得るコスト を O(1) とします。 また、異なるメッセージであっても、同一ユーザーは同じパスワードを 使い回すと仮定します。 なお、2^S は、M より有意に大きいため、ほぼ全てのメッセージについて、 異なる salt が使われているものとします。 ここで、salt なしの場合、辞書作成に必要なコストは O(D)、辞書攻撃に 必要なコストは O(N) です。 では、salt ありの場合は、どうでしょう。 全てのありうる salt に対して辞書を作成するのに必要な計算コスト および記憶コストは O(D * 2^S) ですが、これは S が十分大きければ (例えば S=64) 計算量的にも、あるいは記憶容量的にも実現不能になります。 従って、あらかじめ辞書を記憶媒体に作成するのは不可能で、全ての メッセージについて、試行するしかありません。 これに要する計算コストは、O(M*D) となり、M が大きければ、 O(N) や O(D) よりも有意に大きな値になります。 すなわち、Sとして十分大きなビット数を用いると、辞書攻撃に必要な 計算量が、min(M*D/N, M*D/D) == min(M*D/N, M) 倍程度になるわけです。

> また、異なるメッセージであっても、同一ユーザーは同じパスワードを > 使い回すと仮定します。 この仮定は本質的ではないので、N==M とおいて、 Sとして十分大きなビット数を用いると、辞書攻撃に必要な計算量が、 min(M*D/M, M*D/D) == min(D, M) 倍程度になるわけです。 と書いた方が分かりやすかったですね。

>従って、あらかじめ辞書を記憶媒体に作成するのは不可能で、全ての >メッセージについて、試行するしかありません。 >これに要する計算コストは、O(M*D) となり、M が大きければ、 >O(N) や O(D) よりも有意に大きな値になります。 納得しました。計算量はM倍ですよね。 うちの掲示板ではMがそんなに大きくないので、「全てのsaltに対応する 辞書を作成する」というのが現実的と思えず、「探索空間が salt のビット数分 広がる」のところで混乱していました。 丁寧な説明ありがとうございました。

>>これを気にするのであれば、salt とプログラム埋め込みのsecret >>の両方を使うのが良いと思います。どちらか片方だけであれば、 >>salt の方を選ぶのが良い習慣だと思います。 > >両方使うようにして、今までの分はsaltを空文字にしておけば、 >今までの投稿については、以前のパスワードが変わらず使えるかなあ、と >一瞬考えたのですが、D/B流出の時にパスワードがばれる危険性を考えて >いるのだからそれじゃ本末転倒ですね (^^; > >今までの投稿が削除できなくなってもおそらく誰も困らないでしょうから >(いまさら「しくじったので書き直し」はないでしょうから)、今度時間が >できたときに修正しておきます。 ほとんど文脈無視ですが_o_、salt として本文を使うってのはどうですかね？ 管理者による本文の修正は出来なくなりますけどね。

>ほとんど文脈無視ですが_o_、salt として本文を使うってのはどうですかね？ むにゃ。もう直しちゃいましたし (^^; saltとして本文を使うということは、D/B流出がなくてもsalt漏れまくり、 ということですから、秘密の文字列を併用しなければだめでしょうけど、 それ前提なら使える手かとは思います。 でも、複数の投稿に同じsaltが振られる可能性がそこそこありますし、 別にフィールドを増やすことは可能なので、本文を使う必然性はないですよね。