Posts Union CTF
Post
Cancel

Union CTF

HumanServer

Source Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
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

print(ORDER)

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
        print(self.key)

    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

Here we are taking the role of an attacker in between Alice and Bob and we can modify the parameters that they send each other. The curve looks secure as well so we can’t really attack that.

The interesting portion is the nonce that they use:

1
2
3
4
5
6
7
8
    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
        print(self.key)

We can see here that they XOR the nonce with the shared key and check that they have the same shared key afterwards. To exploit that I went with the following approach:

  • Use the generator of the curve as your key
  • Send the point that was generated by Alice as the nonce to Bob and vice versa

This means that we get the following

\[(a * G) \oplus B = A \oplus B\]

So now their shared key is basically A ^ B and we can then decrypt the flag with that

Solution Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
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 pwn import *

from fastecdsa.curve import secp256k1
from fastecdsa.point import Point

r = remote('134.122.111.232', 54321, level='debug')

def json_recv():
    line = r.recvuntil("}")
    return json.loads(line.decode())

def json_send(hsh):
    request = json.dumps(hsh).encode()
    r.sendline(request)

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

def get_public_key(private):
    A = G * private
    return A

def get_nonce(private, received):
    r = Point(int(received["Px"]), int(received["Py"]), curve=secp256k1)
    return (r * private).x

def decrypt_flag(shared_secret: int, iv: str, ciphertext: str):
    key = hashlib.sha1(long_to_bytes(shared_secret)).digest()[:16]
    cipher = AES.new(key, AES.MODE_CBC, bytes.fromhex(iv))
    plaintext = cipher.decrypt(bytes.fromhex(ciphertext))

    return unpad(plaintext, 16).decode()


mykey = get_public_key(1)

r.recvuntil("Alice sends public key")
r.recv()

Alice = json_recv()
print(Alice)
r.recvuntil("Send to Bob: ")

to_bob = {
    "Px": mykey.x,
    "Py": mykey.y,
    "nonce": get_nonce(1, Alice)
}

json_send(to_bob)

r.recvuntil("Bob sends public key")
r.recv()

Bob = json_recv()
print(Bob)
r.recvuntil("Send to Alice: ")

to_alice = {
    "Px": mykey.x,
    "Py": mykey.y,
    "nonce": get_nonce(1, Bob)
}

json_send(to_alice)

r.recvuntil("Alice sends encrypted flag to Bob")
print(r.recvuntil("\n\n"))

flag = json_recv()
print(flag)

shared = Alice["Px"] ^ Bob["Px"]

print(decrypt_flag(shared, flag["iv"], flag["encrypted_flag"]))

Mordel Primes

Source Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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

Basically here the hint that was given weired me out. It said more or less that it could generate any prime number over the real numbers. This may be true but the way they are generated in the code above doesn’t guarantee a prime. So my guess was that k was small enough to brute force since they probably took only the first primes that worked and thats it.

I brute forced this using SAGE and got the key k used pretty fast.

Solution Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import sys

from Crypto.Util.number import bytes_to_long, long_to_bytes

N = 5766655232619116707100300967885753418146107012385091223647868658490220759057780928028480463319202968587922648810849492353260432268633862603886585796452077987022107158189728686203729104591090970460014498552122526631361162547166873599979607915485144034921458475288775124782641916030643521973787176170306963637370313115151225986951445919112900996709332382715307195702225692083801566649385695837056673372362114813257496330084467265988611009917735012603399494099393876040942830547181089862217042482330353171767145579181573964386356108368535032006591008562456350857902266767781457374500922664326761246791942069022937125224604306624131848290329098431374262949684569694816299414596732546870156381228669433939793464357484350276549975208686778594644420026103742256946843249910774816227113354923539933217563489950555104589202554713352263020111530716888917819520339737690357308261622980951534684991840202859984869712892892239141756252277430937886738881996771080147445410272938947061294178392301438819956947795539940433827913212756666332943009775475701914578705703916156436662432161
c = 5724500982804393999552325992634045287952804319750892943470915970483096772331551016916840383945269998524761532882411398692955440900351993530895920241101091918876067020996223165561345416503911263094097500885104850313790954974285883830265883951377056590933470243828132977718861754767642606894660459919704238136774273318467087409260763141245595380917501542229644505850343679013926414725687233193424516852921591707704514884213118566638296775961963799700542015369513133068927399421907223126861526282761409972982821215039263330243890963476417099153704260378890644297771730781222451447236238246395881031433918137098089530325766260576207689592620432966551477624532170121304029721231233790374192012764855164589022421648544518425385200094885713570919714631967210149469074074462611116405014013224660911261571843297746613484477218466538991573759885491965661063156805466483257274481271612649728798486179280969505996944359268315985465229137237546375405105660181489587704128670445623442389570543693177429900841406620324743316472579871371203563098020011949005568574852024281173097996529

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

k = 1

p1 = 0 # 17922287659013798442573402576339735849131128752056341575054197930940787246564949598938335376226031527888079106524104711777865485173232825060793232006924673971381527349154104858168561572160671487344179035618322434925270004055702274152607679042184080640691186862346789874863888075906696781653068925076057856953267732589112379785385330133335551948122941721689924982720304114154248001316403957518439002843731516224614663616879830159618638468356727817020281211416957107830839823313351269768071723444073187217264382241


while True:
    Q = k*P

    if is_prime(Q[0].numerator()):
        if N%Q[0].numerator() == 0:
            p1 = Q[0].numerator()
            break
    k+=1
#    sys.stdout.write(k)

q1 = N // p1
assert N == q1*p1

e = 0x10001

phi = (q1-1) * (p1-1)
d = inverse_mod(e, phi)
print(long_to_bytes(pow(c, d, N)))
This post is licensed under CC BY 4.0 by the author.

Rookie Mistake

LINE CTF