HackTheBox – Infinite Descent

In this write-up we will be visiting the Infinite Descent challenge from HackTheBox.

DevOps have come up with a great way to choose primes for RSA and an even better way to established a key for AES.

Can you find the flaws?

Flag Format: HTB{flag}


We are given three files, email.msg, fasterprimes.py and AESbootstrap.py. The contents of the email.msg file is as follows.

From: CayceP <cayce.pollard@>
Sent: 11 August 2017 18:15
To: Deschain, Roland
Subject: Progress update

Hi Rolly,

Just a quick update. We've addressed your issues with the numpy PSNG by ditching it and created a mersenne twister from scratch.
This will be used as the pre-secret from the RSA exchange for bootstrapping the AES comms.

We have some problems with the RSA generator that we're ironing out. Security have some questions around the
way primes are chosen but I think they're just getting in the way. To prove it's working just fine I've sent your
private key through secure comms and your public key is below with the message; we've also used this to encrypt a pre-shared
secret. Can you decrypt with your private key and check the pre-shared key works with the twister?

Have a good weekend,

CayceP

-----BEGIN PUBLIC KEY-----
MIGeMA0GCSqGSIb3DQEBAQUAA4GMADCBiAKBgFbDk+zYy1tbjwPpsTWbYjIfBtZk
walARbJxLg6QhyalsGnBx064VFIH9XIKzPK/Dt1RzMO68gy7zLOiyipPtYb2n0M6
WcdDGgw9J9+xx4HjXZCHx4h4zQhfQeOYymeSPewXJOe+GT31ymz6/Q1Ulyq/jWnD
XZogxfbXi6bIwuN7AgMBAAE=
-----END PUBLIC KEY-----

-----BEGIN MESSAGE-----
41296290787170212566581926747559000694979534392034439796933335542554551981322424774631715454669002723657175134418412556653226439790475349107756702973735895193117931356004359775501074138668004417061809481535231402802835349794859992556874148430578703014721700812262863679987426564893631600671862958451813895661
-----END MESSAGE-----

The contents of the fasterprimes.py file is as follows.

#!/usr/bin/env python
#**********************************************************************
# filename: fasterprimes.py
# version: 0.06.2-alpha
# release date: 20170806
# dev: Cayce Pollard
# qa: NOT PASSED, open defects.
# finds a specified length prime, then a neighbouring prime for speed. 
# DEFECTS
# ID[243], category A4, owner: CayceP, comment: may have to be run several times to generate valid RSA values
# ID[552], category A9, owner: AppSec, comment: Do neighbouring primes present a security risk?
#**********************************************************************


from Crypto.Util import number
from Crypto.PublicKey.RSA import construct
from Crypto.PublicKey import RSA
import sympy


