# Boston Key Party 2015 'Airport' writeup

*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:

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

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*b*, using^{s}≡ 4 (mod p)*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…*(the subscribed 2 means base 2, i.e. binary), then after 3 iterations of the_{2}`slowpower`

loop, we have*accum ≡ base*. If^{1012}*base = root(101*, then this will cause the sleep function to be called, which we can measure. If the binary representation of_{2}, 4, p)*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 *x ^{n}
≡ 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 = y ^{u}* we then have

*x*for some

^{n}≡ y^{u · n}≡ y^{1 + k(p - 1)}≡ y · (y^{p - 1})^{k}(mod p)*k*. Now according to Fermat’s little theorem, this means that

*x*. Thus

^{n}≡ y · 1^{k}≡ y (mod p)*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. *z ^{2} ≡ 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*is a possible solution.

^{(p+1)/4}**mod**pFor 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 *x ^{2} ≡ x^{v · n} ≡ y^{v} ≡ 4^{v}*
and thus

*x = 2*is a possible solution.

^{v}In Python, the implementation of the more generic approach may look like this:

## Solving the captcha

This part is very standard, we just brute-force the suffix until we find a match:

The final exploit code can be found in our Github repository.