HSCTF8参加記

#はじめに
2回目のCTFのコンテスト参加です。説明を読む限りアメリカの高校生向け大会？(HighSchoolCTF?)らしい。英語読めません。
問題数が多くて手が付けやすかったです。
大学の友人(途中参加)と二人で参加。結果的には7204点(個人4453点)、全体で124位でした。
解いた順番で振り返るのがなかなかに面倒なので、ジャンルごとに振り返っていきます。
フラグそのものには触れません。
ほぼ終了直後に書いてます。
文章が思考の垂れ流しなので文体が酷いです。

#algo
##not-really-math
>"m","a"と数字で構成された文字列が与えられる。
>mは掛け算記号、aは足し算記号とするが、掛け算より足し算が優先される。
>これらを踏まえて計算結果を出力せよ。

mまたはaが来るまで数字を読む。
mが来たら掛けるための数に読んだ数字を足す。
aが来たら掛けるための数に読んだ数字を足した上で答えにそれを掛けて、掛けるための数字をリセット。
最後にaが来た時と同じ処理を忘れずに。

~~~Python
s=input()
ns=""
num=0
ans=1
while s!="":
  c=s[0]
  s=s[1:]
  if (c=="m"):
    num+=int(ns)
    ans*=num
    num=0
    ns=""
  elif c=="a":
    num+=int(ns)
    ns=""
  else:
    ns+=c
num+=int(ns)
ans*=num
print(ans%(2**32-1))
~~~

##Extended Fibonacci Sequence
>Snをn個目までのフィボナッチ数を連結したものと定義する。
>入力としてnが与えられるのでS1からSnまでの総和の下11桁を求めよ。

単純な和であるならば下から数えて12桁目以降は下11桁には干渉しないので、10^11でmodをとりながらフィボナッチ数列を計算。
Sについても同様で結局下11桁しか関係ないので、フィボナッチ数が12桁を超えたうえでmodをとって先頭のゼロが欠けてしまった場合にzfillしてやれば問題なし。

~~~Python
n=int(input())
fibo=[0,1]
mod=10**11
s=1
si="1"
sx="1"
for i in range(2,n+1):
  fibo.append((fibo[-1]+fibo[-2])%mod)
  if i>50:
    si+=str(fibo[-1]).zfill(11)
  else:
    si+=str(fibo[-1])
  si=si[-11:]
  s+=int(si)
  s%=mod
  #print(i,fibo[-1],si,s)
print(s)
~~~


##Extended Fibonacci Sequence2

>0つ目を4、1つ目を5としたフィボナッチ数列Fを用意する。
>SnをFのn個目までの総和とする。
>nが与えられるのでS0からSnまでの総和の下10桁を求めよ。

