2022 | DownUnderCTF | misc

last digit

#binary search

题目

Can you get the flag given its last digit?

nc 2022.ductf.dev 30003

last-digit.py

with open('/flag.txt', 'rb') as f:
    FLAG = int.from_bytes(f.read().strip(), byteorder='big')

assert FLAG < 2**1024

while True:
    print("Enter your number:")

    try:
        n = FLAG * int(input("> "))
        print("Your digit is:", str(n)[-1])
    except ValueError:
        print("Not a valid number! >:(")

Dockerfile

FROM python:3.10.7

RUN /usr/sbin/useradd --no-create-home -u 1000 ctf

COPY flag.txt /
COPY last-digit.py /home/ctf/

RUN chmod a+x /home/ctf/last-digit.py

RUN apt-get update && apt-get install -y socat && rm -rf /var/lib/apt/lists/*

USER ctf

CMD socat \
        TCP-LISTEN:1337,reuseaddr,fork \
        EXEC:"python -u /home/ctf/last-digit.py"

解题思路

• Python 3.10.7 新增了 integer string conversion length limitation，在默认设置下，十进制数在 int 和 str 间相互转换，位数不能超过 \(4300\) 位，否则会触发 ValueError 异常
• str(n) 可能触发 ValueError 异常，结合输入来二分求出 Flag

• 参考 Manger's Attack 进行二分，边界 \(B\) 为 \(10^{4300}\)

  • 通过 \(10^x\) 确定 Flag 的位数，若 \(10^{x-1} \times\) FLAG 的位数小于 \(4300\) 而 \(10^x \times\) FLAG 的位数大于 \(4300\)，那么 \(10^x \times\) FLAG \(\in [B, 10B)\)，由此可初步确定 FLAG \(\in [\frac{B}{10^x}, \frac{B}{10^{x-1}})\)
  • 设当前 FLAG 的最小值 \(mn=\lfloor\frac{B}{10^x}\rfloor\)，当前 FLAG 的最大值 \(mx=\lfloor\frac{B}{10^{x-1} }\rfloor\)，\(y=\lfloor\frac{2B}{mx+mn}\rfloor\)，则 \(y \times \lfloor\frac{mx+mn}{2}\rfloor \approx B\)
  • 向服务器发送 \(y\)，若触发 ValueError 说明 \(y \times\) FLAG \(\ge B\)，则设 \(mn=\lceil\frac{B}{y}\rceil\)，否则设 \(mx=\lfloor\frac{B}{y}\rfloor\)

  import pwn
  from Crypto.Util.number import long_to_bytes
  
  B = 10 ** 4300
  
  conn = pwn.remote('2022.ductf.dev', 30003)
  l, r = 4000, 4300
  while l < r:
      mid = (l + r) // 2
      conn.sendafter('>', f'{10 ** mid}\n')
      ret = conn.recvline().decode()
      if '>:(' in ret:
          r = mid - 1
      else:
          l = mid + 1
  
  mn = B // 10 ** l
  mx = B // 10 ** (l - 1)
  
  while mx > mn:
      tmp = 2 * B // (mx + mn)
      conn.sendafter('>', str(tmp) + '\n')
      ret = conn.recvline().decode()
      if '>:(' in ret:
          mn = (B + tmp) // tmp
      else:
          mx = B // tmp
  
  print(long_to_bytes(mn))
  

• 官方 WP 直接二分输入，最后根据边界求得 FLAG

  import pwn
  from Crypto.Util.number import long_to_bytes
  
  def oracle(x):
      conn.sendlineafter(b'> ', str(x).encode())
      o = conn.recvline().decode()
      return '>:(' in o
  
  conn = pwn.remote('192.168.56.104', 30003)
  
  U = 10 ** 4300
  FLAG_BITS = 1024
  
  lower = U // 2 ** FLAG_BITS
  upper = U
  # FLAG 有 1024 位，至多需要二分 1024 次
  for _ in range(1024):
      middle = (upper + lower) // 2
      if oracle(middle):
          upper = middle - 1
      else:
          lower = middle + 1
  
  f = (U + middle) // middle
  
  print(long_to_bytes(f))
  

• 虽然没有随机算法，但是实际交互时不同连接 limitation 时有时无 (ŏωŏ) 原因不明...

Flag

CTF{14288_bits_should_be_enough_for_anybody_:)}

---

最后更新: 2022年9月26日 15:02:47

Contributors: YanhuiJessica
Pageviews:

评论