Hack.lu CTF 2018 Writeup

この大会は2018/10/16 19:00(JST)～2018/10/18 19:00(JST)に開催されました。
今回もチームで参戦。結果は 1109点で1035チーム中51位でした。
自分で解けた問題をWriteupとして書いておきます。

Relations (Crypto)

いろいろ試してみる。

$ nc arcade.fluxfingers.net 1821
------------------------------
Welcome to theory world
------------------------------

------------------------------
Possible Oracles
(XOR) Choose XOR Oracle
(ADD) Choose ADD Oracle
(DEC) For trying to decrypt
-----------------------------*
XOR

Please choose the operand in hex >>> 01
Ciphertext is  sY4v3laEDC9hcW7OLMoOkxrz7SVVioYl+4ni7XawrypvCKuodcSPtwpvEJyvNGxDQgEM+qCeKcaq
xk1a7I65qQ==

------------------------------
Possible Oracles
(XOR) Choose XOR Oracle
(ADD) Choose ADD Oracle
(DEC) For trying to decrypt
-----------------------------*
XOR

Please choose the operand in hex >>> 0001
Ciphertext is  sY4v3laEDC9hcW7OLMoOkxrz7SVVioYl+4ni7XawrypvCKuodcSPtwpvEJyvNGxDQgEM+qCeKcaq
xk1a7I65qQ==

------------------------------
Possible Oracles
(XOR) Choose XOR Oracle
(ADD) Choose ADD Oracle
(DEC) For trying to decrypt
-----------------------------*
XOR

Please choose the operand in hex >>> 56
Ciphertext is  NWwcbySi44ud+TDvirbaZbwH0P5iXI0DIce9fPsp1PAapdofgXXHF2Up8cVdgmQZff4z9IUxemHh
7vHVQ6pz+w==

------------------------------
Possible Oracles
(XOR) Choose XOR Oracle
(ADD) Choose ADD Oracle
(DEC) For trying to decrypt
-----------------------------*
ADD

Please choose the operand in hex >>> 56
Ciphertext is  YGuF1Rl5Xj44kM+21Fazt7IFH0pDb5VV9QhnWghpIfCQr6fjwi2ko9RHEdw+s7dgEMKTWaf3eum/
QeqPcV6Vng==

$ nc arcade.fluxfingers.net 1821
------------------------------
Welcome to theory world
------------------------------

------------------------------
Possible Oracles
(XOR) Choose XOR Oracle
(ADD) Choose ADD Oracle
(DEC) For trying to decrypt
-----------------------------*
DEC

Enter the key base64 encoded >>> MDEy                                    
Traceback (most recent call last):
  File "/home/chall/rka.py", line 113, in <module>
    main()
  File "/home/chall/rka.py", line 107, in main
    aes = pyaes.AESModeOfOperationECB(key)
  File "/home/chall/pyaes/aes.py", line 304, in __init__
    self._aes = AES(key)
  File "/home/chall/pyaes/aes.py", line 134, in __init__
    raise ValueError('Invalid key size')
ValueError: Invalid key size

どうやらAESの鍵にXORやADDして暗号化した結果を表示していると推定できる。各ビットに対して、XORした鍵とADDした鍵が同じ場合は、ビットが立っていないことになることを利用して、鍵を1ビットずつ割り出し、128ビット分判明したら復号する。

import socket
import re
import base64

def recvuntil(s, tail):
    data = ''
    while True:
        if tail in data:
            return data
        data += s.recv(1)

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('arcade.fluxfingers.net', 1821))

b_key = ''
for i in range(128):
    print 'Round %d' % (i + 1)
    print b_key
    send_data = hex(2**i)[2:].rstrip('L')

    data = recvuntil(s, '*\n')
    print data + 'XOR'
    s.sendall('XOR\n')
    data = recvuntil(s, '>>> ')
    print data + send_data
    s.sendall(send_data + '\n')

    data = recvuntil(s, '\n\n')
    pattern = 'Ciphertext is  (.+)\n(.+)\n'
    m = re.search(pattern, data)
    ciphertext = m.group(1) + m.group(2)
    print data

    data = recvuntil(s, '*\n')
    print data + 'ADD'
    s.sendall('ADD\n')
    data = recvuntil(s, '>>> ')
    print data + send_data
    s.sendall(send_data + '\n')

    data = recvuntil(s, '\n\n')
    pattern = 'Ciphertext is  (.+)\n(.+)\n'
    m = re.search(pattern, data)
    ciphertext2 = m.group(1) + m.group(2)
    print data

    if ciphertext == ciphertext2:
        b_key = '0' + b_key
    else:
        b_key = '1' + b_key

key = ''
for i in range(0, 128, 8):
    key += chr(int(b_key[i:i+8], 2))

print key.encode('hex')
b64_key = base64.b64encode(key)

