Beginners CTF 2019 writeup - くれなゐの雑記

はじめてCTFにチームとして参加しました！！！！！

R19 というチームで参加してました！ kurenaifと申します

常設じゃないCTFはやるのは初めてです！

知り合いにpwnをひたすら布教されていたので、CTFはpwnだと思っていたのですが、実はCryptoもあり、それが面白そうだったのでチームメイトに俺はCryptoをやるぞーーーー！！！と言ってCryptoだけやりました。

pwnもやってみたのですが、すべてを忘却していたため頑張って思い出そうと思います。

[Crypto] [warmup] So Tired

so_tired.tar.gz が渡されました中身は encrypted.txt だったのですがこれがとても長い… なんか最後の方に == とかついてますし、 base64 encode らしさがありますねというわけで

$ cat encrypted.txt | tr -d '\n' | base64 -d  > src

out を見てみると、よくわからないバイナリですね… よくわからないバイナリはとりあえず file を見てみましょう

$ file src
out: zlib compressed data

どうやらzlibだそうです！

#!/usr/bin/python3
# a.py
import zlib

f = open("src", "rb")
data = f.read()
f.close()

dc = zlib.decompress(data)
f = open("out", "wb")
f.write(dc)
f.close()

outを見てみると…

$ cat encrypted.txt | wc -c
373728
$ file out 
out: ASCII text, with very long lines, with no line terminators
$ cat out | wc -c
370052

あっ…(察し)

また base64 してみると、どうやらこれも zlib みたいです。 base64 と zlib をひたすらぐるぐるさせたのが、この暗号みたいですね。

それではさっきのPythonと組み合わせて

# a.sh
while true
do
cp out out.bak
cat out | tr -d "\n" | base64 -d > src
python3 a.py
wc -c out
done

これでエラーが出るまで待ち続けましょう！

base64: invalid input
Traceback (most recent call last):
  File "a.py", line 8, in <module>
    dc = zlib.decompress(data)
zlib.error: Error -3 while decompressing data: incorrect header check
37 out

エラーが出ました！いい文字数ですね！

$ cat out
ctf4b{very_l0ng_l0ng_BASE64_3nc0ding}

[Crypto] Party

どうやら、3組のpair、すなわち合計6つの数字が与えられるみたいですね。

coeff を x
出力された数字を y
partyをr

とおくと、以下の式が成り立っていることがわかります！

$\begin{bmatrix} r_0^0 & r_0^1 & r_0^2 \\\ r_1^0 & r_1^1 & r_1^2 \\\ r_2^0 & r_2^1 & r_2^2 \end{bmatrix} \begin{bmatrix} x_0 \\\ x_1 \\\ x_2 \end{bmatrix} = \begin{bmatrix} y_0 \\\ y_1 \\\ y_2 \end{bmatrix}$

$x_0$ がフラグですね

行列の形がわかれば、あとは行列を斜めにするやつをやるだけです！少数型に落とすと情報が欠けそうで怖かったので、有理数クラスを使って解いてます。

#!/usr/bin/python3

import numpy as np
from fractions import Fraction
from Crypto.Util.number import long_to_bytes

def f(x, coeff):
    y = 0
    for i in range(len(coeff)):
        y += coeff[i] * pow(x, i)
    return y

def solve(mat):
    for row in range(len(mat)):
        tar = mat[row][row]
        for col in range(len(mat[row])):
            mat[row][col] /= tar
        for r in range(len(mat)):
            if r == row:
                continue
            boost = mat[r][row]
            for c in range(len(mat[r])):
                mat[r][c] -= mat[row][c] * boost
    return mat

N = 512
M = 3

r = [0]*3
y = [0]*3

file = open("src", "r")

for i in range(3):
    r[i] = Fraction(int(file.readline()))
    y[i] = Fraction(int(file.readline()))

mat = [
    [Fraction(1), Fraction(r[0]), Fraction(r[0]*r[0]), y[0]],
    [Fraction(1), Fraction(r[1]), Fraction(r[1]*r[1]), y[1]],
    [Fraction(1), Fraction(r[2]), Fraction(r[2]*r[2]), y[2]],
]

print(solve(mat))
for i in range(len(mat)):
    for j in range(len(mat[i])):
        print(mat[i][j], end=" ")
    print()

print(long_to_bytes(mat[0][-1]))

しっかり単位行列になってフラグが取れました！

1 0 0 175721217420600153444809007773872697631803507409137493048703574941320093728 
0 1 0 6759741750199108721817212574266152064959437506612887142001761070682826541920627672362291016337903640265385249474489124882116454124173716091800442011015857 
0 0 1 8559415203809303629563171044315478022492879973152936590413420646926860552595649298493153041683835412421908115002277197166850496088216040975415228249635834 
b'ctf4b{just_d0ing_sh4mir}

