# Software-update -- 34C3CTF

# Software-update

**by mandlebro, l0rdc0mm4nd3r, goulov and jofra**

## General description

This challenge has a service that accepts a zip file and if the signature inside is a valid RSA PSS signature of the Xor of the hash of the files and folders inside, it runs two python scripts.

## TLDR:

- since we can include an arbitrary number of files, we can find a set of 256
`sha256`

hashes which are a basis for \(\mathbb{Z}_2^{256}\). - change the python files in a way that it runs system and prints the flag.
- compute the hash of the new zip, \(h_{new}\), and find which set of files \(I\) of the basis to include in order that \(h_{new} \oplus \bigoplus_{i\in I} sha256(i) = h_{orig}\). This will pass the check for validity and get your flag.

## Too short, pls explain

The code is not that short and some potential attack vectors were explored:

- when computing the hash of the file tree, the code is (basically)
`for f in files: if os.path.isfile(f): h = ...# compute hash elif os.path.isdir(f): h = ...# compute hash else: pass result = xor(result, h)`

so, if we could find a type of file that would not be a file or a dir (in the eyes of

`os.path`

) we would go through the pass option of the`if`

, and so we would perform the xor with a previous`h`

, thus effectively removing it. We spent some time on this but without success. -
hidden files were ignored in the hash computation (not even listed in the previous filename list so we could not use the pass vulnerability), however we could not exploit this in any way as well.

- finally, we noticed that we can have full control of the computed hash since we can upload any number of files (as long as we dont exceed some size). Thus, we can potentially find a set of hashes whose
`xor`

combinations generate all other hashes.

## The attack

We now need to find this set of 256 hashes that generate all other hashes through their combination. This can be described by finding a basis for the matrix space of size 256 over \(\mathbb{Z}_2\). We run the following until we obtain a basis of size 256:

- randomly generate a hash
- add it to the basis
- if the dimension of the new basis increases, add it, else discard it.

This can easily be performed in `sage`

:

```
def genbasis():
V = VectorSpace(GF(2), 256)
fn, b = genrandhash()
fnames = [fn]
basis = [b]
S = V.subspace(basis)
dim = S.dimension()
while dim != 256:
fn, b = genrandhash()
new = V.subspace(basis+[b])
dim_new = new.dimension()
if dim < dim_new:
# we got a useful vector, lets add it
fnames += [fn]
basis += [b]
dim = dim_new
return fnames, basis
```

We now have our basis \(B\) for the full hash space, and so, if we want to generate a set of files that hash to \(h\) we only need to find the combination of elements of the basis that `xor`

to \(h\):
\(B\cdot x = h\)
We now only need to invert \(B\) and obtain \(x\):
\(x=B^{-1} h\)
With this we obtain a way to find a set of hashes that hash to any value we want.

Now, we need to:

- change our the loaded
`pre-copy.py`

script, for instance as:`import os print(os.system('find / -iname flag')) print(os.system('cat *')) print(os.system('grep -r "34C3_"')) print(os.system('cat /flag')) print('STT is are nice')`

- compute the new hash of the zip tree, \(h_{new}\)
- find the set of files \(I\) such that \(h_{real} = h_{new} \oplus \bigoplus_{i\in I} sha256(i)\)
- submit the new zipped file and get the flag!

gg ESPR