Here's a somewhat late writeup for the three-stage crypto composition gipfel/kipferl/zipfel from our recent CTF.

The overall goal in all three challenges was to break a password-authenticated key exchange (PAKE) protocol inspired by SPEKE. The core idea is simple: Do Diffie–Hellman as usual, but with a generator that's derived from a pre-shared key ("the password"), and add a key-confirmation stage.

In all three stages, the key step of the solution was to reduce the problem to offline bruteforcing of the (short, numeric) password.

gipfel

Since it is the simplest, let's have a look at the source code for "gipfel" first:

#!/usr/bin/env python3
from Crypto.Hash import SHA256
from Crypto.Cipher import AES
import signal, random
random = random.SystemRandom()

q = 0x3a05ce0b044dade60c9a52fb6a3035fc9117b307ca21ae1b6577fef7acd651c1f1c9c06a644fd82955694af6cd4e88f540010f2e8fdf037c769135dbe29bf16a154b62e614bb441f318a82ccd1e493ffa565e5ffd5a708251a50d145f3159a5

def enc(a):
    f = {str: str.encode, int: int.__str__}.get(type(a))
    return enc(f(a)) if f else a

def H(*args):
    data = b'\0'.join(map(enc, args))
    return SHA256.new(data).digest()

def F(h, x):
    return pow(h, x, q)

################################################################

password = random.randrange(10**6)

def go():
    g = int(H(password).hex(), 16)

    privA = 40*random.randrange(2**999)
    pubA = F(g, privA)
    print(f'{pubA = :#x}')

    pubB = int(input(),0)
    if not 1 < pubB < q:
        exit('nope')

    shared = F(pubB, privA)

    verA = F(g, shared**3)
    print(f'{verA = :#x}')

    verB = int(input(),0)
    if verB == F(g, shared**5):
        key = H(password, shared)
        flag = open('flag.txt').read().strip()
        aes = AES.new(key, AES.MODE_CTR, nonce=b'')
        print(f'flag:', aes.encrypt(flag.encode()).hex())
    else:
        print(f'nope! {shared:#x}')

# three shots, three opportunities
# to seize everything you ever wanted
# would you capture? or just let it slip?
signal.alarm(2021)
go()
go()
go()

In a nutshell, this code:

• hashes the password to a group element $g$;
• generates a keypair $(a,g^a)$ and sends $g^a$; (The scalar $a$ is chosen to be divisible by $40$, such that it cancels any small-subgroup parts during exponentiations.)
• receives $B$ and computes the shared secret $s:=B^a$;
• sends $g^{s^3}$ and expects to receive $g^{s^5}$ back (with the intention of confirming that both parties know $s$).

On success, the server encrypts the flag using a hash of $(\mathit{password},s)$ as the key and sends it to the client. Otherwise (if the client failed to provide $g^{s^5}$), it sends back the correct $s$ for no other reason than to taunt the client.

I won't spend too much time discussing "gipfel" as it was the most-solved challenge of the entire CTF.

crypto ez lol
— hxp CTF players, probably

Short summary: Pick pubB as any element of order 2 or 4; this makes shared == 1; hence verA == H(password) and we can bruteforce the correct password offline by hashing all possible choices and comparing to the received verA value. In the second iteration of go(), simply run the protocol honestly with the correct password.

Elements of order 2 or 4 are $q-1$ and its (integer) square roots.

kipferl

The next incarnation "kipferl" of this challenge was pretty much the same overall thing, but using the elliptic curve $E:y^2=x^3+x$ over ${\mathbb{F}}_q$ instead of the multiplicative group ${\mathbb{F}}_q^{\times }$.

Here's the entire diff:

--- gipfel/vuln.py
+++ kipferl/vuln.py
@@ -5,6 +5,29 @@
 random = random.SystemRandom()

 q = 0x3a05ce0b044dade60c9a52fb6a3035fc9117b307ca21ae1b6577fef7acd651c1f1c9c06a644fd82955694af6cd4e88f540010f2e8fdf037c769135dbe29bf16a154b62e614bb441f318a82ccd1e493ffa565e5ffd5a708251a50d145f3159a5
