読者です 読者をやめる 読者になる 読者になる

Tokyo Westerns / MMA CTF 2nd 2016 に参加しました

CTF自体が初参加、しかもソロプレイ。
ということで、1問も解けない不安があったんですけど、初心者でも解ける問題が用意されてて、めちゃ面白かったです。
結果は109位。


ちゃんとWriteup(解法)を書くことがすごく重要らしいので、簡潔に書いてみました。

Welcome!! (Misc,Warmup 10)

コピペです。

TWCTF{Welcome_To_TW_MMACTF!!}

一つ気になったのが、Welcome!!提出チーム数が821なのに、点数が正のチームが835チームなんですよね。
14チームはどこに消えたのか。
怖いですね。

Make a Palindrome! (PPC,Warmup 20,30)

与えられた単語を並び替えて回文にする。
制限は、単語数N<=10、テストケース30個、時間制限3分。
ということで、O(N!)のプログラムで十分間に合います。

# words: input
# answer: answer
for t in itertools.permutations(words):
    if "".join(t) == "".join(t)[::-1]:
        answer=t
        break
TWCTF{Charisma_School_Captain}
TWCTF{Hiyokko_Tsuppari}

Twin Primes (Crypto,Warmup 50)

双子素数を扱ったRSA暗号による暗号文の復号。
p*qと(p+2)*(q+2)からp,qがわかるので逆算が可能です。

from Crypto.PublicKey import RSA
from Crypto.Util.number import *

encrypted=7991219189591014572196623817385737879027208108469800802629706564258508626010674513875496029177290575819650366802730803283761137036255380767766538866086463895539973594615882321974738140931689333873106124459849322556754579010062541988138211176574621668101228531769828358289973150393343109948611583609219420213530834364837438730411379305046156670015024547263019932288989808228091601206948741304222197779808592738075111024678982273856922586615415238555211148847427589678238745186253649783665607928382002868111278077054871294837923189536714235044041993541158402943372188779797996711792610439969105993917373651847337638929

n1=19402643768027967294480695361037227649637514561280461352708420192197328993512710852087871986349184383442031544945263966477446685587168025154775060178782897097993949800845903218890975275725416699258462920097986424936088541112790958875211336188249107280753661467619511079649070248659536282267267928669265252935184448638997877593781930103866416949585686541509642494048554242004100863315220430074997145531929128200885758274037875349539018669336263469803277281048657198114844413236754680549874472753528866434686048799833381542018876362229842605213500869709361657000044182573308825550237999139442040422107931857506897810951 #p*q
n2=19402643768027967294480695361037227649637514561280461352708420192197328993512710852087871986349184383442031544945263966477446685587168025154775060178782897097993949800845903218890975275725416699258462920097986424936088541112790958875211336188249107280753661467619511079649070248659536282267267928669265252935757418867172314593546678104100129027339256068940987412816779744339994971665109555680401467324487397541852486805770300895063315083965445098467966738905392320963293379345531703349669197397492241574949069875012089172754014231783160960425531160246267389657034543342990940680603153790486530477470655757947009682859 #(p+2)*(q+2)

pplusq=(n2-n1-4)//2

e = long(65537)
d1 = inverse(e, n1-pplusq+1) #pq-(p+q)+1 (p-1)*(q-1)
d2 = inverse(e, n1+pplusq+1) #pq+(p+q)+1 (p+1)*(q+1)
key1 = RSA.construct((n1, e, d1))
key2 = RSA.construct((n2, e, d2))

encrypted=key2.decrypt(encrypted)
encrypted=key1.decrypt(encrypted)
encrypted=long_to_bytes(encrypted)
print encrypted 
TWCTF{3102628d7059fa267365f8c37a0e56cf7e0797ef}

Super Express (Crypto 100)

線形的にハッシュ化されたハッシュ値の復号。
例えば、key="DCBAEFGH"だったら、

x=(ord("A")(ord("B")(ord("C")(ord("D")*x+ord("E"))+ord("F"))+ord("G"))+ord("H")) % 251 
 =(P*x+Q) % 251

のようになるので、

ord("T")=84 : P*84+Q%251=0x80
ord("W")=87 : P*87+Q%251=0x5e

からP=156,Q=76が求まり各文字の対応がわかります。

A={}
P=156
Q=76
for x in range(251):
    c=(P*x+Q)%251
    A['%02x' % c]=chr(x)

encrypted="805eed80cbbccb94c36413275780ec94a857dfec8da8ca94a8c313a8ccf9"
ans=""
for i in range(0,len(encrypted),2):
    ans+=A[encrypted[i:i+2]]
print ans
TWCTF{Faster_Than_Shinkansen!}

rps-ng (PPC 130)

じゃんけんAIに50回中40回以上勝つ。
AIはプレイヤーの(前の手,今回の手)になった回数をtable[前の手][今回の手]に記録、その回数を評価し最善手を出してきます。
tableは初め0~5に値で初期化されていますが、プレイヤーはその値はわかりません。
プレイヤーは、じゃんけんをしながらtableを予想し、矛盾に対して辻褄合わせをします。

my_table=[[0 for x in range(3)] for y in range(3)]
prev=0
result = 0
RPS=["R","P","S"]

def my_hand():
    global prev
    global my_table
    j = -1
    m = -1
    for i in range(3):
        if m < my_table[prev][i]:
            m = my_table[prev][i]
            j = i
    return (j + 2) % 3
#cur 0:R 1:P 2:S
#result 1:win 0:draw -1:lose
def update_my_table(cur,result):
    global prev
    global my_table
    # print(RPS[cur])
    m = -1
    for i in range(3):
        if m < my_table[prev][i]:
            m = my_table[prev][i]
    if result == 0:
        my_table[prev][(cur - 1) % 3]+=1
    elif result == -1:
        my_table[prev][cur]+=1
    my_table[prev][cur]+=1
    prev = cur
TWCTF{The_hand_is_determined_by_mien}

Lights Out! (PPC 100,300)

lights out(ライツアウト)亜種の解答プログラムを作る。
「ライツアウト 解法」とググって出てくるサイトに、掃き出し法で解くっぽいことが載っています。
実装法は全くわからなかったので他人のコードをpythonに移植してnormalのみ解きました。
lunaticはメモリエラーで挫折。

TWCTF{peaceful_tea_party}

glance (Misc 50)

gifアニメの画像を分解して繋げ直して一枚の画像にする。
ImageMagickで、

convert +append glance.gif _glance.gif
TWCTF{Bliss by Charles O'Rear}


(Web Pwn Forensic Reverseが1問も解けませんでした)