authored by yu121
オブリビエイト！
import os
import signal
import secrets
from fastecdsa.curve import secp256k1
from fastecdsa.point import Point
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import long_to_bytes
signal.alarm(60)
flag = os.environ.get("FLAG", "Alpaca{**** REDACTED ****}").encode()
# Oblivious Transfer using Elliptic Curves
G = secp256k1.G
a = secrets.randbelow(secp256k1.q)
A = a * G
print(f"{A.x = }")
print(f"{A.y = }")
x, y = map(int, input("B> ").split(","))
B = Point(x, y, secp256k1)
k0 = long_to_bytes((a * B).x, 32)
k1 = long_to_bytes((a * (B - A)).x, 32)
def encrypt(message, key):
return AES.new(key, AES.MODE_ECB).encrypt(pad(message, 16))
print(encrypt(flag[0::3], k0).hex())
print(encrypt(flag[1::3], k1).hex())
print(encrypt(flag[2::3], bytes(c0 ^ c1 for c0, c1 in zip(k0, k1))).hex())
Oblivious Transfer using Elliptic Curvesとコメントが書かれています。
https://arxiv.org/pdf/cs/0605114
下記論文を読んでみると、Chosen one-out-of-two oblivious transferとプロトコルがあるらしいです。
$k_0, k_1$とbytes(c0 ^ c1 for c0, c1 in zip(k0, k1))の値を求めたらフラグが求められます。
解法
先ほど紹介した論文によると、
- 2つの情報のうち、1つしか取得できない
- AliceはBobが2つの秘密のうちどちらを得たのかわからない
となるらしいです。
最初に、$k_0$を求めてみましょう。k0 = long_to_bytes((a * B).x, 32)によって求められます。
さて、少し上のコードでG = secp256k1.Gと定義されており、その後、$a\cdot G$を計算しています。つまり、$G$は既知であるため、$a$も復元することができます。よって、今回$B=G$と定義し、代入すれば求められます。
次に、$k_1$を求めてみましょう。k1 = long_to_bytes((a * (B - A)).x, 32)によって求められます。
$B-A$が$G$となれば嬉しいので、$B = A + G$とすれば$k_0$と同様に求めることができます。
最後に、bytes(c0 ^ c1 for c0, c1 in zip(k0, k1))を求めてみましょう。今回の問題プロトコルから、$k_0, k_1$のどちらかしか情報を得ることができません。つまり、どうにかして、$k_0 = k_1$となるようにできないか考えてみましょう。
$k_0 = k_1$より、
$$
a \cdot B = \pm a \cdot(B-A)
$$
を解いていき関係性を探していけば良さそうです。
$a \cdot(B-A)$のとき、
\begin{align}
a \cdot B &= a \cdot(B-A)\\
a \cdot B &= a\cdot B - a\cdot A\\
0 &= A
\end{align}
となります。
$-a \cdot(B-A)$のとき、
\begin{align}
a \cdot B &= -a \cdot(B-A)\\
a \cdot B &= - a\cdot B + a\cdot A\\
2 a \cdot B &= a\cdot A\\
B &= A/2
\end{align}
となります。以上より、$A/2$とすることにより、$k_0 \oplus k_1$の値は0となり、encrypt関数のkeyは0となるため復元できます。
from pwn import *
from fastecdsa.curve import secp256k1
from fastecdsa.point import Point
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from Crypto.Util.number import long_to_bytes, inverse
from itertools import zip_longest
HOST = "34.170.146.252"
PORT = 60975
def decrypt(c, key):
c = bytes.fromhex(c)
aes = AES.new(key, AES.MODE_ECB)
return unpad(aes.decrypt(c), 16)
def get_A(io):
io.recvuntil(b'A.x = ')
Ax = int(io.recvline().strip())
io.recvuntil(b'A.y = ')
Ay = int(io.recvline().strip())
return Ax, Ay
def get_flag0():
io = remote(HOST, PORT)
Ax, Ay = get_A(io)
G = secp256k1.G
io.sendlineafter("B> ", f"{G.x},{G.y}".encode())
c0 = io.recvline().strip().decode()
k0 = long_to_bytes(Ax, 32)
io.close()
return decrypt(c0, k0)
def get_flag1():
io = remote(HOST, PORT)
Ax, Ay = get_A(io)
G = secp256k1.G
A = Point(Ax, Ay, secp256k1)
B = A + G
io.sendlineafter("B> ", f"{B.x},{B.y}".encode())
_ = io.recvline().strip().decode()
c1 = io.recvline().strip().decode()
k1 = long_to_bytes(Ax, 32)
io.close()
return decrypt(c1, k1)
def get_flag2():
io = remote(HOST, PORT)
Ax, Ay = get_A(io)
A = Point(Ax, Ay, secp256k1)
B = inverse(2, secp256k1.q) * A
io.sendlineafter("B> ", f"{B.x},{B.y}".encode())
_ = io.recvline().strip().decode()
_ = io.recvline().strip().decode()
c2 = io.recvline().strip().decode()
k2 = b"\x00" * 32
io.close()
return decrypt(c2, k2)
print("[+] Get flag0")
flag0 = get_flag0()
print("[+] Get flag1")
flag1 = get_flag1()
print("[+] Get flag2")
flag2 = get_flag2()
flag = bytearray()
for a, b, c in zip_longest(flag0, flag1, flag2, fillvalue=None):
if a is not None:
flag.append(a)
if b is not None:
flag.append(b)
if c is not None:
flag.append(c)
print("[+] Flag:", flag.decode())
Flag: Alpaca{secure_ot+safe_ec=insecure_otec:3ce8a76d0b0f079dbd}