K.Maebashi's BBS

> saltがばれてる状態では、「探索空間が salt のビット数分広がる」 > ことはないように思いますが…まだ何か勘違いしてますでしょうか。 D: 辞書のサイズ S: salt のビット数 N: ユーザ数 M: メッセージ数 とします。 ここで、一つのMD5ハッシュ値から辞書を引いてパスワードを得るコスト を O(1) とします。 また、異なるメッセージであっても、同一ユーザーは同じパスワードを 使い回すと仮定します。 なお、2^S は、M より有意に大きいため、ほぼ全てのメッセージについて、 異なる salt が使われているものとします。 ここで、salt なしの場合、辞書作成に必要なコストは O(D)、辞書攻撃に 必要なコストは O(N) です。 では、salt ありの場合は、どうでしょう。 全てのありうる salt に対して辞書を作成するのに必要な計算コスト および記憶コストは O(D * 2^S) ですが、これは S が十分大きければ (例えば S=64) 計算量的にも、あるいは記憶容量的にも実現不能になります。 従って、あらかじめ辞書を記憶媒体に作成するのは不可能で、全ての メッセージについて、試行するしかありません。 これに要する計算コストは、O(M*D) となり、M が大きければ、 O(N) や O(D) よりも有意に大きな値になります。 すなわち、Sとして十分大きなビット数を用いると、辞書攻撃に必要な 計算量が、min(M*D/N, M*D/D) == min(M*D/N, M) 倍程度になるわけです。