東京大学のコンピューター系サークルTSGが主催らしい。正直、開始前は「そんなに難しい問題は出ないだろう」と侮っていたけど、めっちゃ難しかった。
チームsuperflipは2852点で5位。
Cooldown
Survey
Thank you for participating in TSG CTF!
Please tell us your experiences and earn the bonus point.
English: https://forms.gle/xxxx
Japanese: https://forms.gle/xxxxTSG CTF に参加してくださりありがとうございます！
よければ参加した感想をお聞かせください。ボーナスポイントを付与します。
英語: https://forms.gle/xxxx
日本語: https://forms.gle/xxxx
アンケートに答えると1点分のフラグがもらえる。最後の最後で問題が解けてその問題が面白いかもしれないから、アンケートに答えるのは後のほうが良いかと思うものの、同点だと順位は点を得た順だから早く答えたいし、悩ましい。
TSGCTF{Hosting_a_CTF_is_really..._REALLY_tough_and_challenging!}
Warmup
Sanity Check
Log in to our Discord server for TSG CTF and find the flag here:
TSG CTF のDiscordサーバーにログインして↓の場所に書いてあるフラグを送信してください。
TSGCTF{ur_here_cuz_u_absolutely_won_inshack_ctf?}
Pwn
Odd Multiplier
Can you do multiplication?
The flag is in /home/user/flag
nc 34.85.75.40 30002Difficulty estimate: Easy
想定難易度Easyだから考えてみたものの、解けなかった。
255未満の奇数をいくつか入力してその積を計算するプログラム。多倍長乗算を自前で実装しているが、下位桁から順に見ていって 00 になったら終了している。要はNULL終端文字列のようなものなので、適当に積を大きくしてやれば、スタックのカナリアもlibcの戻り先アドレスも分かる。後はカナリアを元の値にして、戻り先アドレスをOne-gadget RCEにすれば良いのだと思う。数学力が足りなくて、これを奇数の積でどう実現するのかが分からなかった。
0x...???xxxxxxxxxxxxxxxx????????????????xxxxxxxxxxxxxxxx????????????????????????????????????????????????
のxを指定した値、?は何でも良いというのを奇数の積で表現するのはどうすれば良いのだろう。伸ばしていく途中にすでに値が入っている場合もあるので、その対応も必要。
Web
BADNONCE Part 1/Part 2
Reining in the Web with ...?
http://35.187.214.138:10023/?q=XSS
Please send the flag1.Estimated Difficulty: Medium
Please send the flag2.
Estimated Difficulty: Medium
解けず。
<?php
session_start();
$nonce = md5(session_id());
:
<meta http-equiv="Content-Security-Policy" content="script-src 'nonce-<?= $nonce ?>';">
:
<script nonce=<?= $nonce ?>>
console.log('Welcome to the dungeon :-)');
</script>
:
<!-- Here is an injection point :-) -->
<?= $_GET['q'] ?>
「これでXSSができるなら、CSPの意味とは……」と考えたけれど、
The server must generate a unique nonce value each time it transmits a policy.
とのことで、同一セッションでnonceを使い回していることになるのが脆弱性だろうか。
Secure Bank
I came up with more secure technique to store user list. Even if a cracker could dump it, now it should be of little value!!!
http://34.85.75.40:19292/ユーザ情報を保存するのに、もっとセキュアな方法を思いついた気がしなくもない。 仮に全部ダンプされてしまったとしても、かなり無価値になりそうでは。
http://34.85.75.40:19292/Difficulty estimate: Easy
他のユーザーに送金ができて、残高が10,000,000,000を越えるとフラグが得られる。送金部分のコードは、
post '/api/transfer' do
return err(401, 'login first') unless src = session[:user]
return err(400, 'bad request') unless dst = params[:target] and String === dst and dst != src
return err(400, 'bad request') unless amount = params[:amount] and String === amount
return err(400, 'bad request') unless amount = amount.to_i and amount > 0
sleep 1
hashed_src = STRETCH.times.inject(src){|s| Digest::SHA1.hexdigest(s)}
hashed_dst = STRETCH.times.inject(dst){|s| Digest::SHA1.hexdigest(s)}
res = DB.query 'SELECT balance FROM account WHERE user = ?', hashed_src
row = res.next
balance_src = row && row[0]
res.close
return err(422, 'no enough coins') unless balance_src >= amount
res = DB.query 'SELECT balance FROM account WHERE user = ?', hashed_dst
row = res.next
balance_dst = row && row[0]
res.close
return err(422, 'no such user') unless balance_dst
balance_src -= amount
balance_dst += amount
DB.execute 'UPDATE account SET balance = ? WHERE user = ?', balance_src, hashed_src
DB.execute 'UPDATE account SET balance = ? WHERE user = ?', balance_dst, hashed_dst
json({amount: amount, balance: balance_src})
end
ユーザーIDをSHA1に掛けているので、ハッシュが衝突すると同じユーザーになってしまう。ただし、送金元と送金先が同一ユーザーかどうかの判定はハッシュ化前。ということで、SHA1(user1)=SHA1(user2)が成り立つようなユーザーIDuser1とuser2で、user1からuser2に全額送金すると残高が倍になる。
ユーザーIDとしてはSHA1が衝突するPDFの先頭部分を使えば良い。SHA1は一度衝突したら両方に同じコンテンツを追加しても衝突したままなので、ユーザーIDが他の参加者に取られていたら、適当な文字列を追加すれば良い。バイナリデータを送信しないといけないので、ブラウザではなくcurlでポチポチした。
別解。
TSG CTF 2019 Writeup - Secure Bank - こんとろーるしーこんとろーるぶい
シングルスレッドで動いているんじゃなかったのか……。
TSGCTF{H4SH_FUNCTION_1S_NOT_INJ3C71V3... :(}
Crypto
OPQRX
Can you decrypt RSA? I'll give a hint value, XOR.
ここにRSAの暗号文がありますが、XORをあげるので、代わりに平文をください。
Difficulty Estimate: Easy
RSA暗号。N=P*Qの他にX=P^Qも与えられる。
掛け算の筆算を考えると、a*bの下d桁は、aとbの下d桁にしか依存しない。555123*666456=369965054088も777123*888456=690439592088も下3桁は088である。
XによってPとQの値を下位桁から探索していくと、P*QとNの下位桁が一致するというのが強力な枝刈りになって、3分程度で答えが求められる。
X = 950358059600474305827771380683741458994102949126303386140253951747972276999022342208262800760061154398271068516253175545735456284984933121377404958083314600655447129775868209462982744186518957772122396756451141101530041779955245471472134699242664534814221273939880846730251297763359790557422127540709102136769366092399273623925570872859266548882987518588530617720397165019176108480156876913848103894864771903530413550704276937306948683609983799509662220045635940160920596367820951543381669617525581893239594901173734116054697069635020002486845048804682305078106964316183798068618639241948197675223115348163019048625373765550949273567042933864894263655621306241833349642978696892492213984491118558186425036609374626368657763236619642299850791946710919682040219563850092641243093906165685956695639258845635807997678135071126411514233212329352759106255311517050069284549350052584108601349762457513286109309685191933647198018596263095604001928907171502875081594253618031333487818528683297444472724705834348968685867101260408703944578321377003322277616161558951427955865100991857694166101106561131471922637073992792768831828380493392423497335535612525566590750772745411732685028183267169226764749141325626854817138130631949844771053951960
N = 247465623232529638570403627954515140549125464704817835183645669188472743182462350040656945325450657857795456553396687569720980842982926845337227966696522093282786882561968615864736765752433069546858439815030651380785843674190791402853951236494718634304312751098515936783858994195570922580683332803369701363402529074402664491617600861267722232614873579834618864491313983011984783179171484956546212881647063328679330401752122426273399745247394558879616944190407436620707694460705838905167958310291748206503803245570812818460951229153004100082641961722909449085000926517536505862666390730672438786667437732727892530932043888271965398718458040093563806864200347078192024936196446329155635755682462402577559908583721738674671712235928511130814290140488609275201531091941022025423945245655138749471773951982326940397563668812663911560805472790354465176645654925712665466908761601630548710031513794557078929877256958912825742035898444107900195605803439822642914124421169419665012462368428063174117176948217351889525290996526478175910563577827404884951074164990948585830040593958196959384856700062914243351708318383463054253935630461024868395311859856823997566468043613201152144317218540388233163044090076375023156913766157903266102228806511766874546238501462729789311305353532852243350014435557292562277534441782977536950667942409622824703681942287094306687529563976259226568536477006987758537902779031652725318651412097989762378829049950725567335828279044984627929916893167368380666080846093308718960187199678171390844781410123277536707822610961039098290794321102160488402500912631820436740755297381500867354726950237473157706745732481020409089136649142836959359494679712387674635517522465929790194532886549752549296525326753661396418942921238641862841862062523739794185828404110732054050991100263967931482921549160288056234483320030511150838991553475977254477982555698760709836081377694957203251796012604022819780158470545306037123726144297059699951351522178070972246076273281750790146118258080309984762387853921776334456422671205443649323821265510825075358823620914441131837218471866299818058325805391640744310939129416240071558620256757906619101813132910694274256665801559376989999327799895968742876386311015510228756261286000612508092571831683964733063518480933968224775829439608716169155578215817882852862506665551979130227190512028135937769869149065155592833328152008778223352658264026115418397316311825039015464475393415911842445128662864755158473389001859110809489
E = 65537
C = 38292826706641216197843504024442473810304021733514451674093213928285248206581440804382750412040887271040802347875317791241766024921473228404695871017478971358043108872759997071604134571145632444890962123400867988299720826951697743018301463745437874886471856189203658771918213330370568116597671937234517684350844457560748316765528685035787121369688963100742605146223188219823044747059438808663118931444860689199058383273989761139776185693880705114030744137694916118577357618886718996561416159751609291056288383072188225742693264976539230860895884979155649321473725137314438905587563576686790028504585718870222050725422615608593162022543355433501610656100656390969549536782697723232083896243322848431946061430870092255185038860802722297859103382933439318448178426630322096447063497659583523406322273845339351942166550925881712869778934735961149831772419648770236423703778723709444074774848123177937341096799046441632009391879828882947968574005475222868208181869257328113346954778678246921806895756722458089660774852257216218215808974146798709289339389262445340618875434418284218058428043448686605333666457077432829562549724024902120335397651378232322610446055675419301412421106727875968903348833369153306108013434674775382056357049594636017276583463994846272581542940834432469709833096499918026534841080645909295142106259175030365691510336715363687103695664308943450214512604477679897247821600646499130163417531360091862226215014951623512776412924518253491354722974882416598688799566899430112327839786083498652816075049879123875037397210282458262075630647426596559506653960639198563847404854433138206824762240117486424443541276062622450481252963886447743305106741755625393982965955449252982502400943583974279541514867833295668849211670439562950515041383905926077150598226197512830572160465815250946291000472385227962209742945274795499069129229632516658868321068874484377798039972658708538006538591069685862343473277090657067119342545903879280904833995538022922695355992924800030338000982764572271044035105159200522915596166488049773949980105458112099226431959533158261775419858136750649339995749317237166469933837147003693606374953899602388950411523146406309727420544388352005658922216757121426412510588922115785795472332119978070111697951388862117411170313506043948916399276331265222331256207884612355562474861844964026947655141931410062960340978440773611758524297473204811668212292023445223770150008515042103444551443481759899935450672833801013486294074702610305157
import sys
sys.setrecursionlimit(10000)
def exgcd(m, n):
if n>0:
y,x,d = exgcd(n, m%n)
return x, y-m/n*x, d
else:
return 1, 0, m
def search(d, P, Q):
if d==4100:
if P*Q==N:
D = exgcd(E, (P-1)*(Q-1))[0] % ((P-1)*(Q-1))
print hex(pow(C, D, N))[2:-1].decode("hex")
exit(0)
return
for i in range(2):
P2 = P | i<<d
Q2 = Q | (X^i<<d) & 1<<d
m = (1<<(d+1))-1
if ((P2*Q2)&m)==(N&m):
search(d+1, P2, Q2)
search(0, 0, 0)
TSGCTF{Absolutely, X should be 'S' in 'OPQRX'.}
OMEGA
A ring in the shape of omega is there...
Ω < ゴロンゴロン(環っかが転がる音)
Difficulty estimate: Easy
最後のほうはこの問題を考えていたのだけど、解けなかった。
x = sub(x, mul(div(x, y), y))（divでは整数に丸められる）というのはたしかに剰余で、2次元の変な空間でこれをやっているとはいえ、「中国の剰余定理を使うだけでしょ？ Easy！」ということだと思うが……。
追記。
（簡単に実装できる加算以外の）四則演算は、問題のプログラムに揃っているのだから、中国剰余定理を書いてみれば良かった。書いたらいけた。
下記のコードを問題のproblem.rbに追記して実行すると答えが出る。
:
require 'test/unit/assertions'
include Test::Unit::Assertions
def add(x, y)
a, b = x
c, d = y
[a+c, b+d]
end
def exgcd(m, n)
if n==[0,0] then
return [[1, 0], [0, 0], m]
else
y,x,d = exgcd(n, mod(m, n))
# q = m//n
m2 = sub(m, mod(m, n))
q = div(m2, n)
loop do
s = sub(m2, mul(q, n))
break if s==[0, 0]
q = add(q, div(s, n))
end
# [x, y-m/n*x, d]
return [x, sub(y, mul(q, x)), d]
end
end
def crt(a1, a2, m1, m2)
x1,x2,d = exgcd(m1, m2)
if d==[1, 0] then r = [1, 0]
elsif d==[-1, 0] then r = [-1, 0]
elsif d==[0, 1] then r = [-1, -1]
elsif d==[0, -1] then r = [1, 1]
elsif d==[1, 1] then r = [0, -1]
elsif d==[-1, -1] then r = [0, 1]
else
puts 'error! %p' % [d]
raise
end
x1 = mul(x1, r)
x2 = mul(x2, r)
d = mul(d, r)
assert add(mul(x1, m1), mul(x2, m2))==[1, 0]
# x1*m1 + x2*m2 = [1, 0]
# よって
# x1*m1 = [1, 0] (mod m2)
# x2*m2 = [1, 0] (mod m1)
#
# a2*x1*m1 = a2 (mod m2)
# a1*x2*m2 = a1 (mod m1)
#
# r = a2*x1*m1 + a1*x2*m2
# r = a2 (mod m2)
# r = a1 (mod m1)
ans = add(
mul(a2, mul(x1, m1)),
mul(a1, mul(x2, m2)))
return mod(ans, mul(m1, m2))
end
f = [0, 0]
mall = [1, 0]
PROBLEM.each do |a, m|
f = crt(f, a, mall, m)
mall = mul(mall, m)
end
puts f.map{|t|[t.to_s(16)].pack("H*")}.join
任意のaに対してa+z=aが成り立つようなzが0に対応するので、z=[0, 0]。1に対応するiは、a*i=aから、i=[1, 0]。拡張ユークリッドの互除法を動かしてみたら、結果が[1, 0]以外の値になることがあったので、mulの定義を見ながら適切な値を掛けて[1, 0]に直す。また、拡張ユークリッドの互除法中の整数除算（m//n）は、div単体だと内部で浮動小数点数を使っていて誤差が発生するので一工夫必要。誤差をnで割って加えることを繰り返せば良い。
たしかに、剰余環が謎の環になっただけで、中国の剰余定理を使うだけの簡単な問題ではある……。
TSGCTF{I_H34RD_S0ME_IN7EGERS_INCLUDING_EISENSTEIN'S_F0RM_EUCL1DE4N_R1NG!}
Curved
If you get curved, then...
曲がり角は駐車禁止ですよ？
Estimated difficulty: Medium
標準ではない楕円曲線上での離散対数問題を解けという問題。
:
# P = 2 ** 256 - 2 ** 32 - 977
P = 2 ** 256 - 2 ** 32 - 313441 # We all like hacks, ain't we?
:
Gx = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
Gy = sqrt(Gx ** 3 + 7)
G = [Gx, Gy]
flag = File.read('flag')
h = mul(G, flag.unpack("H*")[0].hex)
assert h == [
0x56df2adff3c3749cc4c62c9e7da339dc02d157868a1d76f9d058d634d6a9525f,
0xc167d7eb600437e2d6ead69ebcf2b1b2f88939c0fafda0b19aa3db33f5024b43,
]
楕円曲線なんもわからんけど、ググっていたら同じような問題の解法を見つけた。
zip(*factor(E.order()))をzip(*factor(P.order()))に直す（この問題ではたまたまEとPの位数が一緒だから困らなかった？）のと、primesの個数を調整。
M = 2 ** 256 - 2 ** 32 - 313441
A = 0
B = 7
P = (0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798, 0xb63818c3db63feba08b2a7926e4df30266895386031296b4ba7dd760b4d9cdc5)
Q = (0x56df2adff3c3749cc4c62c9e7da339dc02d157868a1d76f9d058d634d6a9525f, 0xc167d7eb600437e2d6ead69ebcf2b1b2f88939c0fafda0b19aa3db33f5024b43)
F = FiniteField(M)
E = EllipticCurve(F,[A,B])
P = E.point(P)
Q = E.point(Q)
factors, exponents = zip(*factor(P.order()))
primes = [factors[i] ^ exponents[i] for i in range(len(factors))]
print(primes)
primes = primes[:-1]
dlogs = []
for fac in primes:
t = int(P.order()) / int(fac)
dlog = discrete_log(t*Q,t*P,operation="+")
dlogs += [dlog]
print("factor: "+str(fac)+", Discrete Log: "+str(dlog)) #calculates discrete logarithm for each prime order
l = crt(dlogs,primes)
print(l)
[16, 3, 23, 251, 157229, 7392373, 8666891, 18222037, 696663547, 946050631, 237140208281, 291304131568817]
factor: 16, Discrete Log: 13
factor: 3, Discrete Log: 1
factor: 23, Discrete Log: 7
factor: 251, Discrete Log: 189
factor: 157229, Discrete Log: 88732
factor: 7392373, Discrete Log: 596846
factor: 8666891, Discrete Log: 6963744
factor: 18222037, Discrete Log: 14985241
factor: 696663547, Discrete Log: 236207427
factor: 946050631, Discrete Log: 329659139
factor: 237140208281, Discrete Log: 11437073562
5462541443624622557322434549034030102387804220735361156906077
これではビット数が足りないけれど、フラグは
- この値に
primesの積の整数倍を足したものである - 上位の桁は
TSGCTF{である
ということが分かっているのでゴリ押す。
P = [16, 3, 23, 251, 157229, 7392373, 8666891, 18222037, 696663547, 946050631, 237140208281]
p = 1
for t in P:
p *= t
r = 5462541443624622557322434549034030102387804220735361156906077
a = int("TSGCTF{".encode("hex"), 16)
for i in range(30):
f = a*256**i/p*p+r
f = "%x"%f
if len(f)%2!=0:
f = "0"+f
f = f.decode("hex")
print i, f
:
22 TSGEh[R5gbJ・・・T止ｨﾓ・憫ｹｽ
腎+脱1ﾔ^・蝮ｩ K
24 TSGCTIｬ槭_ｸ\ｱ・拱 6:&ﾎ3:=ﾝｴj}
25 TSGCTF{BewareOfTheSh@rpCurves!!}
・SGCTF{烝凞･ﾇDｮ觸<・
27 TSGCTF{ ｶ/ｹe・Iｸ・@hｽ・ﾁ8ｹｻﾍqﾁﾍ
:
ちなみに、解いた後でprimesを全て使うようにして裏で動かしていたら答えが出てきた。
:
factor: 237140208281, Discrete Log: 11437073562
factor: 291304131568817, Discrete Log: 149009426905685
1087950870612075716361732424623822388961276702940085355932530092911122308221
が、これでもビット数が足りない。Gの位数は251ビットなのに、フラグは255bit。なので、いずれにせよ後からちょっと探索する必要はある。
TSGCTF{BewareOfTheSh@rpCurves!!}
Stego
Harekaze
Are you ready for next CTF?
次のCTFの準備はお済みですか？
Difficulty Estimate: Medium
Harekaze CTF、今年もあるのか。
読めそうで読めない。
先に出題されていた0000000000000000の問題画像と見比べると、量子化係数の値が値が小さい。
$ hexdump -C -v harekaze.jpg
00000000 ff d8 ff e0 00 10 4a 46 49 46 00 01 01 00 00 01 |......JFIF......|
00000010 00 01 00 00 ff db 00 84 00 05 03 04 04 04 03 05 |................|
00000020 04 04 04 05 05 05 06 07 0c 08 07 07 07 07 0f 0b |................|
00000030 0b 09 0c 11 0f 12 12 11 0f 11 11 13 16 1c 17 13 |................|
00000040 14 1a 15 11 11 18 21 18 1a 1d 1d 1f 1f 1f 13 17 |......!.........|
00000050 22 24 22 1e 24 1c 1e 1f 1e 01 05 05 05 07 06 07 |"$".$...........|
00000060 0e 08 08 0e 1e 14 11 14 1e 1e 1e 1e 1e 1e 1e 1e |................|
00000070 1e 1e 1e 1e 1e 1e 1e 1e 1e 1e 1e 1e 1e 1e 1e 1e |................|
00000080 1e 1e 1e 1e 1e 1e 1e 1e 1e 1e 1e 1e 1e 1e 1e 1e |................|
00000090 1e 1e 1e 1e 1e 1e 1e 1e 1e 1e ff c0 00 11 08 00 |................|
000000a0 32 01 90 03 01 11 00 02 11 01 03 11 01 ff c4 01 |2...............|
000000b0 a2 00 00 01 05 01 01 01 01 01 01 00 00 00 00 00 |................|
000000c0 00 00 00 01 02 03 04 05 06 07 08 09 0a 0b 10 00 |................|
000000d0 02 01 03 03 02 04 03 05 05 04 04 00 00 01 7d 01 |..............}.|
000000e0 02 03 00 04 11 05 12 21 31 41 06 13 51 61 07 22 |.......!1A..Qa."|
000000f0 71 14 32 81 91 a1 08 23 42 b1 c1 15 52 d1 f0 24 |q.2....#B...R..$|
:
$ hexdump -C -v 0000000000000000.jpg
00000000 ff d8 ff e0 00 10 4a 46 49 46 00 01 01 00 00 01 |......JFIF......|
00000010 00 01 00 00 ff db 00 84 00 0a 07 07 08 07 06 0a |................|
00000020 08 08 08 0b 0a 0a 0b 0e 18 10 0e 0d 0d 0e 1d 15 |................|
00000030 16 11 18 23 1f 25 24 22 1f 22 21 26 2b 37 2f 26 |...#.%$"."!&+7/&|
00000040 29 34 29 21 22 30 41 31 34 39 3b 3e 3e 3e 25 2e |)4)!"0A149;>>>%.|
00000050 44 49 43 3c 48 37 3d 3e 3b 01 0a 0b 0b 0e 0d 0e |DIC<H7=>;.......|
00000060 1c 10 10 1c 3b 28 22 28 3b 3b 3b 3b 3b 3b 3b 3b |....;("(;;;;;;;;|
00000070 3b 3b 3b 3b 3b 3b 3b 3b 3b 3b 3b 3b 3b 3b 3b 3b |;;;;;;;;;;;;;;;;|
00000080 3b 3b 3b 3b 3b 3b 3b 3b 3b 3b 3b 3b 3b 3b 3b 3b |;;;;;;;;;;;;;;;;|
00000090 3b 3b 3b 3b 3b 3b 3b 3b 3b 3b ff c0 00 11 08 05 |;;;;;;;;;;......|
000000a0 20 05 20 03 01 11 00 02 11 01 03 11 01 ff c4 01 | . .............|
000000b0 a2 00 00 01 05 01 01 01 01 01 01 00 00 00 00 00 |................|
000000c0 00 00 00 01 02 03 04 05 06 07 08 09 0a 0b 10 00 |................|
000000d0 02 01 03 03 02 04 03 05 05 04 04 00 00 01 7d 01 |..............}.|
000000e0 02 03 00 04 11 05 12 21 31 41 06 13 51 61 07 22 |.......!1A..Qa."|
000000f0 71 14 32 81 91 a1 08 23 42 b1 c1 15 52 d1 f0 24 |q.2....#B...R..$|
試しに貼り合わせてみると、
TSGCTF{UnderTheBlueSeaMermaidSwims}
0000000000000000
I took a photo at university on a sunny day~~
天気がいい日に大学で写真を撮ったよ
コンテスト終了後も考えていて、「分からないなぁ」とDiscordで検索したら、作問者が解説を書いていた。
kurgm今日 午後4時35分
0000000000000000: In some of the 8x8 blocks in the JPEG file, AC coefficients have a redundant ZRL (run of 16 zero coefficients) just before a EOB (end-of-block). Plotting those blocks will give you a QR code. @🇳 🇴 🇽 🇹 🇺 🇷 🇳 🇮 🇽
I think it was much of guessing
をダウンロードし、エラーになるのでちょっと直し、
diff --git a/picojdec.py.org b/picojdec.py
index b644b0a..4928c5c 100755
--- a/picojdec.py.org
+++ b/picojdec.py
@@ -371,9 +371,9 @@ def parse_DQT(r, image):
print(f' DQT[{t}]: Pq={pq} Tq={tq} Q_k={q}')
lq -= 1 + 64 * n
t += 1
+ # register QuantizationTable
+ image['QT'][tq] = q
assert lq == 0, "invalid DQT payload"
- # register QuantizationTable
- image['QT'][tq] = q
# Huffman table-specification
py -3 picojdec.py 0000000000000000.jpg > dump.txt で結果を保存する。
普通はSqがこんな感じなのに、
MCU#4761: C[0] pos=5,29
Huffman: 010 -> 1
DC s=1 diff=-1 pred=+20
Huffman: 1100 -> 17
AC r=1 s=1 val=+1
Huffman: 11100 -> 33
AC r=2 s=1 val=+1
Huffman: 1010 -> 0
AC EOB
Sq=[19, 0, 1, 0, 0, 1]...
Rz=[190, 0, 7, 0, 0, 6]...
Ri=[[190, 0, 6, 0, 0, 0, 0, 0], [7, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0]]
I=[[154, 153, 153, 152, 152, 153, 153, 154], [154, 153, 152, 152, 152, 152, 153, 154], [153, 153, 152, 151, 151, 152, 153, 153], [153, 152, 152, 151, 151, 152, 152, 153], [152, 152, 151, 151, 151, 151, 152, 152], [152, 151, 151, 150, 150, 151, 151, 152], [152, 151, 150, 150, 150, 150, 151, 152], [152, 151, 150, 150, 150, 150, 151, 152]]
こうなっているブロックがある。
MCU#2640: C[0] pos=16,16
Huffman: 00 -> 0
DC diff=0 pred=+18
Huffman: 1100 -> 17
AC r=1 s=1 val=-1
Huffman: 11111111001 -> 240
ZRL
Huffman: 1010 -> 0
AC EOB
Sq=[18, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]...
Rz=[180, 0, -7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]...
Ri=[[180, 0, 0, 0, 0, 0, 0, 0], [-7, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0]]
I=[[149, 149, 149, 149, 149, 149, 149, 149], [149, 149, 149, 149, 149, 149, 149, 149], [150, 150, 150, 150, 150, 150, 150, 150], [150, 150, 150, 150, 150, 150, 150, 150], [151, 151, 151, 151, 151, 151, 151, 151], [151, 151, 151, 151, 151, 151, 151, 151], [152, 152, 152, 152, 152, 152, 152, 152], [152, 152, 152, 152, 152, 152, 152, 152]]
これはたしかにおかしい。周波数成分は先頭が低周波で末尾が高周波。高周波は0が多くなるので末尾の0は省略できるのだろう。というか、JPEGはこんな冗長性を許すのか。末尾の0を許さない仕様にしたほうが圧縮効率が良さそうなものだけど。
あとは、このおかしなブロックを可視化すれば良い。
import re
re1 = re.compile(" pos=(\d+),(\d+)")
re2 = re.compile(" Sq=\[.* 0\]")
x = 0
y = 0
M = [[0]*164 for _ in range(164)]
for l in open("dump.txt"):
m = re1.search(l)
if m:
x = int(m.group(1))
y = int(m.group(2))
m = re2.search(l)
if m:
M[y][x] = 1
from PIL import Image
im = Image.new("RGB", (164,164))
for y in range(164):
for x in range(164):
im.putpixel((x, y), [(255,255,255),(0,0,0)][M[y][x]])
im.save("qr.png")
ノイズが入っているのは、元から高周波が詰まっていて、..., 0, 0, 0を埋められなかった部分だろうか。
読むと、
Whoa, congratulations! The flag is:
TSGCTF{I_understand_JPEG_perf3ctly}
JPEG、完全に理解した。
正方形の変なサイズを見た時点で、「ブロックごとに何かの情報を含んでQR？」は気づくべきだったか。
空の部分に、変な高周波が乗っているなぁと思ったけど、特に関係無かったらしい。
TSGCTF{I_understand_JPEG_perf3ctly}
Forensics
Obliterated File
Working on making a problem of TSG CTF, I noticed that I have staged and committed the flag file by mistake before I knew it. I googled and found the following commands, so I'm not sure but anyway typed them. It should be ok, right?
TSG CTFに向けて問題を作っていたんですが，いつの間にか誤ってflagのファイルをコミットしていたことに気付いた！とにかく，Google先生にお伺いして次のようなコマンドを打ちこみました．よくわからないけどこれできっと大丈夫...？
\$ git filter-branch --index-filter "git rm -f --ignore-unmatch problem/flag" --prune-empty -- --all
\$ git reflog expire --expire=now --all
\$ git gc --aggressive --prune=nowDifficulty Estimate: easy - medium
↓のAgainの方法で解いた。なぜAgainが出てきたのかと思ったら……w
ffiとobliterated fileだけ解けました。pwnは、手も足も出ないです。obliterated fileはgit desktopでrevertしてたらflagというファイルができたので、zlibで解凍しました。#TSG_CTF
— ec (@ec76237290) 2019年5月5日
commit 28d2b74b0c40583a87cf275f9f0cdfd55042884d
Author: tsgctf <info@tsg.ne.jp>
Date: Thu May 2 05:45:41 2019 +0900
add problem statement
をrevertすると、./flagが出てくる。./problem/flagは消しているけれど、最初に./flagを作って移動していたのを忘れていたのか。
TSGCTF{$_git_update-ref_-d_refs/original/refs/heads/master}
Obliterated File Again
I realized that the previous command had a mistake. It should be right this time...?
さっきのコマンドには間違いがあったことに気づきました．これで今度こそ本当に，本当に大丈夫なはず......？
\$ git filter-branch --index-filter "git rm -f --ignore-unmatch *flag" --prune-empty -- --all
\$ git reflog expire --expire=now --all
\$ git gc --aggressive --prune=nowDifficulty Estimate: easy - medium
まあ、.git/objects/xxか.git/objects/packに残っているのだろう。packにあった。git unpack-objectsで展開する。git unpack-objectsは空のリポジトリで実行する必要がある。展開したobjectは素のdeflateで圧縮されていてpigzで解凍できる。
$ rm -rf tmp
$ mkdir tmp
$ cd tmp
$ git init
Initialized empty Git repository in /mnt/d/documents/ctf/tsg2019/Obliterated File Again/tmp/.git/
$ git unpack-objects < ../easy_web/.git/objects/pack/pack-b799d65ebb2cc3fab7878fcf2a2642585de29408.pack
Unpacking objects: 100% (101/101), done.
$ find .git/objects/ -type f | xargs -I {} pigz -d -c {} > log
あとはlogの中身を探せば良い。gitの履歴を見るに、flag自体もdeflateで圧縮されているので先頭は78。00 78を検索。
00005c40 70 61 72 61 6d 61 74 6f 72 73 0a 62 6c 6f 62 20 |paramators.blob |
00005c50 39 39 00 78 9c 1d c7 41 0a 80 20 10 05 d0 cb b4 |99.x...A.. .....|
00005c60 0d 8d bc 41 50 07 a8 fd c7 d0 54 4a 8b 99 69 11 |...AP.....TJ..i.|
00005c70 d1 dd 8b 56 8f 37 8d 43 37 f5 77 85 90 04 e7 e1 |...V.7.C7.w.....|
00005c80 ac f8 9a fc 82 da e1 83 d5 4e 29 a4 62 37 f5 2f |.........N).b7./|
00005c90 7a eb 58 65 cb e2 09 a3 26 ba b0 68 42 36 6b 2a |z.Xe....&..hB6k*|
00005ca0 01 06 b9 61 31 6b 0b 5d 20 b1 61 1c a4 e7 ad cd |...a1k.] .a.....|
00005cb0 cf 0b 8c 8d 25 7b 62 6c 6f 62 20 36 38 35 00 72 |....%{blob 685.r|
TSGCTF{$_git_update-ref_-d_refs/original/refs/heads/master_S0rry_f0r_m4king_4_m1st4k3_0n_th1s_pr0bl3m}
Reversing
ffi
Try typing some flags
適当なフラグを打ってみてください
TTFフォントファイルが問題。これは面白かった。
Windowsではヒエログリフの「𓂸」は単独では表示されない。前後に他のヒエログリフの文字を並べると表示される → 𓂶𓂸。フォントの合字の仕組みを使っているらしい。これを使って問題を作って見たいなと思っていたけれど、正解の文字列を入力すると、表示が変わるくらいしか思いつかなかった。この問題はもっとすごい。
テスト。
— kusanoさん@がんばらない (@kusano_k) 2019年3月31日
𓂸
𓂶𓂸
𓂸𓂶
𓂶𓂸𓂶https://t.co/l5ItxEeyS0
TSGCTF{hoge_fuga_piyo}しか入力していない。is correctはフォント側で追加されている。
MS公式のFontToolsの中のttfdump.exeでダンプできるらしいが、リンクが切れている。ここから落とせる。
でも、このサイトのほうが使い勝手が良かった。
346番目のグリフが表示できれば正解。DataのGSUB – Glyph Substitution Tableの中に置換情報が入っている。これの読み方が分からず悩んだ。
"lookupType": 1と、`"lookupType": 6のsubtablesが対応している。例えば、
{
"lookupType": 1,
"lookupFlag": 0,
"subtables": [{
"substFormat": 2,
"coverage": {
"format": 2,
"ranges": [
{"start": 64,"end":64,"index":0},{"start":66,"end":91,"index":1},{"start":94,"end":94,"index":27}]},
"substitute": [337,96,108,118,124,133,141,153,166,168,179,188,198,204,217,228,231,247,257,263,275,280,291,299,303,317,324,347]}]}
と
{
"substFormat": 3,
"backtrackCoverage": [{
"format": 1,
"glyphs": [345]}],
"inputCoverage": [{"format":2,"ranges":[{"start":64,"end":64,"index":0},{"start":66,"end":91,"index":1},{"start":94,"end":94,"index":27}]}],
"lookaheadCoverage": [],
"lookupRecords": [{"sequenceIndex":0,"lookupListIndex":6}]},
は、345番目のグリフの後に、64, 66, 67, 68, ..., 91, 94番目のグリフが来たら、それぞれ337, 96, 108, 118, ..., 324, 347番目のグリフに置換する、という意味になるらしい。64番目のグリフは_、66番目から91番目はaからz、94番目は}。337番目は_、96番目はa、…と見た目は変わらないようになっている。これさえ分かれば、後ろから探索するだけ、特に分岐も無く一本道だった。
import json
A = []
B = []
for l in open("gsub.json"):
t = json.loads(l)
if t["lookupType"]==1 and t["subtables"][0]["substFormat"]==2:
A += [t["subtables"][0]["substitute"]]
if t["lookupType"]==6:
B = [x["backtrackCoverage"][0]["glyphs"][0]
for x in t["subtables"]
if x["inputCoverage"][0]["format"]==2]
assert len(A)==len(B)
n = len(A)
x = 346
flag = ""
while x!=345:
for i in range(n):
if x in A[i]:
flag += "_abcdefghijklmnopqrstuvwxyz}"[A[i].index(x)]
x = B[i]
break
print "TSGCTF{"+flag[::-1]
TSGCTF{ligature_state_machine}
Misc
Recorded
Note The foregoing commands were typed with the JIS keyboard, not US keyboard.
何が起こった？
注意 これらのコマンドはJISキーボードのパソコンで実行されました。
\$ sudo docker build -t problem .
\$ sudo docker run -it --device=/dev/input/event1:/dev/input/event1 problem "/bin/bash"
root@hogehuga:/tmp# cat /dev/input/event1 > input &Difficulty Estimate: Medium
解けなかった。
/dev/input/event1のフォーマット。
from struct import unpack
# https://github.com/spotify/linux/blob/master/include/linux/input.h
key = [
"RESERVED", "ESC", "1", "2", "3", "4", "5", "6",
"7", "8", "9", "0", "MINUS", "EQUAL", "BACKSPACE", "TAB",
"Q", "W", "E", "R", "T", "Y", "U", "I",
"O", "P", "LEFTBRACE", "RIGHTBRACE", "ENTER", "LEFTCTRL", "A", "S",
"D", "F", "G", "H", "J", "K", "L", "SEMICOLON",
"APOSTROPHE", "GRAVE", "LEFTSHIFT", "BACKSLASH", "Z", "X", "C", "V",
"B", "N", "M", "COMMA", "DOT", "SLASH", "RIGHTSHIFT", "KPASTERISK",
"LEFTALT", "SPACE", "CAPSLOCK", "F1", "F2", "F3", "F4", "F5",
"F6", "F7", "F8", "F9", "F10", "NUMLOCK", "SCROLLLOCK", "KP7",
"KP8", "KP9", "KPMINUS", "KP4", "KP5", "KP6", "KPPLUS", "KP1",
"KP2", "KP3", "KP0", "KPDOT", "", "ZENKAKUHANKAKU", "102ND", "F11",
"F12", "RO", ]
d = open("input", "rb").read()
for i in range(0, len(d), 24):
_, _, t,c,v = unpack("<QQHHI", d[i:i+24])
if t==1 and v!=0:
print key[c]
適当にスクリプトを書いて打たれたキーを抽出し、JIS配列で記号の配置が異なることを考えて直していくと、
rm /dev/urandom
rm /dev/random
LANG=C date --utc > /dev/random
echo nyan >> /dev/random
curl -O https://www.openssl.org/source/openssl-1.1.1b.tar.gz
tar xzvf openssl-1.1.1b.tar.gz
cd openssl-1.1.1b
vim crypto/rand/rand_unix.c
637G
d17d
621G
d2d
603G
dd
480G
d30d
:wq
vim crypto/rand/rand_lib.c
250G
d2d
:wq
./config
make -j 4
cd ..
LD_LIBRARY_PATH=./openssl-1.1.1b ./openssl-1.1.1b/apps/openssl genrsa 1024 > key.pem
LD_LIBRARY_PATH=./openssl-1.1.1b ./openssl-1.1.1b/apps/openssl rsautl -encrypt -inkey key.pem -in flag.txt -out encrypted
fg 1
を実行していることが分かる。date --utcとopenssl genrsaを実行したときの両方の時刻を総当たりで推測するのは難しいが、/dev/input/event1に時刻が入っているので、それを見れば良い。
ただ、opensslのtime(NULL)をいくつか潰してみたけれど、それでもgenrsaの結果が変わる。timeを潰したり無いのか他にもまだ乱数ソースがあるのか分からないが、諦めた。
追記。なるほど、残りの乱数ソースはPIDか。