Harekaze mini CTF 2020 Writeup

11-01-2021 - 3 minutes, 3 seconds -
Crypto CTF Writeup 2020 Web

scoreboard

Wani Hackaseで参加して1032点の23位。

開始時刻ちょっと後に、予定を入れてしまっていたのでそんなに取り組めなかったけど勉強になりました。問題設定はシンプルだけど一筋縄では解けない問題が好きなので楽しかったです。 Harekazeの方々運営ありがとうございました🙇🙇

rsa [Crypto]

\[ \begin{eqnarray} n &=& pq \\ e &=& 65537 \\ c_1 &\equiv& m^e \mod n \\ c_2 &\equiv& (p+q)^e \mod n \\ c_3 &\equiv& (p-q)^e \mod n \\ \end{eqnarray}\]

が与えられるので、\(m(={\rm flag})\)を復元する。

\(c_2, c_3\) は実際に展開すると

\[ c_2 \equiv p^e + q^e \mod n \\ c_3 \equiv p^e - q^e \mod n\]

であるから、\((c_2+c_3) / 2 \equiv p^e \mod n\) を得る。 \(\gcd(n, p^e) = p\) となるので、あとは秘密鍵を復元して復号する。

import shutil
import math

shutil.copy("output.txt", "output.py")

from output import *

