PwnCollege - note cryptography

Posted on In Views: Disqus:

cryptography

aes

ecb

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
import string

import requests
from pwn import *
from pwn import b64d, context, log

# AES-ECB: 16 bytes (128 bits) per block, PKCS#7 padding

context.log_level = "info"

URL = "http://challenge.localhost"
charset = string.printable.strip()

log.info("Start")

result = b""

block_size = 16

# b"A|flag{arch_linux_is_the_best_distro}"


def send_data(data):
    r = requests.post(URL, data={"content": data + "A"})
    if r.status_code != 200:
        exit()


def cleanup():
    r = requests.post(URL + "/reset")
    if r.status_code != 200:
        exit()


def send_part_of_flag(data):
    send_data(data.decode("latin1"))
    # <b>Encrypted backup:</b><pre>{b64encode(ct).decode()}</pre>
    r = requests.get(URL)
    a = r.text.split("<b>Encrypted backup:</b><pre>")[1].split("</pre>")[0]
    b = b64d(a)
    cleanup()
    return b


for i in range(1, 60):
    block_idx = (i - 1) // block_size
    pad_len = (block_size - i) % block_size
    padding = b"A" * pad_len

    ct = send_part_of_flag(padding)

    target_block = ct[block_idx * 16 : (block_idx + 1) * 16]

    for c in charset:
        c = c.encode()
        ct2 = send_part_of_flag(padding + result + c)
        guess_block = ct2[block_idx * 16 : (block_idx + 1) * 16]
        if guess_block == target_block:
            log.success(f"Found: {c} at {i}")
            result = result + c
            break

print(result)

cbc

POA - Decrypt

Padding Oracle Attack (POA)，专门针对 AES 算法的 CBC（密码分组链接）模式。

在 CBC 解密模式中，密文被分成 16 字节的块。当前密文块 Cn 先经过 AES 核心解密函数，得到一个中间值 (Intermediate Value) In。然后，In 必须和前一个密文块 Cn − 1（或者第一块的 IV）进行异或 (XOR)，才能得到最终的明文 Pn。

数学表示非常简单，这也是整个攻击的核心公式：

Pn = In ⊕ Cn − 1

服务端在解密后会检查 PKCS#7 填充是否合法（比如缺少 1 个字节就是 0x01，缺 2 个就是 0x02 0x02）。如果我们篡改了密文发过去，服务端解密后发现 padding 不对报错返回信息如 “Error”，发现 padding 对了就正常返回。服务端这个“只告诉你对不对，不告诉你为什么”的行为，就被视作 Oracle

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
from Crypto.Util.Padding import unpad
from pwn import *
from pwn import log, process, unhex, xor

# CBC mode - Padding Oracle Attack (Decrypt)

def get_encrypted_password():
    p = process(["/challenge/dispatcher", "flag"])
    p.recvuntil(b"TASK: ")
    res = unhex(p.recvline().strip())
    p.close()
    return res


def check_padding(p_worker, iv_test, cipher_block):
    payload = (iv_test + cipher_block).hex()
    p_worker.sendline(f"TASK: {payload}".encode())
    response = p_worker.recvline().decode()
    return "Error" not in response


log.info("Start")

target_data = get_encrypted_password()
blocks = [target_data[i : i + 16] for i in range(0, len(target_data), 16)]
p_worker = process(["/challenge/worker"])

recovered_plaintext = b""

for block_idx in range(1, len(blocks)):
    current_cipher_block = blocks[block_idx]
    original_prev_block = blocks[block_idx - 1]

    intermediate_value = bytearray(16)

    # 从块的最后一个字节向前爆破 (15 down to 0)
    for pad_val in range(1, 17):
        idx = 16 - pad_val

        for guess in range(256):
            # 构造用于测试的伪造前一块 (C'_{n-1})
            test_iv = bytearray(16)

            # 填充已经爆破出的中间值字节，使其异或后等于当前 pad_val
            for i in range(idx + 1, 16):
                test_iv[i] = intermediate_value[i] ^ pad_val

            # 将我们当前的猜测放入 target 字节
            test_iv[idx] = guess

            if check_padding(p_worker, bytes(test_iv), current_cipher_block):
                # 找到了正确的 guess，由于我们可能有 0x01 的伪正例，严谨起见需要进一步校验（此处从简）
                intermediate_value[idx] = guess ^ pad_val
                print(f"[+] Found byte {idx}: {hex(intermediate_value[idx])}")
                break

    # P_n = Intermediate_n \oplus C_{n-1}
    decrypted_block = xor(bytes(intermediate_value), original_prev_block)
    recovered_plaintext += decrypted_block
    print(f"[*] Decrypted block {block_idx}: {decrypted_block}")

# 去除 PKCS#7 padding
final_password = unpad(recovered_plaintext, 16).decode("latin1")
print(f"\n[!] Extracted Password: {final_password}")

POA - Encrypt

在 CBC 模式下，解密的本质是：

Pn = DK(Cn) ⊕ Cn − 1

利用 Padding Oracle Attack，我们可以爆破出某个密文块的中间状态 In：

In = DK(Cn)

既然 In 是固定的（仅由 Cn 和你无法获取的 Key 决定），那么只要我们能完全控制前一个密文块 Cn − 1，我们就能随心所欲地控制解密出的明文 Pn！公式如下：

Cn − 1 = In ⊕ Ptarget

解决思路： 从目标明文的最后一个 block 开始倒推：

  1. 随机生成一个垃圾 block 作为最后一个密文块 CN。
  2. 利用 Padding Oracle 算出 CN 的中间值 IN。
  3. 利用 IN 和你想要的明文 PN，计算出前一个密文块 CN − 1。
  4. 将 CN − 1 作为新的目标块，重复上述步骤，直到你算出最前面的 IV。
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
# worker
#!/usr/bin/exec-suid -- /usr/bin/python3 -I

from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from Crypto.Random import get_random_bytes

import time
import sys

key = open("/challenge/.key", "rb").read()

while line := sys.stdin.readline():
    if not line.startswith("TASK: "):
        continue
    data = bytes.fromhex(line.split()[1])
    iv, ciphertext = data[:16], data[16:]

    cipher = AES.new(key=key, mode=AES.MODE_CBC, iv=iv)
    try:
        plaintext = unpad(cipher.decrypt(ciphertext), cipher.block_size).decode('latin1')
    except ValueError as e:
        print("Error:", e)
        continue

    if plaintext == "sleep":
        print("Sleeping!")
        time.sleep(1)
    elif plaintext == "please give me the flag, kind worker process!":
        print("Victory! Your flag:")
        print(open("/flag").read())
    else:
        print("Unknown command!")

# dispatcher
#!/usr/bin/exec-suid -- /usr/bin/python3 -I

import os

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Random import get_random_bytes

key = open("/challenge/.key", "rb").read()
cipher = AES.new(key=key, mode=AES.MODE_CBC)
ciphertext = cipher.iv + cipher.encrypt(pad(b"sleep", cipher.block_size))

print(f"TASK: {ciphertext.hex()}")
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
import os

from pwn import *
from pwn import log, process, xor

# CBC mode - Padding Oracle Attack (Encrypt)


def check_padding(p_worker, iv_test, cipher_block):
    payload = (iv_test + cipher_block).hex()
    p_worker.sendline(f"TASK: {payload}".encode())
    response = p_worker.recvline().decode()
    return "Error" not in response


log.info("Start")

p_worker = process(["/challenge/worker"])

target_message = b"please give me the flag, kind worker process!"
target_message = pad(target_message, 16)
message_blocks = [target_message[i : i + 16] for i in range(0, len(target_message), 16)]

forged_ciphertext = [os.urandom(16)]

