The **kipferl** challenge was very similar to **gipfel** with the only difference being that the finite field Diffie-Hellman was replaced with elliptic curve Diffie-Hellman over a weird curve over the same prime. As our **gipfel** solution only used the group structure and the values $verA$ and $shared$, we could adapt it to also work on **kipferl**. For the **gipfel** solution go [here](https://ctftime.org/writeup/31900). There were a few twists though:
 - The generator $G$ could now lie on the original curve or on its twist. This made the simple speedup of **gipfel** above slightly more tricky, as we needed to test where the generator guess is to reduce by the correct order. - The scalar multiplication operations as implemented in the challenge are quite slow, and we needed to run quite a lot of them in the time limit of 2021 seconds.
To address these issues, we precomputed the possible generators for all passwords together with information on whether they lied on the original curve or twist curve and used parallelization for the rest. The script below precomputes generator information in Sagemath.
	# Requires tqdm and pycryptodome	import json	from tqdm import tqdm	from Crypto.Hash import SHA256
	q = 0x3a05ce0b044dade60c9a52fb6a3035fc9117b307ca21ae1b6577fef7acd651c1f1c9c06a644fd82955694af6cd4e88f540010f2e8fdf037c769135dbe29bf16a154b62e614bb441f318a82ccd1e493ffa565e5ffd5a708251a50d145f3159a5	K = GF(q)	a, b = K(1), K(0)
	curve = EllipticCurve([a, b])
	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()
	if __name__ == "__main__":		print("Precomputing gs...")		gs = {}		for pw in tqdm(range(10**6)):			g = int(H(pw).hex(), 16)			try:				curve.lift_x(K(g))				mod = "orig"			except:				mod = "twist"			gs[pw] = {				"g": g,				"mod": mod			}
		with open("gs.json", "w") as f:			json.dump(gs, f)
Next the actual attack script in Python. We actually reduce by a square root $r$ of the order of the original curve as its group structure is bi-cyclic ($\mathbb{Z}_r \times \mathbb{Z}_r$). With enough cores the script below gets the flag.
	#!/usr/bin/env python3	from pwn import *	from Crypto.Hash import SHA256	from Crypto.Cipher import AES	from binascii import unhexlify	from multiprocessing import Pool	from tqdm import tqdm	import json
	q = 0x3a05ce0b044dade60c9a52fb6a3035fc9117b307ca21ae1b6577fef7acd651c1f1c9c06a644fd82955694af6cd4e88f540010f2e8fdf037c769135dbe29bf16a154b62e614bb441f318a82ccd1e493ffa565e5ffd5a708251a50d145f3159a5	a, b = 1, 0	order_orig = 21992493417575896428286087521674334179336251497851906051131955410904158485314789427947788692030188502157019527331790513011401920585195969087140918256569620608732530453375717414098148438918130733211117668960801178110820764957628836	order_sqrt = 4689615487177589107664782585032558388794418913529425573939737788208931564987743250881967962324438559511711351322406	order_twist = 2 * q + 2 - order_orig
	################################################################
	# 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))		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):		r = xMUL((h,1), x)		return r[0] * pow(r[1],-1,q) % q
	def test_F(args):		password, g, verA, exp = args		out = F(g, exp)		if verA == out:			return True, password, g		else:			return False, password, g
	def solve_pow(server):		pow_regex = re.compile(r"\"([0-9a-f]+)\"")		bits_regex = re.compile("([0-9]+) zero")
		pow_line = server.recvline()		pow_challenge = pow_regex.search(pow_line.decode()).groups()[0]		pow_bits = bits_regex.search(pow_line.decode()).groups()[0]
		pow_proc = subprocess.run(["./pow-solver", pow_bits, pow_challenge], capture_output=True)		pow_res = pow_proc.stdout.strip()
		server.sendline(pow_res)
	def decrypt(password, shared, data):		key = H(password, shared)		aes = AES.new(key, AES.MODE_CTR, nonce=b'')		return aes.decrypt(unhexlify(data))
	if __name__ == "__main__": log.info("Loading gs...")		with open("gs.json") as f:			gs = json.load(f)
		server = remote("65.108.176.252", 1099) log.info("Solving PoW")		solve_pow(server)		log.success("Solved PoW")
		pubA = int(server.recvline().strip().decode().split(" = ")[1], 16)
		server.sendline(b"2")
		verA = int(server.recvline().strip().decode().split(" = ")[1], 16)
		server.sendline(b"2") # This will fail and we will get shared.
		shared = int(server.recvline().strip().decode().split("! ")[1], 16)		exp_orig = shared**3 % order_sqrt		exp_twist = shared**3 % order_twist
		tasks = [(int(password), val["g"], verA, exp_orig if val["mod"] == "orig" else exp_twist) for password, val in gs.items()]
		pool = Pool()		res = pool.imap_unordered(test_F, tasks)		for r in tqdm(res, total=len(gs)):			if r[0]:				password = r[1]				g = r[2]				pool.terminate()				pool.join()				break		else:			log.error("No luck")			exit(1)		log.success(f"We got the g: {g}")		log.success(f"We got the password: {password}")
 log.info("---- Second run ----")
		pubA = int(server.recvline().strip().decode().split(" = ")[1], 16)
		privB = 10		pubB = F(g, privB)
		server.sendline(str(pubB).encode())
		verA = int(server.recvline().strip().decode().split(" = ")[1], 16)
		shared = F(pubA, privB)		assert verA == F(g, (shared**3))		verB = F(g, (shared**5))
		server.sendline(str(verB).encode())
		encrypted_flag = server.recvline().strip().decode().split(": ")[1]		log.success(f"The flag is {decrypt(password, shared, encrypted_flag)}")
		server.close()