CRC(巡回冗長検査)

どうも。duckです。
巡回冗長検査書くよ。
理論は難しくないですが、実装に癖がありまする。

今回の流れ
理論編
実装編
高速化



理論編

概要
巡回冗長検査(巡回冗長検査 - Wikipedia)とは、誤り検出の手法の一つ。
データ送信の際にデータの破損(ビット欠落など)が起こっていないかの判定に用いる。割り算をする際の多項式(生成多項式という)の次数によってcrc-32,crc-64などと呼ばれる。生成多項式は誤り検出しやすいものを使う。(wikipedia参照、標準と反転があるが後述)
もっとも単純な誤り検出の方法としては、同じbit列を二回送信するなどがある。今回の巡回冗長検査はそれよりかは高度。

理論
一言で言うならば、二進数係数多項式(生成多項式)の割り算のあまりが巡回冗長検査。

・定義(例)
bitと二進数多項式の対応
bitをbとしたとき多項式f_bとしてあらわす。例を見ると早い。
m=1011000なら
f_m=1*x^6 + 0 * x^5 + 1 * x^4 + 1 * x^3 + 0* x^2+ 0*x + 0=x^6+x^4+x^3
c=11なら
f_c=1*x+1=x+1

crc計算手順
送信するメッセージをm、生成多項式をgとおく。このとき以下の手順でcrcの計算をする。
1.gの(bit数-1)だけ、mの後ろに0を詰め込む。これをm'とおく。
2.f_m'を求める。
3.f_m'f_gで割ったあまりのbit表現がcrc


m=1011010,g=10011とする。
1.m'=10110100000
2.f_m'=x^{10}+x^8+x^7+x^5
3.f_g=x^4+x+1であり、f_m'f_gで割ったあまりを計算すると
f_{crc}=x^3+x^2+x+1。よってcrc=1111

・巡回冗長検査手順
1.[送信側]m'+crcを送信する
2.[受信側]m'+crcをgで割り算し、0になればビット誤りがないと判断する

理由
f_m'=P*f_g+f_{crc}
f_m'-f_{crc}=P*f_g
f_m'+f_{crc}=P*f_g(係数がGF(2)のため1=-1)より、f_{m'+crc}は必ずf_gで割り切れる。

もし送られてきたm'に誤りがあれば、割り算の結果が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をもつ数。

f:id:falconctf:20191025080006j:plain
説明的な何か
こんなん自分で割り算やってみないとわからんて。(丸投げ)

・反転実装
pythonではこっちが主流なはず。実装の難易度が違いすぎるから。
多項式の読み方を逆にする。(次数が大きい項が右端になる。)
gは適した固定の多項式を使いたい事情がある。(Wikipediaみて)

m=1011010,g=11001(上の例の多項式と同じ)とする。
1.m'=00001011010
2.f_m'=x^9+x^7+x^6+x^4
3.f_g=x^4+x+1であり、f_m'f_gで割ったあまりを計算すると
f_{crc}=x^3+x^2+x。よって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の設定しなくてもいいしサイコーですね。

f:id:falconctf:20191026074113j:plain
適当な画像
実行例

#送信
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でも同じ作業できる。

f:id:falconctf:20191026080943j:plain
テーブル利用crc32_reverse

・謎
wikipedia見ればわかるがなぜかcrc32のときは
初期値をcrc=0xffffffffとしcrc^0xffffffffをreturnする風潮がある。
考えたけど意味は不明だった。

ちなみに私の実装例はすべてcrc=0を初期値としている実装である。
まあそういこともあるんだと思っておく。

2019/10/27 追記


有力情報を頂いた。リンク先を見ると、全部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

QRコードを偽造してお金持ちになる問題。ただし、その分誰かが借金を背負う。過酷な世界。
URLにアクセスして、Registerしたあとログインする。

home画面はこんな感じ。

