FireShell CTF 2020 writeup - みつのCTF精進記録

はじめに
[Crypto: 497 pts] monKEYprito
[Crypto: 497 pts] Conora Secret
[rev: 261 pts] Simple Encryption
[ppc: 408 pts] Warmup ROX

はじめに

FireShell CTFに参加しました．開催時間が短いので軽い気持ちででたらすごく難しくてめちゃくちゃ大変でした．
自分たちStarrySkyは2330ポイントで41位でした．もうちょっと頑張りたかったです．でも楽しかったです！
f:id:mi__tsu:20200323144644p:plain
というわけで自分が解いた問題のwriteupを書いていきます．得点はCTFが終わった後の最終的なものを載せています．

[Crypto: 497 pts] monKEYprito

MoNkEy_CRYptor.py
you_was_monkeyd.enc

以下のような暗号化スクリプトが渡されました．

#&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&@@@@@@@&&&&@&&&&&&&&&&&&&&&&&&&&&&&&&@&&@&&@&@@@@@@@@@@@@@@@&@@@&&&&&@&&&&&&&@@&&&&&&&@&&&@@@@@@@@@@&@&&&&&&&&&&&&&&
#,,,,,,,,,,,,,,******************///*////*,,**,,.***,***.*,,,.,.,,********//*/////((/(#####(/*(/(/***,*,*/**,,,,,,,,,*,*******//(///*****,,,,,,,,,,,,,,
#***,,,,,,,,**************////////*****,*,,,,,.*,,**/**,,,,,.*,,*,**,**/,,/(((//////(///((///*(/*//,**,*,,*,..,....,,,****,*,,(((//*****,,,,,,,,,,,,,,,
#*****,,,,,***************/***(*/***,,,,,,,,,,**,***/*/******,*,****///////*/*////**(//(//*//////*/***,*,*,,....  .,,...,*/**,/((/***,**,,,,,,,,,,,,,,,
#*********************///((//*///**,**,,*,,,,,,,,*////*********,**///*/**//(///**/***,*///////*////*,,,,*,*,.**,.,,,,,*,******/((//*/******,,,,,,,,,,,*
#*****,,,,,***********/(#((/(((((///*,,,,,*,.,,*,,..,****,*/((/*/*,,,*,.,,*,******/*/**////****//*****//*,***,*,,,,,,**,**,,,,*(((((/*******,,,,,,,,***
#*****,,,,,,,********///*/*/(#(#((//***/,,,,,,,,,*/*/***//((##(#/#/.....,. .,,,////(//////*/,///*(*//**/****/****,,.,********/////((/////***,,,,,,,****
#***,,,,,,,,,,*****/*/*//*/(/((/****,,,**.,/(####(/###/*/(((%##/.   ,**..**,*//(##((/((*/*/(*//(//////////****************//////////(((//////**,,,*****
#*,,,,,,,,,*******///*//***/*****,,,,,**/(/  , ....  /*/////(/.,*..   .,,*#(,(####(((((//*//((((//(/*/#/(/*******/**///*///*//***/////*////////*,,*****
#,,,,,*,**********///***/**////***,***/*,.  ,*/*//* .,////***////((#(/*//((((((//(//(*///((///*/(**/*/////////******///**/*/////***,,,,***//((//*******
#,,,,,,*****************////////((///((##(//****/##((/**/***,**/((#((((##((#(((#((//((///////*/*((((///(/((/**/*/*//*//******/****,,*,,*******//****,,,
#,,,,**********/*****//*/(/(////((/(((####%#%#%#(((/(*,*,*,,,,,**//(//////(//////(#((((/////(//****(/*/(*/////*///**/*,***********,,..,,******,*,,,,,,,
#,,,**********/****/*/////*/##(//(((###/((((((((/((/**,*,,,,,,,,,**/////((///*//**/////////////////////(///((/*/*(/*/*********,,,,,,*,***,,*,,**,,,**,,
#,,,***********///(/*/((((#(((((//((#((##((/(((((**,**,*.**,,,,**,*,,,/*///(/((((//////(/(/**////////(*/*//(/*///(**/**,,,,,*,,,,**....,,,,,,**.,...,**
#,,,**********/***///(#((((////(##(#%(//(//(///****,,*****,,**,,,****,****//(//(//(((/(((((##(((##((////////*//////**/*,,,*,*,,,,, ,,,.,,,,,,,*,,*,...,
#,.,,*********//////*/((((((#((##((//(((/(/#(*****,**/////*****/*****/*//((*////*((/((((((((#(((##(###(///(*/(//*****,,,,,,,,***,,,,,,*,,*,,*,,*,.*.,,,
#,,,,,**********//*////(((##((#(/(((/(///////**/***//*///(/ ,*////*/////(//(((#/((((#(//(*((/(///(##(/(/*((//*,,***,,...,,,,,,***,**/*,,*,*,/,,,,*,,*,,
#.....,,,,,,*******///((((((/((///((###((*((//(***,,(((**/**////(((((/(/(((((((#((/(/////////(/**(*//((((//********,,,,,.*..***,,*,*,******,,,*,*****,,
#.........,*****/////(((#(/((########((((((((/////////(///((######((((((/(((#(((((///*,****(*((/*//*(*/((//**/*/...,*,,.,*,***,*/*,*,**/,*****,*,*/**,*
#.....,,,,,,,******/(((((((######((((#//(/(((/(((((((((/##%#%#((((((/////****/*,.,... ,,*,***(//((/*((//////*,,.,...,**/***,****/,**/*,,/*//*/*,**,**,*
#.....,,,,,,*///*/*//(((#####(##((((///*//#((((((((((((/(/(/////**/*,//(//////**..,*,..,,*/*,**/(/((/(#/(//**,,...,,,******,,**,,,//,,/*,*,/(***,,***,*
#.....,*****,**////(########((#(((////**//**//*/(*****//***(#%%###%(%%%%#(((/*. .//,/((/((/**/(////#(*//*/**,**,,,.,,,*//****,,,,,****/*/*,*//*********
#...,,,,.,,,*,,,***(######((#(/(////////**.,,***//(#&&&&#&&&&&&%%&%###%##(/*,., ,,,/#(//#(////////////(//***///**,*.,***/*******/*********/****/***,//,
#...,,,,,,,***/**/((((####(((((((//(///***,,....#(##&@@@&%&@@@@&#%&%/(%%(///(,*...#(//###//////////((/(/**/,*/,,**,,*/,*,**,****,,*,*/*/,//*/*/*****,/(
#.,,,,,,,,***,,*,*/((####(((((((((((((//****,**..#(#%@@@@%#@@@@&##%##/#%#*(((/,.*((/(((/**/*/*//////(/(*/**,,**,*****//,,***,**,/***/*,/,,****/*////,/*
#....,,,..,,,,,,,*//(#((####(####(#(((///****///*,#((&&@&%(%&&&#((((##*((((*..*////(/(***/////////((///*,******,*****,,*,,,,*,,**,,***/**,*//***/*,**/*
#......,,,,,,,*,**//((#########(##((/(///////*((//,(//**/(((#%%#(%%(%####(.,*/////(/*****/*//////////**,,,******/*(/*,,,**,,,*,,****,,**/***///********
#.........,,,*,,,*////(#(####(##((/((((//////((/(//*./(/#%%((%&%#(#%##(*,*//((//(/******/////////////*///**/***/**/**,*,****,*****,,***//****//*****///
#........,,,,,,,,**////(((#(###(((((((((((/(///////**,*/((#(//###((/**//(/(/(///*,,,*/**/***///*//**///(//***/*//*,***,,/****,,************,,,,***///**
#............,,,.,,**//((###((###((#((((((((((//////****,,**/**(((#(((////*////********////////***/**/*///**/***//,**/**,*******,*************,********
#..............,,***//(((((###########((((((((/(/////***///////////*//////////***,*,*/***///////*///*,**,***/*/**/*,,,*****/***,,*************,*,,*,**/
#
#          THE MONKEY ENCRYPTOR          THE MONKEY ENCRYPTOR          THE MONKEY ENCRYPTOR          THE MONKEY ENCRYPTOR
#          THE MONKEY ENCRYPTOR          THE MONKEY ENCRYPTOR          THE MONKEY ENCRYPTOR          THE MONKEY ENCRYPTOR
#          THE MONKEY ENCRYPTOR          THE MONKEY ENCRYPTOR          THE MONKEY ENCRYPTOR          THE MONKEY ENCRYPTOR
#
import os
import zipfile
from secret import flag
os.path.realpath(__file__)

