[zer0pts CTF 2022] MathHash

server.py

import struct
import math
import signal
import os

def MathHash(m):
    hashval = 0
    for i in range(len(m)-7):
        c = struct.unpack('<Q', m[i:i+8])[0]
        t = math.tan(c * math.pi / (1<<64))
        hashval ^= struct.unpack('<Q', struct.pack('<d', t))[0]
    return hashval

if __name__ == '__main__':
    FLAG = os.getenv('FLAG', 'zer0pts<sample_flag>').encode()
    assert FLAG.startswith(b'zer0pts')

    signal.alarm(1800)
    try:
        while True:
            key = bytes.fromhex(input("Key: "))
            assert len(FLAG) >= len(key)

            flag = FLAG
            for i, c in enumerate(key):
                flag = flag[:i] + bytes([(flag[i] + key[i]) % 0x100]) + flag[i+1:]

            h = MathHash(flag)
            print("Hash: " + hex(h))
    except:
        exit(0)

 

MathHash function is quite complicated and hard to manipulate. However we know that first 8 bytes for flag is "zer0pts{".

 

Let's see how to extract $flag[8]$.

 

Once you set key bytes are all zero except $key[1] = 0xFF$, only $m[0:8], m[1:9]$ are effected. Moreover, since we already know $flag[0:8]$, $H(m[0:8])$ can be calculated locally.

 

Therefore $H(flag) \oplus H(flag \oplus key) = H(flag[0:8]) \oplus H(flag[0:8] \oplus 0x00FF000000000000) H(flag[1:9]) \oplus H(flag[1:9] \oplus 0xFF00000000000000)$.

 

You can bruteforce $flag[9]$ $0x20 to 0x7f$ to satisfy above equation. The logic for recover $flag[10]$, $flag[11]$, ... are same as above.

 

When I implement an actual exploit code, I bruteforced each two bytes.

 

solver.py

from pwn import *

from tqdm import tqdm
import struct
import math
import random
from itertools import product

def MathHash(m):
    hashval = 0
    for i in range(len(m)-7):
        c = struct.unpack('<Q', m[i:i+8])[0]
        t = math.tan(c * math.pi / (1<<64))
        hashval ^= struct.unpack('<Q', struct.pack('<d', t))[0]
    return hashval


r = remote('misc.ctf.zer0pts.com', 10001)

def interactive(x):
    r.recvuntil(b': ')
    r.sendline(x)
    r.recvuntil(b': ')
    return int(r.readline()[2:], 16)

flag = bytearray(b'zer0pts{s1')
flag += bytearray(25 - len(flag))

h_original = interactive('00')


brute = list(product(range(0x20,0x7f),range(0x20,0x7f)))
for i in range(10,24,1):
    cand = brute[:]    
    while True:
        next_cand = []
        delta1 = random.randint(0,255)
        delta2 = random.randint(0,255)
        query = '0'*(2*(i-7)) + hex(delta1)[2:].zfill(2) + hex(delta2)[2:].zfill(2)
        target = interactive(query) ^ h_original
        print(delta1,delta2,target)
        for v1, v2 in cand:
            m1 = flag[:i] + bytearray([v1,v2])
            h1 = MathHash(m1)
            m2 = m1[:]
            m2[i-7] = (m2[i-7] + delta1) % 0x100
            m2[i-6] = (m2[i-6] + delta2) % 0x100
#            print(m1.hex(),m2)
#            exit()

            h2 = MathHash(m2)
            if h1 ^ h2 == target:
                next_cand.append((v1,v2))
        cand = next_cand
        cand1 = []
        for v1,v2 in cand:
            if v1 not in cand1:
                cand1.append(v1)
        if len(cand1) == 1:            
            break


    flag[i] = cand[0][0]
    #flag[i+1] = cand[0][1]
    print(flag[:i+1])
        
    #break