# Plaid 2024
*Note: Không giải được câu nào trong lúc giải diễn ra . Nên mình sẽ dựng local mà giải lại tất cả các bài trong khả năng.*
# **DHCPPP**
Source:
```py
import time, zlib
import secrets
import hashlib
import dns.nameserver
import requests
from Crypto.Cipher import ChaCha20_Poly1305
import dns.resolver
CHACHA_KEY = secrets.token_bytes(32)
TIMEOUT = 1e-1
flag = "PCTF{d0nt_r3u5e_th3_n0nc3_d4839ed727736624}"
def encrypt_msg(msg, nonce):
# In case our RNG nonce is repeated, we also hash
# the message in. This means the worst-case scenario
# is that our nonce reflects a hash of the message
# but saves the chance of a nonce being reused across
# different messages
nonce = sha256(msg[:32] + nonce[:32])[:12]
cipher = ChaCha20_Poly1305.new(key=CHACHA_KEY, nonce=nonce)
ct, tag = cipher.encrypt_and_digest(msg)
return ct+tag+nonce
def decrypt_msg(msg):
ct = msg[:-28]
tag = msg[-28:-12]
nonce = msg[-12:]
cipher = ChaCha20_Poly1305.new(key=CHACHA_KEY, nonce=nonce)
pt = cipher.decrypt_and_verify(ct, tag)
return pt
def calc_crc(msg):
return zlib.crc32(msg).to_bytes(4, "little")
def sha256(msg):
return hashlib.sha256(msg).digest()
RNG_INIT = secrets.token_bytes(512)
class DHCPServer:
def __init__(self):
self.leases = []
self.ips = [f"192.168.1.{i}" for i in range(3, 64)]
self.mac = bytes.fromhex("1b 7d 6f 49 37 c9")
self.gateway_ip = "192.168.1.1"
self.leases.append(("192.168.1.2", b"rngserver_0", time.time(), []))
def get_lease(self, dev_name):
if len(self.ips) != 0:
ip = self.ips.pop(0) # get the first available IP
self.leases.append((ip, dev_name, time.time(), []))
else:
# relinquish the oldest lease
old_lease = self.leases.pop(0)
ip = old_lease[0]
self.leases.append((ip, dev_name, time.time(), []))
pkt = bytearray(
bytes([int(x) for x in ip.split(".")]) +
bytes([int(x) for x in self.gateway_ip.split(".")]) +
bytes([255, 255, 255, 0]) +
bytes([8, 8, 8, 8]) +
bytes([8, 8, 4, 4]) +
dev_name +
b"\x00"
)
#devname = msg[1:] '149.28.155.175'
#pkt = bytes(ip + gateway + [255, 255, 255, 0] + [8, 8, 8, 8] + [8, 8, 4, 4] + devname)
pkt = b"\x02" + encrypt_msg(pkt, self.get_entropy_from_lavalamps()) + calc_crc(pkt)
return pkt
def get_entropy_from_lavalamps(self):
# Get entropy from all available lava-lamp RNG servers
# Falling back to local RNG if necessary
entropy_pool = RNG_INIT
for ip, name, ts, tags in self.leases:
if b"rngserver" in name:
try:
# get entropy from the server
output = requests.get(f"http://{ip}/get_rng", timeout=TIMEOUT).text
entropy_pool += sha256(output.encode())
except:
# if the server is broken, get randomness from local RNG instead
entropy_pool += sha256(secrets.token_bytes(512))
return sha256(entropy_pool)
def process_pkt(self, pkt):
assert pkt is not None
src_mac = pkt[:6]
dst_mac = pkt[6:12] #mac
msg = pkt[12:]
if dst_mac != self.mac:
return None
if src_mac == self.mac:
return None
if len(msg) and msg.startswith(b"\x01"):
dev_name = msg[1:] #bytes
lease_resp = self.get_lease(dev_name)
return (
self.mac +
src_mac + # dest mac
lease_resp
)
else:
return None
class FlagServer:
def __init__(self, dhcp):
self.mac = bytes.fromhex("53 79 82 b5 97 eb")
self.dns = dns.resolver.Resolver()
self.process_pkt(dhcp.process_pkt(self.mac + dhcp.mac + b"\x01" + b"flag_server"))
def send_flag(self):
# with open("flag.txt", "r") as f:
# flag = f.read().strip()
curl("example.com", f"/{flag}", self.dns)
def process_pkt(self, pkt):
assert pkt is not None
src_mac = pkt[:6]
dst_mac = pkt[6:12]
msg = pkt[12:]
if dst_mac != self.mac:
return None
if src_mac == self.mac:
return None
if len(msg) and msg.startswith(b"\x02"):
# lease response
pkt = msg[1:-4]
pkt = decrypt_msg(pkt)
crc = msg[-4:]
assert crc == calc_crc(pkt)
# print(pkt)
self.ip = ".".join(str(x) for x in pkt[0:4])
self.gateway_ip = ".".join(str(x) for x in pkt[4:8])
self.subnet_mask = ".".join(str(x) for x in pkt[8:12])
self.dns1 = ".".join(str(x) for x in pkt[12:16])
self.dns2 = ".".join(str(x) for x in pkt[16:20])
self.dns.nameservers = [self.dns1, self.dns2]
assert pkt.endswith(b"\x00")
print("[FLAG SERVER] [DEBUG] Got DHCP lease", self.ip, self.gateway_ip, self.subnet_mask, self.dns1, self.dns2)
return None
elif len(msg) and msg.startswith(b"\x03"):
# FREE FLAGES!!!!!!!
self.send_flag()
return None
else:
return None
def curl(url, path, dns):
ip = str(dns.resolve(url).response.resolve_chaining().answer).strip().split(" ")[-1]
url = "http://" + ip
print(f"Sending flage to {url}")
requests.get(url + path)
if __name__ == "__main__":
dhcp = DHCPServer()
flagserver = FlagServer(dhcp)
while True:
pkt = bytes.fromhex(input("> ").replace(" ", "").strip())
out = dhcp.process_pkt(pkt)
if out is not None:
print(out.hex())
out = flagserver.process_pkt(pkt)
if out is not None:
print(out.hex())
```
## Phân tích source code:
Điểm đầu tiên cần lưu ý là hàm `get_entropy_from_lavalamps(self)`
```python
def get_entropy_from_lavalamps(self):
# Get entropy from all available lava-lamp RNG servers
# Falling back to local RNG if necessary
entropy_pool = RNG_INIT
for ip, name, ts, tags in self.leases:
if b"rngserver" in name:
try:
# get entropy from the server
output = requests.get(f"http://{ip}/get_rng", timeout=TIMEOUT).text
entropy_pool += sha256(output.encode())
except:
# if the server is broken, get randomness from local RNG instead
entropy_pool += sha256(secrets.token_bytes(512))
return sha256(entropy_pool)
```
Ta thấy `entropy_pool` chỉ được thay đổi khi đầu vào của ta chứa chuỗi `b"rngserver"` . Như vậy, nếu như đầu vào của ta không chưa chuỗi `b"rngserver"` thì output của hàm `get_entropy_from_lavalamps()` cũng sẽ giống hệt nhau.
Hàm tiếp theo cần chú ý là `encrypt_msg(msg, nonce)` với nonce là output của hàm `get_entropy_from_lavalamps()`
```python
def encrypt_msg(msg, nonce):
# In case our RNG nonce is repeated, we also hash
# the message in. This means the worst-case scenario
# is that our nonce reflects a hash of the message
# but saves the chance of a nonce being reused across
# different messages
nonce = sha256(msg[:32] + nonce[:32])[:12]
cipher = ChaCha20_Poly1305.new(key=CHACHA_KEY, nonce=nonce)
ct, tag = cipher.encrypt_and_digest(msg)
return ct+tag+nonce
```
Để giảm thiểu tình trạng `nonce-reuse` thì hàm `encrypt_msg(msg, nonce)` sẽ tính một nonce mới bằng cách `sha256(msg[:32] + nonce[:32])`và lấy 12 bytes đầu tiên. `msg` có format như sau:
```python
bytearray(
bytes([int(x) for x in ip.split(".")]) +
bytes([int(x) for x in self.gateway_ip.split(".")]) +
bytes([255, 255, 255, 0]) +
bytes([8, 8, 8, 8]) +
bytes([8, 8, 4, 4]) +
dev_name +
b"\x00"
)
```
Ý tưởng ở đây là nonce-reused attack và mục đích của ta là thay đổi `bytes([8, 8, 8, 8])` thành DNS server của ta để nhận flag.
## [ChaCha20-Poly1305](https://en.wikipedia.org/wiki/ChaCha20-Poly1305)
Có thể hiểu đơn giản là ChaCha20 cipher kết hợp với **[Poly1305](https://en.wikipedia.org/wiki/Poly1305) MAC.**
Để thực hiện **Poly1305 nonce reuse attack** ta cần tìm hiểu cơ chế tạo `tag` của Poly1305.
Đầu tiên, khởi tạo một đa thức thuộc trường $F_p$ với $p = 2^{130} - 5$ và là số nguyên tố.
$$
P(x) = c_1x^q + c_2p^{q-1}+ ...+c_qx \mod p
$$
Với hệ số $c_i$ là từng block 16 bytes của plaintext được xác thực. Và $tag$ có đạng
$$
tag = (P(r)+s) \mod 2^{128}
$$
Với r và s là secret keys.
Ta cần hai đa thức ứng với 2 message khác nhau nhưng có cùng giá trị $r$ và $s$ bởi vì chúng phụ thuộc vào key (luôn không đổi) và nonce (ta có thể tác động để tạo ra 2 bản mã với cùng giá trị nonce).
$$
tag = ((c_1r^q + c_2r^{q-1}+ ...+c_qr \mod p) + s) \mod 2^{128} \\
$$
$$
tag' = ((c_1'r^q + c_2'r^{q-1}+ ...+c_q'r \mod p) + s) \mod 2^{128}
$$
Trừ 2 phương trình với nhau để triệu tiêu $s$:
$$
tag - tag' + k.2^{128} = (c_1-c_1')r^q + (c_2 - c_2')r^{q-1} + ... + (c_q - c_q')r \mod p
$$
Với $-4 ≤ k ≤ 4$ vì $p > 3.2^{128}$. Vì vậy, ta có thể bruteforce $k$ để tìm nghiệm $r$ của phương trình trên.
Khi đã có được $r$, ta tìm lại $s$ như sau:
$$
s = tag - (c_1r^q + c_2r^{q-1}+ ...+c_qr \mod p) \mod 2^{128}
$$
Tiếp theo ta cần convert ciphertext sẽ được xác thực theo format mà **Poly1305** yêu cầu (theo [Pycryptodome](https://github.com/Legrandin/pycryptodome/blob/master/lib/Crypto/Cipher/ChaCha20_Poly1305.py#L162))
Ta sẽ thử tạo 2 ciphertext có nonce giống hệt nhau, vì đây là thử nghiệm nên sẽ gửi 2 `dev_name` giống hệt nhau nếu thu được 2 ciphertext giống nhau thì thỏa yêu cầu:
```python
from pwn import *
dhcp_mac = bytes.fromhex("1b 7d 6f 49 37 c9")
flag_mac = bytes.fromhex("53 79 82 b5 97 eb")
fake_mac = b'\x00'*6
conn = process(['python3', 'dhcppp.py'])
print(conn.recvline().strip().decode())
def send_dhcp(dev_name: bytes):
payload = fake_mac + dhcp_mac + b'\x01' + dev_name
conn.sendline(payload.hex().encode())
return conn.recvline().strip().decode()[2:]
def send_flag_server(enc_pkt: bytes):
payload = fake_mac + flag_mac + b'\x02' + enc_pkt
conn.sendlineafter(b'> ', payload.hex().encode())
return conn.recvline().strip().decode()
dev_name = b'A'*10
for i in range(3, 64-1):
send_dhcp(dev_name)
enc1 = send_dhcp(dev_name)
print(enc1)
pkt = enc1[12*2+2:]
print(send_flag_server(bytes.fromhex(pkt)))
for i in range(3, 64):
send_dhcp(dev_name)
enc2 = send_dhcp(dev_name)
print(enc2)
pkt = enc2[12*2+2:]
print(send_flag_server(bytes.fromhex(pkt)))
```
Và thu được:
Như vậy nếu đổi thành 2 `dev_name` khác nhau thì ta sẽ thu được 2 ciphertext có cùng nonce và key
```python
dev_name = b'A'*10
for i in range(3, 64-1):
send_dhcp(dev_name)
enc1 = send_dhcp(dev_name)
for i in range(3, 64):
send_dhcp(dev_name)
dev_name = b'A'*9 + b'B'
enc2 = send_dhcp(dev_name)
```
Bước tiếp theo là convert theo format yêu cầu của **Poly1305,** cơ bản là như sau (theo **[RFC 7539](https://datatracker.ietf.org/doc/html/rfc7539#autoid-22)** mục 2.8.1):
```
chacha20_aead_encrypt(aad, key, iv, constant, plaintext):
nonce = constant | iv
otk = poly1305_key_gen(key, nonce)
ciphertext = chacha20_encrypt(key, 1, nonce, plaintext)
mac_data = aad | pad16(aad)
mac_data |= ciphertext | pad16(ciphertext)
mac_data |= num_to_4_le_bytes(aad.length)
mac_data |= num_to_4_le_bytes(ciphertext.length)
tag = poly1305_mac(mac_data, otk)
return (ciphertext, tag)
```
ở đây ta không sử dụng `aad` nên `len(aad)` sẽ là 0.
```python
def convert(msg):
return msg + b'\x00'*(16-(len(msg)%16)) + long_to_bytes(0, 8)[::-1] + long_to_bytes(len(msg), 8)[::-1]
ct1 = convert(ct1)
ct2 = convert(ct2)
```
Tiếp đến ta khởi tạo đa thức như sau (theo **[RFC 7539](https://datatracker.ietf.org/doc/html/rfc7539#section-2.5.1)** mục 2.5.1):
```
clamp(r): r &= 0x0ffffffc0ffffffc0ffffffc0fffffff
poly1305_mac(msg, key):
r = (le_bytes_to_num(key[0..15])
clamp(r)
s = le_num(key[16..31])
accumulator = 0
p = (1<<130)-5
for i=1 upto ceil(msg length in bytes / 16)
n = le_bytes_to_num(msg[((i-1)*16)..(i*16)] | [0x01])
a += n
a = (r * a) % p
end
a += s
return num_to_16_le_bytes(a)
end
```
Code:
```python
p = 2**130 - 5
PR = PolynomialRing(GF(p), 'r')
r = PR.gen()
count = (len(ct1) + 15)//16
tag1 = int.from_bytes(tag1, 'little')
tag2 = int.from_bytes(tag2, 'little')
a1 = 0
for i in range(count):
n = ct1[i*16:(i+1)*16] + b'\x01'
n = int.from_bytes(n, 'little')
a1 += n
a1 = a1*r
count = (len(ct2) + 15)//16
a2 = 0
for i in range(count):
n = ct2[i*16:(i+1)*16] + b'\x01'
n = int.from_bytes(n, 'little')
a2 += n
a2 = a2*r
rs = set()
for k in range(-4, 5):
roots = (a1 - a2 - (tag1 - tag2) + k * 2**128).roots()
for root in roots:
rs.add(int(root[0]))
```
Ta biết được `r = (le_bytes_to_num(key[0..15])` như vậy r tối đa có 128 bit và ta sẽ loại các trường hợp $> 128$ (phần lớn là $> 128$ bit).
```python
for r in rs:
if r.bit_length() <= 128:
break
s = (tag1 - int(a1(r))) % 2**128
def g(ct, r, s):
count = (len(ct) + 15) // 16
a = 0
for i in range(count):
n = ct[i*16:(i+1)*16] + b'\x01'
n = int.from_bytes(n, 'little')
a += n
a = a*r % p
a = (a+s) % 2**128
return a
assert g(ct1, r, s) == tag1
assert g(ct2, r, s) == tag2
```
Bước tiếp theo ta cần tạo một ciphertext mới mà chứa dns server mà mình muốn, vì mã hóa bằng chacha20 và t đã biết được plaintext nên chỉ cần recover lại keystream và tạo ciphertext bằng keystream đó.
```python
pkt = bytearray(
bytes([192, 168, 1, 2]) +
bytes([192, 168, 1, 1]) +
bytes([255, 255, 255, 0]) +
bytes([8, 8, 8, 8]) +
bytes([8, 8, 4, 4]) +
dev_name +
b"\x00"
)
fake_pkt = bytearray(
bytes([192, 168, 1, 2]) +
bytes([192, 168, 1, 1]) +
bytes([255, 255, 255, 0]) +
bytes([0, 0, 0, 0]) + #ip dns server
bytes([8, 8, 4, 4]) +
dev_name +
b"\x00"
)
keysteam = xor(current_ct, pkt)
ct = xor(fake_pkt, keysteam)
```
Phần còn lại là tính tag ứng với ciphertext mới của ta và gửi đến server, lưu ý cũng cần phải đưa ciphertext về format mà **Poly1305** yêu cầu và thêm giá trị `calc_crc()` ở cuối payload.
```python
tag = long_to_bytes(g(convert(ct), r, s), 16)[::-1]
payload = ct + tag + nonce1 + calc_crc(fake_pkt)
print(send_flag_server(payload))
payload = fake_mac + flag_mac + b'\x03' + b'\x00'
conn.sendlineafter(b'> ', payload.hex().encode())
```
Cuối cùng ta cần giải quyết vấn đề server dns mà mình chưa có giải pháp 😕
### ***Update***
Cuối cùng mình đã tìm được giải pháp là sử dụng [fakedns](https://github.com/pathes/fakedns/tree/master), dựng fake dns trên 1 con vps và sửa dns mặc định đã nhận được thành ip của con vps sau đó dùng `nc -lvnp 80` để nhận flag (nhờ teammate chứ mình cũng k rành mấy cái này 😅). Vì hôm nay (18/04/2024) mặc dù giải đã end nhưng chall vẫn còn mở nên mình đã thử connect và exploit bằng script của mình.
→ kết quả
Full script:
```python
from pwn import *
from Crypto.Util.number import *
import zlib
from tqdm import tqdm
dhcp_mac = bytes.fromhex("1b 7d 6f 49 37 c9")
flag_mac = bytes.fromhex("53 79 82 b5 97 eb")
fake_mac = b'\x00'*6
def calc_crc(msg):
return zlib.crc32(msg).to_bytes(4, "little")
def parse(enc):
enc_msg = enc[12 :]
enc_msg = enc_msg[1 :-4]
ct = enc_msg[:-28]
tag = enc_msg[-28 :-12 ]
nonce = enc_msg[-12:]
return ct, tag, nonce
def convert(msg):
return msg + b'\x00'*(16 -(len(msg)%16)) + long_to_bytes(0 , 8 )[::-1] + long_to_bytes(len(msg), 8)[::-1]
while True:
# conn = process(['python3', 'dhcppp.py'])
conn = remote('dhcppp.chal.pwni.ng', 1337)
# context.log_level = 'DEBUG'
print(conn.recvline().strip().decode())
def send_dhcp(dev_name: bytes):
payload = fake_mac + dhcp_mac + b'\x01' + dev_name
conn.sendline(payload.hex().encode())
return conn.recvline().strip().decode()[2:]
def send_flag_server(enc_pkt: bytes):
payload = fake_mac + flag_mac + b'\x02' + enc_pkt
conn.sendlineafter(b'> ', payload.hex().encode())
return conn.recvline().strip().decode()
dev_name = b'A'*32
for i in tqdm(range(3 , 64 - 1)):
send_dhcp(dev_name)
enc1 = send_dhcp(dev_name)
for i in tqdm(range(3 , 64)):
send_dhcp(dev_name)
dev_name = b'A'*31 + b'B'
enc2 = send_dhcp(dev_name)
ct1, tag1, nonce1 = parse(bytes.fromhex(enc1))
ct2, tag2, nonce2 = parse(bytes.fromhex(enc2))
current_ct = ct2
ct1 = convert(ct1)
ct2 = convert(ct2)
print('ct1 = ', ct1)
print('ct2 = ', ct2)
from sage.all import *
p = 2**130 - 5
PR = PolynomialRing(GF(p), 'r')
r = PR.gen()
count = (len(ct1) + 15)//16
tag1 = int.from_bytes(tag1, 'little')
tag2 = int.from_bytes(tag2, 'little')
a1 = 0
for i in range(count):
n = ct1[i*16:(i+1)*16] + b'\x01'
n = int.from_bytes(n, 'little')
a1 += n
a1 = a1*r
count = (len(ct2) + 15)//16
a2 = 0
for i in range(count):
n = ct2[i*16:(i+1)*16] + b'\x01'
n = int.from_bytes(n, 'little')
a2 += n
a2 = a2*r
rs = set()
for k in range(-4, 5):
roots = (a1 - a2 - (tag1 - tag2) + k * 2**128).roots()
for root in roots:
rs.add(int(root[0]))
pos_r = []
for r in rs:
if r.bit_length() <= 128:
pos_r.append(r)
def g(ct, r, s):
count = (len(ct) + 15) // 16
a = 0
for i in range(count):
n = ct[i*16:(i+1)*16] + b'\x01'
n = int.from_bytes(n, 'little')
a += n
a = a*r % p
a = (a+s) % 2**128
return a
pkt = bytearray(
bytes([192, 168, 1, 2]) +
bytes([192, 168, 1, 1]) +
bytes([255, 255, 255, 0]) +
bytes([8, 8, 8, 8]) +
bytes([8, 8, 4, 4]) +
dev_name +
b"\x00"
)
fake_pkt = bytearray(
bytes([192, 168, 1, 2]) +
bytes([192, 168, 1, 1]) +
bytes([255, 255, 255, 0]) +
bytes([0, 0, 0, 0]) + #ip dns
bytes([0, 0, 0, 0]) + #ip dns
dev_name +
b"\x00"
)
keysteam = xor(current_ct, pkt)
ct = xor(fake_pkt, keysteam)
for r in pos_r:
try:
s = (tag1 - int(a1(r))) % 2**128
assert g(ct1, r, s) == tag1
assert g(ct2, r, s) == tag2
tag = long_to_bytes(g(convert(ct), r, s), 16)[::-1]
payload = ct + tag + nonce1 + calc_crc(fake_pkt)
print(send_flag_server(payload))
payload = fake_mac + flag_mac + b'\x03' + b'\x00'
conn.sendlineafter(b'> ', payload.hex().encode())
conn.interactive()
except:
continue
conn.close()
```
### ***references:***
[https://crypto.stackexchange.com/questions/83629/forgery-attack-on-poly1305-when-the-key-and-nonce-reused](https://crypto.stackexchange.com/questions/83629/forgery-attack-on-poly1305-when-the-key-and-nonce-reused)
[https://datatracker.ietf.org/doc/html/rfc7539](https://datatracker.ietf.org/doc/html/rfc7539)
[https://github.com/pathes/fakedns/tree/master](https://github.com/pathes/fakedns/tree/master)
# Paranormial Commitment Scheme
## Phân tích
Tổng quan toàn bộ challenge là mô phỏng lại cơ chế của KZG commitment scheme. Cụ thể như sau:
Chi tiết về KZG commitment: https://dankradfeist.de/ethereum/2020/06/16/kate-polynomial-commitments.html#fn:2
### **Elliptic curves and pairings**
Gọi $\mathbb{G}_1, \mathbb{G}_2$ là 2 đường xong elliptic với pairing $e: \mathbb{G}_1 \times \mathbb{G}_2 → \mathbb{G}_T$. Goị $p$ là order của $\mathbb{G}_1, \mathbb{G}_2$ và $G_1, G_2$ là generator của $\mathbb{G}_1, \mathbb{G}_2$
Thì:
$$
[x]_1 = xG_1 \in \mathbb{G}_1 \text{ and } [x]_2 = xG_2 \in \mathbb{G}_2
$$
Detail: https://vitalik.eth.limo/general/2017/01/14/exploring_ecp.html
### Trusted setup
Gỉa sử ta có một bí mật $s$, thì trusted setup sẽ là $[s^i]_1$ và $[s^i]_2$ với $i = 0, \dots, n-1$ được công khai cho cả prover và verifer. Trong challenge này là `g1_basis` và `g2_base` ($[s^i]_1$ và $[s]_2$ thay vì $[s^i]_2$)
```rust
pub fn new(degree: usize, secret: Fr) -> Self {
let mut cur = G1Affine::one();
let mut g1_basis = Vec::with_capacity(degree);
for _ in 0..=degree {
g1_basis.push(cur);
cur = cur.mul(secret).into_affine();
}
let g2_base = G2Affine::one().mul(secret).into_affine();
Self { g1_basis, g2_base }
}
```
Tiếp đến ta cần một đa thức bậc $n$ thuộc $\mathbb{F}_p$ .
```rust
pub fn new(coefficients: Vec<Fr>) -> Self {
Polynomial { coefficients }
}
pub fn rand(degree: usize) -> Self {
let mut rng = OsRng::new().unwrap();
let coefficients = std::iter::from_fn(|| Some(rng.gen::<Fr>()))
.take(degree)
.collect();
Polynomial { coefficients }
}
```
Nếu đa thức có dạng $p(X) = \sum_{i=0}^np_i(X^i)$, thì prover có thể tính $[p(s)]_1$ như sau:
$$
[p(s)]_1 = [\sum_{i=0}^n p_is^i]_1 = \sum_{i=0}^np_i[s^i]_1
$$
$[p(s)]_1 = p(s)G_1$
Nhưng điểm khác biệt là đa thức trong challenge bị biến đổi sau khi khởi tạo:
```rust
let setup: Setup = serde_json::from_reader(f).expect("error deserializing setup");
let mut poly = Polynomial::rand(DEGREE);
let mut f = File::open(flag_path).unwrap();
let mut flag = [0u8; 32];
f.read_exact(&mut flag).expect("error reading flag file");
let flag = U256::from_big_endian(&flag);
let mut offset = Fr::from_str(&flag.to_string()).unwrap();
let alpha = Fr::from_str(ALPHA).unwrap();
offset.sub_assign(&poly.evaluate(alpha));
// offset = flag - poly(alpha)
poly.add_scalar(offset);
// poly(x) = poly(x) + offset = poly(x) + flag - poly(alpha)
```
$$
f(x) = f(x) + flag - f(\alpha)
$$
$→ f(\alpha) = flag$
### Commitment
Lúc này $C = [p(s)]_1$ được gọi là commitment của đa thức $p(X)$
```rust
pub fn commit(&self, setup: &Setup) -> G1Affine {
let mut res = <G1Affine as GenericCurveAffine>::Projective::zero();
for (coeff, b) in self.coefficients.iter().zip(setup.g1_basis.iter()) {
let term = b.mul(*coeff);
res.add_assign(&term);
}
res.into_affine()
}
```
### Proof
Để chứng minh $p(z) = y$, ta qui ước $\pi = [q(s)]_1$
Verifier sẽ xác minh bằng chứng thông qua phương trình sau:
$$
e(\pi, [s-z]_2) = e(C-[y]_1, H)
$$
```rust
let com = poly.commit(&setup);
let f = File::create(output_path).unwrap();
let mut values = Vec::with_capacity(NUM_POINTS);
for i in 0..NUM_POINTS {
let z = Fr::from_str(&i.to_string()).unwrap();
let (mut y, mut proof) = poly.prove(&setup, z);
let mut rng = OsRng::new().unwrap();
if rng.gen_weighted_bool(PARANOMIAL_RATE) {
println!("paranormial activity occured");
y = rng.gen::<Fr>();
proof = G1Affine::one().mul(rng.gen::<Fr>()).into_affine();
}
values.push((y, proof));
}
```
điểm cần chú ý:
```rust
const PARANOMIAL_RATE: u32 = 3;
...
if rng.gen_weighted_bool(PARANOMIAL_RATE) {
println!("paranormial activity occured");
y = rng.gen::<Fr>();
proof = G1Affine::one().mul(rng.gen::<Fr>()).into_affine();
}
```
Với xác xuất $1/3$ giá trị của $y$ sẽ bị set thành ngẫu nhiên và $proof$ cũng bị thay đổi theo và hiển nhiên những giá trị này không có tác dụng để ta khai thác.
```rust
serde_json::to_writer(f, &(com, values)).expect("serialization failed");
```
Cuối cùng ta nhận được `com` và `values`, tương ứng với commitment của $f(x) = C = [f(s)]_1$ và tập hợp các giá trị của đa thức tại các điểm kèm theo $proof - \pi$ và các giá trị random gây nhiễu với xác xuất $1/3$
## Solution
Như vậy, ta chỉ cần sử dụng tính chất $pairing$ để kiểm tra các điểm thỏa mãn:
$$
e(\pi, [s-z]_2) = e(C-[y]_1, H)
$$
```rust
fn verify(comm: &G1Affine, y: &Fr, proof: &G1Affine, setup: &Setup, z: Fr) -> bool {
let ht = setup.g2_base;
let hz = G2Affine::one().mul(z).into_affine();
// LHS = e(pi, Ht - Hi)
let mut lhs = proof.pairing_with(&ht);
let pi_hz = proof.pairing_with(&hz).inverse().unwrap();
lhs.mul_assign(&pi_hz);
// RHS = e(C - Gy, H)
let h = G2Affine::one();
let gy = G1Affine::one().mul(*y).into_affine();
let mut rhs = comm.pairing_with(&h);
let gy_h = gy.pairing_with(&h).inverse().unwrap();
rhs.mul_assign(&gy_h);
lhs.eq(&rhs)
}
...
let valid_points: Vec<(usize, &(Fr, G1Affine))> = values
.iter()
.enumerate()
.progress()
.filter(|(z, (y, proof))| {
let z = Fr::from_str(&z.to_string()).unwrap();
verify(&comm, y, proof, &setup, z)
})
.collect();
```
Sau đó dùng **Lagrange interpolation** để recover đa thức $f(x)$
```rust
fn lagrange_interpolation(points: Vec<(usize, &Fr)>, eval: Fr) -> Fr {
let mut res = Fr::zero();
let n = points.len();
// Precompute x_i values as Fr elements to avoid repeated conversion
let x_values: Vec<Fr> = points
.iter()
.map(|(x_i, _)| Fr::from_str(&x_i.to_string()).unwrap())
.collect();
for i in 0..n {
let (_, y_i) = points[i];
let mut prod_res = Fr::one();
for j in 0..n {
if i != j {
// alpha - x_j
let mut numerator = eval;
let x_j = x_values[j];
numerator.sub_assign(&x_j);
// x_i - x_j and its inverse
let mut denominator = x_values[i];
denominator.sub_assign(&x_j);
let denominator_inv = denominator.inverse().unwrap(); // Inverse of x_i - x_j
// Multiply result with the fraction (eval - x_j) / (x_i - x_j)
numerator.mul_assign(&denominator_inv);
prod_res.mul_assign(&numerator);
}
}
// Multiply by y_i and accumulate the result
prod_res.mul_assign(y_i);
res.add_assign(&prod_res);
}
res
}
```
→ flag: `PCTF{k4t3_d3t3cts_paran0rm1als}`
# MMORPG
...
Sign in with Wallet
Connect another wallet