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