レインボーテーブルは「あるハッシュ値に対して総当たり攻撃を行った際の計算結果を、別のハッシュ値を攻撃する際に使用する」というアイデアに端を発する。例えば、平文 Pi (i = 1, 2, ...) と、それらをハッシュ化した値 Ci をテーブルに格納しておき、このテーブルを逆引きすればハッシュ値から対応する平文が得られる。
ここで、あるハッシュ値 Ci を種として、次のターゲットとなる平文を適当に選ぶ関数 R を考える。ここで、関数 R には、出力が平文の候補として正当であること（例えば、パスワードが英数字しか受け付けないならば、常に英数字だけからなる文字列を出力すること）と、副作用がないという条件を満たせば、どんな関数を使用してもよい。このハッシュ値から平文候補となる値を生成する関数 R を「還元関数」(reduction function) と呼ぶ。
ハッシュ関数を H とすると、適当に選んだ最初の平文 Pi から、Pi をハッシュ関数に通した値 Ci 、次のターゲットとなる平文 Pi+1 を得るという処理の流れは次のようになる。
また、テーブル作成時に指定していなかった文字種が平文に含まれていた場合も、テーブルから平文を得ることはできない。したがって、パスワードに十分な長さと文字種をもたせることが、レインボーテーブルへの有効な対策となる。
今のところ、生成に必要な領域の問題から、8文字を超える長さの平文に対するレインボーテーブルは一般的に利用できるようにはなっていない。しかし、 LM hash （Windows のパスワードに使用されている）に対しては集中的な解析が行われており、例えば Shmoo Group によるレインボーテーブルが利用可能になっている。
用途
各種 Unix, Linux, BSD のほとんど全てではソルトつきのハッシュ関数が使われているが、ソルトなしのハッシュ関数（特に MD5）を使用しているアプリケーションは数多くある。また、 Windows NT/Windows 2000 ファミリは LAN Manager と NT Lan Manager でソルトなしのハッシュ関数を使用しており、これらに対しては盛んにレインボーテーブルの生成が行われていた。
Making a Faster Cryptanalytical Time-Memory Trade-Off, Philippe Oechslin, Advances in Cryptology - CRYPTO 2003, 23rd Annual International Cryptology Conference, Santa Barbara, California, USA, August 17--21, 2003, Proceedings. Lecture Notes in Computer Science 2729 Springer 2003, ISBN 3-540-40674-3
![{\displaystyle \left[{\begin{array}{ccccccc}P_{i}&C_{i}&P_{i+1}&C_{i+1}&P_{i+2}&\cdots &C_{i+m-1}\\P_{j}&C_{j}&P_{j+1}&C_{j+1}&P_{j+2}&\cdots &C_{j+m-1}\\P_{k}&C_{k}&P_{k+1}&C_{k+1}&P_{k+2}&\cdots &C_{k+m-1}\\\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots \\\end{array}}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/84c6ef13878c44db4bafbfdff43f79460b35646c)
