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$.

(Proof.) “$\Leftarrow$” is obvious from the “theorem”. To show “$\Rightarrow$“,
we know from the above that there is a prefix $\hat x$ of $x$ with
$g^\hat x\equiv4\pmod p$. For this particular $g$, this condition is equivalent
to $4^{\hat x/k}\equiv4\pmod p$, which is the case if
and only if $\hat x/k=1$ since $4$ generates the group of squares modulo
$p$ and $\hat x\leq x\leq q-1$. Hence, $k=\hat x$ 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}`