ASCIS CTF 2024 - LoveLinhaLot Writeup#

  • Category: Crypto
  • Score: 999/1000
  • Solve: 2/63

Source code# 

import random
import string
from Crypto.Util.number import isPrime

BLOCK_LEN = 129
CHARSET = string.ascii_uppercase + string.ascii_lowercase + string.digits
users, pwd_hashes = {}, []
allowed_blocks = []

q1 = 57895665874783536962369408363969823887021530656373208299565102620846005563716018275834077962292286213472570266375824572745671541793458387390711613089471407869558363212866932533545785125988453002675479793768261480181947144057144941974626043243654731721303589851520175899531854692118423229594279209070187162279
p1 = 2 * q1 + 1
g1 = 2
assert isPrime(p1)
assert isPrime(q1)
assert pow(g1, q1, p1) == 1
x1 = random.randint(1, 2 ** 256)
y1 = pow(g1, x1, p1)

def block_hash(block, bases, a):
    for x, y in zip(bases, block):
        a = a * pow(x, y, p1) % p1
    
    return a
def secure_hash(data, token, is_login = False):
    assert len(data) + 1 >= BLOCK_LEN, "Invalid Length"
    
    if len(data) % BLOCK_LEN != 0:
        data += b'\x80'
        data += b'\x00' * (BLOCK_LEN - len(data) % BLOCK_LEN - 1)
        
    blocks = [data[i:i + BLOCK_LEN] for i in range(0, len(data), BLOCK_LEN)]
    bases = [pow(g1, x, p1) for x in token] + [g1]
    yu_1 = y1
    
    for block in blocks:
        if all(x == 0 for x in block[:-1]):
            raise ValueError("No cheese this time")
        if is_login:
            if block not in allowed_blocks:
                raise ValueError("Invalid block")
        yu_1 = block_hash(block, bases, yu_1)
        allowed_blocks.append(block)
    
    return yu_1

def register(username, password):
    token = [random.randint(1, q1 - 1) for _ in range(BLOCK_LEN - 1)]
    if username in users:
        print("Username already exists")
        return False
    pwd_hash = secure_hash(password, token)
    users[username] = token
    pwd_hashes.append(pwd_hash)
    return True

    
def login(username, password):
    if username not in users:
        return False
    token = users[username]
    try:
        password.decode()
    except:
        return False
    pwd_hash = secure_hash(password, token, True)
    return pwd_hash in pwd_hashes

def breach(username):
    if username not in users:
        return None
    return users[username]

def menu():
    print("1. Register")
    print("2. Login")
    print("3. Exit")

def main():
    admin_username = "admin"
    admin_password = ''.join(random.choices(CHARSET, k = BLOCK_LEN - 1)).encode() + b'\x00'
    register(admin_username, admin_password)
    print(f'User {admin_username} registered successfully')
    for _ in range(5):
        try:
            menu()
            choice = int(input("> "))
            if choice == 1:
                username = input("Enter username: ")
                password = bytes.fromhex(input("Enter password: "))
                if register(username, password):
                    print(f'User {username} registered successfully')
            elif choice == 2:
                username = input("Enter username: ")
                password = bytes.fromhex(input("Enter password: "))
                if login(username, password):
                    if username == admin_username:
                        print("Welcome admin, here is your flag: ")
                        print(open("flag.txt").read())
                        exit()
                    else:
                        print(f"Welcome user {username}")
                else:
                    print("Invalid credential")
            elif choice == 3:
                print("Gud bye")
                exit(0)
            elif choice == 1337:
                victim = input("Give me the victim name: ")
                victim_token = breach(victim)
                print("Shhhhh, don't tell anyone about this")
                print(victim_token)
            else:
                print("Invalid choice")
                exit(0)
        except ValueError:
            print("No No No No")
    
if __name__ == "__main__":
    main()

Challenge Analysis#

