Closed1

レインボーテーブルの仕組みをなんとなく理解したような気がする

inabajunmrinabajunmr

これは

を読んでなんとなく理解した気持ちになったレインボーテーブルを、自分の理解をチェックするために整理した文章です。正しいかどうかはいまいち自信がない、という状態で記載しています。

レインボーテーブルを作る

ハッシュ関数と還元関数というものがある。

還元関数はハッシュから平文を取得するための関数。ただし元の平文に戻すわけではなく、ハッシュから適当な平文候補を取得するためのもの。パスワードAのハッシュがハッシュAだとして、還元関数(ハッシュA)はパスワードAではなくパスワードBが得られる。

ここで、以下のような計算をする。

パスワードA1 → ハッシュA1 → パスワードB1 → ハッシュB1 → パスワードC1 → ハッシュC1 ... パスワードZ1

ハッシュからパスワードを求める際には、還元関数を使う。この還元関数は毎回同じではなく、ハッシュA1からパスワードB1を求める還元関数とハッシュB1からパスワードC1を求める還元関数は別のものとなる。
ハッシュA1からパスワードB1を求める還元関数を還元関数AB、ハッシュB1からパスワードC1を求める還元関数を還元関数BCと呼ぶことにする。

上記の計算を、いろんなパスワードに対して行うと以下のようになる。

パスワードA1 → ハッシュA1 → パスワードB1 → ハッシュB1 → パスワードC1 → ハッシュC1 ... パスワードZ1
パスワードA2 → ハッシュA2 → パスワードB2 → ハッシュB2 → パスワードC2 → ハッシュC2 ... パスワードZ2
パスワードA3 → ハッシュA3 → パスワードB3 → ハッシュB3 → パスワードC3 → ハッシュC3 ... パスワードZ3
パスワードA4 → ハッシュA4 → パスワードB4 → ハッシュB4 → パスワードC4 → ハッシュC4 ... パスワードZ4
.
.
.
パスワードAn → ハッシュAn → パスワードBn → ハッシュBn → パスワードCn → ハッシュCn ... パスワードZn

この計算を行った際の最初のパスワードAと最後のパスワードZの組み合わせがレインボーテーブルの実体となる。単純なパスワードとハッシュの組み合わせのテーブルと比べて、中間の計算結果を持たなくて良い分必要なストレージが少なくて済む。

パスワードA1, パスワードZ1
パスワードA2, パスワードZ2
パスワードA3, パスワードZ3
パスワードA4, パスワードZ4
パスワードAn, パスワードZn

レインボーテーブルを使ってハッシュから平文を求める

ハッシュ1からパスワード1を求める場合、まずハッシュ1に対して 還元関数YZ(ハッシュ1)の計算を行う。この結果がレインボーテーブルのいずれかのZnにマッチした場合、例えばZ4にマッチした場合について考える。

この場合、 還元関数YZ(ハッシュ1)還元関数YZ(ハッシュY4)が同じ、ということになる。ハッシュY4のハッシュ化前の平文はパスワードY4である。このパスワードY4はパスワードA4からレインボーテーブル作成時と同様の計算をすること計算することが出来る(衝突を考えない場合)。

マッチしなかった場合、次に 還元関数YZ(ハッシュ関数(還元関数XY(ハッシュ1)))の計算する。この結果がレインボーテーブルのいずれかのZnにマッチした場合、例えばZ3にマッチした場合について考える。

パスワードX3 → ハッシュX3 → パスワードY3 → ハッシュY3 → パスワードZ3

上記のレインボーテーブル計算過程において、パスワードZ3を求めるために還元関数YZ(ハッシュ関数(還元関数XY(ハッシュX3)))という計算をしている。つまり、 還元関数YZ(ハッシュ関数(還元関数XY(ハッシュ1)))とパスワードZ3が等しいということは、ハッシュ1の平文パスワード1はパスワードX3である、といえる(衝突を考えない場合)。この場合もパスワードX3はレインボーテーブル作成時と同様の手順でパスワードA3から求めることができる。

ハッシュから平文を求める場合、このようにして平文を求めたいハッシュに対してレインボーテーブル作成時と逆向きに還元関数とハッシュ化を繰り返してパスワードZnとマッチする値を探索していく。

このスクラップは2021/07/21にクローズされました