De Danske Cybermesterskaber: Kuuuurveen

May 9, 2021 Crypto
Share on:

Overview

Writeup by: ChrRaz

Kuuuurveen

We are given the following challenge description. A client and a server have been communicating the flag over an encrypted channel.

Der er en Kuuuuuuuuuuuuuuurveeeeeee, er den ikke smuk?
En client og en server kommunikere over en krypteret kommunikationskanal. Se om du ved hjælp af source koden kan finde frem til flaget som ligger gemt i følgende cipher text.

Serveren sender:
    fMcMebR1Osrx6bvguXcYGsgNw+152PNT5u/ld5LB34k=
    GOB/Vh3J40wUPs0LUOhpZmV7oiNQ54yzdUGv8Vte/hc=

Client sender:
    Xyziy608ke7cIOWiJ041eSd4lSdX8t2nWU4af5jEyww=
    Sr5lm+pOPih+Duf1AD4MYxh2HiHprfPtV24J9X5I4Nc=
    Bf3ooLl88b+H5W90zlRMmg==6IetS1I5jEnKzduIEFHOUmw=

The code

We are given the following file called curev25519.py which seemingly implements Curve25519 which is considered cryptographically secure. I have removed the details of some functions as they are not important to the solution.

import random

# y^2 = x^3 + 486662 * x^2 + x

A = 486626
s = 1

p = 2**255 - 19

G = [0x9, 0x20ae19a1b8a086b4e01edd2c7748d14c923d4d7e6d7c61b229e9c5a27eced3d9]


# from "Complete Addition Law for Montgomery Curves"
# by Jaeheon Kim, Je Hong Park, Dong-Chan Kim, and Woo-Hwan Kim
def affine_add(Ax, Ay, Az, Bx, By, Bz):
    ...


def smul(a, Ax, Ay):
    ...


def key_gen(base = G):
  a = random.randint(0, p)

  return a, smul(a, base[0], base[1])

The other file comm.py is quite long. The most important part to us is where they perform the key exchange:

  # use custom base point
  G = [0x71f2f4b0fc461c6b495c07666be790db41e20c404ce1979ba3c6321cc008b837,
       0x1b38534269b9eab12584260f17b3b070cb115a7c40701425c76021812b56eff7]

  # generate DH key pair
  a, (Ax, Ay) = key_gen(G)


  data = base64.b64encode(Ax.to_bytes(32, 'big')) + \
         base64.b64encode(Ay.to_bytes(32, 'big'))

  conn.sendall(data)
  print(data)

  data = bytes()
  while len(data) < 88:
    data += conn.recv(1024)

  Bx = int.from_bytes(base64.b64decode(data[:44]), 'big')
  By = int.from_bytes(base64.b64decode(data[44:88]), 'big')


  # compute share secret
  Sx, Sy = smul(a, Bx, By)

The attack

The filename sounds like a hint and if we look closely at the file we see that the implementer has made a mistake in copying the A coffiecient of the curve. This yields a different curve and if we input this into Sage we see that the generator $G$ has very low order.

ec = EllipticCurve(GF(2**255-19), [0,486626,0,1,0])
G = (0x71f2f4b0fc461c6b495c07666be790db41e20c404ce1979ba3c6321cc008b837,
     0x1b38534269b9eab12584260f17b3b070cb115a7c40701425c76021812b56eff7)

G.order() # 5158488229

This means that we can solve the discrete logarithm problem easily to recover the private key of either the client or the server. Here S and C are the public keys exchanged by the server and client. s is the recovered private key of the server.

# Serveren sender:

S = ec(int.from_bytes(base64.b64decode('fMcMebR1Osrx6bvguXcYGsgNw+152PNT5u/ld5LB34k='), 'big'),
       int.from_bytes(base64.b64decode('GOB/Vh3J40wUPs0LUOhpZmV7oiNQ54yzdUGv8Vte/hc='), 'big'))

# Client sender:

C = ec(int.from_bytes(base64.b64decode('Xyziy608ke7cIOWiJ041eSd4lSdX8t2nWU4af5jEyww='), 'big'),
       int.from_bytes(base64.b64decode('Sr5lm+pOPih+Duf1AD4MYxh2HiHprfPtV24J9X5I4Nc='), 'big'))

tag, ciphertext = (base64.b64decode('Bf3ooLl88b+H5W90zlRMmg=='), base64.b64decode('6IetS1I5jEnKzduIEFHOUmw='))

s = discrete_log(S, G, operation='+') # 4745914629

shared = CC * ss

Now that we have the shared secret we can use the same code as the client and server to derive the AES key and decrypt the message.

# derive key
m = hashlib.sha256()
m.update(int(shared[0]).to_bytes(32, 'big'))
digest = m.digest()

key   = digest[:16]
nonce = digest[16:]

cipher = AES.new(key=key, mode=AES.MODE_GCM, nonce=nonce)

cipher.decrypt_and_verify(ciphertext, tag) # b'DDC{As-Iw-RUV1gb}'