SECCON Beginners CTF 2019 writeup

はじめに

yharimaで参加し、11th / 666 placeでした。(自分は実質何もやってない)
今回はbinary強い人とweb強い人がチームにいたのでcryptoに専念してみた。(2問しか解けなかったので死にたい...) f:id:kent056-n:20190526175444p:plain

他のメンバーのブログはこちら。 yuta1024.hateblo.jp

lai.hateblo.jp

So Tired

問題文。

最強の暗号を作りました。 暗号よくわからないけどきっと大丈夫!

File: so_tired.tar.gz

Fileを展開するとBase64エンコードされた文字列(めっちゃ長い)が書かれたテキストファイルが出てくる。
とりあえずデコードしてファイルとして保存してみる。

$ cat encrypted.txt | base64 -D > outdata

fileコマンドを実行してみると、zlib形式であることがわかる。

$ file outdata
outdata: zlib compressed data

zlibを展開すると、またBase64エンコードされた文字列(めっちゃ長い)が書かれたテキストファイルが出てくる。
以降、zlib -> Base64エンコード文字列 -> zlib -> ... の繰り返しになり、クッソめんどくさいので問題文とも一致する。
以下、solverです。適当に"ctf4b"が含まれている箇所でbreakするようにしました。

import zlib
import base64

i = 1
while True:
    data = open("outdata" + str(i - 1), "r")
    s = zlib.decompress(data.read())
    data.close()
    if ("ctf4b" in s) :
        print s
        break

    if ("ctf4b" in base64.b64decode(s)) :
        print base64.b64decode(s)
        break

    with open("outdata" + str(i), mode='w') as f:
        f.write(base64.b64decode(s))
    i += 1

上記のsolverを実行すると500個くらいファイルがブチまけられて最悪な気持ちになるけどフラグがでてきます。

ctf4b{very_l0ng_l0ng_BASE64_3nc0ding}

Party

以下、問題文。

Let's 暗号パーティ

File: party.tar.gz

tarを展開すると、encrypt.pyとencryptedというファイルが出てくる。それぞれのファイルの中身は以下の通り。
encrypt.py

from flag import FLAG
from Crypto.Util.number import bytes_to_long, getRandomInteger, getPrime


def f(x, coeff):
    y = 0
    for i in range(len(coeff)):
        y += coeff[i] * pow(x, i) # i = 0, 1, 2
    return y


N = 512
M = 3
secret = bytes_to_long(FLAG)
assert(secret < 2**N)

coeff = [secret] + [getRandomInteger(N) for i in range(M-1)]
party = [getRandomInteger(N) for i in range(M)]

val = map(lambda x: f(x, coeff), party)
output = list(zip(party, val))
print(output)

encrypted

[(5100090496682565208825623434336918311864447624450952089752237720911276820495717484390023008022927770468262348522176083674815520433075299744011857887705787, 222638290427721156440609599834544835128160823091076225790070665084076715023297095195684276322931921148857141465170916344422315100980924624012693522150607074944043048564215929798729234427365374901697953272928546220688006218875942373216634654077464666167179276898397564097622636986101121187280281132230947805911792158826522348799847505076755936308255744454313483999276893076685632006604872057110505842966189961880510223366337320981324768295629831215770023881406933), (3084167692493508694370768656017593556897608397019882419874114526720613431299295063010916541874875224502547262257703456540809557381959085686435851695644473, 81417930808196073362113286771400172654343924897160732604367319504584434535742174505598230276807701733034198071146409460616109362911964089058325415946974601249986915787912876210507003930105868259455525880086344632637548921395439909280293255987594999511137797363950241518786018566983048842381134109258365351677883243296407495683472736151029476826049882308535335861496696382332499282956993259186298172080816198388461095039401628146034873832017491510944472269823075), (6308915880693983347537927034524726131444757600419531883747894372607630008404089949147423643207810234587371577335307857430456574490695233644960831655305379, 340685435384242111115333109687836854530859658515630412783515558593040637299676541210584027783029893125205091269452871160681117842281189602329407745329377925190556698633612278160369887385384944667644544397208574141409261779557109115742154052888418348808295172970976981851274238712282570481976858098814974211286989340942877781878912310809143844879640698027153722820609760752132963102408740130995110184113587954553302086618746425020532522148193032252721003579780125)]

encryptedの中身はpartyとvalであることがわかる。また、FLAG(secret)は coeff[0]に入っていることがわかる。つまり、partyとvalからcoeffを導出できれば良さそうということに気づく。
そして、よくみると方程式を立てることができ、導出可能であることがわかる。以下、solver。

from sympy import *

party0 = 5100090496682565208825623434336918311864447624450952089752237720911276820495717484390023008022927770468262348522176083674815520433075299744011857887705787
val0 = 222638290427721156440609599834544835128160823091076225790070665084076715023297095195684276322931921148857141465170916344422315100980924624012693522150607074944043048564215929798729234427365374901697953272928546220688006218875942373216634654077464666167179276898397564097622636986101121187280281132230947805911792158826522348799847505076755936308255744454313483999276893076685632006604872057110505842966189961880510223366337320981324768295629831215770023881406933
party1 = 3084167692493508694370768656017593556897608397019882419874114526720613431299295063010916541874875224502547262257703456540809557381959085686435851695644473
val1 = 81417930808196073362113286771400172654343924897160732604367319504584434535742174505598230276807701733034198071146409460616109362911964089058325415946974601249986915787912876210507003930105868259455525880086344632637548921395439909280293255987594999511137797363950241518786018566983048842381134109258365351677883243296407495683472736151029476826049882308535335861496696382332499282956993259186298172080816198388461095039401628146034873832017491510944472269823075
party2 = 6308915880693983347537927034524726131444757600419531883747894372607630008404089949147423643207810234587371577335307857430456574490695233644960831655305379
val2 = 340685435384242111115333109687836854530859658515630412783515558593040637299676541210584027783029893125205091269452871160681117842281189602329407745329377925190556698633612278160369887385384944667644544397208574141409261779557109115742154052888418348808295172970976981851274238712282570481976858098814974211286989340942877781878912310809143844879640698027153722820609760752132963102408740130995110184113587954553302086618746425020532522148193032252721003579780125
# coeff[0] = x, coeff[1] = y, coeff[2] = z
x, y, z = symbols('x y z')
ans = solve([x + (y * party0) + (z * pow(party0, 2)) - val0, x + (y * party1) + (z * pow(party1, 2)) - val1, x + (y * party2) + (z * pow(party2, 2)) - val2])
print(ans)

出力はこんな感じ。

{x: 175721217420600153444809007773872697631803507409137493048703574941320093728, y: 6759741750199108721817212574266152064959437506612887142001761070682826541920627672362291016337903640265385249474489124882116454124173716091800442011015857, z: 8559415203809303629563171044315478022492879973152936590413420646926860552595649298493153041683835412421908115002277197166850496088216040975415228249635834}

x = coeff[0] = secret なので、xを文字列にして終了。

ctf4b{just_d0ing_sh4mir}

おわりに

Go RSAとBit Flip解けなかった...死にてぇ...
ちょっと捻られると解けなくなるので良くないな...