# 逆向遍历目标明文块
for block_idx, p_block in enumerate(reversed(message_blocks)):
    log.info(
        f"Forging block {len(message_blocks) - block_idx} / {len(message_blocks)}..."
    )
    current_cipher_block = forged_ciphertext[0]
    intermediate_value = bytearray(16)

    # 爆破 16 个 byte
    for pad_val in range(1, 17):
        idx = 16 - pad_val
        found = False

        for guess in range(256):
            test_iv = bytearray(16)
            # 填充已知的中间值，构造所需的 padding
            for i in range(idx + 1, 16):
                test_iv[i] = intermediate_value[i] ^ pad_val

            test_iv[idx] = guess

            if check_padding(p_worker, bytes(test_iv), current_cipher_block):
                # 处理 padding=1 时的 false positive
                # 如果你爆破 `idx = 15` 时，原密文的解密结果恰好是 `0x02 0x02`，就会因为误判 `0x01` 成功。
                if pad_val == 1:
                    test_iv[idx - 1] ^= 1
                    if not check_padding(
                        p_worker, bytes(test_iv), current_cipher_block
                    ):
                        continue

                intermediate_value[idx] = guess ^ pad_val
                found = True
                break

        if not found:
            log.error("Fail")
            exit(1)

    prev_cipher_block = xor(bytes(intermediate_value), p_block)
    forged_ciphertext.insert(0, prev_cipher_block)

iv = forged_ciphertext[0]
final_ciphertext = b"".join(forged_ciphertext[1:])
final_payload = (iv + final_ciphertext).hex()

log.success("Payload forged successfully. Sending to worker...")
p_worker.sendline(f"TASK: {final_payload}".encode())

print(p_worker.recvall(timeout=2).decode())
1
2
3
4
5
6
7
8
9
10
[*] Start
[+] Starting local process '/challenge/worker': pid 185
[*] Forging block 3 / 3...
[*] Forging block 2 / 3...
[*] Forging block 1 / 3...
[+] Payload forged successfully. Sending to worker...
[+] Receiving all data: Done (79B)
[*] Stopped process '/challenge/worker' (pid 185)
Victory! Your flag:
pwn.college{IWMb6al3m7LNcJmiBAyOUdRv2Kh.dFDN3kDL4cjM1gzW}

Asymmetric Encryption

DHKE

Diffie-Hellman Key Exchange

1. 公共参数 (The Public Info)

Alice 和 Bob 首先要在公网上明文敲定一个巨大的质数 p 和一个原根 g。因为它们在有限域 (Finite Field，即基于 modulo p 的环境) 中定义了接下来所有运算的规则。Eve 完全可以看到这两个数字。

2. 私钥 (The Private Keys)

接着，两人各自在本地生成一个绝对保密的随机数——Alice 的是 a，Bob 的是 b。

3. 计算并交换公钥 (Public Keys)

接下来是在终端里跑计算的时候了：

  • Alice 计算： A = ga (mod  p)
  • Bob 计算： B = gb (mod  p)

算完之后，他们把 A 和 B 明文扔到网络上交换。

4. 离散对数难题 (Discrete Logarithm)

现在，Eve 手里有 p, g, A, 和 B。

如果这是普通的实数域，用高中学的对数函数就能反推出 a 和 b。但是在有限域里，因为有一个 modulo p 的存在，数值会在 0 到 p − 1 之间无限循环。这被称为“离散对数难题”。

  • Alice 拿到了 Bob 的公钥 B，计算：s = Ba (mod  p)
  • Bob 拿到了 Alice 的公钥 A，计算：s = Ab (mod  p)

让我们用一点初中数学展开它：

s = (gb)a (mod  p) = gab (mod  p) = (ga)b (mod  p)

Alice 和 Bob 得到了完全一致的 s！这个 s 就是他们接下来用来跑 AES 的对称密钥。

在这个体系里，A 和 B 被称为 public keys，a 和 b 则是 private keys。

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
# 2048-bit MODP Group from RFC3526
pro = int.from_bytes(
    bytes.fromhex(
        "FFFFFFFF FFFFFFFF C90FDAA2 2168C234 C4C6628B 80DC1CD1 "
        "29024E08 8A67CC74 020BBEA6 3B139B22 514A0879 8E3404DD "
        "EF9519B3 CD3A431B 302B0A6D F25F1437 4FE1356D 6D51C245 "
        "E485B576 625E7EC6 F44C42E9 A637ED6B 0BFF5CB6 F406B7ED "
        "EE386BFB 5A899FA5 AE9F2411 7C4B1FE6 49286651 ECE45B3D "
        "C2007CB8 A163BF05 98DA4836 1C55D39A 69163FA8 FD24CF5F "
        "83655D23 DCA3AD96 1C62F356 208552BB 9ED52907 7096966D "
        "670C354E 4ABC9804 F1746C08 CA18217C 32905E46 2E36CE3B "
        "E39E772C 180E8603 9B2783A2 EC07A28F B5C55DF0 6F4C52C9 "
        "DE2BCBF6 95581718 3995497C EA956AE5 15D22618 98FA0510 "
        "15728E5A 8AACAA68 FFFFFFFF FFFFFFFF"
    ),
    "big",
)
g = 2
print(f"p = {pro:#x}")
print(f"g = {g:#x}")

a = getrandbits(2048)
A = pow(g, a, pro)
print(f"A = {A:#x}")

try:
    B = int(input("B? "), 16)
except ValueError:
    print("Invalid B value (not a hex number)", file=sys.stderr)
    sys.exit(1)
if B <= 2**1024:
    print("Invalid B value (B <= 2**1024)", file=sys.stderr)
    sys.exit(1)

s = pow(B, a, pro)
try:
    if int(input("s? "), 16) == s:
        print("Correct! Here is your flag:")
        print(open("/flag").read())
    else:
        print("Incorrect... Should have been:", file=sys.stderr)
        print(f"s = {s:#x}")
except ValueError:
    print("Invalid s value (not a hex number)", file=sys.stderr)
    sys.exit(1)
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
from pwn import *
from pwn import log, process

pro = process(["/challenge/run"], stdin=process.PTY, stdout=process.PTY)

log.info("START")

pro.recvuntil(b"p = ")
p = int(pro.recvline().strip(), 16)

pro.recvuntil(b"g = ")
g = int(pro.recvline().strip(), 16)

pro.recvuntil(b"A = ")
A = int(pro.recvline().strip(), 16)

B = p
pro.recvuntil(b"B? ")
pro.sendline(f"{B:#x}")

s = 0
pro.recvuntil(b"s? ")
pro.sendline(f"{s:#x}")

pro.interactive()

DHKE to AES

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
#!/usr/bin/exec-suid -- /usr/bin/python3 -I

import sys
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Random.random import getrandbits

flag = open("/flag", "rb").read()
assert len(flag) <= 256

# 2048-bit MODP Group from RFC3526
p = int.from_bytes(bytes.fromhex(
    "FFFFFFFF FFFFFFFF C90FDAA2 2168C234 C4C6628B 80DC1CD1 "
    "29024E08 8A67CC74 020BBEA6 3B139B22 514A0879 8E3404DD "
    "EF9519B3 CD3A431B 302B0A6D F25F1437 4FE1356D 6D51C245 "
    "E485B576 625E7EC6 F44C42E9 A637ED6B 0BFF5CB6 F406B7ED "
    "EE386BFB 5A899FA5 AE9F2411 7C4B1FE6 49286651 ECE45B3D "
    "C2007CB8 A163BF05 98DA4836 1C55D39A 69163FA8 FD24CF5F "
    "83655D23 DCA3AD96 1C62F356 208552BB 9ED52907 7096966D "
    "670C354E 4ABC9804 F1746C08 CA18217C 32905E46 2E36CE3B "
    "E39E772C 180E8603 9B2783A2 EC07A28F B5C55DF0 6F4C52C9 "
    "DE2BCBF6 95581718 3995497C EA956AE5 15D22618 98FA0510 "
    "15728E5A 8AACAA68 FFFFFFFF FFFFFFFF"
), "big")
g = 2
print(f"p = {p:#x}")
print(f"g = {g:#x}")

