暗号理論コミュのハッシュ値から元データは生成しうるか？

ツイッターでkawaz氏がまとめた「平文パスワードの再送問題について」。
http://togetter.com/li/77080

ハッシュ値から元データは生成しうるのでしょうか。
togetter上で紹介されていたサイトを眺めてみたのですが、よく分かりません。。。

第8回魂、奪われた後――弱いパスワードの罪と罰
http://www.atmarkit.co.jp/fsecurity/rensai/view08/view01.html

ここでのポイントは、「総当り攻撃でハッシュ値を生成（し、手元のハッシュ値リストと照合）することは、通常予期されるリソースで可能なのか」という問題なのかと思います。

ご教示、宜しくお願いします。

コメント(11)

最初
全て
最新の40件

[1] mixiユーザー 12月10日 00:17

もちろんハッシュ空間に依存します。
安全なハッシュアルゴリズムを使用し、十分に安全なパスワードを設定していると仮定するならば、総当り攻撃でしか解読は不可能です。
で、ハッシュ値の空間が１秒間に試行できる照合処理に対して現実的でない回数分以上あればいいわけです。
単純化して言うと１日に１０億回照合できたとしてもハッシュ空間が１０億×２万種類であれば平均して１万日もかかります。
ハッシュだけでなく大抵の暗号アルゴリズムに対しても同様のことが言えます。

[2] mixiユーザー 12月10日 10:47

そのtogetterはいまいち当事者もまとめた人も混乱してる気がしますが。
たとえばざっと見た感じ、オケゲム氏は「十分に安全なパスワード」を前提としていないように思える。

あと「通常予期されるリソース」と言われますが、ソルトを使ってない場合、あらかじめ時間をかけて生成した、ありそうなパスワード（←十分に安全ではないパスワードですね）のハッシュ値のリストと照合できるので「あらかじめ時間をかけて」というリソースを想定できるのに対し、ソルトを使っていたらそれはできない。

[3] mixiユーザー 12月12日 17:15

＞サントさん

ご教示有難うございます。
ハッシュ空間は、http://www.atmarkit.co.jp/fsecurity/rensai/view08/view01.htmlの例では512bitでしたが、これでは不十分なのでしょうね。

＞metanestさん

なるほど、ソルトという概念は初耳でした。
ソルトを使用することで、攻撃者側は｢ソルト奪取後でなければ計算を開始できず、予め準備することが困難になる｣というわけですね。
有難うございます。

[4] mixiユーザー 12月12日 18:10

> これでは不十分なのでしょうね。

違います。
その記事の中に現れるパスワード例は、このトピック内の用語で言うと「十分に安全なパスワード」でないパスワード、なのです。

[5] mixiユーザー 12月12日 19:28

>3
一応言っておきますが現実的な時間内にハッシュ値が解読されるのと、その運用に危険性があるのは別です。総当りでハッシュを破る場合、元の値の判定処理が必要です。
もちろん元の値を知らないので、直接照合できず、推定で行います。
例えば元の値がパスワードなら解読値を利用してのログインを行い、成功したなら解読できたと判断します。しかし、通常パスワードはユーザIDと共にログインに利用されます。なので、特定IDの一定時間内のログイン失敗回数を規定しておけば、解読は困難になります。
また、パスワード（もしくはハッシュ値）が毎回同じではない場合も不正な攻撃が困難です。毎回変わる特定の値（ソルト）を混合した値によってハッシュ値を生成した場合では、ログインに利用されるハッシュ値はユーザが入力するパスワードは同じにもかかわらず毎回異なります。なので、解読できたとしてもその元の値は意味を成しません。他にもパスワードを短時間・少回数ごとに完全に新たなものにする運用方法もあります。極端なものではワンタイムパスワードと言い、毎回パスワードが変わり、その前後で関連は全くありません。なので、解読できたとしても既にそのパスワードは利用できません。
つまり、ハッシュ生成元の値が解読される＝即不正な攻撃に利用できる、というわけではありません。
更にハッシュ生成元の値がテキストでなくバイナリであった場合、そのどの値が正解か分からない、や、テキストデータだがおかしくは無い、通常あり得るテキストが複数種類解読できた場合どちらが正解か分からない等、そもそも判定方法が無い場合もあります。

ただし以上の事は、総当り攻撃でしか解読が不可能な安全なパスワード（元データ）に限ります。ユーザ名と同じだとか同じ文字ばかりだとか、英単語をそのまま使用しただとか予めパスワードを限定しうる場合は、他の攻撃が可能です。

ちなみにこれらは一般論で記事と関係があるかは読んでいないので分かりません。

[6] mixiユーザー 12月12日 20:10

> 毎回変わる特定の値（ソルト）

チャレンジ、ではないでしょうか？

[7] mixiユーザー 12月12日 20:24

>6
チャレンジは厳密に言えばハッシュ関数のためだけのものではなく、それを無視したとしてもソルトはチャレンジを含蓄するものですので、この場合ソルトの方がより適切であると思います。

[8] mixiユーザー 12月15日 12:03

ワンタイムパスワードが登場していますが、既知のワンタイムパスワードは多くがワンタイムパスワードを生成するトークンが真性であることを証明しているだけでそのトークンが本人の手中にあるのか攻撃者の手中にあるかについては関知していません。別途、記憶すべき固定パスワードを併用することが不可欠です。この点への留意が必要です。

[9] mixiユーザー 01月10日 09:46

この話題が出た時、メッセージの照合などに使うハッシュと違い、非常に計算が重いハッシュ関数にすることで、ブルートフォースを難しくする、という話題がウェブで出ていた記憶があるのですが、今検索してみたところ、SHA-1 などを何回も通すというストレッチングという手法については出てきたのですが、ハッシュ関数自体を重いものにするという手法と具体的な関数について、見つけられませんでした。
なにかご存知のかた、おられましたらご教示ください。

[10] mixiユーザー 01月10日 14:50

>9
聞いたことはありませんが、それってブルートフォースの計算量を増やすのが目的ですよね。
ハッシュ空間を拡大して平均試行回数を増やすので十分ではないでしょうか？
しかもコンピュータの発達に伴って容易に計算量を増やせないので、実用的ではありません。

もし短期間しか使用できなくとも良いというのなら以下のようなものはいかがでしょうか？
１、検索エンジンで特定のワードを検索する
２、ヒットしたページのX番目にアクセスする。
３、アクセスしたページを語句解析し、Y番目のワードを取得する。
４、取得したワードを用いて検索エンジンで検索する。
５、２に戻る

シードは検索エンジン種類と初期ワードと、検索試行回数とそのそれぞれのXとYの値から成ります。最終的にたどり着いたページのURLやHTMLなどを従来のハッシュ関数にかけたのがハッシュ値です。
これはHTTPのオーバーヘッドがかかるため、計算量は少なくても時間はかかります。
もちろん、ページ内容が書き換えられたり、検索結果順位が変化したらハッシュ値も変わりますが。

ログインすると、みんなのコメントがもっと見れるよ