Here is a quick summarization of the problem:

  • The server implements a simple authentication with 3 main functions:
    • Register a user with username $U$ and password $P$, compute and save password hash $H(T, P)$ where $T$ is a unique token for each user and $H$ is a custom function
    • Login with username $U$ and password $P$, the server verify by compute password hash $H(T, P)$ again and check if it is stored.
    • Retrieve token $T$ of abitrary user.
  • You have 5 queries, the goal is to login as admin and retrieve the flag

Solution#

Brainstorm#

  • Upon the connection, the server generate a private key $x$ in range $[1, q - 1]$ and compute $y = g^x \pmod{p}$
  • The $H(T, P)$ can be written as follow: $$\displaylines{ T = (T_0, T_1, …, T_{127}, 1) \\ P = (P_0, P_1, …) \\ H(T, P) = y \prod_{i=0}\prod_{j=0}^{128}g^{T_jP_{ij}} \pmod{p}}$$ where $P_i$ is the number representation of each 129 characters in $P$ and $T_i \in [1, q - 1]$
  • In the login, you can spot out that return line looks fishy:
    return pwd_hash in pwd_hashes
  • If I can enforce a hash collision of hash function $H$, then I can grab the flag as follow:
    1. Create account with credential $U_{user}, P_{user}$, obtain $H_{user} = H(T_{user}, P_{user})$
    2. Find a password $P’$ such that $H(T_{admin}, P’) = H_{user}$
    3. Login with username admin and password $P’$ to obtain the flag

Hash Collision#

  • Denote $S_i$ as sum of characters at position $i$ of all blocks in $P$, i.e. $$S_i = \sum_{j=0}P_{ji}$$$$S = (S_0, S_1, …)$$$$=> H(T, P) = yg^{\sum_{i=0}^{128}{T_iS_i}} = g^{x + \sum_{i=0}^{128}T_iS_i} \pmod{p}$$
  • Set $h = x + \sum_{i=0}^{128}{T_iS_i} $
  • The target is to find $P’$ whose $S’$ satisfy the equation: $$x + \sum{T_{admin}S’} = h_0 = x + \sum{T_{user}S_{user}} \pmod{q} $$$$ => \sum{T_{admin}S’} = \sum{T_{user}S_{user}} \pmod{q} $$
  • I have full control over the $P_{user}$, and $T_{user}$ can be retrieved from the server => Compute the RHS of the equation is trivial
  • Since each element in $S’$ is sum of characters, it is supposed to be small, while $T_{admin}$ is very huge (range $[1, q - 1]$). This implies the usage of LLL algorithm to find such $S'$
  • Here is the lattice: $$ \begin{align} M = \left( \begin{array}{ccccc} 1 & 0 & \dots & 0 & T_0 \\ 0 & 1 & \dots & 0 & T_1 \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ 0 & 0 & \dots & 1 & T_{127} \\ 0 & 0 & \dots & 0 & q \end{array} \right) \end{align} $$
  • The target vector should only contains positive values so that I can craft the payload
  • In this challenge, I use Babai CVP algorithm and slowly increase the target vector until I get the desired output. Also, the final value must be smaller than the RHS, so that $S’_{128}$ exists.

Notes#

  • For the payload craft, please refer the to the script below, also the decode method in Python does not raise an exception when the byte value is in range $[0, 127]$
  • The login only allows blocks that are used in register function, so you have to register another account with $P’$ before login as admin
  • This challenge is heavily inspired by Invention in OpenECSC Round 2. The main change here is the use of group $Z_p$ and token generation.
  • My script does not guarantee to find such target vector in each connection, so I have to run it 2-3 times to obtain the flag. Also the runtime is pretty long since it includes performing LLL on 128 x 128 lattice.
  • The first version of this challenge can be solved trivially by register a password with 129 null bytes. Therefore I delivered a revenge challenge with a check in secure_hash function in later phase of the CTF.
  • After the competition, @tvdat20004 from team UIT.Efficiency V - who blooded the revenge version - told me that the CVP part can be speed up by using ConnorM’s repo.

