ストレッチング

質問

こんにちは。

今日、パスワードに関する記事を読みました。
パスワードというのは平文で保存しないで、代わりにハッシュ関数を施した値を保存して、これらの値が漏えいしても元のパスワードが解読されないようにしているみたいです。そして「ストレッチング」というのは、このハッシュ計算を何回も施した値を保存するのだそうです。

そこで、質問です:
パスワードの保護に関して「十分に安全なハッシュ計算」（そういうモノがあるとして）の冪乗は、再び「十分に安全なハッシュ計算」になるのでしょうか。

よろしくお願いします。

回答No.3

日吉 龍（@VDSL） · ベストアンサー

再び#1です。

私は文学部出身の人間で数式には滅法弱いので、私が理解できた範囲について補足させて頂きます。

> 元々パスワードの代わりにハッシュ値を保存すると、正しいパスワードとは異なる値を入力しても解錠してしまうという危険がありますが、それが増大したり…などで、安全性が低下したり（ほとんど役立たずになったり）することはないのか、突破に要する計算量の理論上の下限という意味では弱くなっていることもあるのではないか、という疑問です。

たとえば、参考に挙げて頂いたURLのように、f^10,000(x)の結果をyとして保存した場合、任意の入力値xについてf^n(x)を計算した結果、偶然yという出力を得る(= 衝突が発生する)可能性は確かにありますし、nが増加すれば増加するほどn回未満の試行で衝突が発生する可能性は確かに高くなります。

しかし、仮に10,000未満のn回目で衝突が発生するようなxを発見できたとしても、パスワードを保存しているサーバはプログラムに従って必ず10,000回計算を行います。このため、正確にnが10,000の時にyとなるxを求めないことには、攻撃に成功した(= パスワードを突破した)ことになりません。n回未満のどこかではなく、正確にn回目で衝突が発生するような、本来のxとは異なるxが出現する可能性は、nが増加すればするほど低くなるはずです。

また、仮に将来的に任意のyに対応するxを求める方法が発見されたとしても(現在利用されているハッシュアルゴリズムでそのようなものはありませんが)、nが増加すればするほど攻撃に要する時間も増加するので、安全性は高まっているといえるのではないでしょうか。なお、

> もし、弱くならない（or 強くなる）のであれば、ｆ, ｆ^2, ｆ^3, …と無数に安全な（or より安全な）ハッシュ関数が得られてしまうというのが最初の違和感がでした。

ですが、nが大きくなればなるほど安全になるのが事実だとしても、計算にかけられる時間は有限なので、実際の実装は要求される安全性と処理時間とのトレードオフになります。たとえば、オンラインバンキングのパスワードを格納するのであれば、n = 10,000とするのも非現実的ではありませんが、流出して困るような情報が一歳存在しない社内の検証サーバのnを10,000に設定するのは、守るべき情報の価値を考えると過剰といえるでしょう。

参考 : ハッシュの衝突耐性について
http://ja.wikipedia.org/wiki/MD5#.E3.83.8F.E3.83.83.E3.82.B7.E3.83.A5.E3.81.AE.E8.A1.9D.E7.AA.81.E8.80.90.E6.80.A7.E3.81.AB.E3.81.A4.E3.81.84.E3.81.A6

補足

> ですが、nが大きくなればなるほど安全になるのが事実だとしても、計算にかけられる時間は有限なので、
>
いいえ。jmh は「再び十分に安全ですか」と疑いを持っています。逆に「ｎが大きくなればなるほど脆弱になっていくのではないですか」と質問しています。

回答No.2

日吉 龍（@VDSL）

こんにちわ、#1です。

> つまり、ストレッチングに関しての「安全」という言葉の意味は単に「ｆの逆計算表は既に知られていても、ｆ^n の逆関数は未だだから」ということでしょうか？

f = ユーザがパスワードとして設定する文字列の長さの方が、f^n = fをハッシュ関数にかけた結果として得られる文字列よりも圧倒的に短いということはお分かりかと思います。極端な話、f^n以上の長さの文字列を要求するシステムが仮に存在したとすれば、"fの逆計算表はすでに知られている"という前提が覆されますし、f^nすると逆に脆弱になってしまいます。

