どんな記事？
この記事はNSSOL Advent Calendar 2021の13日目の記事です。
突然ですがNSSOLでは社内イベントとしてCTFを行っていたりします。
CTFといっても一般的なものとは違い、技術的な側面だけではなく謎解き的な側面や社内の知識が必要な問題があったりしてわいわいと楽しんでいます。
ぼくは今年その運営として問題を作成しました。内容としては、ハッシュ値がDBから流出した + レインボーテーブルが与えられた想定で、平文のパスワードを復元するというものです。
レインボーテーブルとは
レインボーテーブルの利点
ハッシュ値から平文を復元する方法として素朴に思いつくのは、考えられる平文すべてに対してハッシュ値をあらかじめ計算しておく方法です。
しかし、たとえば64種類（英数小文字 + 記号）からなる8文字のパスワードを256バイトの長さのハッシュに変換したとすると、必要な記憶領域は 64^8 * 256 byte というとてつもなく巨大な領域が必要となります。
レインボーテーブルを利用するとこの領域を（たとえば）1GB程度に節約することができます。
レインボーテーブルの対策
パスワードをハッシュ化して保存しても比較的簡単復元されてしまうということですが、ではどうすればいいのか？というとソルト付きハッシュを利用する対策がよく用いられます。
ソルトとは平文にランダムな文字列を加えてハッシュ化することです。詳しくはこちらをどうぞ。
レインボーテーブルの概要
それではレインボーテーブルとはなにものかを説明していきます。
といってもすでに世の中にわかりやすい説明がたくさんあるので、詳しくはそちらを参照してください。
レインボーテーブルの作り方ですが、ハッシュ値から平文を計算する還元関数というものを 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') となるとそれ以降のチェインが重複してしまいムダとなってしまうからです。
還元関数の作り方はいろいろあると思いますが、次の実装例ではこちらのアイディアを参考にさせていただきました。
具体的には、還元関数 R_i はハッシュ値（今回は16進数変換している）に i を加算した値を36進数としてみる、という方法を利用しています。利用可能文字が M 種類のときに数字を M 進数とみることで平文空間の文字列が生成できるという発想です。
実装例
それではpythonを利用した実装例を載せておきます。実際のコンテストでは make_table で作成したレインボーテーブルを write_table で出力したものを配布して、 decode の部分を実装してもらう形式にしていました。
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]