f:id:falconctf:20191020154251p:plain
home画面
1000000$むしり取ればフラッグが見れるっぽい。最初はrootが500くれてるだけの画面だったが、いろいろいじってたら今はこんな感じになってる。

send画面。

f:id:falconctf:20191020154458p:plain
send画面
人にお金を送るためのQRコードを発行できる。ただし持ってるお金以上送ろうとすると怒られる。

もらったQRコードをここで読んでみた。(QRコードをパソコンで読み取る(インストール不要)

username=egg&amount=100&proof=MI0bWQyatoUpSAwexg5YfHsb16bVb/HvGO9S73dOnlUiMSAwjDWHNyfVBJu4LboVjYNRHX7Amd268Hn42CJCz9ACog8wCjDxUF86bhqo/gNRrX2hVEmmr3TVD5y/oyWcV0qhdI9sCgfs4LBHdYEZ88Y2t9mQ+y8reD9wKBg50HvHYLs+wgwZMSAwEqtINttKiFkBf1z0oRDZVNzlDMHIcNBmpWPqsspe5hYwCjChQs4pLc1BI+RcZEcwnlIVXKMg3DtLCpmb2ae68wVpFjAgMICbAKUpCUTEkvPqCgAyEn495kmmuIHHwvAMOcgoBBckMAowc88QQ3fzC/fScQ/bYjgWatbrwSv6oC5b7FKjGVe8UgkxCjCFM8gQREFJNGRpfKk0oxjHDid21FI+kyBx8grtsf0vKjAK&hash=c728621fcb2fc4fffb72f4ce548a5d04b8a7424199f022d0377c2f99e76564d9

これをrecieve画面で読み込むとお金をゲットできる。

f:id:falconctf:20191020155001p:plain
rcieve画面

ユーザーの初期の手持ちは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))

とくにここ。111111111111 \cdots 111(10000個並んでる。)回も crc32を使って計算している。
方針は単純。どっかでループすると思われるので、それを特定する。ランダム要素がないので最悪でもcrc32を2^{32}回ぶん回せばループが発覚する。鳩ノ巣原理。
あとは111111111111 \cdots111 \bmod loopを計算して、ループの先だけ計算すればよし。

2^{32}回ぶん回すのも頭おかしいと思ったが、ほとんど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。

CRT:
CTFで使う数学 後編 - CTFと共に生きる

まずは、ふつーの復号を見よう。
m = C ^d \pmod N
一ミリも面白くない。まあこの計算が重いので軽くしようぜってこと。

まずは中国剰余定理でばらして復号してみる。
x \equiv C^d \pmod p
x \equiv C^d \pmod q
の連立合同方程式の解は0 \leq x < pqの中にあり中国剰余定理で計算できる。
これが実はmになる。

なぜか。
C ^ d \equiv m ^ {ed -1} \equiv m * {(m^{p-1})}^{k(q-1)} \equiv m \pmod pとなる。
フェルマーの小定理CTFで使う数学 前編 - CTFと共に生きる
対称性を考慮し、上の連立合同方程式は
x\equiv m \pmod p
x\equiv m \pmod q
とかける。これを(*)とおく。

よって
x=pk+m,x=ql+m(k,l:整数)と書け、両辺引くことにより
pk=qlp,qは互いに素だからk=q,l=p
つまりx=pq+m \equiv m \pmod N

実際にx=mを求めるために、
m_p=m\pmod p,m_q=m\pmod qとおく。
中国剰余定理の解の求め方としてGarner法を思い出すと
x=m=m_p + p * t
ただし、t=(p ^{-1} \bmod q )((m_q - m_p) \bmod q)

この式がよく復号のところで出てくる。



ここからさらに高速化する。
x \equiv C^d \pmod p
x \equiv C^d \pmod q
を使っていたが、これは
x \equiv C_p ^ {d_p} \pmod p
x \equiv C_q ^ {d_q} \pmod qを用いても同じでありこっちのほうが計算が早い。
ただし、
C_p \equiv C \pmod p,e d_p \equiv 1 \pmod p-1,C_q \equiv C \pmod q,e d_q \equiv 1 \pmod q-1を満たす。