Solve Script# 

import string
from sage.all import *
from pwnlib.tubes.process import process
from pwnlib.tubes.remote import remote
from sage.modules.free_module_integer import IntegerLattice

BLOCK_LEN = 128
q1 = 57895665874783536962369408363969823887021530656373208299565102620846005563716018275834077962292286213472570266375824572745671541793458387390711613089471407869558363212866932533545785125988453002675479793768261480181947144057144941974626043243654731721303589851520175899531854692118423229594279209070187162279
p1 = 2 * q1 + 1
g1 = 2

username = b"Zayn"
passwd = b'NCIm6RJuC5dKHohq2J6vnd8mSsesHzDC77TH5PDoGLcXUEXSJQdPGWSBGa1Y03Vzyz0GNTkm6S8iO3grixHmY07sobuhXFwmuYfFDEjzkxgbs5aajuEe7ijpkHB3JF8T\x00'
M = [[0 for _ in range(BLOCK_LEN + 1)] for __ in range(BLOCK_LEN + 1)]

CONN = process(['python3', 'server.py'])
CONN.sendlineafter(b'>', b'1')
CONN.sendlineafter(b'username:', username)
CONN.sendlineafter(b'password:', passwd.hex().encode())

CONN.sendlineafter(b'>', b'1337')
CONN.sendlineafter(b'name:', username)
CONN.recvline()
user_token = eval(CONN.recvline().decode().strip())
print(user_token[0])

CONN.sendlineafter(b'>', b'1337')
CONN.sendlineafter(b'name:', b"admin")
CONN.recvline()
admin_token = eval(CONN.recvline().decode().strip())
print(admin_token[0])

bases = [pow(g1, x, p1) for x in user_token]

rhs = 0
for x, y in zip(user_token, passwd):
    rhs += x * y % q1

for i in range(BLOCK_LEN):
    M[i][i] = 1
    M[i][-1] = admin_token[i]
M[-1][-1] = -q1
M = Matrix(ZZ, M)

M = IntegerLattice(M, lll_reduce=True).reduced_basis
G = M.gram_schmidt()[0]

# Babai CVP
for bit in range(7, 15):
    print(f'{bit = }')
    target = vector(ZZ, [2 ** bit for _ in range(BLOCK_LEN)] + [rhs])
    diff = target
    for i in reversed(range(G.nrows())):
        diff -=  M[i] * ((diff * G[i]) / (G[i] * G[i])).round()
    res = target - diff
    msg = [x for x in res[:-1]]
    if all(x >= 0 for x in msg) and res[-1] < rhs:
        msg.append(rhs - res[-1])
        print(msg)
        break
if len(msg) != 129:
    print("Failed")
    exit()

admin_password = b""
while any([x > 0 for x in msg]):
    for i in range(len(msg)):
        if msg[i] >= 0x7f:
            admin_password += b"\x7f"
            msg[i] -= 0x7f
        elif msg[i] == 0:
            admin_password += b"\x00"
        elif msg[i] < 0x7f:
            admin_password += bytes([msg[i]])
            msg[i] = 0

if len(admin_password) % 129 != 0:
    admin_password += b"\x00" * (129 - len(admin_password) % 129)
print(len(admin_password))
blocks = [admin_password[i:i + 129] for i in range(0, len(admin_password), 129)]  
blocks = b''.join(list(set(blocks)))

CONN.sendlineafter(b'>', b'1')
CONN.sendlineafter(b'username: ', b'Zyan')
CONN.sendlineafter(b'password: ', blocks.hex().encode())

CONN.sendlineafter(b'>', b'2')
CONN.sendlineafter(b'username: ', b'admin')
CONN.sendlineafter(b'password: ', admin_password.hex().encode())

CONN.interactive()

Flag: ASCIS{d1D_U_U53_lll?}
Flag: ASCIS{d1d_1_g3t_My_r3v3ng3???}