[BKP 2015] Airport – Crypto 500 Writeup

I participated in Boston Key Party 2015. Here’s my writeup of Airport, a hard 500-point cryptography challenge.

The hint for the problem says

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.

Opening up the package, we see that they have implemented a simple modular exponentiation algorithm which takes your input b and computes b^e % m for a randomly-generated, secret exponent e and a large safe prime m. The obvious change here is that the square-and-multiply exponentiation algorithm, aptly named slowpower, pauses for one full second any time an intermediate result is equal to 4.

Clearly, the expected solution is to use the one-second delay to extract the exponent. A partial result at step k is given as b^e[:k] % m, where e[:k] denotes the number formed by taking the first k bits of e. Note that if we know e[:k-1], there are only two possibilities for e[:k]: e[:k-1] * 2 (if the kth bit is 0) or e[:k-1] * 2 + 1 (if the kth bit is 1). So, if we know e[:k-1], we can input some b such that b^(e[:k-1]*2+1) % m == 4. If we see a 1 second delay, we know that the kth bit is a 1; otherwise, the kth bit must be 0.

Thus, we can extract the secret one bit at a time. All that’s left to do is compute a suitable b at each stage. Luckily, their use of a safe prime makes this very easy: the modulus m is prime, and equal to 2q+1 where q is also a prime.

The goal here is to find a b such that b^r == 4 for a given exponent r, i.e. to take the rth root mod m = 2*q+1. Let s be such that r*s = 1 mod 2q (we’re assuming such an s exists). Then, by Fermat’s Little Theorem, b == b^(rs) == 4^s mod m. For s to exist, we note that r must be odd because it must invert s mod 2q — hence why we chose to check the e[:k-1]*2+1 case up above. To compute s, we can simply apply Euler’s Theorem: s = r^(q-2) mod 2q.

Finally, we did a few things to make the attack more reliable – very important because the attack takes anywhere from 20 to 40 minutes to run. You can see the full details in the attack.py script:

import sys
from socket import *
import time

TARGET = ('52.1.245.61', 1025)
#TARGET = ('localhost', 1234)

s = socket()
s.connect(TARGET)
s.settimeout(0.1)

def rd(*suffixes):
    out = ''
    while 1:
        try:
            x = s.recv(1)
            if not x:
                raise EOFError()
            sys.stdout.write(x)
            sys.stdout.flush()
            out += x
        except timeout:
            if out:
                return out
            continue

        for suffix in suffixes:
            if out.endswith(suffix):
                break
        else:
            continue
        break
    return out

def pr(x):
    s.send(x)
    print "<%s" % x

def solve_challenge(s):
    from hashlib import sha1
    import itertools

    start = s.split(" ")[-1]
    print "Generating challenge response..."

    chrs = map(chr, xrange(256))

    for i, s in enumerate(itertools.product(chrs, repeat=8)):
        if i % 131072 == 0:
            print "tested: ", i
        s = ''.join(s)
        ha = sha1()
        ha.update(start + s)
        digest = ha.digest()
        if digest.endswith("\xff\xff\xff"):
            return start + s
    return None

answer = solve_challenge(s.recv(12))
s.send(answer)

SAFEPRIME = 27327395392065156535295708986786204851079528837723780510136102615658941290873291366333982291142196119880072569148310240613294525601423086385684539987530041685746722802143397156977196536022078345249162977312837555444840885304704497622243160036344118163834102383664729922544598824748665205987742128842266020644318535398158529231670365533130718559364239513376190580331938323739895791648429804489417000105677817248741446184689828512402512984453866089594767267742663452532505964888865617589849683809416805726974349474427978691740833753326962760114744967093652541808999389773346317294473742439510326811300031080582618145727L

def nth_root(x, r, p):
    q = (p-1)/2 # assume it is a safeprime
    return pow(x, pow(r, q-2, p-1), p)

def brute_key():
    cur = 0
    while 1:
        cand = cur*2+1
        t = time.time()
        pr(str(nth_root(4, cand, SAFEPRIME)))
        result = rd()
        elapsed = time.time() - t

        print
        print "time:", elapsed,
        if 1.2 <= elapsed <= 1.4:
            cur = cur*2 + 1
            print "(+1)"
        elif 0.2 <= elapsed <= 0.4: cur = cur*2 print "(+0)" else: print "(out of range)" print "current:", bin(cur) # Sanity check if bin(cur).endswith('0' * 100): print "didn't see ones for a while: rolling back" cur >>= 105

brute_key()