+a, b = 1, 0
+
+################################################################
+
+# https://www.hyperelliptic.org/EFD/g1p/data/shortw/xz/ladder/ladd-2002-it
+def xDBLADD(P,Q,PQ):
+    (X1,Z1), (X2,Z2), (X3,Z3) = PQ, P, Q
+    X4 = (X2**2-a*Z2**2)**2-8*b*X2*Z2**3
+    Z4 = 4*(X2*Z2*(X2**2+a*Z2**2)+b*Z2**4)
+    X5 = Z1*((X2*X3-a*Z2*Z3)**2-4*b*Z2*Z3*(X2*Z3+X3*Z2))
+    Z5 = X1*(X2*Z3-X3*Z2)**2
+    X4,Z4,X5,Z5 = (c%q for c in (X4,Z4,X5,Z5))
+    return (X4,Z4), (X5,Z5)
+
+def xMUL(P, k):
+    Q,R = (1,0), P
+    for i in reversed(range(k.bit_length()+1)):
+        if k >> i & 1: R,Q = Q,R
+        Q,R = xDBLADD(Q,R,P)
+        if k >> i & 1: R,Q = Q,R
+    return Q
+
+################################################################

 def enc(a):
     f = {str: str.encode, int: int.__str__}.get(type(a))
@@ -15,7 +38,8 @@
     return SHA256.new(data).digest()

 def F(h, x):
-    return pow(h, x, q)
+    r = xMUL((h,1), x)
+    return r[0] * pow(r[1],-1,q) % q

 ################################################################

The change to an elliptic curve doesn't necessarily change anything in principle, but it so happens that this particular implementation of the elliptic-curve operations (or rather, the dehomogenization step in F) crashes with a ZeroDivisionError exception whenever it encounters the point at infinity. Hence, small-subgroup attacks like for "gipfel" aren't applicable anymore.

