This challenge consists in a Python server that receives a number as input, exponentiate it to a secret number modulo a prime and if the result is equal to 4 we get the flag. The exponentiation is done using the square&multiply algorithm and when the accumulator is equal to 4 the server “sleeps” for 1 second. This of course leads to some kind of timing attack.

First thing to notice is that if we know the secret the problem gets easy: we can compute our input as _pow(4, mod_invert(secret, p-1), p) _(*). If we compute this result to the power of secret we obtain 4. So how to get the secret? We can use the same observation from above and the fact that square&multiply is used. In fact this algorithm processes the exponent bit by bit, so two different exponents that have the first N bits equal will lead to the same internal result as long as the equal bits are processed, afterwards the execution will diverge. How can we exploit this? If we have a guess for the first bits of the secret we can send pow(4, mod_invert(guess, p-1), p). Then, if our guess is correct, after the Nth bit of secret is processed (where N is the length of guess), the internal state of the algorithm will be equal to 4 and the server will “sleep”.

We know that the first bit is set to 1, so our first guess can be 11 (**) (in binary). We send pow(4, mod_invert(0b11, p-1), p) and if the server sleeps it means that our guess was correct. Let’s say it didn’t, so the second bit is zero. Now we go on and we send pow(4, mod_invert(0b101, p-1), p), again if it sleeps the third bit of the secret is one, zero otherwise.

This script automates the process. I did not bother to write it in a nice way and implement more functionality to also send the right value to get the key but it allows to retrieve the secret (that does not change between connections). I believe that once the secret is known it’s straightforward to also send the input to get the flag.

Thanks to the organizers for this awesome CTF!

fox

(*) The careful reader would notice that this works only if the secret is invertible in p-1, luckily this was the case.

(**) 10 (in binary) would not be a good choice as p-1 is even and thus it would not be invertible