Ảnh minh họa: HTB Global Cyber Skills Benchmark 2026 — Crypto writeups

Once or nothing

Category : Crypto
Difficulty : Very easy

1,Tổng quan

Server code triển khai một hệ thống chữ kí số tưởng tự như lược đồ kí Lamport nhưng tái sử dụng cặp khóa

khóa riêng tư và khóa công khai :
- AuthKey (Khóa bí mật): Chứa một mảng gồm 256 cặp số ngẫu nhiên (s0, s1)
- AuthPub (Khóa công khai): Chứa 256 cặp giá trị băm tương ứng (hash(s0), hash(s1))

fn issue_credentials() -> (AuthKey, AuthPub) {
    let key_pairs = std::array::from_fn(|_| {
        (
            U256::from_be_slice(&get_random_bytes(N/8)),
            U256::from_be_slice(&get_random_bytes(N/8))
        )
    });
    let commitments = key_pairs.iter().map(|(s0, s1)| {
                                (hash_digest(&s0.to_be_bytes()), hash_digest(&s1.to_be_bytes()))
                            })
                            .collect::<Vec<_>>()
                            .try_into()
                            .unwrap();
    (AuthKey { key_pairs }, AuthPub { commitments })
}

Kí/ cấp token cho thông điệp:
- Pad thông điệp m thành 256 bit
- Duyệt qua từng bit:
  - Nếu bit tại vị trí i là 0: Chọn số bí mật s0 tại vị trí đó đưa vào token.
  - Nếu bit tại vị trí i là 1: Chọn số bí mật s1 tại vị trí đó đưa vào token.

fn issue_token(m: &[u8], auth_key: AuthKey) -> [U256; N] {
    let mut padded = [0u8; N/8];
    padded[(N/8 - m.len().min(N/8))..].copy_from_slice(&m[..m.len().min(N/8)]);
    let message_bits = U256::from_be_bytes((&padded).into());
    let hash_bits = to_bits(message_bits);
    assert!(hash_bits.len() == auth_key.key_pairs.len(), "ERROR: The number of hash bits and the size of the secret key must match.");
    std::array::from_fn(|i| {
        let (zero, one) = auth_key.key_pairs[i];
        if hash_bits[i] { one } else { zero }
    })
}

Xác thực token :
- Dựa vào các bit 0 hoặc 1 để nhặt ra các chuỗi băm tương ứng từ khóa công khai AuthPub.
  - Băm các số trong Token do người dùng gửi lên và so sánh với các chuỗi băm vừa nhặt ra. Nếu khớp toàn bộ,token đó là thật.

fn validate_token(m: &[u8], token: [U256; N], auth_pub: AuthPub) -> bool {
    let mut padded = [0u8; N/8];
    padded[(N/8 - m.len().min(N/8))..].copy_from_slice(&m[..m.len().min(N/8)]);
    let message_bits = U256::from_be_bytes((&padded).into());
    let hash_bits = to_bits(message_bits);
    assert!(hash_bits.len() == auth_pub.commitments.len(), "ERROR: The number of hash bits and the size of the public key must match.");
    let chosen_pk = std::array::from_fn(|i| {
        let (zero, one) = auth_pub.commitments[i];
        if hash_bits[i] { U256::from_be_slice(&one) } else { U256::from_be_slice(&zero) }
    });
    let hashed_token: [U256; N] = token.map(|s| { U256::from_be_bytes(hash_digest(&s.to_be_bytes()).into()) });
    chosen_pk == hashed_token
}

Đảm bảo xử lí thông điệp thành 256 bit trước khi đưa vào hàm kí

fn to_bits(n: U256) -> [bool; N] {
std::array::from_fn(|i| n.bit_vartime((N - 1 - i) as u32))
}

Thử thách chính là tìm được token hợp lên cho thông điệp đích “d9_netadmin”
- Server là 1 Oracle , ta có thể gửi thông điệp bất kì ( trừ thông điệp đích) và nhân đuọc token tương ứng

2,Cách tấn công

Lược đồ chữ kí này khá dễ dàng để bẻ gãy chỉ với 2 lần request oracle
- Lược đồ chữ kí Lamport tái sử dụng khóa => Lỗ hỏng lớn nhất
- Hàm kí và xác thực thực hiện riêng lẻ trên từng bit
- Việc hỏi oracle token cho thông điệp bất kì chỉ check xem thông điệp đó có chứa thông điệp đích (target msg) hay không => chia đôi thông điệp đích để hỏi
Quy trình tấn công :
- gửi thông điệp 1 : msg1 = b'd' + b'\xff' * 10 (11 bytes)
  - Ta lấy được token của padded_msg1 là [21 bytes \x00] + b'd' + [10 bytes \xff]
- gửi thông điệp 2 : msg2 = b'9_netadmin' (10 bytes)
  - Ta lấy được token của padded_msg1 là [22 bytes \x00] + b'9_netadmin'
- cắt ghép 176 phần tử đầu của token1 ( tức là phần [21 bytes \x00] + b'd') và 80 phần tử cuối của token2 ( tức là phần b'9_netadmin') $=>$ ta đươc valid token của padded_target_msg : [21 bytes \x00] + b'd9_netadmin'
$=>$ gửi server và lấy flag

Code khai thác

from pwn import *
import re
import binascii

context.log_level = 'error'

def get_token(io, hex_msg):
    io.sendlineafter(b'> ', b'1')
    io.sendlineafter(b'hex: ', hex_msg.encode())
    
    all_data = b''
    while b'Token issued:' not in all_data:
        all_data += io.recvline()
    
    token_line = all_data.decode()
    while ']' not in token_line:
        token_line += io.recvline().decode()
    
    hex_numbers = re.findall(r'Uint\(0x([0-9A-Fa-f]{64})\)', token_line)
    tokens = [int(h, 16) for h in hex_numbers]
            
    return tokens


def main():
    host = '154.57.164.82'
    port = 30548
    io = remote(host, port)
    
    #token of msg1 
    msg1 = b'd' + b'\xff' * 10
    hex_msg1 = binascii.hexlify(msg1).decode()
    token1 = get_token(io, hex_msg1)
    print(f"Done token for msg1")
    print(f"Token1: {token1[:10]}...") 
    
    #token of msg2
    msg2 = b'9_netadmin'
    hex_msg2 = binascii.hexlify(msg2).decode()
    token2 = get_token(io, hex_msg2)
    print(f"Done token for msg2")
    print(f"Token2: {token2[:10]}...")
    
    #combine token1 and token2 to find token of target msg 
    target = b'd9_netadmin'
    final_token = token1[:176] + token2[176:]
    print(f"Done token for target msg")
    print(f"Target token: {final_token[:10]}...")
    
    #send token of target msg and get flag 
    io.sendlineafter(b'> ', b'2')
    io.sendlineafter(b'validate: ', target)
    
    token_hex_str = ','.join(f"{t:064x}" for t in final_token)
    io.sendlineafter(b'hex): ', token_hex_str.encode())
    
    try:
        print(io.recvline(timeout=3).decode())
    except Exception as e:
        print(f"Error: {e}")
    io.close()

if __name__ == '__main__':
    main()

Kết quả chạy code

kết quả chạy code exploit

FLAG : HTB{d0n7_f0rg3t_t0_h4sh_b3f0r3_4nyth1ng_3ls3_7448fc110228c05199bcd26c433b1559}

Twice or nothing

Category : Crypto
Difficulty : Easy

1,Tổng quan

