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

これは
- https://medium-company.com/レインボーテーブル/
- https://dev.classmethod.jp/articles/rainbowtable/
- https://it-trend.jp/encryption/article/64-0067
を読んでなんとなく理解した気持ちになったレインボーテーブルを、自分の理解をチェックするために整理した文章です。正しいかどうかはいまいち自信がない、という状態で記載しています。
レインボーテーブルを作る
ハッシュ関数と還元関数というものがある。
還元関数はハッシュから平文を取得するための関数。ただし元の平文に戻すわけではなく、ハッシュから適当な平文候補を取得するためのもの。パスワード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とマッチする値を探索していく。