| tags:Crypto categories:writeups series:Boston Key Party 2015

# Boston Key Party 2015 - Airport (Crypto 500)

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!

(*) 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