Airport was a cryptography challenge worth 500 points at the Boston Key Party CTF 2015.

We’re provided access to a remote server that implements a custom crypto protocol:

1. Let p = 2q + 1 = 2732…5727 be a safe prime (i.e. q is prime too).
2. Choose a random integer s from the range [1, (p-1)/2).
3. Read an integer b from the client.
4. If bs ≡ 4 (mod p), send the flag to the client. Otherwise, send bs mod p to the client and go to step 3.

Reconstruction s from only a set of (b, s) pairs is hard according to the Discrete logarithm conjecture. However, the server also leaks timing information to the client because it uses the following square-and-multiply implementation for step 4:

From now on, we assume that we can compute arbitrary roots modulo p, i.e. we can compute a function root(n, y, p) with the property that (root(n, y, p))n ≡ y (mod p). We will go into the details of how to implement this function below.

Equipped with this, we can:

• Given s, compute b such that bs ≡ 4 (mod p), using b = root(s, 4, p). This will allow us to solve the task once we figure out s.
• Check whether s starts with a given bit string P. Let’s say P = 101. If s = 101…2 (the subscribed 2 means base 2, i.e. binary), then after 3 iterations of the `slowpower` loop, we have accum ≡ base1012. If base = root(1012, 4, p), then this will cause the sleep function to be called, which we can measure. If the binary representation of s does not start with 101, then it is very likely that no sleep will occur.

Using the second primitive, we can reconstruct s bit by bit using the following algorithm:

And, after apprixmately 2048 seconds of waiting:

``````0b1 1.10669398308 0.115952014923
0b10 0.0756859779358 1.15882515907
0b101 0.160202026367 1.19808292389
0b1011 0.161967039108 1.16554093361
0b10111 1.18343901634 0.153500080109
0b101110 0.153550863266 1.1789689064
0b1011101 1.18081712723 0.135214090347
...
FLAG{diffie_hellman_im_awfully_fond_of_youuuuuu}
``````

All that remains is filling in the implementation of the root function and the captcha solver.

## Computing arbitrary roots modulo p

The problem is, given n and y, find an x such that xn ≡ y (mod p).

Assume that n = 2k + 1 is an odd number. We then have gcd(n, p - 1) = 1 because p - 1 = 2q with q prime. Thus, the modular inverse of n modulo p - 1 exists. Let’s call it u. It can be computed using the extended Euclidean algorithm. By definition, we have u · n ≡ 1 (mod p - 1). With x = yu we then have *xn ≡ yu · n ≡ y1 + k(p - 1) ≡ y · (yp

• 1</sup>)k (mod p)* for some k. Now according to Fermat’s little theorem, this means that xn ≡ y · 1k ≡ y (mod p). Thus x is the n-th root of y that we were looking for.

The case with n = 2k is a bit more complicated: First note that if z is a square root of y, i.e. z2 ≡ y (mod p), then x = root(k, z, p) is the solution we are looking for. Luckily for us, computing square roots modulo the given p is not hard. Since p ≡ 3 (mod 4), we can use a theorem due to Lagrange to compute a square root z: It says that z = y(p+1)/4 mod p is a possible solution.

For the case where n is even, we can alternatively use the fact that we always have y = 4 to make our lives a bit easier: If gcd(n, p - 1) = 2, we can find a v such that v · n ≡ 2 (mod p - 1). Then we have x2 ≡ xv · n ≡ yv ≡ 4v and thus x = 2v is a possible solution.

In Python, the implementation of the more generic approach may look like this: