No.3ベストアンサー
- 回答日時:
再び#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 強くなる)のであれば、f, f^2, f^3, …と無数に安全な(or より安全な)ハッシュ関数が得られてしまうというのが最初の違和感がでした。
ですが、nが大きくなればなるほど安全になるのが事実だとしても、計算にかけられる時間は有限なので、実際の実装は要求される安全性と処理時間とのトレードオフになります。たとえば、オンラインバンキングのパスワードを格納するのであれば、n = 10,000とするのも非現実的ではありませんが、流出して困るような情報が一歳存在しない社内の検証サーバのnを10,000に設定するのは、守るべき情報の価値を考えると過剰といえるでしょう。
参考 : ハッシュの衝突耐性について
http://ja.wikipedia.org/wiki/MD5#.E3.83.8F.E3.83 …
この回答への補足
> ですが、nが大きくなればなるほど安全になるのが事実だとしても、計算にかけられる時間は有限なので、
>
いいえ。jmh は「再び十分に安全ですか」と疑いを持っています。逆に「nが大きくなればなるほど脆弱になっていくのではないですか」と質問しています。
No.2
- 回答日時:
こんにちわ、#1です。
> つまり、ストレッチングに関しての「安全」という言葉の意味は単に「fの逆計算表は既に知られていても、f^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% …
この回答への補足
ありがとうございます。自分自身の質問の意味がだんだんハッキリしてきたような気がします。申し訳ないです。
> f = ユーザがパスワードとして設定する文字列の長さの方が、f^n = fを
> ハッシュ関数にかけた結果として得られる文字列よりも圧倒的に短いということは
> お分かりかと思います。…
>
いいえ。2つのハッシュ計算法fとf^n とを比較していますので、fとf^n への「入力」は同じ「平文のパスワード(または+ソルト)」です。
y = f(x) ← xの代わりにyを保存します。
y = f(f(x)) = (f^2)(x) ← xの代わりにyを保存します。
y = f(f(f(x))) = (f^3)(x) ← …
…
y = f(f(…f(x))…) = (f^n)(x) ← 入力はいつもxです。
例えば、f(x) = (2 * x) % 16 =「入力値を2倍して16で割った余り」とすると、fの出力から入力を求めるには少しの計算が必要ですが、f^4 は定数関数=0なので全く計算する必要がありません。つまりf^4 の方が少し危険に見えます。元々パスワードの代わりにハッシュ値を保存すると、正しいパスワードとは異なる値を入力しても解錠してしまうという危険がありますが、それが増大したり…などで、安全性が低下したり(ほとんど役立たずになったり)することはないのか、突破に要する計算量の理論上の下限という意味では弱くなっていることもあるのではないか、という疑問です。もし、弱くならない(or 強くなる)のであれば、f, f^2, f^3, …と無数に安全な(or より安全な)ハッシュ関数が得られてしまうというのが最初の違和感がでした。
ちなみに、読んだのはこれだったようです:
http://blog.tokumaru.org/2013/08/1.html
しばらく、お休みしてました。申し訳ないです。
しかし少し疑問が解けたような気がします。今日、wikipedia の「暗号学的ハッシュ関数」を読み直したら、
>
> 暗号学的ハッシュ関数は『既知』の全暗号攻撃法に耐性がなければならない。
> 少なくとも、…
>
とありました (『』は jmh)。何度も読んだハズなのに気付かなかったです。「既知の」とハッキリ書いてありました 。
http://ja.wikipedia.org/wiki/%E6%9A%97%E5%8F%B7% …
「原像計算困難性」「第2原像計算困難性」「衝突困難性」の「困難性」というのは、これらの「既知の攻撃方法」による困難性を指していて、未知の攻撃方法への耐性はそもそも評価していなかったようです。wikipedia には
>
> 計算複雑性理論では「困難 (hard)」という用語は特定の意味を持つ。
> しかしここでいう「困難」は、それとはほとんど関係がない。
>
とあって、"ここでいう「困難」" が分からない…と思っていましたが、直前に書いてあったのです。
ストレッチングに対する攻撃手法は「それを再計算する以外は知られていない」のだから、元のハッシュ関数よりもずっと強いという結論になるのだと思います。
No.1
- 回答日時:
こんにちわ。
要するに、"パスワードの文字列をハッシュ関数にかけた結果"と、"その値を更にハッシュ関数にかけた結果"について、安全性に違いがあるかどうかという質問ですよね。
ご存知の通り、任意のハッシュ文字列αから元の文字列を推測することは基本的に不可能です。
強引に推測する場合、元の文字列となりうる文字列を片っ端からハッシュ関数にかけて、その結果がαになるまで施行を繰り返すブルートフォース攻撃を行うことになりますが、これは攻撃の効率が非常に悪い攻撃になります(莫大な時間と計算量を要する)。
それならば、予め任意の文字列をハッシュ関数にかけた結果をデータベースとして保持しておき、必要なときはそのデータベースを検索すればいいじゃないか、という攻撃方法が考案されました。そのデータベースを"レインボーテーブル"と呼びます。ちなみに、個人レベルでレインボーテーブルを作成するのは不可能に近いので、それを利用したい場合は膨大な計算リソースを持つ誰かが計算した結果を利用することになります。
参考URLを見て頂ければ分かりますが、実はレインボーテーブルは比較的容易に入手できてしまいます。しかし、対象となる文字列の長さはたかが知れており、参考URLの例では最大10文字となっています(それ以上は作成自体 or ファイルサイズが現実的ではなくなる)。政府クラスの膨大な計算リソースを持った組織が本気になればもう少し文字数は増えるでしょうが、桁が増えることに指数関数的に計算量が飛躍的に増加するため、せいぜい数文字増える程度でしょう。
ここで最初に戻りますが、"パスワードの文字列をハッシュ関数にかけた結果(のハッシュ文字列)"は、パスワードが10文字以下であれば誰でも入手可能なインボーテーブルに載っているので、多少の心得がある人の手にかかればすぐに解読できてしまいます。しかし、"その値を更にハッシュ関数にかけた結果"は、入力される文字列が現在は脆弱とされあまり利用されなくなったMD5でさえ32文字、SHA1であれば40文字にもなるため、レインボーテーブルを利用して解読するのは世界中の誰にも当分不可能でしょう。
結論として、"一度ハッシュ関数にかけた結果を入力文字列とすることは、入力文字列を飛躍的に長くすることを意味するため、レインボーテーブルを利用したクラッキングが事実上不可能になる"という効果があるといえるでしょう。
参考URL:http://project-rainbowcrack.com/table.htm
この回答への補足
ありがとうございます。
> 要するに、"パスワードの文字列をハッシュ関数にかけた結果"と、
> "その値を更にハッシュ関数にかけた結果"について、安全性に違いが
> あるかどうかという質問ですよね。
>
はい。ハッシュ関数fのn乗「f^n」(n≧1)同士を比較しています。
例えば…、
1. 異なる入力に対して同一の出力を得てしまう可能性は、元のハッシュ関数fよりもf^2、f^3、f^4、…の方が(この順で)高くなっていくように感じます。
2. 36度の回転行列の逆行列を求めるよりも、その10乗の逆行列を計算する方が直感的には簡単に思えます。ハッシュ関数の冪乗は必ず逆算が困難なのでしょうか。
…というようなことでした。
> 予め任意の文字列をハッシュ関数にかけた結果をデータベースとして保持しておき、
>
つまり、ストレッチングに関しての「安全」という言葉の意味は単に「fの逆計算表は既に知られていても、f^n の逆関数は未だだから」ということでしょうか?
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- その他(コンピューター・テクノロジー) ハッシュ値を取ったらその取ったハッシュ値はどのように保管すればよいのでしょうか?ハッシュ値のデータす 2 2023/07/02 19:40
- その他(セキュリティ) パスワードの管理どうすればよいでのしょうか? 6 2023/06/10 14:11
- その他(セキュリティ) アカウントの乗っ取りで質問です。長いです。 先月ツイッターの乗っ取りにあい、アカウントを全て新しくし 2 2022/03/25 20:47
- その他(コンピューター・テクノロジー) なぜデータの整合性を確認する時はハッシュ値で確認するのでしょうか?ハッシュ値は衝突する可能性があるの 5 2023/07/05 20:38
- その他(コンピューター・テクノロジー) exFATの外付けSSDからパソコンのNTFSの内蔵ストレージにコピーした場合はコピーしたデータのハ 2 2023/08/09 19:51
- Excel(エクセル) 【困っています】VBA 追加処理の記述を教えてください。 1 2022/08/25 22:54
- Visual Basic(VBA) 【前回の続き続きです、ご教示ください】VBAの記述方法がわかりません。 2 2022/08/24 20:49
- Visual Basic(VBA) 【困っています2】VBA 追加処理の記述を教えてください。 2 2022/08/26 11:42
- その他(セキュリティ) パスワードの管理について googleのパスワードマネージャーはダメ? 2 2023/01/27 23:09
- その他(ソフトウェア) F-BASICで計算中の実行が中途で勝手に止まり、大変困っています。 2 2023/03/02 16:15
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
メールをパスワードつきで送る方法
-
Excelのセルにユーザー名...
-
YouTubeが毎回ログインしないと...
-
大学定期試験過去問サイト「過...
-
メールを返信したら、英語のメ...
-
LINE TCBというところからLINE...
-
メールのマナー編
-
インスタの捨て垢で友達のスト...
-
メールアドレスで上付きのハイフン
-
エクセルで複数ファイルに同一...
-
「@」(アットマーク)の無いメ...
-
メールアドレス 上バーの入力...
-
CSVファイルを添付するときにパ...
-
URLとメールアドレス
-
メールエラー
-
メールアドレスから個人を特定...
-
高一男子です 僕が絶対に悪いん...
-
Outlookで、メールを他...
-
インスタグラムでブロックされ...
-
ワードに入力したメールアドレ...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
Excelのセルにユーザー名...
-
メールをパスワードつきで送る方法
-
LINE TCBというところからLINE...
-
メールアドレス 上バーの入力...
-
大学定期試験過去問サイト「過...
-
メールエラー
-
メールのマナー編
-
メールアドレスで上付きのハイフン
-
インスタの捨て垢で友達のスト...
-
インスタのアイコンについてるN...
-
メールを返信したら、英語のメ...
-
steam版 apexのログアウト方法...
-
ビーリアルのユーザー名を変え...
-
メールアドレスから個人を特定...
-
携帯電話を解約してもSMSの受信...
-
「@」(アットマーク)の無いメ...
-
YouTubeが毎回ログインしないと...
-
解約済みの iPadについて 解約...
-
カカオで退会せずに、アプリだ...
-
CSVファイルを添付するときにパ...
おすすめ情報