Mind In The Clouds

17 minutes to read

We are given the Python source code of the server that holds the flag:

import json
import signal
import subprocess
import socketserver
from hashlib import sha1
from random import randint
from Crypto.Util.number import bytes_to_long, long_to_bytes, inverse
from ecdsa.ecdsa import curve_256, generator_256, Public_key, Private_key, Signature
import os


fnames = [b'subject_kolhen', b'subject_stommb', b'subject_danbeer']
nfnames = []


class ECDSA:
    def __init__(self):
        self.G = generator_256
        self.n = self.G.order()
        self.key = randint(1, self.n - 1)
        self.pubkey = Public_key(self.G, self.key * self.G)
        self.privkey = Private_key(self.pubkey, self.key)

    def sign(self, fname):
        h = sha1(fname).digest()
        nonce = randint(1, self.n - 1)
        sig = self.privkey.sign(bytes_to_long(h), nonce)
        return {"r": hex(sig.r)[2:], "s": hex(sig.s)[2:], "nonce": hex(nonce)[2:]}

    def verify(self, fname, r, s):
        h = bytes_to_long(sha1(fname).digest())
        r = int(r, 16)
        s = int(s, 16)
        sig = Signature(r, s)

        if self.pubkey.verifies(h, sig):
            return retrieve_file(fname)
        else:
            return 'Signature is not valid\n'


ecc = ECDSA()


def init_storage():
    i = 0
    for fname in fnames[:-1]:
        data = ecc.sign(fname)
        r, s = data['r'], data['s']
        nonce = data['nonce']
        nfname = fname.decode() + '_' + r + '_' + s + '_' + nonce[(14 + i):-14]
        nfnames.append(nfname)
        i += 2


def retrieve_file(fname):
    try:
        dt = open(fname, 'rb').read()
        return dt.hex()
    except:
        return 'The file does not exist!'


def challenge(req):
    req.sendall(b'This is a cloud storage service.\n' +
                b'You can list the files inside and also see their contents if your signatures are valid.\n')

    while True:
        req.sendall(b'\nOptions:\n1.List files\n2.Access a file\n')
        try:
            payload = json.loads(req.recv(4096))
            if payload['option'] == 'list':
                payload = json.dumps(
                    {'response': 'success', 'files': nfnames})
                req.sendall(payload.encode())
            elif payload['option'] == 'access':
                fname = payload['fname']
                r, s = payload['r'], payload['s']
                dt = ecc.verify(fname.encode(), r, s)
                if ('not exist' in dt) or ('not valid' in dt):
                    payload = json.dumps({'response': 'error', 'message': dt})
                else:
                    payload = json.dumps({'response': 'success', 'data': dt})
                req.sendall(payload.encode())
            else:
                payload = json.dumps(
                    {'response': 'error', 'message': 'Invalid option!'})
                req.sendall(payload.encode())
        except:
            payload = json.dumps(
                {'response': 'error', 'message': 'An error occured!'})
            req.sendall(payload.encode())


class incoming(socketserver.BaseRequestHandler):
    def handle(self):
        signal.alarm(30)
        req = self.request
        challenge(req)


class ReusableTCPServer(socketserver.ForkingMixIn, socketserver.TCPServer):
    pass


def main():
    init_storage()
    socketserver.TCPServer.allow_reuse_address = True
    server = ReusableTCPServer(("0.0.0.0", 1337), incoming)
    server.serve_forever()


if __name__ == "__main__":
    main()

Source code analysis

The program begins by calling init_storage. After that, it starts a TCP socket server that will call challenge:

class incoming(socketserver.BaseRequestHandler):
    def handle(self):
        signal.alarm(30)
        req = self.request
        challenge(req)


class ReusableTCPServer(socketserver.ForkingMixIn, socketserver.TCPServer):
    pass


def main():
    init_storage()
    socketserver.TCPServer.allow_reuse_address = True
    server = ReusableTCPServer(("0.0.0.0", 1337), incoming)
    server.serve_forever()

There is an alarm of 30 seconds, which means that the server closes connections after this elapsed time. However, this won’t be a problem.

This is init_storage:

fnames = [b'subject_kolhen', b'subject_stommb', b'subject_danbeer']
nfnames = []

# ...

ecc = ECDSA()


def init_storage():
    i = 0
    for fname in fnames[:-1]:
        data = ecc.sign(fname)
        r, s = data['r'], data['s']
        nonce = data['nonce']
        nfname = fname.decode() + '_' + r + '_' + s + '_' + nonce[(14 + i):-14]
        nfnames.append(nfname)
        i += 2

We see that it uses an ECDSA signature on each of the filenames in fnames, except for the last one (subject_danbeer). Each signature is appended to nfnames, with some additional information (more about this later).

The challenge function shows the options we can use to interact with the server:

