Rotten Secured Algorithm is the only challenge that I have written for Firebird Intro CTF. Two people (out of 166) ended up solving the challenge.

There is a Python script attached in the challenge, as well as the output file. Let's see what's going on in the Python:

# Challenge written on Aug 26, 2020 by Mystiz.

from Crypto.PublicKey import RSA
import random
import time
from datetime import datetime
from secret import flag

t = int(time.time())

assert len(flag) < 256

k = RSA.generate(1024)

p, q = k.p, k.q

n = p * q
e = random.randrange(2**1024) * (p-1) * (q-1) + 1

m = f'''
This message is encrypted on {datetime.fromtimestamp(t)}.
I have crafted the public key - it is so secure that no one is able to recover this message ever.
But wait, you said you did? Then take this flag - {flag} and get away. I mean congrulations!
'''.strip().encode()

m = int.from_bytes(m, 'big')
c = pow(m, e, n)

print('n =', hex(n))
print('e =', hex(e))
print('c =', hex(c))

Okay. So there are few points worth noticing:

  1. It is encrypting a message under RSA, under a strangely generated $e$ (Normally $e$ would be 65537).
  2. The message contains so much known junk spoken by the challenge author (i.e., me). There are two unknowns however, namely the time and the flag.
  3. The challenge is written on August 26, 2020.
  4. There is a spelling mistake in the message. It should be congratulations.

Exploiting the spelling mistake⌗

Well I think I've received so much bug reports regarding the last point (i.e., the spelling mistake):

Actually I want to say when I saw this q at the first, you're having typo of congratulations ~ hoifanrd

Yes. This is a bug. And no, it is not exploitable.

W$e$ird?⌗

Since the encryption exponent is so weird, let's see what is going on with that $e$. A random number $k$ is generated, then $e := k(p-1)(q-1) + 1$. Weird? Weird!

If you are familiar with RSA, you may notice that $(p-1)(q-1)$ is actually used in the normal case (Reference: Wikipedia). This number is, in particular, the reason why RSA works. This is actually the Euler's totient of $n := pq$. From Euler's theorem, for any $m$ that is coprime with $n$, we have \(m^{\phi(n)}\equiv 1\ (\text{mod}\ n).\)

That said, $m^{(p-1)(q-1)}\equiv 1\ (\text{mod}\ pq).$ Hence, if it is encrypted in the way stated by the Python script, it would be:

\[c \equiv m^{k(p-1)(q-1)+1} \equiv (m^{(p-1)(q-1)})^k\cdot m \equiv 1^k\cdot m \equiv m\ (\text{mod}\ n).\]

And yes - the ciphertext is actually the plaintext (under modulo $m$). This may reflected from the experiments some of you conducted. If $m$ is small, we can easily find it from the ciphertext.

Image credit from TWY(TM).

Yes. the reason $e$ is here is to behave as a red herring. Thank you for your attention.

Exhausting the time⌗

And now we have the relation that $m \equiv c\ (\text{mod}\ n)$. There would be many possibilities: $m = c$, $m = c+n$, $m = c+2n$, .... If you try them one by one, good luck.

Before recovering the message $m$, let's see how is the message being constructed:

m = f'''
This message is encrypted on {datetime.fromtimestamp(t)}.
I have crafted the public key - it is so secure that no one is able to recover this message ever.
But wait, you said you did? Then take this flag - {flag} and get away. I mean congrulations!
'''.strip().encode()

We have known that the length of the flag is shorter than 256 (Honestly you can only solve the ones with length shorter than 128. This is my bug.). And datetime.fromtimestamp(t) has a very specific format like 2020-09-21 15:47:49. What can we do?

Theoretically, there is an algorithm called LLL (Lenstra-Lenstra-Lovasz) that is able to find solutions in a given lattice space. You could do that with this particular algorithm, but it is too advanced for me (and for Cousin maybe). So use this next time.

From the fact that the challenge is written on August 26, we assume that datetime.fromtimestamp(t) == '2020-08-26 XX:XX:XX' (Hereby the X's are some unknowns). We can simply exhaust them from 00:00:00 to 23:59:59 (you can even do it better if you are familiar if you know the hours when I am awake). The number of unknowns will be reduced to one (i.e. the flag) if you can exhaust the time.

Building an equation for the flag⌗

Consider an oversimplified question: if the flag is actually empty, what will happen?

The answer is simple. The message would be:

This message is encrypted on 2020-08-26 XX:XX:XX.
I have crafted the public key - it is so secure that no one is able to recover this message ever.
But wait, you said you did? Then take this flag -  and get away. I mean congrulations!

When converted to an integer (suppose that the time is really XX:XX:XX but not the actual one), it will be:

111248663542485736107250227974426013508583933776109722990494951955869643865085766128037408566272079682265560188238495576887647937838386527644916125289689416278118827241320779801619838335804717580911731281367515940649917152582252528274393473425137994288149900060945962282660291806279495325384766649404408091927920917263453285767966612073096911168387141245249711982237414649323433359135300425008775820354827731945921592891386243185082414719634127857865697060215684219773073280308125162213590874254658642402741061947455536121831844020354136129599385073360725378757409

Does it sound meaningless to you? It sound meaningless to me, too. But what if the length of the flag is one? Let $x$ be the flag that is converted into an integer. We have the following equation:

# m_prefix is the integer representation of "This message is encrypted... take this flag - "
m_prefix = 0x54686973206d65737361676520697320656e63727970746564206f6e20323032302d30382d32362058583a58583a58582e0a492068617665206372616674656420746865207075626c6963206b6579202d20697420697320736f207365637572652074686174206e6f206f6e652069732061626c6520746f207265636f7665722074686973206d65737361676520657665722e0a42757420776169742c20796f75207361696420796f75206469643f205468656e2074616b65207468697320666c6167202d20 
# m_suffix is the integer representation of " and get away. I mean congrulations!"
m_suffix = 0x20616e642067657420617761792e2049206d65616e20636f6e6772756c6174696f6e7321

# The equation. The left hand side is the message modulo n.
assert (m_suffix + 256**36 * x + 256**37 * m_prefix) % n == c

One can solve the equation by moving everything to the right, except $x$:

\[x \equiv 256^{-36}(c - m_\text{suffix} - 256^{37} m_\text{prefix})\ (\text{mod}\ n).\]

But the length of flag is not necessarily one. In this case, you can simply replace $256^{37}$ by something else (indeed $256^{36+\text{length}}$). By iterating the length, you should be able to compute a correct $x$ - hence the flag!

This is the final exploit script for the challenge:

# import the libraries yourselves

# plug them in yourselves
n = ...
c = ...

for h in range(24):
  for m in range(60):
    for s in range(60):
      for l in range(256):
        # plug h, m, s into m_prefix yourselves
        m_prefix = int.from_bytes('This message is encrypted...', 'big')
        m_suffix = int.from_bytes(' and get away...', 'big')
        
        x = powmod(256, -36, n) * (c - m_suffix - powmod(256, 36+l, n) * m_prefix) % n
        print(int.to_bytes(x, length=(x.bit_length() + 7)//8, byteorder='big'))

Although it looks like it is written in Python, I have only the rough idea implemented. The rest is left as exercise 😄. Very easy, right?

Finally, since $n$ is only 1024 bits long, I got to claim that the length of the flag should be shorter than 128 for this method to work. Asserting that the length shorter than 256 was my unintentional typo (along with the spelling mistake).

So that's it. Bye.