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:

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

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:

s = socket.create_connection((SERVER, PORT))

# ... solve proof-of-work test

def oracle(b):
    """ Let the server compute b^s mod p. If the result is 4, print
    the flag. Otherwise, return the result and the timing. """
    t0 = time.time()
    s.send(str(b) + '\n')
    ans = s.recv(4096)
    t = time.time() - t0
    if any(c not in "0123456789" for c in ans):
        print ans
        sys.exit(0)
    return int(ans), t

prefix = 1
while True:
    prefix <<= 1
    # check the two possible hypotheses on the extension of s
    _, a = oracle(root(prefix | 0, 4, p))
    _, b = oracle(root(prefix | 1, 4, p))
    print bin(prefix>>1), a, b
    # no difference in timing, we are at the last bit
    if abs(a - b) < 0.5:
        break
    if b > a:
        # the version with an appended 1 bit took longer, so it is the correct guess
        prefix |= 1

# there are two possible options for the last bit, check them using the
# exponentiation oracle
for c in (prefix | 0, prefix | 1):
    if oracle(13)[0] == pow(13, c, p):
        s = c
        break
else:
    # something went wrong
    assert 0

# send the final guess and get the flag
oracle(root(s, 4, p))

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:

def ex_gcd(a, b):
    x1 = 0; y1 = 1
    x = 1; y = 0
    while b:
        q = a / b; r = a % b
        x2 = x - q * x1; y2 = y - q * y1
        a = b; b = r; x = x1; x1 = x2; y = y1; y1 = y2
    return a, x, y

def root2(y, p):
    """ Solve x^2 == y (mod p) """
    assert p % 4 == 3
    x = pow(y, (p+1)/4, p)
    assert pow(x, 2, p) == y
    return x

def root(n, y, p):
    """ Solve x^n == y (mod p) """
    g, u, _ = ex_gcd(n, p-1)
    if g == 2:
        return root(n/2, root2(y, p), p)
    assert g == 1
    u %= p-1
    x = pow(y, u, p)
    assert pow(x, n, p) == y
    return x

Solving the captcha

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

pref = s.recv(4096)
assert len(pref) == 12
print "Solving challenge %s" % pref
i = 0
while True:
    answer = pref + ''.join(chr(random.randint(0,0xff)) for _ in xrange(8))
    assert len(answer) == 20
    ha = hashlib.sha1()
    ha.update(answer)
    if ha.digest().endswith('\xff\xff\xff'):
        break
    i += 1
    if i % 100000 == 0:
        print i
print "Done!"
s.send(answer)

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