事前計算
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/01/22 00:56 UTC 版)
「レインボーテーブル」を参照 最も基本的な形態として、事前計算とは辞書（あるいはパスワード候補の探索空間）の各語のハッシュ値を計算し、ハッシュ値の一覧を検索できるよう平文パスワードとハッシュ値のペアを保存しておくことである。こうしておけば、暗号化されたパスワード（ハッシュ値）を新しく入手した際、平文パスワードを割り出すのは造作もないことである。ソルトが適切に使われていない場合、辞書攻撃において事前計算は非常に有効であり、大容量記憶媒体の劇的な低価格化で、かなりの大型辞書を使うことも現実的になった。 さらに効率的な事前計算攻撃の手法も考えられる。すなわち時間と空間のトレードオフを考慮すると、次のような妥協点が導かれる。サイズが N の探索空間は、サイズが O(N2/3) のデータベースへ収めることができ、かつその探索にかかる時間は O(N2/3) となる。この理論は、最近になって実際の技法として洗練されたものになっている。別の例では、アルファベットと数字からなる Windows LAN Manager パスワードを二、三分で解析してしまうものもある。非常に脆弱なパスワードハッシュ法を使っていた過去の LAN Manager の場合は、さらに時間が短縮される。Windows Vista/Server 2008 よりも前の Windows では、後方互換のためパスワードの計算と保管に LAN Manager ハッシュを標準で使っていた。 事前計算と似た手法に、いわゆるメモ化がある。これは複数パスワードの解析を、一個分の解析コストで済ませるために使われる。パスワードの暗号化は、記憶済みハッシュの比較よりもずっと時間がかかるため、一度暗号化したパスワードの内容は記憶しておき、効率的な探索アルゴリズムを使って各々暗号化したパスワードと比較するのである。無論、この2つの手法は組み合わせることもできる。時間と空間のトレードオフを考慮した攻撃手法は、個別に解析するより短い時間で複数パスワードを同時に解析するよう、作り変えることができる。
※この「事前計算」の解説は、「パスワードクラック」の解説の一部です。
「事前計算」を含む「パスワードクラック」の記事については、「パスワードクラック」の概要を参照ください。
- 事前計算のページへのリンク
