ふるつき

v(*'='*)v かに

3kCTF 2020 writeup

We got 1st place!! Thanks to all the admins for holding a good competition.

f:id:Furutsuki:20200726110824p:plain

overall challenge files and scripts are here

[rev/misc/crypto] pyzzle1/2

The given file pyzzle is an AST produced by libCST. @st98 found a way to recover it into python script.

from libcst import *

with open('pyzzle', 'r') as f:
  program = f.read()

cst = eval(program)
with open('original.py', 'w') as f:
  f.write(cst.code)

The logic of a recovered script file was quite simple. It did just XORing.

import binascii

plaintext = "REDACTED"

def exor(a, b):
    temp = ""
    for i in range(n):
        if (a[i] == b[i]):
            temp += "0"
        else:
            temp += "1"
    return temp


def BinaryToDecimal(binary):
    string = int(binary, 2)
    return string

# encryption
PT_Ascii = [ord(x) for x in plaintext]

PT_Bin = [format(y, '08b') for y in PT_Ascii]
PT_Bin = "".join(PT_Bin)

n = 26936
K1 = '...'
K2 = '...'

L1 = PT_Bin[0:n]
R1 = PT_Bin[n::]

f1 = exor(R1, K1)
R2 = exor(f1, L1)
L2 = R1

f2 = exor(R2, K2)
R3 = exor(f2, L2)
L3 = R2

R3 = '...'
L3 = '...'
cipher = L3+R3

So decryption was also simple.

from params import K1, K2, L3, R3
from Crypto.Util.number import *


def exor(a, b):
    temp = ""
    for i in range(n):
        if (a[i] == b[i]):
            temp += "0"
        else:
            temp += "1"
    return temp

n = 26936

# L3 = R2 = f1 ^ L1 = R1 ^ K1 ^ L1
# R1 = f2 ^ L2 = (R2 ^ K2) ^ (R1) = (f1 ^ L1) ^ K2 ^ R1 = (R^1 ^ K1) ^ L1 ^ K2 ^ R1 = K1 ^ K2 ^ L1
L1 = exor(exor(R3, K1), K2)
R1 = exor(exor(L3, K1), L1)

plaintext = long_to_bytes(int(L1 + R1, 2))
with open("plaintext", "wb") as f:
    f.write(plaintext)

The first flag was in the comment section of plaintext: 3k{almost_done_shizzle_up_my_nizzle}.

The plaintext was the STP format file. It had the edges and vertices with its coordinates. Let's draw them on the canvas.

from PIL import Image, ImageDraw

lines = open("plaintext2.stp").read().strip().split("\n")
points = {}
for line in lines:
    if not line.startswith("DD"):
        continue
    _, idx, x, y = line.strip().split(" ")
    points[int(idx)] = (int(x), int(y))

img = Image.new("RGB", (2200, 200))
draw = ImageDraw.Draw(img)

for line in lines:
    if not line.startswith("E "):
        continue
    _, p1, p2, _ = line.strip().split(" ")
    p1 = points[int(p1)]
    p2 = points[int(p2)]

    draw.line([p1, p2], fill=(255, 255, 255), width=1)

img.save("flag.png")

f:id:Furutsuki:20200726112229p:plain

[rev] microscopic

There is a key checking logic in the sub_F7C. It is straightforward, requiring that (len(input) ^ input[i]) + i == bss_0x202020[i].

xs = [0x14,0x4D,0x5E,0x4C,0x4A,0x4E,0x1D,0x51,0x56,0x5C,0x4C,0x5F,0x84,0x4F,0x5F,0x51,0x65,0x6F,0x62,0x62,0x56,0x6A,0x58,0x8F,0x5A,0x6A,0x5C,0x70,0x7A,0x70,0x6C,0x69,0x62,0x99,0x63,0x76,0x74,0x2B,0x80]
l = len(xs)
ys = []
for i, x in enumerate(xs):
    ys.append(chr(x - i ^ l))
print("".join(ys))

