expohash

Fishy is trying to hack into a secret government website again!!!

They learned from fishy’s attempts last year, so they created a password of 10^5 integers, and each integer x in the password satisfies 0 <= x <= 2^31. However, this password was too long for them to check, so they made up a method that they hoped was quicker. They included 10^5 tests that the password checker will do.

In each test, the computer checks from some left bound L to some right bound R, where 1 <= L <= R <= 10^5. The computer takes the xor of each value in the range L to R inclusive of the password and checks if that equals the expected value V. Fishy has found the the values for L, R, V for each test, but he needs your help to find a valid password. Can you help him?

You will be given the L, R, and V values for each test, and each test will be on their own line. For example, the first few tests could look something like:

1 4 6 5 12 9 574 990 743485 …

Print back the values in the array, each separated by a newline

nc 2020.redpwnc.tf 31458

Solution

The gist of the problem is this: we have an array of 10^5^ integers and the XOR values of 10^5^ ranges in the array, and we’re required to reconstruct the array using this information. While this question might seem a bit abstract when thought of in terms of ranges, as each range may be of a different size, it’s easier to form an idea about what to do if we treat the XOR value of each range as the XOR of two prefix XOR values.

To make this clear, first, let’s take the array to be 1-indexed and let’s call it arr. Let pref[i] = arr[0] ^ arr[1] ^ ... ^ arr[i] for 0 ≤ i ≤ 10^5^ (let pref[0] = 0). The XOR of the range between L and R is arr[L] ^ arr[L+1] ^ ... ^ arr[R-1] ^ arr[R]. From the definition of pref[i], we can rewrite this as pref[R] ^ pref[L-1]. Thus, we can approach the problem as follows: we’ve been given XOR values of 10^5^ pairs of values from the pref array and we need to reconstruct pref from them. Then, we can find arr using the relation arr[i] = pref[i] ^ pref[i-1].

We can think of each element in pref as a node in a graph. There is an edge between two nodes in this graph if we know the XOR of the pref values corresponding to the nodes, and the weight of the edge is this XOR value. We can start a depth-first search (DFS) from pref[0] and calculate the pref values of all the nodes in its connected component using this basic idea: if we know the pref value corresponding to a node (let this value be x), we can calculate the pref value of a node attached to it via an edge with weight w as x ^ w. We apply this recursively until no more pref values can be assigned in this manner. If there are still unassigned nodes, we randomly set the pref value of some unassigned node to 0 and repeat this process. Once we have the pref values, we can easily calculate the arr values as mentioned above. Giving a valid set of values for arr (there may be several valid arrs possible) will get you the flag.

Program

expohash.cpp

Flag

flag{1_g0t_th3_c0mb_thx}