a = getrandbits(2048)
A = pow(g, a, p)
print(f"A = {A:#x}")

try:
    B = int(input("B? "), 16)
except ValueError:
    print("Invalid B value (not a hex number)", file=sys.stderr)
    sys.exit(1)
if B <= 2**1024:
    print("Invalid B value (B <= 2**1024)", file=sys.stderr)
    sys.exit(1)

s = pow(B, a, p)
key = s.to_bytes(256, "little")[:16]

# friendship ended with DHKE, AES is my new best friend
cipher = AES.new(key=key, mode=AES.MODE_CBC)
flag = open("/flag", "rb").read()
ciphertext = cipher.iv + cipher.encrypt(pad(flag, cipher.block_size))
print(f"Flag Ciphertext (hex): {ciphertext.hex()}")
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
from Crypto.Cipher import AES
from pwn import *
from pwn import log, process, unhex

pro = process(["/challenge/run"], stdin=process.PTY, stdout=process.PTY)

log.info("START")

pro.recvuntil(b"p = ")
p = int(pro.recvline().strip(), 16)

pro.recvuntil(b"g = ")
g = int(pro.recvline().strip(), 16)

pro.recvuntil(b"A = ")
A = int(pro.recvline().strip(), 16)

B = p
pro.recvuntil(b"B? ")
pro.sendline(f"{B:#x}")

s = 0
key = s.to_bytes(256, "little")[:16]


pro.recvuntil(b"Flag Ciphertext (hex): ")
ciphertext = unhex(pro.readline().strip())

cipher = AES.new(key=key, mode=AES.MODE_CBC)

flag = cipher.decrypt(ciphertext)

print(flag)

pro.interactive()

RSA 1

Rivest-Shamir-Adleman

Alice 首先在后台静默生成两个大素数 p 和 q 然后将它们相乘：

n = p × q

这个公开的 n 定义了一个模 n 的有限域 (Finite Field)。欧拉定理指出，模 n (即 p × q) 域中的指数运算，实际上是在模 (p − 1)(q − 1) 的域中进行的。or 交换环 (Commutative Ring)

只要知道 (p − 1)(q − 1)，Alice 就可以轻松计算出一个 d，使得：

e × d ≡ 1 (mod  (p − 1)(q − 1))

  • Public Key (公钥): 包含 n 和 e。你可以把它们像推送到 AUR 一样公开出去。这里的 e 通常选一个较小但安全的数值（比如 65537），以降低计算开销（绝不浪费 CPU 周期，很符合 Arch 精神）。
  • Private Key (私钥): 就是 d。绝对私密，是你掌控一切的终极凭证。

RSA 的非对称魅力在于：

  • Encryption (加密): Bob 拿到 Alice 的公钥，把明文消息 m 加密成密文 c：

c ≡ me (mod  n)

  • Decryption (解密): Alice 用她的私钥 d 进行逆向操作来恢复明文 m：

m ≡ cd (mod  n)

  • 原理解释: 因为 cd = (me)d = me × d = m1 = m。

身份验证 (Attestation/Signatures)

因为 e × d = d × e，Alice 也可以用私钥 d 来“加密”消息，而任何拥有公钥 e 的人都能“解密”。只有拥有 d 的 Alice 才能生成这串特定的密文，这就完美证明了消息绝对且仅来自于 Alice 本人。

如果你要回复 Bob，你同样需要获取 Bob 的公钥（属于他自己的 n 和 e），然后重复上述的流程。

1
2
3
4
5
6
7
8
9
10
flag = open("/flag", "rb").read()
assert len(flag) <= 256

key = RSA.generate(2048)
print(f"(public)  n = {key.n:#x}")
print(f"(public)  e = {key.e:#x}")
print(f"(private) d = {key.d:#x}")

ciphertext = pow(int.from_bytes(flag, "little"), key.e, key.n).to_bytes(256, "little")
print(f"Flag Ciphertext (hex): {ciphertext.hex()}")
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from pwn import *
from pwn import log, process, unhex

pro = process(["/challenge/run"], stdin=process.PTY, stdout=process.PTY)
log.info("START")
pro.recvuntil(b"(public)  n = ")
n = int(pro.recvline().strip(), 16)

pro.recvuntil(b"(public)  e = ")
e = int(pro.recvline().strip(), 16)

pro.recvuntil(b"(private) d = ")
d = int(pro.recvline().strip(), 16)

pro.recvuntil(b"Flag Ciphertext (hex): ")
ciphertext = unhex(pro.readline().strip())

flag = pow(int.from_bytes(ciphertext, "little"), d, n).to_bytes(256, "little")

print(flag)

pro.interactive()

RSA 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# challenge

#!/usr/bin/exec-suid -- /usr/bin/python3 -I

from Crypto.PublicKey import RSA

flag = open("/flag", "rb").read()
assert len(flag) <= 256

key = RSA.generate(2048)
print(f"e = {key.e:#x}")
print(f"p = {key.p:#x}")
print(f"q = {key.q:#x}")

ciphertext = pow(int.from_bytes(flag, "little"), key.e, key.n).to_bytes(256, "little")
print(f"Flag Ciphertext (hex): {ciphertext.hex()}")

e × d ≡ 1 (mod  (p − 1)(q − 1))

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
from pwn import *
from pwn import log, process, unhex

pro = process(["/challenge/run"], stdin=process.PTY, stdout=process.PTY)
log.info("START")
pro.recvuntil(b"e = ")
e = int(pro.recvline().strip(), 16)

pro.recvuntil(b"p = ")
p = int(pro.recvline().strip(), 16)

pro.recvuntil(b"q = ")
q = int(pro.recvline().strip(), 16)

pro.recvuntil(b"Flag Ciphertext (hex): ")
ciphertext = unhex(pro.readline().strip())

n = p * q

d = pow(e, -1, (p - 1) * (q - 1))

flag = pow(int.from_bytes(ciphertext, "little"), d, n).to_bytes(256, "little")

print(flag)

pro.interactive()

RSA 3

Full challenge source (levels 1-14) 
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
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
#!/usr/bin/exec-suid -- /usr/bin/python3 -I

import sys
import string
import random
import pathlib
import base64
import json
import textwrap

from Crypto.Cipher import AES
from Crypto.Hash.SHA256 import SHA256Hash
from Crypto.PublicKey import RSA
from Crypto.Random import get_random_bytes
from Crypto.Random.random import getrandbits, randrange
from Crypto.Util.strxor import strxor
from Crypto.Util.Padding import pad, unpad


flag = open("/flag", "rb").read()
config = (pathlib.Path(__file__).parent / ".config").read_text()
level = int(config)


def show(name, value, *, b64=True):
    print(f"{name}: {value}")


def show_b64(name, value):
    show(f"{name} (b64)", base64.b64encode(value).decode())

def show_hex_block(name, value, byte_block_size=16):
    value_to_show = ""

    for i in range(0, len(value), byte_block_size):
        value_to_show += f"{value[i:i+byte_block_size].hex()}"
        value_to_show += " "
    show(f"{name} (hex)", value_to_show)


def show_hex(name, value):
    show(name, hex(value))


def input_(name):
    try:
        return input(f"{name}: ")
    except (KeyboardInterrupt, EOFError):
        print()
        exit(0)


def input_b64(name):
    data = input_(f"{name} (b64)")
    try:
        return base64.b64decode(data)
    except base64.binascii.Error:
        print(f"Failed to decode base64 input: {data!r}", file=sys.stderr)
        exit(1)


def input_hex(name):
    data = input_(name)
    try:
        return int(data, 16)
    except Exception:
        print(f"Failed to decode hex input: {data!r}", file=sys.stderr)
        exit(1)


def level1():
    """
    In this challenge you will decode base64 data.
    Despite base64 data appearing "mangled", it is not an encryption scheme.
    It is an encoding, much like base2, base10, base16, and ascii.
    It is a popular way of encoding raw bytes.
    """
    show_b64("flag", flag)