def challenge(req):
    req.sendall(b'This is a cloud storage service.\n' +
                b'You can list the files inside and also see their contents if your signatures are valid.\n')

    while True:
        req.sendall(b'\nOptions:\n1.List files\n2.Access a file\n')
        try:
            payload = json.loads(req.recv(4096))
            if payload['option'] == 'list':
                payload = json.dumps(
                    {'response': 'success', 'files': nfnames})
                req.sendall(payload.encode())
            elif payload['option'] == 'access':
                fname = payload['fname']
                r, s = payload['r'], payload['s']
                dt = ecc.verify(fname.encode(), r, s)
                if ('not exist' in dt) or ('not valid' in dt):
                    payload = json.dumps({'response': 'error', 'message': dt})
                else:
                    payload = json.dumps({'response': 'success', 'data': dt})
                req.sendall(payload.encode())
            else:
                payload = json.dumps(
                    {'response': 'error', 'message': 'Invalid option!'})
                req.sendall(payload.encode())
        except:
            payload = json.dumps(
                {'response': 'error', 'message': 'An error occured!'})
            req.sendall(payload.encode())

Well, not many things to do here. We will use list to take said signatures (nfnames). Then, we need to use access to read any of the files, provided its corresponding signature.

We know that it reads a file because the verify method of ECDSA uses retrieve_file:

class ECDSA:
    # ...

    def verify(self, fname, r, s):
        h = bytes_to_long(sha1(fname).digest())
        r = int(r, 16)
        s = int(s, 16)
        sig = Signature(r, s)

        if self.pubkey.verifies(h, sig):
            return retrieve_file(fname)
        else:
            return 'Signature is not valid\n'

# ...

def retrieve_file(fname):
    try:
        dt = open(fname, 'rb').read()
        return dt.hex()
    except:
        return 'The file does not exist!'

Therefore, we might need to read subject_danbeer to get the flag. But we don’t have its signature! So, we must find a way to sign this filename in order to read it.

The server uses ECDSA with the ecdsa library under a wrapper class called ECDSA:

class ECDSA:
    def __init__(self):
        self.G = generator_256
        self.n = self.G.order()
        self.key = randint(1, self.n - 1)
        self.pubkey = Public_key(self.G, self.key * self.G)
        self.privkey = Private_key(self.pubkey, self.key)

    def sign(self, fname):
        h = sha1(fname).digest()
        nonce = randint(1, self.n - 1)
        sig = self.privkey.sign(bytes_to_long(h), nonce)
        return {"r": hex(sig.r)[2:], "s": hex(sig.s)[2:], "nonce": hex(nonce)[2:]}

    def verify(self, fname, r, s):
        h = bytes_to_long(sha1(fname).digest())
        r = int(r, 16)
        s = int(s, 16)
        sig = Signature(r, s)

        if self.pubkey.verifies(h, sig):
            return retrieve_file(fname)
        else:
            return 'Signature is not valid\n'


ecc = ECDSA()

Notice that the ecc variable is initialized when the program starts, not when a new connection arrives. Therefore, it doesn’t matter that the server closes the connection after 30 seconds, because we can simply reconnect and it will use the same ecc variable.

ECDSA

Basically, ECDSA signatures are a pair of values such that:

Where:

is the message to sign (fname)
is a hash function (SHA256)
is a randomly-chosen nonce
is the private key
is a generator point of the P-256 elliptic curve
is the order of the P-256 elliptic curve

Solution

This time, we are given additional information about nonces in init_storage:

def init_storage():
    i = 0
    for fname in fnames[:-1]:
        data = ecc.sign(fname)
        r, s = data['r'], data['s']
        nonce = data['nonce']
        nfname = fname.decode() + '_' + r + '_' + s + '_' + nonce[(14 + i):-14]
        nfnames.append(nfname)
        i += 2

Notice that we only have two known messages and signatures, so let’s write the equations we have (let ):

Normally, in this situation where we have partial information about nonces, we must use a lattice-based technique to find a solution for the above system of equations. Notice that we have 2 equations but 3 unknowns, so we can’t solve this directly.

If we read the code carefully, we are given nonce[(14 + i):-14], with i += 2; and nonce is an 256-bit integer in hexadecimal format. Therefore, we can say:

Where we have the value of and , and we know that and .

Failed ideas

When dealing with this situation (known as biased nonces), we need to transform the equations into a Hidden Number Problem (HNP).

The HNP is usually defined as:

Where is the hidden number, is bounded, and both and are known, given equations.

So, we can get an HNP expression as follows:

Alright, so let’s add the information we know about :

We will not be solving an exact version of the HNP because we have an additional unknown. However, we can still use a lattice-based technique to solve this.

First, we need to take care of , for this, we can add multiples of :

I’ve highlighted unknowns in red color and substituted:

At this point, we can write the above equations as a product of two matrices:

Since, the result is a zero vector, we can try to target a short vector that contains the information we want. For instance:

The above expression tells that the lattice spanned by the columns of the matrix contains a vector , which is short because there are a lot of short coordinates (i.e. , , ). Therefore, we can use an algorithm called LLL to reduce the lattice basis and see if it finds this short vector.

In order to improve LLL effectiveness, we can add an arbitrarily large weight to the column with , because we want to force LLL to use it only once. For instance, . So this will be the matrix to be LLL-reduced:

And the target vector will be .

I tried implementing this approach and it didn’t succeed. I modified the matrix a bit, using only one equation, combining both equations, increasing weights… and nothing. So I took a step back and tried something smarter.