Tiếp nối bài Once or nothing, server vẫn triển khai hệ thống cấp token dựa trên lược đồ chữ kí Lamport. Ở bài trước, server kí trực tiếp các bit của thông điệp sau khi pad nên ta có thể chia thông điệp đích thành các phần, xin token rồi cắt ghép lại.
Sang bài này, server đã thêm bước băm thông điệp bằng SHA-256 trước khi kí. Cấu trúc khóa vẫn giữ nguyên:
- AuthKey (Khóa bí mật): Chứa 256 cặp số ngẫu nhiên (s0, s1).
- AuthPub (Khóa công khai): Chứa 256 cặp giá trị băm tương ứng (hash(s0), hash(s1)).
- Một cặp khóa được tạo lúc bắt đầu phiên và dùng lại cho các lần cấp token trong phiên đó.

cấp token cho thông điệp:

Băm thông điệp m bằng SHA-256 để thu được 256 bit.
Duyệt từng bit từ trái sang phải: bit tại vị trí i bằng 0 thì lấy s0 ở vị trí đó, bằng 1 thì lấy s1.

fn issue_token(m: &[u8], auth_key: AuthKey) -> [U256; N] {
    let message_hash = U256::from_be_bytes(hash_digest(m).into());
    let hash_bits = to_bits(message_hash);
    assert!(hash_bits.len() == auth_key.key_pairs.len(), "ERROR: The number of hash bits and the size of the secret key must match.");
    std::array::from_fn(|i| {
        let (zero, one) = auth_key.key_pairs[i];
        if hash_bits[i] { one } else { zero }
    })
}

Xác thực token:

Server cũng băm thông điệp bằng SHA-256, rồi dựa vào từng bit để chọn giá trị băm tương ứng trong AuthPub.
Băm từng phần tử của token và so sánh với các giá trị đã chọn. Khớp đủ 256 vị trí thì token hợp lệ.

fn validate_token(m: &[u8], token: [U256; N], auth_pub: AuthPub) -> bool {
    let message_hash = U256::from_be_bytes(hash_digest(m).into());
    let hash_bits = to_bits(message_hash);
    assert!(hash_bits.len() == auth_pub.commitments.len(), "ERROR: The number of hash bits and the size of the public key must match.");
    let chosen_pk = std::array::from_fn(|i| {
        let (zero, one) = auth_pub.commitments[i];
        if hash_bits[i] { U256::from_be_slice(&one) } else { U256::from_be_slice(&zero) }
    });
    let hashed_token: [U256; N] = token.map(|s| { U256::from_be_bytes(hash_digest(&s.to_be_bytes()).into()) });
    chosen_pk == hashed_token
}

Ngoài việc thêm SHA-256, server còn giới hạn số lần cấp token:
```
const BURN_LIMIT: u8 = 5;
```
```
if issue_count > BURN_LIMIT {
    println!("[BURNOUT] Maximum token issues reached. Key material exhausted.");
    break;
}
```
- issue_count ban đầu bằng 0 và chỉ tăng sau khi cấp token thành công.
- Điều kiện là > 5, nên khi issue_count = 5 ta vẫn xin được thêm một token => tổng cộng 6 token.
- Sau 6 lần cấp token, ta vẫn chọn được chức năng xác thực. Server chỉ kiểm tra giới hạn khi chọn chức năng cấp token tiếp.
Mục tiêu vẫn là tạo token hợp lệ cho d9_netadmin. Oracle từ chối kí mọi thông điệp có chứa chuỗi này.

2,Cách tấn công

Việc thêm SHA-256 khiến cách chia thông điệp ở bài trước không còn dùng trực tiếp được: các phần của thông điệp không tương ứng với các phần của hash.
Tuy nhiên, lược đồ vẫn tái sử dụng khóa và kí riêng lẻ trên từng bit => ta vẫn có thể ghép các phần tử token, miễn là chọn đúng bit hash tại đúng vị trí.
Gọi h_target = SHA256(b'd9_netadmin'). Khi xin token cho thông điệp m_j, tại vị trí i ta nhận được:
$token_j[i] = s_{i,\,SHA256(m_j)[i]}$
- Nếu SHA256(m_j)[i] == h_target[i], phần tử token_j[i] chính là số bí mật cần dùng cho token đích tại vị trí i.
- Ta không cần biết cả s0 và s1 tại mọi vị trí. Chỉ cần lấy được nhánh mà hash đích yêu cầu.
- Các phần tử được ghép phải giữ đúng vị trí i, vì mỗi vị trí có một cặp số bí mật riêng.
Vậy bài toán trở thành tìm 6 thông điệp sao cho tại mỗi vị trí trong 256 bit, có ít nhất một thông điệp có bit hash trùng với hash đích:
$\forall i\in\{0,\ldots,255\},\quad \exists j\in\{1,\ldots,6\}: SHA256(m_j)[i] = h_{target}[i]$
- SHA-256 tính được ở local nên ta có thể thử nhiều bộ thông điệp trước khi hỏi oracle, không tốn lượt cấp token.
- Với các hash xem như ngẫu nhiên, một vị trí có xác suất bị thiếu là $(1/2)^6 = 1/64$ . Một bộ 6 thông điệp ngẫu nhiên trung bình còn thiếu $256/64 = 4$ vị trí, nên cần kiểm tra độ phủ trước khi gửi.
Quy trình tấn công:
- Tính 256 bit của hash đích theo thứ tự từ bit cao nhất xuống bit thấp nhất, giống hàm to_bits trong server.
- Sinh 1000 thông điệp ứng viên và tính hash của chúng.
- Thử chọn ngẫu nhiên 6 ứng viên, kiểm tra xem đã phủ đủ 256 vị trí chưa. Nếu sau 10000 lần vẫn chưa tìm được, code thử chọn tham lam: mỗi lượt lấy ứng viên phủ thêm nhiều vị trí còn thiếu nhất.
- Chỉ khi đã tìm được bộ phủ đủ, kết nối server và xin 6 token trong cùng một phiên để chúng dùng chung khóa.
- Tại mỗi vị trí i, chọn một token có bit hash tương ứng trùng với h_target[i], rồi lấy phần tử thứ i của token đó:
```
final_token = []
for i in range(N):
    for j in range(NUM_TOKENS):
        if selected[j][1][i] == target_bits[i]:
            final_token.append(tokens[j][i])
            break
```
- Ghép đủ 256 phần tử, gửi thông điệp d9_netadmin cùng token vừa tạo để xác thực => lấy flag.
Như vậy, ý tưởng cắt ghép token của Once or nothing vẫn dùng được. Điểm khác là lần này ta phải tìm các thông điệp có bit hash phù hợp, thay vì chủ động chọn từng phần của thông điệp ban đầu.

Code khai thác

from pwn import *
from hashlib import sha256
import random
import re
import binascii

context.log_level = 'error'

HOST = 'localhost'  
PORT = 1337       

N = 256
TARGET = b'd9_netadmin'
NUM_TOKENS = 6


def hash_bits(msg):
    h = sha256(msg).digest()
    value = int.from_bytes(h, 'big')
    return [(value >> (255 - i)) & 1 for i in range(N)]