def level2():
    """
    In this challenge you will decrypt a secret encrypted with a one-time pad.
    Although simple, this is the most secure encryption mechanism, if you could just securely transfer the key.
    """
    key = get_random_bytes(len(flag))
    ciphertext = strxor(flag, key)
    show_b64("key", key)
    show_b64("secret ciphertext", ciphertext)


def level3():
    """
    In this challenge you will decrypt a secret encrypted with a one-time pad.
    You can encrypt arbitrary data, with the key being reused each time.
    """
    key = get_random_bytes(256)
    assert len(flag) <= len(key)

    ciphertext = strxor(flag, key[:len(flag)])
    show_b64("secret ciphertext", ciphertext)

    while True:
        plaintext = input_b64("plaintext")
        ciphertext = strxor(plaintext, key[:len(plaintext)])
        show_b64("ciphertext", ciphertext)


def level4():
    """
    In this challenge you will decrypt a secret encrypted with Advanced Encryption Standard (AES).
    The Electronic Codebook (ECB) block cipher mode of operation is used.
    """
    key = get_random_bytes(16)
    cipher = AES.new(key=key, mode=AES.MODE_ECB)
    ciphertext = cipher.encrypt(pad(flag, cipher.block_size))
    show_b64("key", key)
    show_b64("secret ciphertext", ciphertext)



def level5():
    """
    In this challenge you will decrypt a secret encrypted with Advanced Encryption Standard (AES).
    The Electronic Codebook (ECB) block cipher mode of operation is used.
    You can encrypt arbitrary data, which has the secret appended to it, with the key being reused each time.
    """
    key = get_random_bytes(16)
    cipher = AES.new(key=key, mode=AES.MODE_ECB)

    ciphertext = cipher.encrypt(pad(flag, cipher.block_size))
    show_b64("secret ciphertext", ciphertext)
    show_hex_block("secret ciphertext", ciphertext)

    while True:
        plaintext_prefix = input_b64("plaintext prefix")
        ciphertext = cipher.encrypt(pad(plaintext_prefix + flag, cipher.block_size))
        show_b64("ciphertext", ciphertext)
        show_hex_block("ciphertext", ciphertext)


def level6():
    """
    In this challenge you will perform a Diffie-Hellman key exchange.
    """
    # 2048-bit MODP Group from RFC3526
    p = int.from_bytes(bytes.fromhex(
        "FFFFFFFF FFFFFFFF C90FDAA2 2168C234 C4C6628B 80DC1CD1 "
        "29024E08 8A67CC74 020BBEA6 3B139B22 514A0879 8E3404DD "
        "EF9519B3 CD3A431B 302B0A6D F25F1437 4FE1356D 6D51C245 "
        "E485B576 625E7EC6 F44C42E9 A637ED6B 0BFF5CB6 F406B7ED "
        "EE386BFB 5A899FA5 AE9F2411 7C4B1FE6 49286651 ECE45B3D "
        "C2007CB8 A163BF05 98DA4836 1C55D39A 69163FA8 FD24CF5F "
        "83655D23 DCA3AD96 1C62F356 208552BB 9ED52907 7096966D "
        "670C354E 4ABC9804 F1746C08 CA18217C 32905E46 2E36CE3B "
        "E39E772C 180E8603 9B2783A2 EC07A28F B5C55DF0 6F4C52C9 "
        "DE2BCBF6 95581718 3995497C EA956AE5 15D22618 98FA0510 "
        "15728E5A 8AACAA68 FFFFFFFF FFFFFFFF"
    ), "big")
    g = 2

    show_hex("p", p)
    show_hex("g", g)

    a = getrandbits(2048)
    A = pow(g, a, p)
    show_hex("A", A)

    B = input_hex("B")
    if not (B > 2**1024):
        print("Invalid B value (B <= 2**1024)", file=sys.stderr)
        exit(1)

    s = pow(B, a, p)

    key = s.to_bytes(256, "little")
    assert len(flag) <= len(key)
    ciphertext = strxor(flag, key[:len(flag)])
    show_b64("secret ciphertext", ciphertext)


def level7():
    """
    In this challenge you will decrypt a secret encrypted with RSA (Rivest–Shamir–Adleman).
    You will be provided with both the public key and private key.
    """
    key = RSA.generate(2048)
    assert len(flag) <= 256
    ciphertext = pow(int.from_bytes(flag, "little"), key.e, key.n).to_bytes(256, "little")
    show_hex("e", key.e)
    show_hex("d", key.d)
    show_hex("n", key.n)
    show_b64("secret ciphertext", ciphertext)


def level8():
    """
    In this challenge you will decrypt a secret encrypted with RSA (Rivest–Shamir–Adleman).
    You will be provided with the prime factors of n.
    """
    key = RSA.generate(2048)
    assert len(flag) <= 256
    ciphertext = pow(int.from_bytes(flag, "little"), key.e, key.n).to_bytes(256, "little")
    show_hex("e", key.e)
    show_hex("p", key.p)
    show_hex("q", key.q)
    show_b64("secret ciphertext", ciphertext)


def level9():
    """
    In this challenge you will hash data with a Secure Hash Algorithm (SHA256).
    You will find a small hash collision.
    Your goal is to find data, which when hashed, has the same hash as the secret.
    Only the first 2 bytes of the SHA256 hash are considered.
    """
    prefix_length = 2
    sha256 = SHA256Hash(flag).digest()
    show_b64(f"secret sha256[:{prefix_length}]", sha256[:prefix_length])

    collision = input_b64("collision")
    if SHA256Hash(collision).digest()[:prefix_length] == sha256[:prefix_length]:
        show("flag", flag.decode())


def level10():
    """
    In this challenge you will hash data with a Secure Hash Algorithm (SHA256).
    You will compute a small proof-of-work.
    Your goal is to find response data, which when appended to the challenge data and hashed, begins with 2 null-bytes.
    """
    difficulty = 2

    challenge = get_random_bytes(32)
    show_b64("challenge", challenge)

    response = input_b64("response")
    if SHA256Hash(challenge + response).digest()[:difficulty] == (b'\0' * difficulty):
        show("flag", flag.decode())


def level11():
    """
    In this challenge you will complete an RSA challenge-response.
    You will be provided with both the public key and private key.
    """
    key = RSA.generate(2048)

    show_hex("e", key.e)
    show_hex("d", key.d)
    show_hex("n", key.n)

    challenge = int.from_bytes(get_random_bytes(256), "little") % key.n
    show_hex("challenge", challenge)

    response = input_hex("response")
    if pow(response, key.e, key.n) == challenge:
        show("flag", flag.decode())


def level12():
    """
    In this challenge you will complete an RSA challenge-response.
    You will provide the public key.
    """
    e = input_hex("e")
    n = input_hex("n")

    if not (e > 2):
        print("Invalid e value (e > 2)", file=sys.stderr)
        exit(1)

    if not (2**512 < n < 2**1024):
        print("Invalid n value (2**512 < n < 2**1024)", file=sys.stderr)
        exit(1)

    challenge = int.from_bytes(get_random_bytes(64), "little")
    show_hex("challenge", challenge)

    response = input_hex("response")
    if pow(response, e, n) == challenge:
        ciphertext = pow(int.from_bytes(flag, "little"), e, n).to_bytes(256, "little")
        show_b64("secret ciphertext", ciphertext)


