BlockCTF 2024 Retrospective

I still participate in CTFs about once monthly, keeps my math skills sharp considering the only category I can ever contribute to reliably is crypto (since I'm the only player on the team who likes math, apparently). Recently we participated in Block CTF and I cleared all three crypto challenges within the first ~14 hours. Figured I would write them up for posterity.

I'd like to get back into doing writeups more frequently, because its proven that explaining a concept helps ensure that you actually understand it, and I'd like to significantly improve my cryptography skills for the more difficult CTFs.

Sizer Cipher (100 pts)

I made my own encryption scheme- check it out! 052c01be88c7f52cbdc3c084c7b1313828034370034dd13778342dff

This is a sourceless crypto, which means it'll be slightly guessy at least until we can figure out what the cipher actually does. It's also reasonable to assume that the provided hex string is the encrypted version of the flag.

A lot of this challenge is guessing and checking until you figure out to some small degree what the encryption is doing. After a while you can realize that the server encrypts in two character blocks, left padding with null bytes to ensure that the length is a multiple of two.

We don't necessarily know the length of the flag, but it's fine since we can just decrypt right to left and either it'll be an even length or it'll be an odd length and we know the first character anyway since all flags are formatted as flag{}.

Each two char block is encrypted by adding a constant value to the block depending on the ending char type (digit, uppercase letter, lowercase letter, or {}) and the value of the starter char.^[1]

The server also has a silent rejection of certain characters. We can determine the set of "allowed" characters by querying every single byte value (there's only 256 anyway) to determine that there are 64 allowed chars:

0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ{}

To decrypt we can build a lookup table that matches each possible two char combination to its encrypted value and then matching the encryptions to the encrypted string. Doing this requires $63 \times 5$ queries to the server of various starting char (63) + end char type (5) combinations. We only need 63 starting chars since no group will ever start with }.

import time
from pwn import *
from Crypto.Util.number import bytes_to_long, long_to_bytes

idcs = []
standard_alph = []
encrypt_alph = []

def is_same_type(c1, c2):
    if c1.isnumeric() and c2.isnumeric(): return True
    if c1.islower() and c2.islower(): return True
    if c1.isupper() and c2.isupper(): return True
    if c1 == c2: return True # handles the braces
    return False

# i = 37
# while i < 127:
#     p = remote('54.85.45.101', 8003)
#     to_send = chr(i)
#     p.sendline(to_send.encode("utf-8"))
#     try:
#         r = p.recv()
#     except EOFError: # try again if this was the case.
#         p.close()
#         continue
#     p.close()
#     i += 1

#     # Not a valid flag char.
#     if r.startswith(b"Invalid"):
#         continue
#     # print(i, to_send, r)

#     idcs.append(i - 1)
#     standard_alph.append(to_send)
#     encrypt_alph.append(r.decode())
#     time.sleep(0.05) # Give the server a little break as a treat.

# diffs = [int(encrypt_alph[i], 16) - idcs[i] for i in range(len(idcs))]
# print(standard_alph)
# print(diffs)

# for i in range(len(diffs)):
#     print(standard_alph[i], encrypt_alph[i], diffs[i])
# Above code determined the standard alphabet and its differences, although we didn't need it in the end.

# Remember that diffs is encrypt - ord(plain), plain = encrypt - diffs
standard_alph = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', '{', '}']
diffs = [4, 4, 4, 4, 4, 4, 4, 4, 4, 4, -39, -39, -39, -39, -39, -39, -39, -39, -39, -39, -39, -39, -39, -39, -39, -39, -39, -39, -39, -39, -39, -39, -39, -39, -39, -39, -97, -97, -97, -97, -97, -97, -97, -97, -97, -97, -97, -97, -97, -97, -97, -97, -97, -97, -97, -97, -97, -97, -97, -97, -97, -97, -61, -62]

double_dict = {}
# Unfortunately have to test ending on "}"
end_chars = ["0", "A", "a", "{", "}"]

diff = 0
# Don't need to go all the way to the end since two char strings will never start with } in the flag
for c1 in standard_alph[:-1]:
    for c2 in end_chars:
        p = remote('54.85.45.101', 8003)
        to_send = c1 + c2
        p.sendline(to_send.encode("utf-8"))
        try:
            r = p.recv()
        except EOFError: # try again if this was the case.
            p.close()
            continue
        p.close()

        # Not a valid flag char.
        if r.startswith(b"Invalid"):
            continue

        val = bytes_to_long(to_send.encode("utf-8"))
        received = int(r.decode(), 16)
        diff = received - val # encrypt - pt

        # Now generate the dict for everything with that starter char and end char combo
        # Since the diff is constant within end char types
        for c3 in standard_alph:
            if not is_same_type(c2, c3): continue
            to_send = c1 + c3
            val = bytes_to_long(to_send.encode("utf-8"))
            double_dict[hex(val + diff)[2:]] = to_send

        time.sleep(0.05) # Give the server a little break as a treat.

ct = "052c01be88c7f52cbdc3c084c7b1313828034370034dd13778342dff"
pt = ""

for i in range(len(ct) - 3, 0, -3):
    pt = double_dict[ct[i:(i + 3)]] + pt
print("f" + pt)

# flag{ImF1ll3dWithSte4kandCann0tD4nc3}

Where's My Key? (150 pts)

The flag server is providing encrypted flags. It looks like there might be a bug in the code and I can't figure out how to decrypt it.

I did this challenge last, because on first glance it looked quite tricky. In reality it was actually very straightforward due to the simple fact that the server doesn't do any sort of input sanitization.

The server implements a very straightforward Elliptic Curve Diffie-Hellman (ECDH) key exchange scheme, using Curve25519.^[2] ECDH is almost identical to normal Diffie-Helman, substituting math over an elliptic curve rather than an integer ring. Briefly for ECDH, suppose we have two cryptologists Andy and Becky. Andy and Becky each generate their private key, $a$ and $b$, which in this case are just integers. In order to safely share their keys, and calculate a shared secret, Andy shares $(a * G)$ to Becky, while Becky shares $(b * G)$ to Andy. The two can then each (independently) calculate the shared secret $(a * b * G)$. $G$ here, in ECDH, refers to the generator point used for the chosen elliptic curve.

The security of ECDH is linked to the difficulty of calculating the "elliptic curve discrete logarithm problem." That is to say, given $(a * G)$ and $G$ it is difficult to impossible to calculate the value of $a$. Thus an interceptor who receives $(a * G)$ and $(b * G)$ cannot calculate the shared secret $(a * b * G)$ from these values.

In this challenge the server accepts your public key $(a * G)$, then calculates its own private and public keys as well as the shared secret. In "standard" ECDH the server is then supposed to share its public key, $(b * G)$ with you, but due to a (intentional) bug in the code it does not, so you have no way of knowing the shared secret... or do you? More on this in a second.

The server then uses the shared secret as the key in an AES encryption in CTR (counter) mode with a random initialization vector (IV). The server then gives you the encrypted flag and the IV, with the assumption that you know the key. The exact mode for the AES encryption here is only relevant as far as we need to know what it is for decryption, given the key.

The problem is then basically solved if you know the shared secret. One approach is to try and reconstruct the shared secret, but the server uses a random private key every time. An alternative method is if you can somehow force the server to have a specific shared secret then you also win. As foreshadowed before the server does not do any input sanitization or validation. Note, then, if you generate your ECDH private key as a string of null bytes, such that $a = 0$ then the shared secret $a * b * G = 0$. Knowing this and the returned IV and ciphertext you can decrypt the flag.

import json

from pwn import *
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes

X25519_KEY_SIZE = 32
# null bytes * anything = null bytes :)
# hence secret will be null bytes
client_pub = bytes(X25519_KEY_SIZE)

p = remote('54.85.45.101', 8001)

to_send = {"client_pub": client_pub.hex()}
p.sendline(json.dumps(to_send).encode())

r = p.recv().decode("utf-8")
d = json.loads(r)
print(d)

iv = bytes.fromhex(d["iv"])
ct = bytes.fromhex(d["ct"])

cipher = Cipher(algorithms.AES(client_pub), modes.CTR(iv))
decryptor = cipher.decryptor()
pt = decryptor.update(ct) + decryptor.finalize()

print(pt)

# flag{0000_wh0_knew_pub_keys_c0uld_be_bad_0000}

Glitch in the Crypt: Exploiting Faulty RSA Decryption (200 pts)

A high-security server, SecureVault Inc., uses RSA encryption to protect sensitive data. The server utilizes a 1024-bit RSA key and employs the CRT optimization during decryption to improve performance. Due to a hardware fault, the server occasionally introduces errors during the decryption process. Specifically, the fault affects the computation of mp = c^{dp} mod p during the CRT step, causing mp to be incorrect, while mq = c^{d_q} mod q remains correct. As an experienced cryptanalyst, you have managed to obtain access to the server's decryption service. Your goal is to exploit the faulty decryption results to recover the prime factors p and q of the RSA modulus n, effectively breaking the encryption scheme and recovering the private key.

The challenge description above essentially outlines exactly how to solve this challenge. The server is a standard RSA decryption oracle that has a 10% chance to introduce a fault into the CRT reconstruction when decrypting RSA.

Section 2.1 of the paper Fault Attacks for CRT Based RSA: New Attacks, New Results, and New Countermeasures outlines the solution to the challenge although with a few mathematical steps skipped that I will outline below.

To decrypt a message in base RSA we calculate

.

The CRT allows us to compute the value mod $n$ by instead computing the decryptions in the subgroups mod $p$ and mod $q$. The math to do this is slightly more involved, first computing the decryption exponents in the subgroups:

As well as the inverse of q in the p group:

Then using the CRT, using notation that matches both Wikipedia and the challenge script:

This is pretty standard CRT, given the modulus of the message in $p$ and $q$ we thus compute the modulus of the message in mod $n = pq$ in the last line. For small messages, this is actually slower than just directly calculating the decryption in mod $n$, but for large messages this is faster or more memory efficient.

A fault attack necessitates a mistake in calculating either $m_1$ or $m_2$, such that we do not correctly calculate the decryption in that subgroup. In this specific challenge the server simulates a fault in calculating $m_1$. A fault in $m_2$, in this notation, would actually be harder to detect and crack, although with respect to the first point the server alerts you that a fault occurred (it would have been perhaps more interesting if it had not).

What happens when $m_1$ is calculated incorrectly? Consider taking the difference of two different decryptions, $A$ and $B$ of the same original ciphertext:

If both decryptions are the same, with no faults, then this value is obviously equal to zero. However, consider that there is a fault in $m_1$ (but not $m_2$):

This value is proportional to $q$! It should be clear then that $GCD(m_A - m_B, N) = q,$^[3] with $p$ following from $p = N / q$. Knowing $p$ and $q$ we can easily reconstruct $d$ and perform the decryption ourself!

from pwn import *
import os
import math
from Crypto.Util.number import bytes_to_long, long_to_bytes

p = remote('54.85.45.101', 8010)

print(p.recvuntil(b"format:\n"))
print("sending")
p.sendline(b"flag") # Want to get how many bytes it is.

r = p.recvline()
ct = int(r.decode().strip().split(" ")[-1][2:], 16)
print(ct)

r = p.recvline()
n_bytes = int(r.decode().split(" ")[-1])
print(n_bytes)


print(p.recvuntil(b"format:\n"))
to_send = os.urandom(n_bytes).hex()
p.sendline(to_send.encode("utf-8"))

r = p.recvline()
print(r.decode().strip().split(" ")[-1][2:])
dc = int(r.decode().strip().split(" ")[-1][2:], 16)

dc_fault = 0
s = p.recvuntil(b"format:\n")

# We will proceed by sending the same string over and over until there is a fault
# We could also get unlucky and there's a fault in the first try so we must account for that
faulted_first = False
if b"Fault" in s:
    faulted_first = True
    print("Faulted first")

# 1/10 chance of faulting means in 20 tries we should for sure fault.
for i in range(20):
    p.sendline(to_send.encode("utf-8"))
    r = p.recvline()
    dc_fault = int(r.decode().strip().split(" ")[-1][2:], 16)

    s = p.recvuntil(b"format:\n")
    if (b"Fault" in s) or (not (b"Fault" in s) and faulted_first):
        break

N = 30392456691103520456566703629789883376981975074658985351907533566054217142999128759248328829870869523368987496991637114688552687369186479700671810414151842146871044878391976165906497019158806633675101
e = 65537

q = math.gcd(dc - dc_fault, N)
print(q)
p = N // q
print(p)
phi = (q - 1) * (p - 1)
d = pow(e, -1, phi)

pt = pow(ct, d, N)
print(q)
print(long_to_bytes(pt))

# flag{cr4ck1ng_RS4_w1th_f4ul7s}

Conclusion

We ended up placing 30th, and for a brief moment I was the MVP with my crypto clear although that was deposed in the last few hours of the challenge. Alas, perhaps next time.