def find_messages():
    target_bits = hash_bits(TARGET)

    #generate candidate messages
    candidates = []
    for i in range(1000):
        msg = f'candidate_{i}_{random.getrandbits(128):032x}'.encode()
        if TARGET in msg:
            continue
        candidates.append((msg, hash_bits(msg)))

    #find 6 messages covering all bits of target hash
    for _ in range(10000):
        selected = random.sample(candidates, NUM_TOKENS)
        covered = [False] * N

        for _, bits in selected:
            for i in range(N):
                if bits[i] == target_bits[i]:
                    covered[i] = True

        if all(covered):
            return selected

    #greedy fallback if random search fails
    selected = []
    covered = [False] * N
    remaining = candidates[:]

    for _ in range(NUM_TOKENS):
        best = None
        best_gain = -1

        for candidate in remaining:
            msg, bits = candidate
            gain = sum(not covered[i] and bits[i] == target_bits[i] for i in range(N))
            if gain > best_gain:
                best_gain = gain
                best = candidate

        if best is None:
            break

        selected.append(best)
        remaining.remove(best)
        _, bits = best
        for i in range(N):
            if bits[i] == target_bits[i]:
                covered[i] = True

    if all(covered):
        return selected

    raise RuntimeError('Could not find 6 suitable messages')


def parse_token(line):
    line = line.decode(errors='replace')
    m = re.search(r'Token issued:\s*\[(.*)\]', line)
    if not m:
        raise ValueError(f'Could not parse token:\n{line}')

    parts = [x.strip() for x in m.group(1).split(',')]
    if len(parts) != N:
        raise ValueError(f'Expected 256 token elements, got {len(parts)}')

    tokens = []
    for x in parts:
        m = re.fullmatch(r'Uint\(0x([0-9A-Fa-f]+)\)', x)
        if not m:
            raise ValueError(f'Unexpected token element: {x}')
        tokens.append(int(m.group(1), 16))

    return tokens


def get_token(io, hex_msg):
    io.sendlineafter(b'> ', b'1')
    io.sendlineafter(b'Enter credential payload in hex: ', hex_msg.encode())
    token = parse_token(io.recvline())
    assert len(token) == N
    return token


def main():
    #find messages for token requests
    target_bits = hash_bits(TARGET)
    selected = find_messages()
    print('Done finding messages')

    io = remote(HOST, PORT)

    #token of each message
    tokens = []
    for i, (msg, _) in enumerate(selected):
        hex_msg = binascii.hexlify(msg).decode()
        token = get_token(io, hex_msg)
        tokens.append(token)
        print(f'Done token for msg{i + 1}')
        print(f'Token{i + 1}: {token[:10]}...')

    #combine tokens to find token of target msg
    final_token = []
    for i in range(N):
        target_bit = target_bits[i]
        chosen = None

        for token_index in range(NUM_TOKENS):
            msg, bits = selected[token_index]
            if bits[i] == target_bit:
                chosen = tokens[token_index][i]
                break

        if chosen is None:
            raise RuntimeError(f'No suitable secret for bit position {i}')
        final_token.append(chosen)

    assert len(final_token) == N
    print('Done token for target msg')
    print(f'Target token: {final_token[:10]}...')

    #send token of target msg and get flag
    io.sendlineafter(b'> ', b'2')
    io.sendlineafter(b'Enter admin message to validate: ', TARGET)

    token_hex_str = ','.join(f'{t:064x}' for t in final_token)
    io.sendlineafter(b'Enter token segments (comma-separated hex): ', token_hex_str.encode())

    io.interactive()


if __name__ == '__main__':
    main()

Kết quả chạy code

kết quả chạy code exploit

Pow Pow

Category : Crypto
Difficulty : Medium

1,Tổng quan

Server triển khai một ledger, yêu cầu ta tìm nonce hợp lệ cho 100 block trong 30 giây.

Mỗi block chứa 3 dòng giao dịch ngẫu nhiên do server cung cấp.
Nonce phải có độ dài đúng 32 bytes.
Hash của block được tính từ hash block trước, dữ liệu giao dịch và nonce nối lại với nhau.
Block hợp lệ khi biểu diễn hash dưới dạng 256 bit có 50 bit đầu bằng 0.

def validate_block(self, blockdata, nonce):
    hash = self.ledger_hash(long_to_bytes(self.ledger[-1]) + blockdata + nonce)
    hash_bits = bin(hash)[2:]
    hash_bits = "0"*(256 - len(hash_bits)) + hash_bits
    if hash_bits[:self.POW_hardness] == self.POW_hardness*"0":
        self.ledger.append(hash)
        return True
    else:
        return False

Hàm ledger_hash được server tự định nghĩa:
```
def ledger_hash(self, data):
    hash = (self.a * bytes_to_long(data) + self.b) % self.n
    return hash
```
- a, b, n đều là số nguyên tố 256 bit, với a < n và b < n.
- Server in cả 3 tham số ngay khi kết nối.
- Nếu gọi số nguyên biểu diễn dữ liệu là x, ta có:
$H(x) = (ax+b)\bmod n$

Hash khởi đầu của ledger cũng tính được từ dữ liệu cố định:

genesis_block = sha256(b"Korvia command channel genesis").digest()
self.ledger = [self.ledger_hash(genesis_block)]

Sau 100 block hợp lệ, server trả về giá trị ledger_hash(FLAG) ở dạng hex:
```
elif len(korvia_ledger.ledger) > 100:
    print("[SUCCESS] Ledger breached. Flag payload: " + hex(korvia_ledger.ledger_hash(FLAG))[2:])
    break
```
- Ledger đã có một phần tử khởi đầu, nên thêm 100 block thì độ dài bằng 101 và thỏa điều kiện trên.

2,Cách tấn công

Điểm yếu nằm ở hàm hash tuyến tính. Ta biết toàn bộ a, b, n nên có thể giải phương trình để chọn nonce cho hash bằng 0 => chắc chắn thỏa 50 bit đầu bằng 0.
Gọi:
- prefix = long_to_bytes(current_hash) + block_data.
- P = bytes_to_long(prefix).
- r = bytes_to_long(nonce).
Vì nonce dài đúng 32 bytes = 256 bit, phép nối bytes tương ứng với:
$bytes\_to\_long(prefix\mathbin{\|}nonce) = P\cdot 2^{256}+r$
Thay vào hàm hash:
$H = a(P\cdot 2^{256}+r)+b\pmod n$
Đặt:
$C = (aP\cdot 2^{256}+b)\bmod n$
Để hash bằng 0, ta cần:
$ar+C\equiv 0\pmod n$
- n là số nguyên tố và $0<a<n$ => tồn tại nghịch đảo $a^{-1}\pmod n$ .
- Từ đó tính trực tiếp nonce:
$r = (-C\cdot a^{-1})\bmod n$
- Kết quả nằm trong khoảng $0\le r<n<2^{256}$ nên luôn biểu diễn được bằng đúng 32 bytes. Khi gửi hex, pad bên trái cho đủ 64 kí tự.
```
C = (a * (prefix_long << 256) + b) % n
target_nonce = (-C * a_inv) % n
nonce_hex = hex(target_nonce)[2:].rjust(64, '0')
```
Quy trình tạo 100 block:
- Đọc a, b, n, tính a_inv và hash khởi đầu từ chuỗi genesis.
- Đọc đúng 3 dòng giao dịch, giữ lại kí tự xuống dòng \n của từng dòng để dữ liệu giống server.
- Tính nonce theo công thức trên rồi gửi cho server.
- Sau block đầu tiên, hash vừa được thêm vào ledger là 0 => cập nhật current_hash = 0 cho block tiếp theo.
- Lặp lại đủ 100 lần. Mỗi block chỉ cần tính nonce bằng phép toán modulo.
- Lưu ý long_to_bytes(0) trả về b'\x00'. Vì vậy prefix của các block sau bắt đầu bằng một byte 0, đúng với cách nối dữ liệu trong server.
Khôi phục flag từ giá trị server trả về:
- Gọi F = bytes_to_long(FLAG) và y = ledger_hash(FLAG).
- Ta có $y\equiv aF+b\pmod n$ , suy ra:
$F\bmod n = (y-b)\cdot a^{-1}\bmod n$
```
flag_int = ((flag_hash_int - b) * a_inv) % n
flag = long_to_bytes(flag_int)
```
- Khi $F<n$ , giá trị này chính là toàn bộ flag. Flag local HTB{This_is_local_flag} dài 23 bytes nên thỏa điều kiện đó với n 256 bit.
- Nếu $F\ge n$ , công thức chỉ trả về phần dư của flag modulo n; muốn khôi phục đầy đủ cần thêm thông tin.
=> Tính nonce để vượt qua 100 block, rồi dùng cùng nghịch đảo modulo để lấy lại flag.

