2021UnionCTF - WriteUp

Introduction

This is a small write up and recurrence for 2021UnionCTF.

Crypto

human_server

Analysis

This is a Diffie-Hellman key exchange challenge:

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)

We can use Man-in-the-middle attack to solve this challenge.

Exp

#!/usr/bin/env python
from pwn import *
import json, hashlib
from fastecdsa.curve import secp256k1
from fastecdsa.point import Point
from Crypto.Cipher import AES
from Crypto.Util.number import *
context.log_level = "debug"

CURVE = secp256k1
ORDER = CURVE.q
G = CURVE.G

r = remote("134.122.111.232",54321)

r.recvuntil("{\"Px\": ")
Px = int(r.recvuntil(",", drop = True))
r.recvuntil("\"Py\": ")
Py = int(r.recvuntil("}", drop = True))
Pa = Point(Px, Py, curve = secp256k1)
noncea = Pa.x
P = json.dumps({"Px" : G.x, "Py" : G.y, "nonce" : noncea})
r.recvuntil("Send to Bob: ")
r.sendline(P)

r.recvuntil("{\"Px\": ")
Px = int(r.recvuntil(",", drop = True))
r.recvuntil("\"Py\": ")
Py = int(r.recvuntil("}", drop = True))
Pb = Point(Px, Py, curve = secp256k1)
nonceb = Pb.x
P = json.dumps({"Px" : G.x, "Py" : G.y, "nonce" : nonceb})
r.recvuntil("Send to Alice: ")
r.sendline(P)

shared_secret = nonceb ^ noncea
key = hashlib.sha1(long_to_bytes(shared_secret)).digest()[:16]

r.recvuntil("{\"iv\": \"")
iv = bytes.fromhex(r.recvuntil("\",", drop = True).decode("utf-8"))
r.recvuntil("\"encrypted_flag\": \"")
enc = bytes.fromhex(r.recvuntil("\"}", drop = True).decode("utf-8"))
r.close()

cipher = AES.new(key, AES.MODE_CBC, iv)
flag = cipher.decrypt(enc)
print(flag)

# union{https://buttondown.email/cryptography-dispatches/archive/cryptography-dispatches-the-most-backdoor-looking/}

Mordell primes

Analysis

This challenge use an EllipticCurve to generate primes and use RSA to encrypt the flag:

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}')

If we traverse the value of k, we can find that the bit numbers of p and q are growing up. So we can use this way to find the right primes and decrypt the flag.

Exp

from Crypto.Util.number import *
N = 5766655232619116707100300967885753418146107012385091223647868658490220759057780928028480463319202968587922648810849492353260432268633862603886585796452077987022107158189728686203729104591090970460014498552122526631361162547166873599979607915485144034921458475288775124782641916030643521973787176170306963637370313115151225986951445919112900996709332382715307195702225692083801566649385695837056673372362114813257496330084467265988611009917735012603399494099393876040942830547181089862217042482330353171767145579181573964386356108368535032006591008562456350857902266767781457374500922664326761246791942069022937125224604306624131848290329098431374262949684569694816299414596732546870156381228669433939793464357484350276549975208686778594644420026103742256946843249910774816227113354923539933217563489950555104589202554713352263020111530716888917819520339737690357308261622980951534684991840202859984869712892892239141756252277430937886738881996771080147445410272938947061294178392301438819956947795539940433827913212756666332943009775475701914578705703916156436662432161
c = 5724500982804393999552325992634045287952804319750892943470915970483096772331551016916840383945269998524761532882411398692955440900351993530895920241101091918876067020996223165561345416503911263094097500885104850313790954974285883830265883951377056590933470243828132977718861754767642606894660459919704238136774273318467087409260763141245595380917501542229644505850343679013926414725687233193424516852921591707704514884213118566638296775961963799700542015369513133068927399421907223126861526282761409972982821215039263330243890963476417099153704260378890644297771730781222451447236238246395881031433918137098089530325766260576207689592620432966551477624532170121304029721231233790374192012764855164589022421648544518425385200094885713570919714631967210149469074074462611116405014013224660911261571843297746613484477218466538991573759885491965661063156805466483257274481271612649728798486179280969505996944359268315985465229137237546375405105660181489587704128670445623442389570543693177429900841406620324743316472579871371203563098020011949005568574852024281173097996529
e = 0x10001
for k in range(0,30):
    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()
    if p * q == N:
        phi = (p - 1) * (q - 1)
        d = inverse_mod(e,phi)
        m = pow(c,d,N)
        flag = long_to_bytes(m)
        print(flag)

# union{s34rch1ng_thr0ugh_r4tion4l_p01nts}

Cr0wn St3rling

Analysis

This challenge is as follows:

#!/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()}")

We can know that the musical_key consists of these letters:

"ABCDEFG"

And its length is 8.