p = math.gcd((c2 + c3) // 2, n)
q = n // p
assert p * q == n

d = pow(e, -1, (p - 1) * (q - 1))
flag = pow(c1, d, n)
print(bytes.fromhex(f'{flag:x}'))

freshman's dreamという命名、かなりセンスを感じる

QR [Crypto]

近傍?4マスの情報を元にオリジナルのQRコードを復元する。 QRコードには確定パターンがあるので、そこを足がかりに探索するようなコードを書く。

import ast
from itertools import product

with open("output.txt") as f:
    qr = ast.literal_eval(f.read())

size = len(qr) + 1

# 0: white, 1: black, 2: pending
flag = [[2 for _ in range(size)] for _ in range(size)]

def fill(x1, y1, x2, y2, status):
    for i in range(y1, y2 + 1):
        for j in range(x1, x2 + 1):
            flag[i][j] = status

fill(0, 0, 7, 7, 0)
fill(0, 0, 6, 6, 1)
fill(1, 1, 5, 5, 0)
fill(2, 2, 4, 4, 1)

fill(size - 8, 0, size - 1, 7, 0)
fill(size - 7, 0, size - 1, 6, 1)
fill(size - 6, 1, size - 2, 5, 0)
fill(size - 5, 2, size - 3, 4, 1)

fill(0, size - 8, 7, size - 1, 0)
fill(0, size - 7, 6, size - 1, 1)
fill(1, size - 6, 5, size - 2, 0)
fill(2, size - 5, 4, size - 3, 1)

for i in range(size - 2 * 7):
    flag[6][i + 7] = i % 2
    flag[i + 7][6] = i % 2

for _ in range(100):
    for i, j in product(range(size - 1), repeat=2):
        neighbor = ((i, j), (i + 1, j), (i, j + 1), (i + 1, j + 1))
        white = [(I, J) for I, J in neighbor if flag[I][J] == 0]
        black = [(I, J) for I, J in neighbor if flag[I][J] == 1]
        pending = [(I, J) for I, J in neighbor if flag[I][J] == 2]
        if pending:
            if qr[i][j] == 0:
                if len(white):
                    for I, J in pending:
                        flag[I][J] = 0
                if len(black):
                    for I, J in pending:
                        flag[I][J] = 1

            if len(white) == 4 - qr[i][j]:
                for I, J in pending:
                    flag[I][J] = 1

            if len(black) == qr[i][j]:
                for I, J in pending:
                    flag[I][J] = 0

flag = "\n".join("".join(map(str, line)).replace("2", "1") for line in flag)
flag = flag.replace("0", "  ").replace("1", "██")
print(flag)

なんだかんだ最近QR問題って見かけない気がする?解いてないだけかもしれない

Wilhelmina says [Crypto]

\(y_i = z_i + \hat{z_i}\) (\(\hat{z_i}\)は未知)とすると、

\[ \begin{eqnarray} z_i+\hat{z_i} &\equiv& x_im \mod p \\ \hat{z_i} - x_im + z_i &\equiv& 0 \mod p \end{eqnarray}\]

このPDFの4.1 The hidden number problem に書いてある格子でそのまま解けそうなので採用した。

LLL後に\(\hat{z_i}\)が復元されていることが期待されるので、これを利用してflagを復元する。

from Crypto.Util.number import *

n = 5
t = 311
p = 10701453001723144480344017475825280248565900288828152690457881444597242894870175164568287850873496224666625464545640813032441546675898034617104256657175267
xs = [7891715755203660117196369138472423229419020799191062958462005957463124286065649164907374481781616021913252775381280072995656653443562728864428126093569737, 9961822260223825094912294780924343607768701240693646876708240325173173602886703232031542013590849453155723572635788526544113459131922826531325041302264965, 7554718666604482801859172289797064180343475598227680083039693492470379257725537783866346225587960481867556270277348918476304196755680361942599070096169454, 5460028735981422173260270143720425600672799255277275131842637821512408249661961734712595647644410959201308881934659222154413079105304697473190038457627041, 8621985577188280037674685081403657940857632446535799029971852830016634247561494048833624108644207879293891655636627384416153576622892618587617669199231771]
zs = [2445678981428533875266395719064486897322607935804981139297064047499983860197487043744531294747013763946234499465983314356438694756078915278742591478169600, 6687262023290381303903301700938596216218657180198116459210103464914665663217490218525920847803014050091904359944827298080739698457116239163607201903280128, 9144515139738671257281335253441395780954695458291758900110092599410878434836587336752247733779617485272269820837813132894795262162555273673307500761317376, 7005359236736263649027110410188576532095684249796929034336135801107965605961711614006159825405033239188458945408990893269975105260656611838449490684018688, 4638291797440604671051855904609667375394026160401800326727058461541969151082727684535417653507524951373254537356784859777006179731400955193335900924805120]

M = 1<<400
B = matrix(ZZ, [
    [    p,    0,    0,    0,    0,    0,    0],
    [    0,    p,    0,    0,    0,    0,    0],
    [    0,    0,    p,    0,    0,    0,    0],
    [    0,    0,    0,    p,    0,    0,    0],
    [    0,    0,    0,    0,    p,    0,    0],
    [xs[0],xs[1],xs[2],xs[3],xs[4], M//p,    0],
    [zs[0],zs[1],zs[2],zs[3],zs[4],    0,    M],
]).LLL()

for b in B:
    for i in range(n):
        if b[-1] != M:
            continue
        x, z_, z = map(abs, (xs[i], b[i], zs[i]))
        y = z+z_
        flag = y*pow(x, -1, p)%p
        flag = bytes.fromhex(f'{int(flag):x}')
        if b'Harekaze' in flag:
            print(flag)
            exit(0)

まだ格子何もわからん状態だけれども、問題解こうとして調べたり試行錯誤したりしているうちに理解が深まった(気がする)

What time is it now? [Web]

formatパラメータに好きなpayloadを送れるので、 "date '+" . escapeshellcmd($format) . "' 2>&1" をうまく利用してflagを読み出す。 とりあえず別のコマンドを割り込ませられないか考えたが、諸々escapeされているので難しい。 ちゃんとdateの仕様を確認しようとman date したら-fオプションが使えそうだったのでこれを利用してpayloadを組んだ。dateのformatの部分は適当でも通る。

${URL}?format=' -f /flag'

やっぱりDockerfile等含めソースコード配布されているのは非本質が排除されていて嬉しい