Code khai thác

Code theo sovle.py. Đổi HOST, PORT theo instance đang chạy.

from pwn import *
from Crypto.Util.number import bytes_to_long, long_to_bytes, inverse
import hashlib
import re

context.log_level = 'error'

HOST = 'localhost'  
PORT = 1337       


io = remote(HOST, PORT)

init_data = io.recvuntil(b"n =").decode()
a = int(re.search(r"a = (\d+)", init_data).group(1))
b = int(re.search(r"b = (\d+)", init_data).group(1))
n_line = io.recvline().decode().strip()
n = int(n_line)

print("a = ",a)
print("b = ",b)
print("n = ",n)

genesis_block = hashlib.sha256(b"Korvia command channel genesis").digest()
current_hash = (a * bytes_to_long(genesis_block) + b) % n



a_inv = inverse(a, n)

for i in range(100):
    io.recvuntil(b"Validate proxy transaction batch:\n")
    tx1 = io.recvline()
    tx2 = io.recvline()
    tx3 = io.recvline()
    block_data = tx1 + tx2 + tx3
    
    io.recvuntil(b"Enter block nonce in hex: ")
    
    prefix = long_to_bytes(current_hash) + block_data
    prefix_long = bytes_to_long(prefix)
    C = (a * (prefix_long << 256) + b) % n
    target_nonce = (-C * a_inv) % n
    
    nonce_hex = hex(target_nonce)[2:].rjust(64, '0')
    io.sendline(nonce_hex.encode())
    
    #recv flag after sent the last block hash 
    if i == 99:
        io.recvuntil(b'Flag payload: ')
        flag_hash_hex = io.recvline().decode() 
        flag_hash_int = int(flag_hash_hex, 16)
            
        flag_int = ((flag_hash_int - b) * a_inv) % n
        flag = long_to_bytes(flag_int)
        
        print(flag)
        break 
        
    #recv response for the block from 1 -> 99     
    result = io.recvline().decode().strip()
    if "[VALIDATED]" not in result:
        print(f"Failed at block {i+1}: {result}")
        break
        

    current_hash = 0

Kết quả chạy code

kết quả chạy code exploit

Isochronal scramble

Catefory: Crypto
Difficulty : Hard

1, Tổng quan về challenge

Hàm băm CGL

Server code mô phỏng cấu trúc hàm băm GCL dựa trên đồ thị đẳng cấu bậc 2 (2-isogeny graph) trên tập các đường cong siêu đặc dị (Supersingular Elliptic Curves).

p = 2**49 * 3**36 - 1
K = GF(p**2, "x", modulus=[1, 0, 1])
x = K.gen()


def deterministic_sqrt(x):
    return min(x.sqrt(all=True))


def select0(E0, b0):
    torsion_points = sorted(E0.torsion_polynomial(2).roots(multiplicities=False))
    if b0:
        return torsion_points[-1], torsion_points[1]
    else:
        return torsion_points[1], torsion_points[-1]


def select(lambda0, lambda1, b):
    if b:
        return max(lambda0, lambda1)
    else:
        return min(lambda0, lambda1)


def next_curve(A, alpha, b):
    xi = alpha**2
    zeta = 3 * xi + A
    eta = deterministic_sqrt(zeta)
    new_A = -(4 * A + 15 * xi)

    lambda0 = alpha + 2 * eta
    lambda1 = alpha - 2 * eta
    new_alpha = select(lambda0, lambda1, b)
    return new_A, new_alpha


def data_to_bits(data):
    bits = [int(b) for c in data.encode() for b in "{:08b}".format(c)]
    assert bits and all(b in (0, 1) for b in bits)
    return bits


def CGL_hash(E0, data):
    data = data_to_bits(data)
    n = len(data)

    A = E0.a4()
    alpha, _ = select0(E0, data[0])
    for i in range(n - 1):
        A, alpha = next_curve(A, alpha, data[i + 1])

    xi = alpha**2
    new_A = -(4 * A + 15 * xi)
    new_B = -alpha * (8 * A + 22 * xi)

    E = EllipticCurve(E0.base_field(), [new_A, new_B])
    j = str(E.j_invariant()).encode()
    return sha256(j).hexdigest()

Hàm băm dựa vào các bit của dữ liệu được băm để xác định đường đi trên đồ thị đẳng cấu để đi đến kết quả (curve đích)
- dùng bit để xác định điểm xoắn bậc 2 ( có dạng $(\alpha,0)$ ) nào được chọn để làm kernel đi đến đường cong siêu dị tiếp theo, và bước đến đường cong tiếp theo bằng hệ hệ thức Velu
Cấu trúc hàm băm
- Xác định 1 curve khởi đầu của đường đi là $E_0 (A_0, B_0)$
- Với bit đầu tiên ,sử dụng đa thức xoắn 2 (torsion_polynomial(2) : $x^2 + A_0x + B_0 =0$ ) trên $E_0$ để tìm các hạt nhân bậc 2. Hàm select0 dựa vào bit đầu tiên data[0] để chọn ra một điểm hạt nhân $\alpha_0$ (để đi đến curve $A_1$ ) một cách cố định theo quy ước.
- Với các bit sau ( $1 -> l-1$ $1 - > l - 1$ ): hàm next_curve sẽ lấy vào $A_{n-1}$ $A_{n - 1}$ , $\alpha_{n-1}$ $α_{n - 1}$ và bit thứ $n$ $n$ (kết hợp với hàm select) để tính ra $A_{n}$ $A_{n}$ và $\alpha_{n}$ $α_{n}$ . Sử dụng hệ thức Velu cho đẳng cấu bậc 2 (2-isogencyisogency)
  - $\eta = min(\sqrt{3 \alpha^2 + A_{n-1}})$
  - $\lambda_0 = \alpha_{n-1} + 2 \eta$
  - $\lambda_1 = \alpha_{n-1} - 2 \eta$
  - $A_n = -(4 A_{n-1} + 15 \alpha_{n-1}^2)$
  - $\alpha_n = select(\lambda_0, \lambda_1, bits[n])$
- Tính curve cuối cùng :
  - $A_l = -(4 A_l + 15 \alpha_l^2)$
  - $B_l = - \alpha_l (8 A_l + 22 \alpha_l^2)$
- bước cuối:
  - lấy j_invariant của hàm băm cuối : $j = 1728 \cdot \frac{4 A_l^3}{4 A_l^3 +27B_l^2}$
  - Băm j_variant bằng SHA256 để trả về kết quả hàm băm CGL