def get_troll_string():
	troll_string = "MmMmMmMmoOoOoOOoOOonnnNnNNnkkKkKkKkKkkkekeekEKkekekEYyYyyYyyYYYYYYYYYY!!!!!!!!!!!!222@@@@@@2XDDDDDDDD"

	with open("Monkeyd_ziped.zip", 'rb') as file:
		run = 0
		for byte in file.read():
			if(run==2):
				break
			troll_string += troll_string*ord(byte)
			run+=1
	return troll_string

def monkeyd(monkey_troll_string):
	array = []
	rainbow = 1
	with open("Monkeyd_ziped.zip", 'rb') as file:
		for byte in file.read():
			array.append(hex((ord(byte)+ord(monkey_troll_string[(rainbow-1)%(len(monkey_troll_string)-1)])+rainbow%256)%256))
			rainbow+=1

	with open('you_was_monkeyd.enc', 'wb') as output:
		output.write(bytearray(int(i, 16) for i in array))

if __name__ == '__main__':
    zipf = zipfile.ZipFile('Monkeyd_ziped.zip', 'w', zipfile.ZIP_DEFLATED)
    zipf.write("monkey.png", compress_type=zipfile.ZIP_DEFLATED)
    zipf.write(flag, compress_type=zipfile.ZIP_DEFLATED)
    zipf.close()
    monkeyd(get_troll_string())

