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}