C_p ^ {d_p} \equiv  C ^ {d_p} \equiv m ^ {e d_p} \equiv m ^ {a(p-1)} \equiv m \pmod paは整数。
最後の\equivフェルマーの小定理による。

(*)と同じになったことからこの解はmとなることがわかる。





まとめるとC_p,C_q,d_p,d_q
C_p \equiv C \pmod p,ed_p \equiv 1 \pmod {p-1},C_q \equiv C \pmod q,ed_q \equiv 1 \pmod {q-1}を満たすものとし、
x \equiv C_p ^ {d_p} \pmod p
x \equiv C_q ^ {d_q} \pmod qを考える。
この連立合同方程式の解はm\pmod Nとなり

実際に
m_p= C_p ^ {d_p}\pmod p,m_q=C_q ^ {d_q}\pmod q
t=(p ^{-1} \bmod q )((m_q - m_p) \bmod q)とすると
x=m=m_p + p * t、と求められる。

こっちのがm = C ^ d \bmod Nとして計算するよりも断然はやい。

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()

いつものごとく長い文字を置き換える。
I_p={\rm ipmq},I_q={\rm iqmp}。dmp1,dmp2はRSA-CRTでの処理高速化に使う項なので無視。
ふつーのRSA-CRTならI_pI_qの片方でいいのでなんか変だな?と思っておく。

次に

return "Key([e = {0}, n = {1}, x = {2}, y = {3}])".format(self.e, self.d, self.iqmp, self.ipmq)

を見ると、やべえ秘密鍵dが流出してるうける。
が、Nがないので復号無理。
というわけでNを求めに行く。
given:e,d,I_p,I_q

p I_p = 1\pmod  q,
q I_q = 1 \pmod pの周りから情報を抜き出す。
p,qからI_p,I_qを求めていることを考えると、拡張ユークリッドの互除法より
xp+qy=1x,yから
I_p=x \bmod q,I_q=y \bmod pとしているはず。
x=I_pとするとyは負の数であり、bit数を考えるとI_q - pしかない。

よってI_p p + q(I_q - p) = 1
変形して
p(I_p-1)+q(I_q-1)=(p-1)(q-1) \cdots ①
I_p-1,I_q-1に対する拡張ユークリッの互除法からx_0,y_0が求まり
x_0(I_p-1)+y_0(I_q-1)=\gcd{(I_p-1,I_q-1)} = 18 \cdots ②と書ける。
L=\frac{ed-1}{18},X_0=L*x_0,Y_0=L*y_0とおくと、②の両辺にLをかけて
X_0(I_p-1)+Y_0(I_q-1)=ed-1=k(p-1)(q-1)k:整数 を得る。
特殊解X_0,Y_0を用いて
X(I_p-1)+Y(I_q-1)=k(p-1)(q-1)の一般解X,YX=X_0 - \frac{I_q-1}{18}l,Y=Y_0 + \frac{I_p - 1}{18}lと表せる。
①からこの解のなかにX=kp,Y=kqとなるものがあるはずなので、lに対してブルートフォースする。
得られたX=kx_p,Y=ky_qとしたときのx_p,y_qが正しいp,qの判定には、k(x_p-1)(y_q-1)=ed-1を満たすかを用いた。
探索範囲をbit数から絞りこんでなお12分かかった。

p=166564961597106229342966450443567005929416288372170308009700499465281616388542030734600089639466922805142577582894052957547174764252067983124558747593344882775630971023610755334859287415681252266825395627416912206349590353878868107848653100299011246746851490276537231636534462821659050996145878589643016881929
q=135136928230019073146158752709151576119155564982754768027494878210491711363872928718225319693774548227271767324623087432404412585662574641211148315864508708036871556964386141364368797168619283425834644924573664613109609076319077176698754203574237779054129492453503018443013301394555677417140681949745410143477

