# Software Update @ 34C3

> Source: https://rot256.dev/post/software-update/
> Author: Mathias Hall-Andersen
> Date: 2017-12-30
> Tags: CCC, CTF, Sage
> License: CC BY 4.0 — reuse permitted with attribution to Mathias Hall-Andersen (rot256.dev).

Math macros in scope (KaTeX, `\name = expansion`):

```text
\Div = \mathrm{Div}
\FF = \mathbb{F}
\GG = \mathbb{G}
\NN = \mathbb{N}
\Norm = \mathrm{N}
\PRF = \mathsf{PRF}
\RR = \mathbb{R}
\Tr = \mathrm{Tr}
\ZZ = \mathbb{Z}
\adv = \mathscr{A}
\bin = \{0, 1\}
\coloneqq = \mathrel{\mathop:}=
\defeq = \coloneqq
\deg = \text{deg}
\divides =  \ | \ 
\gcd = \text{gcd}
\hash = \mathsf{H}
\img = \text{img}
\ker = \text{ker}
\language = \mathcal{L}
\lc = \mathrm{lc}
\lcm = \text{lcm}
\msg = \mathsf{msg}
\negl = \text{negl}(\lambda)
\pk = \mathsf{pk}
\prob = \mathbb{P}
\sample = \overset{\$}{\gets}
\secpar = \lambda
\sig = \sigma
\sign = \mathsf{Sign}
\sk = \mathsf{sk}
\support = \mathrm{Supp}
\tensor = \otimes
\verify = \mathsf{Verify}
```


# 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:

```text
.
├── 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:

```python
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:

```python
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}$.

```python
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:

```text
[*] 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](https://github.com/rot256/Wargames/tree/master/ccc/software_update)

Thanks to the [Eat, Sleep, Pwn, Repeat](https://ctftime.org/team/15712) team for a wonderful CTF (as always).