どうやらフラグと猿の画像が入ったzipファイルを暗号化しているようです．
まずget_troll_string関数について，どうやらzipファイルの先頭2byteを使ってtroll_stringを変化させているようです．
zipファイルの先頭2 byteはマジックナンバーで，\x50\x48固定です．だからget_troll_stringの出力は常に一定なので次のように書き直すことができました．

def get_troll_string():
    return "MmMmMmMmoOoOoOOoOOonnnNnNNnkkKkKkKkKkkkekeekEKkekekEYyYyyYyyYYYYYYYYYY!!!!!!!!!!!!222@@@@@@2XDDDDDDDD" * 6156

実際の暗号化部分はmonkeyd関数で，troll_stringに従って暗号化しているようです．
ただ暗号化方法が，zipファイルのバイト列を読み込んで，各バイト列にtroll_stringの各文字，カウンタの値(rainbow)をそれぞれ足しているだけなようなので逆に引き算すれば簡単に復号できます．
そるばどぺー

troll_string = "MmMmMmMmoOoOoOOoOOonnnNnNNnkkKkKkKkKkkkekeekEKkekekEYyYyyYyyYYYYYYYYYY!!!!!!!!!!!!222@@@@@@2XDDDDDDDD" * 6156

array = []
rainbow = 1
with open("you_was_monkeyd.enc", "rb") as f:
    for byte in f.read():
        array.append(hex((byte-ord(troll_string[(rainbow-1)%(len(troll_string)-1)])-rainbow%256)%256))
        rainbow += 1
    
    with open('dec.zip', 'wb') as output:
        output.write(bytearray(int(i, 16) for i in array))

$ python solve.py
$ ls
dec.zip  MoNkEy_CRYptor.py  ...
$ unzip dec.zip
Archive:  dec.zip
  inflating: monkey.png              
  inflating: flag.txt

復号したzipファイルにはフラグと画像が入ってました．
f:id:mi__tsu:20200323182418p:plain
F#{SPAM_THE_4w3s0m3_m0nk3y_EVERYWHERE}
実はこの問題，CTFが終わるギリギリのときに出てきたので時間との勝負でした．あと寝てたらCTFが終わっちゃってたので気合で起きて正解でした……

[Crypto: 497 pts] Conora Secret

The challenge provide two files: output.txt and chall.py. The python file is a cypher that is clear El Gamal scheme. The only missing info is the two keys of Bob and Alice that can be retrieved using discrete log.

chall.py
output.txt

暗号化スクリプトとその標準出力は次のようなものでした．

import gmpy2, os
import SECRET