なお、ストレッチングの方法としては、ランダムなsaltと呼ばれる文字列(本文最後のURLをご覧ください)をユーザが設定した文字列に追加してハッシュ化する方法の方がメジャーです。

なので、ストレッチングに関しての「安全」という言葉が意味するところは、"ユーザが設定したオリジナルのパスワードの文字列を意図的に長くする(引き延ばす)ことにより、逆計算表を利用できなく(もしくは、総当たり攻撃を著しく困難 = 事実上不可能に)なるため、安全である"ということだと個人的に思います。
＃stretch = "引き延ばす"という意味の動詞ですし。

余談ですが、f^nの逆計算表が作成されるほどにコンピュータが進化したら、より長いハッシュを出力するハッシュ関数が利用されるようになるでしょう(つまり永遠のいたちごっこです)。

ソルトについての解説 :
http://ja.wikipedia.org/wiki/%E3%83%91%E3%82%B9%E3%83%AF%E3%83%BC%E3%83%89%E3%82%AF%E3%83%A9%E3%83%83%E3%82%AF#.E3.82.BD.E3.83.AB.E3.83.88

お礼

しばらく、お休みしてました。申し訳ないです。

しかし少し疑問が解けたような気がします。今日、wikipedia の「暗号学的ハッシュ関数」を読み直したら、
>
> 暗号学的ハッシュ関数は『既知』の全暗号攻撃法に耐性がなければならない。
> 少なくとも、…
>
とありました (『』は jmh)。何度も読んだハズなのに気付かなかったです。「既知の」とハッキリ書いてありました 。

http://ja.wikipedia.org/wiki/%E6%9A%97%E5%8F%B7%E5%AD%A6%E7%9A%84%E3%83%8F%E3%83%83%E3%82%B7%E3%83%A5%E9%96%A2%E6%95%B0

「原像計算困難性」「第2原像計算困難性」「衝突困難性」の「困難性」というのは、これらの「既知の攻撃方法」による困難性を指していて、未知の攻撃方法への耐性はそもそも評価していなかったようです。wikipedia には
>
> 計算複雑性理論では「困難 (hard)」という用語は特定の意味を持つ。
> しかしここでいう「困難」は、それとはほとんど関係がない。
>
とあって、"ここでいう「困難」" が分からない…と思っていましたが、直前に書いてあったのです。

ストレッチングに対する攻撃手法は「それを再計算する以外は知られていない」のだから、元のハッシュ関数よりもずっと強いという結論になるのだと思います。

補足

ありがとうございます。自分自身の質問の意味がだんだんハッキリしてきたような気がします。申し訳ないです。

> f = ユーザがパスワードとして設定する文字列の長さの方が、f^n = fを
> ハッシュ関数にかけた結果として得られる文字列よりも圧倒的に短いということは
> お分かりかと思います。…
>
いいえ。２つのハッシュ計算法ｆとｆ^ｎ とを比較していますので、ｆとｆ^ｎ への「入力」は同じ「平文のパスワード（または＋ソルト）」です。

ｙ ＝ ｆ(ｘ) ← ｘの代わりにｙを保存します。
ｙ ＝ ｆ(ｆ(ｘ)) ＝ (ｆ^2)(ｘ) ← ｘの代わりにｙを保存します。
ｙ ＝ ｆ(ｆ(ｆ(ｘ))) ＝ (ｆ^3)(ｘ) ← …
…
ｙ ＝ ｆ(ｆ(…ｆ(ｘ))…) ＝ (ｆ^n)(ｘ) ← 入力はいつもｘです。

