# CIS ACTVN 2024 - Crypto

# **Guessme**

from secp256k1 import *
import secrets
from hashlib import sha256
from flag import FLAG

import json

def gen_publickey(a, gen_proof=False):  # generate public key with a Schnorr proof
    A = multiply(G, a)
    if gen_proof:
        k = secrets.randbelow(N)
        R = multiply(G, k)
        
        e = int(sha256((str(P) + str(Gx) + str(Gy) +
                str(A[0]) + str(A[1]) + str(R[0]) + str(R[1])).encode()).hexdigest(), 16)
        
        z = (e*a + k) % N
        
        assert multiply(G, z) == add(multiply(A, e), R)
        return A, (R, z)
    return A

def verify_publickey(A, proof):
    R, z = proof
    
    e = int(sha256((str(P) + str(Gx) + str(Gy) +
            str(A[0]) + str(A[1]) + str(R[0]) + str(R[1])).encode()).hexdigest(), 16)
   
    return multiply(G, z) == add(multiply(A, e), R)

def round(b):
    print("Give me your public key and its Schnorr proof.")
    user_input = input()
    user_input = json.loads(user_input)
    
    A = user_input["publickey"]
    proof = user_input["proof"]
    
    assert verify_publickey(A, proof)
    
    bit = secrets.randbits(1)
    if bit:
        B = add(multiply(G, b), A)
        
    else:
        B = multiply(G, b)
        
    print(f"B = {B}")
    print("Guess my bit.")
    
    user_input = input()
    user_input = json.loads(user_input)
    
    guess = user_input["bit"]
    
    if guess == bit:
        return True
    else:
        return False

if __name__ == "__main__":
    for i in range(1, 129):
        try:
            print(f"Round [{i}/128]")
            res = round(secrets.randbelow(N))
            
            if not res:
                break
        except:
            break
        
    if i == 128:
        print(FLAG)

Challenge có tổng cộng 128 vòng, mỗi vòng có 2 lần kiểm tra:

**Lần 1:**

def verify_publickey(A, proof):
    R, z = proof
    
    e = int(sha256((str(P) + str(Gx) + str(Gy) +
            str(A[0]) + str(A[1]) + str(R[0]) + str(R[1])).encode()).hexdigest(), 16)
   
    return multiply(G, z) == add(multiply(A, e), R)
...
assert verify_publickey(A, proof)

**Lần 2:**

    bit = secrets.randbits(1)
    if bit:
        B = add(multiply(G, b), A)
        
    else:
        B = multiply(G, b)
        
    print(f"B = {B}")
    print("Guess my bit.")
    
    user_input = input()
    user_input = json.loads(user_input)
    
    guess = user_input["bit"]
    
    if guess == bit:
        return True
    else:
        return False

Ta thấy chương trình không kiểm tra điểm ra nhập có thuộc đường cong $secp256k1$ hay không, nên nếu ta gửi một điểm $A$ không thuộc $secp256k1$ thì có thể vượt qua Lần 2 dễ dàng bằng cách kiểm tra xem điểm $B$ được trả về có thuộc đường còng $secp256k1$ hay không, nếu có thì `bit = 0` - nếu không thì `bit = 1`

Để vượt qua Lần 1, ta chỉ cần chọn điểm $A = (0, 1)$ (không thuộc $secp256k1$) và tìm điểm $R = (0, k)$ sao cho thỏa `multiply(G, z) == add(multiply(A, e), R)` → $k = 2$

from secp256k1 import *
import secrets
from hashlib import sha256
import json
from pwn import *

P = 2**256 - 2**32 - 977
N = 115792089237316195423570985008687907852837564279074904382605163141518161494337
A = 0
B = 7
Gx = 55066263022277343669578718895168534326250603453777594175500187360389116729240
Gy = 32670510020758816978083085130507043184471273380659243275938904335757337482424
G = cast("PlainPoint2D", (Gx, Gy))
conn = remote('103.173.227.108', 10001)

z = N
Ax = 0
Ay = 1
Rx = 0
Ry = 2

R = cast("PlainPoint2D", (Rx, Ry))
A = cast("PlainPoint2D", (Ax, Ay, 1)) 

e = int(sha256((str(P) + str(Gx) + str(Gy) +
        str(A[0]) + str(A[1]) + str(R[0]) + str(R[1])).encode()).hexdigest(), 16)
z = N

