レインボーテーブルを実装してみた

どうも。duckです。
~~名前がダサいことで有名な~~レインボーテーブルを実装してみました。ハッシュを調べるとよく出てくるやつです。

ハッシュ概要

ハッシュ関数を ${\rm H}(x)$ とする。
あるデータ $d$ に対して、そのハッシュ値を
$h={\rm H}(d)$ と表す。
この時、ハッシュ値 $h$ からは元のデータ $d$ を計算できない。これがハッシュ関数の満たすべき性質である。
この性質から、認証によく使われるが詳細は割愛。

アタッカーの目線から考えるとハッシュから元のデータを逆算したい。だができない。
そこで、事前にあらゆるデータを計算し、そのハッシュ値をデータベースに保存して逆引きすればよいという発想になる。
しかし、この方法には膨大な記憶領域を必要とするという弱点がある。
そこで考え出されたのがレインボーテーブルである。

理論編

レインボーテーブルとは、計算コストがかかる代わりに、データベースの保存領域を減らすものである。

例えば以下のレインボーテーブルの例ではデータベースに $d_{11},h_{14}$ (最初と最後)のみ保存すれば、 $h_{11},h_{12},h_{13},h_{14}$ のすべてのハッシュを逆算できる。
$d_{11} \xrightarrow{{\rm H}} h_{11} \xrightarrow{{\rm R}} d_{12} \xrightarrow{{\rm H}} h_{12} \xrightarrow{{\rm R}} d_{13} \xrightarrow{{\rm H}} h_{13} \xrightarrow{{\rm R}} d_{14} \xrightarrow{{\rm H}} h_{14}$
${\rm R}$ :リダクション関数、ハッシュ値からデータを作れれば何でもよい。

例として $h = h_{12}$ の逆算を考える。
手順は以下の通り
① $h$ がデータベースと一致するか調べる。一致すると復元できる。
② $h \xrightarrow{{\rm R}} d$ を計算する。
③ $d \xrightarrow{{\rm H}} h$ を計算する。
①に戻る。

$h = h_{12}$ は上記の手順を２周したときにデータベースと一致する。レインボーテーブル全体は４周（chainとよぶ）しているため、以下の手順で $d_{11}$ から $d$ を復元できる。
$d_{11} \xrightarrow{{\rm H}} h \xrightarrow{{\rm R}} d$

chainを増やせばハッシュのヒット率が上がり復元できる確率が高まる。しかし計算コストは増大する。
そこで並列計算を考える。同じ仕組みの列を増やす。

例えば、
$d_{11} \xrightarrow{{\rm H}} h_{11} \xrightarrow{{\rm R}} d_{12} \xrightarrow{{\rm H}} h_{12} \xrightarrow{{\rm R}} d_{13} \xrightarrow{{\rm H}} h_{13} \xrightarrow{{\rm R}} d_{14} \xrightarrow{{\rm H}} h_{14}$
$d_{21} \xrightarrow{{\rm H}} h_{21} \xrightarrow{{\rm R}} d_{22} \xrightarrow{{\rm H}} h_{22} \xrightarrow{{\rm R}} d_{23} \xrightarrow{{\rm H}} h_{23} \xrightarrow{{\rm R}} d_{24} \xrightarrow{{\rm H}} h_{24}$
$d_{31} \xrightarrow{{\rm H}} h_{31} \xrightarrow{{\rm R}} d_{32} \xrightarrow{{\rm H}} h_{32} \xrightarrow{{\rm R}} d_{33} \xrightarrow{{\rm H}} h_{33} \xrightarrow{{\rm R}} d_{34} \xrightarrow{{\rm H}} h_{34}$
とし
データベースには $d_{11},h_{14},d_{21},h_{24},d_{31},h_{34}$ を保存する。これで手順の最大周回数を保ったまま、ヒット率を上げられた。

$d_{11},d_{12},d_{13},{\rm R}$ の決め方にほとんど言及していないがそれは実践編を参考にしてほしい。
ぶっちゃけなんでもいい。

実践編

まずはコード。

from hashlib import md5
from random import randint

class ReinbowTable():
    def __init__(self,line,chain):
        self.line = line
        self.chain = chain
        self.rainbow_table = []
        self.seed = 0

    def generate_line(self):
        rainbow_line=[]
        self.seed = format(randint(0,2**16 - 1),'x')
        rainbow_line.append(self.seed)
        for _ in range(self.chain):
            hash = md5(self.seed.encode()).hexdigest()
            rainbow_line.append(hash)
            self.seed = format(self.reduction(hash),'x')
        return [rainbow_line[0],rainbow_line[-1]]

    def create_rainbow_table(self):
        for _ in range(self.line):
            self.rainbow_table.append(self.generate_line())

    def reduction(self,hash):
        return int(hash,16) & 0xffff

    def check_rainbow_table(self,check_hash):
        init_check_hash = check_hash
        chainline = []
        for chain in range(self.chain):
            line = 0
            flag = False
            for rainbow_hash in self.rainbow_table:
                if check_hash == rainbow_hash[-1]:
                    chainline.append([chain,line])
                line += 1
            check = format(self.reduction(check_hash),'x')
            check_hash = md5(check.encode()).hexdigest()
        for c,l in chainline:
            seed = self.rainbow_table[l][0]
            for _ in range(self.chain - c - 1):
                hash = md5(seed.encode()).hexdigest()
                seed = format(self.reduction(hash),'x')
            if md5(seed.encode()).hexdigest() == init_check_hash:
                return seed
        return "not found"

今回の例
$d_{11},d_{12},d_{13}$ ：乱数を使って生成
ハッシュ：md5を使用
${\rm R}$ ：ハッシュ値の下四桁をとってくるだけ

一般に ${\rm R}$ はほしいデータから決める。
例えば英数字８桁（パスワードにありがち）のデータのハッシュを復元したいなら、 ${\rm R}$ はハッシュ値から英数字８桁を生成する関数を考えるし、
数字のみ６桁～１０桁のデータのハッシュ値を復元したいなら、 ${\rm R}$ はハッシュ値から数字のみ６桁～１０桁を生成する関数を考える。

今回は数字とa~fのみ使う四桁のデータを復元できるように ${\rm R}$ を決めた。

実行例

r=ReinbowTable(1000,1000)
r.create_rainbow_table()
print(r.check_rainbow_table('ad7ed5d47b9baceb12045a929e7e2f66'))

結果

やったぜ。復元できた！

ただ、今回の方法では、a~fのみ使う四桁のデータのハッシュを使っても復元できるハッシュが限られてしまうことがわかった。

r=ReinbowTable(1000,1000)
r.create_rainbow_table()
print(r.check_rainbow_table('81dc9bdb52d04dc20036dbd8313ed055'))

結果

not found

81dc9bdb52d04dc20036dbd8313ed055は1234のハッシュ値なのだが何回やっても復元できなかった。
$d_{11},d_{12},d_{13},...$ は乱数を使っているので、そのうち復元できそうなのに。

おそらく、 ${\rm R}$ の決め方が悪く、偏ってしまっているのだと考えられる。
$h \xrightarrow{{\rm R}} d$ の際に現れる $d$ に偏りを生じ、 $d=1234$ となりにくい（もしくはならない）ということかと。
こういった偏りをなくすように ${\rm R}$ は決定しないといけないということか。md5の中身まで理解しないとそこまでは無理。
${\rm R}$ は何でもいいといったけれど、意外にも職人芸だった。

実装してみると気が付くこともある。