レインボーテーブル入門
出田 守です。 情報セキュリティに興味を持ち、独学で勉強中です。 主にPythonを使用します。時々勉強のためにCを使用することもあります。
ゴール
レインボーテーブルについて理解したことを簡単に説明して、実際に実装してみます。
レインボーテーブルとは
あるハッシュ値から平文を得るために使われる技術です。
最も単純な方法
あるハッシュ値から平文を得るための最も単純な方法は、ハッシュ値と平文のペアから成るテーブルを作って、あるハッシュ値で検索をすれば実現できます。例えば、以下のテーブルから「password」のmd5ハッシュ値「5f4dcc3b5aa765d61d8327deb882cf99」を検索することで元の平文「password」が得られます。
| ハッシュ値 | 平文 |
|---|---|
| e10adc3949ba59abbe56e057f20f883e | 123456 |
| 5f4dcc3b5aa765d61d8327deb882cf99 | password |
| 25f9e794323b453885f5181f1b624d0b | 123456789 |
| ... | ... |
ただ、このテーブルではかなり大きなサイズになってしまいます。
そこで考えられたのがレインボーテーブルです。
レインボーテーブル作成
まず、レインボーテーブルを作成するにあたり、二つの関数を用意します。
- ハッシュ関数: 平文からハッシュ値を得るための関数です。
- 還元関数: ハッシュ値から無造作に平文を選択する関数です。ただし、同じハッシュ値なら常に同じ平文を選択する必要があります。この条件を満たしていればどのような関数でも良いようです。
次に、上記二つの関数を使って、チェインを作ります。具体的には以下のように作ります。
- 平文からハッシュ関数を使って、ハッシュ値を得ます。
- 得られたハッシュ値を還元関数を使って、別の平文を得ます。
- さらにその別の平文をハッシュ関数を使って、ハッシュ値を得ます。
- 1.~3.を決められたチェインの長さまで繰り返します。ただし、還元関数は列毎に別の平文を得られるようにします。
- 最後に、先頭と末尾の平文のみを残したものが一つのチェインとなります。
このチェインを決められた数まで作成したものがレインボーテーブルとなります。
ここまでを一度実装してみます。
還元関数のアイデアは以下のページを参考にしました。
d.hatena.ne.jp
また、レインボーテーブル作成時にtqdmライブラリを使って、プログレスバーを表示していますので、tqdmをインストールする必要があります。
import hashlib import itertools import random from tqdm import tqdm class RainbowTable(object): NUM = "0123456789" LOWER = "abcdefghijklmnopqrstuvwxyz" UPPER = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" def __init__(self, func_hash, char_type, char_length, chain_length, n_chains): self.func_hash = self.md5 if func_hash=="md5" else self.sha1 self.char_type = char_type self.chars = {i:c for i, c in enumerate(char_type)} self.char_length = char_length self.chain_length = chain_length self.n_chains = n_chains self.rainbowtable = [] if self.char_length>16: print("Please char_length must be 16 or less.") exit(1) def md5(self, p): return hashlib.md5(p.encode()).hexdigest() def sha1(self, p): return hashlib.sha1(p.encode()).hexdigest() def reduction(self, h, i): p = "" i = int(h, 16)+i while i: p += self.chars[i%len(self.char_type)] i //= len(self.char_type) return p[:self.char_length] def chain(self, p): ch = [] for i in range(self.chain_length): ch.extend([p, self.func_hash(p)]) # plain + hash p = rt.reduction(ch[-1], i) # reduction plain ch.append(p) return ch def rainbow_table(self, path): fp = open(path, "w") p = itertools.product(self.char_type, repeat=self.char_length) # product all patern in char_type for i, s in enumerate(tqdm(p), start=1): s = "".join(s) chain = self.chain(s) # self.rainbowtable.append([chain[0], chain[-1]]) # append only chain head and chain tail fp.writelines(" ".join([chain[0], chain[-1]])) fp.write("\n") # write format: "head_chain tail_chain\n" if self.n_chains and i>=self.n_chains: # continue if n_chains==0 or i<n_chains, n_chains==0 is all patern break fp.close() def read_table(self, path): fp = open(path, "r") self.rainbowtable = [s.strip().split(" ") for s in fp.readlines()] # read format: "head_chain tail_chain\n" fp.close() if __name__ == "__main__": p = "00000000" rt = RainbowTable(func_hash="md5", char_type=RainbowTable.NUM+RainbowTable.LOWER, char_length=8, chain_length=1000, n_chains=1000) rt.rainbow_table("sample.rt") rt.read_table("sample.rt")
解読
あるハッシュ値からレインボーテーブルを使って平文を得る方法が以下になります。
- あるハッシュ値から末尾で使用した還元関数を使って、平文を得ます。
- 得られた平文とレインボーテーブルの末尾の平文が一致するか確かめます。
ここまでを実装してみます。
... class RainbowTable(object): ... def decode(self, t): if not self.rainbowtable: return False for i in range(self.chain_length-1, -1, -1): # column p = self.reduction(t, i) # to plain for j in range((self.chain_length-1)-i): # loop diff from tail h = self.func_hash(p) p = self.reduction(h, i+j+1) matched_chain = self.match_tail(p) if matched_chain: break if not matched_chain: return False matched_chain = self.chain(matched_chain[0]) return matched_chain[matched_chain.index(t)-1] ... if __name__ == "__main__": ... print("decoded =", rt.decode(rt.md5(p)))