for i in range(128):
    conn.recvline()
    conn.recvline()
    
    to_send = json.dumps({"publickey": A, "proof": [R, z]})
    conn.sendline(to_send.encode())
    conn.recvuntil(b'B = ')
    
    B = eval(conn.recvline().strip().decode())

    bit = 1
    Bx, By = B
        
    if By**2 % P == (Bx**3 + + 7) % P:
        bit = 0
    
    conn.recvline()
    ts = json.dumps({"bit" : bit})
    conn.sendline(ts)
        

conn.interactive()
CIS2024{n0_n33d_t0_gu3ss_1F_y0u_h4v3_1nv4L1D_Curv3_4tt4ck}

# **Chamomile Chameleon 1**

source:

from os import urandom
from hashlib import sha256
import string
import json
# from flag import FLAG
FLAG = b'hello'
num_layers = 11

class Server:
    def __init__(self) -> None:
        
        self.N = 2**num_layers
        self.tree = []
        self.users = []
        
        self.k = urandom(192)
        self.p = 0xffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca237327ffffffffffffffff
        self.q = (self.p - 1) // 2
        self.g = 0x2
        self.x = int.from_bytes(self.k, "big")
        
        self.y = pow(self.g, self.x, self.p)
        self.buile_merkle_tree()
        self.root = self.get_root_hash()

    def keyed_random(self, identifier: bytes, index: int) -> int: # -> not random
        
        return int.from_bytes(sha256(identifier + self.k + str(index).encode()).digest(), "big")

    def chameleon_hash(self, m: int, r: int) -> bytes:
        
        # g^m * y^r mod p
        return (pow(self.g, m, self.p) * pow(self.y, r, self.p) % self.p).to_bytes(192, "big") 

    def chameleon_extract(self, m1: int, r1: int, m2: int) -> int:
        
        # r2 = (x * r1 + m1 - m2) * x^-1 mod q
        r2 = (self.x * r1 + m1 - m2) * pow(self.x, -1, self.q) % self.q
        return r2

    def get_leaf(self, index: int) -> bytes:
        
        # (H(m + k + index ), H(r + k + index)) -> (m, r)
        # g^m * y^r mod p
        
        return self.chameleon_hash(self.keyed_random(b"m", index), self.keyed_random(b"r", index))

    def buile_merkle_tree(self) -> None:
        
        # create N leaf nodes
        curr_layer = [self.get_leaf(i) for i in range(self.N)]
        self.tree.append(curr_layer)
        
        while len(curr_layer) != 1:
            
            curr_layer = [sha256(self.tree[-1][i]+self.tree[-1][i+1]).digest()
                          for i in range(0, len(self.tree[-1]), 2)]
            
            self.tree.append(curr_layer)

    def get_root_hash(self) -> str:
        return self.tree[-1][0].hex()

    def add_user(self, username: str) -> str:
        
        if not all(char in string.printable for char in username):
            return "Invalid username."
        
        if username in self.users:
            return "Username already exists."
        
        if "Chamomile" in username:
            return "No Chamomile no..."
        
        else:
            
            index = len(self.users) % self.N
            self.users.append(username)
            
            
            r = self.chameleon_extract(self.keyed_random(b"m", index), self.keyed_random(
                b"r", index), int.from_bytes(sha256(username.encode()).digest(), "big"))
            
            assert self.chameleon_hash(int.from_bytes(
                sha256(username.encode()).digest(), "big"), r) == self.get_leaf(index)
            
            
            proof = {"username": username, "r": hex(r), "index": index}
            path = []
            
            for layer in self.tree[:-1]:
                
                is_right_node = index % 2
                sibling_index = index - 1 if is_right_node else index + 1
                
                path.append(layer[sibling_index].hex())
                index //= 2
                
            proof["path"] = path
            
            return json.dumps(proof)

    def verify_user(self, proof: str) -> str:
        
        proof = json.loads(proof)
        username = proof["username"]
        index = proof["index"]
        
        assert 0 <= index < self.N
        
        
        tmp = self.chameleon_hash(int.from_bytes(
            sha256(username.encode()).digest(), "big"), int(proof["r"], 16))
        
        for level in range(num_layers):
            
            is_right_node = index % 2
            
            if is_right_node:
                tmp = sha256(bytes.fromhex(
                    proof["path"][level]) + tmp).digest()
            else:
                tmp = sha256(
                    tmp + bytes.fromhex(proof["path"][level])).digest()
                
            index //= 2
            
        if tmp.hex() == self.root:
            if username == "Chamomile":
                return FLAG
            
            return f"Welcome back, {username}."
        else:
            return "Invalid user."

