HackMD
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
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 output.txt didn't seem all that huge, I can just iterate through
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
I wrote a client program used to send/receive messages from the server and carry out the attack.
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
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:
- Input the set
- Say you found
- Do this until you get an error saying
indexis 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
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'])))