Nhiệm vụ của challenge

Ta cần tìm 1 curve khởi tạo $E_0$ và data credential thỏa mãn khi băm credential với curve khởi tạo là $E_0$ thì ta thu được chính credential ( băm như ko băm)

2, Chiến lược tấn công

2.1 Ý tưởng đầu tiên

$j variant$ $j v a r ian t$ được đi qua SHA256 trước khi trả về output => ta ko thể điều khiển được đầu ra từ đầu vào của hàm băm , vậy nên ta sẽ :
- Lấy giá trị $jvariant$ $j v a r ian t$ của 1 đường cong siêu dị , sau đó lấy $SHA256(jvariant)$ $S H A 256 (j v a r ian t)$ để làm đầu vào của hàm băm CGL
  - Với $p \equiv 3 (mod4)$ => ta chọn đường cong phổ biến là $y^2 = x^3 + x$
  - data đầu vào của hàm băm GCL chính là chuỗi hex kết quả của SHA256 => có 512 bit
- => Ta phải tìm đường cong khởi tạo $E_0$ $E_{0}$ sao cho đường đi từ $E_0$ $E_{0}$ qua đường đi xác định bởi các bit trên chuỗi data sẽ đi đến đường cong đích là $y^2 = x^3 + x$ $y^{2} = x^{3} + x$
  - Bài toán trở thành tìm đường đi lùi từ $E_{512} : y^2 = x^3 + x$ để tìm về đường cong $E_0$

2.2 Có thể đi ngược từ $E_{512}$ về $E_0$ không?

Ta đã có đường đi , vậy liệu với $E_{512}$ thì có xuất hiện 1 đường đi lùi dựa trên data để tìm về $E_0$ được ko

2.2.1 Điểm cuối trên đường cong $E_{512}$ về $E_{511}$

Để tìm $A_{511}$ và $\alpha_{511}$ từ đường cong $E_{512}$ ta lập hệ:

\begin{cases} A_{512} = - 4 A_{511} - 15 \alpha_{511}^2 \\ B_{512} = - \alpha_{511}(8 A_{511} + 22 \alpha_{511}^2) \end{cases}

=> 8 \alpha_{512}^3 - 2 A_{512} \alpha_{511} - B_{512} = 0

=> Ta được 2 nghiệm $\alpha_{511}$ ( trừ $\alpha_{511}$ = 0) , từ đó có 2 đường cong $E_{511}$ khi đi từ $E_{512}$ về 1 bước
=> Ta có thể thử bước lùi tiếp từ 2 đường cong $E_{511}$ này này (thử cả 2 nhánh )

2.2.2 Bước cuối tìm $E_0$

Giả sử ta có thể nối chuỗi đi ngược về đến tận điểm $E_0$ và ta tìm được $A_0$ và $\alpha_0$

Ta sẽ khôi phục $B_0$ như sau , từ phương trinh:

\alpha_0 ^2 + A_0 \alpha_0+ B_0 =0

=> B_0 = - \alpha_0^2 - A_0 \alpha_0

Nhưng ta ko chắc rằng $\alpha_0$ có thỏa mãn hàm select0 hay ko => ta cần phải check
=> rất có thể đường đi sẽ đứt khi đi được đến cuối

2.2.3 vấn đề thực sự nằm ở các node trung gian trên đường đi

Ý tưởng về tìm đường đi lùi từ một đường cong

Với phương trình tìm next curve mà challenge cho , ta có thể xây dựng phương trình để tính prev curve như sau :

\begin{cases} \alpha_{n} = \alpha_{n-1} \pm2 \cdot \min(\sqrt{3 \alpha^2 + A_{n-1}})\\ A_n = -(4 A_{n-1} + 15 \alpha_{n-1}^2) \end{cases}

=> \begin{cases} A_{n-1} = - \frac{(A_n + 15 \alpha_n^2)}{4}\\ \alpha_n - \alpha_{n-1} = 2 \cdot \min(\sqrt{3 \alpha^2 - \frac{(A_n + 15 \alpha_n^2)}{4}}) \end{cases}

=> (\alpha_n - \alpha_{n-1})^2 = 12 \alpha_{n-1}^2 - A_{n} - 15 \alpha_{n-1}^2

=> 4 \alpha_{n-1}^2 - 2 \alpha_n \alpha_{n-1} + (A_n + \alpha_n^2) = 0

giải phương trình bậc 2 ta sẽ thu được 2 nghiệm ẩn $\alpha_{n-1}$ là $\alpha_1$ và $\alpha_2$
Từ mỗi giá trị ta có được 1 giá trị hệ số A tương ứng là $A_1$ và $A_2$

=> Vậy liệu 2 nghiệm này có thỏa mãn chính là đường cong trước khi đi lùi $E_n$ lại ?

Ta thấy rằng ở trong code server , có 2 ràng buộc tác động đến việc chọn điểm xoắn bậc 2 để đi tới đường cong tiếp theo

def deterministic_sqrt(x):
return min(x.sqrt(all=True))

def select(lambda0, lambda1, b):
if b:
    return max(lambda0, lambda1)
else:
    return min(lambda0, lambda1)

=> Một nghiệm khi check bằng cách đi xuôi lại hàm next_curve có thể đúng hoặc ko (đi xuối theo công thức có đến $E_n$ ko) thể

Đánh giá về số đường đi lùi có thể của các đường cong trung gian

Với 2 nghiệm $\alpha_1$ và $\alpha_2$ và 2 giá trị $A_1$ và $A_2$ ta giải được , ta thay lại vào phương trình , ta được các biểu thức :

\begin{cases} (\alpha_{n} - \alpha_{1})^2 = 4(3\alpha_{1}^2 - A_{1}) \\ (\alpha_{n} - \alpha_{2})^2 = 4(3\alpha_{2}^2 - A_{2}) \end{cases}

=> \begin{cases} \alpha_{n} - \alpha_{1} = 2\sqrt{3\alpha_{1}^2 - A_{1}} \quad (1) \\ \alpha_{n} - \alpha_{1} = -2\sqrt{3\alpha_{1}^2 - A_{1}} \quad (2) \\ \alpha_{n} - \alpha_{2} = 2\sqrt{3\alpha_{2}^2 - A_{2}} \quad (3) \\ \alpha_{n} - \alpha_{2} = -2\sqrt{3\alpha_{2}^2 - A_{2}} \quad (4) \end{cases}

