TSG CTF Write-up

https://ctf.tsg.ne.jp/

東京大学のコンピューター系サークルTSGが主催らしい。正直、開始前は「そんなに難しい問題は出ないだろう」と侮っていたけど、めっちゃ難しかった。

チームsuperflipは2852点で5位。

<a href="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25276/9fdcc352-6039-c458-8621-13319ebb7231.png"><img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25276/9fdcc352-6039-c458-8621-13319ebb7231.png" width="320"></a> <a href="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25276/422542ec-1f8d-59de-5375-e451fdfad823.png"><img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25276/422542ec-1f8d-59de-5375-e451fdfad823.png" width="320"></a>

## 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/xxxx
>
> TSG 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 30002
>
> Difficulty 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

解けず。

```index.php
<?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.

https://developer.mozilla.org/ja/docs/Web/HTTP/Headers/Content-Security-Policy/script-src

とのことで、同一セッションで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を越えるとフラグが得られる。送金部分のコードは、

```source.rb
  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)`が成り立つようなユーザーID`user1`と`user2`で、`user1`から`user2`に全額送金すると残高が倍になる。

ユーザーIDとしては[SHA1が衝突するPDF](https://shattered.io/)の先頭部分を使えば良い。SHA1は一度衝突したら両方に同じコンテンツを追加しても衝突したままなので、ユーザーIDが他の参加者に取られていたら、適当な文字列を追加すれば良い。バイナリデータを送信しないといけないので、ブラウザではなく`curl`でポチポチした。

別解。

[TSG CTF 2019 Writeup \- Secure Bank \- こんとろーるしーこんとろーるぶい](https://graneed.hatenablog.com/entry/2019/05/05/161950)

シングルスレッドで動いているんじゃなかったのか……。

`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分程度で答えが求められる。

```solve.py
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に追記して実行すると答えが出る。

```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

標準ではない楕円曲線上での離散対数問題を解けという問題。

```curved.rb
 :
# 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,
]
```

楕円曲線なんもわからんけど、ググっていたら同じような問題の解法を見つけた。

https://github.com/hgarrereyn/Th3g3ntl3man-CTF-Writeups/blob/master/2017/picoCTF_2017/problems/cryptography/ECC2/ECC2.md

`zip(*factor(E.order()))`を`zip(*factor(P.order()))`に直す（この問題ではたまたま`E`と`P`の位数が一緒だから困らなかった？）のと、`primes`の個数を調整。

```py
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{`である

ということが分かっているのでゴリ押す。

```solve.py
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、今年もあるのか。

https://harekaze.com/ctf/2019-jp.html

![harekaze.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25276/81674f1e-606e-ab03-760a-d13d7051d906.jpeg)

読めそうで読めない。

先に出題されていた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..$|
```

試しに貼り合わせてみると、

![harekaze2.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25276/7560c075-bd80-8df7-af68-cb5539b39bac.jpeg)

`TSGCTF{UnderTheBlueSeaMermaidSwims}`

### 0000000000000000

> I took a photo at university on a sunny day~~
>
> 天気がいい日に大学で写真を撮ったよ

<a href="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25276/4f6a26e5-30f2-dd52-b765-8311c48d4585.jpeg"><img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25276/4f6a26e5-30f2-dd52-b765-8311c48d4585.jpeg" width="320"></a>

コンテスト終了後も考えていて、「分からないなぁ」と[Discord](https://discord.gg/xJn7v62)で検索したら、作問者が解説を書いていた。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25276/c293c72b-f772-51ff-9e3b-fb7f91140eff.png)

> 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 :bow:

https://github.com/yohhoy/picojdec/blob/6324f3f11347bcabd34d32186fe585d0dd6a08a0/picojdec.py

をダウンロードし、エラーになるのでちょっと直し、

```diff
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`を許さない仕様にしたほうが圧縮効率が良さそうなものだけど。

あとは、このおかしなブロックを可視化すれば良い。

```solve.py
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")
```

![qr.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25276/a1fa0d92-b0c1-7940-875c-30fb77d1b4aa.png)

ノイズが入っているのは、元から高周波が詰まっていて、`..., 0, 0, 0`を埋められなかった部分だろうか。

読むと、

```
Whoa, congratulations! The flag is:
TSGCTF{I_understand_JPEG_perf3ctly}
```

JPEG、完全に理解した。

正方形の変なサイズを見た時点で、「ブロックごとに何かの情報を含んでQR？」は気づくべきだったか。

空の部分に、変な高周波が乗っているなぁと思ったけど、特に関係無かったらしい。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25276/cd55a446-ba1c-db8c-0b5b-be1c391d1ec0.png)

