Google CTF 2022 Writeup

Mon Jul 04 2022

    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, Enc(x)Enc(y)=Enc(x+y)\mathrm{Enc}(x) \mathrm{Enc}(y) = \mathrm{Enc}(x + y). Therefore we can control the decryption of c0=Enc(s)c_0 = \mathrm{Enc}(s) (where ss is secret) by multiplying Enc(y)\mathrm{Enc}(y). c0Enc(y)c_0 \mathrm{Enc}(y) is decrypted to s+ys + 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 xx to i-th byte (0i<1280 \le i < 128) and unpad succeeds this time, i-th byte of secret should be 256x256 - 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 c0Enc(x)c_0 \mathrm{Enc}(x) where xx 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)1150.8%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 nn can be factored when we know h=210253h = 2^{1025} - 3 such that meh+1=mmodnm^{e^{h+1}} = m \mod n in usual RSA.

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

    Let λ(n)=i=1kpiei\lambda(n) = \prod_{i=1}^k p_i^{e_i}. Then λ(λ(n))=lcm(λ(p1e1),,λ(pkek))=lcm(1or2or2e,p2e21(p21),,pkek1(pk1))\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 λ(λ(n))=i=1kqifi\lambda(\lambda(n)) = \prod_{i=1}^k q_i^{f_i}. Since h+1h+1 is a multiple of λ(λ(n))\lambda(\lambda(n)), qiq_i is one of factor of h+1h+1. h+1h+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 fi=1f_i = 1 because of the results above.

    Since λ(λ(n))=i=1kqifi=lcm(1or2or2e1,p2e21(p21),,pkek1(pk1))\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:

    • pi1p_i - 1 is a multiple of some qjq_j
    • If ei2e_i \ge 2, pip_i equals to one of qjq_j

    So I tried to find candidates for pip_i from the factor of h+1h + 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 pip_i. Considering the case when ei2e_i \ge 2, pip_i should be one of set(cands) & set(primes). This intersection contains only 2 and 3. Therefore λ(n)\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 dd to decrypt, where d=e1modλ(n)d = e^{-1} \mod \lambda(n). Though we don't know λ(n)\lambda(n), we can know a multiple of λ(n)\lambda(n) by calculating products of all of cands (and power of 2, 3). Let this product to be LL. When ed=1modLed = 1 \mod L, also ed=1modλ(n)ed = 1 \mod \lambda(n) because λ(n)L\lambda(n) | L. Therefore d=e1modLd = 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 256lencmodn256^{-l}\mathrm{enc} \mod n is successful or not. If ll 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 m1m_1 and the second to be m2m_2. It is easily found that s=m1dpmodps = m_1^{d_p} \mod p and s=m2dqmodqs = m_2^{d_q} \mod q. Calculating ee-th power, se=m1modps^e = m_1 \mod p and se=m2modqs^e = m_2 \mod q. Remark that we know ses^e and almost all part of m1,m2m_1, m_2 except for hmac_key, nonce and digest_message. m1,m2m_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 0x<25616,0yp,yq,z<256200 \le x < 256^{16}, 0 \le y_p, y_q, z < 256^{20}. Note that x,zx, z are the same in m1,m2m_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,yp,zx, y_p, z such that se=m1modps^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 se=m1modp,se=m2modqs^e = m_1 \mod p, s^e = m_2 \mod q, it also holds true that (sem1)(sem2)=0modn(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,yp,yq,zx, 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 nn by calculating gcd of sem1s^e - m_1 and nn. 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...

      ;