[rev] Passage

The binary is based on the printbf. So I dumped brainf*ck instructions from memory and decode by the following script.

import collections

lines = open("instructions").read().strip().split("\n")
bf = ""
for line in lines:
    inst = int(line[-2:], 16)
    count = int(line[8:10], 16)

    if inst == 18: #A
        bf += "+" * count
    elif inst == 15: #B
        bf += "<" * count
    elif inst == 14: #F
        bf += ">" * count
    elif inst == 13: #Z
        bf += "[-]"
    elif inst == 12: #]
        bf += "]"
    elif inst == 11: #[
        pass
    elif inst == 10: #[
        pass
    elif inst == 9: #[
        bf += "["
    elif inst == 6: #.
        pass
    elif inst == 5: #.
        bf += "."

print(bf)

Then I got a brainf*ck script. I wrote a simple interpreter because printbf's behaviour is a bit of different to usual interpreter. By emulating the script, I found some ascii-range values on the memory. So I dumped it then I got the flag.

The following is the my interpreter and solution script.

import string

table = set([ord(c) for c in string.ascii_letters + string.digits + ' -{}_'])

pc = 0
ptr = 0
mem = [0 for _ in range(65536)]

jumplist = {}
code = open("code.bf").read().strip()
while pc < len(code):
    if code[pc] == '+':
        mem[ptr] = (mem[ptr] + 1) % 256

    elif code[pc] == '-':
        mem[ptr] = (mem[ptr] - 1) % 256

    elif code[pc] == '>':
        ptr = (ptr + 1) % 65536

    elif code[pc] == '<':
        ptr = (ptr - 1) % 65536

    elif code[pc] == '[':
        cnt = 0
        if pc not in jumplist:
            pc2 = pc + 1
            while True:
                if code[pc2] == ']':
                    if cnt == 0:
                        jumplist[pc2] = pc-1
                        jumplist[pc] = pc2
                        break
                    else:
                        cnt -= 1
                elif code[pc2] == '[':
                    cnt += 1
                pc2 += 1

        if mem[ptr] == 0:
            pc = jumplist[pc]
            print([chr(v) for v in mem if v in table])

    elif code[pc] == ']':
        pc = jumplist[pc]

    elif code[pc] == '.':
        pass
        # print(mem[ptr], ",", end="")

    
    pc += 1

import code
code.interact(local=locals())

[crypto] once upon a time

The given encryption program is based on https://github.com/MatthewDarnell/SCSS. The difference were:

  • delete decryption
  • redact initialize key

So our task is found a redacted key and decrypt using the referenced repository. The key wasn't in the source code but in the compiled binary. Just reverse it and decrypt by ofb mode, then we could get the flag: 3k{my_hands_are_registered_as_lethal_weapons_that_means_we_get_into_a_fight_i_accidentally_kill_you_i_go_to_jail}.

[crypto] You shall not get my cookies

Be careful that the banner's corner formed by pkcs7 (shit!). If you noticed that, just do the padding oracle encryption attack.

from ptrlib import padding_oracle_encrypt, Socket
from Crypto.Util.Padding import pad
from binascii import hexlify, unhexlify
from logging import getLogger, WARN

getLogger("ptrlib.pwn").setLevel(WARN + 1)

def decrypt(c):
    sock = Socket("youshallnotgetmycookies.3k.ctf.to", 13337)
    sock.sendlineafter("your cookie:", hexlify(c).upper())
    result = sock.recvline().decode()
    result = sock.recvline().decode()
    sock.close()
    if 'Nop' in result:
        return True
    elif "rude" in result:
        raise Exception("RUDE!!!")
    else:
        return False

plain = pad(b'Maple Oatmeal Biscuits', 16)
print(padding_oracle_encrypt(decrypt, plain, bs=16))

By the way, my network issue and physical distance make my script running over 1 hour.

[crypto] RSA textbook

The challenge is pretty similar to De1CTF 2020 - Easy RSA. The difference is d's bit length is a bit of long and three of e are given this time. The paper records the lattice when the three e are given.

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


