ångstromCTF 2024 WriteUps

發表於 2024-05-28

分類於 CTF

這次在 Cystick 中解了一些題目，因為周末正好和 AIS3 Pre-Exam 撞，所以我只有解了最難的三題 Crypto 而已。

tss1

from hashlib import sha256
import fastecdsa.curve
import fastecdsa.keys
import fastecdsa.point

TARGET = b'flag'

curve = fastecdsa.curve.secp256k1

def input_point():
	x = int(input('x: '))
	y = int(input('y: '))
	return fastecdsa.point.Point(x, y, curve=curve)

def input_sig():
	c = int(input('c: '))
	s = int(input('s: '))
	return (c, s)

def hash_transcript(pk, R, msg):
	h = sha256()
	h.update(f'({pk.x},{pk.y})'.encode())
	h.update(f'({R.x},{R.y})'.encode())
	h.update(msg)
	return int.from_bytes(h.digest(), 'big') % curve.q

def verify(pk, msg, sig):
	c, s = sig
	R = s * curve.G + c * pk
	return c == hash_transcript(pk, R, msg)

if __name__ == '__main__':
	import sys

	if len(sys.argv) == 2 and sys.argv[1] == 'setup':
		sk1, pk1 = fastecdsa.keys.gen_keypair(curve)
		with open('key.txt', 'w') as f:
			f.write(f'{sk1}\n{pk1.x}\n{pk1.y}\n')
		exit()

	with open('key.txt') as f:
		sk1, x, y = map(int, f.readlines())
		pk1 = fastecdsa.point.Point(x, y, curve=curve)

	print(f'my public key: {(pk1.x, pk1.y)}')

	print('gimme your public key')
	pk2 = input_point()

	apk = pk1 + pk2
	print(f'aggregate public key: {(apk.x, apk.y)}')

	print('what message do you want to sign?')
	msg = bytes.fromhex(input('message: '))
	if msg == TARGET:
		print('anything but that')
		exit()

	k1, R1 = fastecdsa.keys.gen_keypair(curve)
	print(f'my nonce: {(R1.x, R1.y)}')

	print(f'gimme your nonce')
	R2 = input_point()

	R = R1 + R2
	print(f'aggregate nonce: {(R.x, R.y)}')

	c = hash_transcript(apk, R, msg)
	s = (k1 - c * sk1) % curve.q
	print(f'my share of the signature: {s}')

	print(f'gimme me the aggregate signature for "{TARGET}"')
	sig = input_sig()
	if verify(apk, TARGET, sig):
		with open('flag.txt') as f:
			flag = f.read().strip()
			print(flag)

題目簡單來說是一個 Two party 的 Threshold Schnorr Signature Scheme，aggregate 的 public key 就是雙方的 public key 相加而已。交換完 key 後會各自生成 nonce 交換，然後算出各自的 $s$ ，加起來就是 signature 的一部份。

攻擊方法也很簡單，因為它沒檢查你傳送過去的 $\text{pk}_2$ 是否真的是你的 public key，所以可以自己先生成一組 $(\text{ask},\text{apk}=\text{ask}\cdot G)$ ，然後求 $\text{pk}_2=\text{apk}-\text{pk}_1$ ，因此這樣我們就知道 $\text{apk}$ 的 secret key $\text{ask}$ ，所以可以自己 sign 任何東西。

from pwn import process, remote, context
from fastecdsa import keys, point
import ast
from tss1 import hash_transcript, verify, curve, TARGET

ask, apk = keys.gen_keypair(curve)

# io = process(["python", "tss1.py"])
io = remote("challs.actf.co", 31301)
io.recvuntil(b"my public key: ")
pk_tpl = ast.literal_eval(io.recvline().strip().decode())
pk1 = point.Point(*pk_tpl, curve=curve)
pk2 = apk - pk1
io.sendlineafter(b"x: ", str(pk2.x).encode())
io.sendlineafter(b"y: ", str(pk2.y).encode())
io.sendlineafter(b"sign?", b"peko".hex().encode())
k2, R2 = keys.gen_keypair(curve)
io.sendlineafter(b"x: ", str(R2.x).encode())
io.sendlineafter(b"y: ", str(R2.y).encode())


