UnionCTF Crypto Writeups

I participated in UnionCTF as a member of Super Guesser. We reached 1st place :)

 

Mordell Primes

from Crypto.Util.number import bytes_to_long
from secrets import k, FLAG
 
assert k < 2^128
assert FLAG.startswith(b'union{')
 
E = EllipticCurve(QQ,[0,1,0,78,-16])
P = E(1,8)
Q = k*P
R = (k+1)*P
 
p = Q[0].numerator()
q = R[0].numerator()
 
assert is_prime(p)
assert is_prime(q)
 
e = 0x10001
N = p*q
m = bytes_to_long(FLAG)
c = pow(m,e,N)
 
print(f'N = {N}')
print(f'c = {c}')
 

Solution

The main intuition is that the numerator of $kP$ will grow very fast as $k$ increases. This can be verified by simply checking for small $k$.

Therefore, we can try to simply brute force the value of $k$ and see if the numerators multiply to $N$.

 

E = EllipticCurve(QQ,[0,1,0,78,-16])
P = E(1,8)
 
for i in range(2, 40):
    Q = i * P
    cc = Q[0].numerator()
    if N % cc == 0:
        print(cc) # p, q
 
p = cc
q = N / cc
e = 65537
phi = (p-1) * (q-1)
d = inverse(e, phi)
print(long_to_bytes(pow(c, d, N)))

 

Human Server

import os, random, hashlib, textwrap, json
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from Crypto.Util.number import getPrime, long_to_bytes
 
 
from fastecdsa.curve import secp256k1
from fastecdsa.point import Point
 
FLAG = b'union{XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX}'
 
CURVE = secp256k1
ORDER = CURVE.q
G = CURVE.G
 
class EllipticCurveKeyExchange():
    def __init__(self):
        self.private = random.randint(0,ORDER)
        self.public = self.get_public_key()
        self.recieved = None
        self.nonce = None
        self.key = None
 
    def get_public_key(self):
        A = G * self.private
        return A
 
    def send_public(self):
        return print(json.dumps({"Px" : self.public.x, "Py" : self.public.y}))
 
    def receive_public(self, data):
        """
        Remember to include the nonce for ultra-secure key exchange!
        """
        Px = int(data["Px"])
        Py = int(data["Py"])
        self.recieved = Point(Px, Py, curve=secp256k1)
        self.nonce = int(data['nonce'])
 
    def get_shared_secret(self):
        """
        Generates the ultra secure secret with added nonce randomness
        """
        assert self.nonce.bit_length() > 64
        self.key = (self.recieved * self.private).x ^ self.nonce
 
    def check_fingerprint(self, h2: str):
        """
        If this is failing, remember that you must send the SAME
        nonce to both Alice and Bob for the shared secret to match
        """
        h1 = hashlib.sha256(long_to_bytes(self.key)).hexdigest()
        return h1 == h2
 
    def send_fingerprint(self):
        return hashlib.sha256(long_to_bytes(self.key)).hexdigest()
 
def print_header(title: str):
    print('\n\n'+'*'*64+'\n'+'*'+title.center(62)+'*\n'+'*'*64+'\n\n')
 
def input_json(prompt: str):
    data = input(prompt)
    try:
        return json.loads(data)
    except:
        print({"error": "Input must be sent as a JSON object"})
        exit()
 
def encrypt_flag(shared_secret: int):
    iv = os.urandom(16)
    key = hashlib.sha1(long_to_bytes(shared_secret)).digest()[:16]
    cipher = AES.new(key, AES.MODE_CBC, iv)
    ciphertext = cipher.encrypt(pad(FLAG, 16))
 
    data = {}
    data['iv'] = iv.hex()
    data['encrypted_flag'] = ciphertext.hex()
    return print(json.dumps(data))
 
 
Alice = EllipticCurveKeyExchange()
Bob = EllipticCurveKeyExchange()
 
print_header('Welcome!') 
message = "Hello! Thanks so much for jumping in to help. Ever since everyone left WhatsApp, we've had a hard time keeping up with communications. We're hoping by outsourcing the message exchange to some CTF players we'll keep the load down on our servers... All messages are end-to-end encrypted so there's no privacy issues at all, we've even rolling out our new ultra-secure key exchange with enhanced randomness! Again, we really appreciate the help, feel free to add this experience to your CV!"
welcome = textwrap.fill(message, width=64)          
print(welcome)
 
print_header('Alice sends public key')
Alice.send_public()
 
print_header("Please forward Alice's key to Bob")
alice_to_bob = input_json('Send to Bob: ')
Bob.receive_public(alice_to_bob)
 
print_header('Bob sends public key')
Bob.send_public()
 
print_header("Please forward Bob's key to Alice")
bob_to_alice = input_json('Send to Alice: ')
Alice.receive_public(bob_to_alice)
            
Alice.get_shared_secret()
Bob.get_shared_secret()
 
