HackTheBox Challenge: Infinite Decent

This challenge was a lot of fun and the highest ranked (in terms of difficulty) one I've completed. It begins with two python scripts and an email, containing an RSA public key and messaged encrypted by the corresponding private key.

Not gonna lie, reading this made me feel like a real 1337 hacker, was pretty great

So lets break this email down. This company uses a typical secure communication system wherein a shared secret is sent via one time RSA key pairs, which is then used as the seed of a random number generator (a mersenne twister is a common pseudo-random number generator). This random number generator provides the shared key in future communications encrypted and decrypted with AES.

When you create an RSA key pair, you need two very large prime numbers sufficiently apart from each other. Generating these can take a long amount of time, so what this developer has done is generate the first prime in the standard way, then rather than doing the same again for the second prime has simply started counting in either direction until another large prime is found, as can be seen in the provided script fasterprimes.py:

 

So the main vulnerability here is that the generated primes in the public key are very close. This means we can easily factor the modulus 'n' value provided in the public key. There are two options - Fermat's factoring algorithm, or the much simpler approach of just taking the square root of n and then counting up and down until two primes that multiply to give the original modulus are found. Writing up a script for this is very simple and can be soon below:

An important thing to take into account though is that as we're dealing with very large numbers we can't treat them like normal using standard python int types, as this would result in a loss of precision at the least significant bits, throwing off our results. Instead we have to use a wrapper for the general multi-precision library called gmpy and keep our numbers as 'mpz' types, such that they'll remain accurate after carrying out operations on them. Lets run our script and see our results:

So now we have our RSA prime numbers, time to reconstruct the private key and decrypt our message, conveniently given in integer form already. This can again be done with a very basic script that uses the Euclidean algorithm for finding greatest common divisors such that we can directly obtain the private exponent d.

Saving the output into a file 'presharedkey' we get:

So, just a simple integer. Lets take a look at the 'AESBootStrap.py' script to see if there are any hints on how we might use this:

 

Left out is a standard mersenne twister, as implemented on wikipedia. It seems pretty obvious then that we're to take this number and use each triplet of digits as seed values for the random number generator. In this implementation each output from the generator is and'd against the hex 0xFF, or '11111111', so only the first 8 bits are included.

So our output for the AES key is a series of integers, each within a single byte. Converting to ASCII seems like the obvious route from here.

They're really making us work for this one aren't they? Lets convert from base64...

And there we have it! Our flag, finally. This was an incredibly fun challenge that I really enjoyed doing, so props to the creator.