def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, x, y = egcd(b % a, a)
        return (g, y - (b // a) * x, x)


def getPQ():
    n_length =512 #generates a 1024 bit key.
    while True:
        firstprime = number.getPrime(n_length) #let's get our first number
	lowerp = firstprime - 10
	upperp = firstprime + 10       
	for x in range(lowerp,upperp): #getPrime takes too long so we'll find a nearby prime for q
           if x == firstprime:
             continue
           else:   
             if sympy.isprime(x):
                secondprime = x
                return firstprime, secondprime
                break
        return 1, 1
     
e = 65537

while True:
    p, q = getPQ()  
    if p == 1:
        print("still trying")
    else:
      break


n = p*q #we make our modulus
phi = (p-1)*(q-1) #this one is for making the private key
gcd, d, b = egcd(e, phi) #now we have all our RSA values. 

key_params = (long(n), long(e), long(d))
key = RSA.construct(key_params)
print key.exportKey()
print key.publickey().exportKey()
#keep the pre-shared key below 100 bytes. 
message = #put the message here.
#message = [ord(c) for c in message] #comment out if message is int.
#message = int(''.join(map(str,message)))
print ('message: ', message)
RSAsecret = key.encrypt(int(message),'') #check the encryption works 
print ('RSAsecret: ', RSAsecret) #send this to the recipient
print ('message: ', message) #don't send this you idiot.
print ('Secret check:', key.decrypt(RSAsecret)) #check the message matches the decrypted message/

The contents of the AESbootstrap.py file is as follows.

#!/usr/bin/env python
#**********************************************************************
# filename: AESbootstrap.py
# version: 0.11.7-alpha
# release date: 20170801
# dev: Cayce Pollard
# qa: Jonathan Norrell
# instantiate mersenne each time, feed it every 3 digits of the shared secret
# to establish a shared AES128 key.
#
#**********************************************************************

#textbook mersenne twister from https://en.wikipedia.org/wiki/Mersenne_Twister#Python_implementation (no rolling your own!)

class mersenne(object):

    def __init__(self, seed):
        # Initialize the index to 0
        self.index = 624
        self.mt = [0] * 624
        self.mt[0] = seed  # Initialize the initial state to the seed
        for i in range(1, 624):
            initval = int(0xFFFFFFFF & (1812433253 * (self.mt[i - 1] ^ self.mt[i - 1] >> 30) + i))
            # print(initval)
            self.mt[i] = initval


    def extract_number(self):
        if self.index >= 624:
            self.twist()

        y = self.mt[self.index]

        # Right shift by 11 bits
        y = y ^ y >> 11
        # Shift y left by 7 and take the bitwise and of 2636928640
        y = y ^ y << 7 & 2636928640
        # Shift y left by 15 and take the bitwise and of y and 4022730752
        y = y ^ y << 15 & 4022730752
        # Right shift by 18 bits
        y = y ^ y >> 18

        self.index = self.index + 1

        return int(0xFFFFFFFF & y)

    def twist(self):
        for i in range(624):
            # Get the most significant bit and add it to the less significant
            # bits of the next number
            y = int(0xFFFFFFFF & ((self.mt[i] & 0x80000000) + (self.mt[(i + 1) % 624] & 0x7fffffff)))
            self.mt[i] = self.mt[(i + 397) % 624] ^ y >> 1

            if y % 2 != 0:
                self.mt[i] = self.mt[i] ^ 0x9908b0df
        self.index = 0
        #test


#******************************************************************************
#test tool:
#use this to convert a triplet from the decoded value as seedval
#do this across each of the values to check the candidate against the AESkey.
#******************************************************************************
def gen_and_check(genseed):
    # make an object
    x = mersenne(genseed)
    y = (x.extract_number() & 0xFF) #only interested in LSBs. Use the mask as we don't care about the rest

    return y #candidate for comparison.

list = str(bin(gen_and_check(seedval)))
candidate = list[2::]
candidate = candidate.zfill(8)

Given that we know the RSA scheme from the fasterprimes.py file, we need to deduce the p and q used in the public key from the email.msg file. We can obtain this information by first pulling the n variable from the public key and then performing integer factorization to recover two prime factors of the n product. We use the powerful RsaCtfTool to recover the n variable.

Once we have the n product, we can retrieve p and q using integer factorization. For this challenge I used the online Integer factorization calculator from Alpertron. The Integer factorization calculator gave us the following result.

60927735877056559130803069919621859729817223816091468870468728150535102345085544195001142179497747300756976118359991531766104121379004146329976732080428122272205922112100073487631152244297343150154109815442681320311122134731991282281969152492933055882377304091844616671159896354284349735375653609635116671867 (308 digits) = 7805622068551395034983074294227914827932592556281432557101799867160043121996329164791493852142033952331091204125384233936237118904494182099698709037828123 (154 digits) × 7805622068551395034983074294227914827932592556281432557101799867160043121996329164791493852142033952331091204125384233936237118904494182099698709037828129 (154 digits)

Now that we have the p and q variables, we can modify the script to use these variables instead of generating new p and q variables. Furthermore, we can modify the message to reflect the message given in the email.msg file and change the encryption call to a decryption call. The modified script should look as follows.

#!/usr/bin/env python
from Crypto.Util import number
from Crypto.PublicKey.RSA import construct
from Crypto.PublicKey import RSA
import sympy

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, x, y = egcd(b % a, a)
        return (g, y - (b // a) * x, x)

e = 65537

p = 7805622068551395034983074294227914827932592556281432557101799867160043121996329164791493852142033952331091204125384233936237118904494182099698709037828123
q = 7805622068551395034983074294227914827932592556281432557101799867160043121996329164791493852142033952331091204125384233936237118904494182099698709037828129

n = p*q #we make our modulus
phi = (p-1)*(q-1) #this one is for making the private key
gcd, d, b = egcd(e, phi) #now we have all our RSA values. 

key_params = (long(n), long(e), long(d))
key = RSA.construct(key_params)

message = 41296290787170212566581926747559000694979534392034439796933335542554551981322424774631715454669002723657175134418412556653226439790475349107756702973735895193117931356004359775501074138668004417061809481535231402802835349794859992556874148430578703014721700812262863679987426564893631600671862958451813895661
print key.decrypt(message)

We can now run the script to decrypt the message.

Looking at the gen_and_check function from the AESbootstrap.py file, we notice the following function description.

#******************************************************************************
#test tool:
#use this to convert a triplet from the decoded value as seedval
#do this across each of the values to check the candidate against the AESkey.
#******************************************************************************

After the function definition, we find the following example usage code.

list = str(bin(gen_and_check(seedval)))
candidate = list[2::]
candidate = candidate.zfill(8)

Following these instructions, we must create integers from every 3 characters in the decrypted message and seed them into the gen_and_check function as shown above. This can be scripted in Python as shown below.

decrypted = '500491164140527509149577108534901274218266116126419727365281831678182316'
triplets =  [int(decrypted[i:i+3]) for i in range(0, len(decrypted), 3)]

for seedval in triplets:
    list = str(bin(gen_and_check(seedval)))
    candidate = list[2::]
    candidate = candidate.zfill(8)
    print candidate

We can now run the script to decode the decrypted message.

Looking at the output of the script, we see that we have decoded bit strings from the decrypted message. We can modify the script to automatically convert these bit strings to characters as shown below.

decrypted = '500491164140527509149577108534901274218266116126419727365281831678182316'
triplets =  [int(decrypted[i:i+3]) for i in range(0, len(decrypted), 3)]

result = ''

for seedval in triplets:
    list = str(bin(gen_and_check(seedval)))
    candidate = list[2::]
    result += chr(int(candidate.zfill(8), 2))

print result

We can now run the script to obtain the character representation of the bit strings.

Looking at the output of our final script, we notice that the new output is base64 encoded. We can decode the output as shown below.

And there you have it – the challenge has been solved!

Leave a Reply