Go RSA

RSA暗号の d と encryptされたデータは教えてくれますが、 N をなくしてしまったみたいです！！！！！

Nないのにお前どうやって暗号化してんだよ！！！！

この問題、2つ気づくことに気づけばなんと瞬殺できます

まず一つ、数字が入力できること
そして、その数字に負の数が入ること

ガチャガチャ遊んでいたら、負の数を入ることを発見してしまいました。 -1 が通るならもう自明です。

RSA暗号の暗号化は

c = m^e MOD N

復号は

m = c^d MOD N

ですね。このNがわからないので、復号できないという問題でした。

この問題では、フラグの c の他に、3回まで好きな整数の m を入力することができます。

では、 m に -1 を入れたら…？

通常eは65537とか3とかです。

m = -1^e MOD N = -1 MOD N = N-1

なんと N-1 をもらえました！！！

これを +1 して、複合してやると…

from Crypto.Util.number import long_to_bytes

a = 19721739460005715839687258097463606567568088122562143766673559079928993888011218840527723736945976855276429750686840511245308087039361625859575588315010586932109088534073184785632230817871748507755371081564038161176335857405579592850018586825018841366905735384823298027525055483718836334184117597308146143832746609071410404320299844124897769731428479677374581456236061208983710496710928583658704287830103346312036579012291640838414960806920681837417786550306083430969817954317601886422446799325599439885265181833346633337600066770273573882073976043621513973625591205643086917193039382944499499255990087899534083558712
n = a + 1
d = 16012534574459681485963634139862001145411989213568735706066294645804685807634846967717788543366836663962557081706478331993745344148366136283532609515693857534590486442567835507091820407552582660881197653556068092746906439239029795613811114691641020613919176733171071476305533169723408153840900277253517317842880767356950185288540335520596457402867899206001172130409041175548610181861286325063434009922901699522599455879079648553315178156923597492552797606051253955520510125897947319770306996525090494984301910656673155680183032096435051027220919313430919758310229110059410508088941767032227875386851849410203872128257

x = 4166307417617957284869321340663074830305356736973969287118610781379422763896670624160917668898929485302592913693740635487274812853279249498082813735026859474333821827825022846601676094308501172617202223248824318344700000867606631910692133738577886686239665573753583206491647139406448572619516253202158832537788022928614879944248391229292623896316715442295616471480180228286163207028450461678895309475635821698950149318482145068775702644341882119883921129616029519739738868428874523531712307489141815448685352233906955519708655061860955347613402457489376739490167812575480528575373033977959010646084855165180428882395
print(long_to_bytes(pow(x,d,n)))

いえい！

b'ctf4b{f1nd_7he_p4ramet3rs}'

これ、あってんのか？と思ってましたがどうやら想定解放で、周りを眺めていたら少数派っぽいです…

別解(天才解法)

qiita.com

zeosutt.hatenablog.com

[crypto] bit_flip

元の数字があり、 nc でつなぐたびに、下1/4くらいのランダムな1bitを変えて、暗号化した数字を返してくれます。難しいです。これはRSAなのですが、

N と e と c はわかるのですが、dを教えてくれません。ただの公開鍵の情報です

もしこれで復号できたら、RSA暗号を解読したことになります。まともに解いてられません。

考察1 `e` が小さい

eが3なので、ワンチャン 3乗した結果が N より小さければ 3乗根を求めるだけで解けます。

... 無理でした

考察2 1bitしか変わっていない

もとの数字を x として、i bit目が変わったとすると

$(x + 2^i)^3 \mathrm{or} (x - 2^i)^3$

が大量に渡されるので、なんとかして連立方程式を解けないかと考えました

...無理でした

実はできた

qiita.com

考察3 Flanklin-Reiter Related Message Attack

RSAの暗号の脆弱性を調べていると見つけました。

2つのメッセージ m1 と m2 の差がわかれば解けるという問題です。

1024/4 = 256 bitのうち、1bit変えただけなので、差のパターン数は 256^2 そんなに多くありません。

差は、 xor をとっているので

abs((1 << i) - (1 << j)) or (1 << i) + (1 << j)

の2択です。

2つの差分がわかれば、あとはその全てに対して複合するだけです。

ももいろテクノロジー様のソースコードを使わせていただいて、

inaz2.hatenablog.com

以下のようになりました

# coppersmiths_short_pad_attack.sage

# reference: http://inaz2.hatenablog.com/entry/2016/01/20/022936
import sys


