After four years of team formation, we organized our first edition of Bauhinia CTF last weekend. There are over 650 teams registered and over 200 teams scored. This year, I made one crypto challenge, How to Stop Time. I also coauthored a web/crypto challenge, Amnesia, with @chthollic_.

This post is served as a short writeup of How to Stop Time, a crypto challenge with six solves during the contest period.

Challenge Summary⌗

Good CTF challenges never die. They will be remembered and reused.

Mystiz loves to pay tribute to (i.e., plagarise) challenges. This time he referenced (i.e., copied) code snippets from at least five challenges to build the most unoriginal crypto challenge ever. Also, he is really verbose and there are a lot of red herrings. Can you avoid the rabbit holes and find the vulnerable one(s)?

nc HOST PORT

Attachments: chall.py, mathy.py

In this challenge, two 512-bit numbers $g$ and $x$ are generated. We are asked to send a 512-bit prime $q$ such that $p := 4q+1$ is also a prime. After that, we are given $g$ and $h := g^x \ \text{mod}\ p$. Finally, we are asked to send $x'$. If $x = x'$, we consider that as a win.

If we win 256 times in a row, we will be given the flag.

By the way, there are a lot of strange things going on. Some served as red herring, while some are not. These are some of them:

  1. $g$ and $x$ are generated by Python’s random package,
  2. $\texttt{is\_prime}$ is an implementation based on That-crete log from UIUCTF 2022,
  3. $p := 4q + 1$ is used instead of $p := 2q + 1$.
  4. There are a lot of comments… I have never been more verbose.

Solution⌗

This challenge is implemented in August 2022, approximately one year ago, to serve as an easy-ish challenge as a warm up. The idea came to my mind while I was solving That-crete log from UIUCTF 2022, and everything comes from the $\texttt{is\_prime}$ function:

def is_prime(n):
    bases = [...] # 207 numbers omitted
    for i in range(2, min(256, n)):
        if n % i == 0:
            return False
    if n < 256:
        return True
    return miller_rabin(bases, n)

There are some papers mentioning how to generate strong pseudoprimes, i.e., the composite numbers that passes the Miller-Rabin test. However, while I was attempting that challenge, I found that every $n < 0$ is considered a prime by $\texttt{is\_prime}$. Although it seemed to be useful, I could not make use of that to solve the challenge. That is why How to Stop Time appeared.

Now let’s get back to our challenge. If we send a 512-bit $q$ which is also negative, then $\texttt{is\_prime}(q)$ returns $\texttt{true}$. Similarly, $p := 4q + 1 < 0$ is also considered a prime.

What I did is to find a pair of $(r, k)$ such that $r$ is a small prime, $2^{513} \leq r^k < 2^{514}$ and $r^k \equiv 3 \ (\text{mod}\ 4)$. For instance, $(r, k) = (97523, 31)$ is one of the pairs.

With $(r, k)$, we then can define $p := -r^k$ and $q := (p - 1)/4$. With $g$ and $h := g^x\ \text{mod}\ r^k$, we can easily recover $x$ with Pohlig-Hellman because the modulus is smooth. Being lazy, I simply use h.log(g) from Sage to recover $x$.

Solution script⌗ 

from pwn import *
from rich.progress import track

r = remote('chall-hk.pwnable.hk', 30001)

for i in track(range(256)):
    p = -97523^31
    assert p % 4 == 1
    q = (p - 1) // 4
    r.sendlineafter(b'[<] q = ', str(q).encode())

    r.recvuntil(b'[>] g = ')
    g = int(r.recvline().decode())

    r.recvuntil(b'[>] h = ')
    h = int(r.recvline().decode())

    Zp = Zmod(p)
    g, h = Zp(g), Zp(h)

    x = h.log(g)
    r.sendlineafter(b'[<] x = ', str(x).encode())

r.interactive()

Retrospective⌗

Given that this is not difficult, I expect that there will be more solves. There are some reasons that I could think of:

  1. The bug is really cleverly hidden (I don’t think this is true).
  2. There are too much red herring in the challenge.
  3. Players assumed that the challenges I wrote are hard.

During the contest, I often feel players will be disappointed knowing the intended solution being negative numbers. Please let me know what you think.