# ångstromCTF 2020 - RSA-OTP Writeup

For this challenge we are provided with the server source:

1 | from Crypto.Util.number import bytes_to_long |

At the beginning I was a little bit confused by the comments: usually when something is pointed to as secure, it is what you have to break; unfortunately not this time. So I spent some hours trying to factorize `otp`

function.

Then I tried to modify one of our attempt to break `otp`

: in fact it is an oracle and in particular it leaks the lenght of the decrypted message.

The first thing to notice is that if we send to the server

- if
is even, then the second response is exactly one bit shorter then the first one - if
is odd, the lengths of the first and second response are uncorrelated

Don’t worry, we can still recover our flag: in fact

We are working modulo

We can extend the reasoning to more than one bit. Let’s construct

- send to the server the encrypted flag (let’s call it
) and call the bit length of the response - send to the server
and call the bit length of the response - if
is equal to , then prepend a 0 to , otherwise a (we are interpreting in binary) - repeat these steps enough (we need
bits)

We can now notice that after

That’s all: we can recover all the bits of `actf{this_is_not_what_i_meant_when_i_told_you_to_use_rsa_with_padding}`

.