print_header('Key verification in progress')
alice_happy = Alice.check_fingerprint(Bob.send_fingerprint())
bob_happy = Bob.check_fingerprint(Alice.send_fingerprint())
if not alice_happy or not bob_happy:
    print({"error": "Alice and Bob panicked: Potential MITM attack in progress!!"})
    exit()
 
print_header('Alice sends encrypted flag to Bob')
encrypt_flag(Alice.key)
 
 

Solution

We have to do a MITM attack, but there are some twists - Alice and Bob do a check later to see if they have the same shared secret.

Suppose Alice's secret key, public key is $d_1$, $d_1G$ and Bob's secret key, public key is $d_2$, $d_2G$.

 

Now let's forward Alice's key as $e_1G$ and give the nonce $r_1$ to Bob, where we know the value $e_1$.

This will make Bob's shared secret equal to $(e_1d_2G).x \oplus r_1$. Since $d_2G$ is a known value and $e_1, r_1$ are known, we can calculate this.

 

Similarly, let's forward Bob's key as $e_2G$ and give the nonce $r_2$ to Alice, where we know the value $e_2$.

This will make Alice's shared secret equal to $(e_2d_1G).x \oplus r_2$. We have to make this equal to Bob's shared secret. 

 

This can be done by selecting $r_2$ as $$r_2 = (e_1d_2G).x \oplus (e_2d_1G).x \oplus r_1$$ and we can pass the check between Alice and Bob. We now know the shared secret, so the challenge is solved.

 

Of course, we can just choose $e_1 = e_2 = 1$ and some random value for $r_1$.

 

# curve parameter
X = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Y = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
# random nonce
nonce = 0x7918768917649876918679818976981769817691968917698769
 
r = remote('134.122.111.232', 54321)
r.recvuntil("Alice sends public key")
r.recvline()
r.recvline()
r.recvline()
 
AliceKey = json.loads(r.recvline())
AX = AliceKey["Px"]
AY = AliceKey["Py"]
 
r.recvuntil("Please forward Alice's key to Bob")
r.recvline()
r.recvline()
r.recvline()
 
data = {
    "Px" : X,
    "Py" : Y,
    "nonce" : nonce
}
 
r.send(json.dumps(data))
 
r.recvuntil("Bob sends public key")
r.recvline()
r.recvline()
r.recvline()
 
BobKey = json.loads(r.recvline())
BX = BobKey["Px"]
BY = BobKey["Py"]
 
r.recvuntil("Please forward Bob's key to Alice")
r.recvline()
r.recvline()
r.recvline()
 
 
nonce2 = nonce ^ AX ^ BX
 
data = {
    "Px" : X,
    "Py" : Y,
    "nonce" : nonce2
}
 
r.send(json.dumps(data))
 
shared_secret = BX ^ nonce
 
r.recvuntil("Alice sends encrypted flag to Bob")
r.recvline()
r.recvline()
r.recvline()
 
fin = json.loads(r.recvline())
 
iv = bytes.fromhex(fin["iv"])
enc = bytes.fromhex(fin["encrypted_flag"])
 
key = hashlib.sha1(long_to_bytes(shared_secret)).digest()[:16]
cipher = AES.new(key, AES.MODE_CBC, iv)
flag = cipher.decrypt(enc)
 
print(flag)

 

Cr0wn St3rling

#!/usr/bin/env python3
 
from secrets import flag, musical_key
from Crypto.Util.number import isPrime
import math
 
 
def sieve_for_primes_to(n):
    # Copyright Eratosthenes, 204 BC
    size = n//2
    sieve = [1]*size
    limit = int(n**0.5)
    for i in range(1, limit):
        if sieve[i]:
            val = 2*i+1
            tmp = ((size-1) - i)//val
            sieve[i+val::val] = [0]*tmp
    return [2] + [i*2+1 for i, v in enumerate(sieve) if v and i > 0]
 
 
def is_quasi_prime(n, primes):
    # novel class of semi-prime numbers
    # https://arxiv.org/pdf/1903.08570.pdf
    p2 = 0
    for p1 in primes:
        if n % p1 == 0:
            p2 = n//p1
            break
    if isPrime(p2) and not p1 in [2, 3] and not p2 in [2, 3]:
        return True
    return False
 
 
def bbp_pi(n):
    # Bailey-Borwein-Plouffe Formula
    # sounds almost as cool as Blum-Blum-Shub
    # nth hex digit of pi
    def S(j, n):
        s = 0.0
        k = 0
        while k <= n:
            r = 8*k+j
            s = (s + pow(16, n-k, r) / r) % 1.0
            k += 1
        t = 0.0
        k = n + 1
        while 1:
            newt = t + pow(16, n-k) / (8*k+j)
            if t == newt:
                break
            else:
                t = newt
            k += 1
        return s + t
 
    n -= 1
    x = (4*S(1, n) - 2*S(4, n) - S(5, n) - S(6, n)) % 1.0
    return "%02x" % int(x * 16**2)
 
 
