アカウント名:
パスワード:
John……懐かしい．昔はずいぶんとお世話に．あっちこっちでスペースを借りて(略)#若気の至りって怖い．
Johnの辞書ファイル(wordlist)はあるsaltの元でハッシュ化したとかそういうものではなく，単なる単語帳ですよね？で，wordlistモードの場合は与えられたpass/saltに対し，wordlistから単語を一つずつ拾ってきては与えられたsaltの元でハッシュ値に変換し照合，を延々と繰り返すだけで．
そもそも，総当たりのハッシュ値（しかも異なるsaltに対しても）を記録しておくのはストレージ容量的に非現実的では？128bitのハッシュ値の総和はとんでもない容量になりますし．
あ，128bitってのは適当な値で，その数値そのものには意味はありません．#64bitでも結構いっぱいいっぱいな容量に．
いや、そうじゃないのが出ているそうですが。# John the Ripper じゃないのか?いや、Johnだと聞いたんだが…亜種なのか??
私のきいたのは、Saltごとに辞書を分けた上で、パスフレーズを「ハッシュ値でソート」して持つ、というもの。パスワード表から探したいハッシュ値とSaltは解っているので、まずSaltで辞書を選んで、あとは辞書を二分木探索していく。ハッシュ値でソートしてあるので、たとえば辞書の真ん中の単語のハッシュ値を求めて、探しているハッシュ値と比較すれば、辞書の前半分と後ろ半分のどちら側に目的のパスフレーズがあり得るのか、が判る。
登録してあるパスフレーズ数 n に対してO(log n)で探索が終わる。
で、その上で。このパスフレーズ辞書を、丁度IMEの辞書のように圧縮する、というもの。
そもそも，総当たりのハッシュ値（しかも異なるsaltに対しても）を記録しておくのはストレージ容量的に非現実的では？
非現実的というより、無駄ですね。ようするに「全部」についての辞書はノイズと変わらないの法則が適用されますから。
でも、パスフレーズが短い場合のハッシュ値は比較的高速に総当たりで計算できます。あまりにも長いパスフレーズはどのみち辞書をつくり尽くせません。
なので、パスフレーズの長さの最短と最長の両方を決めて、その範囲だけについて辞書を作る。なにも128bit全パターン生成されるまでパスフレーズを作り続ける必要はない。
60bit 程度の強度のパスワードならテーブル参照が現実的に可能でしょう。特定 salt に対するテーブルを埋めるのも数日(数時間? 数十日?) オーダーで可能ですし、検索にかかる時間は当然ながらそれに比べれば無視できる値。
で、例えば現時点でとりあえず安心かなと適当に計算した結果の 77bit ぐらの強度のパスワードでも辞書の作成やら空いてる CPU での計算とかで現時点でもどうにかなっちゃうという事でしょうか?もちろん 10 年ぐらい先まで考えればその程度のパスワードじゃダメでしょうけど、今なら人間の脆弱性を無視出来るという前提の範囲であればそれなりの安全レベルではあると思ってるんですが…
# まあでも 77bit という値を出す上で 1 つパラメーターが足りてないのは事実。# 実際にそれを少なくとも 10～14bit ぐらいは考えておく必要があるのでトータルで# 90bit ぐらいの強度がなきゃ安全とはいえないというのならまあその通りですが…
## それでもアルファベット大文字・小文字・数字混在のランダム列なら 16 文字でセーフ。
まあしょせん思いつき計算なので細かい部分はどうでも言い事ですが…
よくわからないのが John the Ripper だから何が変わるのかという事。いわゆるパスワードクラックは f(pass,salt)→hash という演算が基本で当然ながら ighashgpu であれJohn the Ripper であれ極端な話エヴァンゲリオン第 7 話でミサトさんが「希望」というパスワードを聞き出す件であれ基本的には pass の部分をどう効率よく生成するかとか関数自体をいかに早く計算するかの差でしかなくてやってる事自体はどれも基本的に同じだと思っています。 ← 認識間違ってます?逆引き辞書が作れる程度のパスワード (せいぜい元パスワードが 1 桁の長さのもの?) ならともかく私の計算の前提である「人間の脆弱性を無視」した f(pass,salt)→hash の単純な演算速度から計算した一定長のランダム列に対しての話であれは本質的に何も変わってないように思えるのですが…
わかってないからダメダメだと突っ込まれてるんだろ＞俺
まず、純粋にパスワードが格納されているパスワード表が手に入って、そこからハッシュ値とSalt値の一覧が手に入ったとしましょう。この場合に、このパスワード表からパスワードを求めるために必要な手間は、総当たり戦略しかない、とします(ハッシュ関数に弱点があったりはしないとする)。
この場合に、77bit相当のパスワードを攻略するための、総計算量は nekurai さんのおっしゃる通りの推測が成り立つでしょう。当然、65536台のPC「だけで」攻略しようとした場合に必要になる時間も想定通りでしょう。
ですので当然、私が突っ込んでいるポイントは「それは前提が間違っている」というものです。なぜ 65536台「しか使えない」のか。# もちろん、そうは言ってもこの人たち自身は物理的に 65536台しかPCを持っていないとしましょう。# クラウドサービス の利用とかも禁止ね。
.
辞書型攻略法の最大のポイントは、「辞書は買える」という点です。辞書…つまり事前計算結果を買えるという事は、「他人のPCの演算パワーを安全に購入できる」事に相当します。別の言い方をすると、辞書を買う事で、総当たり戦に必要な総演算量の一部を削ることができる。
また、そのような辞書の作成自体は特に違法行為ではありません。このため、辞書を作って売る人たちがいます。アングラにも、国防とかの関係者にも。もちろん、こういう人たちは、いかに高速に辞書を作り上げるか、いかに「適切な」パスフレーズ一覧を作り上げて、それに対してハッシュ値を高速に計算するか、について血道をあげている。
こうして作られた辞書を買う事で、辞書に登録されている部分に関しては「検索してみる」だけで済むようになります。お金を出して辞書を作る部分で必要だった総当たり戦の演算時間を、検索時間にまで減らした場合、nekuraiさんの想定する77bitは耐えられるのか?
仮に理想的なアルゴリズムや乱数発生装置を持っていてSaltに偏りがなかったとしても「総当たり戦に必要な演算量」 - 「辞書を買う事で削減できる演算量」が、パスワードの真の強度なのです。
うむ、計算上は確かにその通り。
で、その場合問題となるのは言うまでも無く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)に設定を変更する必要があります。
一つのことを行い、またそれをうまくやるプログラムを書け -- Malcolm Douglas McIlroy
ん？ (スコア:1)
John……懐かしい．昔はずいぶんとお世話に．
あっちこっちでスペースを借りて(略)
#若気の至りって怖い．
Johnの辞書ファイル(wordlist)はあるsaltの元でハッシュ化したとかそういうものではなく，単なる単語帳ですよね？
で，wordlistモードの場合は与えられたpass/saltに対し，wordlistから単語を一つずつ拾ってきては与えられたsaltの元でハッシュ値に変換し照合，を延々と繰り返すだけで．
そもそも，総当たりのハッシュ値（しかも異なるsaltに対しても）を記録しておくのはストレージ容量的に非現実的では？
128bitのハッシュ値の総和はとんでもない容量になりますし．
Re:ん？ (スコア:1)
あ，128bitってのは適当な値で，その数値そのものには意味はありません．
#64bitでも結構いっぱいいっぱいな容量に．
Re:ん？ (スコア:1)
いや、そうじゃないのが出ているそうですが。
# John the Ripper じゃないのか?いや、Johnだと聞いたんだが…亜種なのか??
私のきいたのは、Saltごとに辞書を分けた上で、パスフレーズを「ハッシュ値でソート」して持つ、というもの。
パスワード表から探したいハッシュ値とSaltは解っているので、まずSaltで辞書を選んで、あとは辞書を二分木探索していく。ハッシュ値でソートしてあるので、たとえば辞書の真ん中の単語のハッシュ値を求めて、探しているハッシュ値と比較すれば、辞書の前半分と後ろ半分のどちら側に目的のパスフレーズがあり得るのか、が判る。
登録してあるパスフレーズ数 n に対してO(log n)で探索が終わる。
で、その上で。このパスフレーズ辞書を、丁度IMEの辞書のように圧縮する、というもの。
非現実的というより、無駄ですね。ようするに「全部」についての辞書はノイズと変わらないの法則が適用されますから。
でも、パスフレーズが短い場合のハッシュ値は比較的高速に総当たりで計算できます。
あまりにも長いパスフレーズはどのみち辞書をつくり尽くせません。
なので、パスフレーズの長さの最短と最長の両方を決めて、その範囲だけについて辞書を作る。なにも128bit全パターン生成されるまでパスフレーズを作り続ける必要はない。
fjの教祖様
Re:ん？ (スコア:2, すばらしい洞察)
60bit 程度の強度のパスワードならテーブル参照が現実的に可能でしょう。
特定 salt に対するテーブルを埋めるのも数日(数時間? 数十日?) オーダーで可能ですし、
検索にかかる時間は当然ながらそれに比べれば無視できる値。
で、例えば現時点でとりあえず安心かなと適当に計算した結果の 77bit ぐらの強度のパスワードでも
辞書の作成やら空いてる CPU での計算とかで現時点でもどうにかなっちゃうという事でしょうか?
もちろん 10 年ぐらい先まで考えればその程度のパスワードじゃダメでしょうけど、今なら人間の
脆弱性を無視出来るという前提の範囲であればそれなりの安全レベルではあると思ってるんですが…
# まあでも 77bit という値を出す上で 1 つパラメーターが足りてないのは事実。
# 実際にそれを少なくとも 10～14bit ぐらいは考えておく必要があるのでトータルで
# 90bit ぐらいの強度がなきゃ安全とはいえないというのならまあその通りですが…
## それでもアルファベット大文字・小文字・数字混在のランダム列なら 16 文字でセーフ。
まあしょせん思いつき計算なので細かい部分はどうでも言い事ですが…
よくわからないのが John the Ripper だから何が変わるのかという事。
いわゆるパスワードクラックは f(pass,salt)→hash という演算が基本で当然ながら ighashgpu であれ
John the Ripper であれ極端な話エヴァンゲリオン第 7 話でミサトさんが「希望」というパスワードを
聞き出す件であれ基本的には pass の部分をどう効率よく生成するかとか関数自体をいかに早く計算
するかの差でしかなくてやってる事自体はどれも基本的に同じだと思っています。 ← 認識間違ってます?
逆引き辞書が作れる程度のパスワード (せいぜい元パスワードが 1 桁の長さのもの?) ならともかく
私の計算の前提である「人間の脆弱性を無視」した f(pass,salt)→hash の単純な演算速度から計算した
一定長のランダム列に対しての話であれは本質的に何も変わってないように思えるのですが…
わかってないからダメダメだと突っ込まれてるんだろ＞俺
Re:ん？ (スコア:1)
まず、純粋にパスワードが格納されているパスワード表が手に入って、そこからハッシュ値とSalt値の一覧が手に入ったとしましょう。
この場合に、このパスワード表からパスワードを求めるために必要な手間は、総当たり戦略しかない、とします(ハッシュ関数に弱点があったりはしないとする)。
この場合に、77bit相当のパスワードを攻略するための、総計算量は nekurai さんのおっしゃる通りの推測が成り立つでしょう。当然、65536台のPC「だけで」攻略しようとした場合に必要になる時間も想定通りでしょう。
ですので当然、私が突っ込んでいるポイントは「それは前提が間違っている」というものです。なぜ 65536台「しか使えない」のか。
# もちろん、そうは言ってもこの人たち自身は物理的に 65536台しかPCを持っていないとしましょう。
# クラウドサービス の利用とかも禁止ね。
.
辞書型攻略法の最大のポイントは、「辞書は買える」という点です。
辞書…つまり事前計算結果を買えるという事は、「他人のPCの演算パワーを安全に購入できる」事に相当します。
別の言い方をすると、辞書を買う事で、総当たり戦に必要な総演算量の一部を削ることができる。
また、そのような辞書の作成自体は特に違法行為ではありません。このため、辞書を作って売る人たちがいます。アングラにも、国防とかの関係者にも。もちろん、こういう人たちは、いかに高速に辞書を作り上げるか、いかに「適切な」パスフレーズ一覧を作り上げて、それに対してハッシュ値を高速に計算するか、について血道をあげている。
こうして作られた辞書を買う事で、辞書に登録されている部分に関しては「検索してみる」だけで済むようになります。お金を出して辞書を作る部分で必要だった総当たり戦の演算時間を、検索時間にまで減らした場合、nekuraiさんの想定する77bitは耐えられるのか?
仮に理想的なアルゴリズムや乱数発生装置を持っていてSaltに偏りがなかったとしても
「総当たり戦に必要な演算量」 - 「辞書を買う事で削減できる演算量」
が、パスワードの真の強度なのです。
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 (暑いか寒い)
Re:ん？ (スコア:1)
>そうじゃないのが出ているそうですが。
そうですか，そんなものがでているのですか．
世の中進歩してるんだなあ……
#進歩……と呼んでいいのかはわかりませんが(苦笑)
>パスフレーズの長さの最短と最長の両方を決めて、その範囲だけについて辞書を作る。
なるほど．
普通だったら辞書+ルールで時間をかけてやるようなものを，ある程度あらかじめ変換済みの辞書を作っておくことでいくらか高速化出来る，と．
世の中進歩（それはもういい）
確かに，ハッシュ関数が複雑化して計算に時間がかかるようになると，そういう事前にある程度準備しておく，ってのの利点が増えるわけですね．
恐らく現実的には，そういう場合でも乱数的なパスワードは相変わらず強いんでしょうが，「一般のユーザーアカウントを適当に何個か引っこ抜けりゃいいや」って目的だと脅威になっちゃうわけですね．しかも短いパスワードに対してはあらかじめ計算機をぶんまわしてリスト化できるから，ハッシュ関数をめんどくさい計算量の（多少）多いものにしても意味がない，と．