class Cipher():
    state = None
    nbits = None
    p = None
    g = None

    def __init__(self, nbits = 160):
        self.nbits = nbits
        seed = reduce(lambda a, b: (a << 8) | ord(b), os.urandom(128), 0)
        self.state = gmpy2.random_state(seed)
        self.p = self.generaterandomvalue()
        self.g = self.generaterandomvalue()

    def generaterandomvalue(self):
        randomvalue = gmpy2.mpz_urandomb(self.state, self.nbits)
        return gmpy2.next_prime(randomvalue)

    def genkey(self):
        while True:
            v = self.generaterandomvalue()
            if v < self.p:
                break
        return v


c = Cipher()
alicekey = c.genkey()
bobkey = c.genkey()

A = gmpy2.powmod(c.g, alicekey, c.p)
B = gmpy2.powmod(c.g, bobkey, c.p)

alicemessage = SECRET.alicemessage
aliceciphered = (pow(A, bobkey, c.p) * alicemessage) % c.p

bobmessage = SECRET.bobmessage
bobciphered = (pow(A, bobkey, c.p) * bobmessage) % c.p

print 'g:', c.g
print 'p:', c.p

print (A, aliceciphered)
print (B, bobciphered)

g: 271288297309032254959087925221099038857108692921
p: 1102599800392365312390928345103450099096472467311
(mpz(434975788934893935486812987784904932345816911149L), mpz(16411897893431398084407358496852070907176230853L))
(mpz(170780066307111969073123095839072967904862735531L), mpz(673443080181189918056298223003913178931188451777L))

普通のElGamal暗号で二つの平文を暗号化しているようです．初めは秘密鍵の使い回しがまずいのかと思って式変形をコネコネしてましたが，平文を計算する変形までたどりつくことができませんでした(というか無理では？？)
実は愚直に総当り的なことをすればalicekeyやbobkeyが求まっちゃうのでは，と思いオレオレふるいで気合で計算しましたがダメダメでした．6時間くらい回して結果はコードのバグが見つかるといった代物です．本当にだめ．
ぐぐってみると，数体ふるいで離散対数を計算してくれるOSSがありました．悲しいけど嬉しい．
GitHub - kurhula/cado-nfs
./cado-nfs.py -dlp -ell "ell" target="h” "p" とすれば， ${ \log h \mod ell }$ が求められるようです．
ellはpの素因数の最大値です．
注意として，cado-nfsで出てくるlogの底は適当なものなので底の変換をしてあげなくてはいけません．またこの時の法はellです．
そのため，ただcado-nfsをやっただけだと ${ \log_g h \equiv \frac{\log h}{\log g} \mod ell }$ までしか求まりません．
まあでもPohlig-Hellmanにcado-nfsで出てきた答えを組み込めば大丈夫そうですね！
そるばどぺー

from Crypto.PublicKey import RSA
from functools import reduce
import math
import gmpy2
import re