Từ hệ 4 biểu thức ở trên, ta chia thành 2 tập hợp :
- Tập 1 (Nhánh $\alpha_{1}$ ): Gồm biểu thức $(1)$ và $(2)$ .
- Tập 2 (Nhánh $\alpha_{2}$ ): Gồm biểu thức $(3)$ và $(4)$ .
Hàm deterministci_sqrt sẽ chọn ra mỗi nhánh 1 biểu thức bằng việc so sánh
- $\sqrt{3\alpha_{1}^2 - A_{1}}$ và $- \sqrt{3\alpha_{1}^2 - A_{1}}$ ở nhánh 1
- $\sqrt{3\alpha_{2}^2 - A_{2}}$ và $- \sqrt{3\alpha_{2}^2 - A_{2}}$ ở nhánh 2
Hàm select sẽ chọn ra mỗi nhánh 1 biểu thức bằng việc xác định bit và so sánh theo quy tắc
- $\alpha_1 + 2\sqrt{3\alpha_{1}^2 - A_{1}}$ và $\alpha_1- 2\sqrt{3\alpha_{1}^2 - A_{1}}$ ở nhánh 1
- $\alpha_1 + 2\sqrt{3\alpha_{2}^2 - A_{2}}$ và $\alpha_1 - 2\sqrt{3\alpha_{2}^2 - A_{2}}$ ở nhánh 2
Nghiệm nào trải qua được cả 2 bộ lọc sẽ tạo thành 1 prev curve hợp lệ của $E_n$
Vì các giá trị này còn phụ thuộc và $\alpha_n$ và $A_n$ => ta rất khó để định hướng được quy luật của việc so sánh
Nhưng nếu coi như xác suất 1 nghiệm vượt qua được mỗi bộ lọc là 50/50 , ta rút ra dc kết luận sau
- Xác suất để cả 2 nghiệm đều hợp lệ là $0,25$ ( ta có thể đâm 2 nhánh )
- Xác suất để cả 1 nghiệm đều hợp lệ là $0,5$ ( ta có thể đâm nhánh tiếp)
- Xác suất để cả 0 nghiệm đều hợp lệ là $0,25$ ( nhánh cụt)

=> Ta kết luận rằng không phải lúc nào nhánh cũng đâm về tận cuối được

2.3 Chiến lược backtrack để tìm đến $E_0$

Với các xác suất đi lùi được của 1 đường cong như đã nói ở trên , liệu ta có thể đi lùi tận 512 lần?

=> Tùy thuộc vào độ may mắn

Đánh giá với chiến lược backtracking

Với backtracking , ta sẽ cố đâm mọi nhánh đi lùi có thể đến khi đi được 512 bước để đến $E_0$
Giả sử từ điểm xuất phát , ta đâm được 2 nhánh , và tại mỗi nhánh sau đó ,mỗi điểm có thể đâm được 0 , 1 hoặc 2 nhánh tiếp
- Nếu ta xuất phát với 1 đường cong đích không may mắn , hoàn toàn có thể nhánh nào cũng sẽ cụt
- Nếu ta xuất phát với 1 đường cong đích may mắn hơn , tức cây tìm kiếm có thể đâm sâu hơn so với đích không may mắn
  - nếu cây tìm kiếm có thể đâm sâu thêm => vì đâm càng xấu , với xác suất đâm 2 là 0,25 , đâm tiếp là 0,5 thì càng sâu càng có nhiều nhánh , mà càng có nhiều nhánh thì xác suất có nhiều nhánh đâm dc sâu nữa lại càng cao => cây sẽ khó mà bị cụt hết đường hơn , tức là càng đâm được sâu càng khó chết
  - Ta hoàn toàn có thể đâm đến 512 tầng đối với trường hợp này

=> Ta có thể thử backtracking từ 1 đường cong đích, nếu may mắn ,ta có thể đâm tận 512 lần và lấy được $E_0$

Thử với đường cong $y^2 = x^3 + x$

Thử xuất phát đi lùi với đường cong đích , ta nhận ra đây là 1 đường cong không may mắn

Terminal

2.4 Trick cuối cùng : Bước tiến vài bước để lùi

Đường cong $y^2 = x^3 + x$ không thể đi về đích , vậy ta có thể tìm cách để đi đến các đương còng khác để lấy làm điểm đich để xuất phát lùi về
Code server đã cho ta sẵn cách để đến các đường cong siêu đặc dị khác từ 1 đường cong xuất phát
Ta sẽ bước ngẫu nhiên theo chiều xuôi một vài bước từ đường cong $y^2 = x^3 + x$ đến với các đường cong khác để thử backtrack về , nếu cây tìm kiếm bị cụt giữa đường , ta lại bước ngẫu nhiên đến một đường cong khác để thử lại , cho đến khi gặp được một đường cong may mắn có thể quay trở về $E_0$
Việc thử nhiều lần gần như sẽ có một đường cong đi được đến đích $E_0$

3, Code khai thác

from sage.all import *
from pwn import *
import hashlib
import random

p = 2**49 * 3**36 - 1
K = GF(p**2, "x", modulus=[1, 0, 1])
x = K.gen()

P_y = K['y']
y = P_y.gen()#old_alpha variable 

def deterministic_sqrt(val):
    return min(val.sqrt(all=True))

def select0(E0, b0):
    torsion_points = sorted(E0.torsion_polynomial(2).roots(multiplicities=False))
    if b0:
        return torsion_points[-1], torsion_points[1]
    else:
        return torsion_points[1], torsion_points[-1]

def select(lambda0, lambda1, b):
    if b:
        return max(lambda0, lambda1)
    else:
        return min(lambda0, lambda1)

def next_curve(A, alpha, b):
    xi = alpha**2
    zeta = 3 * xi + A
    eta = deterministic_sqrt(zeta)
    new_A = -(4 * A + 15 * xi)
    lambda0 = alpha + 2 * eta
    lambda1 = alpha - 2 * eta
    new_alpha = select(lambda0, lambda1, b)
    return new_A, new_alpha

def data_to_bits(data):
    bits = [int(b) for c in data.encode() for b in "{:08b}".format(c)]
    assert bits and all(b in (0, 1) for b in bits)
    return bits


def backtrack(A_curr, alpha_curr, bit_idx, bits):
    if bit_idx == 0:
        B0 = -alpha_curr**3 - A_curr * alpha_curr
        E0 = EllipticCurve(K, [A_curr, B0])
        
        alpha_test, _ = select0(E0, bits[0])
        if alpha_test == alpha_curr:
            return E0
        return None

    depth = 511 - bit_idx
    if depth % 50 == 0:
        log.info(f"Depth : {depth}/511...")

    b = bits[bit_idx]
    
    # PT bậc 2: 4*y^2 - 2*alpha_curr*y + (alpha_curr^2 + A_curr) = 0
    eq = 4*(y**2) - 2*alpha_curr*y + (alpha_curr**2 + A_curr)
    candidates = eq.roots(multiplicities=False)
    
    for alpha_old_cand in candidates:
        A_old_cand = (-A_curr - 15 * (alpha_old_cand**2)) / 4
        try:
            t_A, t_alpha = next_curve(A_old_cand, alpha_old_cand, b)
            if t_A == A_curr and t_alpha == alpha_curr:
                
                result = backtrack(A_old_cand, alpha_old_cand, bit_idx - 1, bits)
                
                if result is not None:
                    return result
                    
        except ValueError:
            continue
            
    return None



def solve():
    attempts = 0
    while True:
        attempts += 1
        print(f"\n[*] Lần thử thứ {attempts}: đang đi đến 1 đích ngẫu nhiên")
        
        # Tạo điểm đích ngẫu nhiên
        A = K(1)
        E = EllipticCurve(K, [A, 0])
        alpha, _ = select0(E, 0)
        
        for _ in range(30):
            b = random.choice([0, 1])
            A, alpha = next_curve(A, alpha, b)
           
        xi = alpha**2
        target_A = -(4 * A + 15 * xi)
        target_B = -alpha * (8 * A + 22 * xi)
        E_final = EllipticCurve(K, [target_A, target_B])

        
        # Tính credential và bits từ cái đích này
        j_inv = str(E_final.j_invariant()).encode()
        credential = hashlib.sha256(j_inv).hexdigest()
        bits = data_to_bits(credential)
        
        #Tính A511 , alpha511 
        eq_tail = 8*y**3 + 2*target_A*y - target_B
        # Bỏ [root[0] for root in...] đi
        roots_alpha_511 = eq_tail.roots(multiplicities=False)
        
        for alpha_511 in roots_alpha_511:
            A_511 = (-target_A - 15*alpha_511**2)/4
            
            E0 = backtrack(A_511, alpha_511, 511, bits)
            if E0 is not None:
                log.success(f"tìm thấy gốc E0 sau {attempts} lần thử.")
                return E0, credential