N = 12170190688004538444277411858659743698858881698522002560104158646993985233366286537140023919311475138247627293483294012428391264973961998717641256731743650816966630823200651379840685959607068295100050560483372204779059185916233606668058455492543750789590662887744463330804561435647720395428571207395720326720079784739378979190536116850099548129878814526898868252532680831715727722854511143304480680172052813141124420045611849828057723775363105949126828405455366200106404262310675794659470280643495090398585218024841176044368628727517113941678716688564185680961627362553111203039001198980515164358280669308454156335407
e1 = 3608925965574376523567945341556278002516414013521504911184984382205274952167864225371696017993914370497201512168776166664088733042670271646970202280312387281923684119807730941123751515160638485698825644259362763695807647636424870261387602647920252532625627698043754500477196359587280636895393200790995388403075695605752313259071472848947759665811971017441614507395695166977173983209874826569262567456954762013063380865150534725774724048932079149474773099227628235894219595993039786915437293792843467687437824528953466687440976745496029400371187996064849843219741352701174026683144995955926404403452468786948428940027
e2 = 2705742985834249419593731294742640629063082486092845443539270908653438835415907814640922583157596954837534793829979420920198220583127130141172579878212440120192417321752335684151522579530049628576946957043579231780623871429784888205786958275264941043957214384797910571377927751881376467152335343819159923905777819744174333126671522426796324838179520524018483919571215970759256674475827355541411323954244780923617745270386685895731319052600788632072228874066127098381849641952288244849313571762646260481179154523761739298818111645172710767353435965052896552293260158397774508443428719331456374349726714924857674679205
e3 = 3035365189985498586303047048784147960258852204370735950376858958412525602591256013408704341559429814208409740880540723564047453268194004007025515302654689487102249859432374152268384575758806644375008555596328108954751739613261097357911851867276625220692495609283168900124098676799207897772849526250849182230188000946516269730320060104809776594584791996622731993896557212016228453224349936398794285686351250712690093264997448606619172537355077652043467103166971300884698914802166607190765845078412359425449726466096602648615851255067426028168676632944926874766408639251537680297862420982004104687562994618386282503979
c = 8428440225372437159697731953040047552034760946696949785472254831497076019605441760668381296291759447497600405504562269104549915534101891117092326606340168399884372637000427767246446007973335837452013998684912761764510307152056346432612919127031634162077989869360717849451315550957073076040273291239841901635055739913150280146317663383345358421035311465389299247093408775682992619258004736599439564552486105106585061374815530581898589428950106020942797612406757368312750240904783591854877330620611395246954169095417676892061171148418509328414536101813085141351870212082214659362996288288403303642365539978759986883582



alpha2 = 815./2048
M1 = int(gmpy2.mpz(N)**(3./2))
M2 = int( gmpy2.mpz(N) )
M3 = int(gmpy2.mpz(N)**(3./2 + alpha2))
M4 = int( gmpy2.mpz(N)**(0.5) )
M5 = int( gmpy2.mpz(N)**(3./2 + alpha2) )
M6 = int( gmpy2.mpz(N)**(1.+alpha2) )
M7 = int( gmpy2.mpz(N)**(1.+alpha2) )
D = diagonal_matrix(ZZ, [M1, M2, M3, M4, M5, M6, M7, 1])
B = Matrix(ZZ, [ [1, -N,   0,  N**2,   0,      0,      0,    -N**3],
                 [0, e1, -e1, -e1*N, -e1,      0,   e1*N,  e1*N**2],
                 [0,  0,  e2, -e2*N,   0,   e2*N,      0,  e2*N**2],
                 [0,  0,   0, e1*e2,   0, -e1*e2, -e1*e2, -e1*e2*N],
                 [0,  0,   0,     0,  e3,  -e3*N,  -e3*N,  e3*N**2],
                 [0,  0,   0,     0,   0,  e1*e3,      0, -e1*e3*N],
                 [0,  0,   0,     0,   0,      0,  e2*e3, -e2*e3*N],
                 [0,  0,   0,     0,   0,      0,      0, e1*e2*e3] ]) * D

