はじめに

この記事ではInterKosenCTFで出題した問題の解説を書きます。他の問題のwriteupについては下記リンクから参照してください。

ptr-yudai.hatenablog.com

概要

Description: nc others.kosenctf.com 10300
File: matroska.tar.gz

サーバーで動いているプログラムのソースコードが渡されます．スロットゲームで大金を稼ぐゲームで，お金の状態を保存して途中でゲームを終了でき，次回からそのセーブデータ（トークン）を使って状態をロードすることができます．お金は一度に1～500ドル賭けることができ，お金が負の値になってもトークンを保存することはできますが，ゲームを続行することはできません．ブルートフォースを防ぐため最初にPoWがあり，sha256の最後の方が一致するようなテキストを送る必要があります．ここは簡単なので解くコードだけ置いておきます．

import hashlib
import string
import random
import sys

target = sys.argv[1]

while True:
    text = ''.join([random.choice(string.ascii_letters) for i in range(16)])
    md5 = hashlib.sha256(text).hexdigest()
    if md5[-5:] == target[-5:]:
        print(text)
        print(md5, target)
        break

さて，トークンは「お金@署名」という形式で渡され，署名は楕円曲線（secp256k）を利用して生成されます．

def sign(m):
    """ Calculate a signature for the money """
    G, q = P256.G, P256.q
    if m >= q:
        raise ValueError("Too large value to sign.")
    if m <= -q:
        raise ValueError("Too small value to sign.")
    sign = 1 if m >= 0 else -1
    P, Q, R = sign*a*G, sign*b*G, c*G
    S = pow(m, prime, q)*G + m*m*P + m*Q + R
    enc = _asn1_public_key(S)
    return base64.b64encode(enc)

$G, p$ はそれぞれsecp256kのベースポイント，位数です． $P, Q, R$ は $G$ を定数倍したものなのですが， $a, b, c$ は秘密なので分かりません．また，トークンは

${}$ $$ S_{m} = \left\{ \begin{array}{} {(m^{p} \mod q)G + m^{2} P + mQ + R} & ( x \geq 0) \\ {(m^{p} \mod q)G - m^{2} P - mQ + R} & ( x < 0) \end{array} \right. $$

で生成されます．したがって，任意の金額 $m$ のトークンを作るには $P, Q, R, m^{p}$ が分かっている必要があります．初項がなければ連立方程式で $P, Q, R$ は簡単に求まるのですが，今回は $m^{p}$ があるのでそう簡単にはいきません．

解法

まずは特徴的な金額を与えて出てくるトークンを考えましょう． $m = 0$ のとき，

$S_{0} = (0^{p} \mod q)G + 0^{2} P + 0 \cdot Q + R = R$

なので， $R$ が求まります．また， $m=1,-1$ のとき，

$S_{1} = (1^{p} \mod q)G + 1^{2} P + 1 \cdot Q + R = G + P + Q + R$

$S_{-1} = ((-1)^{p} \mod q)G - (-1)^{2} P - (-1) \cdot Q + R = -G - P + Q + R$

です．これらを辺々足すと

$S_{1} + S_{-1} = 2(Q + R)$

となりますが， $R$ は分かっているので $Q = 2^{-1}(S_{1} + S_{-1} - 2R)$ となります．さらに， $G$ も分かっているので， $P = S_{1} - G - Q - R$ より求まります．

これで $P,Q, R$ が分かるのですが， $m^{p} \mod q$ から $p$ を求めるのは離散対数問題なので解けません．しかし，今回の目標は任意の $m$ からトークンを作ることではなく，お金を増やすことなので， $m=q-1$ の場合を考えてみます．すると，

$(q-1)^{p} \mod q = (-1)^{p} \mod q = -1 \mod q = q-1$

となり，非常に大きい値の $m^{p} \mod q$ が分かることになります．したがって，ここまでに求めた楕円曲線上の点 $P, Q, R$ を用いて

$S=(q-1)G + (q-1)^{2} P + (q-1)Q + R = -G + P - Q + R$

を計算すれば金額が $q-1$ の時の署名が求まります．

import base64
from fastecdsa.asn1 import _asn1_public_key
from fastecdsa.asn1 import decode_key
from fastecdsa.curve import P256
from fastecdsa.point import Point

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def token2point(token):
    from fastecdsa.asn1 import ASN1_PARSED_DATA, OBJECT_IDENTIFIER
    _, token = token.split('@')
    ASN1_PARSED_DATA.append((OBJECT_IDENTIFIER, P256.oid))
    return decode_key(base64.b64decode(token))[1]

G, q = P256.G, P256.q
Sn1 = token2point('-1@A0IABCOzUtB+jjcg7rSy0h2xBOf2DrrTJlW1n239LGrCMi+KwVGcQXCMM/UfD5GQA8XKpGpL0DCob/A6wEcrmNoq6Xg=')
S0  = token2point('0@A0IABGA062NzBN0dFxWwXv+xzMgfbc6A3048RVTrDEMajEHizL/r/szmYLR1PkLVwfCzb8HGAElwvK1k9jUFmqcX4Rg=')
S1  = token2point('1@A0IABHZo6IoUfkynj8h19v+JT07Kj+vUIrD6YFOoKIzUiF/D7lc6pn51ux65oXs2jrIpTl40suHgjjolCJHH2bU+28c=')

R = S0
Q = modinv(2, q) * (Sn1 + S1) - R
P = S1 - G - Q - R
m = q - 1
S = -G + P - Q + R

print(R)
print(P)
print(Q)

enc = _asn1_public_key(S)
print(str(m) + "@" + base64.b64encode(enc))

あとがき

もともとふるつきがRSAの凖同型性を用いて作ったslot machineだったのですが，楕円曲線使えば難しくならないかなーと思って改造しました．解けるけど思いつくのが難しい暗号問題を作るのは本当に大変で，このアイデアに辿り付くまでに何枚も紙を使いました．結果として良い感じの難しさになったのですが，数学が得意な高専生にはもっと解いて貰いたかったです．

CTFするぞ

CTF以外のことも書くよ

【Crypto 300】slot machine - InterKosenCTF 作問writeup

はじめに

概要

解法

あとがき