def level13():
    """
    In this challenge you will work with public key certificates.
    You will be provided with a self-signed root certificate.
    You will also be provided with the root private key, and must use that to sign a user certificate.
    """
    root_key = RSA.generate(2048)

    show_hex("root key d", root_key.d)

    root_certificate = {
        "name": "root",
        "key": {
            "e": root_key.e,
            "n": root_key.n,
        },
        "signer": "root",
    }

    root_trusted_certificates = {
        "root": root_certificate,
    }

    root_certificate_data = json.dumps(root_certificate).encode()
    root_certificate_hash = SHA256Hash(root_certificate_data).digest()
    root_certificate_signature = pow(
        int.from_bytes(root_certificate_hash, "little"),
        root_key.d,
        root_key.n
    ).to_bytes(256, "little")

    show_b64("root certificate", root_certificate_data)
    show_b64("root certificate signature", root_certificate_signature)

    user_certificate_data = input_b64("user certificate")
    user_certificate_signature = input_b64("user certificate signature")

    try:
        user_certificate = json.loads(user_certificate_data)
    except json.JSONDecodeError:
        print("Invalid user certificate", file=sys.stderr)
        exit(1)

    user_name = user_certificate.get("name")
    if user_name in root_trusted_certificates:
        print(f"Invalid user certificate name: `{user_name}`", file=sys.stderr)
        exit(1)

    user_key = user_certificate.get("key", {})
    if not (isinstance(user_key.get("e"), int) and isinstance(user_key.get("n"), int)):
        print(f"Invalid user certificate key: `{user_key}`", file=sys.stderr)
        exit(1)

    if not (user_key["e"] > 2):
        print("Invalid user certificate key e value (e > 2)", file=sys.stderr)
        exit(1)

    if not (2**512 < user_key["n"] < 2**1024):
        print("Invalid user certificate key n value (2**512 < n < 2**1024)", file=sys.stderr)
        exit(1)

    user_signer = user_certificate.get("signer")
    if user_signer not in root_trusted_certificates:
        print(f"Untrusted user certificate signer: `{user_signer}`", file=sys.stderr)
        exit(1)

    user_signer_key = root_trusted_certificates[user_signer]["key"]
    user_certificate_hash = SHA256Hash(user_certificate_data).digest()
    user_certificate_check = pow(
        int.from_bytes(user_certificate_signature, "little"),
        user_signer_key["e"],
        user_signer_key["n"]
    ).to_bytes(256, "little")[:len(user_certificate_hash)]

    if user_certificate_check != user_certificate_hash:
        print("Untrusted user certificate: invalid signature", file=sys.stderr)
        exit(1)

    ciphertext = pow(int.from_bytes(flag, "little"), user_key["e"], user_key["n"]).to_bytes(256, "little")
    show_b64("secret ciphertext", ciphertext)


def level14():
    """
    In this challenge you will perform a simplified Transport Layer Security (TLS) handshake, acting as the server.
    You will be provided with Diffie-Hellman parameters, a self-signed root certificate, and the root private key.
    The client will request to establish a secure channel with a particular name, and initiate a Diffie-Hellman key exchange.
    The server must complete the key exchange, and derive an AES-128 key from the exchanged secret.
    Then, using the encrypted channel, the server must supply the requested user certificate, signed by root.
    Finally, using the encrypted channel, the server must sign the handshake to prove ownership of the private user key.
    """
    # 2048-bit MODP Group from RFC3526
    p = int.from_bytes(bytes.fromhex(
        "FFFFFFFF FFFFFFFF C90FDAA2 2168C234 C4C6628B 80DC1CD1 "
        "29024E08 8A67CC74 020BBEA6 3B139B22 514A0879 8E3404DD "
        "EF9519B3 CD3A431B 302B0A6D F25F1437 4FE1356D 6D51C245 "
        "E485B576 625E7EC6 F44C42E9 A637ED6B 0BFF5CB6 F406B7ED "
        "EE386BFB 5A899FA5 AE9F2411 7C4B1FE6 49286651 ECE45B3D "
        "C2007CB8 A163BF05 98DA4836 1C55D39A 69163FA8 FD24CF5F "
        "83655D23 DCA3AD96 1C62F356 208552BB 9ED52907 7096966D "
        "670C354E 4ABC9804 F1746C08 CA18217C 32905E46 2E36CE3B "
        "E39E772C 180E8603 9B2783A2 EC07A28F B5C55DF0 6F4C52C9 "
        "DE2BCBF6 95581718 3995497C EA956AE5 15D22618 98FA0510 "
        "15728E5A 8AACAA68 FFFFFFFF FFFFFFFF"
    ), "big")
    g = 2

    show_hex("p", p)
    show_hex("g", g)

    root_key = RSA.generate(2048)

    show_hex("root key d", root_key.d)

    root_certificate = {
        "name": "root",
        "key": {
            "e": root_key.e,
            "n": root_key.n,
        },
        "signer": "root",
    }

    root_trusted_certificates = {
        "root": root_certificate,
    }

    root_certificate_data = json.dumps(root_certificate).encode()
    root_certificate_hash = SHA256Hash(root_certificate_data).digest()
    root_certificate_signature = pow(
        int.from_bytes(root_certificate_hash, "little"),
        root_key.d,
        root_key.n
    ).to_bytes(256, "little")

    show_b64("root certificate", root_certificate_data)
    show_b64("root certificate signature", root_certificate_signature)

    name = ''.join(random.choices(string.ascii_lowercase, k=16))
    show("name", name)

    a = getrandbits(2048)
    A = pow(g, a, p)
    show_hex("A", A)

    B = input_hex("B")
    if not (B > 2**1024):
        print("Invalid B value (B <= 2**1024)", file=sys.stderr)
        exit(1)

    s = pow(B, a, p)
    key = SHA256Hash(s.to_bytes(256, "little")).digest()[:16]
    cipher_encrypt = AES.new(key=key, mode=AES.MODE_CBC, iv=b"\0"*16)
    cipher_decrypt = AES.new(key=key, mode=AES.MODE_CBC, iv=b"\0"*16)

    def decrypt_input_b64(name):
        data = input_b64(name)
        try:
            return unpad(cipher_decrypt.decrypt(data), cipher_decrypt.block_size)
        except ValueError as e:
            print(f"{name}: {e}", file=sys.stderr)
            exit(1)

    user_certificate_data = decrypt_input_b64("user certificate")
    user_certificate_signature = decrypt_input_b64("user certificate signature")
    user_signature = decrypt_input_b64("user signature")

    try:
        user_certificate = json.loads(user_certificate_data)
    except json.JSONDecodeError:
        print("Invalid user certificate", file=sys.stderr)
        exit(1)

    user_name = user_certificate.get("name")
    if user_name != name:
        print(f"Invalid user certificate name: `{user_name}`", file=sys.stderr)
        exit(1)

    user_key = user_certificate.get("key", {})
    if not (isinstance(user_key.get("e"), int) and isinstance(user_key.get("n"), int)):
        print(f"Invalid user certificate key: `{user_key}`", file=sys.stderr)
        exit(1)

    if not (user_key["e"] > 2):
        print("Invalid user certificate key e value (e > 2)", file=sys.stderr)
        exit(1)

    if not (2**512 < user_key["n"] < 2**1024):
        print("Invalid user certificate key n value (2**512 < n < 2**1024)", file=sys.stderr)
        exit(1)

    user_signer = user_certificate.get("signer")
    if user_signer not in root_trusted_certificates:
        print(f"Untrusted user certificate signer: `{user_signer}`", file=sys.stderr)
        exit(1)

    user_signer_key = root_trusted_certificates[user_signer]["key"]
    user_certificate_hash = SHA256Hash(user_certificate_data).digest()
    user_certificate_check = pow(
        int.from_bytes(user_certificate_signature, "little"),
        user_signer_key["e"],
        user_signer_key["n"]
    ).to_bytes(256, "little")[:len(user_certificate_hash)]

    if user_certificate_check != user_certificate_hash:
        print("Untrusted user certificate: invalid signature", file=sys.stderr)
        exit(1)

    user_signature_data = (
        name.encode().ljust(256, b"\0") +
        A.to_bytes(256, "little") +
        B.to_bytes(256, "little")
    )
    user_signature_hash = SHA256Hash(user_signature_data).digest()
    user_signature_check = pow(
        int.from_bytes(user_signature, "little"),
        user_key["e"],
        user_key["n"]
    ).to_bytes(256, "little")[:len(user_signature_hash)]

    if user_signature_check != user_signature_hash:
        print("Untrusted user: invalid signature", file=sys.stderr)
        exit(1)

    ciphertext = cipher_encrypt.encrypt(pad(flag, cipher_encrypt.block_size))
    show_b64("secret ciphertext", ciphertext)


