SECCON Beginners CTF 2019 writeup
はじめに
yharimaで参加し、11th / 666 placeでした。(自分は実質何もやってない)
今回はbinary強い人とweb強い人がチームにいたのでcryptoに専念してみた。(2問しか解けなかったので死にたい...)
他のメンバーのブログはこちら。 yuta1024.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解けなかった...死にてぇ...
ちょっと捻られると解けなくなるので良くないな...