DownUnderCTF 2024 - super party computation

normal.py

from pwn import process, context
from Crypto.PublicKey import ECC
from Crypto.Signature import DSS
from Crypto.Hash import SHA256
from Crypto.Util.number import bytes_to_long
import json
from server import key_agreement, Paillier_PublicKey, e_add_const, e_mul_const

CURVE = "p256"


class RPC:
    def __init__(self, io):
        self.io = io
        self._cached_methods = {}

    def recvjson(self):
        return json.loads(self.io.recvline().decode())

    def sendjson(self, d):
        self.io.sendline(json.dumps(d).encode())

    def recvuntil_json(self):
        while True:
            try:
                return self.recvjson()
            except json.decoder.JSONDecodeError:
                pass

    def __getattr__(self, name):
        if name in self._cached_methods:
            return self._cached_methods[name]

        def func(**kwargs):
            data = {"action": name}
            for k, v in kwargs.items():
                data[k] = v
            self.sendjson(data)
            return self.recvuntil_json()

        self._cached_methods[name] = func
        return func


# context.log_level = "debug"
io = process(["python", "server.py"])
rpc = RPC(io)

msg_to_sign = b"konpeko"
zvalue = bytes_to_long(SHA256.new(msg_to_sign).digest())

# phase 1
alice_key = ECC.generate(curve=CURVE)
ret1 = rpc.gen_keys(x=int(alice_key.pointQ.x), y=int(alice_key.pointQ.y))
bob_pub = ECC.construct(
    curve=CURVE, point_x=ret1["bob_ecdsa_pub"][0], point_y=ret1["bob_ecdsa_pub"][1]
)
pailler_pub = Paillier_PublicKey(ret1["paillier_pub"]["n"])
bob_ecdsa_priv_enc = ret1["bob_ecdsa_priv_enc"]
shared_ecdsa_pub_x, shared_ecdsa_pub_y = key_agreement(
    static_pub=bob_pub, static_priv=alice_key
)
shared_ecdsa_pub = ECC.construct(
    curve=CURVE, point_x=shared_ecdsa_pub_x, point_y=shared_ecdsa_pub_y
)
sig_scheme = DSS.new(shared_ecdsa_pub, "fips-186-3")

# phase 2
alice_nonce_key = ECC.generate(curve=CURVE)
ret2 = rpc.mul_share(x=int(alice_nonce_key.pointQ.x), y=int(alice_nonce_key.pointQ.y))
bob_nonce_pub = ECC.construct(
    curve=CURVE, point_x=ret2["bob_nonce_pub"][0], point_y=ret2["bob_nonce_pub"][1]
)

# phase 3
curve_q = int(alice_key._curve.order)
sig_r = int(key_agreement(static_pub=bob_nonce_pub, static_priv=alice_nonce_key)[0])
alice_d = int(alice_key.d)
alice_k = int(alice_nonce_key.d)
t = e_mul_const(pailler_pub, bob_ecdsa_priv_enc, sig_r)
t = e_mul_const(pailler_pub, t, alice_d)
t = e_add_const(pailler_pub, t, zvalue)
t = e_mul_const(pailler_pub, t, pow(alice_k, -1, curve_q))
# t = enc(k_alice^-1 * (z + d_alice * d_bob * sig_r))

ret3 = rpc.sign_and_validate(message=msg_to_sign.hex(), partial_sig_ciphertext=t)
signature = bytes.fromhex(ret3["signature"])

try:
    sig_scheme.verify(SHA256.new(msg_to_sign), signature)
    print("Signature is valid")
except ValueError:
    print("Signature is invalid")

solve.py

from pwn import process, remote, context
from Crypto.PublicKey import ECC
from Crypto.Signature import DSS
from Crypto.Hash import SHA256
from Crypto.Util.number import bytes_to_long
import json
from server import key_agreement, Paillier_PublicKey, e_add_const, e_mul_const

CURVE = "p256"