def challenge():
    challenge_level = globals()[f"level{level}"]
    description = textwrap.dedent(challenge_level.__doc__)

    print("===== Welcome to Cryptography! =====")
    print("In this series of challenges, you will be working with various cryptographic mechanisms.")
    print(description)
    print()

    challenge_level()


challenge()

.config -> 11

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from pwn import *
from pwn import log, process

pro = process(["/challenge/run"], stdin=process.PTY, stdout=process.PTY)
log.info("START")
pro.recvuntil(b"e: ")
e = int(pro.recvline().strip(), 16)

pro.recvuntil(b"d: ")
d = int(pro.recvline().strip(), 16)

pro.recvuntil(b"n: ")
n = int(pro.recvline().strip(), 16)

pro.recvuntil(b"challenge: ")
challenge = int(pro.recvline().strip(), 16)

ciphertext = pow(challenge, d, n)

pro.recvuntil(b"response: ")
# 把整数转成十六进制字符串，切掉 0x，再编码成 bytes 流
pro.sendline(hex(ciphertext)[2:].encode())

pro.interactive()

RSA 4

.config -> 12

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def level12():
    """
    In this challenge you will complete an RSA challenge-response.
    You will provide the public key.
    """
    e = input_hex("e")
    n = input_hex("n")

    if not (e > 2):
        print("Invalid e value (e > 2)", file=sys.stderr)
        exit(1)

    if not (2**512 < n < 2**1024):
        print("Invalid n value (2**512 < n < 2**1024)", file=sys.stderr)
        exit(1)

    challenge = int.from_bytes(get_random_bytes(64), "little")
    show_hex("challenge", challenge)

    response = input_hex("response")
    if pow(response, e, n) == challenge:
        ciphertext = pow(int.from_bytes(flag, "little"), e, n).to_bytes(256, "little")
        show_b64("secret ciphertext", ciphertext)
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
from Crypto.PublicKey import RSA
from pwn import *
from pwn import b64d, log, process

pro = process(["/challenge/run"], stdin=process.PTY, stdout=process.PTY)
log.info("START")

key = RSA.generate(1024)

e = key.e
d = key.d
n = key.n
pro.recvuntil(b"e: ")
pro.sendline(hex(e)[2:].encode())

pro.recvuntil(b"n: ")
pro.sendline(hex(n)[2:].encode())

pro.recvuntil(b"challenge: ")
challenge = int(pro.recvline().strip(), 16)

ciphertext = pow(challenge, d, n)

pro.recvuntil(b"response: ")
# 把整数转成十六进制字符串，切掉 0x，再编码成 bytes 流
pro.sendline(hex(ciphertext)[2:].encode())

pro.recvuntil(b"secret ciphertext (b64): ")
b = b64d(pro.recvline().strip())

flag = int.from_bytes(b, "little")

print(pow(flag, d, n).to_bytes(256, "little"))

pro.interactive()

RSA Signatures

Signing Oracle

同态乘法特性 (Homomorphic Multiplication)。在数学上，两个消息的签名相乘，等于它们乘积的签名：

Sig(m1) × Sig(m2) ≡ Sig(m1 × m2) (mod  n)

b"flag" 的小端序整数值是 1734437990，这是一个偶数。我们将它除以 2：

  • m1 = 2 （对应字节 b"\x02"）
  • m2 = 1734437990/2 = 867218995 （对应字节 b"\xb3\xea\xb0\x33"）

这两个数字的字节流中都不包含 b"flag"，可以完美 Bypass dispatcher 的过滤机制。让它们各自被签名，然后把签名相乘，就能生成真正 1734437990 的签名！

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
# worker
#!/usr/bin/exec-suid -- /usr/bin/python3 -I

import sys

from base64 import b64decode

n = int(open("/challenge/key-n").read(), 16)
e = int(open("/challenge/key-e").read(), 16)

if len(sys.argv) < 2:
    print(f"Usage: {sys.argv[0]} [signature-b64]")
    sys.exit(1)

signature = b64decode(sys.argv[1])
c = int.from_bytes(signature, "little")
assert c < n, "Message too big!"
command = pow(c, e, n).to_bytes(256, "little").rstrip(b"\x00")

print(f"Received signed command: {command}")
if command == b"flag":
    print(open("/flag").read())

# dispatcher
#!/usr/bin/exec-suid -- /usr/bin/python3 -I

import sys

from base64 import b64encode, b64decode

n = int(open("/challenge/key-n").read(), 16)
d = int(open("/challenge/key-d").read(), 16)

if len(sys.argv) < 2:
    print(f"Usage: {sys.argv[0]} [command-b64]")
    sys.exit(1)

command = b64decode(sys.argv[1].strip("\0"))

if b"flag" in command:
    print(f"Command contains 'flag'")
    sys.exit(1)

signature = pow(int.from_bytes(command, "little"), d, n).to_bytes(256, "little")
print(f"Signed command (b64): {b64encode(signature).decode()}")
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
from pwn import *
from pwn import b64d, b64e, log, process

log.info("START")

n = int(open("/challenge/key-n").read(), 16)
e = int(open("/challenge/key-e").read(), 16)

# The target integer representation of b"flag" (little endian)
# 0x67616c66 = 1734437990
target_int = int.from_bytes(b"flag", "little")

# Factor the integer into two parts to bypass the "flag" substring filter
m1 = 2
m2 = target_int // 2

# Convert factors back to bytes
command1 = m1.to_bytes(1, "little")
command2 = m2.to_bytes(4, "little")

c1 = b64e(command1).encode()
c2 = b64e(command2).encode()

# Fetch signature 1
p1 = process(["/challenge/dispatcher", c1])
p1.recvuntil(b"Signed command (b64): ")
signature1 = int.from_bytes(b64d(p1.recvline().strip()), "little")
p1.close()

# Fetch signature 2
p2 = process(["/challenge/dispatcher", c2])
p2.recvuntil(b"Signed command (b64): ")
signature2 = int.from_bytes(b64d(p2.recvline().strip()), "little")
p2.close()

# Homomorphic Multiplication to forge the final signature
signature = pow(signature1 * signature2, 1, n).to_bytes(256, "little")

# Profit
p3 = process(["/challenge/worker", b64e(signature)])
p3.interactive()

cryptographic hashes

sha1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# challenge
#!/usr/bin/exec-suid -- /usr/bin/python3 -I

flag = open("/flag").read()
prefix_length = 6
flag_hash = hashlib.sha256(flag.encode("latin")).hexdigest()
print(f"{flag_hash[:prefix_length]=}")