def digital_root(n):
    # reveals Icositetragon modalities when applied to Fibonacci sequence
    return (n - 1) % 9 + 1 if n else 0
 
 
def fibonacci(n):
    # Nature's divine proportion gives high-speed oscillations of infinite
    # wave values of irrational numbers
    assert(n >= 0)
    if n < digital_root(2):
        return n
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)
 
 
def is_valid_music(music):
    # Leverage music's infinite variability
    assert(all(c in "ABCDEFG" for c in music))
 
 
def is_valid_number(D):
    # Checks if input symbolizes the digital root of oxygen
    assert(8==D)
 
 
def get_key(motif):
    is_valid_music(motif)
    is_valid_number(len(motif))
    # transpose music onto transcendental frequencies
    indexes = [(ord(c)-0x40)**i for i, c in enumerate(motif)]
    size = sum(indexes)
    assert(size < 75000) # we will go larger when we have quantum
    return indexes, size
 
 
def get_q_grid(size):
    return [i for i in range(size) if is_quasi_prime(i, sieve_for_primes_to(math.floor(math.sqrt(size))+1))]
 
 
if __name__ == "__main__":
    print("[+] Oscillating the key")
    key_indexes, size = get_key(musical_key)
    print("[+] Generating quasi-prime grid")
    q_grid = get_q_grid(size)
    # print(f"indexes: {key_indexes}  size: {size}  len(q_grid): {len(q_grid)}")
 
    out = []
    for i, p in enumerate(flag):
        print(f"[+] Entangling key and plaintext at position {i}")
        index = key_indexes[i % len(key_indexes)] * fibonacci(i)
        q = q_grid[index % len(q_grid)]
        key_byte_hex = bbp_pi(q)
        # print(f"index: {index:10}  fib: {fibonacci(i):10}  q-prime: {q:10}  keybyte: {key_byte_hex:10}")
        out.append(ord(p) ^ int(key_byte_hex, 16))
 
    print(f"[+] Encrypted: {bytes(out).hex()}")
 

Solution

We start by making some quick observations -

• The length of key_indexes must be 8 due to the check is_valid_number.
• There are only $7^8$ keys since there are 7 possible choices for each entry of the musical key.
• Actually, the first entry of key_indexes is guaranteed to be 1. Make that $7^7$ valid key_indexes.
• Fibonacci function is implemented pretty badly, and we can change that to simple dynamic programming
• There's nothing we need to do about the $\pi$ function
• The q_grid function is suboptimal, but it runs in decent time so no need to worry about that.

We will now decrease the number of key_index candidates by using the known plaintext "union".

• Each entry of key_indexes works in a separable way, so we can work with each entry separately
• There are 7 possible choices for a specific key_indexes entry
• The problem is we do not know the length of q_grid (we do not know the variable $size$ in advance)
• For $i < 5$, the maximum value of the index is $7^4 \cdot 3$, which is small compared to the length of the q_grid for $size = 75000$.
• Therefore, we can reasonably assume that the length of q_grid is larger than the index.
• Now we can try out each candidate for a specific key_indexes entry - this is sufficient to get the first 5 entries of key_indexes.

We now have only $7^3$ candidates to work with. We can try every single one of them.

• The only slow part of the brute force is generating the q_grid and calculating its length.
• This can be done very fast by calculating q_grid for $size = 75000$ and using binary search to calculate the "actual length of the q_grid" (i.e. number of entries that are less than the actual "size" variable)
• However, since we have a lot of time, we can just calculate q_grid for $size = 75000$ then simply calculate the actual length of the q_grid with brute force. It doesn't take too long for us to get the flag anyway..

q_grid = get_q_grid(75005) 
enc = bytes.fromhex('76f64667220717784affa07cf6b8be52c7d8348d778a41615efa9e53f2566b27fd96eb984c08')
fib = [0, 1]
for i in range(2, 50):
    fib.append(fib[i-1] + fib[i-2])
 
# the first note of the musical key does not matter since the key_index will become 1 anyway
 
# known plaintext
ptxt = "union"
for i in range(0, 5):
    if i == 0: # first note doesn't matter
        continue
    for j in range(1, 8): # try all 7 possible notes
        idx = (j ** i) * fib[i]
        q = q_grid[idx] # we assume idx < actual length of q_grid
        key_byte_hex = bbp_pi(q)
        out = enc[i] ^ int(key_byte_hex, 16)
        if out == ord(ptxt[i]): # match
            print(chr(64 + j)) # output the note
 