おいおいお前マジか。さっきより簡単じゃないか。
前述の通りただの加算の場合、ある桁以上はその桁未満に干渉しないのでmodを取りながら段階を踏んで計算してやればよい。
と思ったら、これだけやたらTLEが速い。今まで手作業で入力してたがこれは間に合わない。必死にnetcat上でPythonを動かす方法を探す。
あった。(https://gist.github.com/leonjza/f35a7252babdf77c8421)
ということでコードは前もって計算したうえでnetcatを用いて接続して読み取った数字の答えをひたすら入力するものになった。
fがフィボナッチ数列、sがSの数列、ssumがSの総和になっている。

(netcat使う問題でPython動かす方法についてはちゃんと調べていつか記事を別途で書くつもりです。)

~~~Python
from netcat import Netcat

f=[4,5]
s=[4,9]
ssum=[4,13]
mod=10**10
for i in range(1000):
  f.append((f[-1]+f[-2])%mod)
  s.append((s[-1]+f[-1])%mod)
  ssum.append((ssum[-1]+s[-1])%mod)


  
nc = Netcat('extended-fibonacci-sequence-2.hsc.tf', 1337)
nc.read()
nc.read()

x=[]

while 1:
  while "Here" not in x[0]:
    x=nc.read().decode().split("\n")
    print(x)
  n=int(x[1])
  x[0]="ya"
  nc.write((str(ssum[n])+"\n").encode())
  print(ssum[n])
~~~

##hopscotch

>ケンケンパーの輪っかを書いていく。
>1つか2つずつ書いていくときに総和が入力nになるような組み合わせは何通りあるか。

嘘だろ。またフィボナッチ数列か。
一応、どうしてフィボナッチ数列になるかというと、n段の階段を1段か2段ずつ上る場合の上り方と考えたときに、n段目に行くにはn-1段目かn-2段目からしか行けないので、それら2つの段への上り方の通り数の総和がそのままn段目への上り方の総和になり、0段目と1段目は1通りずつしかなく(初期状態と初期状態から1段上った状態)、2段目以降への上がり方の通り数がそのままフィボナッチ数列になるため。

~~~Python
fib=[1,1]

for i in range(1000):
  fib.append((fib[-2]+fib[-1])%10000)

while 1:
  print(fib[int(input())])
~~~


#crypto
##aptenodytes-forsteri

~~~Python:aptenodytes-forsteri.py
flag = open('flag.txt','r').read() #open the flag
assert flag[0:5]=="flag{" and flag[-1]=="}" #flag follows standard flag format
letters = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
encoded = ""
for character in flag[5:-1]:
    encoded+=letters[(letters.index(character)+18)%26] #encode each character
print(encoded)
~~~

どう見てもシーザー暗号。18個戻すだけ。

##opisthocomus-hoazin

~~~Python:opisthocomus-hoazin.py
import time
from Crypto.Util.number import *
flag = open('flag.txt','r').read()
p = getPrime(1024)
q = getPrime(1024)
e = 2**16+1
n=p*q
ct=[]
for ch in flag:
    ct.append((ord(ch)^e)%n)
print(n)
print(e)
print(ct)
~~~

お、RSA暗号、と思ったのが運の尽き。ずっとランダムなpとqからどうやって復号するか悩む。
よく見たら、"ord(ch)^e"、排他的論理和か……。
使われてそうな文字を同じ加工して照らし合わせる。

~~~Python
n=15888457769674642859708800597310299725338251830976423740469342107745469667544014118426981955901595652146093596535042454720088489883832573612094938281276141337632202496209218136026441342435018861975571842724577501821204305185018320446993699281538507826943542962060000957702417455609633977888711896513101590291125131953317446916178315755142103529251195112400643488422928729091341969985567240235775120515891920824933965514217511971572242643456664322913133669621953247121022723513660621629349743664178128863766441389213302642916070154272811871674136669061719947615578346412919910075334517952880722801011983182804339339643
e=65537
ch=[65639, 65645, 65632, 65638, 65658, 65653, 65609, 65584, 65650, 65630, 65640, 65634, 65586, 65630, 65634, 65651, 65586, 65589, 65644, 65630, 65640, 65588, 65630, 65618, 65646, 65630, 65607, 65651, 65646, 65627, 65586, 65647, 65630, 65640, 65571, 65612, 65630, 65649, 65651, 65586, 65653, 65621, 65656, 65630, 65618, 65652, 65651, 65636, 65630, 65640, 65621, 65574, 65650, 65630, 65589, 65634, 65653, 65652, 65632, 65584, 65645, 65656, 65630, 65635, 65586, 65647, 65605, 65640, 65647, 65606, 65630, 65644, 65624, 65630, 65588, 65649, 65585, 65614, 65647, 65660]

cch=set(ch)
alp="abcdefghijklmnopqrstuvwxyz"
alp+=alp.upper()
alp+="{}_1234567890\"'!#$%&()"
dic={}
for c in alp:
  dic[(ord(c)^e)%n]=c

print(dic)

for i in ch:
  if i in dic:
    print(dic[i],end="")
  else:
    print(i,end="")

print()

~~~

##regulus-satrapa

~~~Python:regulus-satrapa.py
from Crypto.Util.number import *
import binascii
flag = open('flag.txt','rb').read()
p = getPrime(1024)
q = getPrime(1024)
n = p*q
e = 2**16+1
pt = int(binascii.hexlify(flag).decode(),16)
print(p>>512)
print(q%(2**512))
print(n, e)
print(pow(pt,e,n))
~~~

pとqが半分ずつ欠けているところから何とかして秘密鍵を出さないといけなさそう。
なんかの定理が使えるかとか考えたものの結局覆面算の要領で照らし合わせたほうが速そう。
(pの下xbit*qの下xbit)の下xbit=nの下xbit  になるので、nとqを一番下のbitから照らし合わせながらpを1bitずつ埋めていく。
具体的には、pのxbit目を1にした場合にnのxbit目が計算と合うかをチェックして合う場合pのそのbitは1、合わない場合は0になる。
pが埋まったら、qの上位512bitに対しても1bitずつ照らし合わせて埋めていく。(筆算で言うところの上下を入れ替えれば同じ操作になる)


~~~
p:       1010101
q:    X  xxxx100←(2)つまりqの下から1bit目は0   (5)下から2bit目も0  (7)下から3bit目は1
      ----------
         0000000←(1)ここはnの下から1bit目から考えて0   (3)つまりこの行全体0
        0000000 ←(4)上の行全部0かつnの下から2bit目も0なのでここも同様に0
       1010101  ←(6)上2行が0かつ、nの下から3bit目が1なのでここには1が入る
         :
n:10000100110100

~~~
~~~Python
n=20478919136950514294245372495162786227530374921935352984649681539174637614643555669008696530509252361041808530044811858058082236333967101803171893140577890580969033423481448289254067496901793538675705761458273359594646496576699260837347827885664785268524982706033238656594857347183110547622966141595910495419030633639738370191942836112347256795752107944630943134049527588823032184661809251580638724245630054912896260630873396364113961677176216533916990437967650967366883162620646560056820169862154955001597314689326441684678064934393012107591102558185875890938130348512800056137808443281706098125326248383526374158851
e=65537
c=19386365681911176116962673929966212779218446893629616096165535479988405148285413619761557889189211704676408056225729231312267774666516067344628902420462860500796694348719854753450503310214423075716290790730397428257808016249943644108687242803494660111203848028946883397960407526446222857172233473980414880412616288479351174943750112131566288658840674793729931330990659775746679427920973741044231239820653713719744056152497641552948891194509604049453065742204369183052918461477609558512635361757334304706673378249269583497003794274869298361016417188996692715520035544727779966978038114830108861813134381830342160591600

pp=10782851882643568436690840861500470716392138950798808847901800880356088489358510127370728036479767973147003063168467186230765513438172292951359505497400115
qq=156706242812597368863822639576094365104687347205289704754937898429597824385199919052246554900504787988024439652223718201546746425116946202916886816790677

nn=n%(2**512)

bn=bin(nn)
ch=0
ap=0
for i in range(512):
  j=2**i
  qj=qq*j
  if bin(ch+qj)[-(i+1)]==bn[-(i+1)]:
    ap+=j
    ch+=qj


ch=0
p=pp<<512
p+=ap
bq=(bin(qq)[2:]).zfill(512)
for i in range(512):
  j=2**i
  if bq[-(i+1)]=="1":
    ch+=p*j
bn=bin(n)
aq=qq
for i in range(512,1024):
  j=2**i
  pj=p*j
  if bin(ch+pj)[-(i+1)]==bn[-(i+1)]:
    aq+=j
    ch+=pj

q=aq
print("p=",p)
print("q=",q)
print("pcheck:",(p>>512)==pp)
print("qcheck:",q%(2**512)==qq)
print("n==p*q:",n==p*q)
import math 

d=pow(e,-1,math.lcm(p-1,q-1))
print("d=",d)
m=pow(c,d,n)
print("m=",m)
m=hex(m)[2:]
print("hex(m)=",m)

for i in range(len(m)//2):
  print(chr(int(m[i*2:i*2+2],16)),end="")
print()

~~~

#misc
1ポイント問題は書きません
##sanity-check,discord-flag
そのまま

##Return of the Intro to Netcat
Netcatで指定のアドレスに接続するとソルバーについてとその場で生成されたランダムな文字列が出てくるので、それをそのまま別のターミナルで実行して、出てきたものを入れてやればよい。

##LSBlue,pallets-of-gold,glass-windows
青空白猫にお世話になりました。
それぞれ、青色ビット0抽出(バイナリ)、赤色ビット7抽出、アルファチャンネル無効化で出る。

##geographic-mapping
2枚目が、LIBERTASという特徴的な紋章とロープウェイ乗り場で検索を掛けたらサンマリノの山の山頂であることがわかった。
が1枚目がさっぱりなので友人に投げた。マルタらしい。

#web
##digits-of-pi
A2のセルなどからsourceというシートの存在がわかるが非表示になっていて開けない。
0とかflagで検索を掛けたら見れた。

#pwn,rev
何の成果も得られませんでした……


#感想
振り返ってみると簡単な問題しか解けてないなぁという感じがする。
得意のcryptoをあまり解けなかったのが悔しい。
問題を食わず嫌いする傾向があるのでもうちょっと色々触っていきたい。
ハリネズミ本も購入したのでこれからいろいろ勉強していくつもりです。