今週土日に開催されていたDownUnderCTF 2021に出たので自分が解いたCrypto問題のWriteupを書きます。Crypto問題以外も解きましたが、記憶が無いので書きません。

Table of Contents §

Substitution Cipher I §

次のようなスクリプトとその実行結果(output.txt)が配布される。

def encrypt(msg, f):
    return ''.join(chr(f.substitute(c)) for c in msg)

P.<x> = PolynomialRing(ZZ)
f = 13*x^2 + 3*x + 7

FLAG = open('./flag.txt', 'rb').read().strip()

enc = encrypt(FLAG, f)
print(enc)

フラグの各文字をとおくと、を計算して別の文字に置換している。

というわけでフラグになり得る文字から逆変換テーブルを生成すれば良い。

import string


def f(x):
    return 13*x**2 + 3*x + 7


def create_table():
    cs = string.printable
    ret = {}
    for c in cs:
        _c = ord(c)
        ret[f(_c)] = c

    return ret


def exploit():
    enc = open("./output.txt").read()
    table = create_table()
    flag = ""
    for c in enc:
        _c = ord(c)
        flag += table[_c]
        print(flag)


if __name__ == "__main__":
    exploit()

Flag: DUCTF{sh0uld'v3_us3d_r0t_13}

Substitution Cipher II §

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

from string import ascii_lowercase, digits
CHARSET = "DUCTF{}_!?'" + ascii_lowercase + digits
n = len(CHARSET)

def encrypt(msg, f):
    ct = ''
    for c in msg:
        ct += CHARSET[f.substitute(CHARSET.index(c))]
    return ct

P.<x> = PolynomialRing(GF(n))
f = P.random_element(6)

FLAG = open('./flag.txt', 'r').read().strip()

enc = encrypt(FLAG, f)
print(enc)

I同様1文字ずつの変換なので逆変換テーブルを作ればよいのだが、肝心の式がf = P.random_element(6)で知ることが出来ない。

ここでフラグがDUCTF{<text>}の形であるとすれば、7文字分はどの文字に置換されるかが判明する。fが6次の式という事は未知の係数は7つなのでにフラグフォーマットの各文字を、に対応する暗号文を入れば7元の連立方程式となり、解く事が出来る。

なお、Dに対応するCHARSET.index()が0である事からだけは自明に求まる。よって残りの6つを使って行列に形にして逆行列を左から掛けて解いた(正確にはDに対応する結果を行列に入れると行列式が0になって逆行列が求められないので排除した)。

from string import ascii_lowercase, digits


# GLOBAL (Don't change, touch and abuse them!!)
CHARSET = "DUCTF{}_!?'" + ascii_lowercase + digits
n = len(CHARSET)  # 47
F = GF(n)


def get_known_table():
    enc = open("./output.txt").read().strip()
    known_former = "DUCTF{"
    known_latter = "}"

    ret = {}

    for j, c in enumerate(known_former):
        i = CHARSET.index(c)
        enc_c = enc[j]
        enc_i = CHARSET.index(enc_c)
        ret[i] = enc_i

    i = CHARSET.index(known_latter)
    enc_c = enc[-1]
    enc_i = CHARSET.index(enc_c)
    ret[i] = enc_i

    return ret


def create_matrix():
    mat = []
    w = []
    table = get_known_table()
    for k, v in table.items():
        if k == 0:
            continue

        l = []
        for i in range(6, 0, -1):
            l.append(F(k**i))
        mat.append(l)
        w.append(F(v-1))

    return (mat, w)


def solve(mat, w):
    mat = Matrix(F, mat)
    w = vector(F, w)

    print(mat)
    print(w)

    inv = mat^(-1)
    coefs = inv * w

    return coefs


def check(f):
    table = get_known_table()
    for k, v in table.items():
        assert f(k) == F(v)


def decrypt(f):
    table = {}
    enc = open("./output.txt").read().strip()
    for c in CHARSET:
        i = CHARSET.index(c)
        enc_c = CHARSET[f(i)]
        if enc_c not in table:
            table[enc_c] = []
        table[enc_c].append(c)

    print(len(table))

    flag = ""
    for c in enc:
        cand = table[c]
        if len(cand) == 1:
            flag += cand[0]
            flag += " "
        else:
            flag += "("
            for _c in cand:
                flag += _c
                flag += ", "
            flag = flag[:-2]
            flag += ") "

    return flag


def exploit():
    mat, w = create_matrix()
    coefs = solve(mat,w)
    print(coefs)

    PR.<x> = PolynomialRing(F)
    f = 1
    for e, coef in zip(range(6,0,-1), coefs):
        f += coef * x^e

    check(f)
    flag = decrypt(f)
    print(flag)


if __name__ == "__main__":
    exploit()

実行結果は次の通り

$ sage exploit.sage
[ 1  1  1  1  1  1]
[17 32 16  8  4  2]
[24  8 34 27  9  3]
[ 7 37 21 17 16  4]
[21 23 14 31 25  5]
[32 21 27 28 36  6]
(19, 34, 32, 41, 13, 40)
(41, 15, 40, 9, 28, 27)
35
D (U, !) C (T, t) F { g o 0 d _ 0 l ' _ l 4 g r 4 (f, n, p) g (3, 8) } 

結果に一意性が無いので重複しているところはそれっぽいのを選んだ。

Flag: DUCTF{go0d_0l'_l4gr4ng3}

よく考えたらラグランジュ補間で解けた、どこかで実装済みのはずなのでこれを流用すれば良かった。

treasure §

次のようなスクリプトが動いている。

#!/usr/bin/python3

import re
from Crypto.Util.number import long_to_bytes
from Crypto.Random import random
from secret import REAL_COORDS, FLAG_MSG

FAKE_COORDS = 5754622710042474278449745314387128858128432138153608237186776198754180710586599008803960884
p = 13318541149847924181059947781626944578116183244453569385428199356433634355570023190293317369383937332224209312035684840187128538690152423242800697049469987

def create_shares(secret):
    r1 = random.randint(1, p - 1)
    r2 = random.randint(1, p - 1)
    s1 = r1*r2*secret % p
    s2 = r1*r1*r2*secret % p
    s3 = r1*r2*r2*secret % p
    return [s1, s2, s3]

def reveal_secret(shares):
    s1, s2, s3 = shares
    secret = pow(s1, 3, p) * pow(s2*s3, -1, p) % p
    return secret

def run_combiner(shares):
    try:
        your_share = int(input('Enter your share: '))
        return reveal_secret([your_share, shares[1], shares[2]])
    except:
        print('Invalid share')
        exit()

def is_coords(s):
    try:
        return re.match(r'-?\d+\.\d+?, -?\d+\.\d+', long_to_bytes(s).decode())
    except:
        return False

def main():
    shares = create_shares(REAL_COORDS)
    print(f'Your share is: {shares[0]}')
    print(f'Your two friends input their shares into the combiner and excitedly wait for you to do the same...')

    secret_coords = run_combiner(shares)
    print(f'The secret is revealed: {secret_coords}')
    if not is_coords(secret_coords):
        print('"Hey those don\'t look like coordinates!"')
        print('Your friends grow a bit suspicious, but you manage to convince them that you just entered a digit wrong. You decide to try again...')
    else:
        print('"Let\'s go get the treasure!!"')
        print('Your friends run off to the revealed location to look for the treasure...')
        exit()

    secret_coords = run_combiner(shares)
    if not is_coords(secret_coords):
        print('"This is way too sus!!"')
        exit()

    if secret_coords == FAKE_COORDS:
        print('You\'ve successfully deceived your friends!')

        try:
            real_coords = int(input('Now enter the real coords: '))
            if real_coords == REAL_COORDS:
                print(FLAG_MSG)
            else:
                print('Incorrect!')
        except:
            print('Incorrect!')
    else:
        print('You are a terrible trickster!')

if __name__ == '__main__':
    main()

秘密をとおいて秘密分散をしているようである。シェアを、乱数を、素数をとおくと、次のような式が成り立つ。

$$ \begin{aligned} s_1 &\equiv r_1r_2s \bmod p \cr s_2 &\equiv r_1^2r_2s \bmod p \cr s_3 &\equiv r_1r_2^2s \bmod p \end{aligned} $$

この式からを計算すれば秘密が復元される。

シェアの配布の後、シェアの入力が求められ、そこから復元した秘密が開示される。これがもし特定の形式(つまりis_coords()Trueになる)を満たしていればその場でプログラムは終了する。当然、配られたシェアを与えるとこのような結果になる。

ではis_coords()Falseになるようなシェアを与えるとどうなるのかというとシェアの再入力を求められる。それを提出して復元された秘密が、is_coords()Trueでかつ、REAL_COORDSで無いものであれば座標入力に移り、ここでREAL_COORDSを入力すればフラグが開示sあれる。is_coords()Trueでかつ、REAL_COORDSでないものはFAKE_COORDSとしてソースコード中になるのでこれを利用する。

最初に与えるシェアを、その提出によって復元された秘密をとおくとが成り立つ。ここからを求める事が出来る。

よって、FAKE_COORDSとおくと2回目に送信するシェアをとおけばが成立し、はさっき求めたばかりなのでの3乗根を取る事で求められる。

ついでにREAL_COORDSとおけばから求めることが出来るので最後にこれを送信してフラグを入手する。

使用コードは次の通り(3乗根を求めるのはターミナルで待機させておいたSageの対話環境でやったので無いです、まあ残りは自明なので...)

from pwn import remote
from Crypto.Util.number import long_to_bytes
from xutil.misc import conn_info

# !!GLOBAL!!
# DON'T TOUCH, CHANGE AND ABUSE THEM
FAKE_COORDS = 5754622710042474278449745314387128858128432138153608237186776198754180710586599008803960884
p = 13318541149847924181059947781626944578116183244453569385428199356433634355570023190293317369383937332224209312035684840187128538690152423242800697049469987


def exploit():
    host, port = conn_info("nc pwn-2021.duc.tf 31901")
    sc = remote(host, port)
    sc.recvuntil(b"Your share is: ")
    s1 = int(sc.recvline().strip())

    invalid_s1 = 114514  # <- what?
    sc.recvuntil(b"Enter your share: ")
    sc.sendline(str(invalid_s1).encode())
    print(invalid_s1)

    sc.recvuntil(b"The secret is revealed: ")
    invalid_secret = int(sc.recvline().strip())
    print(invalid_secret)

    r13r23s2 = invalid_s1**3 * pow(invalid_secret, -1, p) % p
    secret = s1**3 * pow(r13r23s2, -1, p) % p
    print("[+] r1^3 * r2^3 * s2 =", r13r23s2)
    print("[+] secret =", secret)
    print("[+] REAL_COORDS:", long_to_bytes(secret))

    sc.interactive()

if __name__ == "__main__":
    exploit()

Flag: DUCTF{m4yb3_th3_r34L_tr34sur3_w4s_th3_fr13nDs_w3_m4d3_al0ng_Th3_W4y.......}

サラッと大切な事がフラグに書いてある

Secuchat §

secuchat.dbというファイルだけが渡される、fileコマンドで調べるとsqlite3のデータベースのダンプらしいので適当なツールで眺めてみる。DB Browser for SQLiteを使用した。

すると概ね次のような構造になっている事がわかる

tablecolumns
Conversationid, initiator, pear, initial_parameters
Messageconversation, timestamp, from_initiator, next_parameters,encrypted_message
Parametersid, encrypted_aes_key_for_initiator, encrypted_aes_key_for_peer
Userusername, rsa_key

Guessすると通信時に相手のrsa_keyで暗号化したencrypted_aes_key_for_[initiator|peer]を使ってメッセージを暗号化し、送信していると思われる。問題のDescriptionからrsa_keyはRSA2048-OAEPに準拠しているキーらしいのでpycryptodomeを使ってパラメータを取り出すと、どれもこれもe = 65537だったのでnが複数ある時の典型である素数の使い回しを疑って確認すると1組だけ共通素数を利用しているのがあった。

というわけである会話に関しては復号出来る事が判明したので総当りを試みる。存在するAES鍵を全部復号し、正しく復号されたもので全メッセージを復号してDUCTFが含まれているものを探したら1つだけあり、そこにフラグが書かれていた。

なお、データベースから鍵やら何やらを取り出すのが面倒だな~って思ってたらkurenaifさんがそれをやってくれるスクリプトを提供してくれました、感謝。

# codes from @kurenaif
# vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
import sqlite3
from Crypto.Cipher import AES, PKCS1_OAEP
from Crypto.PublicKey import RSA
from itertools import combinations
from math import gcd
from string import printable

con = sqlite3.connect('secuchat.db')
cur = con.cursor()

user = []
for row in cur.execute('SELECT * FROM User'):
    user.append({'username': row[0], 'rsa_key': row[1]})

conversation = []
for row in cur.execute('SELECT * FROM Conversation'):
    conversation.append({
        'id': row[0],
        'initiator': row[1],
        'peer': row[2],
        'initial_parameters': row[3]})

message = []
for row in cur.execute('SELECT * FROM Message'):
    message.append({
        'conversation': row[0],
        'timestamp': row[1],
        'from_initiator': row[2],
        'next_parameters': row[3],
        'encrypted_message': row[4]})

parameters = []
keys = []
for row in cur.execute('SELECT * FROM Parameters'):
    keys.append([row[1], row[3]])
    keys.append([row[2], row[3]])
    parameters.append({
        'id': row[0],
        'encrypted_aes_key_for_initiator': row[1],
        'encrypted_aes_key_for_peer': row[2],
        'iv': row[3]})

# for m in message:
#     for key in keys:
#         c = m['encrypted_message']
#         print(key[0])
#         crypto = AES.new(key[0], AES.MODE_CBC, key[1])
#         print(crypto.decrypt(c))

# ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

ns = []
n_to_name = {}
for record in user:
    name = record["username"]
    key = RSA.importKey(record["rsa_key"])
    n = key.n
    e = key.e
    assert e == 0x10001
    ns.append(n)
    n_to_name[n] = name

names_to_cipher = {}
for n1, n2 in combinations(ns, 2):
    g = gcd(n1, n2)
    if g != 1:
        print("[+] Found!!")
        for n in [n1, n2]:
            assert n % g == 0
            p,q = g, n // g
            d = pow(0x10001, -1, (p-1) * (q-1))
            info = (n, 0x10001, d, p, q)
            _key = RSA.construct(info, consistency_check=True)
            names_to_cipher[n_to_name[n]] = PKCS1_OAEP.new(_key)

all_aes_keys = []
for params in parameters:
    iv = params["iv"]
    key1 = params["encrypted_aes_key_for_initiator"]
    key2 = params["encrypted_aes_key_for_peer"]
    all_aes_keys.append((key1, iv))
    all_aes_keys.append((key2, iv))

valid_aes_keys = []
for enc_key, iv in all_aes_keys:
    for _, cipher in names_to_cipher.items():
        try:
            key = cipher.decrypt(enc_key)
        except ValueError:
            continue

        print(len(key), key)
        valid_aes_keys.append((key, iv))

print(f"[+] {len(valid_aes_keys)} keys are decrypted")

for record in message:
    m = record["encrypted_message"]
    for aes_key, iv in valid_aes_keys:
        cipher = AES.new(aes_key, AES.MODE_CBC, iv)
        pt = cipher.decrypt(m)
        print(pt)

Flag: DUCTF{pr1m1t1v35, p4dd1ng, m0d35- wait, 3n7r0py?!}

yadlp §

チームメイトのDronex君との共闘です。

次のようなスクリプトとその実行結果(output.txt)が渡される。

def G_add(A, B):
    x1, y1 = A
    x2, y2 = B
    return ((x1*x2 + D*y1*y2) % p, (x1*y2 + x2*y1 + 2*y1*y2) % p)

def G_mul(A, k):
    out = (1, 0)
    while k > 0:
        if k & 1:
            out = G_add(out, A)
        A = G_add(A, A)
        k >>= 1
    return out

def rand_element():
    while True:
        x = randint(1, p-1)
        d = x^2 * (D + 1) - D
        if (x & 1 == d & 1) and kronecker(d, p) == 1:
            y = (x + sqrt(Zmod(p)(d))) * inverse_mod(D, p) % p
            return (x, y)

D = 13337
p = 17568142778435152362975498611159042138909402642078949814477371651322179417849164549408357464774644525711780515232117470272550677945089719112177956836141583
assert p.nbits() >= 512
assert ((p-1)//2).is_prime() # safe prime

FLAG = open('flag.txt', 'rb').read().strip()
assert len(FLAG) % 8 == 0
M = [int.from_bytes(FLAG[i:i+8], 'big') for i in range(0, len(FLAG), 8)]

G = [rand_element() for _ in M]
c = (1, 0)
for m, gi in zip(M, G):
    c = G_add(c, G_mul(gi, m))

print(f'{D = }')
print(f'{p = }')
print(f'{G = }')
print(f'{c = }')

楕円曲線上の有理点群と似たような曲線上の有理点群が用意され、その上でDLPを解く問題のようである。有理点が幾つか与えられているのでとなるような係数を探したところである事がわかった。

ちなみに、この形であることは行列を上手く立てて行列式を計算したらわかり、それを伝えたらDronexがパラメータまで特定してくれた。

さて、この形は双曲線と似ており、Dronexによれば双曲線を回転させたものらしい。終了後に知ったが、双曲線の一般的な定義が英語版Wikipediaにあった。

というわけで"hyperbolic curve discrete log"とかで調べるとこの論文に辿り着き、これによればの場合、位数はになるらしい、FactorDBにこいつを突っ込んでみると如何にもPohlig-Hellmanが使えそうな感じに素因数分解される。

というわけでBaby-Step and Giant-StepとPohlig-Hellmanアルゴリズムを実装すれば離散対数問題は解ける。これはDronexが書いてくれた。

さて、問題は普通だったらc = flag * Gみたいな形でflagが特定出来る事が多いのだが、今回はそうもいかない。具体的にはフラグを複数(6つ)に分割してのようにおき、同様にGの各要素ものようにおくとのようになっている。

ここでが原始根である事が判明したのでここから各に対して離散対数問題を解いた結果をに対して離散対数問題を解いた結果をとおくと次のようになっている(は整数)。

$$ \begin{aligned} nG_6 &= \left\{\sum_{i=1}^5 (m_ig_i)\right\}G_6 + m_6G_6 \cr \Rightarrow n &\equiv \sum_{i=1}^5 m_ig_i + m_6 \bmod p+1 \cr \Rightarrow n &- \sum_{i=1}^5 m_ig_i - k(p+1) = m_6 \end{aligned} $$

ここから次のような格子(基底は列ベクトル)を組んで右からを掛けるとになる。

$$ \left( \begin{matrix} n & -g_1 & -g_2 & -g_3 & -g_4 & -g_5 & -(p+1) \cr & 1 \cr & & 1 \cr & & & 1 \cr & & & & 1 \cr & & & & & 1 \cr & & & & & & 1 \cr \end{matrix} \right) $$

この格子の体積はだいたいで、は64bitなのでLLLで出てくる小さな基底の上界よりも小さく、遠くもない。よって上手く出てくれそうである。

from pwn import remote
from Crypto.Util.number import long_to_bytes, bytes_to_long
import base64
import json

# !!GLOBAL!!
# DON'T TOUCH, CHANGE AND ABUSE THEM
CONN_INFO = ""
D = 13337
p = 17568142778435152362975498611159042138909402642078949814477371651322179417849164549408357464774644525711780515232117470272550677945089719112177956836141583
G = [(8249149405495350491346934933585109414510787432598250096114687570379053133508711862485128035174547571919256235441699899388417666835599315963507480727674285, 10151966144947987666795899106244951506314545969111450078363915090201899029695981970354886015549281568762501638756950135017679627954071369058817947706039379), (10148658254415475588279956574772196898575718154643967163626694400363009168529645860280959810873028393970853643723425023678857408220330929116526467295542507, 3332426625916817700349475905733631656792492189677766534230576987725484499618918928882667666640821403823057239790395654518704427126712280655564669757208129), (1839326681086939925214853980855626023120414606039474419455499625885357274275815189399880356995376514021329118829062071144818562457268892324773839713533977, 17502649671831125396398431215302241914145169143474764941575812028922929277656849105757332346628455059539582448544435155655055157181361580680672298566085040), (3165955958968203879237344349962533642598441044481692770147807839372942715856047580766073222297692574025922260374409920417665600069665162502514403188432579, 9382092026348588885644924948782239369051861025018411316856012639637274661831713783735305424388410778778529413114167923397187236739639802371814632949741663), (8500294063291124527108623281980255870507549734362604259645984044370658620385351338711051998886026260657132944353675335178871934798200163035190278483491633, 7641198814027309580920446604109217188703337221305342467525089149977505415741300885194767452232679123441594451455097533000754553745051816419202345186703390), (12352685673550986453697035560006632628194788902921398545668828437339873544223895997440585227838919968929669738393535610103382084842900404005432007637193943, 2453949984320580417885537763124479618094084392655766673219227195157341323190069350175423869908524758510177197973709821798974003013596311361995273762475822)]
c = (5388567167658786935158413401674168420144429277172064721472662913563775670320298461949979362402157764272762755236320989018989446360740720072488623102776015, 7420389277336940268114831002964626027945367662485419944369852006741899961686908509331719915794976159062761271182318814519641566938538911041229521838799714)
order = p+1
# from factorDB
factors = [(2, 4), (3, 3), (3271, 1), (18119, 1), (23857, 1), (35923, 1), (1505323, 1), (3036643, 1), (3878597, 1), (7306661, 1), (661850419, 1), (696183413, 1), (737026033, 1), (748888849, 1), (764475661, 1), (790916521, 1), (1000657271, 1), (1016247923, 1), (1213865039, 1), (2090081803, 1), (3882107087, 1), (4012893277, 1)]


def G_add(A, B):
    x1, y1 = A
    x2, y2 = B
    return ((x1*x2 + D*y1*y2) % p, (x1*y2 + x2*y1 + 2*y1*y2) % p)


def G_mul(A, k):
    out = (1, 0)
    while k > 0:
        if k & 1:
            out = G_add(out, A)
        A = G_add(A, A)
        k >>= 1
    return out


# codes from my team mate: Dronex
# vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
def G_inv(g):
    return Matrix(Zmod(p), [[g[0], D*g[1]], [g[1], (g[0]+2*g[1])]]).solve_right(vector(Zmod(p),[1, 0]))


def G_bsgs(base, y, order):
    if base == (1, 0):
        if y != (1, 0):
            raise ValueError("no solution")
        return None # このDLPは意味がない
    assert G_mul(base, order) == (1, 0)
    dic = {}
    m = ceil(sqrt(order))
    z = (1, 0)
    for i in range(m):
        dic[z] = i
        z = G_add(z, base)     

    z = G_mul(G_inv(base), m)
    for i in range(m):        
        if y in dic:
            return (dic[y] + i*m) % order
        y = G_add(y, z)
    raise RuntimeError("maybe bug")


def G_log(base, y):
    ps = []
    ms = []
    for f, d in factors:
        f = f ** d
        phi = (p+1) // f
        bb = G_mul(base, phi)
        yy = G_mul(y, phi)
        order = G_bsgs(bb, yy, f)
        assert G_mul(bb, order) == yy
        if order is not None:
            ps.append(order)
            ms.append(f)
    order = crt(ps, ms)
    assert G_mul(base, order) == y
    return order

# ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^


# search primitive root
# for g in G:
#    is_primitive = True
#    for _p, e in factors:
#        q = order // _p
#        res = G_mul(g, q)
#        if res == (1,0):
#            is_primitive = False
#            break

#    print(f"[{is_primitive}] {g}")

# primitive root
g0 = G[5]

def create_conn():
    host, port = conn_info(CONN_INFO)
    return remote(host, port)


def exploit():
    # c = n1 * G1
    n1 = G_log(g0, c)
    print("[+] n1 =", n1)
    ns = []
    mat = [
        [n1, 0, 0, 0, 0, 0, 0]
    ]

    for i, g in enumerate(G[:-1]):
        _n = G_log(g0, g)
        ns.append(_n)
        row = [-_n, 0, 0, 0, 0, 0, 0]
        row[i+1] = 1
        mat.append(row)

    mat.append([-order, 0, 0, 0, 0, 0, 1])

    print("[+] matrix is created")

    mat = Matrix(ZZ, mat)
    llled = mat.LLL()
    print("[+] LLL is completed")

    for b in llled:
        print("-----" * 20)
        for _c in b:
            _c = abs(_c)
            print(hex(_c), long_to_bytes(_c))



if __name__ == "__main__":
    exploit()

実行結果は次の通り。

[+] n1 = 2317225096600917854828607598415895794303123788026147125642911218463153035917102678452039911900753570983303015546163018331388639671559221312084553221137785
[+] matrix is created
[+] LLL is completed
----------------------------------------------------------------------------------------------------
0x335f444c5021217d b'3_DLP!!}'
0x44554354467b615f b'DUCTF{a_'
0x313333375f687970 b'1337_hyp'
0x337262306c615f6d b'3rb0la_m'
0x333374735f746833 b'33ts_th3'
0x5f6d756c7431706c b'_mult1pl'
0x80929f0d32067e74 b'\x80\x92\x9f\r2\x06~t'
----------------------------------------------------------------------------------------------------

フラグ部分を適当に並び替えて復元した

Flag: DUCTF{a_1337_hyp3rb0la_m33ts_th3_mult1pl3_DLP!!}

OTWhat 1 §

secuchat同様にソースコードは無く、今度はWebページのリンクだけが与えられる。URLと署名を提出するフォームがあり、問題文によればhttps://EVILCODE/<arbitrary path>のようなURLの署名を送ることが出来れば良いらしい。

しかし何で署名されているのかすら全くわからない。こういう時はだいたいページのソースコードを見れば何かあるとHacking with Guessing PlatformことTryHackMeで学んだので見てみるとRSAのPEMファイルがベタ書きしてあった。問題の説明文から多分署名鍵だと思われる。

(ちなみに署名において署名者が使う鍵を「公開鍵」って言ったり検証プロセスを「公開鍵で復号」とか言うとTwitterでFF外から怒られが発生したりするらしい、個人的にはそんなネチネチ目くじらを立てなくても良いとは思いますが...)

これをpycryptodomePublicKey.RSAで読み込むと至って普通の数値であり、secuchat同様に単体の鍵としては何も問題無いようである。

とりあえず(検証結果が)正常なURLと正常な署名が与えられているので、を署名とおいて、先程の署名鍵を使ってを計算してみると多分PKCS#1 V1.5に則ったようなバイト列が入手出来る。

このバイト列の正確な説明はRFC3447等を参照していただくとして、この問題では末尾にURLのハッシュ値が格納されているということが効いてくる。また、使われているハッシュアルゴリズムはSHA3-512である。

このままでは現実世界でも使われている堅牢なスキームに立ち向かう事になるのだが、署名を送信するとページのコメント欄に次のようなものが現れる。

成功時: update.c:69:main(): strcmp(hash, &decrypted_signature[512 - 64]) = 0
失敗時: update.c:69:main(): strcmp(hash, &decrypted_signature[512 - 64]) = 255

この出力から推測するにstrcmpを用いてURLのハッシュ値と署名にくっつけたハッシュ値を比較していると思われる。

加えて、署名をちょっと変える、つまり復号結果がパディングの規準に準拠していないようなものになったものを送ってもこの比較は行われているらしい。

以上の2点からまずハッシュ値がXX 00 ...となるようなURLを用意した上で、適当な署名に対してを計算し、そのハッシュ格納部が同様にXX 00から始まるようなものを探して提出すれば受理されるはずである。

(多分00 ...のようなものでもいけるはず、「ヌル文字同士ってどう比較されるんだろう?」って思ったので安全のために1文字確保した。)

以下のコードでそのような署名とURLを探して提出したら無事にフラグが開示された。

from pwn import remote
from Crypto.Util.number import long_to_bytes, bytes_to_long
from Crypto.PublicKey import RSA
from Crypto.Signature import pkcs1_15
from Crypto.Hash import SHA3_512
import string
import base64
import json
import requests
from xutil.misc import conn_info

# !!GLOBAL!!
# DON'T TOUCH, CHANGE AND ABUSE THEM
CONN_INFO = ""
normal_sig = "ipTX+GMCdI1da1Bwq6BLzMHBgbMVuWoydFa9s+5xsN/0KLsybT8fHuev4vZ1frd4d569mZlRw+PDsC1zy96OeR8uks4aaz9fR8nSbRsDOJICWw1rj1srpyl7xhxYd591/7EZBPH4MMJi66IFZUThLE1RJppbOHv02kkzzE2y79Hi/UoxGdkImZDVfgL+2Ic1ZUqkkff8g4dNKxlgwKfQHgwUfq7W8PaGhk7cfUfPxyo78jGtwXN4XuES23h2pf8aFXnWTZNglJrbXW6xNr28FpKEtyY+Njm0u4mn+LJywYDfQbxhxpxW0vEppxR2zmkW24M2IHRDBfWOkygttL3suwveLARJTIKElDu7diKBErdTYZr5cNDubSbcQMNjMZ18lD+4UNSSwmMMgwNXrI1QAzh4Ndi+QR0HYeUh0oYrtcAe2Mlvx8GYfVWjxW2sLk98jNl5kZcD3HT/oX8LYdaKKVhkLcGzq1AgLhhCNs6ugLv+/SVzFx0Vw5mKi1N1K7OlvEkryG3Fx31tD89A0KKiHHZ0ZHGjJKe/d6N5DIGx0yvTIFX56mwJd+GGv+tGzVN2UZsxJvWrc1yWltCeYGNnl6hBZixBk/DodWpOF8XFM/4y0GGXRjIp9hO1E7ySf33L7sxrUNfCKTN5bfTEQ6OdkxgKMTqqo8is5P95wcz6kt4="
good_url = b"https://GOODCODE/"
evil_url = b"https://EVILCODE/"


def create_conn():
    host, port = conn_info(CONN_INFO)
    return remote(host, port)


def search_zero_path():
    l = 1
    found = False
    while True:
        print(l)
        for c in string.ascii_lowercase:
            s = c * l
            m = evil_url + s.encode()
            h = SHA3_512.new(m).digest()
            if h[1] == 0:
                print("[+] Found!!")
                print(f"[+] [{h[:2]}] in sha3-512({m})")
                return (m, h[:2])

        l += 1



def create_fake_sig(n, e, target_bytes):
    sig = n // 2
    while True:
        m = long_to_bytes(pow(sig, e, n))
        if len(m) != 512:
            sig += 1
            continue

        h = m[448:]
        if h[:2] == target_bytes:
            return sig

        sig += 1


def exploit():
    pem = open("pubkey.pem").read().strip()
    key = RSA.importKey(pem)
    print(key.n.bit_length())
    print(key.e)
    sig = base64.b64decode(normal_sig)
    res = pow(bytes_to_long(sig), key.e, key.n)
    res = long_to_bytes(res)
    
    i = res.index(b"\x00")
    t = res[i+1:]
    sha512_bytes = long_to_bytes(0x3051300d060960864801650304020a05000440)
    assert sha512_bytes in t
    h = t[len(sha512_bytes):]
    print(h)
    print(h.hex())

    hash_512 = SHA3_512.new(good_url)
    _h = hash_512.digest()
    print(_h)

    target_url, target_bytes = search_zero_path()
    fake_sig = create_fake_sig(key.n, key.e, target_bytes)
    fake_sig = base64.b64encode(long_to_bytes(fake_sig))

    print(f"[+] url: {target_url}")
    print(f"[+] sig: {fake_sig}")


if __name__ == "__main__":
    exploit()

Flag: DUCTF{https://wiibrew.org/wiki/Signing_bug#L0L_memcmp=strcmp}

フラグ記載のURLだと似たような脆弱性がiOSにあったらしい。

ちなみにFirst Bloodでした。今年で3件目です。

OTWhat 2 §

OTWhat 1同様にWebページのリンクだけ渡される。説明文を見ると今度は署名がECDSAになり、使われているのはP-256曲線ということがわかる。

今回もコメントでデバッグ出力が出るのだが、URLのハッシュ値しか与えられない。ちなみに使われているアルゴリズムは1同様SHA3-512である。

まず最初に署名からを抽出するところである。これは何故か1年前に購入していたプログラミングビットコインこの記事を参考にして抽出した。

この結果を観察すると1組の署名においてが一致することがわかった。を署名時に使われるnonceとおくと、(はP-256曲線の生成元)のx座標がになるため、同じが使われている事になる。

という事はsame nonce attackが使えそうである。この攻撃に関しては何故か日本語Wikipediaが詳しいのでそちらを参照していただきたい。

これを利用すれば秘密鍵が特定出来るので任意のメッセージを署名し放題になる。これで無事に解ける...と思いきやそうもいかなかった。

署名する際にメッセージのハッシュ値を用いるのだが、今回使っているのはSHA3-512であり、P-256曲線のパラメータは256bitである事からハッシュ値をこのサイズにまで切り詰める必要がある。

これは単純にP-256曲線の位数で割るだけでは解決しない。Wikipediaに書いてあるように上位256bitを用いる必要がある。

これを最初無視していたせいで無事に計算出来たのx座標が重複した署名のにならないという事態が発生した。

またそれに気づいてもハッシュ値の加工にも苦戦した。前述の通り、ハッシュ値の上位256bitを用いるのだがこれは数値では無く「digestされたバイト列で上位64bit」の事を意味する。つまり、数値で上位256bitだけを取っていると例えば00 ...のようなハッシュ値では00を無視してしまうので異なる結果が得られてしまう。

結局この辺はPythonのfastecdsaの実装を見たりして解決した。

下記コードのeがハッシュ値であり、mpz_fdiv_q_2exp関数を用いて下位256bitを切り捨てていることが分かる。

if(digestBits > orderBits) {
        mpz_fdiv_q_2exp(e, e, digestBits - orderBits);
    }

これで無事にハッシュ値を切り詰めた結果が得られたのでを求めることが出来た。後は先程名前を出したfastecdsaを用いてhttps://EVILCODE/を署名し、その結果を形式に沿うようにバイト列にしてbaes64エンコードしたものを提出するとフラグが得られた。

from pwn import remote
from Crypto.Util.number import long_to_bytes, bytes_to_long
from fastecdsa.curve import P256 as _curve
from fastecdsa.ecdsa import sign, verify
from Crypto.Hash import SHA3_512
from hashlib import sha3_512
import string
import base64
import json
import requests
from xcrypto.ec import EllipticCurve, ECDSA, ECPoint
from xcrypto.mod import is_quadratic_residue


# !!GLOBAL!!
# DON'T TOUCH, CHANGE AND ABUSE THEM
p = _curve.p
a = _curve.a
b = _curve.b
order = _curve.q
gx = _curve.gx
gy = _curve.gy
G = _curve.G
# mycurve = EllipticCurve(a, b, p)
# mycurve.set_order(order)
# G = ECPoint(gx, gy, mycurve)
evil_url = b"https://EVILCODE/"


def get_data_from_log():
    all_sig = ""
    ret = []
    raw_log = open("log.txt").read().strip()
    lines = raw_log.split("\n")
    for line in lines:
        url, sig = line.split(" ")
        ret.append((url.strip(), base64.b64decode(sig.strip())))
        all_sig += sig.strip()

    return ret


def exploit():
    sigs = []
    url_and_sig = get_data_from_log()
    for url, sig in url_and_sig:
        header = sig[:4]
        assert header[0] == 0x30
        r_header = sig[2:4]
        assert r_header[0] == 0x02
        r_length = r_header[1]
        r = sig[4:4+r_length]
        assert len(r) == r_length

        s_idx = 4+r_length
        s_header = sig[s_idx:s_idx+2]
        assert s_header[0] == 0x2
        s_length = s_header[1]
        s = sig[s_idx+2:]
        assert len(s) == s_length

        r = bytes_to_long(r)
        s = bytes_to_long(s)
        z = SHA3_512.new(url.encode()).digest()
        z = bytes_to_long(z)
        z //= 2**256
        # z = z % (2**256)
        assert r < order
        assert s < order
        # print(sig.hex())
        # print(f"{r=}")
        # print(f"{s=}")

        sig = (r,s,z, url)
        sigs.append(sig)

    rs = []
    dupl_r = None
    for r, s, z, _ in sigs:
        if r in rs:
            print("[+} Duplicated Nonce!!")
            dupl_r = r

        rs.append(r)

    dupl_sigs = list(filter(lambda sig: sig[0] == dupl_r, sigs))

    print(dupl_sigs)
    (r1, s1, z1, u1), (r2, s2, z2, u2) = dupl_sigs
    assert r1 == r2
    s_diff = (s1 - s2) % order
    z_diff = (z1 - z2) % order
    k = z_diff * pow(s_diff, -1, order) % order

    assert (k*G).x == r1

    d  = (s1 * k - z1) * pow(r1,-1, order) % order
    _d = (s2 * k - z2) * pow(r2,-1, order) % order

    assert d == _d


    # check d
    # myecdsa = ECDSA(mycurve, G, d*G, d)
    # for r, s, z, _ in sigs:
    #   print(myecdsa.verify(r, s, z))

    Q = d*G
    for r, s, z, url in sigs:
        print(verify((r,s), url, Q, hashfunc=sha3_512))

    # evil_url = b"https://GOODCODE/update/abcd0b64039c6eff5a1cbf50f24eb6c62f25f8f39da28fdc112433b93ada6018"
    _r, _s = sign(evil_url, d, hashfunc=sha3_512)
    b_r = long_to_bytes(_r)
    if b_r[0] >= 0x80:
        b_r = b"\00" + b_r
    b_s = long_to_bytes(_s)
    if b_s[0] >= 0x80:
        b_s = b"\00" + b_s

    fake_r = b"\x02" + len(b_r).to_bytes(1, "little") + b_r
    fake_s = b"\x02" + len(b_s).to_bytes(1, "little") + b_s

    fake_rs = fake_r + fake_s

    sig_len = len(fake_rs)
    sig = b"\x30" + sig_len.to_bytes(1, "little") + fake_rs

    print(sig)
    print("[+] URL:", evil_url)
    print("[+] signature:", base64.b64encode(sig))


if __name__ == "__main__":
    exploit()

Flag: DUCTF{27C3 Console Hacking 2010 (PS3 3p1c F41l)}

PS3でも同様の攻撃が出来たという話は割と有名

ちなみにSecond Bloodでした。OTWhat 1同様に純粋な数学力でなく、ググり力と仕様を読み込む力とGuessing力が問われた問題だったのでもしかするとCryptoよりもバグハントとかの方が向いているのかもしれないです。

感想 §

josephさんの作問力が量と質共に高く驚きました。背景の数学を知らなくても一応解けるんですが、作問者Writeupを見るとどの問題もそれをしっかりと解説しており、全CTF作問者のお手本となるような問題と作問者Writeupでした。

他の問題に関しては、一部問題がソース未配布でGuessing要素があったりしましたがそれ以上に「解答者が出た問題に対してヒントを開示する」という事が気になりました。これまではヒントを出される前に解いた事が無かったのでそれに言及しているのを見ても何も感じませんでしたが、実際やられてみると複雑な気持ちでした。(もっとも、そう感じるだけ強くなったと思い込むべきなのかもしれませんが...)

ちなみに粘着質なのでこの件はSurveyにもCTFtimeにもTwitterにも書きました、このブログで4回目の言及です。

それはともかくとしてCTF全体としては(主にjosephさんの問題のおかげで)楽しめました。来年も開催/作問してください。

I belong to "joseph fan club". Thanks so much!!