`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=now
> 
> Difficulty Estimate: easy - medium

↓のAgainの方法で解いた。なぜAgainが出てきたのかと思ったら……w

<blockquote class="twitter-tweet" data-lang="ja"><p lang="ja" dir="ltr">ffiとobliterated fileだけ解けました。pwnは、手も足も出ないです。obliterated fileはgit desktopでrevertしてたらflagというファイルができたので、zlibで解凍しました。<a href="https://twitter.com/hashtag/TSG_CTF?src=hash&amp;ref_src=twsrc%5Etfw">#TSG_CTF</a></p>&mdash; ec (@ec76237290) <a href="https://twitter.com/ec76237290/status/1124940853791739904?ref_src=twsrc%5Etfw">2019年5月5日</a></blockquote>

```
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=now
>
> Difficulty Estimate: easy - medium

まあ、`.git/objects/xx`か`.git/objects/pack`に残っているのだろう。packにあった。[git unpack-objects](https://git-scm.com/docs/git-unpack-objects)で展開する。`git unpack-objects`は空のリポジトリで実行する必要がある。展開したobjectは素のdeflateで圧縮されていて[`pigz`で解凍できる](https://stackoverflow.com/questions/3178566/how-to-deflate-with-a-command-line-tool-to-extract-a-git-object)。

```shell-session
$ 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ではヒエログリフの「𓂸」は単独では表示されない。前後に他のヒエログリフの文字を並べると表示される → 𓂶𓂸。フォントの合字の仕組みを使っているらしい。これを使って問題を作って見たいなと思っていたけれど、正解の文字列を入力すると、表示が変わるくらいしか思いつかなかった。この問題はもっとすごい。

<blockquote class="twitter-tweet" data-lang="ja"><p lang="ja" dir="ltr">テスト。<br>𓂸<br>𓂶𓂸<br>𓂸𓂶<br>𓂶𓂸𓂶<a href="https://t.co/l5ItxEeyS0">https://t.co/l5ItxEeyS0</a></p>&mdash; kusanoさん@がんばらない (@kusano_k) <a href="https://twitter.com/kusano_k/status/1112314636156567552?ref_src=twsrc%5Etfw">2019年3月31日</a></blockquote>

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25276/08db7381-faee-3458-749d-2086c773d946.png)

`TSGCTF{hoge_fuga_piyo}`しか入力していない。` is correct`はフォント側で追加されている。

MS公式のFontToolsの中のttfdump.exeでダンプできるらしいが、リンクが切れている。ここから落とせる。

https://download.microsoft.com/download/f/f/a/ffae9ec6-3bf6-488a-843d-b96d552fd815/FontTools.exe

でも、このサイトのほうが使い勝手が良かった。

https://fontdrop.info/

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25276/7c34d3d4-1363-3b6a-8e16-96aebc823901.png)

346番目のグリフが表示できれば正解。DataのGSUB – Glyph Substitution Tableの中に置換情報が入っている。これの読み方が分からず悩んだ。

`"lookupType": 1`と、``"lookupType": 6`の`subtables`が対応している。例えば、

```json
{
  "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]}]}
```

と

```json
{
  "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`、…と見た目は変わらないようになっている。これさえ分かれば、後ろから探索するだけ、特に分岐も無く一本道だった。

```solve.py
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]
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25276/efc68ef3-5a73-c619-ae94-c9a020e92418.png)

`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`のフォーマット。

http://www.tatapa.org/~takuo/input_subsystem/input_subsystem.html

```solve.py
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か。

[TSG CTF 2019 Writeup - Recorded - 0xiso’s blog](https://0xiso.hatenablog.com/entry/2019/05/05/192214)