# Union CTF

We played on 19 Feb 2021 and placed 66th / 466.

## Mordell Prime

We are given `mordell_primes.sage` below and an `output.txt` that has the values of $N$ and $c$.

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

Because the elliptic curve is limited by an integer field, not an integer mod ring and because $N$ and $c$ in `output.txt` didn't seem all that huge, I can just iterate through $k$. In other words, $x$ and $y$ aren't limited by mods like in a typical elliptic curve equation $y^{2} = ax^{2} + bx + c \pmod{p}$; they just have to be integers.

`solution.sage`

from Crypto.Util.number import *

exec(open("output.txt").read())

E = EllipticCurve(QQ, [0, 1, 0, 78, -16])
P = E(1, 8)

for k in range(1, 1000, 2):
    print(k)
    Q = k * P
    R = (k + 1) * P
    p = Q[0].numerator()
    q = R[0].numerator()
    if GCD(p, N) != 1:
        p = GCD(p, N)
        q = N // p
        print("found")
        break
    if GCD(q, N) != 1:
        q = GCD(q, N)
        p = N // q
        print("found")
        break

phi = (p - 1) * (q - 1)
d = inverse_mod(0x10001, phi)
m = pow(c, d, N)
print(long_to_bytes(m))

## Humanserver

We are given `human_server.py` below and had server connection details.

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)

This challenge simulates a MITM (Man In The Middle) attack on an ECDH (Elliptic Curve Diffie Hellman Exchange). The premise of ECDH is the discrete log problem: it's easy to multiply points on an elliptic curve, but it's difficult to determine the number of times a point is multiplied given the starting and ending points. In this source code's scenario, the generator is the point that's being multiplied, the number of times a point is multiplied is Alice and Bob's secrets, and the multiplication results are Alice and Bob's public keys. Alice and Bob receive each other's public keys, and multiply them with their private keys to theoretically obtain the same point, the shared key.

The vulnerability with this challenge is that we can send the generator point instead of Alice and Bob's public keys, and that the nonce is weak. If we send the generator to Bob instead of Alice's key, then Bob's shared key becomes $bG$ where $b$ is Bob's secret key. If we send the generator to Alice instead of Bob's key, then Alice's shared key is $aG$. Then we have to elude the nonce ($n$) verifaction that states $aG \oplus n_{1} = bG \oplus n_{2}$. We can input any random number $\gt 2^{64}$ for $n_{1}$, and for $n_{2}$ to work, all have to do to calculate it is $aG \oplus bG \oplus n_{1}$. We already know $aG$ and $bG$ as they are public keys.

I wrote a client program used to send/receive messages from the server and carry out the attack.


import json
from fastecdsa.curve import secp256k1
import hashlib
from Crypto.Util.number import long_to_bytes
from Crypto.Cipher import AES

G = secp256k1.G
nonce = 2**64 + 1

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

p1 = input_json("Alice pub: ")
print(json.dumps({
    "Px": G.x, "Py": G.y, "nonce": nonce
}))

p2 = input_json("Bob pub: ")
print(json.dumps({
    "Px": G.x, "Py": G.y, "nonce": p1["Px"] ^ nonce ^ p2["Px"]
}))

data = input_json("Encrypted flag: ")
key = p2["Px"] ^ nonce
key = hashlib.sha1(long_to_bytes(key)).digest()[:16]
cipher = AES.new(key, AES.MODE_CBC, bytes.fromhex(data["iv"]))
print(cipher.decrypt(bytes.fromhex(data["encrypted_flag"])))

## Crown Sterling

We were given the source code of a cryptosystem and the resulting ciphertext (`76f64667220717784affa07cf6b8be52c7d8348d778a41615efa9e53f2566b27fd96eb984c08`).

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

This code is highly trollish but still a bit complicated. Once you simplify it, you will see a strategy:

1. Input the set $\{a, b, c, d, e, f\}$ as the first character of the key. If it matches the first character of the ciphertext, then you have the key.
2. Say you found $a$ was the first letter. Then try $aa$, $ab$, ... as the keys to 1.
3. Do this until you get an error saying `index` is out of range.

You probably have the first six characters of the key by now. So you can calculate `len(q_grid)` easily now and bruteforce the rest.

My code more or less follows the last step below.

from cr0wn_sterling import *
import math
from itertools import product

begins = "union{"

ciphertext = bytes.fromhex("76f64667220717784affa07cf6b8be52c7d8348d778a41615efa9e53f2566b27fd96eb984c08")
clen = len(ciphertext)

def fibo(n):
    phi = (1 + math.sqrt(5)) / 2
    return round(pow(phi, n) / math.sqrt(5))

fib_cache = {i: fibo(i) for i in range(clen)}

primes = get_q_grid(75000)
pi_cache = {}

for perm in list(product("ABCDEF", repeat=2)):
    mid = "".join(p for p in perm)
    perm = "ACDADC" + mid # from trial and error
    try:
        key_indexes, size = get_key(perm)
    except:
        continue
    qlen = len(get_q_grid(size))
    if not qlen:
        continue
    print(perm)

    flag = ""
    for i in range(clen):
        index = key_indexes[i % len(key_indexes)] * fib_cache[i]
        q = primes[index % qlen]
        khb = bbp_pi(q)
        out = chr(ciphertext[i] ^ int(khb, 16))
        flag += out
    if flag.startswith(begins):
        print(flag)

## Neoclassical

In this challenge, we are given neoclassical.py and output.txt.

`neoclassical.py`

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]

if __name__ == "__main__":
    A,a = gen_public_key(G,p)
    print(a)
    B,b = gen_public_key(G,p)
    print(b)
    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}")

`output.txt`

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]
encrypted_flag = {'iv': 'f62c1400190702198a26c4f855030f8c', 'encrypted_flag': '9580af623a2427920469c31407f9cec7ccab2389cb3a120869106bf6c6f6fe09810172a1f0f3892c321237ac0e4b7d9a'}

Once you simplify the code, you'll realize you need to solve the equation $G^{a} = A\pmod{p}$ for $a$, the private key. Because $G$ and $A$ are matrices (instead of numbers like in the normal Diffie-Hellman Exchange), $a$ can be easily solved. I found the [theory](https://crypto.stackexchange.com/questions/3840/a-discrete-log-like-problem-with-matrices-given-ak-x-find-k) helpful and a [previous ctf solution](https://ctftime.org/writeup/8681) to copy code from.

`sol.sage`

from neoclassical import *

exec(open("output.txt").read())

R = IntegerModRing(p)
M_a = Matrix(R, [[A[5*i + j] for j in range(5)] for i in range(5)])
M_b = Matrix(R, [[B[5*i + j] for j in range(5)] for i in range(5)])
M_g = Matrix(R, [[G[5*i + j] for j in range(5)] for i in range(5)])

J, P = M_g.jordan_form(transformation=True)
I = ~P * M_a * P
alpha = J[3][3] * I[3][4] / I[4][4]
print(alpha)

shared_secret = gen_shared_secret(B,alpha,p)
key = sha1(str(shared_secret).encode('ascii')).digest()[:16]
cipher = AES.new(key, AES.MODE_CBC, bytes.fromhex(encrypted_flag['iv']))
print(cipher.decrypt(bytes.fromhex(encrypted_flag['encrypted_flag'])))