On 2020-04-17 I participated as part of the USS in PlaidCTF.
As usual thanks to the
organizers and sponsors for putting together such nice challenges.
As usual in CTFs there were a bunch of challenges and if you solved
one correctly, a special flag in form of a binary string appears from
somewhere. This flag can be submitted in the web-interface and your
team gets points.
The USS team made the 134th place among the 541 participants, even
though we solved only one challenge.
This post contains my writeup of the challenge xorsa. If you want to
play around with the challenge, you can find it
If you want to read other writeups, go
flag.enc: From the sage file and the file name it is suggested, that
this is the encrypted flag.
Below is the content of the sage file.
This is very similar to the usual setup for RSA.
We have unknown prime numbers p, q. There is a modulus n=pq.
We have the public part of the key e = 65537 and the secret part d
such that ed = 1 mod (p-1)(q-1).
If we could factorize n and get to know p and q, we could compute the
OAEP is used for padding, which is also fairly standard.
The suspicious part that screams “look at me” is that p^^q == x and x
is known. After reading previous discussions of my teammate I learned
that ^^ is sage syntax for the xor operation.
So maybe it is possible to factor n, as we know x.
I simply googled this and found clever people who already solved this
The idea is that we first look at the i least significant bits (i.e.,
mod 2**i) start with i=1 and factorize there.
This gives us the lowest bits of each, p and q.
Then we increase i. As we know the xor,
we only have two more possibilities for the next bit of p to test.
We repeat this, until i covers teh whole number.
In the linked stackexchange discussion, there is a link to a github
repo, where someone has
already implemented this.
The next steps are thus as follows:
Extract n from the RSA public key.
Factorize n using the knowledge of x and the github code.
Decrypt the encrypted flag.
Extracting n from the RSA public key
If you know the commands, this is fairly straightforward.
Running the following code shows n.
Take the code from here and
invoke it like this: ./xorfactor n x, where you have to substitute n
and x with the correct values.
Decrypting the flag
Now that we have all the components together, all that remains is
creating the private key and decrypting the flag.
For this, I was able to reuse some of the initial challenge code.
Note the assertion that p*q == n. Stuff like this is very important
for debugging when it would not have worked.