category : crypto
points : 135
solves : 36
Binary search on if secret.startswith(b"OOO{"):
This challenge is about secret sharing scheme
reconstitute_secret takes out 5 rows from the matrix according to the index in the provided shares. Then inverse the matrix and dot product the first row with the shares to get the secret. Since we only cares about secret, other rows in inverse matrix is not important. In other words, reconstitute_secret takes 5 shares and dot product with a vector of size 5. Just like this a_1 * s_1 + a_2 * s_2 + a_3 * s_3 + a_4 * s_4 + a_5 * s_5. All operation is done under modulus P.
redeem_actual_flag will decrypted the actual flag from 3 shares we provided and 2 shares in the server and check that it starts with "OOO{". That sounds like some oracle attack!!! Assume the shares we provided is s_3, s_4, s_5. Instead of s_5, we use s_5 + x * a_5^-1 with arbitrary x to feed to oracle. We will get flag + x. flag is stored in little endian, so "OOO{" is in the lower bits. Making an arbitrary x << 32 and observe that how big the value of x << 32 will make flag + (x << 32) overflow to be modulus by P and invalid the check. That means binary search for the smallest x such that flag + (x << 32) >= P.
Next question is how do we get a_5. redeem_user_flag can do reconstitute and give us the actual value of secret. Set the values of shares to 0, 0, 0, 0, 1 to extract a_5.
Because the shares is being random shuffle, we also need know the index of the secret_id.1 and secret_id.2 in order to extract the same inverse matrix. This can be done by simply brute force these two index, which has only (100 - 1 - 2) * (100 - 1 - 2) possibilities. And test whether flag + (1 << 32) still valid.
OOO{ooo_c4nt_ke3p_secr3ts!}