def sign(sk, pk, msg):
    k, R = keys.gen_keypair(curve)
    c = hash_transcript(pk, R, msg)
    s = (k - c * sk) % curve.q
    return c, s


c, s = sign(ask, apk, TARGET)
assert verify(apk, TARGET, (c, s))
io.sendlineafter(b"c: ", str(c).encode())
io.sendlineafter(b"s: ", str(s).encode())

io.interactive()
# actf{r0gu3_4ggr3g4t1on_632d50edb72d34d3}

BLÅHAJ

p = random_prime(2**1024)
q = random_prime(2**1024)
a = randint(0, 2**1024)
b = randint(0, 2**1024)

def read_flag(file='flag.txt'):
    with open(file, 'rb') as fin:
        flag = fin.read()
    return flag

def pad_flag(flag, bits=1024):
    pad = os.urandom(bits//8 - len(flag))
    return int.from_bytes(flag + pad, "big")

def generate_keys(p, q):
    n = p * q
    e = 0x10001
    return n, e

def encrypt_message(m, e, n):
    return pow(m, e, n)

flag = read_flag()
m = pad_flag(flag)

n, e = generate_keys(p, q)
assert m < n

c = encrypt_message(m, e, n)

print(c)
print(n)
print(p + b * q)
print(a * p + q)

簡單來說就是要分解 $n=pq$ ，而題目額外給了 $x=p+bq,y=ap+q$ ，其中 $a,b,p,q$ 都是 1024 bits 的數。

我的作法是這樣，先令

f(t,u)=(x-t)(y-u)

可知 $f(p,q) \equiv 0 \pmod{n}$ ，所以可以展開得到:

f(t,u)=xy-uy-tx+tu

因此有:

xy-qy-px+pq \equiv xy-qy-px \equiv 0 \pmod{n}

其中 $x,y,n$ 已知，所以可以 LLL 求 $p,q$ 。

from sage.all import *
from Crypto.Util.number import long_to_bytes
from lll_cvp import solve_inequality

c = 2084015642966578282323320320430355169303796428932452813616522534642993911885394832889877216337047505539910273209203092431502448659110975363836148150333450975665054754794923282649866834797382152974537871637107602980242305752842881056832372729032719323542397731147821640234181272537527934691830138813076673120558790685225545176722374373891797444430162049094331866632430714818874728168815552807267537023134887147693780578518721495129472480845244586874832711656372700340333956532029558890132512276495501200465374040059705096729628227299657939763878581814774444365099164760074348408594002376240830368408586554430584367239
n = 5054759650831149212497593612117505449996534385400799412730981223889391367155509695417999090910848750197375100341995228567935542100150279063805945642486626676563744817810946769932250256245882026085508665771131635110277852237029849869509707637709162425864373201102790718464450861787668024958787992996715870537273213999452948215564503811414448019655761914535646338206972306327692776792357656461421160012732874929753400746379737081861110621084719920237555759371086828748564360804144357313056202764375401039317055078455329940265973052825170224804217772389893623634664438855142967283765161646402518311874260437023116525027
x = 14624164038828170251441254789590748299059493407127408167381909039718004816732842597998978394090418984661609925783012574638050052448399168193536431334288702858151820090630198056959727167341057230779720998603705567821824977324339182361973824850629918120718796161913475916523630822110582289148982548632694537423158073771024615682852893559402668337273941915650824074226258103607152649283649471317242038305999409041659019944804416273274057125302350242520142492153556081164794428695882962406952831655367215074021698796576010502956218034153621531037983312180680329891048894826768653762528273739711501728033951545847806707848
y = 1510897008373983998701686017209922960816127339466860789588606160332147878962564913406764611385229470849971288077374239278171471973749602656414838820558074700119192355231338991849403695036849047083282822255108161230346034624768585764808760248402952634113444599722515269998684427399124583405247144573527109975222081257008029790260559860849979421716752798127739488994858649526260912935259888277927955180906055358279957687314992052797112774530972530343550573798533793482820201610887225201749606682312677680359451371010180070950980849389904579670739506805226809592052548210734843148295456283103192907412693805696885095055

# f(t,u)=(x-t)(y-u)
# f(p,q)=0 (mod n)
# f(t,u)=xy-ux-ty+tu=xy-ux-ty (mod n)
# x, y ~ 2^1024 -> LLL

L = matrix([[n, 0, 0, 0], [x * y, 1, 0, 0], [-y, 0, 1, 0], [-x, 0, 0, 1]])
lb = [0, 1, 0, 0]
ub = [0, 1, 2**1024, 2**1024]
sol = solve_inequality(L, lb, ub)

_, _, p, q = map(int, sol)
assert p * q == n
phi = (p - 1) * (q - 1)
d = pow(0x10001, -1, phi)
m = pow(c, d, n)
print(long_to_bytes(m))

作者的 intended solution 方法有點小小的不一樣，不過最後導出的結果和我是一樣的:

xy \equiv (p+bq)(ap+q) \equiv ap^2+bq^2 \equiv xq + yp \pmod{n}

tss2

#!/usr/local/bin/python

from hashlib import sha256
import fastecdsa.curve
import fastecdsa.keys
import fastecdsa.point

TARGET = b'flag'

curve = fastecdsa.curve.secp256k1

def input_point():
	x = int(input('x: '))
	y = int(input('y: '))
	return fastecdsa.point.Point(x, y, curve=curve)

def input_sig():
	c = int(input('c: '))
	s = int(input('s: '))
	return (c, s)

def hash_transcript(pk, R, msg):
	h = sha256()
	h.update(f'({pk.x},{pk.y})'.encode())
	h.update(f'({R.x},{R.y})'.encode())
	h.update(msg)
	return int.from_bytes(h.digest(), 'big') % curve.q

def verify(pk, msg, sig):
	c, s = sig
	R = s * curve.G + c * pk
	return c == hash_transcript(pk, R, msg)

if __name__ == '__main__':
	import sys

	if len(sys.argv) == 2 and sys.argv[1] == 'setup':
		sk1, pk1 = fastecdsa.keys.gen_keypair(curve)
		with open('key.txt', 'w') as f:
			f.write(f'{sk1}\n{pk1.x}\n{pk1.y}\n')
		exit()

	with open('key.txt') as f:
		sk1, x, y = map(int, f.readlines())
		pk1 = fastecdsa.point.Point(x, y, curve=curve)

	print(f'my public key: {(pk1.x, pk1.y)}')

	print('gimme your public key')
	pk2 = input_point()

	print('prove it!')
	sig = input_sig()
	if not verify(pk2, b'foo', sig):
		print('boo')
		exit()

	apk = pk1 + pk2
	print(f'aggregate public key: {(apk.x, apk.y)}')

	print('what message do you want to sign?')
	msg = bytes.fromhex(input('message: '))
	if msg == TARGET:
		print('anything but that')
		exit()

	k1, R1 = fastecdsa.keys.gen_keypair(curve)
	print(f'my nonce: {(R1.x, R1.y)}')

	print(f'gimme your nonce')
	R2 = input_point()

	R = R1 + R2
	print(f'aggregate nonce: {(R.x, R.y)}')

	c = hash_transcript(apk, R, msg)
	s = (k1 - c * sk1) % curve.q
	print(f'my share of the signature: {s}')

	print(f'gimme me the aggregate signature for "{TARGET}"')
	sig = input_sig()
	if verify(apk, TARGET, sig):
		with open('flag.txt') as f:
			flag = f.read().strip()
			print(flag)

和 tss1 類似，但是它這次在接受 $\text{pk}_2$ 之後會檢查你有沒有 foo 字串的 signature，作為一個 proof 來證明你真的知道 $\text{pk}_2$ 的 secret key。因此前面的 rogue public key attack 在這邊就沒有作用了。

我一開始的想法是說它既然要求的是 foo 的 signature，我可不可以用它的 signing oracle 的 sign foo，然後用得到的 $\text{apk}$ 去當作下一次連線的 $\text{pk}_2$ 送過去。

這樣想一想會發現你會得到的 public key 形式為 $\text{apk}_i = i \cdot \text{sk}_1 + \text{sk}_2$ ，所以只要重複做 $q$ 次之後 $\text{sk}_1$ 就會消失，代表我們知道 $\text{apk}_q$ 的 secret key。然而這個攻擊是行不通的，因為它需要 $q$ 次連線才能做到，這樣不如直接爆破 secret key 比較快。

總之這部分我還是有寫個 script 來說明這個我可以讓 server 出現 $\text{apk}_i$ 的可行性:

from pwn import process, remote, context
from fastecdsa import keys, point
import ast
from tss2 import hash_transcript, verify, curve, TARGET

sk2, pk2 = keys.gen_keypair(curve)

# context.log_level = "debug"


def sign(sk, pk, msg):
    k, R = keys.gen_keypair(curve)
    c = hash_transcript(pk, R, msg)
    s = (k - c * sk) % curve.q
    return c, s


io = process(["python", "tss2.py"])
io.recvuntil(b"my public key: ")
pk_tpl = ast.literal_eval(io.recvline().strip().decode())
pk1 = point.Point(*pk_tpl, curve=curve)
io.sendlineafter(b"x: ", str(pk2.x).encode())
io.sendlineafter(b"y: ", str(pk2.y).encode())
c, s = sign(sk2, pk2, b"foo")
io.sendlineafter(b"c: ", str(c).encode())
io.sendlineafter(b"s: ", str(s).encode())
apk = pk1 + pk2

msg = b"foo"
io.sendlineafter(b"sign?", msg.hex().encode())
io.recvuntil(b"my nonce: ")
R1_tpl = ast.literal_eval(io.recvline().strip().decode())
R1 = point.Point(*R1_tpl, curve=curve)
k2, R2 = keys.gen_keypair(curve)
io.sendlineafter(b"x: ", str(R2.x).encode())
io.sendlineafter(b"y: ", str(R2.y).encode())

io.recvuntil(b"my share of the signature: ")
s1 = int(io.recvline().strip().decode())

R = R1 + R2
c = hash_transcript(apk, R, msg)
s2 = (k2 - c * sk2) % curve.q

s = (s1 + s2) % curve.q
assert verify(apk, msg, (c, s))

io.close()


def cont(i, apk, c, s):
    io = process(["python", "tss2.py"])
    io.recvuntil(b"my public key: ")
    pk_tpl = ast.literal_eval(io.recvline().strip().decode())
    pk1 = point.Point(*pk_tpl, curve=curve)
    io.sendlineafter(b"x: ", str(apk.x).encode())
    io.sendlineafter(b"y: ", str(apk.y).encode())
    io.sendlineafter(b"c: ", str(c).encode())
    io.sendlineafter(b"s: ", str(s).encode())
    apk2 = pk1 + apk  # sk = sk1 + (sk1 + sk2)

    msg = b"foo"
    io.sendlineafter(b"sign?", msg.hex().encode())
    io.recvuntil(b"my nonce: ")
    R1_tpl = ast.literal_eval(io.recvline().strip().decode())
    R1 = point.Point(*R1_tpl, curve=curve)
    R2 = (i - 1) * R1  # see below
    io.sendlineafter(b"x: ", str(R2.x).encode())
    io.sendlineafter(b"y: ", str(R2.y).encode())
    io.recvuntil(b"my share of the signature: ")
    s1 = int(io.recvline().strip().decode())

    R = R1 + R2
    c = hash_transcript(apk2, R, msg)
    # s1 = (k1 - c * sk1) % curve.q
    # s2 = (k2 - c * ((i - 1) * sk1 + sk2)) % curve.q
    # if (i - 1) k1 = k2, (i - 1) * s1 - s2 = c * sk2 is known, so:
    s2 = ((i - 1) * s1 - c * sk2) % curve.q

    s = (s1 + s2) % curve.q
    assert verify(apk2, msg, (c, s))

    io.close()
    return apk2, c, s


sk1 = 76955832679704021796451678563974610015930082877934961757640258812995135898232
assert (sk1 + sk2) * curve.G == apk
apks = [None, apk]
for i in range(2, 5):
    print(i)
    apk, c, s = cont(i, apk, c, s)
    assert (i * sk1 + sk2) * curve.G == apk
    apks.append(apk)

後來花了不少時間之後我才想到說它題目 $\text{sk}_1$ 是靜態的，所以重複連線的話也是使用一樣的 key，然後又想到之前有在某個地方看過說某些 MPC protocol 在 concurrent 的情況下是不安全的。

所以找了一找就找到 On the (in)security of ROS。它那邊就是說有很多這類型的 protocol 在 concurrent 的情況下可以變成一個叫 ROS 的問題，而那邊論文就提出了一個攻擊可以在多項式時間內解決 ROS，因此代表很多同類型的 protocol 在 concurrent 狀況下是不安全的。

而 ROS Attack 一般來說是先收到對方傳來的 commitment $R$ ，然後在 concurrent 的情況下可以算出一些神奇的係數，然後針對想要 forge 的目標做一些處裡後可以得到某個 linear combination $\rho$ 可以去生成一些特殊的 challenge $c$ (hash value in Fiat–Shamir Transform)。把 $c$ 一次送給全部連線後可以得到一些 response $s$ ，而對它做 $\rho$ linear combination 就可以得到 forge 的 signature。

在這邊 threshold signature 的情況下 $R$ 是對方的 nonce，而 $c$ 是 hash_transcript(apk, R, msg)，所以我們可以就類似的方法去求出適當的 $R_2$ 讓 $c$ 變成我們想要的值，然後就可以 forge 出 signature 了。

不過這攻擊數學細節有點複雜，我自己也沒看懂，所以我只是拿論文 appendix 提供的 sage code，結合別人對同一篇論文寫的文章中的範例，對它亂做一些改動就弄出來了。可能以後還是得花時間好好研究一下。

from sage.all import GF
from pwn import process, remote
from fastecdsa import keys, point
import ast, random
from tss2 import hash_transcript, verify, curve, TARGET
from tqdm import tqdm
from concurrent.futures import ThreadPoolExecutor

sk2, pk2 = keys.gen_keypair(curve)


def connect(i):
    # io = process(["python", "tss2.py"])
    io = remote("challs.actf.co", 31302)
    return io


def sign(sk, pk, msg):
    k, R = keys.gen_keypair(curve)
    c = hash_transcript(pk, R, msg)
    s = (k - c * sk) % curve.q
    return c, s


def establish(io, sk2, pk2):
    io.recvuntil(b"my public key: ")
    pk_tpl = ast.literal_eval(io.recvline().strip().decode())
    pk1 = point.Point(*pk_tpl, curve=curve)
    io.sendlineafter(b"x: ", str(pk2.x).encode())
    io.sendlineafter(b"y: ", str(pk2.y).encode())
    c, s = sign(sk2, pk2, b"foo")
    io.sendlineafter(b"c: ", str(c).encode())
    io.sendlineafter(b"s: ", str(s).encode())
    apk = pk1 + pk2
    return apk


def do_sign_get_nonce_R1(io, msg):
    io.sendlineafter(b"sign?", msg.hex().encode())
    io.recvuntil(b"my nonce: ")
    R1_tpl = ast.literal_eval(io.recvline().strip().decode())
    R1 = point.Point(*R1_tpl, curve=curve)
    return R1


def send_nonce_R2_get_s(io, R2):
    io.sendlineafter(b"x: ", str(R2.x).encode())
    io.sendlineafter(b"y: ", str(R2.y).encode())

    io.recvuntil(b"my share of the signature: ")
    s1 = int(io.recvline().strip().decode())
    return s1


Zp = GF(curve.q)
ell = 256
messages = [f"message{i}".encode() for i in range(ell)]

# ios = [connect() for _ in tqdm(range(ell), desc="Init")]
# apks = [establish(io, sk2, pk2) for io in tqdm(ios, desc="Establish")]
# apk = apks[0]
# R1 = [
#     do_sign_get_nonce_R1(io, msg)
#     for io, msg in zip(tqdm(ios, desc="Get nonce"), messages)
# ]

with ThreadPoolExecutor(max_workers=32) as executor:
    ios = list(tqdm(executor.map(connect, range(ell)), desc="Init", total=ell))
    apks = list(
        tqdm(
            executor.map(establish, ios, [sk2] * ell, [pk2] * ell),
            desc="Establish",
            total=ell,
        )
    )
    apk = apks[0]
    R1 = list(
        tqdm(
            executor.map(do_sign_get_nonce_R1, ios, messages),
            desc="Get nonce",
            total=ell,
        )
    )
    print("done, forging signature...")

# idk what am I doing here, but blindly modifying the code from following sources works...
# https://eprint.iacr.org/2020/945.pdf (Appendix)
# https://qsang.xin/2023/05/23/Onthe-in-securityofROS/
# it appears to find some magic coeffficients that can forge signatures with linear combination of existing signatures...

k2 = [[random.randrange(curve.q), random.randrange(curve.q)] for i in range(ell)]
R2 = [[x * curve.G, y * curve.G] for x, y in k2]


c = [
    [hash_transcript(apk, R1[i] + R2[i][b], messages[i]) for b in range(2)]
    for i in range(ell)
]
g_func = lambda x, z=0: sum(
    [int(Zp(2) ** i / (c[i][1] - c[i][0])) * x[i] for i in range(ell)], z
)
forged_R = g_func(R1, z=point.Point.IDENTITY_ELEMENT)
forged_message = b"flag"
forged_c = hash_transcript(apk, forged_R, forged_message)
bits = [
    int(b)
    for b in bin((forged_c - g_func([c[i][0] for i in range(ell)])) % curve.q)[
        2:
    ].rjust(256, "0")
][::-1]
chosen_R2 = [R2[i][b] for (i, b) in enumerate(bits)]

with ThreadPoolExecutor(max_workers=32) as executor:
    s1 = list(
        tqdm(
            executor.map(send_nonce_R2_get_s, ios, chosen_R2),
            desc="Get signature share",
            total=ell,
        )
    )

signatures = [
    (int(c[i][bits[i]]), int(s1[i] + k2[i][bits[i]] - c[i][bits[i]] * sk2))
    for i in range(ell)
]
forged_signature = (
    forged_c,
    (g_func(s1) - forged_c * sk2) % curve.q,
)

print([verify(apk, messages[i], signatures[i]) for i in range(ell)])
print(verify(apk, forged_message, forged_signature))

c, s = forged_signature
io = ios[0]
io.sendlineafter(b"c: ", str(c).encode())
io.sendlineafter(b"s: ", str(s).encode())
io.interactive()
# actf{th1nk_0uts1de_th3_c0nn3ct1on_d953f18e8c0870e8}

作者的 solver

tss1#

BLÅHAJ#

tss2#

tss1

BLÅHAJ

tss2