Rubis
Description
Hello C-Team,
During our investigation of Omniflags, we came across a cluster of ships called Rubis that was used to store top-secret information randomly in one of the ships and would rotate this secret every few days to stop attackers from finding the secret. It has been long since Rubric was deprecated however, we found out Rubis still contains a key component that will assist in the rescue of the prisoners from the space prison. We managed to get the source code that was used to run Rubis and for better or for worse, Rubis is still running at
<ip>:<port>
. We need you to unlock the ship that contains the flag so we can save the prisoners.Godspeed, HQ
Ship Ahoy!
Connecting to the server, we have a few options:
What would you like to do?
1. Get previous ships
2. Get public certificate
3. Get password hint
4. Unlock a ship
Prints out 5 seemingly random numbers
Prints out
n
ande
Prints out a hex string
Asks for a ship number and password, unlocks the ship if the password is correct
We are also given a challenge.py
file which consists of the code running this server, so let's check it out
First, we have an RSA
class, which I annotated with ###
class RSA():
def __init__(self, key_length): ### Takes in the key length
self.e = 0x10001 ### e initialized to 65537
phi = 0
prime_length = key_length // 2
### Regenerate primes while gcd(e, phi) != 1
while GCD(self.e, phi) != 1:
x = getRandomNBitInteger(prime_length) ### Random x
self.p = nextprime(x) ### p is the next prime after x
self.q = prevprime(x) ### q is the previous prime before x
phi = (self.p - 1) * (self.q - 1) ### Define phi = (p - 1)(q - 1)
self.n = self.p * self.q ### Initialize n = pq
self.d = inverse(self.e, phi) ### d = e^(-1) mod phi
def encrypt(self, message):
message = bytes_to_long(message)
return pow(message, self.e, self.n) ### c = m^e mod n
def decrypt(self, encrypted_message):
message = pow(encrypted_message, self.d, self.n) ### m = c^d mod n
return long_to_bytes(message)
For the most part, __init__
describes the initialization of RSA, two large primes p
and q
, an integer e
such that gcd(e, phi) = 1
where phi = (p - 1)(q - 1)
, n = pq
, and the secret key d
is the inverse of e
in modular n
Encryption and decryption follow the same steps as normal RSA
What's peculiar is that instead of randomly generating p
,q
first, e
is initialized and p
,q
are chosen until they satisfy the GCD requirement. Also, the two primes are not truly randomly generated, as they are both dependent on x
and thus are relatively close primes. This means n
is likely easy to factor
Secondly, there is a Ship
class, which is straightforward
class Ship():
### Ships have a password and data
def __init__(self, password, data):
self.password = password
self.data = data
Finally, we have a Cluster
class
class Cluster():
def __init__(self, rsa, password, flag):
self.rsa = rsa ### Initialize RSA with the RSA class
self.ships = {} ### Empty ships
for i in range(1000000):
### Initialize 1000000 ships
### Each ship has password "pa$$w0rd" and data "Nothing to see here :( Better luck next time!"
self.ships[i] = Ship(b"pa$$w0rd", b"Nothing to see here :( Better luck next time!")
self.prevShips = [] ### Previous ships are empty
self.currentShip = 0 ### Current ship is at index 0
random.seed(round(time.time())) ### Set a random seed
self.masterPassword = password ### Set the password
self.setCurrentShip() ### Initialize previous ship and current ship
self.populateSpecialShip(password, flag) ### Set current ship to the password and flag
def setCurrentShip(self):
### Initialize previous ships to random values between 1 and 1000000
for i in range(5):
self.prevShips.append(random.randrange(1000000))
### Initialize current ship to the next random value between 1 and 1000000
self.currentShip = random.randrange(1000000)
def populateSpecialShip(self, password, flag):
self.ships[self.currentShip].password = password
self.ships[self.currentShip].data = flag
From this, we make a few observations
All ships, except for the current ship, has password
pa$$w0rd
and dataNothing to see here :( Better luck next time!
The current ship is the "special ship" we want, with a password we don't know and the data is the flag!
The previous ships are 5 randomly generated values from 1 to 1000000 generated before generating the value for the current ship
We also have some class functions, which corresponds to the input options we have on the server
def getPrevShips(self):
return self.prevShips ### Returns previous ships
This is called by input 1. Get previous ships
def getPasswordHint(self):
return hex(self.rsa.encrypt(self.masterPassword))
This is called by input 3. Get password hint
It encrypts the master password with RSA then turns it into a hex string
def unlockShip(self, ship, password):
if (ship < 0 or ship > 1000000):
print(f"No ship exists with id: {ship}")
exit(1)
elif (self.ships[ship].password == password):
print(
f"You've managed to unlock ship {ship}! Here's what's inside: \n{self.ships[ship].data.decode()}")
else:
print("Err... couldn't open the ship! Maybe next time...\n")
exit(1)
This is called by input 4. Unlock a ship
It checks if the password is same as the ship's password, then prints the data if it is
It exists if we fail to open the ship, so it is not possible to brute force
Now we have all the information we need, let's try to get the flag!
Note - Be careful when restarting the session, as the RSA values and previous ships are randomly generated on bootup and will be different each time. If we need to restart, we'll need to go through all the steps again!
We will need the password, so let's get that. Start a session than choose option 2 to get the value of n
and e
. If we want to decrypt the password, we need the secret key d
Let's try factoring n
to get p
and q
It runs pretty fast due to the poor generation of p
and q
We can then calculate phi = (p - 1)(q - 1)
and d = e^(-1) mod phi
from Crypto.Util.number import inverse
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
Now we have the secret key for RSA, so let's get the password hint with input 3. Since it's a hex string, we need to convert it to its numerical value
from Crypto.Util.number import long_to_bytes
hex = '{PASSWORD HINT}'
enc = int(hex, 0) ### Convert into number
key = pow(enc, d, n) ### Decrypt the password
print(long_to_bytes(key))
We get that the password is f32m47'5_f4c702124710n_m37h0d_f02_7h3_w1n!!
So we have the password, now we need to find the special ship to get the flag. How will we do that? Aren't the ships randomly generated? Also unlockShip
will call exit(1)
if we fail to unlock a ship, so we can't try them all until our password works :(
Now I had to think what option 1. Get the previous ships meant, since it was the only one we haven't used yet. It seemingly has nothing to do with the current ship as it is randomly and independently generating numbers for the previous ship, then the current ship. At least, in theory...
Consider random.seed(round(time.time()))
This sets a seed, but what does that mean? In reality, there is no such thing as true random. For the most part we use pseudorandom generators, which are a sequence of seemingly random numbers. For any one seed, there is a different sequence of numbers
But if we have the same seed, we will have the exact same sequence of numbers. This is why you need to change seeds on every use
We can try to exploit this fact and try to get the same seed that the server uses on bootup. Check the time when you run the server and keep track of it. Then, get the previous ships. We will compare different times as seeds until the first 5 numbers match the previous ships:
import random, time
time = 1677361020 ### Roughly the time I ran the server
targets = [862117, 375147, 59052, 38858, 261625] ### Previous ships
while True:
accept = True
random.seed(time)
for i in range(5): ### Check if the first 5 numbers are the same
temp = random.randrange(1000000)
if temp != targets[i]:
accept = False
break
if accept:
print(time)
random.seed(time)
for i in range(5):
print(random.randrange(1000000))
break
time = time + 1 ### Test all possible times until it works
print("\n")
random.seed(time)
for i in range(6):
print(random.randrange(1000000)) ### Get the 6th number
Now we have the 6th number generated by the seed, which must be our current ship! Select option 4, then pass in the ship number and the password to get the flag
Flag
magpie{17_w45n'7_72u1y_24nd0m_4f732_411}
Last updated