satto1237’s diary

s4tt01237’s diary

ラーメンとかCTFとかセキュリティとか

SECCON Beginners CTF 2020 Write-up

はじめに

2020/05/23に ~ 2020/05/24に開催されたSECCON Beginners CTF 2020に会社の同期とチームを結成して参加しました.
チームとしては17問解いて19位でした (1009チーム中).
今回は自分が解いた5問のWrite-upを書きます.

f:id:satto1237:20200525124255p:plain

f:id:satto1237:20200525124246p:plain

Rev

yakisoba [Easy, 144solved, 156pts]

Would you like to have a yakisoba code?

(Hint: You'd better automate your analysis)

> file yakisoba
yakisoba: ELF 64-bit LSB pie executable x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, for GNU/Linux 3.2.0, BuildID[sha1]=fc0031f79ea88d284f3177f980b40110c2612f3e, stripped

アプローチ:シンボリック実行

とりあえずidaでフローグラフをみてみます.

f:id:satto1237:20200525125403p:plain

これを読む気にはなりませんね…(1つ1つのロジックは単純だったので気合があれば読めるのかも?)

(Hint: You'd better automate your analysis)

ヒントに従って、angrで自動解析することにします.

idaでmain関数を確認すると,0x000006D2に到達できればいいことがわかります.

f:id:satto1237:20200525151157p:plain

そのため,ソルバは以下のようになります.

import angr

p = angr.Project('./yakisoba', load_options={'auto_load_libs': False})
state = p.factory.entry_state()
sim = p.factory.simulation_manager(state)
sim.explore(find=(0x400000 + 0x6d2,), avoid=(0x400000 + 0x6f7,))
print(sim.found[0].posix.dumps(0))
> python solve.py
WARNING | 2020-05-25 06:15:25,139 | cle.loader | The main binary is a position-independent executable. It is being loaded with a base address of 0x400000.
b'ctf4b{sp4gh3tt1_r1pp3r1n0}\x00\xd9\xd9\xd9\xd9'

ctf4b{sp4gh3tt1_r1pp3r1n0}

ghost [Medium, 68solved, 279pts]

A program written by a ghost 👻

chall.gs

/flag 64 string def /output 8 string def (%stdin) (r) file flag readline not { (I/O Error\n) print quit } if 0 1 2 index length { 1 index 1 add 3 index 3 index get xor mul 1 463 { 1 index mul 64711 mod } repeat exch pop dup output cvs print ( ) print 128 mod 1 add exch 1 add exch } repeat (\n) print quit

output.txt

3417 61039 39615 14756 10315 49836 44840 20086 18149 31454 35718 44949 4715 22725 62312 18726 47196 54518 2667 44346 55284 5240 32181 61722 6447 38218 6033 32270 51128 6112 22332 60338 14994 44529 25059 61829 52094 

アプローチ:動的解析

問題名やスクリプトの文法(スタック指向)からghostscript (postscript?)だということがわかります.

最初はドキュメントを読みながら愚直に解析していたのですが,途中で出力結果が入力文字列の長さに依存しないことに気づきました.

> gs chall.gs
ctf4b
3417 61039 39615 14756 10315

そのため,方針を静的解析ではなく,indexごとに文字空間を全探索する動的解析に切り替えました.

ソルバは以下のようになります.

import subprocess
import string

enc_flag = ['3417', '61039', '39615', '14756', '10315', '49836', '44840', '20086', '18149', '31454', '35718', '44949', '4715', '22725', '62312', '18726', '47196', '54518', '2667', '44346', '55284', '5240', '32181', '61722', '6447', '38218', '6033', '32270', '51128', '6112', '22332', '60338', '14994', '44529', '25059', '61829', '52094']
flag = b'ctf4b{'

while len(flag) < len(enc_flag):
    for c in string.printable:
        p = subprocess.Popen(['gs', 'chall.gs'], stdin=subprocess.PIPE, stdout=subprocess.PIPE, stderr=subprocess.PIPE)
        p.stdin.write(flag + c.encode() + b'\n')
        p.stdin.flush()
        res = p.stdout.readlines()[-1].decode().strip().split()[-1]
        if res == enc_flag[len(flag)]:
            print(f'flag is {flag.decode() + c}')
            flag += c.encode()
            break
> python  solve.py
flag is ctf4b{s
flag is ctf4b{st
flag is ctf4b{st4
flag is ctf4b{st4c
flag is ctf4b{st4ck
flag is ctf4b{st4ck_
flag is ctf4b{st4ck_m
flag is ctf4b{st4ck_m4
flag is ctf4b{st4ck_m4c
flag is ctf4b{st4ck_m4ch
flag is ctf4b{st4ck_m4ch1
flag is ctf4b{st4ck_m4ch1n
flag is ctf4b{st4ck_m4ch1n3
flag is ctf4b{st4ck_m4ch1n3_
flag is ctf4b{st4ck_m4ch1n3_1
flag is ctf4b{st4ck_m4ch1n3_1s
flag is ctf4b{st4ck_m4ch1n3_1s_
flag is ctf4b{st4ck_m4ch1n3_1s_4
flag is ctf4b{st4ck_m4ch1n3_1s_4_
flag is ctf4b{st4ck_m4ch1n3_1s_4_l
flag is ctf4b{st4ck_m4ch1n3_1s_4_l0
flag is ctf4b{st4ck_m4ch1n3_1s_4_l0t
flag is ctf4b{st4ck_m4ch1n3_1s_4_l0t_
flag is ctf4b{st4ck_m4ch1n3_1s_4_l0t_0
flag is ctf4b{st4ck_m4ch1n3_1s_4_l0t_0f
flag is ctf4b{st4ck_m4ch1n3_1s_4_l0t_0f_
flag is ctf4b{st4ck_m4ch1n3_1s_4_l0t_0f_f
flag is ctf4b{st4ck_m4ch1n3_1s_4_l0t_0f_fu
flag is ctf4b{st4ck_m4ch1n3_1s_4_l0t_0f_fun
flag is ctf4b{st4ck_m4ch1n3_1s_4_l0t_0f_fun!
flag is ctf4b{st4ck_m4ch1n3_1s_4_l0t_0f_fun!}

ctf4b{st4ck_m4ch1n3_1s_4_l0t_0f_fun!}

siblangs [Medium, 37solved, 363pts]

Well, they look so similar... siblangs.apk

> file siblangs.apk
siblangs.apk: Zip archive data, at least v?[0] to extract

f:id:satto1237:20200525155917p:plain

アプローチ:grep + デコンパイル

とりあえずsiblangs.apkunzipします.

ここでctf4bgrepすると以下のようなJavaScriptで書かれた処理を見つけることができます.

> grep -r 'ctf4b' ./siblangs
./siblangs/assets/index.android.bundle:
[snipped]
state={flagVal:"ctf4b{",xored:[34,63,3,77,36,20,24,8,25,71,110,81,64,87,30,33,81,15,39,90,17,27]},t.handleFlagChange=function(o){t.setState({flagVal:o})},t.onPressValidateFirstHalf=function(){if("ios"===h.Platform.OS){for(var o="AKeyFor"+h.Platform.OS+"10.3",l=t.state.flagVal,n=0;n<t.state.xored.length;n++)if(t.state.xored[n]!==parseInt(l.charCodeAt(n)^o.charCodeAt(n%o.length),10))return void h.Alert.alert("Validation A Failed","Try again...");h.Alert.alert("Validation A Succeeded","Great! Have you checked the other one?")}else h.Alert.alert("Sorry!","Run this app on iOS to validate! Or you can try the other one :)")},t.onPressValidateLastHalf=function(){"android"===h.Platform.OS?p.default.validate(t.state.flagVal,function(t){t?h.Alert.alert("Validation B Succeeded","Great! Have you checked the other one?"):h.Alert.alert("Validation B Failed","Learn once, write anywhere ... anywhere?")}):h.Alert.alert("Sorry!","Run this app on Android to validate! Or you can try the other one :)")},t}return(0,n.default)
[snipped]

ここでは,key (AkeyForios10.3)と入力文字列のxor[34,63,3,77,36,20,24,8,25,71,110,81,64,87,30,33,81,15,39,90,17,27]と一致するかのチェックを行っています.

そのため,以下の処理でflagを復元できます.

a = [34,63,3,77,36,20,24,8,25,71,110,81,64,87,30,33,81,15,39,90,17,27]
key = b"AKeyForios10.3"*2

flag = bytearray()
for x,k in zip(a,key):
    flag.append(x^k)
print(flag.decode())

ctf4b{jav4_and_j4va5cr

どうやら残りのflagを取得するにはh.Platform.OS?p.default.validateを調べる必要があるようです.

dex2jarを用いてclasses.dexclasses-dex2jar.jarに変換し,JD-GUIJava側のソースコードを確認するとValidateFlagModule.classでValidateを行っていることが確認できます.
ValidateFlagModule.classでは,encrypted flagAES-GCMで復号し,入力文字列と比較する処理を行っています. また,このクラスでは,復号の際にハードコーディングされたsecret keyを利用しているので,encrypted flagをdecryptする処理は以下のように簡単に再現することができます.

import java.security.SecureRandom;
import javax.crypto.Cipher;
import javax.crypto.SecretKey;
import javax.crypto.spec.GCMParameterSpec;
import javax.crypto.spec.SecretKeySpec;

class DecryptLastFlag {
    private static final int GCM_IV_LENGTH = 12;
    private static final SecretKey secretKey = new SecretKeySpec("IncrediblySecure".getBytes(), 0, 16, "AES");
    private final SecureRandom secureRandom = new SecureRandom();

    public static void main(String[] args) {
        byte[] arrayOfByte = new byte[43];
        byte[] tmp8_6 = arrayOfByte;
        tmp8_6[0] = 95;
        byte[] tmp13_8 = tmp8_6;
        tmp13_8[1] = -59;
        byte[] tmp18_13 = tmp13_8;
        tmp18_13[2] = -20;
        byte[] tmp23_18 = tmp18_13;
        tmp23_18[3] = -93;
        byte[] tmp28_23 = tmp23_18;
        tmp28_23[4] = -70;
        byte[] tmp33_28 = tmp28_23;
        tmp33_28[5] = 0;
        byte[] tmp38_33 = tmp33_28;
        tmp38_33[6] = -32;
        byte[] tmp44_38 = tmp38_33;
        tmp44_38[7] = -93;
        byte[] tmp50_44 = tmp44_38;
        tmp50_44[8] = -23;
        byte[] tmp56_50 = tmp50_44;
        tmp56_50[9] = 63;
        byte[] tmp62_56 = tmp56_50;
        tmp62_56[10] = -9;
        byte[] tmp68_62 = tmp62_56;
        tmp68_62[11] = 60;
        byte[] tmp74_68 = tmp68_62;
        tmp74_68[12] = 86;
        byte[] tmp80_74 = tmp74_68;
        tmp80_74[13] = 123;
        byte[] tmp86_80 = tmp80_74;
        tmp86_80[14] = -61;
        byte[] tmp92_86 = tmp86_80;
        tmp92_86[15] = -8;
        byte[] tmp98_92 = tmp92_86;
        tmp98_92[16] = 17;
        byte[] tmp104_98 = tmp98_92;
        tmp104_98[17] = -113;
        byte[] tmp110_104 = tmp104_98;
        tmp110_104[18] = -106;
        byte[] tmp116_110 = tmp110_104;
        tmp116_110[19] = 28;
        byte[] tmp122_116 = tmp116_110;
        tmp122_116[20] = 99;
        byte[] tmp128_122 = tmp122_116;
        tmp128_122[21] = -72;
        byte[] tmp134_128 = tmp128_122;
        tmp134_128[22] = -3;
        byte[] tmp140_134 = tmp134_128;
        tmp140_134[23] = 1;
        byte[] tmp146_140 = tmp140_134;
        tmp146_140[24] = -41;
        byte[] tmp152_146 = tmp146_140;
        tmp152_146[25] = -123;
        byte[] tmp158_152 = tmp152_146;
        tmp158_152[26] = 17;
        byte[] tmp164_158 = tmp158_152;
        tmp164_158[27] = 93;
        byte[] tmp170_164 = tmp164_158;
        tmp170_164[28] = -36;
        byte[] tmp176_170 = tmp170_164;
        tmp176_170[29] = 45;
        byte[] tmp182_176 = tmp176_170;
        tmp182_176[30] = 18;
        byte[] tmp188_182 = tmp182_176;
        tmp188_182[31] = 71;
        byte[] tmp194_188 = tmp188_182;
        tmp194_188[32] = 61;
        byte[] tmp200_194 = tmp194_188;
        tmp200_194[33] = 70;
        byte[] tmp206_200 = tmp200_194;
        tmp206_200[34] = -117;
        byte[] tmp212_206 = tmp206_200;
        tmp212_206[35] = -55;
        byte[] tmp218_212 = tmp212_206;
        tmp218_212[36] = 107;
        byte[] tmp224_218 = tmp218_212;
        tmp224_218[37] = -75;
        byte[] tmp230_224 = tmp224_218;
        tmp230_224[38] = -89;
        byte[] tmp236_230 = tmp230_224;
        tmp236_230[39] = 3;
        byte[] tmp242_236 = tmp236_230;
        tmp242_236[40] = 94;
        byte[] tmp248_242 = tmp242_236;
        tmp248_242[41] = -71;
        byte[] tmp254_248 = tmp248_242;
        tmp254_248[42] = 30;

        Cipher localCipher = Cipher.getInstance("AES/GCM/NoPadding");
        GCMParameterSpec localGCMParameterSpec = new GCMParameterSpec(128, arrayOfByte, 0, 12);
        localCipher.init(2, secretKey, localGCMParameterSpec);
        arrayOfByte = localCipher.doFinal(arrayOfByte, 12, arrayOfByte.length - 12);
        
        for (byte x : arrayOfByte) {
            System.out.print((char)x);
        }

        System.out.println();
    }
}

1pt_3verywhere}

最後に2つのflagを合わせることで完全なflagを得ることができます.

ctf4b{jav4_and_j4va5cr1pt_3verywhere}

Crypto

Noisy equations [Easy, 76solved, 261pts]

noise hides flag.

nc noisy-equations.quals.beginners.seccon.jp 3000

problem.py

from os import getenv
from time import time
from random import getrandbits, seed


FLAG = getenv("FLAG").encode()
SEED = getenv("SEED").encode()

L = 256
N = len(FLAG)


def dot(A, B):
    assert len(A) == len(B)
    return sum([a * b for a, b in zip(A, B)])

coeffs = [[getrandbits(L) for _ in range(N)] for _ in range(N)]

seed(SEED)

answers = [dot(coeff, FLAG) + getrandbits(L) for coeff in coeffs]

print(coeffs)
print(answers)

アプローチ:差をとることでノイズを消去する

problem.pyを読むと44変数(これはncすれば分かります)の連立方程式の解がflagになっていることが分かります.
ですが,この連立方程式はノイズが加わったanswersを与えられるため,そのままでは解くことができません.
しかし,ありがたいことにノイズはSEDDで固定されるため,coeffsanswersを2回取得し,差をとることでノイズを消去することができます.

f:id:satto1237:20200525213030p:plain

f:id:satto1237:20200525213046p:plain

f:id:satto1237:20200525213055p:plain

あとは連立方程式を解くだけです.

SymPyNumPy逆行列を求めようとしたら微妙に上手くいかなかったのでガウスジョルダンの消去法で連立方程式の解を求めます.

ソルバは以下のようになります.

from random import getrandbits, seed
from pwn import *
import numpy as np

r = remote('noisy-equations.quals.beginners.seccon.jp', 3000)

coeffs_a = eval(r.recvline().decode().strip())
answers_a = eval(r.recvline().decode().strip())


r = remote('noisy-equations.quals.beginners.seccon.jp', 3000)
coeffs_b = eval(r.recvline().decode().strip())
answers_b = eval(r.recvline().decode().strip())

coeffs = [[a - b for a,b in zip(coeff_a, coeff_b)] for coeff_a, coeff_b in zip(coeffs_a,coeffs_b)]
answers = [a - b for a, b in zip(answers_a,answers_b)]

coeffs_mat = np.array(coeffs)
answers_mat = np.array(answers)

for i in range(len(coeffs_mat)-1):
    for j in range(i+1, len(coeffs_mat)):
        coef = coeffs_mat[j][i] / coeffs_mat[i][i]
        coeffs_mat[j] -= coeffs_mat[i] * coef
        answers_mat[j] -= answers_mat[i] * coef

for i in range(len(coeffs_mat)-1, 0, -1):
    answers_mat[i] /= coeffs_mat[i][i]
    coeffs_mat[i] /= coeffs_mat[i][i]
    for j in range(i):
        answers_mat[j] -= answers_mat[i] * coeffs_mat[j][i]
        coeffs_mat[j][i] = 0

print(answers_mat) 

flag = ''
for x in answers_mat[1:]:
    flag += chr(round(x))
print('c' + flag)
> python  solve.py
[1.4373191156143338e+78 116.00000000002152 102.00000000002716
 51.99999999999115 97.99999999999812 122.99999999991692 114.00000000001545
 52.00000000002947 110.00000000002872 99.99999999992944 48.00000000004317
 109.00000000003224 94.99999999995093 52.99999999994877 50.999999999970356
 51.00000000005113 100.00000000006227 95.00000000002443 49.00000000000767
 53.00000000000038 95.00000000005183 110.00000000002365 50.99999999993853
 99.00000000000699 51.000000000033324 53.000000000014914
 53.000000000011006 51.99999999985527 114.00000000002838
 120.99999999998803 95.00000000000075 102.00000000002628 47.99999999999231
 114.0000000000347 95.00000000002042 53.00000000003555 50.99999999998389
 98.99999999995198 116.99999999995693 113.99999999994883 48.99999999994941
 54.999999999976076 121.00000000008183 125.00000000002167]
ctf4b{r4nd0m_533d_15_n3c3554ry_f0r_53cur17y}

1文字目は誤差ってたので無視しました

ctf4b{r4nd0m_533d_15_n3c3554ry_f0r_53cur17y}

RSA Calc [Medium, 52solved, 319pts]

F(1337)=FLAG!

nc rsacalc.quals.beginners.seccon.jp 10001

server.py

from Crypto.Util.number import *
from params import p, q, flag
import binascii
import sys
import signal


N = p * q
e = 65537
d = inverse(e, (p-1)*(q-1))


def input(prompt=''):
    sys.stdout.write(prompt)
    sys.stdout.flush()
    return sys.stdin.buffer.readline().strip()

def menu():
    sys.stdout.write('''----------
1) Sign
2) Exec
3) Exit
''')
    try:
        sys.stdout.write('> ')
        sys.stdout.flush()
        return int(sys.stdin.readline().strip())
    except:
        return 3


def cmd_sign():
    data = input('data> ')
    if len(data) > 256:
        sys.stdout.write('Too long\n')
        return

    if b'F' in data or b'1337' in data:
        sys.stdout.write('Error\n')
        return

    signature = pow(bytes_to_long(data), d, N)
    sys.stdout.write('Signature: {}\n'.format(binascii.hexlify(long_to_bytes(signature)).decode()))

def cmd_exec():
    data = input('data> ')
    signature = int(input('signature> '), 16)

    if signature < 0 or signature >= N:
        sys.stdout.write('Invalid signature\n')
        return

    check = long_to_bytes(pow(signature, e, N))
    if data != check:
        sys.stdout.write('Invalid signature\n')
        return

    chunks = data.split(b',')
    stack = []
    for c in chunks:
        if c == b'+':
            stack.append(stack.pop() + stack.pop())
        elif c == b'-':
            stack.append(stack.pop() - stack.pop())
        elif c == b'*':
            stack.append(stack.pop() * stack.pop())
        elif c == b'/':
            stack.append(stack.pop() / stack.pop())
        elif c == b'F':
            val = stack.pop()
            if val == 1337:
                sys.stdout.write(flag + '\n')
        else:
            stack.append(int(c))

    sys.stdout.write('Answer: {}\n'.format(int(stack.pop())))


def main():
    sys.stdout.write('N: {}\n'.format(N))
    while True:
        try:
            command = menu()
            if command == 1:
                cmd_sign()
            if command == 2:
                cmd_exec()
            elif command == 3:
                break
        except:
            sys.stdout.write('Error\n')
            break


if __name__ == '__main__':
    signal.alarm(60)
    main()

アプローチ:署名を合成する

server.pyを読むと計算結果が1337になる関数Fの署名を得ることができればflagも取得できることが分かります.
しかし,署名を行うには次の制約があるようです.

  • 署名対象にFが含まれていてはならない
  • 署名対象に1337が含まれていてはならない

次に計算部分のロジックを確認すると1336,1,+,Fであれば計算結果が1337になることが分かります.
あとは署名を行うだけなのですが,1336,1,+,Fは署名の制約を受けるため直接署名を行うことができません(1336,1,+,FにはFが含まれているため).
ここで, (m_1^{d} \bmod n \times m_2^{d} \bmod n ) \bmod n = (m_1 m_2)^{d} \bmod nとなることを利用し,この制約を回避します.
具体的には1336,1,+,F232340431793906185350214として素因数分解し,Fまたは1337が含まれないトークンを2つ生成し, これらのトークンに対して署名を行い,合成することで1336,1,+,Fの署名を入手します.

ソルバは以下のようになります.

from pwn import *
from Crypto.Util.number import *

TOKEN = b'1336,1,+,F'

t1 = 12530004045462689
t2 = 2 * 181**2 * 283

r = remote('rsacalc.quals.beginners.seccon.jp', 10001)


received = r.recvline()
N = int(received.decode().strip().split(' ')[1],10)

received = r.recvuntil('> ')
r.sendline(b'1')
r.sendline(long_to_bytes(t1))
received = r.recvline()
t1_sign = int(received.decode().strip().split(' ')[2],16)

received = r.recvuntil('> ')
r.sendline(b'1')
r.sendline(long_to_bytes(t2))
received = r.recvline()
t2_sign = int(received.decode().strip().split(' ')[2],16)

token_sign = t1_sign * t2_sign % N
received = r.recvuntil('> ')
r.sendline(b'2')
r.sendline(TOKEN)
r.sendline(hex(token_sign)[2:])
received = r.recvline()

print(received.decode())
python solve.py
data> signature> ctf4b{SIgn_n33ds_P4d&H4sh}

ctf4b{SIgn_n33ds_P4d&H4sh}

f:id:satto1237:20200525221359p:plain

因みに3rd bloodでした(ちょっと嬉しかった)

まとめ

  • 同期強い(CTF初参加の同期もflagとってたのですごいなと思いました)
  • Pwnとスマートコントラクト何も分からん(勉強する(これずっと言ってる
  • Encrypter解けなかったのかなりつらかった(Beginner向けCTFなんだからソースコード配布しても良かったのでは???Padding Oracle Attackに辿り着くまでに余計なGuessingが発生するし、PKCS#7パディングを使っていて、暗号利用モードがCBCってことは明示しても良かったのでは???