レインボーテーブルでパスワードを復元してみる

# どんな記事？
この記事は[NSSOL Advent Calendar 2021](https://qiita.com/advent-calendar/2021/nssol)の13日目の記事です。

突然ですがNSSOLでは社内イベントとしてCTFを行っていたりします。
CTFといっても一般的なものとは違い、技術的な側面だけではなく謎解き的な側面や社内の知識が必要な問題があったりしてわいわいと楽しんでいます。

ぼくは今年その運営として問題を作成しました。内容としては、ハッシュ値がDBから流出した + レインボーテーブルが与えられた想定で、平文のパスワードを復元するというものです。

# レインボーテーブルとは
## レインボーテーブルの利点
ハッシュ値から平文を復元する方法として素朴に思いつくのは、考えられる平文すべてに対してハッシュ値をあらかじめ計算しておく方法です。
しかし、たとえば64種類（英数小文字 + 記号）からなる8文字のパスワードを256バイトの長さのハッシュに変換したとすると、必要な記憶領域は `64^8 * 256 byte` というとてつもなく巨大な領域が必要となります。
レインボーテーブルを利用するとこの領域を（たとえば）1GB程度に節約することができます。

## レインボーテーブルの対策
パスワードをハッシュ化して保存しても比較的簡単復元されてしまうということですが、ではどうすればいいのか？というとソルト付きハッシュを利用する対策がよく用いられます。
ソルトとは平文にランダムな文字列を加えてハッシュ化することです。詳しくは[こちら](https://qiita.com/shioshiota/items/d439e63c4ee651d956ab)をどうぞ。

## レインボーテーブルの概要
それではレインボーテーブルとはなにものかを説明していきます。
といってもすでに世の中に[わかりやすい説明](https://persol-tech-s.co.jp/corporate/security/article.html?id=57)がたくさんあるので、詳しくはそちらを参照してください。

レインボーテーブルの作り方ですが、ハッシュ値から平文を計算する還元関数というものを `n` 個用意します（`R_n` とします）。この関数はハッシュ関数 (`H`) の逆関数になっている必要はまったくありません。この `n` 個の還元関数を用いて平文 `p` に対して `c = R_N(...R_2(H(R_1(H(p))))...)` といったようにハッシュ化と還元関数適用を繰り返したハッシュ値 `c` を計算します。
この過程で計算される一連のハッシュ値、平文の集まりのことをチェインと呼びます。
レインボーテーブルで保存しておくのはチェインの先頭と最後尾の `p` と `c` の組み合わせの集合です。

では、これら `(p_i, c_i) (0<i<n)` を用いてどのようにパスワードを復元するかを説明します。
基本的な方針としては、与えられたハッシュ値がレインボーテーブルの最後のハッシュ値のいずれかではないかと仮定して検索します。そうでなかった場合は、最後列の1つ前の列のハッシュ値ではないかと仮定するとように、後ろから前に探索していきます。

step1: 与えられたハッシュ値 `C` に対して `c_i` を検索する
step2-1: 一致する `c_i` が見つかった場合、そのチェインを復元する（対応する `p_i` があるので復元可能）。復元したチェインの中の `p_i` が目標のパスワードとなる。
step2-2: 一致する `c_i` が見つからなかった場合、`C` に還元関数 `R_n` を適用する
step3: 以下step1をループ

## 還元関数について
さて先程までの説明にでてきた還元関数の作り方ですが、できるだけ異なるハッシュ値 `c, c'` について `R_i(c) != R_i(c')` であることが求められます。なぜなら `R_i(c) = R_i(c')` となるとそれ以降のチェインが重複してしまいムダとなってしまうからです。

還元関数の作り方はいろいろあると思いますが、次の実装例では[こちら](https://satob.hatenablog.com/entry/20120219/p1)のアイディアを参考にさせていただきました。
具体的には、還元関数 `R_i` はハッシュ値（今回は16進数変換している）に `i` を加算した値を36進数としてみる、という方法を利用しています。利用可能文字が `M` 種類のときに数字を `M` 進数とみることで平文空間の文字列が生成できるという発想です。

# 実装例
それではpythonを利用した実装例を載せておきます。実際のコンテストでは `make_table` で作成したレインボーテーブルを `write_table` で出力したものを配布して、 `decode` の部分を実装してもらう形式にしていました。

```python
import hashlib

class RainbowTable:
    def __init__(self, char_list, char_max_length, chain_length, n_chains):
        """
        レインボーテーブルのコンストラクタ

        Parameters
        ----------
        char_list : List[str]
            パスワードに利用できる文字のリスト
        char_max_length : int
            パスワードの最大長
        chain_length : int
            チェインの長さ
        n_chains : int
            チェインの数
        """
        self.char_list = char_list
        self.char_max_length = char_max_length
        self.chain_length = chain_length
        self.n_chains = n_chains

    def _hash_func(self, p):
        """
        パスワードからハッシュ値を計算する関数

        Parameters
        ----------
        p : str
            パスワード

        Returns
        -------
        c : str
            ハッシュ値    
        """
        return hashlib.md5(p.encode()).hexdigest()

    def _reduction(self, h, i):
        """
        i番目の還元関数

        Parameters
        ----------
        h : str
            ハッシュ値
        i : str
            何番目の関数か

        Returns
        -------
        p : str
            平文    
        """     
        p = self._make_str(int(h, base=16)+i)
        return p[:self.char_max_length]   

    def _make_chain(self, p):
        """
        pからはじまるチェインを作成する関数
 
        Parameters
        ----------
        p : str
            平文

        Returns
        -------
        chain : List[str]
            チェイン    
        """ 
        chain = []
        for i in range(self.chain_length):
            chain.append(p)
            chain.append(self._hash_func(p))
            p = self._reduction(self._hash_func(p), i)
        chain.append(p)
        return chain

    def _make_str(self, i):
        """
        整数iからそれをN（= 文字種数）進数としてみたときの文字列を作成する関数
 
        Parameters
        ----------
        i : int
            もととなる数

        Returns
        -------
        s : str
            生成後の文字列    
        """        
        s = ""
        if i == 0:
            return self.char_list[0]
        while i:
            s += self.char_list[i%len(self.char_list)]
            i //= len(self.char_list)
        return "".join(list(reversed(s)))

    def _get_match_chain(self, tail):
        l = [chain for chain in self.table if tail == chain[1]]
        retrun None if len(l) == 0 else l[0]

    def make_table(self):
        for i in range(self.n_chains):
            p = self._make_str(i)
            chain = self._make_chain(p)
            self.table.append((chain[0], chain[-1]))

    def write_table(self, file_name):
        with open(file_name, "w") as f:
            for t in self.table:
                f.write(t[0] + " " + t[1] + "\n")

    def decode(self, target):
        for i in range(self.chain_length-1, -1, -1):
            p = self._reduction(target, i)
            for j in range((self.chain_length-1)-i):
                h = self._hash_func(p)
                p = self._reduction(h, i+j+1)
            chain_t = self._get_match_chain(p)
            if chain_t is not None:
                break
        if chain_t is None:
            return None
        chain = self._make_chain(chain_t[0])
        return chain[chain.index(target)-1]

```