def main():
    print("Wait for the server to initialize...")
    s = Server()
    print(f"Public committed root: {s.root}")
    
    print(f"Chameleon public key: {hex(s.y)}")
    
    while True:
        try:
            user_input = input()
            user_input = json.loads(user_input)
            option = user_input["option"]
            
            if option == 1:
                msg = s.add_user(user_input["username"])
                
            elif option == 2:
                proof = input()
                msg = s.verify_user(proof)
                
            else:
                print("Invalid option, goodbye.")
                return
            print(msg)
        except:
            return

if __name__ == "__main__":
    main()

Để lấy được flag ta phải tạo proof tương ứng với giá trị của username là `Chamomile`

**Điểm cần chú ý:**

`self.buile_merkle_tree()`: Ta thấy cây merkle với N lá được tạo ra ngay từ đầu và không hề có sự thay đổi diễn ra → với bất kì giá trị của username nào được thêm thì giá trị của các lá vẫn sẽ không thay đổi. Như vậy việc khai thác thông qua thay đổi phần tử trong cây merkle là không hợp lý.

> hint: This server can store unlimited users, but the tree can only hold N entries. Where is the leaf for the (N+1)-th user ?
>

Thông qua hint được cung cấp, trước mắt ta cần kiểm tra phương thức khởi tạo user của challenge

    index = len(self.users) % self.N
    self.users.append(username)
  
  
    r = self.chameleon_extract(self.keyed_random(b"m", index), self.keyed_random(
        b"r", index), int.from_bytes(sha256(username.encode()).digest(), "big"))
  
    assert self.chameleon_hash(int.from_bytes(
        sha256(username.encode()).digest(), "big"), r) == self.get_leaf(index)
  
  
    proof = {"username": username, "r": hex(r), "index": index}
    path = []
  
    for layer in self.tree[:-1]:
      
        is_right_node = index % 2
        sibling_index = index - 1 if is_right_node else index + 1
      
        path.append(layer[sibling_index].hex())
        index //= 2
      
    proof["path"] = path
  
return json.dumps(proof)

Có thể hiểu đơn giản như sau, server sẽ cung cấp cho ta một giá trị $r_2$ sao cho từ $r_2$, username, index và $r_2$ có thể tính lại giá trị đại nút lá mà `username` đại diện trong cây merkle:

    assert self.chameleon_hash(int.from_bytes(
        sha256(username.encode()).digest(), "big"), r) == self.get_leaf(index)

Và $r_2$ mà ta được sever cung cấp được khởi tạo như sau:

$$
r_2 = (x r_1 + m_1 - m_2) x^{-1} \mod q
$$

Tiếp đến ta sẽ liên hệ với hint đã được author cung cấp, giả sử ta gọi hàm `add_user` lần thứ $N+1$ thì index của user sẽ trở về $0$ (`index = len(self.users) % self.N`). Lúc này ta sẽ được 2 phương trình như sau:

$$
r_2 = (x r_1 + m_1 - m_2) x^{-1} \mod q
$$

$$
r_2' = (x r_1 + m_1 - m_2') x^{-1} \mod q
$$

Như vậy, để tính lại $x$ ta chỉ cần trừ 2 phương trình cho nhau:

$$
r_2 - r_2' = x^{-1} (m_2' - m_2) \mod q
$$

$$
x = (m_2' - m_2) (r_2 - r_2')^{-1} \mod q
$$

Khi có được $x$ ta dễ dàng tính $k$ và khởi tạo một giá trị $r$ mới sao cho phù hợp với username là `Chamomile`

from pwn import *
import json
from tqdm import tqdm
from hashlib import sha256

num_layers = 11
N = 2**num_layers
p = 0xffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca237327ffffffffffffffff
q = (p - 1) // 2
g = 0x2

# conn = process(['python3', 'chameleon.py'])
conn = remote('103.173.227.108', 10002)

conn.recvuntil(b"root: ")
root = int(conn.recvline().strip().decode() , 16)

conn.recvuntil(b"Chameleon public key: ")

pk = int(conn.recvline().strip().decode()[2:], 16)
user1 = 'a'
user2 = 'b'

tosend = json.dumps({"option": 1, "username": user1})
conn.sendline(tosend.encode())