Nがわかったので解けた。Cを暗号文とする。

m=pow(C,d,N)

flag:hitcon{1t_is_50_easy_t0_find_th3_modulus_back@@!!@!@!@@!}


flagをみてもピンとこないあたり想定解ではないんでしょうか?英語力不足で意味をくみ取れていないだけ?

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

どうも。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}は上記の手順を2周したときにデータベースと一致する。レインボーテーブル全体は4周(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}はほしいデータから決める。
例えば英数字8桁(パスワードにありがち)のデータのハッシュを復元したいなら、{\rm R}ハッシュ値から英数字8桁を生成する関数を考えるし、
数字のみ6桁~10桁のデータのハッシュ値を復元したいなら、{\rm R}ハッシュ値から数字のみ6桁~10桁を生成する関数を考える。

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

実行例

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のハッシュ値なのだが何回やっても復元できなかった。
d_{11},d_{12},d_{13},...は乱数を使っているので、そのうち復元できそうなのに。

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


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

pythonのモジュールのソースコード読みたいよ

import random 
random.__file__

で場所がわかる。

pythonモジュールはよくCで書かれたライブラリを呼んでるけど、pythonの中には実行ファイルしかないので
ソースは
GitHub - python/cpython: The Python programming language
などを探すとよい。

Balsn CTF 2019 Crypto

どうも。duckです。
解けません。
どこまでflagににじり寄ったかまとめます。ついでに調べて得た知識もかるく。


1.collision
ハッシュは逆算不可能なんだよ!!
ってことで解けません。

ハッシュの問題って
・DB検索(レインボーテーブル含む)
・ハッシュ衝突させるやつ

ぐらいしか思いつかないんですがどうなんでしょう。解いてる人多いし悔しい。


2.unpredictable
これが一番解けそうでした。
疑似乱数生成器(メルセンヌツイスタ)の内部状態を復元して、RSAもどきを解く問題だと思います。

Mersenne Twisterの出力を推測してみる - ももいろテクノロジー
こことほぼ同じなんですが

randrange(3133731337)

から復元する部分が違います。これがまじむりつらい。

randrangeの実装をソース読んでみたんですけど(後メルセンヌツイスタのソースも)
randrange(N)はNのビット数以下の乱数をメルセンヌツイスタからもらってもしそれがNより大きいなら取り直すってことやってるんすよ。
今、2^{31} < 3133731337 < 2^{32}
なので、3133731337 < メルセンヌ < 2^{32}のときはその値が破棄されてしまうと。output.texに書かれてるのはメルセンヌ < 3133731337となった時だけです。

つまるところ、我々が入手したデータは穴抜けのデータであり、メルセンヌツイスタの内部情報を参考記事のように簡単には復元できないと。
悲しい。

ということで、メルセンヌツイスタの動作から、穴抜け部分の復元を図ります。
3つの内部状態から新たな内部状態1つを作るので、3つわかってれば復元できます。
このプログラムを考えてたら終わってました。
つうか確率で失敗するのでやる気出ませんでした。
だって1/4くらいでとりなおしがはっせいするんだぜ?運ゲーじゃーん。
まあでもたぶんこの方針だよなあ。


3.harc4
rc4でしたっけ。ストリーム暗号のやつ。
調べてもどんなアルゴなのか出てこないこと多すぎない?
もう次からさっさとソース読みます。

from Crypto.Cipher import ARC4

これの中身見てから再挑戦しよ。


4.shellcode writer
見た記憶がない。やってないとおもわれ。


まあWriteupまちですね。

今回は
・うるせえいいからぐぐれ
・なけりゃソースよめ
の二つができたのでエンジニアっぽいしよしとします。

有名なライブラリとかモジュールって結構読みやすいので、今までなんで忌避してたんだろうって感じです。
エラーメッセージの分岐おおすぎるのがうざいだけであとは超きれい。

レインボーテーブルがわかったので実装してみよっかな。
そしたらまた記事書きますね。
ではまた。