時間メモリトレードオフ

1980年にMartin Hellmanが示した手法である。値の連鎖を事前に計算しておくことで、ハッシュのような関数の逆引きをブルートフォースよりずっと速く行え、しかも完全な参照表よりはるかに少ない容量で済む。保存量を増やせば探索が短くなる、というトレードオフこそが要点だ。

2003年にPhilippe Oechslinが発表したレインボーテーブルは、連鎖の衝突を避けることでHellmanの設計を改良し、Windowsのパスワードハッシュに対して実用的なものにした。防御の鍵はハッシュそのものではなくソルトである。パスワードごとに固有のソルトを使えば、事前計算した表は一人分にしか使えず、遅いハッシュを使えば推測のたびにコストがかかる。