corCTF 2021 writeup - Attack All Around

久しぶりにwriteupを書く気がします。

corCTF 2021

Result

f:id:partender810:20210823152726p:plain — crypto以外が解けない…

Writeup

misc

yeetcode

Brush up on your coding skills and ace your next interview with YeetCode! Flag is at ./flag.txt
https://yeetcode.be.ax
ファイル：yeetcode.tar.xz

引数a, bが渡されるとその和を返り値とする関数fを作るとCongrat!とほめてくれますほめてくれます。

def f(a,b):
  return a+b

tar.xzを解凍してyeet.pyを見るとテストケース10個の内2個は固定値でした。固定値かどうかは実際関係なかったのです。

FLAGが./flag.txtにあるということで、このプログラムから開けないか試してみました。

def f(a,b):
  g = open("./flag.txt","rb").read()
  return a+b

このプログラムを提出したところ、エラーは吐かれませんでした。ということはファイルを開けたでしょう。あとは手作業ゲーです。

def f(a,b): #example
  g = open("./flag.txt","rb").read()
  if g[0] == ord("c"): return a+b
  else: return 0

これでg[0]が"c"かどうか分かります。if文が真ならCongrat!と褒められ、偽なら当たってないと言われます。if文をこんな限定的にせず、二分探索とかの方が効率的です。

corctf{1m4g1n3_cp_g0lf_6a318dfe}

crypto

fibonary

Warmup your crypto skills with the superior number system!
ファイル：enc.py, flag.enc

フィボナッチ数列のナップザック暗号ですね。超増加数列ではありませんが、復号可能です。

f = open("flag.enc")
a = f.readlines()
print(a)
enc = a[0].split()
print(enc)
fib = [1, 1]
for i in range(2, 11):
    fib.append(fib[i - 1] + fib[i - 2])
flag = ""
for i in range(len(enc)):
    val = 0
    for j in range(len(enc[i])):
        if enc[i][j] == "1": val += fib[len(fib)-1-j]
    flag += chr(val)
print(flag)

corctf{b4s3d_4nd_f1bp!113d}

4096

I heard 4096 bit RSA is secure, so I encrypted the flag with it.
ファイル：4096.tar.xz

nが32bit素数128個の積であるmultiple prime RSAです。

factorDBでは素因数分解できないので、sageに投げます。

from Crypto.Util.number import *
n = (中略)
c = (中略)
e = 65537
fac = "(中略)" #sagemathの結果を入れる
primes = list(map(int,fac.split(" * ")))
phi = 1
for p in primes:
    phi *= (p-1)
d = inverse(e,phi)
m = pow(c,d,n)
print(long_to_bytes(m))

corctf{to0_m4ny_pr1m3s55_63aeea37a6b3b22f}

dividing_secrets

I won't give you the secret. But, I'll let you divide it.
nc crypto.be.ax 6000
ファイル：server.py

離散対数問題ですが、変数divに代入する値を適切にすれば簡単に解けます。

flagの最終文字を求めます。
x = 256k+l とすると、lが最終バイトです。div=256を投げると、g^k を渡されます。それを256乗し、その値とg×lがencrypted flagになります。lは256通りしかないのでbrute forceで解けます。

flagの最終2文字目を求めます。
先ほどのkがxに該当します。なのでencrypted flag = g^kとなります。
k = 256k'+l' となり、l'を先と同様に求めます。

これらを繰り返しflagの全ての文字を求めていきます。

HOST, PORT = "crypto.be.ax", 6000
s, f = sock(HOST, PORT)
g = int(read_until(f).split()[-1])
p = int(read_until(f).split()[-1])
enc = int(read_until(f).split()[-1])
t = 1
bef = enc
flag = ""
for i in range(64):
    t *= 256
    print(i,read_until(f,"number> "))
    s.send(str(t).encode()+b"\n")
    tmp = int(read_until(f).strip())
    print(tmp)
    for j in range(256):
        if (pow(tmp,256,p)*pow(g,j,p))%p == bef:
            flag += chr(j)
            break
    bef = tmp
    print("flag =",flag[::-1])

corctf{qu4drat1c_r3s1due_0r_n0t_1s_7h3_qu3st1on8852042051e57492}

supercomputer

I ran this code with a supercomputer from the future to encrypt the flag, just get your own and decryption should be simple!
ファイル：supercomputer.tar.xz

n = (p^q) × r, a1 = randrange(n), t = (a1ⁿ) + ( (n-a1)ⁿ) とあります。flagがv(p, t) とxorされます。

関数vは、tが素数pの何乗で割り切れるかの最大値を返り値とします。

ではtはpで何回割れるのでしょうか？ tを展開します。

( (n-a1)^n) 
=n^n - C0×n^(n-1)×a1 + ... + Ck×n×a1^(n-1) -  a1^n

となり、最終項が(a1ⁿ)と打ち消されます。

この時点でtがnの倍数であることが分かります。( (n-a1)ⁿ) を展開した際にnが掛けられない唯一の項が打ち消されました。

次に、( (n-a1)ⁿ) の最終2項目の係数Ckを求めます。パスカルの三角形を考えると、x乗するときの2項目と最終2項目の係数はxです。つまりCk = nです。

( (n-a1)^n) 
=n^n - C0×n^(n-1)×a1 + ... + Ck'×n^2×a1^(n-2)+ n×n×a1^(n-1) -  a1^n

a1ⁿ 以外n²で括ることができる＝tがn²の倍数であることが分かりました。

n = (p^q) × rより、tがn²の倍数であれば2q回pで割れます。ゆえにv(p, t)の返り値は2qです。

import pwn
import binascii
from Crypto.Util.number import *
p,q,r = (中略)
enc = b'(中略)'
print(pwn.xor(binascii.unhexlify(enc),long_to_bytes(q*2)))

corctf{1_b3t_y0u_d1dnt_4ctu411y_d0_th3_m4th_d1d_y0u?}

babyrsa

discord is the best place to store secrets
ファイル：babyrsa.PNG, output.txt, script.py

script.pyやbabyrsa.PNGを見ると、10進数表記のn, p, qの一部の桁は見えています。Coppersmithを使うのにどう落とし込むか…。
pの不明な桁数がいくつか、nを参考すると41桁あることが分かりました。

p = int( str(pの上位84桁)+(不明な41桁)+str(pの下位30桁) ) です。下位41+30桁がすべて0の時と9の時とで、上位bitがどこまで一致するか確かめたところ275bit一致しました。つまり不明な41桁がなんであろうとpの上位275bitは一定となります。

SageMathを使ってCoppersmith's Attackをやってみる - ももいろテクノロジー

いつもの資料を使います。コード内のkbitsは未知のbit数を表し、pが512bitならkbits = 219となります。つまり512-219 = 293bitは既知でないといけません。

ここで、pの上位275bitは分かっていて、残り293-275=18bitをbrute forceします。2¹⁸ ≒ 260000なので余裕です。

n = (中略)
pbar = (中略)
PR.<x> = PolynomialRing(Zmod(n))
for i in range(pow(2,18) ):
  pbar = pbar + (i<<219)
  f = x + pbar

  x0 = f.small_roots(X=2^kbits, beta=0.3)
  if len(x0) > 0:
    print(x0[0] + pbar)
    break