Attack All Around

今やCTFと競プロばかりだが、トビタテ生のアメリカ留学やTOEFL奮闘記

SECCON Beginners CTF 2021 Crypto writeup

Beginnerの範囲が広い。

SECCON Beginners


Result

f:id:partender810:20210523145854p:plain
まあまあいい結果ではないでしょうか


Writeup

simple_RSA

Let's encrypt it with RSA!
ファイル:simple_RSA.tar.gz

忘れない内に

$ tar -zvxf xxx.tar.gz

e=3と小さいです。me < n であるLow Public Exponent Attackだろうとエスパーし、cのe乗根を取るとあったのであとはlong_to_bytesして終了です。

import gmpy2
from Crypto.Util.number import *
n = (中略)
e = 3
c = (中略)
m,ch = gmpy2.iroot(c,3)
assert ch
print(long_to_bytes(int(m)))

ctf4b{0,1,10,11...It's_so_annoying.___I'm_done}


Logical_SEESAW

We have an innovative seesaw!
ファイル:Logical_SEESAW.tar.gz

flag[i]=0なら、key[i]がなんであろうと0になります。16回行って毎回0になっているところはflag[i] = 0, そうでないならflag[i] = 1として最後long_to_bytesすればOKです。

cipher = (中略)
cip = [[] for _ in range(len(cipher[0]))]


for j in range(len(cipher)):
    for i in range(len(cipher[j])):
        cip[i].append(cipher[j][i])
m = ""
for c in cip:
    if c.count("1") > 0: m += "1"
    else: m += "0"
print(long_to_bytes(int(m,2)))

ctf4b{Sh3_54w_4_SEESAW,_5h3_54id_50}


GFM

Github Flavored Markdown
Google Facebook Microsoft
And...?
ファイル:gfm.tar.gz

enc = key × M × key (全て行列)であり、enc, keyが与えられているのであとはsageに逆行列行列積を計算させればOKです。行列積なので掛ける順番に気を付けましょう。

key × M × key = enc
key × M × key × key_inv = enc × key_inv 
key × M = enc × key_inv 
key_inv × key × M = key_inv × enc × key_inv 
M = key_inv × enc × key_inv 
SIZE = 8
p = random_prime(2^128)
MS = MatrixSpace(GF(p), SIZE)

M = copy(MS.zero())
key = matrix( (中略) )
enc = matrix( (中略) )

key_inv = key.inverse()

d = enc*key_inv
p = 331941721759386740446055265418196301559
m = key_inv*d
for i in range(8):
    for j in range(8):
        print(chr(m[i,j]%p),end="")

ctf4b{d1d_y0u_pl4y_w1th_m4tr1x_4nd_g4l0is_f1eld?}


Imaginary

虚数は好きですか?
接続方法: nc imaginary.quals.beginners.seccon.jp 1337
ファイル:app.py

AESのECBモードなのである平文に対して毎回同じ暗号文になります。

pythonの辞書型に対して、"1337i" in self.numbersがtrueになるのは、self.numbersのkeyに"1337i"が含まれている必要があります。

しかし、このサーバは"(自然数) + (自然数)i"とself.numbersのkeyを決めるので、「1337i"」の暗号文は簡単に作れそうですが、「"1337i"」の暗号文は無理そうです。なので、ちょうど「"」で平文ブロックが終わるものと、「1337i"」から始まる平文ブロックを暗号化してもらい、あとはそれら二つを合成して、「{xxx "1337i": xxx}」となる暗号文を生成します。

具体的には、step1を「1337i"」から始まる平文ブロックの暗号文を得る、step2を「"」で終わる平文ブロックの暗号文を得るとすると、

step1
re = 123, im = 456 をsaveする
re = 1, im = 1337 をsaveする
Export

step2 re = 1234, im = 4567 をsaveする
re = 1, im = 1337 をsaveする
Export

となります。あとはstep2で得られた暗号文の先頭64bytesとstep1で得られた暗号文の64bytes以降を足したものをImportすればflagが手に入ります。

json.loadsとかでエラー吐かないように平文を気を付けないといけなかったのが難しいですね。

ctf4b{yeah_you_are_a_member_of_imaginary_number_club}


Field_trip

Someone is getting ready for a field trip.
ファイル:Field_trip.tar.gz