例えば、ｆ(ｘ) ＝ (2 * ｘ) % 16 ＝「入力値を２倍して１６で割った余り」とすると、ｆの出力から入力を求めるには少しの計算が必要ですが、ｆ^4 は定数関数＝０なので全く計算する必要がありません。つまりｆ^4 の方が少し危険に見えます。元々パスワードの代わりにハッシュ値を保存すると、正しいパスワードとは異なる値を入力しても解錠してしまうという危険がありますが、それが増大したり…などで、安全性が低下したり（ほとんど役立たずになったり）することはないのか、突破に要する計算量の理論上の下限という意味では弱くなっていることもあるのではないか、という疑問です。もし、弱くならない（or 強くなる）のであれば、ｆ, ｆ^2, ｆ^3, …と無数に安全な（or より安全な）ハッシュ関数が得られてしまうというのが最初の違和感がでした。

ちなみに、読んだのはこれだったようです:
http://blog.tokumaru.org/2013/08/1.html

回答No.1

日吉 龍（@VDSL）

こんにちわ。

要するに、"パスワードの文字列をハッシュ関数にかけた結果"と、"その値を更にハッシュ関数にかけた結果"について、安全性に違いがあるかどうかという質問ですよね。

ご存知の通り、任意のハッシュ文字列αから元の文字列を推測することは基本的に不可能です。
強引に推測する場合、元の文字列となりうる文字列を片っ端からハッシュ関数にかけて、その結果がαになるまで施行を繰り返すブルートフォース攻撃を行うことになりますが、これは攻撃の効率が非常に悪い攻撃になります(莫大な時間と計算量を要する)。

それならば、予め任意の文字列をハッシュ関数にかけた結果をデータベースとして保持しておき、必要なときはそのデータベースを検索すればいいじゃないか、という攻撃方法が考案されました。そのデータベースを"レインボーテーブル"と呼びます。ちなみに、個人レベルでレインボーテーブルを作成するのは不可能に近いので、それを利用したい場合は膨大な計算リソースを持つ誰かが計算した結果を利用することになります。

参考URLを見て頂ければ分かりますが、実はレインボーテーブルは比較的容易に入手できてしまいます。しかし、対象となる文字列の長さはたかが知れており、参考URLの例では最大10文字となっています(それ以上は作成自体 or ファイルサイズが現実的ではなくなる)。政府クラスの膨大な計算リソースを持った組織が本気になればもう少し文字数は増えるでしょうが、桁が増えることに指数関数的に計算量が飛躍的に増加するため、せいぜい数文字増える程度でしょう。

ここで最初に戻りますが、"パスワードの文字列をハッシュ関数にかけた結果(のハッシュ文字列)"は、パスワードが10文字以下であれば誰でも入手可能なインボーテーブルに載っているので、多少の心得がある人の手にかかればすぐに解読できてしまいます。しかし、"その値を更にハッシュ関数にかけた結果"は、入力される文字列が現在は脆弱とされあまり利用されなくなったMD5でさえ32文字、SHA1であれば40文字にもなるため、レインボーテーブルを利用して解読するのは世界中の誰にも当分不可能でしょう。

結論として、"一度ハッシュ関数にかけた結果を入力文字列とすることは、入力文字列を飛躍的に長くすることを意味するため、レインボーテーブルを利用したクラッキングが事実上不可能になる"という効果があるといえるでしょう。

参考URL：

http://project-rainbowcrack.com/table.htm

補足

ありがとうございます。

> 要するに、"パスワードの文字列をハッシュ関数にかけた結果"と、
> "その値を更にハッシュ関数にかけた結果"について、安全性に違いが
> あるかどうかという質問ですよね。
>
はい。ハッシュ関数ｆのｎ乗「ｆ^n」（ｎ≧１）同士を比較しています。

例えば…、

1. 異なる入力に対して同一の出力を得てしまう可能性は、元のハッシュ関数ｆよりもｆ^2、ｆ^3、ｆ^4、…の方が（この順で）高くなっていくように感じます。

2. ３６度の回転行列の逆行列を求めるよりも、その１０乗の逆行列を計算する方が直感的には簡単に思えます。ハッシュ関数の冪乗は必ず逆算が困難なのでしょうか。

…というようなことでした。

> 予め任意の文字列をハッシュ関数にかけた結果をデータベースとして保持しておき、
>
つまり、ストレッチングに関しての「安全」という言葉の意味は単に「ｆの逆計算表は既に知られていても、ｆ^n の逆関数は未だだから」ということでしょうか？