Instead, we simply run the key exchange once (in any way) to obtain a pair of verA and shared values from the server. Recalling that verA equals $[s^3]G$, this allows us to recover $G$ by inverting $s^3$ modulo the curve order $\mathrm{\#}E({\mathbb{F}}_q)=q-1$ and computing $[s^{-3}mod(q-1)]\mathtt{verA}=G$. (If $s^3$ is not invertible modulo $q-1$, simply start over.) Then simply bruteforce the password as usual by comparing hashes to $G$, and repeat the key exchange honestly.

zipfel

Finally, the real raison d'être for all three of these challenges: "zipfel". It taketh away verA and giveth back absolutely nothing:

--- kipferl/vuln.py
+++ zipfel/vuln.py
@@ -58,9 +58,6 @@

     shared = F(pubB, privA)

-    verA = F(g, shared**3)
-    print(f'{verA = :#x}')
-
     verB = int(input(),0)
     if verB == F(g, shared**5):
         key = H(password, shared)

As far as I know, this challenge would be unsolvable if the underlying group was "generic". However, the elliptic curve $E$ used here is very special: It's pairing-friendly, with embedding degree one!

Now, unfortunately, it turns out I made a small mistake while picking the parameters. It didn't make the challenge (much) easier, but I think the unintended solution is significantly less pretty. I'll first explain what I originally had in mind and then show the simplified version.

Original solution

The upshot is that the pairing on the elliptic-curve group allows us to solve a variant of the DDH problem, giving rise to an oracle which can be used to bruteforce passwords offline like in the earlier challenges. In short, we may send a random $\mathtt{pubB}=Q$ to the server to obtain a tuple $(\mathtt{pubA},\mathtt{shared})=([a]G,[a]Q)$. Thus, we have the "Diffie–Hellman square" $$\begin{gathered} \boxed{\text{?}}\stackrel{a}{⟶}[a]G \\ \phantom{x} \\ Q\stackrel{a}{⟶}[a]Q \end{gathered}$$ and the goal is to find a point among the possible choices (i.e., password hashes) that fits into the top-left corner of this diagram.
(Note that the "usual" relationship $Q=[b]G$ need not necessarily hold, hence the "missing" vertical arrows.)

Thus, for each candidate password, we may compute the corresponding generator point $P$, and then we're facing the question

Given $(P,\mathtt{pubA},Q,[a]Q)$, is it true that $\mathtt{pubA}=[a]P$?

It is clear that the correct guess $P=G$ will satisfy this property, whereas it is overwhelmingly unlikely for a random $P$. Deciding whether this property holds or not is a mild generalization of the "co-DDH problem" as defined in Galbraith and Rotger's paper Easy Decision-Diffie–Hellman Groups; the difference is that here it's not guaranteed a priori that $\mathtt{pubA}$ is a multiple of $P$. The method to solve co‑DDH from the paper carries over effortlessly to the setting from the CTF challenge nonetheless.

Long story short: The Weil pairing (specialized to our setting) is an efficient* map $$e:E[\ell ]\times E[\ell ]\to {\mathbb{F}}_q^{\times }$$ which is bilinear in the sense that $$e([a]P,[b]Q)=e(P,Q{)}^{ab}$$ holds for all points $P,Q\in E[\ell ]$ and integers $a,b\in \mathbb{Z}$.

(Here, $\ell$ is the prime such that $q=4{\ell }^2+1$. Obviously, the pairing stuff is the reason $q$ was chosen in such a special way. The pairing does exist in vast generality, but usually the target group is ${\mathbb{F}}_{q^k}^{\times }$ for a ridiculously huge extension degree $k$, making the pairing exponentially hard to compute — or, as a matter of fact, to even write down the output.)

The reason this is relevant here is because pairings solve decisional problems: Given $(P,[a]P,Q,[c]Q)$, the Weil pairing can in many cases decide whether $c\equiv a(\mathrm{mod}\ell )$ by checking the equation $$e(P,[c]Q)\stackrel{?}{=}e([a]P,Q)\text{.}$$

Interestingly, the only case where this fails is precisely the DDH situation where $Q$ is a multiple of $P$: The self-pairing $e(P,P)$ is trivial (always equal to $1$), hence we have $e(P,[c][b]P)=1=e([a]P,[b]P)$ for all choices of $a$ and $c$.

Indeed, this exact strategy works for the CTF challenge: Send a random $\mathtt{pubB}$, receive $\mathtt{pubA}$ and $\mathtt{shared}$, and search through candidate generator points $P$ to find one that satisfies $e(P,\mathtt{shared})=e(\mathtt{pubA},\mathtt{pubB})$. Then use the password from which $P$ was obtained to run the protocol honestly and obtain the flag.

Mistakes were made

At the heart of the simpler solution is that the hash function mapping strings to curve points was not restricted to a cyclic subgroup of the curve. This means that the points obtained by hashing candidate passwords are almost certainly linearly independent, and therefore only one of them — the real $G$ — lies in the same cyclic subgroup as the public key $\mathtt{pubA}=[a]G$.

Thus, after receiving $\mathtt{pubA}$, we can simply go through all candidate values $P$ for the generator $G$ and compute $e(P,\mathtt{pubA})$. The (almost certainly unique) point where this value equals $1$ is the correct generator, i.e., the hash of the password.

Lesson learned: Pairings also solve (cyclic) subgroup membership. :^)

Speed

The fact that the server uses $x$-only arithmetic can be exploited to eliminate about half of the possible passwords without computing a single pairing: Half of all $x$-coordinates don't actually define a curve point over ${\mathbb{F}}_q$ (i.e., trying to solve for the corresponding $y$ takes us to the extension ${\mathbb{F}}_{q^2}$), so if we reconnect until $\mathtt{pubA}$ is on the curve (which is needed for the pairings anyway), we know that the correct $G$ must be a point over ${\mathbb{F}}_q$ too and can immediately discard all the passwords whose hash gives a point over ${\mathbb{F}}_{q^2}$.

In reality, the Tate pairing will be noticeably faster (and can be applied in approximately the same way), but in order to keep things straightforward I've restricted the discussion here to the Weil pairing.

My own implementation of the (Tate) pairing solves the challenge within a single connection on a 4-core laptop. Other people have successfully used SageMath on bigger machines. (Also note that it wasn't really necessary to solve the challenge within a single connection, so being slower was fine too.)

Also, since some people complained about the allegedly excessive proof of work on these challenges: This was because the entire point was to break the PAKE in the sense of converting online bruteforce to offline bruteforce; hence, bruteforcing online clearly had to be costly.

In case anyone was wondering...

• Gipfel is the German translation of "peak", an anagram of PAKE.
• Kipferl is a style of bread or pastry with a curved shape, not dissimilar to a croissant.
• Zipfel 🤷‍♂️