L = B.LLL()

v = Matrix(ZZ, L[0])
x = v * B**(-1)
phi_ = (e1*x[0,1]/x[0,0]).floor()
print(phi_)

[crypto] A hundred friends

This is appearently Hastad's broadcast attack on padded message.

As the m is large 3 ciphertexts are not enough to recover full plaintext, thus I used 5 ciphertexts.

# https://raw.githubusercontent.com/pwang00/Cryptographic-Attacks/master/Public%20Key/RSA/hastad.sage
"""
Sage implementation of Hastad's broadcast attack for small public exponent and multiple message/ciphertext pairs
"""

import binascii
import random


def linear_padding(ciphertexts, moduli, pad_array, const_array=(), e=3, eps=1/8):
#     if not(len(ciphertexts) == len(moduli) == len(pad_array) == len(const_array) == e):
#         raise RuntimeError("Moduli and ciphertext arrays have to be equal in length, and contain at least as many elements as e")
 
    '''
    Initialization with placeholders
    ciphertexts: ciphertext array
    T_array: Chinese Remainder Theorem coefficients
    moduli: Modulus array
    pad_array: Linear coefficient of padding applied to the message during encryption
    const_array: constant pad added to message during encryption (optional)
    '''

    n = len(ciphertexts)

    T_array = [Integer(0)]*n
    crt_array = [Integer(0)]*n
    polynomial_array = []

    for i in range(n):
        crt_array = [0]*n
        crt_array[i] = 1
        T_array[i] = Integer(crt(crt_array,moduli))

    G.<x> = PolynomialRing(Zmod(prod(moduli)))
    for i in range(n):
        polynomial_array += [T_array[i]*((pad_array[i]*x+const_array[i])^e - Integer(ciphertexts[i]))] #Representation of polynomial f(x) = (A*x + b) ^ e - C where (A*x + b) is the padding polynomial

    g = sum(polynomial_array).monic()  #Creates a monic polynomial from the sum of the individual polynomials
    roots = g.small_roots(epsilon=eps)
    return roots[0] if len(roots) >= 1 else -1



# def test_linear_padding():
#     moduli = []
#     ciphertexts = []
#     pad_array = []
#     const_array = []
#     e = 3
#     pad_bound = 2^512
#     prime_bound = 2^1024
#     m = int.from_bytes(b"p00rth0_th3_p00r", "big")
# 
#     for i in range(e):
#         pad = 1 # random.randint(0,pad_bound)
#         constant = random.randint(0,pad_bound)
#         pad_array += [pad]
#         const_array += [constant]
#         p = random_prime(prime_bound,proof=false)
#         q = random_prime(prime_bound,proof=false)
#         n = p*q
#         moduli += [n]
#         ciphertexts.append(pow(pad * m + constant,e,n))
# 
#     print(linear_padding(ciphertexts, moduli, pad_array, const_array))
#     return 0

import json
from random import sample

with open("params.json", "r") as f:
    params = json.load(f)

for i in range(1000):
    ns = []
    cs = []
    alist = []
    blist = []
    es = []
    e = 3
    paramlist = sample(params, k=5)
    for param in paramlist:
        ns.append(param["n"])
        cs.append(param["c"])
        alist.append(1)
        blist.append(param["pad"])

    res = linear_padding(cs,ns,alist,blist,e=e)
    if res == -1:
        print("NOT FOUND ({})".format(i),es)
    else:
        print(res)
        break

[misc] libcDB

jq was used to filter the result. and we could know that $maindb was defined like that . as $maindb from the error message. The query like this was to steal the username/password: .search fprintf 0x4b970 name=$maindb.users[].username.

Then we could get the admin's username and password and could execute .secret to get the flag: 3k{jq_is_r3ally_HelpFULL_3af4bcd97f5}.