We know the flag head is union{, so we can use this information to get the 2rd-6nd letters of musical_key, and brute the remaining characters to get flag.

Exp

#!/usr/bin/env python3
from Crypto.Util.number import isPrime
import math, itertools

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))]

output = bytes.fromhex("76f64667220717784affa07cf6b8be52c7d8348d778a41615efa9e53f2566b27fd96eb984c08")
known_flag = b"union{"
known_key_byte = [a ^ b for a,b in zip(output,known_flag)]
print(known_key_byte)

fibonacci_arr = [0,1]
q_grid = get_q_grid(75000)

for i in range(2,len(output)):
    fibonacci_arr.append(fibonacci_arr[i-1] + fibonacci_arr[i-2])

musical_key = ["*"] * 8

for i in range(1,len(known_key_byte)):
    for j in range(1,8):
        index = (j ** i) * fibonacci_arr[i]
        q = q_grid[index % len(q_grid)]
        key_byte_hex = bbp_pi(q)
        if int(key_byte_hex,16) == known_key_byte[i]:
            musical_key[i] = chr(0x40 + j)

unkown_key_length = musical_key.count("*")
dic = "ABCDEFG"

for i in itertools.product(dic,repeat = unkown_key_length):
    try:
        brute_key = [i for i in musical_key]
        for j in range(unkown_key_length):
            idx = brute_key.index("*")
            brute_key[idx] = i[j]
        key_indexes, size = get_key(brute_key)
        q_grid = get_q_grid(size)
        flag = []
        for i, p in enumerate(output):
            index = key_indexes[i % len(key_indexes)] * fibonacci_arr[i]
            q = q_grid[index % len(q_grid)]
            key_byte_hex = bbp_pi(q)
            flag.append(p ^ int(key_byte_hex, 16))
        print(bytes(flag))
    except:
        pass

# union{b45ed_oN_iRR3fut4bL3_m4th3m4G1c}

Neo-Classical Key Exchange

This writeup is referenced from rkm0959

Analysis

This is a Diffie-Hellman key exchange challenge with matrices over Fp:

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}")

This is a Discrete Logarithm Problem with matrices.

Consider following things:

The Jordan Canonical Form of G is as follows:

[ 935653797092383|               0|               0|               0                0]
[----------------+----------------+----------------+---------------------------------]
[               0| 895583106357469|               0|               0                0]
[----------------+----------------+----------------+---------------------------------]
[               0|               0| 741118640597053|               0                0]
[----------------+----------------+----------------+---------------------------------]
[               0|               0|               0|1001557463764859                1]
[               0|               0|               0|               0 1001557463764859]

And we can find that:

$$
G^a = A \\
G = PJP^{-1} \\
J^a = P^{-1}AP
$$

We focus on the sub-matrix in the lower right corner of $G$(assume as $S$), its form is as follows:
$$
S =
\left[
\begin{matrix}
\lambda & 1 \\
0 & \lambda \\
\end{matrix}
\right]
$$

Then:
$$
S^a =
\left[
\begin{matrix}
\lambda^a & a\lambda^{a-1} \\
0 & \lambda^a \\
\end{matrix}
\right]
$$

And we can get a as:

$$
a = (a\lambda^{a-1} \times \lambda) / \lambda^a
$$
Finally we can solve this dlp problem.

Exp

