writeup

tkbctf4.md

monocrome bar

リンクをクリックしてみるとサイズが72900*1の細長い白黒png画像が手に入った
sqrt(72900)を求めてみるとぴったり270だったので試しに折り返してみた

#! /usr/bin/python
#coding :utf-8

import Image

img = Image.open("monochrome_bar.png")

newImg = Image.new("1", (270, 270))

pixImg = img.load()
pixNewImg = newImg.load()

for i in range(270):
    for j in range(270):
        pixNewImg[j, i] = pixImg[i * 270 + j, 0]

newImg.save("monochrome_square.png")

QRcodeが生成できたので読み取ってみた
RkxBR3tDaDF0M2sxazBrMXNoMW4tbTRufQ==
base64でdecodeすると
FLAG{Ch1t3k1k0k1sh1n-m4n}

gradius

x86-64(動かせない)だけどELFなのでとりあえずobjdumpしてmainから読んでた
.rodataセクションに"FLAG{%s}"なる文字列を見つけたので遡ってみると，
%sで表示する文字列をxorで作っているっぽい
というわけでxorしているデータを特定してひたすらに逆算してみた
FLAG{!!D4GG3R!!}

rcrypto

問題のzipを解凍するとencrypt.pyとresult.txtが得られる

import struct

N = 0xcd892c64f1803742a89e68567aea60283066b368d2c2454ad55f740fb0ff8e98e03f70cd9a2c9168294eee89a9f995d2596f2c0be881bfbfa72cccbb18a77287134e2ffc89e7bce766cca9136074a19f6807c3ff51e5cf53ec79838067cbefac809fccbbe2c1c4d170f3be58b34b9c3dfaeb2914341697d6503a826716073f9808b91c747030e2cdeaf20620b269c701d5ce96623c95c983678fd1175243b9eda7f6a310b4ccfd6c69fa836adb82271c56aa7ca267c1d47e64e69a0c3541f63432b4d75b881c1694a07b546eaee036521213967201cd91ff6a4e1e7c89027eb57096f2e3e5cd274d5cd272be44435b21648538f31760b4f8b50cbcd42f0873d5

def encrypt(M, B):
    return M * (M + B) % N

if __name__ == '__main__':
    s = open('flag', 'r').read()
    tkbctf = struct.unpack('<2I', 'tkbctf4\0')
    flag = int(s.encode('hex'), 16)
    print "1: %d" % encrypt(flag, tkbctf[0])
    print "2: %d" % encrypt(flag, tkbctf[1])

1: 2302864379938375384787522457289953058762346515694717964988017701221632252068998721016780659512789645178039929483162432085291148128875938650563974652974607897108753247761759018159346471819526717450317624121005691577913298753406802656066710989103644069541226797561238591832001786871030959032526532824897381416113004865029523158041337929652792421367459253385313006702525506606665513325657107841851439410104118856833250549528309345600994438901026890993789031255524302387252820866177521016309668779564405438776186649089481716393902512049059686799788362854701624870108840227739233423565617147635810535089953364777452765391
2: 869821841437664579273841208702057334636310328092375384661895122870843280009327763942775667106913326453781559554453279690395959752854296081023254897131426262762124201024166059200347755016000992120349762030587256929453375758557293418778029046615012379759165445526510048231152939113590563355048407714266168812177988203610092674509339069396233061882191910214456155546393848777696938097852335164090584476493820466258280954729469300306911409684786367255431603152145902151223834708442564731418184393252984714050882676106734102146980036229108895568198263271905480015122766218776429803994468521463000793677542363327966917714

ここで数学の話
定数をa, bとする
M*(M+a) % N = c % N, M*(M+b) % N = d % N とすると
{M*(M+a)-M*(M+b)} % N = (c-d) % N
これを整理すると
M(a-b) % N = (c-d) % N
(a-b)とNが互いに素なら，両辺に (a-b)e % N = 1 % N となるeを掛けてやれば
M(a-b)e % N = M % N = (c-d)e % N となってMが求まりそう
eは拡張ユークリッドの互除法を使えば求められるはず

#! /usr/bin/python
#coding: utf-8

import struct

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

def gcd2(a, b):
    if b == 0:
        u = 1
        v = 0
    else:
        q = a / b
        r = a % b
        (u0, v0) = gcd2(b, r)
        u = v0
        v = u0 - q * v0
    return (u, v)

a, b = struct.unpack('<2I', 'tkbctf4\0')
N = 0xcd892c64f1803742a89e68567aea60283066b368d2c2454ad55f740fb0ff8e98e03f70cd9a2c9168294eee89a9f995d2596f2c0be881bfbfa72cccbb18a77287134e2ffc89e7bce766cca9136074a19f6807c3ff51e5cf53ec79838067cbefac809fccbbe2c1c4d170f3be58b34b9c3dfaeb2914341697d6503a826716073f9808b91c747030e2cdeaf20620b269c701d5ce96623c95c983678fd1175243b9eda7f6a310b4ccfd6c69fa836adb82271c56aa7ca267c1d47e64e69a0c3541f63432b4d75b881c1694a07b546eaee036521213967201cd91ff6a4e1e7c89027eb57096f2e3e5cd274d5cd272be44435b21648538f31760b4f8b50cbcd42f0873d5

# m * (m + a) % n = a_
a_ = 2302864379938375384787522457289953058762346515694717964988017701221632252068998721016780659512789645178039929483162432085291148128875938650563974652974607897108753247761759018159346471819526717450317624121005691577913298753406802656066710989103644069541226797561238591832001786871030959032526532824897381416113004865029523158041337929652792421367459253385313006702525506606665513325657107841851439410104118856833250549528309345600994438901026890993789031255524302387252820866177521016309668779564405438776186649089481716393902512049059686799788362854701624870108840227739233423565617147635810535089953364777452765391

# m * (m + b) % n = b_
b_ = 869821841437664579273841208702057334636310328092375384661895122870843280009327763942775667106913326453781559554453279690395959752854296081023254897131426262762124201024166059200347755016000992120349762030587256929453375758557293418778029046615012379759165445526510048231152939113590563355048407714266168812177988203610092674509339069396233061882191910214456155546393848777696938097852335164090584476493820466258280954729469300306911409684786367255431603152145902151223834708442564731418184393252984714050882676106734102146980036229108895568198263271905480015122766218776429803994468521463000793677542363327966917714

d, _ = gcd2(a - b, N)
flag = (a_ - b_) * d % N
flag = hex(flag).replace("0x", "").replace("L", "").decode('hex')
print flag

FLAG{R4b1n cryp705y573m 15 v3ry 1n73r3571ng!!!}

Just Do It?

x86-64だしPEなのでfdbgにかけてちまちま動作を追っていく
どうやらgradiusと同じくひたすらxorする感じらしいのでひたすらxorして正解の文字列を求める 4つのstageからなっていて，それぞれ正解の文字列は
"SYNT{Ra" "wblrqZl" "SvefgCe" "boyrz?}"
これらをつなげてrot13decodeすると
FLAG{EnjoyedMyFirstProblem?}

お粗末さまでした