def main():
    E0, credential = solve()
    io = remote("localhost", 1337)

    def get_parts(val):
        coeffs = val.polynomial().list()
        part0 = int(coeffs[0]) if len(coeffs) > 0 else 0
        part1 = int(coeffs[1]) if len(coeffs) > 1 else 0
        return part0, part1

    a4_0, a4_1 = get_parts(E0.a4())
    a6_0, a6_1 = get_parts(E0.a6())
    
    io.sendlineafter(b"a4.0 > ", str(a4_0).encode())
    io.sendlineafter(b"a4.1 > ", str(a4_1).encode())
    io.sendlineafter(b"a6.0 > ", str(a6_0).encode())
    io.sendlineafter(b"a6.1 > ", str(a6_1).encode())
    
    io.sendlineafter(b"data > ", credential.encode())
    io.interactive()

if __name__ == "__main__":
    main()

4 , Kết quả

Tìm được $E_0$ và lấy flag sau 88 lần bước tiến ngẫũ nhiên

Có thể thấy rất nhiều lần chọn đường cong đích bị cắt hết nhánh sơm

Terminal

Flag : HTB{0n_y0ur_w4y_t0_b3c0m3_4_CGL_h4sh_cr4ck3r_5ab538d258caf3cc9094a6d26763df10}

Isochronal Fixed Point

Category: Crypto
Difficulty : Insane

1, Tổng quan về challenge

Thay đổi so với Isochronal Scramble

Challenge này sử dụng cùng hàm băm CGL và cùng tham số với challenge Isochronal Scramble (xem writeup trước để hiểu chi tiết về hàm băm CGL, đồ thị đẳng cấu bậc 2, và các hàm next_curve, select0, select, deterministic_sqrt).
Tuy nhiên, server có 2 thay đổi quan trọng:

Thay đổi 1: Input là raw bytes, không phải string

Ở Scramble, data_to_bits nhận string rồi .encode():

# Scramble
def data_to_bits(data):
    bits = [int(b) for c in data.encode() for b in "{:08b}".format(c)]

Ở Fixed Point, data_to_bits nhận raw bytes trực tiếp (input qua hex):

# Fixed Point  
def data_to_bits(data):
    bits = [int(b) for c in data for b in "{:08b}".format(c)]

Server nhận payload dưới dạng hex: payload = bytes.fromhex(input("data (hex) > "))

Thay đổi 2: Hai giai đoạn Register + Deploy

registry = set()
while True:
    choice = int(input("choice > "))
    payload = bytes.fromhex(input("data (hex) > "))
    hsh = CGL_hash(E0, payload)
    if choice == 1 and hsh == literal_eval(payload.decode("latin-1")):
        registry.add(hsh)
    elif choice == 2 and hsh in registry:
        eval(payload)

Register (choice 1): payload được decode bằng latin-1, rồi đi qua literal_eval(). Kết quả phải bằng CGL_hash(E0, payload) → tức payload khi parse phải trả về đúng digest
Deploy (choice 2): nếu hash đã nằm trong registry, server sẽ eval(payload) trực tiếp → đây là điểm để ta RCE lấy flag

Nhiệm vụ của challenge

Ở Scramble, ta chỉ cần tìm $E_0$ và credential sao cho CGL_hash(E0, credential) == credential (fixed point đơn thuần)
Ở Fixed Point, ta cần tìm $E_0$ $E_{0}$ và một payload bytes sao cho:
1. literal_eval(payload.decode("latin-1")) trả về digest (để register thành công)
2. CGL_hash(E0, payload) cũng trả về đúng digest đó
3. eval(payload) phải thực thi code in ra FLAG (để lấy flag khi deploy)

=> Payload phải vừa là dữ liệu hợp lệ cho literal_eval, vừa là code cho eval — tức là cần 1 polyglot payload

2, Chiến lược tấn công

2.1 Xây dựng polyglot payload bằng UTF-7 trick

Vấn đề: làm sao 1 chuỗi bytes vừa qua được literal_eval ra string, vừa khi eval thì chạy được print(FLAG)?
Trick UTF-7 coding cookie: Python cho phép khai báo encoding ở đầu file bằng comment # coding: utf_7. Khi eval() parse source code, nó sẽ dùng encoding này để decode
Trong UTF-7, chuỗi +AAo- sẽ decode thành ký tự newline (\n, U+000A)

Vậy ta xây dựng payload như sau:

# coding: utf_7
('<digest>' # +AAo-,print(FLAG)
)