collision = bytes.fromhex(input("Colliding input? ").strip())
collision_hash = hashlib.sha256(collision).hexdigest()
print(f"{collision_hash[:prefix_length]=}")
if collision_hash[:prefix_length] == flag_hash[:prefix_length]:
    print("Collided!")
    print(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
import hashlib

from pwn import *
from pwn import log, process

log.info("START")

p = process(["/challenge/run"], stdin=process.PTY, stdout=process.PTY)

p.recvuntil(b"flag_hash[:prefix_length]=")
collision = p.recvline().strip().replace(b"'", b"").decode()

prefix_length = 6
count = 0

while True:
    flag = str(count).encode()
    flag_hash = hashlib.sha256(flag).hexdigest()

    if flag_hash[:prefix_length] == collision:
        break

    count += 1
    if count % 1000000 == 0:
        log.info(f"Tried {count} combinations...")


p.sendlineafter(b"Colliding input? ", flag.hex().encode())
p.interactive()

sha2

.config -> 10

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def level10():
    """
    In this challenge you will hash data with a Secure Hash Algorithm (SHA256).
    You will compute a small proof-of-work.
    Your goal is to find response data, which when appended to the challenge data and hashed, begins with 2 null-bytes.
    """
    difficulty = 2

    challenge = get_random_bytes(32)
    show_b64("challenge", challenge)

    response = input_b64("response")
    if SHA256Hash(challenge + response).digest()[:difficulty] == (b'\0' * difficulty):
        show("flag", flag.decode())
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
import itertools

from Crypto.Hash.SHA256 import SHA256Hash
from pwn import *
from pwn import b64d, b64e, log, process

log.info("START")

p = process(["/challenge/run"], stdin=process.PTY, stdout=process.PTY)

difficulty = 2

p.recvuntil(b"challenge (b64): ")
challenge = b64d(p.recvline().strip())

for count in itertools.count():
    if SHA256Hash(challenge + count.to_bytes(256, "big")).digest()[:difficulty] == (
        b"\0" * difficulty
    ):
        break

    if count % 1000000 == 0:
        log.info(f"Tried {count} combinations...")

p.recvuntil(b"response (b64): ")
p.sendline(b64e(count.to_bytes(256, "big")))

p.interactive()

trust

TLS1

.config -> 13

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
def level13():
    """
    In this challenge you will work with public key certificates.
    You will be provided with a self-signed root certificate.
    You will also be provided with the root private key, and must use that to sign a user certificate.
    """
    root_key = RSA.generate(2048)

    show_hex("root key d", root_key.d)

    root_certificate = {
        "name": "root",
        "key": {
            "e": root_key.e,
            "n": root_key.n,
        },
        "signer": "root",
    }

    root_trusted_certificates = {
        "root": root_certificate,
    }

    root_certificate_data = json.dumps(root_certificate).encode()
    root_certificate_hash = SHA256Hash(root_certificate_data).digest()
    root_certificate_signature = pow(
        int.from_bytes(root_certificate_hash, "little"),
        root_key.d,
        root_key.n
    ).to_bytes(256, "little")

    show_b64("root certificate", root_certificate_data)
    show_b64("root certificate signature", root_certificate_signature)

    user_certificate_data = input_b64("user certificate")
    user_certificate_signature = input_b64("user certificate signature")

    try:
        user_certificate = json.loads(user_certificate_data)
    except json.JSONDecodeError:
        print("Invalid user certificate", file=sys.stderr)
        exit(1)

    user_name = user_certificate.get("name")
    if user_name in root_trusted_certificates:
        print(f"Invalid user certificate name: `{user_name}`", file=sys.stderr)
        exit(1)

    user_key = user_certificate.get("key", {})
    if not (isinstance(user_key.get("e"), int) and isinstance(user_key.get("n"), int)):
        print(f"Invalid user certificate key: `{user_key}`", file=sys.stderr)
        exit(1)

    if not (user_key["e"] > 2):
        print("Invalid user certificate key e value (e > 2)", file=sys.stderr)
        exit(1)

    if not (2**512 < user_key["n"] < 2**1024):
        print("Invalid user certificate key n value (2**512 < n < 2**1024)", file=sys.stderr)
        exit(1)

    user_signer = user_certificate.get("signer")
    if user_signer not in root_trusted_certificates:
        print(f"Untrusted user certificate signer: `{user_signer}`", file=sys.stderr)
        exit(1)

    user_signer_key = root_trusted_certificates[user_signer]["key"]
    user_certificate_hash = SHA256Hash(user_certificate_data).digest()
    user_certificate_check = pow(
        int.from_bytes(user_certificate_signature, "little"),
        user_signer_key["e"],
        user_signer_key["n"]
    ).to_bytes(256, "little")[:len(user_certificate_hash)]

    if user_certificate_check != user_certificate_hash:
        print("Untrusted user certificate: invalid signature", file=sys.stderr)
        exit(1)

    ciphertext = pow(int.from_bytes(flag, "little"), user_key["e"], user_key["n"]).to_bytes(256, "little")
    show_b64("secret ciphertext", ciphertext)
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
import json

from Crypto.Hash.SHA256 import SHA256Hash
from Crypto.PublicKey import RSA
from pwn import *
from pwn import b64d, b64e, log, process

user_key = RSA.generate(1024)

p = process(["/challenge/run"], stdin=process.PTY, stdout=process.PTY)

p.recvuntil(b"root key d: ")
d = int(p.recvline().strip(), 16)

p.recvuntil(b"root certificate (b64): ")
cert = b64d(p.recvline().strip())

p.recvuntil(b"root certificate signature (b64): ")
cert_sig = b64d(p.recvline().strip())


root_cert_dict = json.loads(cert)
root_n = root_cert_dict["key"]["n"]

user_cert_dict = {
    "name": "user",
    "key": {
        "e": user_key.e,
        "n": user_key.n,
    },
    "signer": "root",
}

user_cert_data = json.dumps(user_cert_dict).encode()
user_cert_hash = SHA256Hash(user_cert_data).digest()

user_cert_signature = pow(int.from_bytes(user_cert_hash, "little"), d, root_n).to_bytes(
    256, "little"
)

p.recvuntil(b"user certificate (b64): ")
p.sendline(b64e(user_cert_data))

p.recvuntil(b"user certificate signature (b64): ")
p.sendline(b64e(user_cert_signature).encode())

p.recvuntil(b"secret ciphertext (b64): ")
ciphertext = b64d(p.recvline().strip())

flag_int = pow(int.from_bytes(ciphertext, "little"), user_key.d, user_key.n)

flag = flag_int.to_bytes(256, "little").replace(b"\x00", b"")
log.success(f"Flag recovered: {flag.decode('utf-8')}")

p.interactive()

TLS2

.config -> 14

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
def level14():
    """
    In this challenge you will perform a simplified Transport Layer Security (TLS) handshake, acting as the server.
    You will be provided with Diffie-Hellman parameters, a self-signed root certificate, and the root private key.
    The client will request to establish a secure channel with a particular name, and initiate a Diffie-Hellman key exchange.
    The server must complete the key exchange, and derive an AES-128 key from the exchanged secret.
    Then, using the encrypted channel, the server must supply the requested user certificate, signed by root.
    Finally, using the encrypted channel, the server must sign the handshake to prove ownership of the private user key.
    """
    # 2048-bit MODP Group from RFC3526
    p = int.from_bytes(bytes.fromhex(
        "FFFFFFFF FFFFFFFF C90FDAA2 2168C234 C4C6628B 80DC1CD1 "
        "29024E08 8A67CC74 020BBEA6 3B139B22 514A0879 8E3404DD "
        "EF9519B3 CD3A431B 302B0A6D F25F1437 4FE1356D 6D51C245 "
        "E485B576 625E7EC6 F44C42E9 A637ED6B 0BFF5CB6 F406B7ED "
        "EE386BFB 5A899FA5 AE9F2411 7C4B1FE6 49286651 ECE45B3D "
        "C2007CB8 A163BF05 98DA4836 1C55D39A 69163FA8 FD24CF5F "
        "83655D23 DCA3AD96 1C62F356 208552BB 9ED52907 7096966D "
        "670C354E 4ABC9804 F1746C08 CA18217C 32905E46 2E36CE3B "
        "E39E772C 180E8603 9B2783A2 EC07A28F B5C55DF0 6F4C52C9 "
        "DE2BCBF6 95581718 3995497C EA956AE5 15D22618 98FA0510 "
        "15728E5A 8AACAA68 FFFFFFFF FFFFFFFF"
    ), "big")
    g = 2

    show_hex("p", p)
    show_hex("g", g)

    root_key = RSA.generate(2048)

    show_hex("root key d", root_key.d)

    root_certificate = {
        "name": "root",
        "key": {
            "e": root_key.e,
            "n": root_key.n,
        },
        "signer": "root",
    }

    root_trusted_certificates = {
        "root": root_certificate,
    }

    root_certificate_data = json.dumps(root_certificate).encode()
    root_certificate_hash = SHA256Hash(root_certificate_data).digest()
    root_certificate_signature = pow(
        int.from_bytes(root_certificate_hash, "little"),
        root_key.d,
        root_key.n
    ).to_bytes(256, "little")

    show_b64("root certificate", root_certificate_data)
    show_b64("root certificate signature", root_certificate_signature)

    name = ''.join(random.choices(string.ascii_lowercase, k=16))
    show("name", name)

    a = getrandbits(2048)
    A = pow(g, a, p)
    show_hex("A", A)

    B = input_hex("B")
    if not (B > 2**1024):
        print("Invalid B value (B <= 2**1024)", file=sys.stderr)
        exit(1)

    s = pow(B, a, p)
    key = SHA256Hash(s.to_bytes(256, "little")).digest()[:16]
    cipher_encrypt = AES.new(key=key, mode=AES.MODE_CBC, iv=b"\0"*16)
    cipher_decrypt = AES.new(key=key, mode=AES.MODE_CBC, iv=b"\0"*16)

    def decrypt_input_b64(name):
        data = input_b64(name)
        try:
            return unpad(cipher_decrypt.decrypt(data), cipher_decrypt.block_size)
        except ValueError as e:
            print(f"{name}: {e}", file=sys.stderr)
            exit(1)

    user_certificate_data = decrypt_input_b64("user certificate")
    user_certificate_signature = decrypt_input_b64("user certificate signature")
    user_signature = decrypt_input_b64("user signature")

    try:
        user_certificate = json.loads(user_certificate_data)
    except json.JSONDecodeError:
        print("Invalid user certificate", file=sys.stderr)
        exit(1)

    user_name = user_certificate.get("name")
    if user_name != name:
        print(f"Invalid user certificate name: `{user_name}`", file=sys.stderr)
        exit(1)

    user_key = user_certificate.get("key", {})
    if not (isinstance(user_key.get("e"), int) and isinstance(user_key.get("n"), int)):
        print(f"Invalid user certificate key: `{user_key}`", file=sys.stderr)
        exit(1)

    if not (user_key["e"] > 2):
        print("Invalid user certificate key e value (e > 2)", file=sys.stderr)
        exit(1)

    if not (2**512 < user_key["n"] < 2**1024):
        print("Invalid user certificate key n value (2**512 < n < 2**1024)", file=sys.stderr)
        exit(1)

    user_signer = user_certificate.get("signer")
    if user_signer not in root_trusted_certificates:
        print(f"Untrusted user certificate signer: `{user_signer}`", file=sys.stderr)
        exit(1)

    user_signer_key = root_trusted_certificates[user_signer]["key"]
    user_certificate_hash = SHA256Hash(user_certificate_data).digest()
    user_certificate_check = pow(
        int.from_bytes(user_certificate_signature, "little"),
        user_signer_key["e"],
        user_signer_key["n"]
    ).to_bytes(256, "little")[:len(user_certificate_hash)]

    if user_certificate_check != user_certificate_hash:
        print("Untrusted user certificate: invalid signature", file=sys.stderr)
        exit(1)

    user_signature_data = (
        name.encode().ljust(256, b"\0") +
        A.to_bytes(256, "little") +
        B.to_bytes(256, "little")
    )
    user_signature_hash = SHA256Hash(user_signature_data).digest()
    user_signature_check = pow(
        int.from_bytes(user_signature, "little"),
        user_key["e"],
        user_key["n"]
    ).to_bytes(256, "little")[:len(user_signature_hash)]

    if user_signature_check != user_signature_hash:
        print("Untrusted user: invalid signature", file=sys.stderr)
        exit(1)

    ciphertext = cipher_encrypt.encrypt(pad(flag, cipher_encrypt.block_size))
    show_b64("secret ciphertext", ciphertext)
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
import json
import random

from Crypto.Cipher import AES
from Crypto.Hash import SHA256
from Crypto.PublicKey import RSA
from Crypto.Util.Padding import pad, unpad
from pwn import *
from pwn import b64d, b64e, log, process

p = process(["/challenge/run"])

log.info("START")

# 1. 提取 DH 参数和 Root 信息
p.recvuntil(b"p: ")
dh_p = int(p.recvline().strip(), 16)
p.recvuntil(b"g: ")
dh_g = int(p.recvline().strip(), 16)

p.recvuntil(b"root key d: ")
root_d = int(p.recvline().strip(), 16)

p.recvuntil(b"root certificate (b64): ")
root_cert_b64 = p.recvline().strip()
root_cert = json.loads(b64d(root_cert_b64).decode())
root_n = root_cert["key"]["n"]

# 跳过 root cert signature 输出
p.recvuntil(b"root certificate signature (b64): ")
p.recvline()

# 2. 获取 Client 信息
p.recvuntil(b"name: ")
client_name = p.recvline().strip().decode()
log.info(f"Target connection name: {client_name}")

p.recvuntil(b"A: ")
client_A = int(p.recvline().strip(), 16)

# 3. Diffie-Hellman Key Exchange
log.info("Initiating DH Key Exchange...")
b_priv = random.getrandbits(2048)
server_B = pow(dh_g, b_priv, dh_p)

# 发送我们的 Public Key B
p.recvuntil(b"B: ")
p.sendline(hex(server_B)[2:].encode())

# 计算 Shared Secret 并派生 AES Key
shared_secret = pow(client_A, b_priv, dh_p)
aes_key = SHA256.new(shared_secret.to_bytes(256, "little")).digest()[:16]

# 初始化 AES-CBC Cipher (Encryptor)
cipher_encrypt = AES.new(key=aes_key, mode=AES.MODE_CBC, iv=b"\0" * 16)


def encrypt_and_b64(data: bytes) -> bytes:
    padded_data = pad(data, 16)
    encrypted = cipher_encrypt.encrypt(padded_data)
    return b64e(encrypted).encode()


# 4. 伪造 User Certificate
log.info("Forging user certificate and signatures...")
user_key = RSA.generate(1024)

user_cert_dict = {
    "name": client_name,  # 必须匹配 Client 请求的名字
    "key": {
        "e": user_key.e,
        "n": user_key.n,
    },
    "signer": "root",
}

user_cert_data = json.dumps(user_cert_dict).encode()
user_cert_hash = SHA256.new(user_cert_data).digest()

# 用泄漏的 root 私钥签名 User Cert
user_cert_sig = pow(int.from_bytes(user_cert_hash, "little"), root_d, root_n).to_bytes(
    256, "little"
)

# 5. 生成 User Handshake Signature
signature_payload = (
    client_name.encode().ljust(256, b"\0")
    + client_A.to_bytes(256, "little")
    + server_B.to_bytes(256, "little")
)
user_sig_hash = SHA256.new(signature_payload).digest()

# 用我们刚才生成的 user 私钥签名 handshake payload
user_signature = pow(
    int.from_bytes(user_sig_hash, "little"), user_key.d, user_key.n
).to_bytes(256, "little")

# 6. 发送加密的握手数据
log.info("Sending encrypted payload via secure channel...")
p.recvuntil(b"user certificate (b64): ")
p.sendline(encrypt_and_b64(user_cert_data))

p.recvuntil(b"user certificate signature (b64): ")
p.sendline(encrypt_and_b64(user_cert_sig))

p.recvuntil(b"user signature (b64): ")
p.sendline(encrypt_and_b64(user_signature))

# 7. 解密 Flag
p.recvuntil(b"secret ciphertext (b64): ")
encrypted_flag = b64d(p.recvline().strip())

# 初始化一个新的 AES Cipher 用于 Decrypt (因为 AES.CBC 是有状态的，或者用同一个重置 IV，但新开一个更稳)
cipher_decrypt = AES.new(key=aes_key, mode=AES.MODE_CBC, iv=b"\0" * 16)
flag = unpad(cipher_decrypt.decrypt(encrypted_flag), 16).decode()

log.success(f"{flag}")