This is yet another annual Firebird CTF and I only wrote one cryptography challenge this time, Goldilocks. There were one solve (out of 53 participating teams) during the contest period.

Challenge Summary⌗

If you think discrete log is too easy, try discrete log log. It is easier.

nc HOST PORT

Attachments: chall.py

In this challenge, we are given primes $p, q$ such that $p = 2q + 1$ and $p$ is 1024 bits. When connected to the server, $x \in [0, 2^{48})$ is generated and we are given $y$ with

$$y \equiv g^{g^x}\ (\text{mod}\ p),$$

where $g = 2$. The goal is to recover $x$ within one hour.

Solution⌗

The baby-step-giant-step algorithm⌗

📝 Note. For simplicity, we assume that $\sqrt{N}$ is an integer.

To start with, we want to tackle a simpler problem: the discrete logarithm problem. That is, if we are given $y$ such that $y \equiv g^x \ (\text{mod}\ p)$, our goal is to find $x$. Assuming that $x \in [0, N)$, we can easily find $x$ by using the BSGS algorithm. To do so, we can compute the two sets $L$ and $R$ given by

$$L = \{g^i \ \text{mod}\ p \ |\ i \in [0, \sqrt{N})\}, \quad R = \{y \cdot g^{-j \cdot \sqrt{N}} \ \text{mod}\ p \ |\ j \in [0, \sqrt{N})\}.$$

Coincidentally there will be $l :\equiv g^i \ \in L$ and $r :\equiv y \cdot g^{-j \cdot \sqrt{N}} \in R$ such that $l = r$. Thus,

$$l = r \Longrightarrow g^i \equiv y \cdot g^{-j \cdot \sqrt{N}} \Longrightarrow y \equiv g^{i + j \cdot \sqrt{N}} \ (\text{mod}\ p).$$

Therefore we are able to find the required $x = i + j \cdot \sqrt{N}$ with $\mathcal{O}(\sqrt{N})$ time.

How about discrete-log-log?⌗

The setting is actually pretty similar. We can write $x = i + j \sqrt{N}$, then we have

$$y \equiv g^{g^x} \equiv g^{g^{i + j \sqrt{N}}} \equiv g^{g^i \cdot g^{j \sqrt{N}}}\ (\text{mod}\ p).$$

If we take the $g^i$-th root on both sides, we have

$$y^{g^{-i}} \equiv y^{1/g^i} \equiv g^{g^j \sqrt{N}}\ (\text{mod}\ p)$$

Alike the above section, we can compute the two sets $L$ and $R$ by

$$L = \{y^{g^{-i}}\ \text{mod} \ p \ | \ i \in [0, \sqrt{N})\}, \quad R = \{g^{g^j \cdot \sqrt{N}} \ \text{mod}\ p \ | \ j \in [0, \sqrt{N})\}.$$

We can do the same to find the required $x = i + j \sqrt{N}$.

Some notes on speeding up the process⌗

Naively, we would use the below code to solve the challenge:

# Find x such that y = g^(g^x) mod p.
def dlog(p, g, y):
    q = (p-1) // 2

    lhs = {}
    for i in range(2**24):
        l = pow(y, pow(g, -i, q), p)
        lhs[l] = i

    for j in range(2**24):
        r = pow(g, pow(g, j * 2**24, q), p)
        if lhs.get(r) is None: continue
        i = lhs.get(r)
        return i + j * 2**24

Since the exponentiations under large modulus are very slow, we might be unable to get the solution within time limit. There are some optimizations that can be done:

  1. [Precompute $R$] We can see that $R$ is dependent of $g$, $p$ and $q$ only. Since they are given and fixed for all of the connections, we can compute $R$ before connecting.
  2. [Reduce the number of exponentiations] Let $l_i = y^{g^{-i}}\ \text{mod}\ p$. Since $$l_i \equiv y^{g^{-i}} \equiv y^{g^{-(i+1) + 1}} \equiv y^{g^{-i} \cdot g} \equiv (y^{g^{-i}})^g \equiv {l_{i+1}}^g \equiv {l_{i+1}}^2 \ \text{mod}\ p,$$ we can actually compute $l_{2^{24}}$ and obtain $l_{2^{24} - 1}$, $l_{2^{24} - 2}$, …, $l_0$ by repeatedly squaring the previous number. This significantly decreases the running time.

You will be given the flag after successfully finding the $x$:

firebird{w3l1_th15_i5_4n0th3r_d10g_ch4l1en93}