# reference: http://inaz2.hatenablog.com/entry/2016/01/20/022936
def short_pad_attack(c1, c2, e, n):
    PRxy.<x,y> = PolynomialRing(Zmod(n))
    PRx.<xn> = PolynomialRing(Zmod(n))
    PRZZ.<xz,yz> = PolynomialRing(Zmod(n))

    g1 = x^e - c1
    g2 = (x+y)^e - c2

    q1 = g1.change_ring(PRZZ)
    q2 = g2.change_ring(PRZZ)

    h = q2.resultant(q1)
    h = h.univariate_polynomial()
    h = h.change_ring(PRx).subs(y=xn)
    h = h.monic()

    kbits = n.nbits()//(18)
    print(h.small_roots(X=2^kbits, beta=0.5))
    diff = h.small_roots(X=2^kbits, beta=0.5)[0]  # find root < 2^kbits with factor >= n^0.5

    return diff

# reference: http://inaz2.hatenablog.com/entry/2016/01/20/022936
def related_message_attack(c1, c2, diff, e, n):
    PRx.<x> = PolynomialRing(Zmod(n))
    g1 = x^e - c1
    g2 = (x+diff)^e - c2

    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic()

    return -gcd(g1, g2)[0]

if __name__ == '__main__':
    n = 82212154608576254900096226483113810717974464677637469172151624370076874445177909757467220517368961706061745548693538272183076941444005809369433342423449908965735182462388415108238954782902658438063972198394192220357503336925109727386083951661191494159560430569334665763264352163167121773914831172831824145331
    e = 3

    c1 = 38448272237964375371726759592758385386616013779162822338653392077256549091123869239648616008586564655973797454298230191967696840378043670012083704181791314856097307077627229165947387478341901251979390480932220983592258282304304001581658323909165412718287474168394422138841873902714319309538983680281287491186
    c2 = 51531223430957857733934880383408638185102108212202467189651292360878470909281785640325226719442938173566544600753270928156891865771525435019551126712738055654692625329783768014054928002128679874456939510971058344318886221948942145053253549048822643888005377157270281027834500602254102431820137131985798724504

    for bit1 in range(1024//4):
        for bit2 in range(bit1):
            sys.stderr.write(str(bit1) + "," + str(bit2) + "\n")
            a = (1<<bit1)
            b = (1<<bit2)
            for diff in [(a+b), (a-b), -(b-a)]:
                # print bit1, bit2
                # print "difference of two messages is %d" % diff

                m1 = int(related_message_attack(c1, c2, diff, e, n))
                m2 = m1 + diff

                pos = []
                i = 0
                while i < 1025: 
                    bm1 = ((m1 >> i) & 1)
                    bm2 = ((m2 >> i) & 1)
                    if bm1 != bm2:
                        pos.append(i)
                    i += 1
                
                if len(pos) != 2:
                    continue

                print(m1)
                print(m1 ^^ (1 << pos[0]))
                print(m1 ^^ (1 << pos[1]))
                print(m1 ^^ (1 << pos[1]) ^^ (1 << pos[0]))

あとは出てきた数字をすべてbyte文字列に戻すと…？

見つかりました！

f:id:kurenaif:20190528005152p:plain

[misc] Dump

休憩時間にときました。いっぱいパケットがありますが、 wireshark の機能を使えば実はhtmlだけ取り出せます！

`File>Export Objects>HTTP...>Packet 3193`

hexdumpの8進数なので、あとはこれをdecodeするだけですね

import struct

file = open("src", "r")

lines = file.readlines()

nums = []
for line in lines:
    nums += list(map(lambda x: int(x, 8), line.split()))

with open("out", "wb") as fout:
    for x in nums:
        print(x)
        fout.write(struct.pack("B", x))

[misc] Sliding puzzle

幅優先探索で出来るくらいの計算量ですが、ちょっと書くのが辛かったので先人のコードをお借りしました。

host = '133.242.50.201'
port = 24912
bufsize = 4096

sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
sock.connect((host, port))

while True:
    a = sock.recv(bufsize).decode()
    print(a)
    rows = a.split('\n')[1:4]

    rows = list(map(lambda x:x.split('|')[1:-1], rows))
    for i in range(len(rows)):
        for j in range(len(rows[i])):
            rows[i][j] = int(rows[i][j])
    ans = checkio(rows)
    res = ",".join(ans)
    sock.send(res.encode())

所感

Crypto たのしい！！！！！！！ pwnやweb、reversingは完全に人に任せていたので、反省です。今度反省会をするので、そのときにコツを教えてもらいます！