# results in C D A D -> set the first five notes as A C D A D
 
 
# brute force 7^3
for i in range(0, 7):
    for j in range(0, 7):
        for k in range(0, 7):
            T = ['A', 'C', 'D', 'A', 'D', chr(65+i), chr(65+j), chr(65+k)]
            key_indexes , size = get_key(T)
            # remove the assertion for size in get_key
            if size >= 75000:
                continue
            # compute the "actual" q_grid
            q_qgrid = []
            for val in q_grid:
                if val < size:
                    q_qgrid.append(val)
            # compute the plaintext
            out = []
            for ii in range(0, len(enc)):
                idx = key_indexes[ii % 8] * fib[ii]
                q = q_qgrid[idx % len(q_qgrid)]
                key_byte_hex = bbp_pi(q)
                out.append(enc[ii] ^ int(key_byte_hex, 16))
            print(bytes(out)) # wait for it..

 

Neo-Classical Key Exchange

import os
from hashlib import sha1
from random import randint
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
 
FLAG = b"union{XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX}"
 
def list_valid(l):
    x = l // 2
    checked = set([x])
    while x * x != l:
        x = (x + (l // x)) // 2
        if x in checked: return False
        checked.add(x)
    return True
 
def list_iter(n):
    x = n
    y = (x + 1) // 2
    while y < x:
        x = y
        y = (x + n // x) // 2
    return x
 
def list_mul(l1,l2,p):
    X, Y = len(l1), len(l2)
    Z = list_iter(X)
    assert X == Y
    assert list_valid(X)
    l3 = []
    for i in range(Z):
        for j in range(Z):
            prod_list = [x*y for x,y in zip(l1[Z*i:Z*(i+1)], l2[j::Z])]
            sum_list = sum(prod_list) % p
            l3.append(sum_list)
    return l3
 
def list_exp(l0, e, p):
    exp = bin(e)[3::]
    l = l0
    for i in exp:
        l = list_mul(l,l,p)
        if i == '1':
            l = list_mul(l,l0,p)
    return l
 
def gen_public_key(G,p):
    k = randint(2,p-1)
    B = list_exp(G,k,p)
    return B,k
 
def gen_shared_secret(M,k,p):
    S = list_exp(M,k,p)
    return S[0]
 
def encrypt_flag(shared_secret: int):
    # Derive AES key from shared secret
    key = sha1(str(shared_secret).encode('ascii')).digest()[:16]
    # Encrypt flag
    iv = os.urandom(16)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    ciphertext = cipher.encrypt(pad(FLAG, 16))
    # Prepare data to send
    data = {}
    data['iv'] = iv.hex()
    data['encrypted_flag'] = ciphertext.hex()
    return data
 
p = 64050696188665199345192377656931194086566536936726816377438460361325379667067
G = [37474442957545178764106324981526765864975539603703225974060597893616967420393,59548952493843765553320545295586414418025029050337357927081996502641013504519, 31100206652551216470993800087401304955064478829626836705672452903908942403749, 13860314824542875724070123811379531915581644656235299920466618156218632047734, 20708638990322428536520731257757756431087939910637434308755686013682215836263, 24952549146521449536973107355293130621158296115716203042289903292398131137622, 10218366819256412940642638446599581386178890340698004603581416301746386415327, 2703573504536926632262901165642757957865606616503182053867895322013282739647, 15879294441389987904495146729489455626323759671332021432053969162532650514737, 30587605323370564700860148975988622662724284710157566957213620913591119857266, 36611042243620159284891739300872570923754844379301712429812256285632664939438, 58718914241625123259194313738101735115927103160409788235233580788592491022607, 18794394402264910240234942692440221176187631522440611503354694959423849000390, 37895552711677819212080891019935360298287165077162751096430149138287175198792, 42606523043195439411148917099933299291240308126833074779715029926129592539269, 58823705349101783144068766123926443603026261539055007453105405205925131925190, 5161282521824450434107880210047438744043346780853067016037814677431009278694, 3196376473514329905892186470188661558538142801087733055324234265182313048345, 37727162280974181457962922331112777744780166735208107725039910555667476286294, 43375207256050745127045919163601367018956550763591458462169205918826786898398, 21316240287865348172884609677159994196623096993962103476517743037154705924312, 7032356850437797415676110660436413346535063433156355547532408592015995190002, 3916163687745653495848908537554668396996224820204992858702838114767399600995, 13665661150287720594400034444826365313288645670526357669076978338398633256587,23887025917289715287437926862183042001010845671403682948840305587666551788353]
A,a = gen_public_key(G,p)
B,b = gen_public_key(G,p)
assert gen_shared_secret(A,b,p) == gen_shared_secret(B,a,p)
 
shared_secret = gen_shared_secret(B,a,p)
encrypted_flag = encrypt_flag(shared_secret)
 
print(f"Alice's public key: {A}") 
print(f"Bob's public key: {B}")
print(f"Encrypted flag: {encrypted_flag}")
 
 
 
 

Solution

The first thing we notice is that list_valid checks if the length of the list is a square, and list_iter simply returns the square root.

Now we look at the main function, the list multiplication. If we stare at it for a while (and notice the "length is a square" stuff) we can find out that this list multiplication is just a matrix multiplication, where the list is the matrix entries in order.

 

Now we have to solve a Diffie-Hellman problem with matrices over $\mathbb{F}_p$. We will do it by solving discrete logarithm problem.

• Idea 1 : The range of the secret keys
• The range of the secret keys are from $2$ to $p$ - this implies that we do not need the entire discrete logarithm, just some part of it.
• Idea 2 : The determinant
• This idea can give us the required information of the (matrix) discrete logarithm if we calculate the respective discrete logarithm (over finite field $\mathbb{F}_p$) on the determinants. However, the primes used here are quite large, which makes this approach infeasible.

Instead of $5 \times 5$ matrices that we actually have to deal with, we first look at $2 \times 2$ matrices over the reals.

The idea is that we want to look at how matrix powers behave in a more relaxed setting, and find some properties we can use in $\mathbb{F}_p$.

 

We try to solve $A^k = B$. Take the Jordan Canonical Form $J$ with $A = PJP^{-1}$. Then we want to solve $$J^k = P^{-1}BP$$ so we may simply assume that $A$ is in a Jordan Canonical Form. If $A$ is in the form of $$A = \left[ \begin{matrix} \lambda_1 & 0 \\ 0 & \lambda_2 \end{matrix} \right]$$ then nothing special happens - we still need a logarithm to compute $k$, which is infeasible in $\mathbb{F}_p$. However, if $A$ is in the form of $$A = \left[ \begin{matrix} \lambda & 1 \\ 0 & \lambda \end{matrix} \right]$$ then we have some interesting phenomenon : $$A^k = \left[ \begin{matrix} \lambda^k & k \lambda^{k-1} \\ 0 & \lambda^k \end{matrix} \right]$$ and now we can get $k$ as $(k\lambda^{k-1} \times \lambda) / \lambda^k$, all of which we know and can be done in $\mathbb{F}_p$.

 

Let's come back to $\mathbb{F}_p$. If we want to use the Jordan Canoncial Form trick, we need our characteristic polynomial to completely split in $\mathbb{F}_p$, and we also need a block of size $2$. Our matrix satisfies all of these properties, so we can just use the exact same technique here as well.

 

Of course, we can see that we have calculated the discrete logarithm modulo $p$, not the full discrete logarithm.

However, because of Idea 1 (secret key range is small) this is enough to solve the problem. Here are some additional notes.

• The Jordan Canonical Form of our matrix $G$ has 4 blocks of size 1, 1, 1, 2. 
• This actually shows that the order of $G$ is $p(p-1)$ - this can be seen as the $p-1$ term dealing with the diagonal entries (Fermat's Theorem) and the $p$ term dealing with the off-diagonal term in our block of size 2. 
• If we want to solve for the discrete logarithm modulo $p-1$, we need discrete logarithm over $\mathbb{F}_p$ which we decided infeasible.
• I think there are some similarities with this challenge and TetCTF 2021 unevaluated.

p = 64050696188665199345192377656931194086566536936726816377438460361325379667067
 
def MAT(X):
    M = Matrix(GF(p), 5, 5)
    cnt = 0 
    for i in range(0, 5):
        for j in range(0, 5):
            M[i, j] = X[cnt]
            cnt += 1
    return M
 
G = 
A = 
B = 
 
GMAT = MAT(G)
AMAT = MAT(A)
BMAT = MAT(B)
 
print(GMAT.charpoly().factor())
print(AMAT.charpoly().factor())
print(BMAT.charpoly().factor())
 
 
J, P = GMAT.jordan_form(transformation = True)
AMAT = P^-1 * AMAT * P
BMAT = P^-1 * BMAT * P
print(J)
print("")
print(AMAT)
print("")
print(BMAT)
 
print(AMAT[3, 4] / AMAT[3, 3] * J[3, 3]) # dlog
print(BMAT[3, 4] / BMAT[3, 3] * J[3, 3]) # dlog
# the rest is relatively trivial (get shared secret, decrypt flag)

 

Why is a raven

import hashlib
from base64 import b64encode
from Crypto.Cipher import AES
 
p = 2^216*3^137 - 1
F.<i> = GF(p^2, modulus=x^2+1)
E = EllipticCurve(F, [0, 6, 0, 1, 0])
 
xQ20=0x000C7461738340EFCF09CE388F666EB38F7F3AFD42DC0B664D9F461F31AA2EDC6B4AB71BD42F4D7C058E13F64B237EF7DDD2ABC0DEB0C6C
xQ21=0x00025DE37157F50D75D320DD0682AB4A67E471586FBC2D31AA32E6957FA2B2614C4CD40A1E27283EAAF4272AE517847197432E2D61C85F5
yQ20=0x001D407B70B01E4AEE172EDF491F4EF32144F03F5E054CEF9FDE5A35EFA3642A11817905ED0D4F193F31124264924A5F64EFE14B6EC97E5
yQ21=0x000E7DEC8C32F50A4E735A839DCDB89FE0763A184C525F7B7D0EBC0E84E9D83E9AC53A572A25D19E1464B509D97272AE761657B4765B3D6
xP20=0x0003CCFC5E1F050030363E6920A0F7A4C6C71E63DE63A0E6475AF621995705F7C84500CB2BB61E950E19EAB8661D25C4A50ED279646CB48
xP21=0x001AD1C1CAE7840EDDA6D8A924520F60E573D3B9DFAC6D189941CB22326D284A8816CC4249410FE80D68047D823C97D705246F869E3EA50
yP20=0x001AB066B84949582E3F66688452B9255E72A017C45B148D719D9A63CDB7BE6F48C812E33B68161D5AB3A0A36906F04A6A6957E6F4FB2E0
yP21=0x000FD87F67EA576CE97FF65BF9F4F7688C4C752DCE9F8BD2B36AD66E04249AAF8337C01E6E4E1A844267BA1A1887B433729E1DD90C7DD2F
xQ30=0x0012E84D7652558E694BF84C1FBDAAF99B83B4266C32EC65B10457BCAF94C63EB063681E8B1E7398C0B241C19B9665FDB9E1406DA3D3846
xQ31=0x0000000
yQ30=0x0000000
yQ31=0x000EBAAA6C731271673BEECE467FD5ED9CC29AB564BDED7BDEAA86DD1E0FDDF399EDCC9B49C829EF53C7D7A35C3A0745D73C424FB4A5FD2
xP30=0x0008664865EA7D816F03B31E223C26D406A2C6CD0C3D667466056AAE85895EC37368BFC009DFAFCB3D97E639F65E9E45F46573B0637B7A9
xP31=0x0000000
yP30=0x0006AE515593E73976091978DFBD70BDA0DD6BCAEEBFDD4FB1E748DDD9ED3FDCF679726C67A3B2CC12B39805B32B612E058A4280764443B
yP31=0x0000000
 
Q_A = E(xQ20 + xQ21*i, yQ20 + yQ21*i)
P_A = E(xP20 + xP21*i, yP20 + yP21*i)
Q_B = E(xQ30 + xQ31*i, yQ30 + yQ31*i)
P_B = E(xP30 + xP31*i, yP30 + yP31*i)
 
# Computes an l^e-isogeny out of E from a set Ss of kernel generators
# as a composition of e l-isogenies
def computeIsogeny(E, Ss, l, e):
    S_tmps = Ss
    E_tmp = E
    ϕ = None
    for k in range(e):
        R_tmps = S_tmps
        for _ in range(e-k-1):
            R_tmps = [ l*R_tmp for R_tmp in R_tmps ]
        ϕ_k = E_tmp.isogeny(kernel=R_tmps)
 
        S_tmps = [ ϕ_k(S_tmp) for S_tmp in S_tmps ]
        E_tmp = ϕ_k.codomain()
        if ϕ is None:
            ϕ = ϕ_k
        else:
            ϕ = ϕ_k * ϕ
    return ϕ
 
k_A = randint(0, 2^216-1)
S_A = P_A + k_A*Q_A
ϕ_A = computeIsogeny(E, [S_A], 2, 216)
Alice = (ϕ_A.codomain().a_invariants(), ϕ_A(P_B).xy(), ϕ_A(Q_B).xy(), ϕ_A(P_A).xy(), ϕ_A(Q_A).xy())
print(f"Alice = {Alice}")
 
k_B = randint(0, 3^137-1) 
S_B = P_B + k_B*Q_B
ϕ_B = computeIsogeny(E, [S_B], 3, 137)
Bob = (ϕ_B.codomain().a_invariants(), ϕ_B(P_A).xy(), ϕ_B(Q_A).xy())
print(f"Bob = {Bob}")
 
(E_B, B_P_A, B_Q_A) = Bob
E_B = EllipticCurve(F, E_B)
B_P_A = E_B(B_P_A)
B_Q_A = E_B(B_Q_A)
B_S_A = B_P_A + k_A*B_Q_A
jAlice = computeIsogeny(E_B, [B_S_A], 2, 216).codomain().j_invariant()
 
(E_A, A_P_B, A_Q_B, _, _) = Alice
E_A = EllipticCurve(F, E_A)
A_P_B = E_A(A_P_B)
A_Q_B = E_A(A_Q_B)
A_S_B = A_P_B + k_B*A_Q_B
jBob = computeIsogeny(E_A, [A_S_B], 3, 137).codomain().j_invariant()
 
assert jAlice == jBob
 
flag = open("flag.txt", "rb").read().strip()
assert len(flag) == 32
 
sk = hashlib.sha256(str(jAlice).encode('ascii')).digest()[:16]
cipher = AES.new(sk, AES.MODE_CBC)
print(f"iv = {b64encode(cipher.iv)}")
print(f"ct = {b64encode(cipher.encrypt(flag))}")
 

 

Solution

This is Supersingular Isogeny Diffie-Hellman protocol. Looking at the Wikipedia article and back, we see that we have extra information, $$\phi_A(P_A), \phi_A(Q_A)$$ Since $\phi_A$ has $S_A = P_A + k_AQ_A$ as it's kernel, we see that $$ \phi_A(P_A + k_AQ_A) = \phi_A(P_A) + k_A \phi_A(Q_A) = 0$$ Also, since the values here are in a subgroup of order $2^{216}$, we can calculate $k_A$ (i.e. discrete logarithm) efficiently with Pohlig-Hellman.

 

Now that we know $k_A$, one of the secret keys, we can just follow our algorithm to calculate the shared secret.

 

p = 2^216*3^137 - 1
F.<i> = GF(p^2, modulus=x^2+1)
E = EllipticCurve(F, [0, 6, 0, 1, 0])
 
def computeIsogeny(E, Ss, l, e):
    S_tmps = Ss
    E_tmp = E
    ϕ = None
    for k in range(e):
        R_tmps = S_tmps
        for _ in range(e-k-1):
            R_tmps = [ l*R_tmp for R_tmp in R_tmps ]
        ϕ_k = E_tmp.isogeny(kernel=R_tmps)
 
        S_tmps = [ ϕ_k(S_tmp) for S_tmp in S_tmps ]
        E_tmp = ϕ_k.codomain()
        if ϕ is None:
            ϕ = ϕ_k
        else:
            ϕ = ϕ_k * ϕ
    return ϕ
 
xQ20=0x000C7461738340EFCF09CE388F666EB38F7F3AFD42DC0B664D9F461F31AA2EDC6B4AB71BD42F4D7C058E13F64B237EF7DDD2ABC0DEB0C6C
xQ21=0x00025DE37157F50D75D320DD0682AB4A67E471586FBC2D31AA32E6957FA2B2614C4CD40A1E27283EAAF4272AE517847197432E2D61C85F5
yQ20=0x001D407B70B01E4AEE172EDF491F4EF32144F03F5E054CEF9FDE5A35EFA3642A11817905ED0D4F193F31124264924A5F64EFE14B6EC97E5
yQ21=0x000E7DEC8C32F50A4E735A839DCDB89FE0763A184C525F7B7D0EBC0E84E9D83E9AC53A572A25D19E1464B509D97272AE761657B4765B3D6
xP20=0x0003CCFC5E1F050030363E6920A0F7A4C6C71E63DE63A0E6475AF621995705F7C84500CB2BB61E950E19EAB8661D25C4A50ED279646CB48
xP21=0x001AD1C1CAE7840EDDA6D8A924520F60E573D3B9DFAC6D189941CB22326D284A8816CC4249410FE80D68047D823C97D705246F869E3EA50
yP20=0x001AB066B84949582E3F66688452B9255E72A017C45B148D719D9A63CDB7BE6F48C812E33B68161D5AB3A0A36906F04A6A6957E6F4FB2E0
yP21=0x000FD87F67EA576CE97FF65BF9F4F7688C4C752DCE9F8BD2B36AD66E04249AAF8337C01E6E4E1A844267BA1A1887B433729E1DD90C7DD2F
xQ30=0x0012E84D7652558E694BF84C1FBDAAF99B83B4266C32EC65B10457BCAF94C63EB063681E8B1E7398C0B241C19B9665FDB9E1406DA3D3846
xQ31=0x0000000
yQ30=0x0000000
yQ31=0x000EBAAA6C731271673BEECE467FD5ED9CC29AB564BDED7BDEAA86DD1E0FDDF399EDCC9B49C829EF53C7D7A35C3A0745D73C424FB4A5FD2
xP30=0x0008664865EA7D816F03B31E223C26D406A2C6CD0C3D667466056AAE85895EC37368BFC009DFAFCB3D97E639F65E9E45F46573B0637B7A9
xP31=0x0000000
yP30=0x0006AE515593E73976091978DFBD70BDA0DD6BCAEEBFDD4FB1E748DDD9ED3FDCF679726C67A3B2CC12B39805B32B612E058A4280764443B
yP31=0x0000000
 
Q_A = E(xQ20 + xQ21*i, yQ20 + yQ21*i)
P_A = E(xP20 + xP21*i, yP20 + yP21*i)
Q_B = E(xQ30 + xQ31*i, yQ30 + yQ31*i)
P_B = E(xP30 + xP31*i, yP30 + yP31*i)
 
Alice = ((0, 6, 0, 6001602663961206370988750155271268843249113105575064100544244329723627508642651491029799456469448718421085928092642609765039188242*i + 17122560027285283790825644308649714063340414789188915872095421354901510218060415163697310413170734130335144089439494750625538071980, 22241966002746626067354539975418232642475646213518284443509300453664841759671344583904727702765870170961054029730219838438930886730*i + 6295409890219768050656401214128285134680958664621604435525993857295024885942522198730338761351461854361939143813589229958450834937), (20693617845250531673791079572257479372406496374051176010221583150895284635664420984163027961195027146723306399733543575074371571546*i + 12579440504826227790399898461168329080116453795381885031938887599830693619864645875985379594607106805272063128287141040474324472579, 17003339040898697587060167865681315428279965204095022676751761236717662173320135824191474549296911745414760875386583097246892970743*i + 2450227209495560745928392442008559789430024267104386893781343959329588604681368476319376824183170770268590193199446339985032818433), (24196999226902675779045571226331502647086872832197399777068255320010293863359017283213324144431537822661506383681353187559191999771*i + 14031872773998733507298731440596005313939108957137912313429212267974724984039194243338858626174518892025349039167378718436374581722, 10067956801857468023514754660550671095579147019588599811273848235704360993890497575424172688000039308192770149207724142524545451074*i + 9704956586624341710808951764565861341114293792082683257320510639095567055930904001585984811139137392398321200917960531515122425604), (21482597851178884503353076937735588452957177768806776910812379517549572253101759233236102347370343956671258496673645283509995572850*i + 14096078902807078355928598956816130045619245790159384751176932745646753234211180941505758827833314091690388346935619473665442809259, 13679392986650554551011681934303695650088628896811869083453967966676089303335417699532232752393700725181942165609165070072195990421*i + 22303973329492411565669001646989446651767650420180177485066511378012378529261175557912535448570067170663048114739927772127080694786), (5031508630808576087782892353323275460174142373365249589846782383660521445945988018058115279743582819518492860550820586178080959929*i + 20361864043088022309832424954188288334129520236737890920001299362176525293198035690628699135584668073379687130832090636102750496003, 5326896702997677262072220524322872052674185107431056651996898750306495168544570294686542579294013185895403025686718275379409582021*i + 7018087072590614715963128743406699936749123349867893045580774389322712378049822434865393438816413618294542843639485193888664986503))
Bob = ((0, 6, 0, 2510377837984569005668272963938229152759212776314258952545654072169410901298850712372306096701112903052487282410712205434980682770*i + 1533616599018469519548641055342254252507904258735350043186382046019246639038089759129707675919612374167907298647004842048842483225, 13335813103700469160284801960413086144549776993448017319107340684719947118153850729369660724596130930055245047262733708054423015655*i + 17338799868192494405204548102094725343306200019012693785648257092061088427620739800739315465276207804594142456129224673452195357714), (2771195673566835722887342815479686444463738278075014443830431110033775598812266459191044593910730473384513927831673567602258951977*i + 14695642564069380381636057787623481658663045420929947439988595067986417545517691517441254145488869846179463754817003384192274626463, 18564301293503451778592169644157610474379393936432543000343986957900909392616771402521075243703340903344745798060095728893961976940*i + 19628333731314344646926186187873836263784148023213378217245128148326949516664862760385029489345376891188072162779569669305066964933), (22650214990480384681860370457554162699319780968761610136003430194938807060051700030135993836240770510069117319449743388225281444184*i + 3377155996988041268039072873935941531295378688722591082040326948052676519006168915555632884024981285908480033902758240587615693054, 17806681788782120983952163360625445316482360798557639190977860032884873427321883793075291472918577432082376117267831746467121303568*i + 21533180999838449404329422084189008931697041812999894837076670480949795196804840300494281304611360768987802541355649881398701758313))
 
(E_A, A_P_B, A_Q_B, A_P_A, A_Q_A) = Alice
E_A = EllipticCurve(F, E_A)
A_P_B = E_A(A_P_B)
A_Q_B = E_A(A_Q_B)
A_P_A = E_A(A_P_A)
A_Q_A = E_A(A_Q_A)
 
# print(discrete_log(A_P_A, A_Q_A, ord=2^216, operation='+'))
k_A = 2^216 - 77755655179930472801709066068873804442103726663917450704829188611
(E_B, B_P_A, B_Q_A) = Bob
E_B = EllipticCurve(F, E_B)
B_P_A = E_B(B_P_A)
B_Q_A = E_B(B_Q_A)
B_S_A = B_P_A + k_A*B_Q_A
jAlice = computeIsogeny(E_B, [B_S_A], 2, 216).codomain().j_invariant()
 
print(jAlice)
 
jAlice = "11056265280320404779614673772059927218754555738553445716393833134024824685344573644810486464601209854921719950024169587404070224902*i + 13483412480684215684949244771895365050495321597976589093887140592592966008044279045153836163302049958922591278477269370463266951423"
sk = hashlib.sha256(jAlice.encode('ascii')).digest()[:16]
 
iv = b'XSglnu+2ZwFuHGE8ddIuJQ=='
iv = base64.b64decode(iv)
ct = b'4VR9ty+lFW6oQoWTVHiDE7A9uKw0KbQzpnCWOGVQXGo='
ct = base64.b64decode(ct)
 
cipher = AES.new(sk, AES.MODE_CBC, iv)
print(cipher.decrypt(ct))