Firmware update - 34C3 CTF solution I saw this recently published riddle and its solution in
this link.
My mathematical background is not so strong. Is it possible that someone here to solve the riddle? My background in math is not strong.
I understand that there is some problem in that they repeatedly XOR each (file_name + '\0' + file_content) with the prev. (file_name + '\0' + file_content), and only then use it for authentication against the asymmetric signature.
I understand that our goal is somehow to zeroed our added files hash by XOR with some calculated unique file names, but I do not know how to do it without weakness in the hash algorithm itself.
Please explain the solution in simplest possible way (but at the same time I want to understand exactly what the weakness here is and what exactly is the solution).
The relevant mathematics is elementary linear algebra.

Focusing on the relevant part of the problem, the defender calculates a signature
$$S(m_1, \ldots, m_n) = H(m_1) \oplus H(m_2) \oplus \ldots \oplus H(m_n)$$
where $\oplus$ is bitwise xor, $H$ is a cryptographic hash function and $(m_i)$ is a family of messages (which are file names) of variable size. The goal of the attacker is to find a family of messages such that:


The signature is equal to some value $S_o$ which is the signature of the legitimate message.
One of the messages has a specific content which is the payload that the attacker wants to inject.
No two messages can be equal, because there can only be a single file by a given name.


So we need to find $n$ and $m_1, \ldots, m_n$ such that
$$S_0 = H(m_0) \oplus H(m_1) \oplus H(m_2) \oplus \ldots \oplus H(m_n)$$
i.e.
$$H(m_1) \oplus H(m_2) \oplus \ldots \oplus H(m_n) = S_1$$
where $S_1 = S_0 \oplus H(m_0)$.

If $H$ was invertible, we'd just take $n=1$ and $m_1 = H^{-1}(S_1)$. But since $H$ is a cryptographic hash function, this approach is out. Nonetheless, let's look a bit more at what we could do if we could find messages whose hash has a specific value.

$H(m)$ is a 256-bit value. Suppose we could find 256 messages $(M_1,\ldots,M_{256})$ such that $H(M_i)$ is all-bit-zero except that the $i$th bit is set. Then we could take a subset of these messages corresponding to the bits that are set in $S_1$: $S_1 = \bigoplus_{i \mid \text{the \(i\)th bit of \(S_1\) is set}} H(M_i)$.

We're trying to express $S_1$ as the xor of a bunch of values. The xor operator is linear: it satisfies all the axioms that define a vector space over the field $GF(2) = \mathbb{Z}/2\mathbb{Z}$. In the field $GF(2)$, the elements are $0$ and $1$, the addition $\oplus$ satisfies $1 \oplus 1 = 0$ (i.e. it's xor) and three's only one way to define multiplication ($0$ times anything has to be $0$ and $1$ times anything has to be that thing). Bitwise xor on 256-bit numbers is vector addition in the vector space $GF(2)^{256}$. And expressing a vector as the result of adding a bunch of vectors is a well-studied problem: we're trying to express $S_1$ as a linear combination of some values.

Any value can be expressed as a linear combination of $100\ldots0$, $0100\ldots0$, $00100\ldots0$, …, $0\ldots010\ldots0$, …, $0\ldots01$. Picking the bits that are set in the resulting value means taking each term $0$ times if the corresponding bit in the result is clear and $1$ times if the corresponding bit is set. A set of vectors such that any value can be expressed as a linear combination is called a generator set of the vector space. A set of vectors such that none of them is a linear combination of the others is called linearly independent. A linearly independent generator is called a basis of the vector space.

If a vector space has a finite basis, then all of its bases have the same number of elements. This number is called the dimension of the vector space. Here we're working in a vector space with a 256-element basis, so it's a 256-dimensional space. The dimension has other nice properties, including the fact that in a vector space of dimension $d$, if a set of $d$ vectors is a generator then it's a basis, and if a set of $d$ vectors is linearly independent then it's a basis.

Recall that our problem is to find a way to express $S_1$ as a linear combination of some vectors. Furthermore each vector must be the hash of some message. We can do that by:


Finding a basis made of vectors that are the hashes of known messages.
Expressing $S_1$ as a linear combination of this basis.


For part 1, recall that it is enough to find 256 hashes that are linearly independent: since the vector space has dimension 256, such a set of 256 hashes will be a basis. $H$ is a cryptographic hash function, so it behaves essentially at random. We can take any message, calculate its hash, and if we don't like the resulting hash then we take a different message and try again. We can construct 256 successive messages such that each new message's hash is not a linear combination of the previous ones. That is:


Take an arbitrary $m_1$. While $H(m_1) = 0$, change $m_1$ and try again.
Take an arbitrary $m_2$. While $H(m_2)$ is either $0$ or $H(m_1)$, change $m_2$ and try again.
Take an arbitrary $m_3$. While $H(m_3)$ is a linear combination of $\{H(m_1),H(m_2)\}$, change $m_3$ and try again.
Take an arbitrary $m_4$, etc.


After building $k$ messages $(m_1,\ldots,m_k)$, there are $2^k$ hashes that are linear combinations of the hashes of those messages. This means that the number of forbidden hash values at each step is $2^0$, $2^1$, $2^2$, etc. At the 256th and last step (i.e. after building 255 messages), the number of forbidden hash values is $2^{255}$, which is half of the total number of possible hash values. This means that the probability of a successful draw is $1/2 = 1-1/2$ for each attempt at the last stage, $1-1/4$ at the previous stage, $1-1/8$ at the stage before, etc. Note that the probability of success is always at least one half, so this randomized algorithm is practical, it won't get stuck trying to find something that's almost impossible to find.

Part 2 is a classical problem in linear algebra which led to the definition of multiplication of matrices. We saw above how to express any vector as a linear combination in the basis made from vectors with all-bits-zero-except-one. We now want to express the old basis in terms of the new one, i.e. to express each all-bits-zero-except-one vector as a linear combination of the new basis. This means finding the inverse of the matrix that expresses the new basis in terms of the old one, which is equivalent to solving a system of 256 linear equations (one for each bit position) with 256 unknowns (the coefficient of each vector in the basis).