rs1 = json.loads(conn.recvline().strip().decode())
print(rs1["index"])

for i in tqdm(range(N - 1)):
    tosend = json.dumps({"option": 1, "username": str(i)})
    conn.sendline(tosend.encode())
    rs = json.loads(conn.recvline().strip().decode())
    
print(rs["index"])
tosend = json.dumps({"option": 1, "username": user2})
conn.sendline(tosend)

rs2 = json.loads(conn.recvline().strip().decode())
print(rs2["index"])

x_inv = eval(rs1["r"]) - eval(rs2["r"])

t1 = int.from_bytes(sha256(user1.encode()).digest(), "big")
t2 = int.from_bytes(sha256(user2.encode()).digest(), "big")

x = pow(x_inv*pow(t2-t1, -1, q), -1, q)
assert pk == pow(g, x, p)
k = x.to_bytes(192, "big")

m = int.from_bytes(sha256(b"m" + k + str(0).encode()).digest(), "big")
r = int.from_bytes(sha256(b"r" + k + str(0).encode()).digest(), "big")

username = b'Chamomile'
m2 = int.from_bytes(sha256(username).digest(), "big")

r2 = (x * r + m - m2) * pow(x, -1, q) % q
path = rs2["path"]

tosend = json.dumps({"option": 2})
conn.sendline(tosend.encode())

tosend = json.dumps({"username": username.decode(), "index": 0, "r":  hex(r2), "path": path})
conn.sendline(tosend.encode())

conn.interactive()
#CIS2024{Ch4m3l30n_h4sh_C0ll1s10n_m4y_r3v34l_Tr4pd00r}

# **Chamomile Chameleon 2**

source: thay đổi một chút so với **Chamomile Chameleon 1**

    def add_user(self, username: str) -> str:
        if not all(char in string.printable for char in username):
            return "Invalid username."
        if username in self.users:
            return "Username already exists."
        if "Chamomile" in username:
            return "No Chamomile no..."
        else:
            index = len(self.users) % self.N
            self.users.append(username)
            
            r = self.chameleon_extract(self.keyed_random(b"m", index), self.keyed_random(
                b"r", index), self.keyed_random(username.encode(), index))
            
            assert self.chameleon_hash(self.keyed_random(
                username.encode(), index), r) == self.get_leaf(index)
            
            proof = {"username": username, "r": hex(r), "index": index}
            path = []
            for layer in self.tree[:-1]:
                is_right_node = index % 2
                sibling_index = index - 1 if is_right_node else index + 1
                
                path.append(layer[sibling_index].hex())
                index //= 2
                
            proof["path"] = path
            return json.dumps(proof)

    def verify_user(self, proof: str) -> str:
        proof = json.loads(proof)
        username = proof["username"]
        index = proof["index"]
        assert 0 <= index < self.N
        tmp = self.chameleon_hash(self.keyed_random(
            username.encode(), index), int(proof["r"], 16))
        for level in range(num_layers):
            is_right_node = index % 2
            if is_right_node:
                tmp = sha256(bytes.fromhex(
                    proof["path"][level]) + tmp).digest()
            else:
                tmp = sha256(
                    tmp + bytes.fromhex(proof["path"][level])).digest()
                
            index //= 2
        if tmp.hex() == self.root:
            if username == "Chamomile":
                return FLAG
            return f"Welcome back, {username}."
        else:
            return "Invalid user."

Lúc này thay vì dùng `sha256(username.encode()).digest(), "big"), r)` như challenge trên thì sever dùng `keyed_random(username.encode(), index)` có cơ chế như sau:

    def keyed_random(self, identifier: bytes, index: int) -> int:
        return int.from_bytes(sha256(identifier + self.k + str(index).encode()).digest(), "big")

Như vậy ta không thể tính trước được $m_2$ vì không biết được $k$. Sau khi xem xét kĩ các đặc tính của tham số thì nhận thấy như sau các giá trị m được hash bằng sha256 → tối đa 32 bytes, trong khi độ lớn của giá trị $x$ nếu qui ra bytes là `192 bytes`.

Như vậy có thể thấy m nhỏ hơn rất nhiều so với $x$. Nếu ta lập được một lattice sử dụng mối quan hệ này thì khả năng cao là sẽ thu được một thứ gì đó có giá trị.

Tiếp đến, bằng phương pháp đã đề cập ở trên, ta thu được 3 phương trình sau:

