I participated Google CTF 2022 as a member of WreckTheLine. The results were 14th/382.

Here are my write-ups for challs I solved.

Solved

crypto

Maybe Someday

35 solves

chall.py
#!/usr/bin/python3

# Copyright 2022 Google LLC
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#      http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.

from Crypto.Util.number import getPrime as get_prime
import math
import random
import os
import hashlib

# Suppose gcd(p, q) = 1. Find x such that
#   1. 0 <= x < p * q, and
#   2. x = a (mod p), and
#   3. x = b (mod q).
def crt(a, b, p, q):
    return (a*pow(q, -1, p)*q + b*pow(p, -1, q)*p) % (p*q)

def L(x, n):
    return (x-1) // n

class Paillier:
    def __init__(self):
        p = get_prime(1024)
        q = get_prime(1024)

        n = p * q
        λ = (p-1) * (q-1) // math.gcd(p-1, q-1) # lcm(p-1, q-1)
        g = random.randint(0, n-1)
        µ = pow(L(pow(g, λ, n**2), n), -1, n)

        self.n = n
        self.λ = λ
        self.g = g
        self.µ = µ

        self.p = p
        self.q = q

    # https://www.rfc-editor.org/rfc/rfc3447#section-7.2.1
    def pad(self, m):
        padding_size = 2048//8 - 3 - len(m)
        
        if padding_size < 8:
            raise Exception('message too long')

        random_padding = b'\0' * padding_size
        while b'\0' in random_padding:
            random_padding = os.urandom(padding_size)

        return b'\x00\x02' + random_padding + b'\x00' + m

    def unpad(self, m):
        if m[:2] != b'\x00\x02':
            raise Exception('decryption error')

        random_padding, m = m[2:].split(b'\x00', 1)

        if len(random_padding) < 8:
            raise Exception('decryption error')

        return m

    def public_key(self):
        return (self.n, self.g)

    def secret_key(self):
        return (self.λ, self.µ)

    def encrypt(self, m):
        g = self.g
        n = self.n

        m = self.pad(m)
        m = int.from_bytes(m, 'big')

        r = random.randint(0, n-1)
        c = pow(g, m, n**2) * pow(r, n, n**2) % n**2

        return c

    def decrypt(self, c):
        λ = self.λ
        µ = self.µ
        n = self.n

        m = L(pow(c, λ, n**2), n) * µ % n
        m = m.to_bytes(2048//8, 'big')

        return self.unpad(m)

    def fast_decrypt(self, c):
        λ = self.λ
        µ = self.µ
        n = self.n
        p = self.p
        q = self.q

        rp = pow(c, λ, p**2)
        rq = pow(c, λ, q**2)
        r = crt(rp, rq, p**2, q**2)
        m = L(r, n) * µ % n
        m = m.to_bytes(2048//8, 'big')

        return self.unpad(m)

def challenge(p):
    secret = os.urandom(2)
    secret = hashlib.sha512(secret).hexdigest().encode()

    c0 = p.encrypt(secret)
    print(f'{c0 = }')

    # # The secret has 16 bits of entropy.
    # # Hence 16 oracle calls should be sufficient, isn't it?
    # for _ in range(16):
    #     c = int(input())
    #     try:
    #         p.decrypt(c)
    #         print('😀')
    #     except:
    #         print('😡')

    # I decided to make it non-interactive to make this harder.
    # Good news: I'll give you 25% more oracle calls to compensate, anyways.
    cs = [int(input()) for _ in range(20)]
    for c in cs:
        try:
            p.fast_decrypt(c)
            print('😀')
        except:
            print('😡')

    guess = input().encode()

    if guess != secret: raise Exception('incorrect guess!')

def main():
    with open('/flag.txt', 'r') as f:
      flag = f.read()

    p = Paillier()
    n, g = p.public_key()
    print(f'{n = }')
    print(f'{g = }')

    try:
        # Once is happenstance. Twice is coincidence...
        # Sixteen times is a recovery of the pseudorandom number generator.
        for _ in range(16):
            challenge(p)
            print('💡')
        print(f'🏁 {flag}')
    except:
        print('👋')

if __name__ == '__main__':
    main()

This chall is related to Paillier cryptosystem. We have an oracle which tells whether fast_decrypt succeeds or not.

Paillier cryptosystem has homomorphic property (See wikipedia). In other words, $\mathrm{Enc}(x) \mathrm{Enc}(y) = \mathrm{Enc}(x + y)$. Therefore we can control the decryption of $c_0 = \mathrm{Enc}(s)$ (where $s$ is secret) by multiplying $\mathrm{Enc}(y)$. $c_0 \mathrm{Enc}(y)$ is decrypted to $s + y$.

Let's consider when fast_decrypt fails. In fast_decrypt there is unpad process.

    def unpad(self, m):
        if m[:2] != b'\x00\x02':
            raise Exception('decryption error')

        random_padding, m = m[2:].split(b'\x00', 1)

        if len(random_padding) < 8:
            raise Exception('decryption error')

        return m

If m[2:] has no \x00, .split fails and raise error.

This error can be caused on purpose by using the homomorphic property. When only 128-th byte from LSB are modified (originally this is \x00), unpad will fail because of a way mentioned above. On top of that, if we add $x$ to i-th byte ($0 \le i < 128$) and unpad succeeds this time, i-th byte of secret should be $256 - x$. We can leak secret in this way.

If we can interactively ask an oracle, we can find secret one by one by bisection method. It's because the number of candidates is 65536 and we can reduce half of candidates in each ask. However in this challenge we have to ask batch. To solve under this condition, assume that each byte of hash is randomly generated on uniform distribution (and hopefully it's true). If we ask to decrypt $c_0 \mathrm{Enc}(x)$ where $x$ is 129 bytes, starts with b"\x01" and contains 11 bytes([256 - 0x30]), the decryption succeeds when any of secret[idx] is b"\x30" (= 0) where idx is the index that satisfies x[1+idx] == bytes([256 - 0x30]). This happens $1 - (15/16)^{11} \simeq 50.8\%$ (11 is selected because this probability is the nearest to 50%). Therefore we can reduce around half candidates from this result.

Using this type of payload 20 times, we can find secret (sometimes fail though) and get flag!

solve.py
import hashlib
import random

from Crypto.Util.number import long_to_bytes
from pwn import remote
from tqdm import tqdm


def pad(m):
    padding_size = 2048//8 - 3 - len(m)
    if padding_size < 8:
        raise Exception('message too long')
    random_padding = b'\0' * padding_size
    while b'\0' in random_padding:
        random_padding = os.urandom(padding_size)
    return b'\x00\x02' + random_padding + b'\x00' + m


def encrypt(m, padding=True):
    if padding:
        m = pad(m)
    m = int.from_bytes(m, 'big')
    r = random.randint(0, n-1)
    c = int(pow(g, m, n**2) * pow(r, n, n**2) % n**2)
    return c


cands = []
for i in range(256**2):
    tmp = long_to_bytes(i, 2)
    tmp = hashlib.sha512(tmp).hexdigest().encode()
    cands.append(tmp)

ts = sorted([256 - i for i in b"0123456789abcdef"])
s = b"fedcba9876543210"

while True:
    io = remote("maybe-someday.2022.ctfcompetition.com", 1337)
    _ = io.recvline()
    _ = io.recvuntil(b"n = ")
    n = int(io.recvline())
    _ = io.recvuntil(b"g = ")
    g = int(io.recvline())
    finish = True
    for _ in tqdm(range(16)):
        _ = io.recvuntil(b"c0 = ")
        c0 = int(io.recvline())
        for i in range(10):
            tmp_enc = encrypt(b"\x01" + (long_to_bytes(ts[i]) + b"\x00") * 11 + b"\x00" * 106, padding=False)
            io.sendline(str(int(tmp_enc * c0 % n**2)).encode())
        for i in range(10):
            tmp_enc = encrypt(b"\x01" + (b"\x00" + long_to_bytes(ts[i])) * 11 + b"\x00" * 106, padding=False)
            io.sendline(str(int(tmp_enc * c0 % n**2)).encode())
        valids = []
        for _ in range(20):
            if io.recvline().strip().decode() == "😀":
                valids.append(True)
            else:
                valids.append(False)
        tmp_cands = {cand: True for cand in cands}
        for i in range(10):
            valid = valids[i]
            for cand in cands:
                if cand not in tmp_cands:
                    continue
                if (valid and s[i] in list(cand[0:22:2])) or (not valid and s[i] not in list(cand[0:22:2])):
                    continue
                del tmp_cands[cand]
        for i in range(10):
            valid = valids[10+i]
            for cand in cands:
                if cand not in tmp_cands:
                    continue
                if (valid and s[i] in list(cand[1:22:2])) or (not valid and s[i] not in list(cand[1:22:2])):
                    continue
                del tmp_cands[cand]
        print(len(tmp_cands))
        io.sendline(next(iter(tmp_cands.keys())))
        if io.recvline().strip().decode() == "👋":
            finish = False
            io.close()
            break
    if finish:
        print(io.recvline())
        break
    io.close()

CTF{p4dd1n9_or4cl3_w1th_h0mom0rph1c_pr0p3r7y_c0m6in3d_in7o_a_w31rd_m47h_puzz1e}

Cycling

50 solves

chall.py
#!/usr/bin/python3

# Copyright 2022 Google LLC
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#      http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.

"""
It is well known that any RSA encryption can be undone by just encrypting the
ciphertext over and over again. If the RSA modulus has been chosen badly then
the number of encryptions necessary to undo an encryption is small.
If n = 0x112b00148621 then only 209 encryptions are necessary as the following
example demonstrates:

>>> e = 65537
>>> n = 0x112b00148621
>>> pt = 0xdeadbeef
>>> # Encryption
>>> ct = pow(pt, e, n)
>>> # Decryption via cycling:
>>> pt = ct
>>> for _ in range(209):
>>>   pt = pow(pt, e, n)
>>> # Assert decryption worked:
>>> assert ct == pow(pt, e, n)

However, if the modulus is well chosen then a cycle attack can take much longer.
This property can be used for a timed release of a message. We have confirmed
that it takes a whopping 2^1025-3 encryptions to decrypt the flag. Pack out
your quantum computer and perform 2^1025-3 encryptions to solve this
challenge. Good luck doing this in 48h.
"""

e = 65537
n = 0x99efa9177387907eb3f74dc09a4d7a93abf6ceb7ee102c689ecd0998975cede29f3ca951feb5adfb9282879cc666e22dcafc07d7f89d762b9ad5532042c79060cdb022703d790421a7f6a76a50cceb635ad1b5d78510adf8c6ff9645a1b179e965358e10fe3dd5f82744773360270b6fa62d972d196a810e152f1285e0b8b26f5d54991d0539a13e655d752bd71963f822affc7a03e946cea2c4ef65bf94706f20b79d672e64e8faac45172c4130bfeca9bef71ed8c0c9e2aa0a1d6d47239960f90ef25b337255bac9c452cb019a44115b0437726a9adef10a028f1e1263c97c14a1d7cd58a8994832e764ffbfcc05ec8ed3269bb0569278eea0550548b552b1
ct = 0x339be515121dab503106cd190897382149e032a76a1ca0eec74f2c8c74560b00dffc0ad65ee4df4f47b2c9810d93e8579517692268c821c6724946438a9744a2a95510d529f0e0195a2660abd057d3f6a59df3a1c9a116f76d53900e2a715dfe5525228e832c02fd07b8dac0d488cca269e0dbb74047cf7a5e64a06a443f7d580ee28c5d41d5ede3604825eba31985e96575df2bcc2fefd0c77f2033c04008be9746a0935338434c16d5a68d1338eabdcf0170ac19a27ec832bf0a353934570abd48b1fe31bc9a4bb99428d1fbab726b284aec27522efb9527ddce1106ba6a480c65f9332c5b2a3c727a2cca6d6951b09c7c28ed0474fdc6a945076524877680
# Decryption via cycling:
pt = ct
for _ in range(2**1025 - 3):
  pt = pow(pt, e, n)
# Assert decryption worked:
assert ct == pow(pt, e, n)

# Print flag:
print(pt.to_bytes((pt.bit_length() + 7)//8, 'big').decode())

This chall is quite simple, how $n$ can be factored when we know $h = 2^{1025} - 3$ such that $m^{e^{h+1}} = m \mod n$ in usual RSA.

Assuming that $m^{e^{h+1}} = m \mod n$ for all $m$, $e^{h+1} = 1 \mod \lambda(n)$ where $\lambda(n)$ is a Carmichael function. In this case, $\lambda(n) = \mathrm{lcm}(p - 1, q - 1)$ Since $\mathrm{gcd}(e, \lambda(n)) = 1$ (otherwise $e^x \ne 1 \mod \lambda(n)$ for any $x$), $h+1$ is a multiple of $\lambda(\lambda(n))$.

Let $\lambda(n) = \prod_{i=1}^k p_i^{e_i}$. Then $\lambda(\lambda(n)) = \mathrm{lcm}(\lambda(p_1^{e_1}), \cdots, \lambda(p_k^{e_k})) = \mathrm{lcm}(\mathrm{1\,or\,2\,or\,}2^{e}, p_2^{e_2-1}(p_2 - 1), \cdots, p_k^{e_k-1}(p_k - 1))$.

Also let $\lambda(\lambda(n)) = \prod_{i=1}^k q_i^{f_i}$. Since $h+1$ is a multiple of $\lambda(\lambda(n))$, $q_i$ is one of factor of $h+1$. $h+1$ can be factored by factordb and results are as follows.

h = 2**1025 - 3
primes = [2, 3, 5, 17, 257, 641, 65537,  274177,  2424833, 6700417, 67280421310721, 1238926361552897, 59649589127497217, 5704689200685129054721, 7455602825647884208337395736200454918783366342657, 93461639715357977769163558199606896584051237541638188580280321, 741640062627530801524787141901937474059940781097519023905821316144415759504705008092818711693940737]
assert prod(primes) == h + 1

Note that $f_i = 1$ because of the results above.

Since $\lambda(\lambda(n)) = \prod_{i=1}^k q_i^{f_i} = \mathrm{lcm}(\mathrm{1\,or\,2\,or\,}2^{e_1}, p_2^{e_2-1}(p_2 - 1), \cdots, p_k^{e_k-1}(p_k - 1))$, the following holds true:

• $p_i - 1$ is a multiple of some $q_j$
• If $e_i \ge 2$, $p_i$ equals to one of $q_j$

So I tried to find candidates for $p_i$ from the factor of $h + 1$. Since len(primes) == 17 is relatively small, power set of primes can be checked whether the product of each set is a prime minus 1.

cands = []
for k in tqdm(range(2**len(primes))):
    tmp = 1
    for i in range(len(primes)):
        if k % 2 == 1:
            tmp *= primes[i]
        k //= 2
    tmp += 1
    if is_prime(tmp):
        cands.append(tmp)

# check
for i in tqdm(range(len(cands))):
    tmp_p = cands[i]
    assert is_prime(tmp_p)
    assert (h + 1) % (tmp_p - 1) == 0

There are totally 604 candidates for $p_i$. Considering the case when $e_i \ge 2$, $p_i$ should be one of set(cands) & set(primes). This intersection contains only 2 and 3. Therefore $\lambda(n)$ equals to power of 2 times power of 3 times products of some of cands.

Here let's get back to RSA. We have to find $d$ to decrypt, where $d = e^{-1} \mod \lambda(n)$. Though we don't know $\lambda(n)$, we can know a multiple of $\lambda(n)$ by calculating products of all of cands (and power of 2, 3). Let this product to be $L$. When $ed = 1 \mod L$, also $ed = 1 \mod \lambda(n)$ because $\lambda(n) | L$. Therefore $d = e^{-1} \mod L$ can decrypt the ciphertext!

solve.sage
from Crypto.Util.number import long_to_bytes
from tqdm import tqdm


e = 65537
n = 0x99efa9177387907eb3f74dc09a4d7a93abf6ceb7ee102c689ecd0998975cede29f3ca951feb5adfb9282879cc666e22dcafc07d7f89d762b9ad5532042c79060cdb022703d790421a7f6a76a50cceb635ad1b5d78510adf8c6ff9645a1b179e965358e10fe3dd5f82744773360270b6fa62d972d196a810e152f1285e0b8b26f5d54991d0539a13e655d752bd71963f822affc7a03e946cea2c4ef65bf94706f20b79d672e64e8faac45172c4130bfeca9bef71ed8c0c9e2aa0a1d6d47239960f90ef25b337255bac9c452cb019a44115b0437726a9adef10a028f1e1263c97c14a1d7cd58a8994832e764ffbfcc05ec8ed3269bb0569278eea0550548b552b1
ct = 0x339be515121dab503106cd190897382149e032a76a1ca0eec74f2c8c74560b00dffc0ad65ee4df4f47b2c9810d93e8579517692268c821c6724946438a9744a2a95510d529f0e0195a2660abd057d3f6a59df3a1c9a116f76d53900e2a715dfe5525228e832c02fd07b8dac0d488cca269e0dbb74047cf7a5e64a06a443f7d580ee28c5d41d5ede3604825eba31985e96575df2bcc2fefd0c77f2033c04008be9746a0935338434c16d5a68d1338eabdcf0170ac19a27ec832bf0a353934570abd48b1fe31bc9a4bb99428d1fbab726b284aec27522efb9527ddce1106ba6a480c65f9332c5b2a3c727a2cca6d6951b09c7c28ed0474fdc6a945076524877680
h = 2**1025 - 3

primes = [2, 3, 5, 17, 257, 641, 65537,  274177,  2424833, 6700417, 67280421310721, 1238926361552897, 59649589127497217, 5704689200685129054721, 7455602825647884208337395736200454918783366342657, 93461639715357977769163558199606896584051237541638188580280321, 741640062627530801524787141901937474059940781097519023905821316144415759504705008092818711693940737]
assert prod(primes) == h + 1

cands = []
for k in tqdm(range(2**len(primes))):
    tmp = 1
    for i in range(len(primes)):
        if k % 2 == 1:
            tmp *= primes[i]
        k //= 2
    tmp += 1
    if is_prime(tmp):
        cands.append(tmp)

# check
for i in tqdm(range(len(cands))):
    tmp_p = cands[i]
    assert is_prime(tmp_p)
    assert (h + 1) % (tmp_p - 1) == 0

L = prod(cands)
d = int(pow(e, -1, L))
print(long_to_bytes(int(pow(ct, d, n))))

CTF{Recycling_Is_Great}

misc

MLSteal

106 solves

Since we can't run query.py by the following error, I started to make a docker environment.

Fatal Python error: BLAS wrapper returned with an error
Python runtime state: initialized
RuntimeError: Specified LAPACK function could not be found.

Current thread 0x00007f8eca5c3740 (most recent call first):
  File "query.py", line 24 in <module>

Aborted (core dumped)

In usr/local/lib/python3.8/dist-packages, there are python packages:

numpy  numpy.libs  numpy-1.22.4.dist-info  scipy  scipy.libs  scipy-1.8.1.dist-info

So I ran docker run -d -v $PWD:/work -it python:3.8 bash at ctf directory and then pip3 install numpy==1.22.4 scipy==1.8.1.

First I tried to query the given prefix. It reveals the flag starts with CTF{ as intended.

python3 query.py "Alice Bobson's password"
b"Alice Bobson's password is CTF{ \n\nOn February 22, 1917, the name is one of the most common names in more than 1,700 males i"

I thought that the flag would be revealed when the next of CTF{ was correct, and tried all chars by brute force. But...

python3 my_query.py "Alice Bobson's password is CTF{A"
b"Alice Bobson's password is CTF{A3rd is CTF{m3m0r1z4t10n-1S-4LL-\n\n\nCory Baumont-Baumont-Governor\n\n\n\nHistory.\n\nAt the end of 1981, Too"

I luckily found CTF{m3m0r1z4t10n-1S-4LL-.

I tried some payloads to get the rest, but the following payload worked.

python3 my_query.py "Alice Bobson's password is CTF{m3m0r1z4t10n-1S-4LL-4LL-4LL-4LL-4LL"
b"Alice Bobson's password is CTF{m3m0r1z4t10n-1S-4LL-4LL-4LL-4LL-4LL-y0u-N33D\n\n\n\nThis is a subgenre of state use that is not running for mayor senators. NBA supported b"

It looked like CTF{m3m0r1z4t10n-1S-4LL-y0u-N33D ends with }. I tried to submit and the system said "FLAG CAPTURED".

CTF{m3m0r1z4t10n-1S-4LL-y0u-N33D}

Unsolved

crypto

Custom Protocol

5 solves

server.py
#!/usr/bin/python3.9

# Copyright 2022 Google LLC
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#      http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.

import enum
import gmpy2
import hashlib
import hmac
import msgs_pb2 
import os
import time
import typing

debug = True  # We can set it to False when in production.
flag = open('flag.txt', 'rb').read().strip()

class DataType(enum.Enum):
  RSA_ENC = 1
  RSA_SIG = 2

version = "My crypto protocol v0.0.1"
enc_oid = ('For this encryption oid I am not sure, but I would guess something '
           'in between 1.2.840.113549.2.7 and 1.2.840.113549.1.1.5 plus nonce '
           ':).')
sig_oid = ('For this signing oid I am not sure, but I would guess something '
           'in between 1.2.840.113549.2.7 and 1.2.840.113549.1.1.5 plus nonce '
           ':).')
enc_algorithm = ('For this encryption algorithm I am not sure, but I would '
                 'guess something in between hmacWithSHA1 and '
                 'sha1WithRSAEncryption plus nonce :).')
sig_algorithm = ('For this signing algorithm I am not sure, but I would guess '
                 'something in between hmacWithSHA1 and '
                 'sha1-with-rsa-signature plus nonce :).')

def pad(data_to_pad: bytes, block_size: int) -> bytes:
    #Apply ISO/IEC 7816-4 padding.
    padding_len = block_size - len(data_to_pad) % block_size
    padding = b'\x80' + b'\x00'*(padding_len - 1)
    return data_to_pad + padding

def unpad(padded_data: bytes, block_size: int) -> bytes:
    #Remove ISO/IEC 7816-4 padding.
    pdata_len = len(padded_data)
    padding_len = pdata_len - padded_data.rfind(b'\x80')
    return padded_data[:-padding_len]

def bytes2int(bytes_val: bytes) -> int:
  return int.from_bytes(bytes_val, 'big')

def int2bytes(int_val: int) -> bytes:
  int_val = int(int_val)
  return int_val.to_bytes((int_val.bit_length() + 7) // 8, 'big')


class RSA:

  def __init__(self):
    self.e = 65537
    self.p = gmpy2.next_prime(bytes2int(os.urandom(256)) | 2**2047 | 2**2046)
    self.q = gmpy2.next_prime(bytes2int(os.urandom(256)) | 2**2047 | 2**2046)
    self.dp = gmpy2.invert(self.e, self.p-1)
    self.dq = gmpy2.invert(self.e, self.q-1)
    self.qInv = gmpy2.invert(self.q, self.p)
    self.n = self.p*self.q
    self.bl = self.n.bit_length()//8

  def parse(self, msg: bytes, hmac_key: bytes, data_type: DataType) -> int:
    if data_type == DataType.RSA_ENC:
      data = msgs_pb2.RSAEncryptionData()
      data.plaintext = msg
      data.oid = enc_oid
      data.algorithm_name = enc_algorithm
    elif data_type == DataType.RSA_SIG:
      data = msgs_pb2.RSASignatureData()
      data.oid = sig_oid
      data.algorithm_name = sig_algorithm
    else:
      raise ValueError('Unknown Data Type.')
    data.version = version
    data.hmac_key = hmac_key
    data.nonce = hmac.digest(hmac_key, int2bytes(time.time()), hashlib.sha1)
    data.digest_message = hmac.digest(hmac_key, msg, hashlib.sha1)
    m = bytes2int(pad(data.SerializeToString(), self.bl))
    if not m < self.n:
      raise ValueError('Message is too long.')
    return m

  def unparse(self, m: int,
              data_type: DataType) -> typing.Union[msgs_pb2.RSAEncryptionData,
                                                   msgs_pb2.RSAEncryptionData]:
    if data_type == DataType.RSA_ENC:
      data = msgs_pb2.RSAEncryptionData()
    elif data_type == DataType.RSA_SIG:
      data = msgs_pb2.RSASignatureData()
    else:
      raise ValueError('Unknown Data Type.')
    data.ParseFromString(unpad(int2bytes(m), self.bl))
    return data

  def encrypt(self, msg: bytes, hmac_key: bytes) -> int:
    return pow(self.parse(msg, hmac_key, DataType.RSA_ENC), self.e, self.n)

  def decrypt(self, enc: int) -> bytes:
    mp = pow(enc, self.dp, self.p)
    mq = pow(enc, self.dq, self.q)
    h = self.qInv*(mp - mq) % self.p
    m = mq + h*self.q
    data = self.unparse(m, DataType.RSA_ENC)
    digest_message = hmac.digest(data.hmac_key,
                                 data.plaintext,
                                 hashlib.sha1)
    if digest_message != data.digest_message:
      raise ValueError('Can\'t decrypt. Integrity check failed.')
    return data.plaintext

  def sign(self, msg: bytes, hmac_key: bytes) -> int:
    sp = pow(self.parse(msg, hmac_key, DataType.RSA_SIG), self.dp, self.p)
    sq = pow(self.parse(msg, hmac_key, DataType.RSA_SIG), self.dq, self.q)
    h = self.qInv*(sp - sq) % self.p
    s = sq + h*self.q
    return s

  def verify(self, msg: bytes, sig: int) -> bool:
    m = pow(sig, self.e, self.n)
    data = self.unparse(m, DataType.RSA_SIG)
    digest_message = hmac.digest(data.hmac_key, msg, hashlib.sha1)
    return digest_message == data.digest_message

def menu() -> int:
  print("")
  print("[1] Get Public key")
  print("[2] Get Encrypted flag")
  print("[3] Decrypt flag")
  print("[4] Get signed flag")
  print("[5] Verify signed flag")
  print("[6] Exit")
  op = int(input(">>> "))
  return op
 
def operation_loop(rsa):
  while True:
    op = menu()
    if op == 1:
      print('e =', hex(rsa.e))
      print('n =', hex(rsa.n))
    elif op == 2:
      hmac_key = os.urandom(16)
      enc = rsa.encrypt(flag, hmac_key)
      print('enc =', hex(enc))
      if debug:
        assert rsa.decrypt(enc) == flag
    elif op == 3:
      enc = int(input("enc (hex)? "), 16)
      try:
        res = rsa.decrypt(enc)
      except:
        res = None
      if res == flag:
        print("Flag decrypted with success :-)")
      else:
        print("Something went wrong. Incorrect ciphertext?")
    elif op == 4:
      hmac_key = os.urandom(16)
      sig = rsa.sign(flag, hmac_key)
      print('sig =', hex(sig))
      if debug:
        assert rsa.verify(flag, sig)
    elif op == 5:
      sig = int(input("sig (hex)? "), 16)
      try:
        res = rsa.verify(flag, sig)
      except:
        res = None
      if res:
        print("Signed flag verified with success :-)")
      else:
        print("Something went wrong. Incorrect signature?")
    elif op == 6:
      print("Bye!")
      break

if __name__ == "__main__":
  print("\nWelcome to my Crypto box. Tell me what operation you want.")
  while True:
    rsa = RSA()
    try:
      operation_loop(rsa)
      break
    except:
      pass

We can get a signature of hmac(flag) and encryption of flag. The format is as follows:

# signature
(
    b"\n\x19My crypto protocol v0.0.1\x12\x10"
    + hmac_key
    + b'\x1a\x85\x01For this signing oid I am not sure, but I would guess something in between 1.2.840.113549.2.7 and 1.2.840.113549.1.1.5 plus nonce :)."\x14'
    + nonce
    + b"*\x88\x01For this signing algorithm I am not sure, but I would guess something in between hmacWithSHA1 and sha1-with-rsa-signature plus nonce :).2\x14"
    + digest_message
    + b"\x80"
    + b"\x00" * 147
)

# encryption
(
    b"\n\x19My crypto protocol v0.0.1\x12\x10"
    + hmac_key
    + b'\x1a\x88\x01For this encryption oid I am not sure, but I would guess something in between 1.2.840.113549.2.7 and 1.2.840.113549.1.1.5 plus nonce :)."\x14'
    + nonce
    + b"*\x89\x01For this encryption algorithm I am not sure, but I would guess something in between hmacWithSHA1 and sha1WithRSAEncryption plus nonce :).2\x14"
    + digest_message
    + b":"
    + long_to_bytes(len(flag))
    + flag
    + b"\x80"
    + b"\x00" * (141 - len(flag))
)

I first tried to leak the length of the flag. Since the padding length is 141 - len(flag), we can know its length by checking whether decrypting $256^{-l}\mathrm{enc} \mod n$ is successful or not. If $l$ is larger than 141 - len(flag) + 1, decrypting causes error because of unpad. I found that the length of flag is 68!! ...so what??

At first glance, there appears to be no vulnerability (I thought so for half a day). I tried to find a vulnerability of protobuf, but nothing was found.

When I was looking at the source code very very carefully, I found that it may cause an error in the following part.

  def sign(self, msg: bytes, hmac_key: bytes) -> int:
    sp = pow(self.parse(msg, hmac_key, DataType.RSA_SIG), self.dp, self.p)
    sq = pow(self.parse(msg, hmac_key, DataType.RSA_SIG), self.dq, self.q)
    h = self.qInv*(sp - sq) % self.p
    s = sq + h*self.q
    return s

In self.parse, there is a int(time.time()). So if the timing is bad, two self.parse(msg, hmac_key, DataType.RSA_SIG) may be different! We can get this signature by the following script.

from Crypto.Util.number import long_to_bytes
from pwn import remote, context

context.log_level = "DEBUG"


io = remote("custom-protocol.2022.ctfcompetition.com", 1337)

io.sendlineafter(b">>> ", b"1")
_ = io.recvuntil(b"e = ")
e = int(io.recvline(), 16)
_ = io.recvuntil(b"n = ")
n = int(io.recvline(), 16)
io.sendlineafter(b">>> ", b"2")
_ = io.recvuntil(b"enc = ")
enc = int(io.recvline(), 16)

while True:
    io.sendlineafter(b">>> ", b"4")
    _ = io.recvuntil(b"sig = ")
    sig = int(io.recvline(), 16)
    if b"My crypto" not in long_to_bytes(int(pow(sig, e, n))):
        break

# example for reproducibility
e = 65537
n = 0xd58b2a4eacc7d68eb0d7616fafdd33daac8dc88a4c887954f5c75842bcd6882760928d38acf66540b1be305ec53369c3310086f0a94b28341a37313a14c4672ff77ed1cf64b2ad1f91273281c2184c9ceffc527d63584875ad1aa2702b835a533c4005d62862a1d4802d7295cb9bc3c7417442dc7209a9817992da79a0c4404bee3fa8fe4311b979250d8cd7f61ad9a087cc0b213cc13ddc418cd12822cd84c9da5740f7667ac25fc88e0885f7f6a500b56680ab38b384e8ce302479710cfc946d229c9ca31d0d8972cd2417d57f3f8584f907005cd69b03bf18f2299c20cbc99175fcb6c035c8dd6816024993d60f98a43b114b11c29821e709f8421fbce09ca4232d1331dddc1a45732cccf167b7c8fab105ad196ee97931ab8590ab546b3f25cdfe65610ca7d15e77bcb4135d20878dcfad9474ef55df631b51d69880295d00838afd5f9b56916ece67fa0e0f879f8aee7b919588b96def0c0f7bcabae053898a530705b9f125facf215b2929dc4ae957b0d30a396a7b9adbd79a46c438b083b1351e07da47fac97664340dbe58a841306ecb255314454e73ff39ba02004f36037baf9038cf0b721063f6309e00d4ba777e561ab6d3332d992bc75e582e90b244ab2e87b53cec4cf989165c64e6be8bee2fd09ad0a1983bb93ed68f52b5cc313ee902cb0d18a74e0ae66a72e2aa53c81876199c7ff2826865db358f24d5af
enc = 0x559b0d8f1edf471c4d68a8acecba20b982368380c2136b03ada36d7bdbc25bbe9bb4358525a3d32d943d3b919831c32c1d59f1f8e7e43d3836a775155b387b683f4e56e8d5ae6a480de4ea25f8ae4da40dabd1e1a5e65f0cf009f00e6fa16ff3e108b728ad92d46dde4a34cb84d9154c96c47b52c7fdf4487327b3050d095baca2b02733a089660d7571886d0135f5c829442b6a7785bd492aa87682fc6015df2fc4ed8895e3693e977f7ebb5ec55a228726792143cb5f4cdde87f426a4d6606f9f61d73c0ac815d6809ac3bfc891b0710716db8e0eb6f8baa4994432d8206723c35e611e6177e924f3d8fdd2241f158f990c5555d82148192530628dc26d4cacf09ddf09f75e7f48e4845a53435b75eac072ff9a4c72dbb554ab40847cc80d5d2fdc5a44a7e9cb3d71e3a34bc38f87aae2b8944e1802f53c9fbe81ced30e6cb7ea553927a9b6a5a43265cabcd599170e172736614083afd7eb7dd944cae1a269e672fb168d374e85f3ee0494fec03e85f512b18b05cfb6f3bd2d4e96b7cdcec6e17736118f1575627b6174f6c4651fd5235bfa10e24d327ca985701f5789b7781643778ab3a0a9dc9f54cd3f95d6897a8c3455bbe3aeb96502c9e0a16b6ed6abd36d893162ab63a664a034f59102e03c0d34b2341a7c92eb4dccfcee56180d54150c7c632b2ca0cc21a69168e7171ce441b8e527bdbeacaee0290e28c871a2e
sig = 0xa696f726e4f1c83607ff5bd81cdb9073422e4cb1fc47822a30167e832a6365608b91f046a39234e687b49991ae40a996cc9ab96e99caa4f4569534b24889406341cb2e52b2d433b55b14832b922ea17c19bbd014288a6aa6f8ae797a3713523060d4bf08a2bb6845eb79ee91fd408cccb830af5308e95055f1ffd9220262b22f234f7e4a63303ec94473fad9eb98c240d5a326acd8094d83117c6dcea014501326318847e96dbb67070237afd24451bf7a1fd2b85a1f7f4ffb9792faaf0be6c127364756d2db5848c541f0f505f8aa4e48dd3ec2d8d73804f4e4f87d7ee70994d91d76d515a3238e1490571d9e25419cd174c982e2392b3c58aab8c16fcbe3c8a1bddbc72bd5751103231925508d5a8cab1ba122731a6a7552547c2e36dcdf461fd14de788dbe9439522a38d4f01b93ead32b41fcdf84b9b31293d9b9d68bb3e13ed68bd42a4fd4e5ece7d7d224a055aa7e2b130f04cce46dbcfdb2799627ed26951d8f84c61c7c1e2bd58f5d45dfabd1b6ebea6dbd3b55f669bf00dd382919dc998d27956422521f9b927b5f27794985243ccba67c03aa974a638918f633b99437a410382c04f967669a31c98e9eed7acf5634d61dc585d569a7f786f68ca4663bfb28606406b550ad2a7af117162a6a87400bedfbcbfd646b0858697dc105a6f1783a3ad29dbf585fc0965c46d5d71d8919b8c42095ec32a547b7c2816b2fe

We have to consider whether it's useful.

Let the first self.parse result to be $m_1$ and the second to be $m_2$. It is easily found that $s = m_1^{d_p} \mod p$ and $s = m_2^{d_q} \mod q$. Calculating $e$-th power, $s^e = m_1 \mod p$ and $s^e = m_2 \mod q$. Remark that we know $s^e$ and almost all part of $m_1, m_2$ except for hmac_key, nonce and digest_message. $m_1, m_2$ has the following form:

base_m = (
    bytes_to_long(b"\n\x19My crypto protocol v0.0.1\x12\x10") * 256 ** 483
    + bytes_to_long(
        b'\x1a\x85\x01For this signing oid I am not sure, but I would guess something in between 1.2.840.113549.2.7 and 1.2.840.113549.1.1.5 plus nonce :)."\x14'
    )
    * 256 ** 329
    + bytes_to_long(
        b"*\x88\x01For this signing algorithm I am not sure, but I would guess something in between hmacWithSHA1 and sha1-with-rsa-signature plus nonce :).2\x14"
    )
    * 256 ** 168
    + bytes_to_long(b"\x80") * 256 ** 147
)
m1 = base_m + 256**467 * x + 256**309 * yp + 256**148 * z
m2 = base_m + 256**467 * x + 256**309 * yq + 256**148 * z

Where $0 \le x < 256^{16}, 0 \le y_p, y_q, z < 256^{20}$. Note that $x, z$ are the same in $m_1, m_2$ because hmac_key and digest_message are the same. Doesn't it seem useful?

(I noticed the vulnerability and the formula above right before the CTF ends...)

I first tried to find $x, y_p, z$ such that $s^e = m_1 \mod p$ by Coppersmith's method. I used defund/coppersmith as usual. But it took so much time that it hadn't finished until the CTF ended :cry:

Right after the CTF ended, I noticed another easier way to solve. Since we know $s^e = m_1 \mod p, s^e = m_2 \mod q$, it also holds true that $(s^e - m_1)(s^e - m_2) = 0 \mod n$. The left hand side of this equation is 2-degree polynomial with regard to $x, y_p, y_q, z$. If we treat this 2-degree term as another variable, we can get linear equation with all variables relatively small. This equation can be solved by LLL algorithm. After these roots are found, we can simply factor $n$ by calculating gcd of $s^e - m_1$ and $n$. Then we can easily decrypt the flag!

solve.sage
from Crypto.Util.number import bytes_to_long, long_to_bytes

base_m = bytes_to_long(b'\n\x19My crypto protocol v0.0.1\x12\x10') * 256**483 + bytes_to_long(b'\x1a\x85\x01For this signing oid I am not sure, but I would guess something in between 1.2.840.113549.2.7 and 1.2.840.113549.1.1.5 plus nonce :)."\x14') * 256**329 + bytes_to_long(b'*\x88\x01For this signing algorithm I am not sure, but I would guess something in between hmacWithSHA1 and sha1-with-rsa-signature plus nonce :).2\x14') * 256**168 + bytes_to_long(b'\x80') * 256**147
sig_enc = int(pow(sig, e, n))

c = base_m - sig_enc
# 256**467 * x + 256**309 * yp + 256**148 * z + c = 0 mod p
# 256**467 * x + 256**309 * yq + 256**148 * z + c = 0 mod q
# => (256**467 * x + 256**309 * yp + 256**148 * z + c)(256**467 * x + 256**309 * yq + 256**148 * z + c) = 0 mod n
# lhs = 256**934 * x**2 + 256**618 * yp*yq + 256**296 * z**2 + 256**776 * (x*yp+x*yq) + 2*256**615 * x*z + 256**457 * (z*yp+z*yq) + 2*256**467*c * x + 256**309*c * (yp+yq) + 2*256**148*c * z + c**2
# alternatively
# lhs = 256**934 * t0 + 256**618 * t1 + 256**296 * t2 + 256**776 * t3 + 2*256**615 * t4 + 256**457 * t5 + 2*256**467*c * t6 + 256**309*c * t7 + 2*256**148*c * t8 + c**2
# where t0 <= 256**32, t1 <= 256**40, t2 <= 256**40, t3 <= 2*256**36, t4 <= 256**36, t5 <= 2*256**40, t6 <= 256**16, t7 <= 2*256**20, t8 <= 256**20
# [t0, ..., t8, 1, 0] = [t0, ..., t8, 1, k] * mat
coeffs = [256**934 % n, 256**618 % n, 256**296, 256**776 % n, 2*256**615 % n, 256**457, 2*256**467*c % n, 256**309*c % n, 2*256**148*c % n, c**2 % n, -n]
mat = matrix(ZZ, 11, 11)
for i in range(10):
    mat[i, i] = 1
for i in range(11):
    mat[i, 10] = coeffs[i]
res = mat.LLL()
C = mat.solve_left(res)

ts = None
for row in C:
    if abs(row[-2]) != 1:
        continue
    if row[-2] == -1:
        row = -row
    ts = row
    break
assert ts is not None
assert sqrt(ts[0]) == ts[6]
assert sqrt(ts[2]) == ts[8]

# The following didn't work... It's probably because ts[3] = x * (yp + yq) is a multiple of ts[7] = yp + yq
# PR.<z> = PolynomialRing(ZZ)
# f = z**2 - int(ts[7]) * z + int(ts[1])
# f.roots()

PR.<yp> = PolynomialRing(Zmod(n))
f = 256**467 * int(ts[6]) + 256**309 * yp + 256**148 * int(ts[8]) + c
f = f.monic()
yp = f.small_roots(beta=0.5)[0]
p = gcd(int(f(yp)), n)
assert n % p == 0 and p > 1
q = n // p
d = int(pow(e, -1, (p - 1) * (q - 1)))
print(long_to_bytes(int(pow(enc, d, n))))

CTF{They_say_never_implement_your_own_crypto...ok_ok_lesson_learned}

After writing the writeup above, I read an official solver. It used Coppersmith and doesn't take so much time to solve. What's the difference between defund/coppersmith and this.

The first difference is a different lattice. defund/coppersmith has more monomials. Maybe official solver is tuned to solve linear equation? I don't know.

The second difference is a way to compose ideals. Before finding the variety, defund/coppersmith composes ideals from the minimum number of polynomials, while official solver from the maximum number of polynomials.

Both of them are needed to solve relatively fast in this case according to my experiment. I don't fully understant why these are needed, have to learn more...