CPCTF 2024 writeup

It's been a while since I participated in CTF. People who were satisfied after solving crypto problems of a certain level of difficulty, and when they used to hold CTF, they thought, “This person always solves problems in a specific genre and goes home.'' I wondered if this was how he felt.

The problems I worked on were interesting and I had fun solving them.

• (Crypto) AAAA
• (Crypto) CES

(Crypto) AAAA

OpenSSH format with almost all maskedRSAofsecret keyYou can show it to me.I only know part of the keyBASE64butTOKYO+INSTITUTE+OF+TECHNOLOGY+DIGITAL+CREATORS+CLUB+TRAPAAAA Just that it includes.

But besides that, the public key, the ciphertext, and You can receive

RSAof for There is a relationship, and an appropriate integerUsingwritten on both sidesdivided by, it is givenis almostYou can see that it matches.

In this problem settingis large and almostConsidering that it is about the size of

aboutIf you takeThe formula is*1the unknown isOnly withIt should be about half the size of , so this remainderpolynomialIf we find the small root ofis found.If you understandis required, so the rest isAll you have to do is find the ciphertext and decrypt it.

The string given in the problem isofbase64It seemed like the result

from base64 import b64decode, b64encode

e = 506184338...
n = 12339326...
k = 6649705358687...

PR.<x> = PolynomialRing(Zmod(e))
f = 1 + k*n - k*x + k
f = f.monic()

s = int(f.small_roots(X=floor(3 * n**0.5), beta=0.5)(0))
phi = n - s + 1

d = int(pow(e, -1, phi))
c = 91909831...

m = pow(c, d, n)
print(bytes.fromhex(hex(m)(2:)))

(Crypto) CES

You can connect to a server that allows you to do any of the following only twice in total:

1. CES- any plaintextCBCencrypt with
2. CES-FlagCBCencrypt with

CES is a block cipher modified from AES, and is the same as the original AES implementation except that the subbytes implementation is as follows.

def concat(a, b):
    tmp = int("{:064b}".format(a) + "{:064b}".format(b), 2)
    tmp_bin_list = (int(n) for n in bin(tmp)(2:))
    irreducible_poly = (1, 0, 0, 0, 1, 1, 0, 1, 1)
    res = np.polydiv(tmp_bin_list, irreducible_poly)(1)
    res = list(map(int, res))
    res = (x % 2 for x in res)
    res = "".join(map(str, res))
    res = int(res, 2)
    return res

def sub_bytes(s, round_key):
    for i, line in enumerate(s):
        for j, x in enumerate(line):
            k = bytes_to_long(matrix2bytes(round_key))
            res = concat(k, s(i)(j))
            assert concat(k, res) == s(i)(j)
            s(i)(j) = res

    return s

thisconcat, subbytes I didn't know how it was implemented, butassert When I looked at the conditions, I thought, “This implementation of subbytes is a linear conversion.''

Among the various steps of AESnon-linearSince the only conversion is subbytes, if this implementation becomes linear, the encryption by CES will be a linear conversion.That is, plaintextthe keyWhen encrypted withEach bit ofandIt can be expressed as XOR of some bits of .The method of adding keys does not depend on the plaintext, so different plaintextthe same keyencrypted withaboutIt should be.

When I experimented with this, that's exactly what happened, so I took advantage of the fact that the same key is used in 1 and 2 in the server implementation, and created an appropriate plaintext ciphertext created by 1 from the encrypted plaintext obtained in 2. I wrote code to decrypt using

from ptrlib import Socket, chunks, xor
import ast
from problem import bytes2matrix, matrix2bytes, N_ROUNDS, inv_shift_rows, inv_mix_columns

def my_decrypt(ciphertext):
    state = bytes2matrix(ciphertext)

    for i in range(N_ROUNDS - 1, -1, -1):
        inv_shift_rows(state)
        if i > 0:
            inv_mix_columns(state)

    plaintext = matrix2bytes(state)
    return plaintext


sock = Socket("ces.web.cpctf.space 30008")
sock.sendlineafter("option: ", "2")
f_enc = ast.literal_eval(sock.recvlineafter("flag: ").decode()) 
iv = ast.literal_eval(sock.recvlineafter("iv: ").decode())

sock.sendlineafter("option: ", "1")
payload = "A" * len(f_enc)
sock.sendlineafter("encrypt: ", payload)
enc = ast.literal_eval(sock.recvlineafter("message: ").decode()) 
iv2 = ast.literal_eval(sock.recvlineafter("iv: ").decode())

flag = b""

for c1, c2 in zip(chunks(f_enc, 16), chunks(enc, 16)):
    c_wo_k = my_decrypt(xor(c1, c2))
    

    flag_i = xor(xor(c_wo_k, xor(b"A" * 16, iv2)), iv)
    flag += flag_i
    print(flag)

    iv = c1
    iv2 = c2

AES has been modified to look like this, so at first glance it looks like a difficult problem, but I think it was a good problem because the difficulty level was adjusted by subtly expressing the nature with assert.

*1:Let s = p + q