This challenge was concerned with exploiting a timing oracle vulnerability, as was already disclosed in the task description:

The timing in this challenge is clearly not very realistic—but the methods you’ll use here can be extended to real-world implementations of modular exponentiation. Server at 52.1.245.61, port 1025. My solution takes a little while. Good luck.

Along with this, the server’s Python source code was provided.

From the code, one recognizes that the server repeatedly performs modular exponentiation of some attacker-chosen base $g$ to the power of a randomly generated secret $x\in\{1,\dots,\frac{p-1}2-1\}$ modulo a public, pre-chosen safe prime $p$; that is, $p=2q+1$ for another prime $q$.

As hinted in the challenge description, the square-and-multiply function provides a (pretty unrealistic) timing oracle: Whenever the accumulator contains the value $4$, the server sleeps for a second. Incidentally, the challenge’s main goal is to provide a number $g$ such that $g^x\equiv4\pmod p$, upon which the server prints the flag.

Additionally, a function called group_check enforces (by ensuring $g^{\frac{p-1}2}\equiv1\pmod p$) that the provided base $g$ is a square modulo $p$ (also known as “quadratic residue”, although the author deems this terminology rather unfortunate), that is, there is some $h\in\mathbb Z$ such that $h^2\equiv g\pmod p$. This means that all computation is performed in the subgroup of squares of $(\mathbb Z/p\mathbb Z)^\ast$, a group with some pretty nice properties — we’ll see a little more about this later.

The following extract should cover the most important parts:

def slowpower(base, power, mod):
    accum = 1
    for bit in bin(power)[2:]:
        if accum == 4:
            time.sleep(1.0)
        accum = accum*accum % mod
        if bit == '1':
            accum = accum*base % mod
    return accum

SAFEPRIME = 27327395392065156535295708986786204851079528837723780510136102615658941290873291366333982291142196119880072569148310240613294525601423086385684539987530041685746722802143397156977196536022078345249162977312837555444840885304704497622243160036344118163834102383664729922544598824748665205987742128842266020644318535398158529231670365533130718559364239513376190580331938323739895791648429804489417000105677817248741446184689828512402512984453866089594767267742663452532505964888865617589849683809416805726974349474427978691740833753326962760114744967093652541808999389773346317294473742439510326811300031080582618145727L

def group_check(p, m):
    if m <= 0:
        return False
    elif m >= p:
        return False
    elif pow(m, (p-1)/2, p) != 1:
        return False
    else:
        return True

# (class ThreadedServer etc.)
    def exponentiate(self):
        base = int(self.request.recv(1024))
        if not group_check(SAFEPRIME, base):
            self.fail("Bad group element.")
        result = slowpower(base, self.SECRET, SAFEPRIME)
        if result != 4:
            self.request.sendall(str(result))
        else:
            self.request.sendall(FLAG)

    def setup(self):
        self.SECRET = rand_exponent(SAFEPRIME)

    def handle(self):
        self.captcha()
        while True:
            self.exponentiate()
        self.request.close()

Let’s see what we can do with this!

We now investigate which values the square-and-multiply implementation’s accumulator assumes before the final result is reached. Let $n$ denote the number of remaining iterations (including the current one). Then, at the beginning of the loop’s body (where the check for the value $4$ is performed), the invariant

accum == pow(base, power >> n, mod)

holds. This is easy to see (technically reducing it to the correctness of slowpower) since if one were to break the loop right now, the resulting accumulator would correspond to the exponent with its $n$ least significant bits cut off. Therefore, we have the following little “theorem”:

The sleep is reached if and only if $g^\hat x\equiv4\pmod p$ for some prefix $\hat x$ of $x$ (with respect to the binary representation).

(More mathematically speaking, “$\hat x$ is a prefix of $x$” means: there is some non-negative integer $k$ such that $\hat x=\lfloor x2^{-k}\rfloor$.)

We now need some more information about the group of squares modulo $p$: This group is cyclic with any non-neutral element being a generator (since its order is $\frac{p-1}2=q$ which is a prime); and each element $y$ has exactly one $i$th root for all $i\in\{1,\dots,q-1\}$. In particular, we can find this root by first obtaining $j\in\{1,\dots,q-1\}$ with $ij\equiv1\pmod q$ using Euclid’s algorithm and then computing $y^j$. By Lagrange’s theorem, this is an $i$th root of $y$, since $(y^j)^i=y^{ij}=y^{ij\bmod q}=y^1=1$.

Using this, we obtain the following “corollary” to the “theorem” above (where $\sqrt[k]{}$ denotes the $k$th root in the group of squares modulo $p$):

If $g=\sqrt[k]4$, then the sleep is reached if and only if $k$ is a prefix of $x$.

Now here’s the catch: If we have already found a prefix $k$ of $x$, then we can easily extend this to a prefix $k’$ by trying both $k’_0:=2k$ and $k’_1:=2k+1$ and checking which of them is a prefix of $x$ using the statement above; that is, by forming the $k’_b$th roots of $4$ for both $b\in\{0,1\}$ and checking whether slowpower sleeps for them or not.

Since of course the most significant bit of $x$ must be $1$, we can start this inductive procedure using the prefix $k=1$ and then iterate until we have found all the bits (at which point the server will already send the flag — convenient!).

Leaving out the gory details, the solver thusly looks like this:

def root(x, n):
    k = mod_inv(n, Q)
    return pow(x, k, P)

def query(k):
    sock.send(str(k).encode('utf8'))
    t0 = time.time()
    r = sock.recv(0x400).strip()
    t1 = time.time()
    if not all(x in b'0123456789' for x in r):
        print('\n\n\n\n!!!! ' + r.decode('utf8') + '\n\n\n')
        exit(0)
    return t1 - t0

guess = 1
for b in reversed(range(Q.bit_length())):
    guess *= 2
    t0 = query(root(4, guess))
    t1 = query(root(4, guess | 1))
    print('{:#x}: {:.4f}'.format(guess, t0))
    print('{:#x}: {:.4f}'.format(guess | 1, t1))
    if t1 > t0:
        guess |= 1
    print('--> ' + hex(guess))

After almost an hour (since leaking each bit takes slightly longer than one second and $p$ is a 2048-bit prime), the script finally printed the flag:

FLAG{diffie_hellman_im_awfully_fond_of_youuuuuu}