Khi literal_eval(payload.decode("latin-1")) parse:
- Latin-1 decode giữ nguyên các byte
- literal_eval thấy một expression ('<digest>' # ...)
- Phần sau # là comment → bị bỏ qua
- Kết quả: trả về string <digest> ✓
Khi eval(payload) parse:
- Python đọc dòng đầu # coding: utf_7 → dùng UTF-7 để decode source
- +AAo- trong UTF-7 = newline → dòng 2 thực sự trở thành:
```
('<digest>' # 
,print(FLAG)
)
```
- Đây là 1 tuple expression hợp lệ: ('<digest>', print(FLAG))
- print(FLAG) được gọi → in ra flag ✓

2.2 Tác động đến bài toán backtracking

Ở Scramble, data là chuỗi hex SHA256 (64 ký tự ASCII) → 512 bit → backtrack 511 bước
Ở Fixed Point, payload có dạng:
```
b"# coding: utf_7\n('<digest>' # +AAo-,print(FLAG)\n)"
```
→ dài hơn đáng kể → khoảng 840 bit → backtrack 839 bước
Logic backtracking hoàn toàn giống Scramble (xem writeup trước): đi ngược từ curve đích về $E_0$ bằng cách giải phương trình bậc 2, thử random target curve nếu nhánh cụt
Điểm khác duy nhất: data_to_bits phải xử lý raw bytes thay vì string, và số bước backtrack nhiều hơn (~840 thay vì 511) → có thể cần thử nhiều target curve hơn một chút

2.3 Flow tổng thể

Random walk từ $y^2 = x^3 + x$ để tạo target curve $E_{final}$
Tính digest = SHA256(j_invariant(E_final))
Tạo payload = make_payload(digest) (polyglot UTF-7)
Verify: literal_eval(payload.decode("latin-1")) == digest
Tính bits từ payload bytes, tìm $\alpha_{last}$ và $A_{last}$ từ curve đích
Backtrack từ bước cuối về bước 0 để tìm $E_0$
Nếu cụt → quay lại bước 1 với target curve khác
Khi tìm được $E_0$ : gửi lên server → register → deploy → lấy flag

3, Code khai thác

from sage.all import *
from pwn import *
from ast import literal_eval
import hashlib
import random
import sys

p = 2**49 * 3**36 - 1
K = GF(p**2, "x", modulus=[1, 0, 1])
x = K.gen()

P_y = K['y']
y = P_y.gen()#old_alpha variable 

sys.setrecursionlimit(10_000)

def deterministic_sqrt(val):
    return min(val.sqrt(all=True))

def select0(E0, b0):
    torsion_points = sorted(E0.torsion_polynomial(2).roots(multiplicities=False))
    if b0:
        return torsion_points[-1], torsion_points[1]
    else:
        return torsion_points[1], torsion_points[-1]

def select(lambda0, lambda1, b):
    if b:
        return max(lambda0, lambda1)
    else:
        return min(lambda0, lambda1)

def next_curve(A, alpha, b):
    xi = alpha**2
    zeta = 3 * xi + A
    eta = deterministic_sqrt(zeta)
    new_A = -(4 * A + 15 * xi)
    lambda0 = alpha + 2 * eta
    lambda1 = alpha - 2 * eta
    new_alpha = select(lambda0, lambda1, b)
    return new_A, new_alpha

def data_to_bits(data):
    if isinstance(data, str):
        data = data.encode()
    return [int(b) for byte in data for b in "{:08b}".format(byte)]

def make_payload(digest):
    # Tạo payload UTF-7 trick: register thấy chuỗi digest qua literal_eval
    # deploy thì eval() chạy print(FLAG) nhờ UTF-7 coding cookie
    return (
        b"# coding: utf_7\n(\'" + digest.encode() +
        b"\' # +AAo-,print(FLAG)\n)"
    )

def backtrack(A_curr, alpha_curr, bit_idx, bits):
    if bit_idx == 0:
        B0 = -alpha_curr**3 - A_curr * alpha_curr
        E0 = EllipticCurve(K, [A_curr, B0])
        
        alpha_test, _ = select0(E0, bits[0])
        if alpha_test == alpha_curr:
            return E0
        return None

    depth = len(bits) - 1 - bit_idx
    if depth % 50 == 0:
        log.info(f"Depth : {depth}/{len(bits) - 1}...")

    b = bits[bit_idx]
    
    # PT bậc 2: 4*y^2 - 2*alpha_curr*y + (alpha_curr^2 + A_curr) = 0
    eq = 4*(y**2) - 2*alpha_curr*y + (alpha_curr**2 + A_curr)
    candidates = eq.roots(multiplicities=False)
    
    for alpha_old_cand in candidates:
        A_old_cand = (-A_curr - 15 * (alpha_old_cand**2)) / 4
        try:
            t_A, t_alpha = next_curve(A_old_cand, alpha_old_cand, b)
            if t_A == A_curr and t_alpha == alpha_curr:
                
                result = backtrack(A_old_cand, alpha_old_cand, bit_idx - 1, bits)
                
                if result is not None:
                    return result
                    
        except ValueError:
            continue
            
    return None


def solve():
    attempts = 0
    while True:
        attempts += 1
        print(f"\n[*] Lần thử thứ {attempts}: đang đi đến 1 đích ngẫu nhiên")
        
        # Tạo điểm đích ngẫu nhiên
        A = K(1)
        E = EllipticCurve(K, [A, 0])
        alpha, _ = select0(E, 0)
        
        for _ in range(30):
            b = random.choice([0, 1])
            A, alpha = next_curve(A, alpha, b)
           
        xi = alpha**2
        target_A = -(4 * A + 15 * xi)
        target_B = -alpha * (8 * A + 22 * xi)
        E_final = EllipticCurve(K, [target_A, target_B])

        
        # Tính credential từ đích, rồi tạo payload UTF-7 trick
        j_inv = str(E_final.j_invariant()).encode()
        digest = hashlib.sha256(j_inv).hexdigest()
        payload = make_payload(digest)
        
        # Kiểm tra payload hợp lệ với literal_eval
        assert literal_eval(payload.decode("latin-1")) == digest
        bits = data_to_bits(payload)
        
        # Tính A_last, alpha_last từ curve đích
        eq_tail = 8*y**3 + 2*target_A*y - target_B
        roots_alpha_last = eq_tail.roots(multiplicities=False)
        
        for alpha_last in roots_alpha_last:
            A_last = (-target_A - 15*alpha_last**2)/4
            
            E0 = backtrack(A_last, alpha_last, len(bits) - 1, bits)
            if E0 is not None:
                log.success(f"tìm thấy gốc E0 sau {attempts} lần thử.")
                return E0, payload


def main():
    E0, payload = solve()
    io = remote("localhost", 1337)

    def get_parts(val):
        coeffs = val.polynomial().list()
        part0 = int(coeffs[0]) if len(coeffs) > 0 else 0
        part1 = int(coeffs[1]) if len(coeffs) > 1 else 0
        return part0, part1

    a4_0, a4_1 = get_parts(E0.a4())
    a6_0, a6_1 = get_parts(E0.a6())
    
    io.sendlineafter(b"a4.0 > ", str(a4_0).encode())
    io.sendlineafter(b"a4.1 > ", str(a4_1).encode())
    io.sendlineafter(b"a6.0 > ", str(a6_0).encode())
    io.sendlineafter(b"a6.1 > ", str(a6_1).encode())
    
    # Register: gửi payload, server literal_eval thấy digest -> thêm vào registry
    io.sendlineafter(b"choice > ", b"1")
    io.sendlineafter(b"data (hex) > ", payload.hex().encode())
    
    # Deploy: gửi lại payload, server eval() chạy UTF-7 trick -> print(FLAG)
    io.sendlineafter(b"choice > ", b"2")
    io.sendlineafter(b"data (hex) > ", payload.hex().encode())
    io.interactive()

if __name__ == "__main__":
    main()

4, Kết quả

Tìm được $E_0$ và lấy flag sau 52 lần bước tiến ngẫu nhiên
Backtrack 839 bước (nhiều hơn 511 bước của Scramble do payload dài hơn)

Terminal

Once or nothing

1,Tổng quan

2,Cách tấn công

Code khai thác

Kết quả chạy code

Twice or nothing

1,Tổng quan

2,Cách tấn công

Code khai thác

Kết quả chạy code

Pow Pow

1,Tổng quan

2,Cách tấn công

Code khai thác

Kết quả chạy code

Isochronal scramble

1, Tổng quan về challenge

Hàm băm CGL

Nhiệm vụ của challenge

2, Chiến lược tấn công

2.1 Ý tưởng đầu tiên

2.2 Có thể đi ngược từ E512E_{512}E512​ về E0E_0E0​ không?

2.2.1 Điểm cuối trên đường cong E512E_{512}E512​ về E511E_{511}E511​

2.2.2 Bước cuối tìm E0E_0E0​

2.2.3 vấn đề thực sự nằm ở các node trung gian trên đường đi

Đánh giá về số đường đi lùi có thể của các đường cong trung gian

2.3 Chiến lược backtrack để tìm đến E0E_0E0​

2.4 Trick cuối cùng : Bước tiến vài bước để lùi

3, Code khai thác

4 , Kết quả

Isochronal Fixed Point

1, Tổng quan về challenge

Thay đổi so với Isochronal Scramble

Thay đổi 1: Input là raw bytes, không phải string

Thay đổi 2: Hai giai đoạn Register + Deploy

Nhiệm vụ của challenge

2, Chiến lược tấn công

2.1 Xây dựng polyglot payload bằng UTF-7 trick

2.2 Tác động đến bài toán backtracking

2.3 Flow tổng thể

3, Code khai thác

4, Kết quả

2.2 Có thể đi ngược từ $E_{512}$ về $E_0$ không?

2.2.1 Điểm cuối trên đường cong $E_{512}$ về $E_{511}$

2.2.2 Bước cuối tìm $E_0$

2.3 Chiến lược backtrack để tìm đến $E_0$