$$
r_1 = (x r_0 + m_0 - m_1) x^{-1} \mod q
$$

$$
r_2 = (x r_0 + m_0 - m_2) x^{-1} \mod q
$$

$$
r_3 = (x r_0 + m_0 - m_3) x^{-1} \mod q
$$

Biến đổi một chút:

$$
r1 - r2 = x^{-1}(m_2 - m_1) \mod q
$$

$$
r2 - r3 = x^{-1}(m_3 - m_2) \mod q
$$

Như vậy nếu ta lập ma trận như sau:

$$
B =
\begin{pmatrix}
q & 0 \\
0 & q \\
r_1 - r_2 & r_2 - r_3
\end{pmatrix}
$$

Thì có khả năng ta sẽ nhận được vector có dạng:

$$
(\pm(m_1 - m_2), \pm(m_2 - m_3))
$$

Như vậy ta đã có thể tính lại $x$ và tìm được giá trị $r$ thỏa mãn cho username là `Chamomile`

from pwn import *
import json
from tqdm import tqdm
from hashlib import sha256

num_layers = 11

N = 2**num_layers
p = 0xffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca237327ffffffffffffffff
q = (p - 1) // 2
g = 0x2

while True:
    #conn = process(['python3', 'chameleon.py'])
    conn = remote('103.173.227.108', 10003)

    conn.recvuntil(b"root: ")
    root = int(conn.recvline().strip().decode() , 16)

    conn.recvuntil(b"Chameleon public key: ")

    pk = int(conn.recvline().strip().decode()[2:], 16)
    user1 = 'a'
    user2 = 'b' 
    user3 = 'c'

    tosend = json.dumps({"option": 1, "username": user1})
    conn.sendline(tosend.encode())

    rs1 = json.loads(conn.recvline().strip().decode())
    print(rs1["index"])

    for i in tqdm(range(N - 1)):
        tosend = json.dumps({"option": 1, "username": str(i)})
        conn.sendline(tosend.encode())
        rs = json.loads(conn.recvline().strip().decode())

    tosend = json.dumps({"option": 1, "username": user2})
    conn.sendline(tosend.encode())

    rs2 = json.loads(conn.recvline().strip().decode())
    print(rs2["index"])

    for i in tqdm(range(N - 1)):
        tosend = json.dumps({"option": 1, "username": str(i+N)})
        conn.sendline(tosend.encode())
        rs = json.loads(conn.recvline().strip().decode())

    tosend = json.dumps({"option": 1, "username": user3})
    conn.sendline(tosend.encode())

    rs3 = json.loads(conn.recvline().strip().decode())
    print(rs3["index"])

    r1 = eval(rs1["r"])
    r2 = eval(rs2["r"])
    r3 = eval(rs3["r"])

    from sage.all import Matrix

    m = [
        [q,     0    ],
        [0,     q    ],
        [r1-r2, r2-r3]
    ]
    m = Matrix(m)
    m = m.LLL()

    # +-(m1 - m2), +-(m2 - m3)
    a,b = list(m[1])
    print(m[1])

    t1 = a * pow(r2-r1, -1, q) % q
    t2 = a * pow(r1-r2, -1, q) % q

    x = 0
    if pow(g, t1, p) == pk:
        x = t1  
    if pow(g, t2, p) == pk:
        x = t2

    if x == 0:
        print("Failed")
        conn.close()
        continue
    print("x = ", x)

    k = x.to_bytes(192, "big")
    m = int.from_bytes(sha256(b"m" + k + str(0).encode()).digest(), "big")
    r = int.from_bytes(sha256(b"r" + k + str(0).encode()).digest(), "big")

    username = b'Chamomile'
    m2 = int.from_bytes(sha256(b'Chamomile' + k + str(0).encode()).digest(), "big")
    r4 = (x * r + m - m2) * pow(x, -1, q) % q
    path = rs3["path"]

    tosend = json.dumps({"option": 2})
    conn.sendline(tosend.encode())
    tosend = json.dumps({"username": username.decode(), "index": 0, "r":  hex(r4), "path": path})
    conn.sendline(tosend.encode())

    f = conn.recvline()
    if b'CIS' in f:
        print(f)
        conn.interactive()

    conn.close()
#CIS2024{Ch4m0m1l3_Ch4m3l3On_Ch4m0m1l3_Ch4m3l3On}