class RPC:
    def __init__(self, io):
        self.io = io
        self._cached_methods = {}

    def recvjson(self):
        return json.loads(self.io.recvline().decode())

    def sendjson(self, d):
        self.io.sendline(json.dumps(d).encode())

    def recvuntil_json(self):
        while True:
            try:
                return self.recvjson()
            except json.decoder.JSONDecodeError:
                pass

    def __getattr__(self, name):
        if name in self._cached_methods:
            return self._cached_methods[name]

        def func(**kwargs):
            data = {"action": name}
            for k, v in kwargs.items():
                data[k] = v
            self.sendjson(data)
            return self.recvuntil_json()

        self._cached_methods[name] = func
        return func


# context.log_level = "debug"
# io = process(["python", "server.py"])
io = remote("2024.ductf.dev", 30021)
rpc = RPC(io)

msg_to_sign = b"pekomiko"
zvalue = bytes_to_long(SHA256.new(msg_to_sign).digest())

# phase 1
alice_d = 12345
alice_key = ECC.construct(curve=CURVE, d=alice_d)
ret1 = rpc.gen_keys(x=int(alice_key.pointQ.x), y=int(alice_key.pointQ.y))
bob_pub = ECC.construct(
    curve=CURVE, point_x=ret1["bob_ecdsa_pub"][0], point_y=ret1["bob_ecdsa_pub"][1]
)
pailler_pub = Paillier_PublicKey(ret1["paillier_pub"]["n"])
bob_ecdsa_priv_enc = ret1["bob_ecdsa_priv_enc"]
shared_ecdsa_pub_x, shared_ecdsa_pub_y = key_agreement(
    static_pub=bob_pub, static_priv=alice_key
)
shared_ecdsa_pub = ECC.construct(
    curve=CURVE, point_x=shared_ecdsa_pub_x, point_y=shared_ecdsa_pub_y
)
sig_scheme = DSS.new(shared_ecdsa_pub, "fips-186-3")

curve_q = int(alice_key._curve.order)
yb = 0
for l in range(1, 256 + 1):
    print(f"{l = }")
    # phase 2
    alice_k = 2**l
    alice_nonce_key = ECC.construct(curve=CURVE, d=alice_k % curve_q)
    ret2 = rpc.mul_share(
        x=int(alice_nonce_key.pointQ.x), y=int(alice_nonce_key.pointQ.y)
    )
    bob_nonce_pub = ECC.construct(
        curve=CURVE, point_x=ret2["bob_nonce_pub"][0], point_y=ret2["bob_nonce_pub"][1]
    )

    # phase 3
    # based on https://eprint.iacr.org/2023/1234.pdf section 4, with some modifications
    sig_r = int(key_agreement(static_pub=bob_nonce_pub, static_priv=alice_nonce_key)[0])
    rx = sig_r * alice_d % curve_q
    rx_prime = rx if rx % 2 != 0 else rx + curve_q
    t = e_mul_const(pailler_pub, bob_ecdsa_priv_enc, rx_prime)
    t = e_mul_const(pailler_pub, t, pow(alice_k, -1, pailler_pub.n))

    eps = pow(alice_k, -1, curve_q) - pow(alice_k, -1, pailler_pub.n)
    zeta = pow(alice_k, -1, curve_q) * zvalue % curve_q
    t = e_add_const(pailler_pub, t, eps * rx_prime * yb + zeta)

    ret3 = rpc.sign_and_validate(message=msg_to_sign.hex(), partial_sig_ciphertext=t)

    if "signature" not in ret3:
        yb += 2 ** (l - 1)
    print(f"{yb:0256b}")
    # bob_priv = ret1["bob_priv"]
    # print(f"{bob_priv:0256b}")
    print()

assert ECC.construct(curve=CURVE, d=yb).pointQ == bob_pub.pointQ
shared_key = ECC.construct(curve=CURVE, d=(alice_d * yb) % curve_q)
assert shared_key.pointQ == shared_ecdsa_pub.pointQ
target_msg = b"We, Alice and Bob, jointly agree to declare war on the emus"
sig_scheme_priv = DSS.new(shared_key, "fips-186-3")
signature = sig_scheme_priv.sign(SHA256.new(target_msg))
try:
    sig_scheme.verify(SHA256.new(target_msg), signature)
    print("good")
except ValueError:
    print("bad")

print(rpc.get_flag(message=target_msg.hex(), signature=signature.hex()))
# DUCTF{d0nt_w0rry_th3_3mus_w1ll_b3_0kay}