[BKP 2015] Wonderland – Crypto 600 Writeup

In CTF Writeups March 2015

I participated in Boston Key Party 2015. Here’s my writeup of Wonderland, a tough 600-point cryptography challenge.

Opening up the provided package, we see that the server implements some kind of elliptic curve scheme. We found that the curve was given in Montgomery curve form, and checked that the arithmetic was all correct (also verified by checking with SAGE).

The server lets us pick an arbitrary base point, which is “exponentiated” to the power of the unknown flag. Thus our goal is to find this flag. With a base point on the curve, this is quite difficult – it is equivalent to the ECC discrete log problem, and there’s no obvious weaknesses with the curve. The order of the points is

k1 = 1461501637330902918203684014253252914573215409208

which factorizes as 2*2*2*182687704666362864775460501781656614321651926151: the presence of the really big prime makes the curve quite secure.

The weakness of the scheme lies in the fact that it accepts arbitrary base points, without checking to see if they lie on the curve. This makes it possible to supply points that actually don’t lie on the curve at all – they lie instead on the “quadratic twist” of the curve, an object with different mathematical properties. In particular, the multiplicative order of points on the quadratic twist is not equal to the multiplicative order of points not on the quadratic twist. For example, the order of the point [8; 1] (a point with x=8) is

k2 = 1461501637330902918203685651179313124738649676760

and, unlike the order of the points on the curve, this order factors as

2*2*2*5*7*31*5857*3280967*68590573243*308648791439*413879086189

which consists of a bunch of small factors.

Now the attack is clear. We can find a non-curve point P_f of order f by computing [8; 1]^k2/f whenever f is a factor of k2. Then, we can ask the server to exponentiate P_f: the result is a point P_f^e for some e congruent to the key. Finding all the es will let us apply the Chinese Remainder Theorem to recover the key.

The actual attack, then, uses a variation of Pollard’s Rho algorithm to compute the discrete logarithms e for each P_f^e. Here’s the gory attack script:

import sys
from socket import *
import time

TARGET = ('54.86.168.156', 40638)
#TARGET = ('localhost', 40638)

def rd(*suffixes):
    out = ''
    while 1:
        try:
            x = s.recv(1)
            if not x:
                break
            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"):
            return start + s
    return None

def test_pt(n):
    global s
    s = socket()
    s.connect(TARGET)
    s.settimeout(0.1)

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

    pr(str(n))
    res = int(rd())
    print
    return res

from server import multiply, square, normalize, power
BASE = 8
SORDER = 1461501637330902918203685651179313124738649676760
factors = [5, 7, 31, 5857, 3280967, 68590573243, 308648791439, 413879086189]

def epow(x, n):
    return normalize(power((x, 1), n))

def mul_inv(a, b):
    b0 = b
    x0, x1 = 0, 1
    if b == 1: return 1
    while a > 1:
        q = a / b
        a, b = b, a%b
        x0, x1 = x1 - q * x0, x0
    if x1 < 0: x1 += b0
    return x1
 
def chinese_remainder(n, a, lena):
    p = i = prod = 1; sm = 0
    for i in range(lena): prod *= n[i]
    for i in range(lena):
        p = prod / n[i]
        sm += a[i] * mul_inv(p, n[i]) * p
    return sm % prod

def dlog(P, b, n):
    ta = {}
    tb = {}
    i = 0
    base = 7
    # a = iP
    # b = (base**j)nP
    # thus: n = i * (base**j)^-1
    res = None
    for i in xrange(n):
        if i % 10000 == 0:
            print '<...%d...>' % i,
            sys.stdout.flush()
        a = epow(P, i)
        ta[a] = i
        tb[b] = i
        if b in ta:
            res = ta[b], i
            break
        if a in tb:
            res = i, tb[a]
            break
        b = epow(b, base)
        i += 1
    if res is None:
        return (0,)
    ai, bi = res
    v = ai * pow(pow(7, bi, n), n-2, n)
    return (v%n, (-v)%n)

results = [[(8, 0)]]

for f in factors:
    P = epow(BASE, SORDER / f)
    # (f+1)P = P
    nP = test_pt(P)
    print f,
    out = dlog(P, nP, f)
    print out
    results.append([(f, x) for x in out])

checkP = 2
check = test_pt(checkP)

import itertools
for k in itertools.product(*results):
    nn, aa = zip(*k)
    n = chinese_remainder(nn, aa, len(nn))
    print n
    if epow(checkP, n) == check:
        print "FLAG:", hex(n)

Share this:

Related