Working idea

Let’s review the system of equations we have (with ):

What if we eliminate the variable ? This is a 256-bit integer, so it’s very large compared to and . We get this:

This equation is much better, because we only have and . We also need to add an extra variable because of , but it shouldn’t be a problem:

So, we can use the following lattice basis matrix:

And the target vector will be , which is much shorter!

The intended solution to this challenge was to find some resources that explain how to deal with partially-known information about ECDSA nonces. One of such resources is this paper, where they also employ the trick of eliminating the variable to unshorten the target vector.

Implementation

First of all, we connect to the remote instance and take the parameters needed for the attack:

io = remote(host, port)

io.sendlineafter(
    b'Options:\n1.List files\n2.Access a file\n',
    json.dumps({'option': 'list'}).encode()
)

files = json.loads(io.recvline().decode())['files']

values = files[0].split('_')
fname = '_'.join(values[:2])
r_1 = int(values[2], 16)
s_1 = int(values[3], 16)
b_1 = int(values[4], 16)
h_1 = int(sha1(fname.encode()).hexdigest(), 16)

values = files[1].split('_')
fname = '_'.join(values[:2])
r_2 = int(values[2], 16)
s_2 = int(values[3], 16)
b_2 = int(values[4], 16)
h_2 = int(sha1(fname.encode()).hexdigest(), 16)

Then, we define the lattice basis matrix:

A_1 = 2 ** 200 * s_1
A_2 = 2 ** 192 * s_2
B_1 = 2 ** 56 * s_1 * b_1 - h_1
B_2 = 2 ** 56 * s_2 * b_2 - h_2

n = generator_256.order()

W = 2 ** 1024

M = Matrix(ZZ, [
    [
        r_2 * A_1 % n,
        r_1 * A_2 % n,
        r_2 * s_1 % n,
        r_1 * s_2 % n,
        n,
        (r_2 * B_1 - r_1 * B_2) % n
    ],
    [1, 0, 0, 0, 0, 0],
    [0, 1, 0, 0, 0, 0],
    [0, 0, 1, 0, 0, 0],
    [0, 0, 0, 1, 0, 0],
    [0, 0, 0, 0, 1, 0],
    [0, 0, 0, 0, 0, W],
]).transpose()

Now we can apply LLL. It is important to reduce entries with % n, otherwise, they will be too big for LLL. Also, notice that we need to scale the matrix by to force LLL to find the desired solution (and then scale it back):

M[:, 0] *= W
L = M.LLL()
L[:, 0] /= W

If LLL is successful, the last row will be our target vector, so we can assert that the first element is and the last element is . Then, we can take the middle values , , and (we use absolute value to avoid negative integers):

row = L[-1]
assert row[0] == 0 and row[-1] == W

a_1 = int(abs(row[1]))
a_2 = int(abs(row[2]))
c_1 = int(abs(row[3]))
c_2 = int(abs(row[4]))

With these, we can reconstruct the nonces and , and easily find , just solving linear equations:

k_1 = 2 ** 200 * a_1 + 2 ** 56 * b_1 + c_1
k_2 = 2 ** 192 * a_2 + 2 ** 56 * b_2 + c_2

x = (s_1 * k_1 - h_1) * pow(r_1, -1, n) % n
assert x == (s_2 * k_2 - h_2) * pow(r_2, -1, n) % n

Once we have the private key, we can sign any message. So, we can sign subject_danbeer and read this file from the server:

k = 1337
fname = 'subject_danbeer'
h = int(sha1(fname.encode()).hexdigest(), 16)
r = int((k * generator_256).x())
s = pow(k, -1, n) * (h + x * r) % n

io.sendlineafter(
    b'Options:\n1.List files\n2.Access a file\n',
    json.dumps({'option': 'access', 'fname': fname, 'r': hex(r), 's': hex(s)}).encode()
)

data = bytes.fromhex(json.loads(io.recvline().decode())['data']).decode()
io.success(f'{fname}:\n{data}')

Flag

If we run the script against the remote instance, we will capture the flag:

$ python3 solve.py 94.237.54.190:39685
[+] Opening connection to 94.237.54.190 on port 39685: Done
[+] subject_danbeer:
    Test subject - Danbeer
    
    DEBUG_MSG - Starting Mind...
    
        What a life this is...
        I lost my only child.
        My home got destroyed by the army.
        They took everything from me and now I'm trapped inside a cloud server.
        I don't even know where my real body is.
        I remember the day that they captured me.
        It was 2 weeks after I lost my precious Klaus.
        I was in the Inn of the city, trying to find more information about the
        android graveyard planet.
        3 men jumped on me!
        I won't give up, I shouted!
        On the day that the suns of the Nim cluster are aligned, I will be there.
        Draeger won't wi...
    
    DEBUG_MSG - Shutting Down...
    
    Notes:
        The subject seems to be rebellious and dangerous for android usage
        HTB{m@st3r1ng_LLL_1s_n0t_3@sy_TODO}
[*] Closed connection to 94.237.54.190 port 39685

The full script can be found in here: solve.py.