# [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 `k`th bit is 0) or `e[:k-1] * 2 + 1` (if the `k`th 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 `r`th 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

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()
```
Previous Article
Next Article