アカウント名:
パスワード:
John……懐かしい．昔はずいぶんとお世話に．あっちこっちでスペースを借りて(略)#若気の至りって怖い．
Johnの辞書ファイル(wordlist)はあるsaltの元でハッシュ化したとかそういうものではなく，単なる単語帳ですよね？で，wordlistモードの場合は与えられたpass/saltに対し，wordlistから単語を一つずつ拾ってきては与えられたsaltの元でハッシュ値に変換し照合，を延々と繰り返すだけで．
そもそも，総当たりのハッシュ値（しかも異なるsaltに対しても）を記録しておくのはストレージ容量的に非現実的では？128bitのハッシュ値の総和はとんでもない容量になりますし．
いや、そうじゃないのが出ているそうですが。# John the Ripper じゃないのか?いや、Johnだと聞いたんだが…亜種なのか??
私のきいたのは、Saltごとに辞書を分けた上で、パスフレーズを「ハッシュ値でソート」して持つ、というもの。パスワード表から探したいハッシュ値とSaltは解っているので、まずSaltで辞書を選んで、あとは辞書を二分木探索していく。ハッシュ値でソートしてあるので、たとえば辞書の真ん中の単語のハッシュ値を求めて、探しているハッシュ値と比較すれば、辞書の前半分と後ろ半分のどちら側に目的のパスフレーズがあり得るのか、が判る。
登録してあるパスフレーズ数 n に対してO(log n)で探索が終わる。
60bit 程度の強度のパスワードならテーブル参照が現実的に可能でしょう。特定 salt に対するテーブルを埋めるのも数日(数時間? 数十日?) オーダーで可能ですし、検索にかかる時間は当然ながらそれに比べれば無視できる値。
で、例えば現時点でとりあえず安心かなと適当に計算した結果の 77bit ぐらの強度のパスワードでも辞書の作成やら空いてる CPU での計算とかで現時点でもどうにかなっちゃうという事でしょうか?もちろん 10 年ぐらい先まで考えればその程度のパスワードじゃダメでしょうけど、今なら人間の脆弱性を無視出来るという前提の範囲であればそれなりの安全レベルではあると思
まず、純粋にパスワードが格納されているパスワード表が手に入って、そこからハッシュ値とSalt値の一覧が手に入ったとしましょう。この場合に、このパスワード表からパスワードを求めるために必要な手間は、総当たり戦略しかない、とします(ハッシュ関数に弱点があったりはしないとする)。
この場合に、77bit相当のパスワードを攻略するための、総計算量は nekurai さんのおっしゃる通りの推測が成り立つでしょう。当然、65536台のPC「だけで」攻略しようとした場合に必要になる時間も想定通りでしょう。
ですので当然、私が突っ込んでいるポイントは「それは前提が間違っている」というもので
うむ、計算上は確かにその通り。
で、その場合問題となるのは言うまでも無くO(総当たり戦に必要な演算量) と O(辞書を買う事で削減できる演算量) の差がどの程度かでしょう。例えば O(総当たり戦に必要な演算量) ＞＞＞ O(辞書を買う事で削減できる演算量) なら実質誤差。O(総当たり戦に必要な演算量) ＜＜＜ O(辞書を買う事で削減できる演算量) なら大変な事態です。
で、計算ははしょるけど 77bit 総当りに対して 1/4 を辞書でカバーしようとすると表のストーリーレベルの PC を 10 億台 1 ヶ月フル稼働すればいいぐらいの値。
世の中にこのクラス or このクラス以上の GPU がそれだけ出荷されているのかとか、そもそもそれだけの辞書を格納するストレージってあるのかという懸念を面倒なので全て無視したとして現時点の辞書を作成した場合の影響をこんな感じに考えればいいんじゃないかと。まあ今後 1 ～ 2 年は世界中の国家を敵に回さなきゃ気にしなくてもいいような気はするけど…全世界を敵に回すならあと 5～6bit (パスワードで 1 文字分) ぐらい必要という気もしてきた ^^;;;
てなわけでそのあたりのパラメータもぶち込んで後でもう 1 度計算し直しますね。
おまけ:ちなみに 10 億台程度なら世界の総発電量に対してのインパクトは 3% 程度っぽい。# コレ [cia.gov]を元に PC 1 台 120wh として計算した場合。# 実際は 150～200wh 程度だと思うのでもうちょっと大きくなると思うけどそれでも誤差の範囲。なのでヤシマ作戦は必要なさげ。
だがそれは1億台10ヶ月でも同じ結果が得られる。3年で2800万台でもいいぞ。# まぁ、この場合「ハッシュ関数の癖」を使って計算をショートカットするほうが# 簡単だけど。
何よりも重要なのは、「必要な辞書が得られてから、Cracking を開始すれば良い」という事だろう。これはコンテストではないのだ。
このへんの話ですかね。
魂、奪われた後――弱いパスワードの罪と罰 － ＠IT [atmarkit.co.jp]
代表的なハッシュ(Saltなし)ならRainbow Tableがすでにあるっぽい?
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
皆さんもソースを読むときに、行と行の間を読むような気持ちで見てほしい -- あるハッカー
ん？ (スコア:1)
John……懐かしい．昔はずいぶんとお世話に．
あっちこっちでスペースを借りて(略)
#若気の至りって怖い．
Johnの辞書ファイル(wordlist)はあるsaltの元でハッシュ化したとかそういうものではなく，単なる単語帳ですよね？
で，wordlistモードの場合は与えられたpass/saltに対し，wordlistから単語を一つずつ拾ってきては与えられたsaltの元でハッシュ値に変換し照合，を延々と繰り返すだけで．
そもそも，総当たりのハッシュ値（しかも異なるsaltに対しても）を記録しておくのはストレージ容量的に非現実的では？
128bitのハッシュ値の総和はとんでもない容量になりますし．
Re: (スコア:1)
いや、そうじゃないのが出ているそうですが。
# John the Ripper じゃないのか?いや、Johnだと聞いたんだが…亜種なのか??
私のきいたのは、Saltごとに辞書を分けた上で、パスフレーズを「ハッシュ値でソート」して持つ、というもの。
パスワード表から探したいハッシュ値とSaltは解っているので、まずSaltで辞書を選んで、あとは辞書を二分木探索していく。ハッシュ値でソートしてあるので、たとえば辞書の真ん中の単語のハッシュ値を求めて、探しているハッシュ値と比較すれば、辞書の前半分と後ろ半分のどちら側に目的のパスフレーズがあり得るのか、が判る。
登録してあるパスフレーズ数 n に対してO(log n)で探索が終わる。
fjの教祖様
Re: (スコア:2, すばらしい洞察)
60bit 程度の強度のパスワードならテーブル参照が現実的に可能でしょう。
特定 salt に対するテーブルを埋めるのも数日(数時間? 数十日?) オーダーで可能ですし、
検索にかかる時間は当然ながらそれに比べれば無視できる値。
で、例えば現時点でとりあえず安心かなと適当に計算した結果の 77bit ぐらの強度のパスワードでも
辞書の作成やら空いてる CPU での計算とかで現時点でもどうにかなっちゃうという事でしょうか?
もちろん 10 年ぐらい先まで考えればその程度のパスワードじゃダメでしょうけど、今なら人間の
脆弱性を無視出来るという前提の範囲であればそれなりの安全レベルではあると思
Re: (スコア:1)
まず、純粋にパスワードが格納されているパスワード表が手に入って、そこからハッシュ値とSalt値の一覧が手に入ったとしましょう。
この場合に、このパスワード表からパスワードを求めるために必要な手間は、総当たり戦略しかない、とします(ハッシュ関数に弱点があったりはしないとする)。
この場合に、77bit相当のパスワードを攻略するための、総計算量は nekurai さんのおっしゃる通りの推測が成り立つでしょう。当然、65536台のPC「だけで」攻略しようとした場合に必要になる時間も想定通りでしょう。
ですので当然、私が突っ込んでいるポイントは「それは前提が間違っている」というもので
fjの教祖様
Re:ん？ (スコア:1)
うむ、計算上は確かにその通り。
で、その場合問題となるのは言うまでも無く
O(総当たり戦に必要な演算量) と O(辞書を買う事で削減できる演算量) の差がどの程度かでしょう。
例えば O(総当たり戦に必要な演算量) ＞＞＞ O(辞書を買う事で削減できる演算量) なら実質誤差。
O(総当たり戦に必要な演算量) ＜＜＜ O(辞書を買う事で削減できる演算量) なら大変な事態です。
で、計算ははしょるけど 77bit 総当りに対して 1/4 を辞書でカバーしようとすると
表のストーリーレベルの PC を 10 億台 1 ヶ月フル稼働すればいいぐらいの値。
世の中にこのクラス or このクラス以上の GPU がそれだけ出荷されているのかとか、そもそも
それだけの辞書を格納するストレージってあるのかという懸念を面倒なので全て無視したとして
現時点の辞書を作成した場合の影響をこんな感じに考えればいいんじゃないかと。
まあ今後 1 ～ 2 年は世界中の国家を敵に回さなきゃ気にしなくてもいいような気はするけど…
全世界を敵に回すならあと 5～6bit (パスワードで 1 文字分) ぐらい必要という気もしてきた ^^;;;
てなわけでそのあたりのパラメータもぶち込んで後でもう 1 度計算し直しますね。
おまけ:
ちなみに 10 億台程度なら世界の総発電量に対してのインパクトは 3% 程度っぽい。
# コレ [cia.gov]を元に PC 1 台 120wh として計算した場合。
# 実際は 150～200wh 程度だと思うのでもうちょっと大きくなると思うけどそれでも誤差の範囲。
なのでヤシマ作戦は必要なさげ。
Re:ん？ (スコア:1)
だがそれは1億台10ヶ月でも同じ結果が得られる。3年で2800万台でもいいぞ。
# まぁ、この場合「ハッシュ関数の癖」を使って計算をショートカットするほうが
# 簡単だけど。
何よりも重要なのは、「必要な辞書が得られてから、Cracking を開始すれば良い」という事だろう。これはコンテストではないのだ。
fjの教祖様
Re:ん？ (スコア:1)
このへんの話ですかね。
魂、奪われた後――弱いパスワードの罪と罰 － ＠IT [atmarkit.co.jp]
代表的なハッシュ(Saltなし)ならRainbow Tableがすでにあるっぽい?
M-FalconSky (暑いか寒い)