data = recvuntil(s, '*\n')
print data + 'DEC'
s.sendall('DEC\n')
data = recvuntil(s, '>>> ')
print data + b64_key
s.sendall(b64_key + '\n')

data = recvuntil(s, '\n')
print data

flag{r3l4t3d_k3y_der1iviNg_fuNct1on5_h4ve_to_be_a_l1mit3d_cla55}

Multiplayer Part 1 (Crypto)

jsonデータ入力。パラメータは x, y, c, d, groupIDで、以下の形式。

{"x": val, "y": val, "c": val, "d": val, "groupID": val}

X = E*1
X == c*P + d*Q
response = get_response(data["x"], data["y"], data["c"], data["d"], data["groupID"])

DBにない場合は登録。指定GroupIDのデータを201個以上登録できたら、フラグが表示される。c, dをランダムな値にしてXを算出。x, yを指定すればよい。

import socket
import re
from gmpy2 import invert
from random import randint

class EllipticCurve(object):
    def __init__(self, a, b, p):
        self.a = a
        self.b = b
        self.p = p

        self.discriminant = -16 * (4 * a * a * a + 27 * b * b)
        if not self.isSmooth():
            raise Exception("The curve %s is not smooth!" % self)

    def isSmooth(self):
        return self.discriminant != 0

    def testPoint(self, x, y, p):
        return (y ** 2) % p == (x ** 3 + self.a * x + self.b) % p

    def __str__(self):
        return 'y^2 = x^3 + %Gx + %G (mod %G)' % (self.a, self.b, self.p)

    def __eq__(self, other):
        return (self.a, self.b, self.p) == (other.a, other.b, other.p)

class Point(object):
    def __init__(self, curve, x, y):
        self.curve = curve
        self.x = x
        self.y = y
        if not curve.testPoint(x, y, curve.p):
            raise Exception("The point %s is not on the given curve %s" % (self, curve))

    def __neg__(self):
        return Point(self.curve, self.x, -self.y)

    def __add__(self, Q):
        if isinstance(Q, Ideal):
            return self
        x_1, y_1, x_2, y_2 = self.x, self.y, Q.x, Q.y
        if (x_1, y_1) == (x_2, y_2):
            if y_1 == 0:
                return Ideal(self.curve)
            s = (3 * x_1 * x_1 + self.curve.a) * int(invert(2 * y_1, self.curve.p))
        else:
            if x_1 == x_2:
                return Ideal(self.curve)
            s = (y_2 - y_1) * int(invert(x_2 - x_1, self.curve.p))
        x_3 = (s * s - x_2 - x_1) % self.curve.p
        y_3 = (s * (x_3 - x_1) + y_1) % self.curve.p
        return Point(self.curve, x_3, self.curve.p - y_3)

    def __sub__(self, Q):
        return self + -Q

    def __mul__(self, n):
        if not (isinstance(n, int) or isinstance(n, long)):
            raise Exception("Can't scale a point by something which isn't an int!")
        else:
            if n < 0:
                return -self * -n
            if n == 0:
                return Ideal(self.curve)
            else:
                Q = self
                R = self if n & 1 == 1 else Ideal(self.curve)
                i = 2
                while i <= n:
                    Q = Q + Q
                    if n & i == i:
                        R = Q + R
                    i = i << 1
        return R

    def __rmul__(self, n):
        return self * n

class Ideal(Point):

    def __init__(self, curve):
        self.curve = curve

    def __str__(self):
        return "Ideal"

    def __neg__(self):
        return self

    def __add__(self, Q):
        return Q

    def __mul__(self, n):
        if not isinstance(n, int):
            raise Exception("Can't scale a point by something which isn't an int!")
        else:
            return self

p = 889774351128949770355298446172353873
a = 12345
b = 67890
px = 238266381988261346751878607720968495
py = 591153005086204165523829267245014771
qx = 341454032985370081366658659122300896
qy = 775807209463167910095539163959068826

def recvuntil(s, tail):
    data = ''
    while True:
        if tail in data:
            return data
        data += s.recv(1)

def make_json(x, y, c, d):
    groupID = 'n0r4n3c0_m1k3n3c0'
    json_format = '{"x": "%d", "y": "%d", "c": "%d", "d": "%d", "groupID": "%s"}'
    json = json_format % (x, y, c, d, groupID)
    return json

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('arcade.fluxfingers.net', 1822))

E = EllipticCurve(a, b, p)
P = Point(E, px, py)
Q = Point(E, qx, qy)

while True:
    c = randint(1, p - 1)
    d = randint(1, p - 1)
    X = c * P + d * Q
    x = X.x
    y = X.y
    json = make_json(x, y, c, d)
    print json
    s.sendall(json + '\n')
    data = recvuntil(s, '}')
    if 'flag1' in data:
        data += recvuntil(s, '}')
        print data
        break
    else:
        print data

flag{d1str1but3_the_rh0w_p0W3r}

*1:x, y