Infinite Descent
6 minutes to read
We are given a Python with a weird RSA implementation (fastprimes.py):
#!/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/
We also have another code that generates a 128-bit key (16 bytes) for AES (AESbootstrap.py):
#!/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)
There is an email where we can find the purpose of the above scripts, as well as the public key for RSA and the ciphertext:
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 RSA cryptosystem is vulnerable because the way to get $n = p \cdot q$ and both prime numbers are really close to each other:
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
Hence, we can find $p$ and $q$ as the prime numbers that are closest to $\sqrt{n}$ from above and from below ($q \leq \sqrt{n} \leq p$). Then, we can make sure that $n = p \cdot q$.
The above can be done easily with Python:
$ python3 -q
>>> from Crypto.PublicKey import RSA
>>> from Crypto.Util.number import isPrime
>>> from gmpy2 import iroot
>>> key = RSA.import_key('''-----BEGIN PUBLIC KEY-----
... MIGeMA0GCSqGSIb3DQEBAQUAA4GMADCBiAKBgFbDk+zYy1tbjwPpsTWbYjIfBtZk
... walARbJxLg6QhyalsGnBx064VFIH9XIKzPK/Dt1RzMO68gy7zLOiyipPtYb2n0M6
... WcdDGgw9J9+xx4HjXZCHx4h4zQhfQeOYymeSPewXJOe+GT31ymz6/Q1Ulyq/jWnD
... XZogxfbXi6bIwuN7AgMBAAE=
... -----END PUBLIC KEY-----
... ''')
>>> key.e
65537
>>> key.n
60927735877056559130803069919621859729817223816091468870468728150535102345085544195001142179497747300756976118359991531766104121379004146329976732080428122272205922112100073487631152244297343150154109815442681320311122134731991282281969152492933055882377304091844616671159896354284349735375653609635116671867
>>> p = iroot(key.n, 2)[0]
>>> while not isPrime(p):
... p += 1
...
>>> q = p - 1
>>> while not isPrime(q):
... q -= 1
...
>>> assert key.n == p * q
Moreover, we can decrypt the ciphertext:
>>> c = 41296290787170212566581926747559000694979534392034439796933335542554551981322424774631715454669002723657175134418412556653226439790475349107756702973735895193117931356004359775501074138668004417061809481535231402802835349794859992556874148430578703014721700812262863679987426564893631600671862958451813895661
>>> phi_n = (p - 1) * (q - 1)
>>> d = pow(key.e, -1, phi_n)
>>> m = pow(c, d, key.n)
>>> hex(m)
'0x48843fc15819e23660c1cd16a573aff247f7024d18eaae397d0896f103ac'
>>> bytes.fromhex(hex(m)[2:])
b'H\x84?\xc1X\x19\xe26`\xc1\xcd\x16\xa5s\xaf\xf2G\xf7\x02M\x18\xea\xae9}\x08\x96\xf1\x03\xac'
>>> len(bytes.fromhex(hex(m)[2:]))
30
The result we get is the seed for AESbootstrap.py, which is a custom PRNG Mersenne Twister implementation. The header of the script tells to use the seed as a decimal number splitted in three-digit numbers. Therefore, we need this:
m_str = str(m)
m_numbers = [int(m_str[i:i+3]) for i in range(0, len(m_str), 3)]
flag = ''
for m_n in m_numbers:
list = str(bin(gen_and_check(m_n)))
candidate = list[2::]
candidate = candidate.zfill(8)
flag += chr(int(candidate, 2))
print(flag)
And we get a Base64-encoded string:
$ python3 solve.py
ZmxhZz1Ccm9rM25fRzRtZQ==
$ python3 solve.py | base64 -d
flag=Brok3n_G4me
And the flag is: HTB{Brok3n_G4me}.
The full script can be found in here: solve.py.