PHPのmd5()などで作成されるランダム英数文字列(32桁)をキーに使った

場合の機密性について知りたいと思っています。

一説によると、8桁のランダム英数をつきとめるのに2~3週間かかると
聞いたのですが、例えば、ランダム英数文字列32桁を、現在最速のコン
ピュータを使って解析した場合、どのくらいの早さでつきとめることが
できるのでしょうか。

また、例えば使用しているキーが複数あった場合は、解析にかかる期間
としての考え方は、1件をつきとめる場合の期間を単純にキーの数で
割ればよいのでしょうか?
それとももっと違う考え方になりますでしょうか。

できれば個人のブログなどでなく、それなりに信頼できそうなサイトの
記述や文献などを提示していただけると嬉しいです。

回答の条件
  • URL必須
  • 1人5回まで
  • 登録:2006/05/25 11:46:35
  • 終了:2006/05/25 23:21:50

回答(4件)

id:naochin No.1

naochin回答回数170ベストアンサー獲得回数82006/05/25 12:06:44

ポイント50pt

ランダム英数文字列を数字+アルファベット大小で64文字と仮定します。

これで表される情報量は2^6です。

文字数が増えれば増えるほど探索に必要な計算量は増加します。

8文字ですと、2^(6*8)=2^48

これが、32文字になりますと、

2^(6*32)=2^(6*32)=2^192

となります。

簡単に言うと、1文字増やすと計算時間が64倍に増えます。

で、現在のところ、単純な全数探索の実験結果としては分散コンピュータ環境で64ビットの例があります(RC5-64 Challenge)。

とりあえず、192ビット分の全数探索は不可能だと考えられています。

http://www.amazon.co.jp/exec/obidos/ASIN/4764901307/503-2796599-...

ここらへんの本を参考にしてはいかがでしょうか。

使用しているキーが複数あるときに、その中の二つが偶然一致してしまう確率というものが存在します。

これが意外に少ない数で結構確率が高くなります。

「誕生日のパラドックス」といわれるものです。

http://ja.wikipedia.org/wiki/%E8%AA%95%E7%94%9F%E6%97%A5%E3%81%A...

たとえば、8文字のランダム英数文字列があった場合、情報量は2^48ですが、

もし、2^24個のランダム英数文字列があった場合 およそ半分の確率で一致することがあります。

32文字ですと2^96個の候補が必要となります。これらを保存するための領域を考えると8文字では足りないが32文字では十分であることがわかります。

(192ビットの情報を2^96個集めるための容量はおよそ2^102バイト=2^60TB=10^20TBです。)

id:golbeza

ありがとうございました。

特に複数キーがある場合、単純にキーの数で割るものではないということが参考になりました。

>32文字ですと2^96個の候補が必要となります。これらを保存するための領域を考えると8文字では足りないが

>32文字では十分であることがわかります。

>(192ビットの情報を2^96個集めるための容量はおよそ2^102バイト=2^60TB=10^20TBです。)

とりあえずは32桁あれば、そう心配しなくてもいいだろうと思ってよいでしょうか・・・?

2006/05/25 12:39:21
id:naochin No.2

naochin回答回数170ベストアンサー獲得回数82006/05/25 18:14:50

ポイント50pt

もう一個問題があって、

乱数で発生させると書かれていますが、その乱数をどう生成するかに問題が発生するケースがあります。

以前、Netscape NavigatorでSSLが解読されたケースがありますが、

それは、暗号そのものでなく、鍵生成乱数の発生方法に問題があったためです。

http://www.nsug.or.jp/readme/no18/95sympo.html


このことを考えると、単純にmd5で作ったものをそのまま使うのはまずいかもしれません。

(MD5自身そんなに強くはないハッシュアルゴリズムです)

SHA-256あたりを使ってやってもよいかもしれませんね。

id:golbeza

ありがとうございます。

乱数の発生方法がばればれだと確かに解読されやすいでしょうね・・・

2006/05/25 22:30:29
id:l-lol-l No.3

l-lol-l回答回数310ベストアンサー獲得回数102006/05/25 20:07:34

ポイント50pt

まずは因果関係が整理されていないので整理しなければなりません。

なにかの元(A)があり、それからPHP:md5を使ってランダム文字列(B)をつくり、それをキーとした暗号かなにか(C)をするわけですね。

まず大切なのは(C)自体の信頼性でしょう。ここがしょぼしょぼならいくらキーがランダムでもなんにもなりません。

ただ、ここでは何も開示されていませんから、それなりに強固だということにします。

次にmd5ですが、これはなにかから120bitのハッシュを作る関数です。それが32文字の英数字に変換されるかもしれませんが、120bit以上の情報はもっていません。

単純に考えれば、できた結果をキーとした場合、全数検索で、2^120回の試行が必要です。

これは、すごく強固です。

さて最後が問題です。PHP:md5の引数になにをいれますか?引数の種類が∞であれば、md5はきちんと働いて2^120種類のキーを生成してくれるでしょう。

でも、0か1しか入れなかったら。。。キーも2種類ですね。

じゃ、現在時間を秒単位で入れて見ましょう。一日はたった81600秒しかありません。攻撃者は1週間分暗い試せばいいでしょうか?たった50万回ためせばばれます。

いれるのはパスワードでしょうか?世の中にはパスワードクラッカーなんてのもあって相当ランダムなパスワードでないとすぐクラックされます。

結局、このシステムでは、最初のPHP:md5に食べさせるランダムなものが鍵を(まさに!)握っています。md5はランダムにみせかけているだけですよ。

お使いのPCにハードウェア乱数生成器はのっていますか?あるいはきちんと検証された議事乱数発生器をつかっていますか?

であれば、大丈夫でしょう。

世の中にはこれに何を入れたか開示していないから大丈夫というふざけた仕様もあります。

でも、この場合仕様が内部流出したり、なにかの加減で仕様がばれると、以降ばれつづけです。注意しましょう

http://q.hatena.ne.jp/1148525194

id:golbeza

ありがとうございます。参考になりました。

キーは確かに時間にしており、マイクロ秒までです。

時間だと、数字しかないし桁数も固定だから逆に解析されやすいでしょうか。

2006/05/25 22:45:34
id:l-lol-l No.4

l-lol-l回答回数310ベストアンサー獲得回数102006/05/25 22:58:13

ポイント50pt

キーは確かに時間にしており、マイクロ秒までです。

それはマイクロ秒まできちんと精度でていますか?世の中には桁はマイクロ秒だけど、いつみても10msまでしか数字が変わらない。たとえば12:34:56.78000000

(0の部分はいつも0)ってなこともあります。

時間だと、数字しかないし桁数も固定だから逆に解析されやすいでしょうか

時間取得関数の戻り値を直接入れるのはみんな考えること=攻撃者が最初に試すこと。でしょう。

たとえばあなたしかしらないランダムバイナリをxorするだけでも、攻撃者には意味不明になります。ただ、ソースが流出したらばればれですが。

ライブラリに擬似乱数生成器 PRNGはありませんか?そこまで気にされるなら、導入してみてはどうでしょうか?opensslを入れると付いてきたような気がします(性能はわかりませんけど)

乱数について

http://www.linux.or.jp/JF/JFdocs/Secure-Programs-HOWTO/random-nu...

id:golbeza

なるほど、マイクロ秒まで出てるかどうかの検証はしていませんでした。

知れば知るほど不安になってきました・・・う~ん いろいろ考えてみます!

2006/05/25 23:20:15

コメントはまだありません

この質問への反応(ブックマークコメント)

トラックバック

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません