ふるつき

v(*'='*)v かに

Midnightsun CTF 2021 writeup

Midnightsun CTFは毎年いくつか独自色の強い問題が出るな、という印象だったのですが、今年はBackupシリーズのcryptoがひどかった印象があります。その他AVRマイコンなどの組み込みに関連する問題が出るのはいつもどおりという感じ。

私は純粋cryptoを2問通しました。どちらもsolve数が二桁前半で、簡単というほどではないが難しい問題ではない、という感じでの面白い問題でした。なんとかチームメイトに怒られない程度の貢献はできたかな。

ocat_024

u = getrandbits(512)
p = next_prime(1337 * u + getrandbits(300))
q = next_prime(2021 * u + getrandbits(300))
n = p * q

sage: n                                                                                                                                                       
376347864369130929314918003073529176189619811132906053032580291332225522349124770927556541528827257242440708492473086949335591022991715583608318595770643139658398940858358366788472884935226392323475683663699450192657590965945792699658618476121298301964814904817629813971114882401961638885452623305901569855693667669
sage: e                                                                                                                                                       
310766221758298615381202293330340201483059349618898159596286032329366528507960364515724537815587119639645241427449290559721282531962504187828968370246921804939126848756614691757878117709116273156365166616707032588454229002048939764035908902821773289938766897121298435864096976179239412103595971947786698704390414999
sage: round(log(d, 2))                                                                                                                                        
376
sage: Zmod(n)(int.from_bytes(flag, 'big'))^e                                                                                                                  
303959676149267585825046248298946771045524761540948385119310381022731003152171453295355624619013005255259014408962058282203132797411290952180380162699236575669681289832696809724483816916203823843359489329046259936011464869397208487809073597880729992617105037777911285154649450892121090200338517719744860831555514222

 p = 1337u + a, q = 2021u + b となっているRSAの問題です。加えて、 dが比較的小さいことが分かっています。

まず第一に注目するのは素数が独特な構造になっていることです。これは過去にConfidence CTF 2019 TeaserでReally Suspicious Acronymとして出題されている形式で、 uが共通しており、 a, bのサイズが比較的小さいことから \frac{p}{q} = \frac{1337u + a}{2021u + b} \simeq \frac{1337}{2021}と近似ができるので、 n \times \frac{1337}{2021} \simeq n \times  \frac{p}{q} = p^2 という近似ができます。この近似により p, qの上位210ビット程度を求めることができます。

しかしこれだけの情報では、Coppersmith's methodを用いた素因数分解には不足です。そこで dが比較的小さいというヒントから、 ed = 1 \mod \phi(N)を使って立式していきます。

 \phi(N) = N - (p + q) + 1 ですから、  p + qを先程近似した値 p', q'と真の値との差 rを用いて p + q = p' + q' + rと表して以下の式が成り立ちます。

 ed = 1 + tN - t(p' + q' + r) + t

さらに \mod eをとります。

 0 \equiv 1 + tN - t(p' + q' + r) + t \mod e  \tag{△}

式(△)において、未知変数は r, t であり、 rは素因数 p, qの未知の部分なので300bit程度、また t = (ed - 1) / \phi(N) \simeq (2^{1045}\times 2^{376} - 1) / 2^{1045} \simeq 2^{376} であることから、 tの大きさは最大でも376bit程度になります。一方 eは1000bit以上ありますから、 r, tは剰余多項式(△)の比較的小さな整数根になっていると言えそうです。したがってCoppersmith's methodによって r, tの具体的な値を求められるかもしれません。多変数多項式の小さい根を求める実装としては、 defund/coppersmith が優れています。これを使って r, tを求めることができれば、 \phi(N)を計算しフラグを求められそうです。

# https://raw.githubusercontent.com/defund/coppersmith/master/coppersmith.sage
import itertools

from sage.rings.polynomial.multi_polynomial_sequence import PolynomialSequence

def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()

    R = f.base_ring()
    N = R.cardinality()
    
    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)

    G = PolynomialSequence([], f.parent())
    for i in range(m+1):
        power = N^(m-i) * f^i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = power
            for variable, shift in zip(f.variables(), shifts):
                g *= variable^shift
            G.append(g)

    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)

    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)

    B = B.dense_matrix().LLL()

    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1/factor)
    B = B.change_ring(ZZ)

    H = Sequence([], f.parent().change_ring(QQ))
    for h in B*monomials:
        if h.is_zero():
            continue
        H.append(h.change_ring(QQ))
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            V = I.variety(ring=ZZ)
            if V:
                roots = []
                for root in V:
                    root = map(R, map(root.__getitem__, f.variables()))
                    roots.append(tuple(root))
                return roots

    return []


n = 376347864369130929314918003073529176189619811132906053032580291332225522349124770927556541528827257242440708492473086949335591022991715583608318595770643139658398940858358366788472884935226392323475683663699450192657590965945792699658618476121298301964814904817629813971114882401961638885452623305901569855693667669
e = 310766221758298615381202293330340201483059349618898159596286032329366528507960364515724537815587119639645241427449290559721282531962504187828968370246921804939126848756614691757878117709116273156365166616707032588454229002048939764035908902821773289938766897121298435864096976179239412103595971947786698704390414999
c =  303959676149267585825046248298946771045524761540948385119310381022731003152171453295355624619013005255259014408962058282203132797411290952180380162699236575669681289832696809724483816916203823843359489329046259936011464869397208487809073597880729992617105037777911285154649450892121090200338517719744860831555514222

p_ = int(sqrt(n * 1337/2021))
q_ = int(sqrt(n * 2021/1337))

PR.<r, t_> = PolynomialRing(Zmod(e))
f = 1 + k_*n - t_*(p_ + q_ + r) + t_
for ans in small_roots(f, [2^300, 2^377]):
    r = int(ans[0])
    phi = n - (p_ + q_ + r) + 1

    d = int(pow(e, -1, phi))

    m = pow(c, d, n)
    print(m)

求まりました。

dbcsig_64434

from hashlib import sha256


def keygen(password):
    while True:
        p = 2 * random_prime(2 ^ 521) + 1
        if p.is_prime(proof=False):
            break
    base, h = 3, password
    for i in range(256):
        h = sha256(h).digest()
    x = int.from_bytes(h * 2, "big")
    return base, p, pow(base, x, p), x


def sign(message, priv):
    h = int(sha256(message).hexdigest(), 16)
    k = next_prime(int.from_bytes(
        sha256(message + priv.to_bytes(128, "big")).digest() + sha256(message).digest(),
        "big"
    ))
    r = int(pow(g, (k - 1) / 2, p))
    s = int(Zmod((p - 1) / 2)(-r * priv + h) / k)
    return r, s


g, p, pub, priv = keygen(b"[redacted]")
r, s = sign(b"blockchain-ready deterministic signatures", priv)

(配布ソースコード中に存在した、問題と直接関係ないコメントを省略しています)

独自のデジタル署名アルゴリズムのようですが、プログラムはいわゆるDSAのそれと似通っています。目的は d = privを求めることで、 g, p, pub, r, sに加えて、平文から求められる hが分かっています。

このアルゴリズムを観察すると、2つ特徴的な部分が見つかります。まず1つ目は秘密鍵 dの構造で、int.from_bytes(h * 2, "big") のように、256bitの値を2回繰り返して並べることで512bitの値を作っています。値の大きさは512bitありますが、情報量としては256bitのものと等価と考えられます。2つめは kの値で、こちらも256bitの値を2つ並べて作られていますが、上位256bitが全くわからない一方、下位256bitは h + \alpha でありおよその値が分かっています。

式をたてて整理してみます。そもそものDSAアルゴリズムでは  ks \equiv -rd + h \mod q (ただしここで q = (p - 1) / 2です)がなりたち、それは今回も同様です。ここで k = 2^{256}k' + h + \alpha,  d = 2^{256}d' + d'と表しつつ、移項して式を整理すると次のような形になります。

 s(2^{256}k'  + h + \alpha) + r(2^{256}d' + d') - h \equiv 0 \mod q

ここで未知数は k', d', \alphaで、 k', d'はそれぞれ256bitの値です。 \alphaはどのくらいかわかりませんが、だいたい1000を超えることはないでしょう。他方、 qは521bit程度の値であり未知数と比較して大きいですから先ほどと同様にCoppersmith's methodが適用できそうです。

# https://raw.githubusercontent.com/defund/coppersmith/master/coppersmith.sage
...

from hashlib import sha256

g = 3
p = 403564885370838178925695432427367491470237155186244212153913898686763710896400971013343861778118177227348808022449550091155336980246939657874541422921996385839128510463
pub = 246412225456431779180824199385732957003440696667152337864522703662113001727131541828819072458270449510317065822513378769528087093456569455854781212817817126406744124198
r = 195569213557534062135883086442918136431967939088647809625293990874404630325238896363416607124844217333997865971186768485716700133773423095190740751263071126576205643521
s = 156909661984338007650026461825579179936003525790982707621071330974873615448305401425316804780001319386278769029432437834130771981383408535426433066382954348912235133967
message = b"blockchain-ready deterministic signatures"
h = int(sha256(message).hexdigest(), 16)

q = (p-1) // 2
# assert q.is_prime ????????

PR.<d_, k_, a> = PolynomialRing(Zmod(q))

f = 2^256 * s * k_ + s * (h + a) + r * (d_ + 2^256 * d_) - h
roots = small_roots(f, [2^256, 2^256, 1000], d=4, m=4)

for root in roots:
    dval = Integer(root[0])
    dval = dval * 2^256 + dval
    if pow(g, dval, p) == pub:
        print("[+] found: {}".format(dval))
        break
    else:
        print("[-] wrong: {}".format(dval))

できました。ところで、この問題のkeygenに従って値が作られていれば pは最大でも522bit程度の値で安全素数になると思ったのですが、実際には pは557bitあり、また安全素数ではありませんでした。これは一体どういうことでしょうか 🤔

Securinets CTF 2021 Quals writeup

楽しく解ける問題ばかりで評価が高い。BOSS問という感じの問題はなかったので割と解かれていた印象。唯一PoWが面倒な形式だったのでもうちょっと丁寧に作ってほしかった感じはある

MiTM

from Crypto.Util.number import long_to_bytes
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from secret import flag
import hashlib
import random
import os
import signal

class DHx():
    def __init__(self):
        self.g = 2
        self.p = 0xf18d09115c60ea0e71137b1b35810d0c774f98faae5abcfa98d2e2924715278da4f2738fc5e3d077546373484585288f0637796f52b7584f9158e0f86557b320fe71558251c852e0992eb42028b9117adffa461d25c8ce5b949957abd2a217a011e2986f93e1aadb8c31e8fa787d2710683676f8be5eca76b1badba33f601f45
        self.private = random.randint(1, self.p - 1)
        self.secret = None

    def getPublicKey(self):
        return pow(self.g, self.private, self.p)

    def share(self, x : int):
        assert x > 1 and x < self.p
        return pow(x, self.private, self.p)

    def getSharedSecret(self, x : int):
        assert x > 1 and x < self.p
        self.secret = pow(x, self.private, self.p)

    def getFingerprint(self):
        return hashlib.sha256(long_to_bytes(self.secret)).hexdigest()

    def checkFingerprint(self, h1 : str, h2 : str):
        return h1 == h2 == self.getFingerprint()

    def encryptFlag(self):
        iv = os.urandom(16)
        key = hashlib.sha1(long_to_bytes(self.secret)).digest()[:16]
        return iv.hex() + AES.new(key, AES.MODE_CBC, iv).encrypt(pad(flag, 16)).hex()

signal.alarm(60)

Alice = DHx()
Bob = DHx()
Carol = DHx()

A = Alice.getPublicKey()
print("Alice sends to Bob: {}".format(A))
A = int(input("Forward to Bob: "))
B = Bob.share(A)
print("Bob sends to Carol: {}".format(B))
B = int(input("Forward to Carol: "))
Carol.getSharedSecret(B)

B = Bob.getPublicKey()
print("Bob sends to Carol: {}".format(B))
B = int(input("Forward to Carol: "))
C = Carol.share(B)
print("Carol sends to Alice: {}".format(C))
C = int(input("Forward to Alice: "))
Alice.getSharedSecret(C)

C = Carol.getPublicKey()
print("Carol sends to Alice: {}".format(C))
C = int(input("Forward to Alice: "))
A = Alice.share(C)
print("Alice sends to Bob: {}".format(A))
A = int(input("Forward to Bob: "))
Bob.getSharedSecret(A)

print("Alice says: ")
if (Alice.checkFingerprint(Carol.getFingerprint(), Bob.getFingerprint())):
    print(Alice.encryptFlag())
else:
    print("ABORT MISSION! Walls have ears; Be careful what you say as people may be eavesdropping.")

名前のとおりにAlice Bob Carol三者のDiffie Hellman鍵共有プロセスに介入して、任意のパラメータの交換を改竄できる。ただし三者は鍵共有のあと、互いの鍵が一致しているかを確かめるために、それぞれの鍵のfingerprintが一致することを確認している。したがって、三者の鍵を同じにしつつ、鍵の中身を知ることができるような改竄の仕方を考える必要がある。

一番簡単な方法は0や1を送って 0^a = 0 1^a = 1と計算してもらうことだが、三者は送られてきたパラメータ x 1 \lt x \lt p であることを確認しているのでこれはできない。それならば -1はどうか。三者秘密鍵 a,b,cが偶数の場合は -1^a \equiv 1 \mod pとなってしまうので途中でエラーになるが、すべて奇数ならば -1^a \equiv -1 \equiv p-1 \mod p p-1に落ち着く。

というわけで p-1を送りつつ a,b,cがそれぞれ奇数になる組み合わせを引くまでガチャする。実際はガチャ用のコードを整えている間にyoshikingがガチャを当てて解いていた。

from ptrlib import Socket
from Crypto.Util.number import long_to_bytes
from Crypto.Cipher import AES
import hashlib
import time

while True:
    time.sleep(1)
    sock = Socket("crypto1.q21.ctfsecurinets.com", 1337)
    p = 0xf18d09115c60ea0e71137b1b35810d0c774f98faae5abcfa98d2e2924715278da4f2738fc5e3d077546373484585288f0637796f52b7584f9158e0f86557b320fe71558251c852e0992eb42028b9117adffa461d25c8ce5b949957abd2a217a011e2986f93e1aadb8c31e8fa787d2710683676f8be5eca76b1badba33f601f45

    sock.sendlineafter("Forward to Bob: ", str(p - 1))
    AB = int(sock.recvlineafter("Carol: "))
    if AB == 1:
        sock.close()
        continue
    sock.sendlineafter("Forward to Carol: ", str(AB))
    print("[+] progress 1")

    sock.sendlineafter("Forward to Carol: ", str(p - 1))
    BC = int(sock.recvlineafter("Alice: "))
    if BC == 1:
        sock.close()
        continue
    sock.sendlineafter("Forward to Alice: ", str(BC))
    print("[+] progress 2")

    sock.sendlineafter("Forward to Alice: ", str(p - 1))
    CA = int(sock.recvlineafter("Bob: "))
    if CA == 1:
        sock.close()
        continue
    sock.sendlineafter("Forward to Bob: ", str(CA))
    print("[+] progress 3")

    print(sock.recvline())
    line = sock.recvline().decode()
    if "ABORT" in line:
        sock.close()
        continue

    key = hashlib.sha1(long_to_bytes(p - 1)).digest()[:16]
    iv, cipher = bytes.fromhex(line[:32]), bytes.fromhex(line[32:])
    aes = AES.new(key, AES.MODE_CBC, iv)
    print(aes.decrypt(cipher))

    break

あとでyoshikingに教えてもらったけど、 a,b,cがそれぞれ偶数の場合でも解けて、1度目の介入では適当な値を渡して、2度目でだけ p-1を送るようにすればshareが a,b,cの偶奇に応じて 1 p-1になるので、↑の方法より確率を上げることができる。

Shilaformi

import signal
from secret import flag
from Crypto.Random import random
from Crypto.Util.number import getPrime

#Odds and evens (hand game)
#https://en.wikipedia.org/wiki/Odds_and_evens_(hand_game)

def pad(choice, n):
    return 2*random.randint(1, n//2 - 1) + choice

def send(choice, n):
    choice = pad(choice, n)
    return pow(2, choice, n )

signal.alarm(360)
print ("Let's play odds and evens! If I win you loose 5 times the amount of money you have bet! I choose odd.\n")

WALLET = 10
while WALLET > 0:
    print("Your current wallet is {} $.\n".format(WALLET))

    if WALLET > 133337:
        print("Wow, You've got filthy rich. Here's your flag: {}".format(flag))
        exit()

    n = getPrime(1024)*getPrime(1024)
    print ("Public Modulus : {}\n".format(n))

    bet = int(input("Place your bet : "))
    assert bet <= WALLET and bet > 0

    choice = random.randint(0, 5)
    print ("Here's my choice : {}\n".format(send(choice, n)))

    player = int(input("Shilaaafooooooormi: "))
    assert player >= 0 and player < 6

    if (choice + player ) & 1:
        print("You lose.")
        WALLET -= 5*bet
    else:
        print("You win.")
        WALLET += bet

print("You got no money left in your wallet. Make sure to come back later!")

いわゆるOdds and evensというゲームらしく、相手が出してきた手と自分が出してきた手の和が偶数になるように値を選んで送れば勝ちとなる。相手は手 x 0 \le x \le 5の間から一つ選び、 n = pq と毎回ことなる乱数 rを用いて y = 2^{2r + x} \mod nとして渡してくれる。

このとき、 yから xの偶奇を判断する問題は、平方剰余問題(quadratic residuosity problem)として知られている 平方剰余問題と行った場合には aから a \equiv x^2 \mod nを満たす xを探す問題を指していそう。この問題は平方剰余の判定問題で、一般的な名前があるのかは知らない。ある値 aがある剰余の法 nの上で平方剰余か(= x^2 \equiv  a \mod nとなる xが存在するか)を調べるためにはルジャンドル記号、あるいはヤコビ記号を使うことができる。ルジャンドル記号は剰余の法が素数である場合に使える記号であり、ヤコビ記号はルジャンドル記号を拡張して合成数にも適用可能にしたものである。ただし、一部の正確性は失われている

大雑把に言えば、 Jacobi(a, n) = 1 のとき aは平方剰余かもしれないし、そうでないかもしれない。一方で Jacobi(a, n) = -1のとき、 aは必ず平方剰余ではない。したがって、与えられた手 y nについて Jacobi(y, n)をみて、その値が1の時はOdds and evensに勝てる確率は1/2であり、その値が1のときは必ず勝つことができる。

ところでここからがよくわかっていないんだけど、チームメイトのS3v3ru5に教えてもらい手元で実験した感じだと、 nの値によってヤコビ記号がうまく働いたり働かなかったりする。うまく働くケースに限って持金を全betし、勝てるかわからないときは1だけ掛けることで持金を増やした。

from ptrlib import Socket
import proofofwork
import gmpy2
import random

sock = Socket("crypto2.q21.ctfsecurinets.com", 1337)
pat = sock.recvregex(r"sha256\(([A-Za-z]+) \+ X\) = 000000")[0]
print(pat)

s = proofofwork.sha256(
        '000000??????????????????????????????????????????????????????????',
        text=pat + b'?????')
print(s)
sock.sendline(s[len(pat):])

# sock = Socket("localhost", 19999)

while True:
    current = int(sock.recvregex(r"wallet is ([0-9]+) \$.\n")[0])
    print(current)
    if current > 133337:
        sock.interactive()
    n = int(sock.recvlineafter("Modulus : "))
    print("[+] got modulus")

    # check n
    flag = True
    for choice in range(0, 6):
        x = 2*random.randint(1, n//2 - 1) + choice
        y = pow(2, x, n)
        if (x % 2 == 0) != (gmpy2.jacobi(y, n) == 1):
            flag = False
    print("[+] check: {}".format(flag))

    bet = 1
    if flag:
        # surely win
        bet = current
    sock.sendlineafter("bet : ", str(bet))

    y = int(sock.recvlineafter("choice : "))
    sock.sendlineafter("mi: ", str(1 if gmpy2.jacobi(y, n) == -1 else 0))
    if b"win" in sock.recvline():
        current += bet
        print("Win! current money: {}".format(current))
    else:
        current -= bet*5
        print("Loose... current money: {}".format(current))

        if current <= 0:
            print("LOOSE")
            break

Sign It!

from Crypto.Util.number import inverse
from Crypto.Random import random
from fastecdsa.curve import Curve
from fastecdsa.point import Point
import hashlib
import signal

class Server():
    def __init__(self, curve, G):
        self.G = G
        self.order = curve.q
        self.d = random.randrange(1, self.order - 1)
        self.P = (self.d * self.G)

    def sign(self, msg):
        z = int(hashlib.sha256(msg.encode()).hexdigest(), 16)
        k = random.randrange(1, self.order - 1)
        r = (k * self.G).x % self.order
        s = (inverse(k, self.order) * (z + r * self.d)) % self.order
        return (r, s)

    def verify(self, msg, sig):
        r, s = sig
        s %= self.order
        r %= self.order
        if s == 0 or r == 0:
            return False
        z = int(hashlib.sha256(msg.encode()).hexdigest(), 16)
        s_inv = inverse(s, self.order)
        u1 = (z * s_inv) % self.order
        u2 = (r * s_inv) % self.order
        W = u1 * self.G + u2 * self.P
        return W.x == r


signal.alarm(360)
# S256 curve params
p = 0x402969301d0ec23afaf7b6e98c8a6aebb286a58f525ec43b46752bfc466bc435
gx = 0x3aedc2917bdb427d67322a1daf1073df709a1e63ece00b01530511dcb1bae0d4
gy = 0x21cabf9609173616f5f50cb83e6a5673e4ea0facdc00d23572e5269632594f1d
a = 0x2ad2f52f18597706566e62f304ae1fa48e4062ee8b7d5627d6f41ed24dd68b97
b = 0x2c173bd8b2197e923097541427dda65c1c41ed5652cba93c86a7d0658070c707
q = 0x402969301d0ec23afaf7b6e98c8a6aeb2f4b05d0bbb538c027395fa703234883
S256 = Curve("S256", p, a, b, q, gx, gy)

PROOF = "Give me flag."
print("Welcome to the ECDSA testing of our probably secure S256 Curve. First choose your own generator then try to sign this message '{}' to prove us wrong.\n".format(PROOF))

print("Choose your point (x y) : ")

try:
    x = int(input("x : "))
    y = int(input("y : "))
    G = Point(x, y, curve=S256)
    S = Server(S256, G)

    sample = "No flags for you."
    print("Here's a sample signature: msg = '{}' , signature = {}".format(
        sample, S.sign(sample)))

    while True:
        msg = input("Message : ").strip()
        r = int(input("r : "))
        s = int(input("s : "))
        if S.verify(msg, (r, s)):
            print("Valid signature.")
            if msg == PROOF:
                from secret import flag
                print("Here you go : {}".format(flag))
                exit()
        else:
            print("Invalid signature.")

except Exception as e:
    print(e)
    exit()

ECDSAに関する問題。こちらからはいわゆるBase Point  Gを渡すことができ、かつ適当なメッセージに署名をしてもらえるので、向こうが指定したメッセージに署名するとフラグがもらえる。

楕円曲線上の離散対数問題が解けでもしない限りそんなことはできない。ところが与えられている楕円曲線のパラメータを見てみると、位数 qが小さい素因数として 157を持っているとS3v3ru5が教えてくれた。このとき、適当な楕円曲線上の点 Gに対して q/157をかけた G' = (q/157)G の位数は157になる。位数が小さければ離散対数問題は簡単にとける。

import hashlib
from ptrlib import Socket
import proofofwork

p = 0x402969301d0ec23afaf7b6e98c8a6aebb286a58f525ec43b46752bfc466bc435
gx = 0x3aedc2917bdb427d67322a1daf1073df709a1e63ece00b01530511dcb1bae0d4
gy = 0x21cabf9609173616f5f50cb83e6a5673e4ea0facdc00d23572e5269632594f1d
a = 0x2ad2f52f18597706566e62f304ae1fa48e4062ee8b7d5627d6f41ed24dd68b97
b = 0x2c173bd8b2197e923097541427dda65c1c41ed5652cba93c86a7d0658070c707
q = 0x402969301d0ec23afaf7b6e98c8a6aeb2f4b05d0bbb538c027395fa703234883

EC = EllipticCurve(GF(p), [a, b])
G = EC(gx, gy)
G2 = (q // 157) * G  # 157 is small factor of order

# sock = Socket("localhost", 19999)
sock = Socket("crypto2.q21.ctfsecurinets.com", 13337)
pat = sock.recvregex(r"sha256\(([A-Za-z]+) \+ X\) = 000000")[0]
print(pat)

s = proofofwork.sha256(
        '000000??????????????????????????????????????????????????????????',
        text=pat + b'?????')
print(s)
sock.sendline(s[len(pat):])

sock.sendlineafter("x : ", str(G2[0]))
sock.sendlineafter("y : ", str(G2[1]))

r, s = sock.recvregex(r"signature = \(([0-9]+), ([0-9]+)\)")
msg = "No flags for you."
z = int(hashlib.sha256(msg.encode()).hexdigest(), 16)
r, s = int(r), int(s)

for k in range(157):
    if (k*G2)[0] == r:
        print("[+] found k: {}".format(k))
        break
else:
    raise ValueError("[-] failed to calculate discrete log")

d = (s*k - z)*inverse_mod(r, 157) % 157
print("[+] found d: {}".format(d))


PROOF = "Give me flag."
z = int(hashlib.sha256(PROOF.encode()).hexdigest(), 16)
r = int((k * G2)[0])
s = (int(inverse_mod(k, 157)) * (z + r * d)) % 157


sock.sendlineafter("Message : ", PROOF)
sock.sendlineafter("r : ", str(r))
sock.sendlineafter("s : ", str(s))
sock.interactive()

LINE CTF 2021 babycrypto4 writeup

LINE CTF は cryptoに関しては満足行くクオリティの問題はありませんでした……。

overview

secp160r1上のECDSAに関する次の20 x 4個のパラメータが与えられます*1。左からr, s, kの上位16bit, hash(m) です。このときにいわゆる秘密鍵dを求めよ、という問題です。

0x92acb929727872bc1c7a5f69c1c3c97ae1c333e2 0xe060459440ebc11a7cd811a66a341f095f5909e5 0xef2b0000 0x68e548ef4984f6e7d05cbcea4fc7c83393806bbf
0xb0f5df566a323de9c9449b925d29b84a607c6b5d 0x84e39e417e47b4fcaf344255103c61ecaaec4129 0xc1c00000 0x1a79e7b0308805508d79f2600a01e70d4f56559e
0xc90081698382f98c817a137db22f11a846d699fe 0x2f8fbb7e74b789cd762b30930ef21862a5fd68ee 0x841b0000 0x95e3302e197be4d8335cf0d17cc70860ea5317f7
0x9d84669314b014bc83f3ac53ddcf3c9536c940b1 0x8b1a69d6e9d75f1698144badc7b93f9a2347839d 0xa1c90000 0xc7af08154a154ac8c58eb14380955834093b3863
0x96d5439a01f47e92be9ff40bee1fecb033b70d3f 0x1c23660695d16bf03ef40e5ef53bdc92a5d348e7 0x816e0000 0x9d3f0dc80e962b9377ed22de66d6421457bcaf5d
0x3ea39f6c446918690b395ba181f6d5d08444897a 0x4478e239338ec6652815d03b8decb2d4f58beaba 0x9d050000 0x478e00e6191477e6cdd17a29719d96d02e5e8960
0xbd1cbcd26fb6cb41878ec155fb2506534e803c97 0xd732fbda187222d85e9a14243b007cc25e1b6b7c 0x445a0000 0x2493379cf90246fe7316963c65f28cd9b0a6ecd4
0x727f7f05a9096beb6d5f65acce6fe42ec3a07dc9 0x8511715efb01ff83b04fe82fb7535dc7de40abef 0x91d0000 0x6ce034dddd5470034068c5146fae4dd039aacaf6
0x513ed0e15f8f3405bf0083a2186926fe60ccb65e 0x28892ebcc428f2a566b39a2dbe03ec436641c948 0x879d0000 0xfe4e2564369a23e07efbf82d01c5ae7e72cd8105
0xebf3e23fbe73c5f50032c8e4a3d8359fef203a03 0xa5b79ae6f8ed237a05b4325c02b8dfe7b9ff5aa7 0x98950000 0x762309f98ebac533fece5321736fc6ba95d8382b
0xc49cdbf6ec3b73188238291fa960675a099b74a0 0xeabb1e7dcd20115a47b94ecfe8780f676e237437 0x287a0000 0x523ea75c4310ac1ac64fa28cc5047b7223e8da0b
0x9e8a731a26f509793e2b8778cd75b518549ab9c8 0x27be029029db9d62cdb729bc592cb0a4e6168bf3 0xebc80000 0x9f0e9e95661f5e93c90b72af0dce38c673c7ef16
0xa74159f377749ad36efc28f9c7608a6758009af 0xa3ce2671944b01f633265a6458ce2cca8b72eda6 0x574c0000 0x16e12f9dece23681927be002d24a0e4e6ed3ae7e
0xcb0a427a05b3e3dcb18a1bb66f9340d2a0c721ab 0x4a242cca295c6018f4a65d1fadbdb45731cccd7a 0x23f40000 0xd7e0a09d8aed604bc1fda1f1965c4a8bf6b58621
0x5dc440585c88e75da002f941520867add07f93ef 0x3612124de46659ef7d79d46f1eb05707e313b84d 0x65850000 0xca6547a9e3f08bd36f700b7282a36033250971ad
0x6e009a8f5138a5b94d4e81b5f2a07ee29b413b39 0x8b3c33c15dca93248f840324d540b7956251d1e0 0xb4f80000 0xe916da678253ff7b31453ba1ec709eb909b37c5d
0x5091314db6155d7a96c1b19098ca235cf86d1f77 0x2c62bf21452a2b326e8db27fb3345e10c63b2821 0x452c0000 0x31dd06dcf95fb04a734149eed64b7b99a575d56e
0x2f6eed036a46ca6e309d8d7292bd3b0796607fcc 0x63b4524f47dcde603426c48bbb2f308bc474e5ce 0x63780000 0xe108d036a12b4f15cc9af89688d26634c5dfc32a
0x247ca1d3450a85612e6176ea5dfec4aeb90e2a3f 0x66b1f9f04e284e28f44402f1ca7803c90786d9c2 0x48a0000 0xd58c608cc4d3adfc131c73cccff952c1d310a1e0
0xab04fc0c4981b047622c786662091f7efbbbd807 0xa2853851df0aaed34dc972bcf7d7d5ffbbc2b401 0x9d040000 0x5bdd98b548b8b0f48a56fb4c41e6d09bf8bd1b0e

solution

いわゆるnonceであるkの上位16bitがわかっているのでこれを利用するのかな、と思うところですが、そもそも32bitのkでは小さすぎるので、半分が与えられていようがいまいが変わらず解けます。

(EC)DSAでは s \equiv (h + rd)k^{-1} \mod n ですから、これを展開して変形すると k - s^{-1}rd  - s^{-1}h \equiv 0 \mod n になります。いくつかのインスタンスを考えて、インスタンスごとに異なる値に添え字をつけると

 k_i - s_u^{-1}r_id  - s_i^{-1}h_i \equiv 0 \mod n

となります。このとき、 k_i, d がそれぞれ未知数で、 r_i, s_i, h_iはそれぞれ既知です。

一方、Hidden Number Problemは以下の式で t_i, a_i既知、 x_i, y未知に未知数を求める問題で、 x_iの最大値がある程度小さい時には、CVPを解いて x_i, yがそれぞれ求めることができます。

 x_i - t_iy + a_i \equiv 0 \mod p

2つの式を見比べてみると、 k_i \leftrightarrow x_i,  s_i^{-1}r_i \leftrightarrow t_i,  d \leftrightarrow y,  a_i \leftrightarrow -s_i^{-1}h_i という対応づけができそうです。そして、 x_iに対応する k_iは最大でも 2^{33} - 1 と小さいですから、CVPを解くことで k_i, xを求められそうです。今回は埋め込み法(embedded technique)と呼ばれる形のSVPを解くことでCVPを解いています。

from hashlib import sha1
import random

# https://neuromancer.sk/std/secg/secp160r1
p = 0xffffffffffffffffffffffffffffffff7fffffff
K = GF(p)
a = K(0xffffffffffffffffffffffffffffffff7ffffffc)
b = K(0x1c97befc54bd7a8b65acf89f81d4d4adc565fa45)
E = EllipticCurve(K, (a, b))
G = E(0x4a96b5688ef573284664698968c38bb913cbfc82, 0x23a628553168947d59dcc912042351377ac5fb32)
E.set_order(0x0100000000000000000001f4c8f927aed3ca752257 * 0x01)

n = int(E.order())

dataset = []
with open("output.txt") as f:
    lines = f.read().strip().split("\n")
    for l in lines:
        # r_, s_, k_, h_ = [int(x, 16) for x in l.split(" ")]
        dataset.append( [int(x, 16) for x in l.split(" ")] )


r, s, k, h = zip(*dataset)
N = 20 # randint(2, 20) # len(h)
print("N = {}".format(N))
t = [r[i] * inverse_mod(s[i], n) % n for i in range(N)]
u = [(h[i] * inverse_mod(-s[i], n) % n) % n for i in range(N)]

nonce_max = 2**32

B = matrix(QQ, N + 2, N + 2)
B.set_block(0, 0, matrix.identity(N) * n)
B.set_block(N, 0, matrix(QQ, 1, N, t))
B.set_block(N+1, 0, matrix(QQ, 1, N, u))
B[N,N] = nonce_max / n
B[N+1,N+1] = nonce_max

L = B.LLL()
for row in list(L):
    k1 = int(abs(row[0]))
    if k1 != 0 and k1 != nonce_max and k1 < nonce_max:
        x = (k1*s[0] - h[0]) * inverse_mod(r[0], n) % n
        kk = (k1 >> 16) << 16
        print(k1, x, kk in k)
        print(int(x)*G)

この問題では k_iがかなり小さいので、3インスタンス程度あればHNPが解けます。

*1:もともと問題文ではsecp160k1となっていましたが、正しくはsecp160r1のようでした。この間違いのアナウンスなしに解いたThe Duckはすごい

CTF crypto 逆引き

粗削りだけどとりあえず公開することにして、少しずつ情報を足していきたい。こういうケースがある、またこういう場合はどうすればよいのかという情報や質問をお待ちしています。

RSA

黙って Twenty Years of Attacks on the RSA CryptosystemRecovering cryptographic keys from partial information, by example を読んでおけば大体なんとかなる

e が 3など (Low Public Exponent)

例えば、 m^e \lt n であればe乗根を取ることで mが手に入る

出題例

nが多くの素因数に分解される

いわゆるMulti-Prime RSA nがどう素因数分解されようともオイラーのφ関数は定義できて、 \mod nでの位数がわかるので逆元 d \equiv e^{-1} \mod \phi(n)が求められる。

出題例

nがある素数と別の合成数までは素因数分解できる

実際には n = p*q*r だが、 p \lt q,r でnを素因数分解した結果 n = p*c (ここで c=q*r)までは得られたが、 c素因数分解は難しそう、というとき。このとき m \lt pであれば、 \mod pの世界で考えることで mを得られる。

出題例 募集中

nが同じでeが異なる複数の暗号文 (Common Modulus)

Common Modulus Attackが適用できる。複数の eが互いに素ではない場合には、それぞれの eの最大公約数を公開鍵とした暗号文が手に入ることになる

出題例 募集中

e, dがわかっているときにnを素因数分解する

def factorize(N, e, d):
    from math import gcd
    import gmpy2

    k = d*e - 1
    t = k
    while t % 2 == 0:
        t //= 2

    g = 3
    while True:
        x = pow(g, t, N)
        if x > 1:
            y = gcd(x - 1, N)
            if y > 1:
                return y, N//y
        g = gmpy2.next_prime(g)

出題例 募集中

φ(n)がわかっているときのnの素因数分解

そもそも \phi(n)がわかっているならsecret exponentが求められるのでわざわざ n素因数分解する必要はない。それでも素因数分解したい場合は n = pq, \phi(n) = pq - p - q + 1より、 b = n - phi + 1 = p + q としておくと、2次方程式の解と係数の関係から p,q = \frac{b \pm \sqrt(b^2 - 4n)}{2}として素因数が求まる

出題例 募集中

何度でも任意の暗号文を復号でき、復号結果のうち一部が手に入る (LSB Leak)

LSB Leak Attackが適用できる。一度に手に入る平文のbit数が多い代わりに、復号の試行回数に制限がある場合もある。LSB Leak Attackには2種類のアプローチがあると思っている。

一つはよく説明されるもので、次の通り。

 (2^eC)^d \equiv 2m \mod nについて考える。 2m \lt n であれば 2mは2倍されているので偶数、すなわちLSBは0となる。一方で 2m \gt nでれば、復号結果は 2m - n となるから( 2n \gt 2m \gt n )偶数と奇数の減算で奇数になる*1。すなわちLSBは1となる。ということは、 2^eCの復号結果のLSBが0ならば 0 \lt m \le \frac{n}{2}が、LSBが1ならば \frac{n}{2} \lt m \lt nがわかる。次に 4^eC についても同様に考えて、次々と mの範囲を2分探索的に縮めていき、 mの値を求める。

もう一つの方法は、次のようなもの。個人的にはこちらのほうが明快。

 C \mod nの復号によって得られるLSB Oracle mの最下位bitである。では 2^{-e}C \mod nの復号結果から得られるLSB Oracleはどうか。これは 2^{-1}m \mod nの最下位bitであり、 mの下から2番目のbitの値である。さらに 2^{-2e}C \mod nの復号結果か得られるLSB Oracle mの下から3番目のbitの値で……とこれを mのbit数だけ繰り返すことで mの全体がわかる。

出題例

pやqに関連する値を暗号化している

うまく暗号文同士のgcdをとったり、 \mod pなどについて考えることによって秘密鍵を入手できる場合がある。

出題例

mやp, q, dの値が一部わかっている、近似できる

LLLやCoppersmith methodを使ってmやp, q, dを求めることができる。Coppersmithも内部ではそれっぽい格子を生成してLLLをしているのでどちらでも解ける。sageに実装されているCoppersmith methodは一変数多項式に対するものだが、多変数多項式に対してはdefundさんが実装しているものが出来がよく、これを使っておけばだいたいなんとかなる。

github.com

出題例

dが同じでnやeが異なる暗号文 (Small Common Private Exponent)

かつ、dがある程度小さければSmall Common Private Exponent Attackができる。

出題例

かつ、 a,b 既知のとき、Franklin-Reiter's Related Message Attackが使える

出題例

ブロック暗号

ECBモードで、任意の平文+フラグが暗号化される

いわゆるChosen Plaintext Attackができる。

出題例

CBCモードで平文の先頭1ブロック程度を変更できれば良い (Bit Flipping)

Bit Flipping Attackで十分

出題例

CBCモードで復号の成否がわかる (Padding Oracle)

Padding Oracle (Encryption) Attackができる。

出題例

2段や3段の暗号化で、使われている鍵が短い (Meet in the Middle Attack)

Meet in the Middle Attackができる。

出題例

独自のS-BOXが使われている

Differential / Linear Cryptoanalysis だろうけど理解してないのでかけない

楕円曲線暗号

基本的な事項はだいたいすべて yoshi-gcc log - ふるつき にあります

その他の暗号

onetime pad

絶対にmany time padなので頻度解析をしながら鍵を当てていくとだんだん解けます。以前インタラクティブに解けるソルバを作ったので使い方を憶えると解きやすくなるはず

zer0pts / mtpsolver · GitLab

出題例

(EC)DSA で同一のnonceが複数回用いられている (Nonce Reuse)

いわゆるnonce-reuse attack

出題例

平文がフラグと連結、圧縮されてから暗号化される(圧縮サイドチャネル攻撃 / compression oracle

多くの圧縮手法では同一の平文が存在すると圧縮効率がよくなるため、もっとも圧縮効率がよくなる1文字を探索することでフラグに対するオラクルとすることができる。これはBEASTやCRIMEといった攻撃手法の原理(のはず)

出題例

*1:すなわち nが素因数に2を含んでいる時にはこの攻撃は成立しない、と思う

Fireshell CTF 2019 Biggars writeup

gist.github.com

とにかく長大なパラメータを持つRSA。nは大きいが小さい素因数からなっていて、簡単に素因数分解できる。

>>> list(factor(n))
[(3, 1545), (7, 1626), (11, 1569), (13, 1552), (17, 1519), (19, 1673), (23, 1498), (29, 1667), (31, 1604), (37, 1542), (41, 1622), (43, 1525), (53, 1606), (59, 1531), (61, 1484), (67, 1631), (71, 1596), (73, 1495), (79, 1656), (83, 1658), (89, 1581), (97, 1592), (101, 1656), (103, 1487), (107, 1488), (109, 1577), (113, 1500), (127, 1514), (131, 1660), (137, 1610), (139, 1677), (149, 1637), (151, 1596), (157, 1656), (163, 1534), (167, 1627), (173, 1580), (179, 1646), (181, 1511), (191, 1651), (193, 1591), (197, 1562), (199, 1661), (211, 1539), (223, 1620), (227, 1492), (229, 1665), (233, 1654), (239, 1679), (241, 1620), (251, 1566), (257, 1622), (263, 1677), (269, 1551), (271, 1563), (277, 1507)]

3つ以上の素因数からなるRSAはMulti-prime RSAと言われる。この場合にもRSA暗号は成立する。オイラーのφ関数を一般化して、 N = \prod_i p_i^{k_i} と表されるとき、 \phi(N) = \prod_i(p_i^{k_i}-p_i^{k_i-1}) である。あとは dを計算して復号すれば良い

ただしこの問題の場合、 nが非常に大きいため、 c^d \mod nの計算はそのままでは非常に時間がかかる。そこでRSA-CRTの考え方を使い、中国剰余定理を用いてこの計算を高速化する。

import gmpy
from params import n, e, c

def chinese_remainder(ms, ns):
    assert(len(ms) == len(ns))

    n = 1
    for i in range(len(ms)):
        n = n * ns[i]

    r = 0
    for i in range(len(ms)):
        p = n / ns[i]
        r += ms[i] * gmpy.divm(1, p, ns[i]) * p
    try:
        return long(r % n)
    except:
        return int(r % n)

factors = [(3, 1545), (7, 1626), (11, 1569), (13, 1552), (17, 1519), (19, 1673), (23, 1498), (29, 1667), (31, 1604), (37, 1542), (41, 1622), (43, 1525), (53, 1606), (59, 1531), (61, 1484), (67, 1631), (71, 1596), (73, 1495), (79, 1656), (83, 1658), (89, 1581), (97, 1592), (101, 1656), (103, 1487), (107, 1488), (109, 1577), (113, 1500), (127, 1514), (131, 1660), (137, 1610), (139, 1677), (149, 1637), (151, 1596), (157, 1656), (163, 1534), (167, 1627), (173, 1580), (179, 1646), (181, 1511), (191, 1651), (193, 1591), (197, 1562), (199, 1661), (211, 1539), (223, 1620), (227, 1492), (229, 1665), (233, 1654), (239, 1679), (241, 1620), (251, 1566), (257, 1622), (263, 1677), (269, 1551), (271, 1563), (277, 1507)]


ms = []
ns = []
for p, k in factors:
    n = pow(p, k)
    phi = pow(p, k) - pow(p, k - 1)
    d = gmpy.divm(1, e, phi)
    m = pow(c, d, n)
    ms.append(m)
    ns.append(n)

m = chinese_remainder(ms, ns)
print(bytes.fromhex(hex(m)[2:]))

zer0pts CTF 2021 振り返り

大筋まとめ

zer0pts CTF 2021 は 成功と言ってよさそう。本番めちゃくちゃヤバいトラブルはなかったし、問題も安定してクオリティの高いものが提供できた。

諸情報

かつてない参加者数になったし、賞金もかつてない量になった。こんなに大規模なCTFの運営に携わることになるとは

Name Value
開催期間 2021-03-06 09:00:00 +09:00 – 2021-03-07 21:00:00 +09:00
登録チーム数 1449
1点以上獲得したチーム数 951
Welcome / Survey 以外の問題も通したチーム数 259

正確な情報ではないけど、参加”者”数だと 3000〜4000 くらいだと思う

Top Teams

Name Score
Super Guesser 5211
K-Students 5153
r00timentary 5153

image.png (138.8 kB)

スコアサーバ

  • InterKosenCTF2020でも使ったkosenctfxをまた採用した
  • かなり安定して動作していて、CTF終了直後にアクセスが集中してレスポンスが悪くなったとき以外は不調は見られなかった
    • このときはDB側が遅くなっていた
  • 前回からいくつか改造した
    • RankingでのFirst - Third Bloodの表示やDiplomaなど
  • Rankingページの描画が重たくなってしまったのは反省点
    • 全チームが何を解いたかを表示しているので描画がある程度遅くなるのは当然
    • さらにFirst - Third Bloodを表示するために各問題に対する正答を提出時刻でソートしているのでまあ遅い
      • これは途中でこの処理をWeb Workerに任せる用に変更したことで多少改善した
  • 一部SQL文にtypoがあり、パスワードリセットが初期ではうまく動かなかった
    • テストを書こう
  • DO の MySQL、初期状態では ANSI_QUOTES が有効になっていて、gormが発行するSQLと噛み合わないことがあった
  • フラグがcase insensitiveに受け入れられていた
    • びっくりした。SQL側の設定だと思う。反省です
  • フロントエンドは競技中に様々なマイナーバージョンアップが加わった
    • 正直必要ないと思ったが、なにやら必要だと思った人もいて、めちゃくちゃ小刻みにデプロイ要求をされてすごく疲弊した
    • CTFのスコアサーバがmobile friendlyである必要、あるのだろうか
      • 当然対応していたほうが良いに違いはないが、本番の真っ最中にこれをやるのはかなりRiskyだと思うが……

インフラ

  • 基本的にDigitalOceanが提供するサービスでインフラ管理を行っていた
    • 3k CTF の prize として DigitalOcean の credit をもらっていたのでDOにしたが、そうでなければAWSなどを使っていたと思う。かゆいところに手が届かない
  • スコアサーバ(API側)は最近登場したDigitalOcean App Platformというやつを利用した
    • herokuやFargateのようなPaaSで、Docker Imageからシュッとアプリケーションが立ち上がって便利だった
      • heroku触ったことないので嘘かも
    • アプリケーションのログをエクスポートできないのはめちゃくちゃ不便だった
      • あんまり関係ないけど、サーバのアクセスログものすごい勢いで流れていてコンピュータスゲーになった
  • スコアサーバ(フロント側)はDigitalOcean Spacesを利用した
    • S3 のようなやつで、CloudFrontを噛ませなくても自由にドメインを決めてCertをつけてCDNがついてくる(Cache Purgeし放題っぽい?)は嬉しいけど、デフォルトルートという概念がなく、必ず index.html をつけてアクセスしないと403になるのがものすごくダサい。DOは早く対応してほしい
    • チーム内でもこれがめちゃくちゃ嫌だから他Platformにしてくれという声があったが、競技開始直前だったことや、すべてをDOで完結させる簡潔さを損ないたくないことからRejectした
    • 流石にこちらは終始安定して稼働していた
  • 問題サーバは基本的に2GB Memory 2 shared vCPUs のインスタンスをカテゴリ毎に立てた
    • こちらもかなり安定して稼働していた
    • 結局問題がどれだけ安定して稼働するかによる
    • DigitalOceanはデフォルトでは3個までしかDropletを建てさせてくれないので、それ以上の数を立てたい場合(や、もうちょっと高級なインスタンスを使いたい場合)は事前に申請する必要がある。一回Rejectされたので焦ってSupport Ticketを切ってお願いしたら素早く対応してくれた
  • 全体的にコストはかなり安く抑えられたと思う。全部合わせても$20から$30の間くらいではないだろうか
    • やっぱりDBが結構高くつくが、システムの要なのでこのくらいの出費は全然OKと思うのが良さそう
    • 結局CTF終了後1週間程度dropletsを立ち上げ続けていたので$50〜%60くらいになった
  • 問題のデプロイや、IPのBanを自動化するCI/CDパイプラインを作成した
    • GitLab CI便利
    • Ansible 便利だけど遅いがち
      • Ansible の信用できるDocker ImageというのがPublicにはないので、毎度 pip install ansible をするような構成にしてみたが、これかなり遅くて実行時間の何割かを持っていっているのでやめるべきだった
    • push する度に何度もpublic keyを配布したりしていて、Ansibleの冪等性からはそれでもいいんだろうけどやっぱり遅いのでなにか実行を制御するしくみは欲しいと思った
    • 様々な理由でCI/CD パイプラインの実行時間を雑に消費した結果、開催当日の朝4時とかになってGitLabで使えるFreeの実行時間がなくなってしまい焦った
      • specific runnerを急いでデプロイした。簡単にできてすごい
  • インフラは結局ほとんど一人で面倒を見ているが、実際は良くないんだろうなと思う
    • 私が寝ているときに問題が発生するとか、いくらでもあり得る
  • Prometheus などを使った監視システムも作っていたが、採用やめた
    • あんまりちゃんとテストできていなかったので余計な不安を抱えたくない
    • しかし監視は重要なのでいつまでも目をそむけてはいられない
  • 問題のConnection Check / Solvability Checkも仕組みをつくったりはしたが、あまり出来がよくなかったので採用しなかった
  • このあたり本当にLMTはすごいなと思う

提供した問題

image.png (152.2 kB)

Authorごとの問題の提供数は以下の通り。うーんptr-yudai CTF! 作問能力どないなっとるんや

Author Count(*)
16 ptr-yudai
5 theoldmoon0602
2 st98
2 mitsu
2 s1r1us
2 zer0pts
1 x0r19x91
1 (=^·u·^=)
  • 提供した問題は全体的に評判が良くて何より
    • No guess をちゃんと達成しているのもよかった
  • 当初48時間CTFの予定だったが問題数に不安があって36時間になった。最終的な問題の解かれ具合をみても36時間が適切だったと思う
    • そもそもCTFの48時間は長すぎるんだよな。しかしTimezone - Fairnessがほしければ48x 時間開催することになる
      • 結局時間に関係なく私生活をなげうってずっと取り組み続けた人が強いんだからTimezone - Fairnessとか気にしなくていいと個人的には思っている
    • 特にwebとrevの問題数に不安があった。webはまあいいとしてもrevの作問リソースがかなり厳しい
      • rev の面白い問題をどうやったら作れるのか、2, 3年考えているけどrevの問題とかないがちなのでわからない
    • 開催直前に問題が発覚して慌てて修正した問題や、今回は採用見送りになった問題がある
      • 慌てて修正した問題も個人的には次回に回したかった。まともにチェックできていないということで出題するのは怖い。一つの壊れた問題でCTF全体が壊れるので
      • CTF始まってから問題追加しようとする人がいたがやめて欲しい。Rejectするのも結構しんどい
        • あとでも言及すると思うけど、これまではかなり少人数で運営していたからコンセンサスを取ろうとする必要もなく目指す方向が一致していたが、だんだん人数が増えて、あと使ってる言語も違ったりしてそういうところで同じ意識を持つのが難しくなっている
  • 全体的な難易度は去年より上がったという声が多かった
    • そんなに変えたつもりはないので勝手に評価基準がズレたっぽい。成長しているということだろうか
    • 難しい問題を提供したいんじゃなくて面白い問題を提供したい、と個人的には思っている。難易度偏重にならないように気をつけたい
  • 事前に予想していたのとは全然違う解かれ具合になったりした
    • GuestFS:AFR はwarmupタグがついているにも関わらず15solves
    • その他にも事前に想定していた難易度とはSolve数が逆転している問題がいくつかあった
    • 結局、難易度の推定は難しいということ
  • 質問をもらっても、基本的には"try harder", "no hint" と返すことになっていた
    • CTFは競技なので良いと思う。ただ、上手い質問の仕方というのはあったりするので、JOIやなんかのように事前に決められた答えが帰ってくる仕組みを作るのが良いんだろうな。そこまでするかどうかというのは置いておいて
  • いくつかunintended solutionはあったが、許容範囲だと思う
    • PDF Generatorは基本的に全部unintended solutionで解かれていたのであとからNot PDF Generatorを提供した
      • 個人的にはこれも必要なかったと思っているが、あまり強く口を出せる領域でもない
  • いくつかの問題ではアクセスが結構集中して、サーバが重たくなったりする時間があった
    • そういう懸念がある問題は基本的にPoW / CAPTCHAを入れるのが良いと思う。これは今後の問題チェック時の確認事項に追加しておきたい
      • そういうものを文書化しているわけではないが、そろそろ文書化するのが良さそう
      • PoWは嫌いな人もいるだろうが、必要なのだからしかたない。しかしPoWを提供する時はWorkerのサンプル実装は提供されるべき

その他

  • Discordでnew challengeのアナウンスとsolve のアナウンスを入れていたが @everyone みたいなチーム名で登録して人々に迷惑をかける人がいた
    • これができるようにしていたのはまあこちらが悪い
    • 正直そんなことをする人がいるとは思ってなかったのでびっくりした。なんの利があったんだろう
    • それに乗っかる人もいた
  • 自分の提供した問題で、提供した配布ファイルが古いもので解けないと言われて焦って配布ファイルを更新したが、更新した配布ファイルも古いままだったりした
    • 焦っていた……
  • prize、急に増えてびっくりした。ありがたい
    • このあとprizeを配る作業がまだある。終わりまでしっかりやりたい

個人的なことの振り返り

  • 楽しかった。CTF運営は最高の娯楽。やめられねぇぜ
    • 準備中 / 終わったあと / writeup と survey を読んでいるときがそれぞれめちゃくちゃ楽しい
    • 運営中は常に不安と戦いながら監視をしている
  • 自分の立ち位置は、「作問者」「インフラ担当」「当日運営」だったと思う。いわゆる"admin"(ここではrng_58さんのような立ち位置を意味している)だったかはわからない
  • 英語できないのでアナウンス業をptr-yudaiとかst98さんに丸投げしていたのは申し訳ないなと思っている
  • 結局 Crypto しか提供できておらず、偏っていて良くないなと思っている
    • Cryptoにしても、もう一段階難しい問題が作れるようになりたい
      • input 増やしていかなければ
    • Web / Rev あたりの簡単だがちょっと頭を使うみたいな問題を作れるようになって、 Web 屋 Rev 屋に本質問題に注力してもらいたいな
  • 当日は早起き & 夜ふかしでめちゃくちゃ疲れた
    • CTF運営は精神力も使うし体力も使う
  • 運営中ptr-yudaiと通話をつないで喋っていたのは良かった
    • 楽しかったし情報の伝達が早いし意思決定もはやくなる

Union CTF 2021 writeup

Mordel Primes

from Crypto.Util.number import bytes_to_long
from secrets import k, FLAG

assert k < 2^128
assert FLAG.startswith(b'union{')

E = EllipticCurve(QQ,[0,1,0,78,-16])
P = E(1,8)
Q = k*P
R = (k+1)*P

p = Q[0].numerator()
q = R[0].numerator()

assert is_prime(p)
assert is_prime(q)

e = 0x10001
N = p*q
m = bytes_to_long(FLAG)
c = pow(m,e,N)

print(f'N = {N}')
print(f'c = {c}')

RSA秘密鍵  p, q有理数体上の楕円曲線 E 上の2点 Q, Rのx座標の分子から生成しています。少し実験すると、有理数体上では k が大きくなればなるほどその座標の値も大きくなっていることがわかります。これは結構なスピードで大きくなるので、 kの値を全探索すれば適切な Q, Rが見つかりそうに思えます。

E = EllipticCurve(QQ,[0,1,0,78,-16])
P = E(1,8)

N = ...
c = ...

for k in range(2, 1000):
    Q = k*P
    R = (k+1)*P

    M = Q[0].numerator() * R[0].numerator()
    if N == M:
        p, q = (Q[0].numerator(), R[0].numerator())
        break
else:
    quit()

e = 0x10001
N = p*q
phi = (p-1)*(q-1)
d = inverse_mod(e, phi)

m = pow(c, d, N)
print(bytes.fromhex(hex(m)[2:]))

感想

要素が無限にある有理数体上の楕円曲線なのだから、値がどんどん大きくなるのはそれはそうだよなぁと思った。そこにたどり着くまでに色々机上の空論をこねくり回してはうまく行かないと頭を抱えていましたが、実験するとすぐだったので実験は大事ですね。

committee

flag.txt というファイルだけが存在する git リポジトリと、そのコミットログが渡されます。リポジトリ自体のログは最初の2コミット分しか記録されていません。また、flag.txt の中身は union{*******3*********_************r****d**********} となっています。

...

commit cb18d2984f9e99e69044d18fd3786c2bf6425733
Author: Peter G. Anderson <pepega@legal.committee>
Date:   Tue Apr 14 12:00:00 2020 +0000

    Proceedings of the flag-deciding committee: 32, 33, 34

commit dca4ca5150b82e541e2f5c42d00493ba8d4aa84a
Author: Christopher L. Hatch <crisscross.the.hatch@legal.committee>
Date:   Mon Mar 23 12:30:00 2020 +0000

    Proceedings of the flag-deciding committee: 8, 31, 36

commit c3e6c8ea777d50595a8b288cbbbd7a675c43b5df
Author: Pamela W. Mathews <pammy.emm@legal.committee>
Date:   Fri Mar 13 12:30:00 2020 +0000

    Proceedings of the flag-deciding committee: 18

commit 08e1f0dd3b9d710b1eea81f6b8f76c455f634e87
Author: Robert J. Lawful <boblaw@legal.committee>
Date:   Wed Mar 4 12:00:00 2020 +0000

    Initial formation of the flag-deciding committee.

与えられた情報から、この問題はコミットログを頼りにフラグのi文字目の値を探索し、ログに残されたコミットハッシュと一致しているかを調べていくことで解けそうです。このためには、gitのコミットハッシュがどのように決まるのかを知る必要があります。これには Gitのコミットハッシュ値は何を元にどうやって生成されているのか | メルカリエンジニアリング というブログ記事が参考になりました。 .git/objects 以下に存在するファイルと照らし合わせながら処理をかいて、最終的に次のようなプログラムで解くことができました。

import re
from datetime import datetime
import zlib
from hashlib import sha1
from typing import List
from ptrlib import brute_force_attack, brute_force_pattern

def get_indices(s: str):
    xs = re.findall(r"\d+", s)
    return [int(x) for x in xs]

class Commit():
    def __init__(self):
        self.binsha = b""
        self.author = ""
        self.date = 0
        self.message = ""

    def __repr__(self):
        return "commit {}\nAuthor: {}\nDate:   {}\n{}".format(self.binsha.hex(), self.author, datetime.fromtimestamp(self.date).strftime("%c +0000"), self.message)

    def get_hash(self, flag, parent):
        blob = "blob {}\0{}".format(len(flag), flag)

        treecontent = b"100644 flag.txt\0" + sha1(blob.encode()).digest()[:20]
        tree = b"tree " + str(len(treecontent)).encode() + b"\0" + treecontent
        treehash = sha1(tree).digest()[:20]

        obj = "tree {}\nparent {}\nauthor {} {} +0000\ncommitter {} {} +0000\n{}".format(treehash.hex(), parent.hex(), self.author, self.date, "Flag-deciding Committee <committee@legal.committee>", self.date, self.message)
        target = b"commit " + str(len(obj)).encode() + b"\0" + obj.encode()
        # return repr(target)
        return sha1(target).hexdigest()


with open("log.txt") as f:
    lines = f.read().strip().split("\n")
    commits = [] # type: List[Commit]
    commit = Commit()
    for i in range(len(lines)):
        if lines[i].startswith("commit "):
            if commit.binsha:
                commit.message = commit.message[:-1]
                commits.append(commit)
                commit = Commit()

            commit.binsha = bytes.fromhex(lines[i][len("commit "):])

        elif lines[i].startswith("Author: "):
            commit.author = lines[i][len("Author: "):]

        elif lines[i].startswith("Date:   "):
            commit.date = int(datetime.strptime(lines[i][len("Date:   "):], "%c %z").timestamp())

        else:
            commit.message += lines[i].lstrip() + "\n"
    commits.append(commit)

flagstr = "union{*******3*********_************r****d**********}\n"
offset = 5
commits = commits[:-2][::-1]
for i in range(1, len(commits)):
    indices = get_indices(commits[i].message)

    for b in brute_force_attack(len(indices)):
        p = brute_force_pattern(b)
        flag2 = list(flagstr)
        for j, k in enumerate(indices):
            flag2[offset + k] = p[j]

        h = commits[i].get_hash("".join(flag2), commits[i-1].binsha)
        if h == commits[i].binsha.hex():
            flagstr = "".join(flag2)
            print(flagstr)
            break
    else:
        raise Exception()

感想

gitのコミットハッシュに関する問題はどう出題したものかと思っていましたが、とてもきれいな出題がなされていてすごいと思いました。そして勉強になった。最初の2コミットが残されていて、自分の書いたプログラムが正しいかどうかをそれで検証できる用になっているのがとても親切だと思います