Inputs
For this problem, we are given the source code of an authenticated service. We have to login by providing a password, which is then concatenated to a salt, hashed with SHA256, and truncated to 48 bits. The server checks if the hash is correct, using a timing-proof algorithm (the two values are XORed, then all the bits of the result are combined with bitwise OR.
Countrary to usual attack scenarios, the actual salt is hidden from us. However, if the login fails, a stale debugging statement informs us of the difference between the stored hash and the computed hash (though because we do not know the salt, we cannot a priori make use of this information, as we do not know how to compute the hash.)
Vulnerability
The XOR implementation used for the timing-safe comparison is destructive (the first operand is replaced with the result of the XOR.) Furthermore, the order of arguments is reversed when testing the password: instead of overwriting the temporary computed hash, it overwrites the stored hash, which persists across login attempts from the same session (but not across connections - the connection handler loads the stored hash from a file before starting its main loop.)
Formally, a connection starts with a stored hash , and for every new submitted password , the stored hash gets replaced by a new value
Solution
The first step is to recover the stored hash. If we submit the same password twice, we get to observe
Once the original hash is observed, the problem reduces to finding a sequence of passwords such that
Because XOR is a linear operation, we know that we can solve this problem for any by finding an orthogonal basis for our vector space. That is, as the hash is 48 bits long, we need to find, for every bit position, a sequence of passwords that hashes to all zeros except in this specific position. Once this is determined, we can get to any hash value by combining the basis vectors for the bits we want.
There is an easier way, though. It is enough for us to find a basis such as the -th vector has a 1 in the i-th bit position, and a 0 in all the previous bit positions. This corresponds to reducing a matrix to upper triangular form. Once we have this basis, we can apply (or not) each of the basis vectors in turn, dynamically adapting to the new result.
We need 48 basis vectors to spawn our 48-dimension output hash. We will use more random vectors, to lower the probability that our random vector set would accidentally be linearily dependant (and thus not a basis)
The solution is thus as such:
- Connect to the service 100 times, submitting different passwords like dummy00, dummy01, dummy02, etc...
- For each password, observe the hash difference, and deduce the actual computed hash (because the original stored hash is known)
- Generate a matrix of bits containing the hashes outputs. This matrix has 100 lines (one per hash) and 48 columns (one per hash bit)
- Adjunct an identity matrix to this one, then make the left part into an upper triangular matrix, by doing the following for each row:
- For every bit before the i-th, check if it is 0. If not, xor with the i-th matrix row to make it 0.
- Ensure that the row has a 1 in its i-th position (if not, drop the row or exchange it with a lower one)
- Select all the rows corresponding to the 1 bits of the target hash, and xor them together. The 100 rightmost bits (where the identity matrix used to live) indicate which passwords from the random set, xored together, generate the target hash
