# [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 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()