先に言うと、チームメイトが惜しいところまで解いて自分が修正してみたら、終了1分前flagが手に入りましたあぶね~~~~~。

Merkle-Hellman knapsack暗号であろうと目を付け、ググるとこのサイトが。

PlaidCTF CTF 2015: Lazy - うさぎ小屋

このサイトに載っているsolver丸パクリです。細かい手法は一切分かりません。

本当のBeginnersはこのソースコードみてナップザック暗号だ!となるのすら難しいと思います。経験がものを言いますね。

b = pub_key
n = len(b)

c = 1010137180395931262752398681857488526009620802401167859543237801022630704004744078316133982172587856565491470015404484864890095896964409269987597733836611756


MULTIPLIER = 100
B = matrix(ZZ, n + 1, n + 1)
B.set_block(0, 0, MULTIPLIER * matrix(n, 1, b))
B.set_block(n, 0, MULTIPLIER * matrix([ - c ]))
B.set_block(0, 1, 2 * identity_matrix(n))
B.set_block(n, 1, matrix([ -1 ] * n))
#print '[*] basis: B =', B

# LLL algorithm
for x in B.LLL():
    if x[0] == 0 and all(x_i in [-1, +1] for x_i in x[1 :]):
        print('[*] found: x =', x)

        # decode x
        m = 0
        flag = ""
        for x_i in (x[1 :]):
            m *= 2
            m += int(x_i == +1)
        print('[*] plaintext: m =', m)
        while m > 0:
            flag += chr(m%256)
            m //=256
        print(flag[::-1])

チームメイトはこのサイトを参考にしてsolverを作ったとのことですが、私はある程度自分でやってしまい、それが原因で上手くいきませんでした。まずはsolverパクろう(教訓)

終了5分前、どうやっても復号できないとチームメイトからslackが来て、その復号文を2進数にして逆順にするとflagが出てきた!急いでsubmitしようとしたらloginしろと言われ焦る。これほどブラウザにパスワードを記憶させててよかったことはありませんでした(笑)

ctf4b{Y35!_I_ju5t_n33d3d_th353_num63r5!}


p-8RSA

It looks someone is encrypting it with RSA.
ファイル:p-8RSA.tar.gz

これ本当にbeginnerか???

まず、qを素数生成して8ずつ小さくしていき、それが素数且つe=17とφ(n)が互いに素でないなら鍵生成を終了します。

後半部分はともかく、とりあえず素因数分解します。factorDBでは上手くいきませんでしたが、自作のフェルマー素因数分解できました。

さあ、eとφ(n)が互いに素でない場合はどうしましょう。とりあえずググって見つけたサイトのアルゴリズムをそのままパクるとflagが出ました。

RSA Risk: When e and PHI share the same factor

これはgoogle力がものを言いました。phi = φ(n)/eとすると、gphi mod N != 1となるgを見つけ、d = e^-1 mod phiとなるdを使って、m = cd mod N を計算します。適切なgだと、gmが元の平文になるとのことです。gはbrute forceします。eとφ(n)が互いに素ではないと、違う平文でも同じ暗号文になってしまうので、得られた平文もどきから頑張って元の平文を手に入れるようなイメージしか湧きませんでした。

def algo1(p,q,e,gg):
    phi = ((p-1)*(q-1))//e
    while True:
        ge = pow(gg,phi,p*q)
        if ge != 1: return ge
        gg += 1
        

n = (中略)
e = 17
c = (中略)
tmp, ch = gmpy2.iroot(n,2)

tmp = int(tmp)-1 #tmpが最初偶数だったため

while True:
    if n%tmp == 0:
        p = tmp
        q = n//p
        print(p)
        print(q)
        assert n==p*q
        phi = ((p-1)*(q-1))//e
        d = inverse(17,phi)
        print("d:",d)
        m = pow(c,d,n)
        l = 1
        fin = True
        while fin:
            mm = m*l
            mes = long_to_bytes(mm%n)
            if b"ctf4b" in mes:
                print(mes)
                fin = False
            l *= algo1(p,q,e,l)
            l %= n
    
    tmp -= 2

ctf4b{4r3_y0u_up5id3_d0wn?_Fr0m_6310w?_0r_60th?}