徳丸本始めました 配布仮想マシンの中身をいじるための設定
どうも。duckです。
昨日から急に徳丸本を読み始めました。
この本は有名なだけあり、徳丸さんの配布している(徳丸本内に記載のパスワード必須)仮想マシンを入れればWebサーバーが立ち上がり手元で本の内容を確かめられるという優れもの。
なんですが、やっぱり本の内容を自己流で改変していろいろいじってみたいのがエンジニアの性。
というわけで仮想マシン内の php ファイル(/var/www/html 内)の編集をしようとしたのですが、いくつか困ったので修正ポイントを書いておきます。
1.vi の設定追加(単純に.vimrcの設定をしてないだけっぽい)
backspace を打っても文字が消されなかったり、i を押したときにinsert モードと画面表示されなかったり不便だったので
.vimrc を新規に追加しました。
# ~/.vimrc を作成 以下中身 set showmode set nocompatible set backspace=indent,eol,start
showmode: モードを切り替えたときに画面に表示してくれる。
nocompatible: 昔のバージョンの互換を切る。方向キーとかで上下左右動かせるようになる。
backspace: backspaceが正しく動くようになる。
sudo コマンドを使うことが多いので .vimrc の設定を読み込むためにシンボリックリンクを貼りました。
sudo ln -s ~/.vimrc /root/.vimrc
これで sudo vi としたときも上記の .vimrcを読み込んでくれます。
2.日本語キーボードに変更
USキーボードの設定になったいたので日本語キーボードに変更しました。
#/etc/default/keyboard 内 #XKBMODEL="pc105" XKBMODEL="jp106"
pc105 -> jp106 にすると日本語キーボードになります。
以上です。
これで好き勝手に php ファイルをいじって遊べます。
満足。
ksnctf-2 Easy Cipher WriteUp
お久しぶりです。duckです。
最近は忙しかったりAtcoderにはまっていたりして全然更新してません。
(メンバーはほかにもいるはずなんだけどどこ行った)
今日は常設ctfやってみたので、久しぶりにWriteUp書きます。
中身はこんな感じ。
ぶっちゃけ2秒でシーザー暗号だとわかりますが、せっかくなので今回はシーザー暗号解読プログラムを作ってみましょう。
ネット上に落ちてるものは大文字と小文字を勝手に変換したり、rot13以外だった場合に探すのが面倒だったりするので
・大文字小文字を区別する
・指定文字列とマッチした結果のみ出力する
ようにceaser.pyを書いてみました。
python3 ceaser.py 暗号文のファイルパス 出力するファイルパス 探したい文字列(変換後)
のように使います。
例を挙げたほうが早いですね。
./ceaser.txtの中身が
gmbh jt evdl.
のとき
python3 ceaser.py ./crypto.txt ./ans.txt flag
をすると
./ans.txtに
flag is duck.
が書かれます。すごい。
これを使えば冒頭のシーザー暗号も簡単に復元できますね(フツーにrot13だった...)
ぜひお試しいただければと思います。
ずいぶん前に書いたので忘れてた仕様
・二つ以上のrotにmatchすると出力ファイルに追記する
コード:
CTFcode/ceaser.py at master · duck-falcon/CTFcode · GitHub
gitとか知らんがなという人とか今すぐコピペして使いたい人とかに以下全文コピーも掲載
(gitのほうはたまに更新するのでできればgitみて)
なんで文字コード使わなかったんだろう?覚えてない。
import copy import sys args = sys.argv #右回り変換 def ceaser(filepath,n,filew = "ceaser.txt",match = ""): alist = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"] Alist = ["A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z"] temp = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"] Temp = ["A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z"] i = n for v in alist: temp[i % 26] = v i += 1 i = n for V in Alist: Temp[i % 26] = V i += 1 with open(filepath) as f: contents = f.read() dict = {} Dict = {} i = 0 for v in alist: dict[v] = temp[i] i = i + 1 i = 0 for V in Alist: Dict[V] = Temp[i] i = i + 1 contents = contents.translate(contents.maketrans(dict)) contents = contents.translate(contents.maketrans(Dict)) if match in contents: with open(filew, mode='a') as F: F.write(contents) print("write success: " + str(n) + "rot ") else:print("no match") a = len(args) if a == 4: for i in range(26): ceaser(args[1],i,args[2],args[3]) else: print("please: <input_file_path> <output_file_path> <match_str>")
CRC(巡回冗長検査)
どうも。duckです。
巡回冗長検査書くよ。
理論は難しくないですが、実装に癖がありまする。
理論編
概要巡回冗長検査(巡回冗長検査 - Wikipedia)とは、誤り検出の手法の一つ。
データ送信の際にデータの破損(ビット欠落など)が起こっていないかの判定に用いる。割り算をする際の多項式(生成多項式という)の次数によってcrc-32,crc-64などと呼ばれる。生成多項式は誤り検出しやすいものを使う。(wikipedia参照、標準と反転があるが後述)
もっとも単純な誤り検出の方法としては、同じbit列を二回送信するなどがある。今回の巡回冗長検査はそれよりかは高度。
理論
一言で言うならば、二進数係数多項式(生成多項式)の割り算のあまりが巡回冗長検査。
・定義(例)
bitと二進数多項式の対応
bitをとしたとき多項式はとしてあらわす。例を見ると早い。
m=1011000なら
c=11なら
・crc計算手順
送信するメッセージをm、生成多項式をgとおく。このとき以下の手順でcrcの計算をする。
1.の(bit数-1)だけ、mの後ろに0を詰め込む。これをm'とおく。
2.を求める。
3.をで割ったあまりのbit表現がcrc。
例
m=1011010,g=10011とする。
1.m'=10110100000
2.
3.であり、をで割ったあまりを計算すると
。よってcrc=1111
・巡回冗長検査手順
1.[送信側]m'+crcを送信する
2.[受信側]m'+crcをgで割り算し、0になればビット誤りがないと判断する
理由
(係数がGF(2)のため)より、は必ずで割り切れる。
もし送られてきたに誤りがあれば、割り算の結果が0にならず、受信側は誤りに気が付ける。
実装編
・素朴な実装これ素朴にpythonで実装したの私が初めて説まである。多倍長整数と絶望的に相性が悪い。
わかりやすさのため(?)冗長に書いてある。一般的に使われてる実装は後述。
#input int def crc4(m,receive = False): keta = len(bin(m)) + 2 g = 0b10011 << (keta - 5) if not receive: crc = m << 4 else: crc = m mask = 1 for i in range(keta - 1): mask |= (mask << 1) for i in range(keta - 4): if crc & 2 ** (keta - 1): crc = crc ^ g crc = crc << 1 crc &= mask else: crc = crc << 1 crc &= mask return crc >> (keta - 4)
receive=Trueとすると、受信時の設定でかいた。
実行例
#送信 print(bin(crc4(0b1011011))) 0b1100 #受信 print(bin(crc4(0b10110111100,True))) 0b0
うまくいってる。
しかしコードの説明がうまくできないので図を載せておく。(わかるとはいっていない)
コードと図の対応を説明する。
コードのketaは図の赤い四角=crcと書いてある部分のbit数に対応。
コードのgは図のgに対応。
コードのmaskはketaのbit数分1を並べた数字で、crcのサイズを固定するのに使用。
2**(keta - 1)は先頭が1で他は0でketa数分のbitをもつ数。こんなん自分で割り算やってみないとわからんて。(丸投げ)
・反転実装
pythonではこっちが主流なはず。実装の難易度が違いすぎるから。
多項式の読み方を逆にする。(次数が大きい項が右端になる。)
gは適した固定の多項式を使いたい事情がある。(Wikipediaみて)
例
m=1011010,g=11001(上の例の多項式と同じ)とする。
1.m'=00001011010
2.
3.であり、をで割ったあまりを計算すると
。よってcrc=0111
これをコードに落とす。三項演算子使えとか言わない。上の例でもやめといたし。
def crc4_reverse(m): keta = len(bin(m)) + 2 g = 0b11001 crc = m for i in range(keta - 4): if crc & 1: crc = crc ^ g crc = crc >> 1 else: crc = crc >> 1 return crc
receiveの設定しなくてもいいしサイコーですね。実行例
#送信 print(bin(crc4_reverse(0b1011010))) 0b111 #受信 crcのつける場所が前になることに注意 print(bin(crc4_reverse(0b01111011010))) 0b0
Wikipediaに標準と反転の生成多項式のbit表現がわざわざかいてあるけど、つまるところ同じ多項式。
高速化
・gの先頭の1は実はいらない割られる数に1が立っているかの判定だけでよいため。
crc & 2 ** (keta - 1) や crc & 1
で事足りる。どうせxorした結果の先頭は0になってるからね。
wikipediaは最初から先頭の1をはしょった形で書かれてる。
・8bit分の割り算を先にしてテーブル化しておく
前回の記事で思いついたけど実装しなかったって言ってたやつ。
いやあ標準的に使われてるのねさすがです。
これも反転のほうが有利だね。標準だと固定長がmによって変わるから、mの長さがわかってからじゃないとテーブル計算ができない。
wikipediaにあわせてcrc32_reverseの例だけ図に起こした。
今まで例で使ってたcrc4_reverseでも同じ作業できる。
・謎
wikipedia見ればわかるがなぜかcrc32のときは
初期値をcrc=0xffffffffとしcrc^0xffffffffをreturnする風潮がある。
考えたけど意味は不明だった。
ちなみに私の実装例はすべてcrc=0を初期値としている実装である。
まあそういこともあるんだと思っておく。
2019/10/27 追記
ググったらそれらしい理由があった
— 道路 (@Nperair) October 25, 2019
0固定故障への対策らしいhttps://t.co/Hzel27DQhx
有力情報を頂いた。リンク先を見ると、全部0になるバグ?の判定ができるためだそう。
参考:Cyclic Redundancy Check(CRC)を理解する - Qiita
巡回冗長検査 - Wikipedia
正直後半書くの飽きてた。4日くらいかいてるからなこれ。
SECCON CTF 2019 Crypto Writeup(+3) Crypto道場八[13/100]
どうも。duckです。
今回はCrypto全部解きました。及第点といったところでしょう。
本戦への壁は厚いっすね。くそう。
1.coffee_break
2.ZKPay
3.Crazy Repetition of Codes
1.coffee_break
貼るけど一応元ファイルもおいとく。
file:encrypt.py
Dropbox - encrypt.py_b7d6c2e28d7f4eee9db8673b5c82191e54d1fea1 - Simplify your life
暗号文は問題文に書いてあった。
cipher.txt
FyRyZNBO2MG6ncd3hEkC/yeYKUseI/CxYoZiIeV2fe/Jmtwx+WbWmU1gtMX9m905
encrypt.py
import sys from Crypto.Cipher import AES import base64 def encrypt(key, text): s = '' for i in range(len(text)): s += chr((((ord(text[i]) - 0x20) + (ord(key[i % len(key)]) - 0x20)) % (0x7e - 0x20 + 1)) + 0x20) return s key1 = "SECCON" key2 = "seccon2019" text = sys.argv[1] enc1 = encrypt(key1, text) cipher = AES.new(key2 + chr(0x00) * (16 - (len(key2) % 16)), AES.MODE_ECB) p = 16 - (len(enc1) % 16) enc2 = cipher.encrypt(enc1 + chr(p) * p) print(base64.b64encode(enc2).decode('ascii'))
自作encrypt関数とAESで暗号化してますがAESのkeyがすでにわかっているのでAESはないも同然。Base64は暗号化ですらない。一瞬でデコードできる。
よって、自作encrypt関数を復号する関数を書くだけでよい。
数式書いてた紙をなくしたので、珍しくコードを貼っておく。なんかちょっとしたmodだった気がする。
def decrypt(key,enc): dec = '' for i in range(len(enc)): num = ord(enc[i]) + 32 - ord(key[i % len(key)]) if 126 > num > 33: dec += chr(num) elif 126 > num + 95 > 33: dec += chr(num+95) return dec
アスキーコードで文字を表してるのが33~126くらいだったと記憶している。
だから上のような書き方だと思われる。たぶん。しかもこれなんか不備があった気がするけど、答え出たから無視した気がする。
from Crypto.Cipher import AES import base64 key1 = "SECCON" key2 = "seccon2019" C = "FyRyZNBO2MG6ncd3hEkC/yeYKUseI/CxYoZiIeV2fe/Jmtwx+WbWmU1gtMX9m905" enc2 = base64.b64decode(C) cipher = AES.new(key2 + chr(0x00) * (16 - (len(key2) % 16)), AES.MODE_ECB) enc1 = cipher.decrypt(enc2) ans = decrypt(key1,enc1) print(ans)
これで答えが出るはず。たぶん。
2.ZKPay
URLにアクセスして、Registerしたあとログインする。
home画面はこんな感じ。1000000$むしり取ればフラッグが見れるっぽい。最初はrootが500くれてるだけの画面だったが、いろいろいじってたら今はこんな感じになってる。
send画面。人にお金を送るためのQRコードを発行できる。ただし持ってるお金以上送ろうとすると怒られる。
もらったQRコードをここで読んでみた。(QRコードをパソコンで読み取る(インストール不要))
username=egg&amount=100&proof=MI0bWQyatoUpSAwexg5YfHsb16bVb/HvGO9S73dOnlUiMSAwjDWHNyfVBJu4LboVjYNRHX7Amd268Hn42CJCz9ACog8wCjDxUF86bhqo/gNRrX2hVEmmr3TVD5y/oyWcV0qhdI9sCgfs4LBHdYEZ88Y2t9mQ+y8reD9wKBg50HvHYLs+wgwZMSAwEqtINttKiFkBf1z0oRDZVNzlDMHIcNBmpWPqsspe5hYwCjChQs4pLc1BI+RcZEcwnlIVXKMg3DtLCpmb2ae68wVpFjAgMICbAKUpCUTEkvPqCgAyEn495kmmuIHHwvAMOcgoBBckMAowc88QQ3fzC/fScQ/bYjgWatbrwSv6oC5b7FKjGVe8UgkxCjCFM8gQREFJNGRpfKk0oxjHDid21FI+kyBx8grtsf0vKjAK&hash=c728621fcb2fc4fffb72f4ce548a5d04b8a7424199f022d0377c2f99e76564d9
これをrecieve画面で読み込むとお金をゲットできる。
ユーザーの初期の手持ちは500しかなく、ユーザーをたくさん作って送り付けてもいいが、ちまちまやってられないので、借金を背負ってもらってゲームを終わらせる。
username=egg&amount=-1000000&proof=MI0bWQyatoUpSAwexg5YfHsb16bVb/HvGO9S73dOnlUiMSAwjDWHNyfVBJu4LboVjYNRHX7Amd268Hn42CJCz9ACog8wCjDxUF86bhqo/gNRrX2hVEmmr3TVD5y/oyWcV0qhdI9sCgfs4LBHdYEZ88Y2t9mQ+y8reD9wKBg50HvHYLs+wgwZMSAwEqtINttKiFkBf1z0oRDZVNzlDMHIcNBmpWPqsspe5hYwCjChQs4pLc1BI+RcZEcwnlIVXKMg3DtLCpmb2ae68wVpFjAgMICbAKUpCUTEkvPqCgAyEn495kmmuIHHwvAMOcgoBBckMAowc88QQ3fzC/fScQ/bYjgWatbrwSv6oC5b7FKjGVe8UgkxCjCFM8gQREFJNGRpfKk0oxjHDid21FI+kyBx8grtsf0vKjAK&hash=c728621fcb2fc4fffb72f4ce548a5d04b8a7424199f022d0377c2f99e76564d9
amount=-1000000となるQRコードはsendからだと作れない仕様なので、自分で作ってreceiveに流せばおけ。
認証に使われってるっぽいproofとhashを復元するのかと思って無駄に時間食った。つらい。
3.Crazy Repetition of Codes
code:
import os from Crypto.Cipher import AES def crc32(crc, data): crc = 0xFFFFFFFF ^ crc for c in data: crc = crc ^ ord(c) for i in range(8): crc = (crc >> 1) ^ (0xEDB88320 * (crc & 1)) return 0xFFFFFFFF ^ crc key = b"" crc = 0 for i in range(int("1" * 10000)): crc = crc32(crc, "TSG") assert(crc == 0xb09bc54f) key += crc.to_bytes(4, byteorder='big') crc = 0 for i in range(int("1" * 10000)): crc = crc32(crc, "is") key += crc.to_bytes(4, byteorder='big') crc = 0 for i in range(int("1" * 10000)): crc = crc32(crc, "here") key += crc.to_bytes(4, byteorder='big') crc = 0 for i in range(int("1" * 10000)): crc = crc32(crc, "at") key += crc.to_bytes(4, byteorder='big') crc = 0 for i in range(int("1" * 10000)): crc = crc32(crc, "SECCON") key += crc.to_bytes(4, byteorder='big') crc = 0 for i in range(int("1" * 10000)): crc = crc32(crc, "CTF!") key += crc.to_bytes(4, byteorder='big') flag = os.environ['FLAG'] assert(len(flag) == 32) aes = AES.new(key, AES.MODE_ECB) encoded = aes.encrypt(flag) assert(encoded.hex() == '79833173d435b6c5d8aa08f790d6b0dc8c4ef525823d4ebdb0b4a8f2090ac81e')
なかなかにクレイジー。
range(int("1" * 10000))
とくにここ。(10000個並んでる。)回も crc32を使って計算している。
方針は単純。どっかでループすると思われるので、それを特定する。ランダム要素がないので最悪でもcrc32を回ぶん回せばループが発覚する。鳩ノ巣原理。
あとはを計算して、ループの先だけ計算すればよし。
回ぶん回すのも頭おかしいと思ったが、ほとんどbit演算だったので意外に行けた。高速化するためにC++で書きなおしたけど。
一応アルゴリズムごと高速化できるアイデアもあったが、実装しなくてもいけたのでお蔵入りした。
こつこつcrcを計算したらあとは以下のコードで復号できた。
import os from Crypto.Cipher import AES key = b"" crc = 0xb09bc54f key += crc.to_bytes(4, byteorder='big') crc = 3836056187 key += crc.to_bytes(4, byteorder='big') crc = 2369777541 key += crc.to_bytes(4, byteorder='big') crc = 3007692607 key += crc.to_bytes(4, byteorder='big') crc = 1526093488 key += crc.to_bytes(4, byteorder='big') crc = 3679021396 key += crc.to_bytes(4, byteorder='big') text='79833173d435b6c5d8aa08f790d6b0dc8c4ef525823d4ebdb0b4a8f2090ac81e' bin=binascii.unhexlify(text) aes = AES.new(key, AES.MODE_ECB) flag = aes.decrypt(bin) print(flag)
眠すぎて何を書いてるかもよくわからない。お休み。
第0.5回 RSAへのAttack ~RSA-CRT~
どうも。duckです。
二回目にして唐突な0.5刻み。マイナーバージョンアップかな?
.5では、Attackじゃないけど知っておかないとCTFで困る(困った)知識について書いていきます。
今回のRSA-CRTだったり、RSA-OAEPだったりですね。
RSA-CRT
一言でいうと、復号の際の高速化処理のために中国剰余定理を使う手法のこと。
ChineseReductionTheoremゆえにCRT。
まずは、ふつーの復号を見よう。
一ミリも面白くない。まあこの計算が重いので軽くしようぜってこと。
まずは中国剰余定理でばらして復号してみる。
の連立合同方程式の解はの中にあり中国剰余定理で計算できる。
これが実はになる。
なぜか。
となる。
(フェルマーの小定理:CTFで使う数学 前編 - CTFと共に生きる)
対称性を考慮し、上の連立合同方程式は
とかける。これを(*)とおく。
よって
(:整数)と書け、両辺引くことにより
。は互いに素だから
つまり。
実際にを求めるために、
とおく。
中国剰余定理の解の求め方としてGarner法を思い出すと
ただし、
この式がよく復号のところで出てくる。
ここからさらに高速化する。
を使っていたが、これは
を用いても同じでありこっちのほうが計算が早い。
ただし、
を満たす。
、は整数。
最後のはフェルマーの小定理による。
(*)と同じになったことからこの解はとなることがわかる。
まとめるとを
を満たすものとし、
を考える。
この連立合同方程式の解はとなり
実際に
、
とすると
、と求められる。
こっちのがとして計算するよりも断然はやい。
HITCON CTF 2019 Crypto Writeup(+1) Crypto道場七[10/100]
どうも。duckです。
HITCONCTFやってきました。辛うじて1題解けたのでWriteup書きます。
1.Lost Modulus Again
今回もファイル共有から。
output
Dropbox - output - Simplify your life
prob.py
Dropbox - prob.py - Simplify your life
短いのでprob.pyは貼る。
from Crypto.Util.number import * class Key: def __init__(self, bits): assert bits >= 512 self.p = getPrime(bits) self.q = getPrime(bits) self.n = self.p * self.q self.e = 0x100007 self.d = inverse(self.e, (self.p-1)*(self.q-1)) self.dmp1 = self.d%(self.p-1) self.dmq1 = self.d%(self.q-1) self.iqmp = inverse(self.q, self.p) self.ipmq = inverse(self.p, self.q) def encrypt(self, data): num = bytes_to_long(data) result = pow(num, self.e, self.n) return long_to_bytes(result) def decrypt(self, data): num = bytes_to_long(data) v1 = pow(num, self.dmp1, self.p) v2 = pow(num, self.dmq1, self.q) result = (v2*self.p*self.ipmq+v1*self.q*self.iqmp) % self.n return long_to_bytes(result) def __str__(self): return "Key([e = {0}, n = {1}, x = {2}, y = {3}])".format(self.e, self.d, self.iqmp, self.ipmq) def main(): key = Key(1024) flag = open('flag').read() encrypt_flag = key.encrypt(flag) assert key.decrypt(encrypt_flag) == flag print key print encrypt_flag.encode('hex') if __name__ == '__main__': main()
いつものごとく長い文字を置き換える。
。dmp1,dmp2はRSA-CRTでの処理高速化に使う項なので無視。
ふつーのRSA-CRTならかの片方でいいのでなんか変だな?と思っておく。
次に
return "Key([e = {0}, n = {1}, x = {2}, y = {3}])".format(self.e, self.d, self.iqmp, self.ipmq)
を見ると、やべえ秘密鍵dが流出してるうける。
が、がないので復号無理。
というわけでを求めに行く。
given:
の周りから情報を抜き出す。
からを求めていることを考えると、拡張ユークリッドの互除法より
のから
としているはず。
とするとは負の数であり、bit数を考えるとしかない。
よって。
変形して
。
に対する拡張ユークリッの互除法からが求まり
と書ける。
とおくと、②の両辺にをかけて
、:整数 を得る。
特殊解を用いて
の一般解がと表せる。
①からこの解のなかにとなるものがあるはずなので、に対してブルートフォースする。
得られたとしたときのが正しいの判定には、を満たすかを用いた。
探索範囲をbit数から絞りこんでなお12分かかった。
p=166564961597106229342966450443567005929416288372170308009700499465281616388542030734600089639466922805142577582894052957547174764252067983124558747593344882775630971023610755334859287415681252266825395627416912206349590353878868107848653100299011246746851490276537231636534462821659050996145878589643016881929 q=135136928230019073146158752709151576119155564982754768027494878210491711363872928718225319693774548227271767324623087432404412585662574641211148315864508708036871556964386141364368797168619283425834644924573664613109609076319077176698754203574237779054129492453503018443013301394555677417140681949745410143477
がわかったので解けた。を暗号文とする。
m=pow(C,d,N)
flag:hitcon{1t_is_50_easy_t0_find_th3_modulus_back@@!!@!@!@@!}
flagをみてもピンとこないあたり想定解ではないんでしょうか?英語力不足で意味をくみ取れていないだけ?
レインボーテーブルを実装してみた
どうも。duckです。
名前がダサいことで有名なレインボーテーブルを実装してみました。ハッシュを調べるとよく出てくるやつです。
ハッシュ概要
ハッシュ関数をとする。あるデータに対して、そのハッシュ値を
と表す。
この時、ハッシュ値からは元のデータを計算できない。これがハッシュ関数の満たすべき性質である。
この性質から、認証によく使われるが詳細は割愛。
アタッカーの目線から考えるとハッシュから元のデータを逆算したい。だができない。
そこで、事前にあらゆるデータを計算し、そのハッシュ値をデータベースに保存して逆引きすればよいという発想になる。
しかし、この方法には膨大な記憶領域を必要とするという弱点がある。
そこで考え出されたのがレインボーテーブルである。
理論編
レインボーテーブルとは、計算コストがかかる代わりに、データベースの保存領域を減らすものである。例えば以下のレインボーテーブルの例ではデータベースに(最初と最後)のみ保存すれば、のすべてのハッシュを逆算できる。
:リダクション関数、ハッシュ値からデータを作れれば何でもよい。
例としての逆算を考える。
手順は以下の通り
①がデータベースと一致するか調べる。一致すると復元できる。
②を計算する。
③を計算する。
①に戻る。
は上記の手順を2周したときにデータベースと一致する。レインボーテーブル全体は4周(chainとよぶ)しているため、以下の手順でからを復元できる。
chainを増やせばハッシュのヒット率が上がり復元できる確率が高まる。しかし計算コストは増大する。
そこで並列計算を考える。同じ仕組みの列を増やす。
例えば、
とし
データベースにはを保存する。これで手順の最大周回数を保ったまま、ヒット率を上げられた。
の決め方にほとんど言及していないがそれは実践編を参考にしてほしい。
ぶっちゃけなんでもいい。
実践編
まずはコード。
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"
今回の例
:乱数を使って生成
ハッシュ:md5を使用
:ハッシュ値の下四桁をとってくるだけ
一般にはほしいデータから決める。
例えば英数字8桁(パスワードにありがち)のデータのハッシュを復元したいなら、はハッシュ値から英数字8桁を生成する関数を考えるし、
数字のみ6桁~10桁のデータのハッシュ値を復元したいなら、はハッシュ値から数字のみ6桁~10桁を生成する関数を考える。
今回は数字とa~fのみ使う四桁のデータを復元できるようにを決めた。
実行例
r=ReinbowTable(1000,1000) r.create_rainbow_table() print(r.check_rainbow_table('ad7ed5d47b9baceb12045a929e7e2f66'))
結果
6387
やったぜ。復元できた!
ただ、今回の方法では、a~fのみ使う四桁のデータのハッシュを使っても復元できるハッシュが限られてしまうことがわかった。
r=ReinbowTable(1000,1000) r.create_rainbow_table() print(r.check_rainbow_table('81dc9bdb52d04dc20036dbd8313ed055'))
結果
not found
81dc9bdb52d04dc20036dbd8313ed055は1234のハッシュ値なのだが何回やっても復元できなかった。
は乱数を使っているので、そのうち復元できそうなのに。
おそらく、の決め方が悪く、偏ってしまっているのだと考えられる。
の際に現れるに偏りを生じ、となりにくい(もしくはならない)ということかと。
こういった偏りをなくすようには決定しないといけないということか。md5の中身まで理解しないとそこまでは無理。
は何でもいいといったけれど、意外にも職人芸だった。
実装してみると気が付くこともある。