# a * x0 + b * y0 = gcd(a, b)
# return gcd(a,b), x0, y0
def egcd(a, b):
    (x0, x1, y0, y1) = (1, 0, 0, 1)
    while b != 0:
        (q, a, b) = (a // b, b, a % b)
        (x0, x1, y0, y1) = (x1, x0 - q * x1, y1, y0 - q * y1)
    return (a, x0, y0)

# a^(-1) % mod
def modinv(a, mod):
    g, x, y = egcd(a, mod)
    if g != 1:
        raise Exception("Modinv does not exist")
    return x % mod

# return x s.t.
# x = y[0] mod n[0]
# x = y[1] mod n[1]
# ...
def chinese_remainder(ns, ys):
    s = 0
    mulmul = reduce(lambda a, b: a * b, ns)
    for n, a in zip(ns, ys):
        p = mulmul // n
        s += a * modinv(p, n) * p
    return s % mulmul

# Baby step Giant step
# g^x = y mod p
def BsGs(g, y, p, q):
    m = int(math.sqrt(q) + 1)

    # Baby step
    baby = {}
    b = 1
    for i in range(m):
        baby[b] = i
        b = (b * g) % p

    # Giant step
    gm = pow(modinv(g, p), m, p)
    giant = y
    for i in range(m):
        if giant in baby:
            x = i * m + baby[giant]
            return x
        else:
            giant = (giant * gm) % p
    print("Error: BsGs")
    return -1

# Pohling-Hellman
def PH(p, g, y, phip_factors):
    bn = []
    for i in range(len(phip_factors) - 1):
        pk = phip_factors[i]
        phippk = (p - 1) // pk
        bk = BsGs(pow(g, phippk, p), pow(y, phippk, p), p, pk)
        bn.append(bk)

    # big factor
    bn.append(68891157682107548008597666707891616)

    print("bn: {}".format(bn))
    x = chinese_remainder(phip_factors, bn)
    return x

# decrypt
def decryption(c1, c2, x, p):
    m = ((c2 % p) * pow(c1, x * (p - 2), p)) % p
    return m

def decodeM(m):
    s = hex(m)[2:]
    l = []
    if (len(s) & 1):
        l.append(chr(int(s[0], 16)))
        s = s[1:]
    ss = re.split("(..)", s)[1::2]
    for i in ss:
        l.append(chr(int(i, 16)))
    return "".join(l) 

g = 271288297309032254959087925221099038857108692921
p = 1102599800392365312390928345103450099096472467311
h = 434975788934893935486812987784904932345816911149
c2 = 16411897893431398084407358496852070907176230853
c1 = 170780066307111969073123095839072967904862735531
bobc = 673443080181189918056298223003913178931188451777
phi_p = [2, 3, 5, 1093, 1223, 67103, 409739750867624373064553668058242381]
ell = 409739750867624373064553668058242381

"""
## from cado-nfs
## x value is incorporated in Pohlig-Hellman
log_h = 89312554803004771914370169287990323
log_g = 49442345370660375073521009173730491
x = log_h * modinv(log_g, ell) % ell
x = 68891157682107548008597666707891616
"""

x = PH(p, g, h, phi_p)
print("x: {}".format(x))
m = decryption(c1, c2, x, p)
print(m)
print(decodeM(m))

m = decryption(c1, bobc, x, p)
print(m)
print(decodeM(m))

F#{d1Scr3t_lOg4m4l}
この問題，最初から公開されていた割にソルブが少なかったので解けたときはすごく嬉しかったです．

[rev: 261 pts] Simple Encryption

I found this small program on my computer and an encrypted file. Can you help me decrypt the file?

chall
flag.enc

暗号化するバイナリと暗号化されたフラグらしきファイルが渡されます．
challはlibcが静的リンクされていて結構大きかったです．またstrippedなので非常に読むのが大変でした．
頑張って逆アセンブルして読んでいると，どうやら中で乱数等は用いて無いことがわかりました．
challを動かして確認すると，暗号化前の文字と暗号化後の文字には一対一の対応がありました！
ということでフラグに使いそうな文字を暗号化してみれば対応がわかり，簡単に複合することができます．
そるばどぺー

import re

chs = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!#$%&()*+,-./:;<=>?@[]^_`{|}~ '0123456789a"
ind = "3d3b39373533312f2d2b29272523211f1d1b19171513110f0d0b7d7b79777573716f6d6b69676563615f5d5b59575553514f4d4bbdb9b7b5b3afadaba9a7a5a3a18b89878583817f494543413f09070503ebbfb19f9d9b99979593918f8d"

ind = re.split('(..)', ind)[1::2]
ind = list(map(lambda ch: chr(int(ch, 16)), ind))

db = {}
for i in range(len(chs)):
    db[ind[i]] = chs[i]

with open("flag.enc", "rb") as f:
    buf = f.read()

flag = ""
for i in buf:
    flag += db[chr(i)]
    print(flag)

print(db)
print(flag)

出力の結果がF#{S2mpl4_encr2pt21n_f1und_1n_g2thub!}でした．
コードがバグってるのかなー……このフラグを入れてもincorrectとなってしまいました．
気合でフラグを修正して最終的に以下のフラグが通りました．数字が一個ずれてるっぽいです．
F#{S1mpl3_encr1pt10n_f0und_0n_g1thub!}

[ppc: 408 pts] Warmup ROX

Server: 142.93.113.55
Port: 31087

エスパー問でした．文字列を入力すると，それに対応した文字列が帰ってきます．
どうやら，入力された文字列とフラグをxorして，その結果を出力しているようです．
ということでヌル文字を送り込めばフラグが入手できます．
そるばどぺー

from pwn import *

r = remote("142.93.113.55", 31087)

r.recv(0x100)
r.sendline("start")

s = "\x00" * 30
r.sendline(s)

r.interactive()

F#{us1ng-X0r-is-ROx-4-l0t}