Resolution
We’re provided with a single binary, an executable los-polllos-hermanos. Running it using strace yields:
...
seccomp(SECCOMP_SET_MODE_FILTER, 0, {len=1, filter=0x7ffdf835aaa8}) = 0
ptrace(PTRACE_TRACEME) = -1 EPERM (Operation not permitted)
...
Looking in Binary Ninja and cross-referencing, we notice a function, sub_1ad1(), called as an ELF constructor which contains the folling code:
We can patch this by right-clicking the line containing the ptrace and clicking Patch > Never Branch, yielding:
The patched binary can be saved by clicking File > Save As > Save file contents only and saving it as los-pollos-hermanos-noptrace. Running the patched binary using strace and inputting inputting 256 As (as required by the binary if you input less) yields:
...
seccomp(SECCOMP_SET_MODE_FILTER, 0, {len=1, filter=0x7fffc6fe4df8}) = 0
ptrace(PTRACE_TRACEME) = -1 EPERM (Operation not permitted)
seccomp(SECCOMP_SET_MODE_FILTER, 0, {len=1800, filter=0x7fffc6fe4e00}) = 0
seccomp(SECCOMP_SET_MODE_FILTER, 0, {len=1800, filter=0x7fffc6fe8640}) = 0
seccomp(SECCOMP_SET_MODE_FILTER, 0, {len=1800, filter=0x7fffc6febe80}) = 0
seccomp(SECCOMP_SET_MODE_FILTER, 0, {len=1800, filter=0x7fffc6fef6c0}) = 0
seccomp(SECCOMP_SET_MODE_FILTER, 0, {len=1800, filter=0x7fffc6ff2f00}) = 0
seccomp(SECCOMP_SET_MODE_FILTER, 0, {len=1800, filter=0x7fffc6ff6740}) = 0
seccomp(SECCOMP_SET_MODE_FILTER, 0, {len=1800, filter=0x7fffc6ff9f80}) = 0
seccomp(SECCOMP_SET_MODE_FILTER, 0, {len=1800, filter=0x7fffc6ffd7c0}) = 0
seccomp(SECCOMP_SET_MODE_FILTER, 0, {len=1800, filter=0x7fffc7001000}) = 0
seccomp(SECCOMP_SET_MODE_FILTER, 0, {len=1800, filter=0x7fffc7004840}) = 0
seccomp(SECCOMP_SET_MODE_FILTER, 0, {len=1800, filter=0x7fffc7008080}) = 0
seccomp(SECCOMP_SET_MODE_FILTER, 0, {len=1800, filter=0x7fffc700b8c0}) = 0
seccomp(SECCOMP_SET_MODE_FILTER, 0, {len=1800, filter=0x7fffc700f100}) = 0
seccomp(SECCOMP_SET_MODE_FILTER, 0, {len=1800, filter=0x7fffc7012940}) = 0
read(0, "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"..., 256) = 256
semop(-956211488, 0x41, 3066379857) = -1 (errno 328)
pwritev2(65, 0x148, 18446744073709551496, 1, RWF_SYNC|RWF_NOWAIT|0x20) = -1 (errno 692)
syscall_0x2b4(0x148, 0x2b4, 0xffffffffffffff88, 0x2c, 0x2c, 0x2c) = -1 (errno 906)
syscall_0x38a(0x2b4, 0x38a, 0xffffffffffffff88, 0x2c, 0x2c, 0x2c) = -1 (errno 1180)
syscall_0x49c(0x38a, 0x49c, 0xffffffffffffff88, 0x2c, 0x2c, 0x2c) = -1 (errno 1450)
syscall_0x5aa(0x49c, 0x5aa, 0xffffffffffffff88, 0x2c, 0x2c, 0x2c) = -1 (errno 1604)
syscall_0x644(0x5aa, 0x644, 0xffffffffffffff88, 0x2c, 0x2c, 0x2c) = -1 (errno 2027)
syscall_0x7eb(0x644, 0x7eb, 0xffffffffffffff88, 0x2c, 0x2c, 0x2c) = -1 (errno 2186)
syscall_0x88a(0x7eb, 0x88a, 0xffffffffffffff88, 0x2c, 0x2c, 0x2c) = -1 (errno 2414)
syscall_0x96e(0x88a, 0x96e, 0xffffffffffffff88, 0x2c, 0x2c, 0x2c) = -1 (errno 2574)
syscall_0xa0e(0x96e, 0xa0e, 0xffffffffffffff88, 0x2c, 0x2c, 0x2c) = -1 (errno 2975)
syscall_0xb9f(0xa0e, 0xb9f, 0xffffffffffffff88, 0x2c, 0x2c, 0x2c) = -1 (errno 3326)
syscall_0xcfe(0xb9f, 0xcfe, 0xffffffffffffff88, 0x2c, 0x2c, 0x2c) = -1 (errno 3459)
syscall_0xd83(0xcfe, 0xd83, 0xffffffffffffff88, 0x2c, 0x2c, 0x2c) = -1 (errno 247)
semop(3459, 0x41, 4294967176) = -1 (errno 328)
pwritev2(65, 0x148, 18446744073709551496, 44, RWF_SYNC|RWF_NOWAIT|0x20) = -1 (errno 692)
syscall_0x2b4(0x148, 0x2b4, 0xffffffffffffff88, 0x2c, 0x2c, 0x2c) = -1 (errno 906)
syscall_0x38a(0x2b4, 0x38a, 0xffffffffffffff88, 0x2c, 0x2c, 0x2c) = -1 (errno 1180)
syscall_0x49c(0x38a, 0x49c, 0xffffffffffffff88, 0x2c, 0x2c, 0x2c) = -1 (errno 1450)
syscall_0x5aa(0x49c, 0x5aa, 0xffffffffffffff88, 0x2c, 0x2c, 0x2c) = -1 (errno 1604)
syscall_0x644(0x5aa, 0x644, 0xffffffffffffff88, 0x2c, 0x2c, 0x2c) = -1 (errno 2027)
syscall_0x7eb(0x644, 0x7eb, 0xffffffffffffff88, 0x2c, 0x2c, 0x2c) = -1 (errno 2186)
syscall_0x88a(0x7eb, 0x88a, 0xffffffffffffff88, 0x2c, 0x2c, 0x2c) = -1 (errno 2414)
syscall_0x96e(0x88a, 0x96e, 0xffffffffffffff88, 0x2c, 0x2c, 0x2c) = -1 (errno 2574)
syscall_0xa0e(0x96e, 0xa0e, 0xffffffffffffff88, 0x2c, 0x2c, 0x2c) = -1 (errno 2975)
syscall_0xb9f(0xa0e, 0xb9f, 0xffffffffffffff88, 0x2c, 0x2c, 0x2c) = -1 (errno 3326)
syscall_0xcfe(0xb9f, 0xcfe, 0xffffffffffffff88, 0x2c, 0x2c, 0x2c) = -1 (errno 3459)
syscall_0xd83(0xcfe, 0xd83, 0xffffffffffffff88, 0x2c, 0x2c, 0x2c) = -1 (errno 247)
semop(3459, 0x41, 4294967176) = -1 (errno 328)
pwritev2(65, 0x148, 18446744073709551496, 44, RWF_SYNC|RWF_NOWAIT|0x20) = -1 (errno 692)
syscall_0x2b4(0x148, 0x2b4, 0xffffffffffffff88, 0x2c, 0x2c, 0x2c) = -1 (errno 906)
syscall_0x38a(0x2b4, 0x38a, 0xffffffffffffff88, 0x2c, 0x2c, 0x2c) = -1 (errno 1180)
syscall_0x49c(0x38a, 0x49c, 0xffffffffffffff88, 0x2c, 0x2c, 0x2c) = -1 (errno 1450)
syscall_0x5aa(0x49c, 0x5aa, 0xffffffffffffff88, 0x2c, 0x2c, 0x2c) = -1 (errno 1604)
syscall_0x644(0x5aa, 0x644, 0xffffffffffffff88, 0x2c, 0x2c, 0x2c) = -1 (errno 2027)
syscall_0x7eb(0x644, 0x7eb, 0xffffffffffffff88, 0x2c, 0x2c, 0x2c) = -1 (errno 2186)
...
And so one. We see a bunch of BPF filters being installed with seccomp(SECCOMP_SET_MODE_FILTER).
The chains of 14 syscalls (starting with semop and pwritev2) are repeated 16 times before the program exits with the message Error: Wrong password..
Looking into the main() function, we can see that for each character c_i of our input, c_i is used as a syscall number, and 13 other syscalls are made with the errno as the syscall number, hence the weird looking syscalls in straces output.
The last errno is then written out to an array indexed by i % 16 that we’ll call input_errno.
We understand that the BPF filters are used to hook the syscalls of the userland program, set the errno number and thus define the next syscall number (or the value written to the array).
Then each time 0 == i % 16, input_errno is multiplied with modulo 0xfffffffb by a matrix 16x16 taken from the array lying at 0x36020 with an index we’ll call mat_i.
The output vector is then checked to have all of its coordinates inferior to 0xFF.
If this condition doesn’t hold, the program exists with the wrong password message.
Otherwise, mat_i is incremented by one.
So we need to find 16 vectors of 16 bytes such that the vector input_errno obtained by mapping each input byte into the syscall loop, and multiplied by a matrix, will produce a short vector, hence the name of the challenge.
In Binary Ninja, we can select the 16x16x16x4 == 0x4000 (we have 16 16x16 matrices with 32-bit coefficients) bytes of the array at 0x36020, and run Right Click > Copy As > C Array > 32-bit Elements (Little Endian), paste the output in a file matrices.py, renaming the variables to values, and replacing the curly brackets with simple brackets.
The first step is to fetch the map from input chars from errnos made by the BPF filters. One way could be to reverse-engineer them but they seem big at there’s lots of them. The other way would be to fetch the value of the rdx register at the end of the syscall loop at 0x2308.
We can fetch the whole map using:
def _get_code_gdb(char, ind=0):
input_content = bytearray(os.urandom(256))
input_content[ind] = char
with tempfile.NamedTemporaryFile() as tmp:
open(tmp.name, "wb").write(input_content)
cmd = "sudo gdb -ex \"b *(0x0000555555554000+0x00002308)\"" + \
f" -ex \"r < {tmp.name}\"" + " -ex \"c\""*ind + \
" -ex \"p \$rdx\" -ex \"set confirm off\"" + \
" -ex \"quit\" ./los-polllos-hermanos-noptrace | tail -n1"
output = subprocess.check_output(cmd, shell=True)
if b"exited" in output:
ret = None
else:
ret = int(output.split(b" = ")[-1], 0)
print(ind, char, ret)
return ret
def get_codes():
with ThreadPoolExecutor() as executor:
futures = {executor.submit(_get_code_gdb, i, ind=0): i for i in range(256)}
return {future.result(): i for future, i in futures.items()}
The map returned by get_codes() is the inverse map of the one mentionned above for convenience (we’ll want to get an input byte from a wanted errno).
In order to fetch a short vector in the lattices generated by the constant matrices, we can run the LLL or the BKZ algorithms in sage:
import matrices
# ...
def main():
p = 0xfffffffb
codes = get_codes()
output = b""
for i in range(16):
# Fetch current matrix
m_i = Matrix(ZZ, 16, 16, matrices.values[i*256:i*256+256])
# Embed it in a matrix for taking account with the modulo
# ( m_i | I )
# ( I*p | 0 )
# Where "I" stands for the 16x16 identity matrix.
aug_m_i = m_i.augment(Matrix.identity(16))
aug_m_i = aug_m_i.stack(Matrix.identity(16).augment(Matrix(16))*p)
# Run the BKZ algorithm.
red_i = IntegerLattice(aug_m_i).BKZ()
# Get a shortest vector and make sure all of it's coefficients are positive.
sv = red_i[0][:16].apply_map(abs)
# Get the input bytes that map to the errnos in order to produce the shortest vector.
preimage = (sv * m_i.inverse() % p).apply_map(lambda e: codes[e])
output += b''.join(map(p8, preimage))
open("/tmp/output.bin", "wb").write(output)
Using /tmp/output.bin as input to los-polllos-hermanos yields the flag:
$ ./los-polllos-hermanos < /tmp/output.bin
Congrats! You can validate the challenge with the flag:
FCSC{ TRUNCATED }
Full script
import errno
from pwn import *
import process
from concurrent.futures import ThreadPoolExecutor
import os
import matrices
from sage.all import *
from sage.modules.free_module_integer import IntegerLattice
setattr(errno, "EHWPOISON", 139)
def _get_code_gdb(char, ind=0):
input_content = bytearray(os.urandom(256))
input_content[ind] = char
with tempfile.NamedTemporaryFile() as tmp:
open(tmp.name, "wb").write(input_content)
cmd = "gdb -ex \"b *(0x0000555555554000+0x00002308)\"" + \
f" -ex \"r < {tmp.name}\"" + " -ex \"c\""*ind + \
" -ex \"p \$rdx\" -ex \"set confirm off\"" + \
" -ex \"quit\" ./los-polllos-hermanos-nopatrace | tail -n1"
output = subprocess.check_output(cmd, shell=True)
if b"exited" in output:
ret = None
else:
ret = int(output.split(b" = ")[-1], 0)
print(ind, char, ret)
return ret
def get_codes():
with ThreadPoolExecutor() as executor:
futures = {executor.submit(_get_code_gdb, i, ind=0): i for i in range(256)}
return {future.result(): i for future, i in futures.items()}
def main():
p = 0xfffffffb
codes = get_codes()
output = b""
for i in range(16):
m_i = Matrix(ZZ, 16, 16, matrices.values[i*256:i*256+256])
aug_m_i = m_i.augment(Matrix.identity(16))
aug_m_i = aug_m_i.stack(Matrix.identity(16).augment(Matrix(16))*p)
red_i = IntegerLattice(aug_m_i).BKZ()
sv = red_i[0][:16].apply_map(abs)
preimage = (sv * m_i.inverse() % p).apply_map(lambda e: codes[e])
output += b''.join(map(p8, preimage))
open("/tmp/output.bin", "wb").write(output)
if "__main__" == __name__:
main()