SECCON Beginners CTF 2021 Crypto writeup
Beginnerの範囲が広い。
Result
Writeup
simple_RSA
忘れない内に
$ 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?}