VolgaCTF 2024 Qualifier Writeup

CTF writeup

この大会は2024/3/31 0:00(JST)～2024/4/1 0:00(JST)に開催されました。
今回もチームで参戦。結果は295点で257チーム中100位でした。
自分で解けた問題をWriteupとして書いておきます。

PQ (crypto)

Nを素因数分解する。

N = 11492900508587989954531440332263108922084741581974222102472118047768380430540353920289746766137088552446667728704705825767564907436992191013818658710263387461050109924538094327413211095570408951831804511312664061115780934181616871945218328272318074413219648490794574757471025686956697500105383560452507555043577475707379430674941097523563439495291391376433292863780301364692520578080638180885760050174506019604723296382744280564071968270446660250234587067991312783613649361373626181634408704506324790573495089018767820926445333763821104985493381745364201010694528200379210559415841578043670235152463040761395093466757
  * 11492900508587989954531440332263108922084741581974222102472118047768380430540353920289746766137088552446667728704705825767564907436992191013818658710263387461050109924538094327413211095570408951831804511312664061115780934181616871945218328272318074413219648490794574757471025686956697500105383560452507555043583332241787496934511124508164581479242699938954664986778778089174462752116916848703843649899098070668669678312274875686923774909987821333120312320645501581685293243247702323898532381890355435523179413889042894904950054113266062322984191234608909924029167449813744492456171898301189923726970620918920525920821

あとは通常通り、RSA暗号の復号を行う。

#!/usr/bin/env python3
from Crypto.Util.number import *

with open('output', 'r') as f:
    params = f.read().splitlines()

N = int(params[0])
c = bytes_to_long(eval(params[1]))
e = 65537

p = 11492900508587989954531440332263108922084741581974222102472118047768380430540353920289746766137088552446667728704705825767564907436992191013818658710263387461050109924538094327413211095570408951831804511312664061115780934181616871945218328272318074413219648490794574757471025686956697500105383560452507555043577475707379430674941097523563439495291391376433292863780301364692520578080638180885760050174506019604723296382744280564071968270446660250234587067991312783613649361373626181634408704506324790573495089018767820926445333763821104985493381745364201010694528200379210559415841578043670235152463040761395093466757
q = 11492900508587989954531440332263108922084741581974222102472118047768380430540353920289746766137088552446667728704705825767564907436992191013818658710263387461050109924538094327413211095570408951831804511312664061115780934181616871945218328272318074413219648490794574757471025686956697500105383560452507555043583332241787496934511124508164581479242699938954664986778778089174462752116916848703843649899098070668669678312274875686923774909987821333120312320645501581685293243247702323898532381890355435523179413889042894904950054113266062322984191234608909924029167449813744492456171898301189923726970620918920525920821
assert N == p * q

phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m = pow(c, d, N)
flag = long_to_bytes(m).decode()
print(flag)

VolgaCTF{0x8922165e83fa29b582f6a252cb337a05}

QR (crypto)

フラグ入りのQRコードに対する処理の概要は以下の通り。

・generator = LFSR(register, branches)
　・generator.register = register(未知)
　・generator.branches = branches(未知)
　・generator.n: registerの長さ
・image: QRコード画像オブジェクト
・w: QRコード画像の幅
・h: QRコード画像の高さ
・new_image: 新しい画像オブジェクト
・pixels: QRコード画像ピクセルデータ
・各ピクセルについて以下を実行
　・pixel: 白の場合1、黒の場合0
　・next_bit = generator.next_bit()
　・encrypted = pixel ^ next_bit
　・new_imageにencrypted * 255を設定

画像のサイズから2x2で1つのセルを表していると推測できる。元の画像の左上から右に0000000000000011になっているはず。
16個分のregisterを割り出すと以下のようになる。

[1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1]

registerの長さを総当たりで考え、推測する。

・長さ1の場合、register = [1]、branches = [1]
　ret = 1
　new = 0
　new ^= 1 = 1
　register = [1] -> NG

・長さ2の場合、register = [0, 1]、branches = [1]
　ret = 1
　new = 0
　new ^= 0 = 0
　register = [0, 0]
　ret = 0
　new = 0
　new ^= 0 = 0
　　：
　0しか出てこない -> NG
　※長さ3～6も同様

・長さ7の場合、register = [1, 0, 0, 0, 0, 0, 1]
　-> branches = [1, 3, 4, 5, 7] -> OK

とりあえずこの前提で復号してみる。

#!/usr/bin/env python3
from PIL import Image

class LFSR:
    def __init__(self, register, branches):
        self.register = register
        self.branches = branches
        self.n = len(register)

    def next_bit(self):
        ret = self.register[self.n - 1]
        new = 0
        for i in self.branches:
            new ^= self.register[i - 1]
        self.register = [new] + self.register[:-1]

        return ret

image = Image.open('qr.png')
w = image.width
h = image.height

pixels = image.load()

## research ##
register = []
for i in range(16):
    pixel = pixels[i, 0] // 255
    if i < 14:
        register.append(pixel ^ 0)
    else:
        register.append(pixel ^ 1)
register = register[::-1]
print('[+] register sequence:', register)

## decrypt ##
register = [1, 0, 0, 0, 0, 0, 1]
branches = [1, 3, 4, 5, 7]

generator = LFSR(register, branches)

org_image = Image.new(image.mode, image.size)

for y in range(h):
    for x in range(w):
        pixel = pixels[x, y] // 255
        next_bit = generator.next_bit()
        decrypted = pixel ^ next_bit

        org_image.putpixel((x, y), decrypted * 255)

org_image.save('flag_qr.png', image.format)


復号した結果、QRコードになったので、コードリーダで読み取る。

VolgaCTF{0x05d76db737ac94674907136eb1f15f02}

Feedback (misc)

アンケートに答えたら、フラグが表示された。

VolgaCTF{5b84a0a9f6ba8d171b4a5633a4457a1f}