from hashlib import sha1
from Crypto.Cipher import AES

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

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 = [28233100393684529817120826374704703970604351085347992179309675559635346595380, 29046194176577252146425228713999025714624645466020308483596362772799464421565, 51414757515365785106884177690982449232859118016584164030996802978303073832864, 32267784952174932165833922809968200325881642530032757218932833269493776228149, 13973793666546842231063337975335309683360495651176415377710477331321414420456, 5286615045753246138573595226543740641269173696296954823357812924414572937107, 43466342875687159863281474559075034075049932698505922755874901032656831073450, 47661605030033906449833071780503259530559725918766113764853049109959949029047, 29762627612115411002000295970517549686591898340299041949451816959553956035443, 49286580271478233284518064235175477517034865850564346192909446300261247213283, 7188366615080791208945602088806130718221011202809096314763875728464565550249, 32182006086354456048519258721570301235369694461013162635052191913678704872393, 21483240138613555020973495536958806124512132313438467660300656866733958284555, 32536424410469390868658830924897162415670475154843962198873348894987606529091, 45625096994113674714302106480828933542072238055815294252728640125290264970846, 24213002979296722993383462232491867853999792671040421022480792914763688570011, 20226375341521636699395168981434607973732973904867124197482261876438894251202, 35665173793762989154951727010732056807487002272231939587142706779138064036737, 44918569326474189030005211458487723881627056771470698141626869348302159144544, 55135331348727541614492445208303357763346452332141430109351274117544563056325, 3933992047445840422521143559241271788171754114229341734112783430664672779696, 21801264227118954504981594527645803342623213184399008070689042493499060756930, 36511317987578612540784999849026900531836613400317039182698008103871338654381, 26496131888936628842836360667203182676230332105839869360126226904814961091203, 30731439605443071877356819320867001660509853590875860716545460172180769908374]
B = [44377211427173233116979050195003801151862259928694524276865425496276215498972, 49241196843948436830587713696810940169354056619506533754073633670263404255961, 23492045323953392330208784813581654383480854895526105331150055254139460724192, 17080512298466023233312431592445586950706981939186458231843048823545276010215, 39604091535611342500963237243447065555062876641002877504522940232561620619318, 56960961102475075778327243487866255394103198246135548238726100230622806328438, 38217368372409493349493021940482885382608210497803407862232172289864983784622, 42335856751075392349376312407843682476509683741291872419641417363122382815132, 51941219313167868120916202016894056878767165096252120052547694800835266376234, 39291827760740007097926684492849490059616209795648655493766840810548112692299, 43135915013972209275982685899523579484981852752898836057210548592960639003728, 23595516638571580424735519959966735718018613005573597878458733582530644060888, 62827451288017543974020113222032392007291072051169612626408144208347674696867, 5592384352020377877919583422508787142347256068192656512514358468697868033175, 18051963256426258602161226818544125427525613549556239701594042609393802930037, 40958445768744523216077674511494171471872825559820257375045060058213312003099, 58717128055983851157674774153408247177039629801049962370399870689530231499322, 1037221856690142468199057506665941102592008657830329236867815734600280869030, 59376420054790038148696948468280202162475373720884110232519335695030684164414, 4151096619484839840558543718588323193224649180369287745679082104762052554517, 59388992954098787668810593349809442685161783884520951198437714884153766418952, 2963435422634311858110276357146679864581253927895056591004158165102829287371, 41537819812103905985231524610057365971827624339877580912325361702870004864439, 39640428648253591645759865709120529164727198669907353665694566732915196666123, 40517325937253252797947519549738947711994111971749366539987665346423972531224]
iv = bytes.fromhex("f62c1400190702198a26c4f855030f8c")
ct = bytes.fromhex("9580af623a2427920469c31407f9cec7ccab2389cb3a120869106bf6c6f6fe09810172a1f0f3892c321237ac0e4b7d9a")

MG = Matrix(GF(p),5,5,G)
MA = Matrix(GF(p),5,5,A)
MB = Matrix(GF(p),5,5,B)

J, P = MG.jordan_form(transformation = True)
MA = P^-1 * MA * P
MB = P^-1 * MB * P

kA = MA[3, 4] / MA[3, 3] * J[3, 3]
kB = MB[3, 4] / MB[3, 3] * J[3, 3]

shared_secret = list_exp(B,kA,p)[0]
key = sha1(str(shared_secret).encode('ascii')).digest()[:16]
cipher = AES.new(key, AES.MODE_CBC, iv)
flag = cipher.decrypt(ct)
print(flag)

# union{high3r_d1m3n510ns_l0w3r_s3cur1ty}

why is a raven..

This writeup is referenced from rkm0959

Analysis

This is a Supersingular isogeny Diffie–Hellman challenge:

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))}")

If you want to know SIDH, you can read this write-up.

And if we focus on the code, we can simply see that Alice send something important:

ϕ_A(P_A).xy(), ϕ_A(Q_A).xy()

Since $ϕ_A$ has:
$$
S_A = P_A + k_AQ_A
$$
as its kernel, we can get:
$$
\phi(S_A) = \phi(P_A + k_AQ_A) = \phi(P_A) + k_A\phi(Q_A) = 0
$$
So we can just calculate $k_A$ with discrete_log

Exp

import hashlib
from base64 import b64decode
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 ϕ

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))
iv = b'XSglnu+2ZwFuHGE8ddIuJQ=='
ct = b'4VR9ty+lFW6oQoWTVHiDE7A9uKw0KbQzpnCWOGVQXGo='

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

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

# A_P_A + k_A * A_Q_A == 0
k_A = discrete_log(E_A(0) - A_P_A, A_Q_A, ord = 2 ^ 216, operation = "+")

B_S_A = B_P_A + k_A * B_Q_A
jAlice = computeIsogeny(E_B, [B_S_A], 2, 216).codomain().j_invariant()

sk = hashlib.sha256(str(jAlice).encode('ascii')).digest()[:16]
iv = b64decode(iv)
ct = b64decode(ct)
cipher = AES.new(sk, AES.MODE_CBC, iv)
flag = cipher.decrypt(ct)
print(flag)

# union{al1c3_in_t0r51ongr0upl4nd}

References

https://en.wikipedia.org/wiki/Man-in-the-middle_attack

https://rkm0959.tistory.com/206

https://en.wikipedia.org/wiki/Jordan_normal_form

https://sectt.github.io/writeups/UnionCTF21/crypto_raven/README