Cryptography

Challenge	Link
is_admin=True	Here

is_admin=True

Description

-

Solution

Exploit

Diberikan source code sebagai berikut

from hashlib import sha256
import random
import os

p = 69278042787891942769502075928585090381290090384778024990006411012262963663859
g = 2
m = 4267738774321166375026693303590202006447685928119906506624384544530089122661922193
a = 1872159875735606573086019350365709191427276692069413859597107145760799047673904037
c = 3852523496907343703707599716820831623137858734069135383774172801943851091960152572

class LCG:
    def __init__(self, m,a,c, seed):
        self.m = m
        self.a = a
        self.c = c
        self.state = seed

    def next(self):
        self.state = (self.a * self.state + self.c) % self.m
        return self.state >> 16

class TokenGenerator:
    def __init__(self, p,g,m,a,c):
        self.p = p
        self.g = g
        self.x = random.randint(1,p)
        self.lcg = LCG(m,a,c, random.randint(1, m))

    def next(self):
        k = self.lcg.next()
        self.x = pow(self.g, k, self.p) * self.x % self.p
        return self.x

class Server:
    def __init__(self):
        self.users = {}
        self.sessions = {}
        self.token_generator = TokenGenerator(p,g,m,a,c)
        self.user = None

    def generate_token(self):
        x = self.token_generator.next()
        return hex(x)

    def register(self, username, password, is_admin=False):
        if username in self.users:
            print("[x] Username already exists")
            return
        token = self.generate_token()
        self.sessions[token] = username
        self.users[username] = {
            "username": username,
            "password": sha256(password.encode()).hexdigest(),
            "token": token,
            "is_admin": is_admin,
        }
        return token

    def get_token(self, username, password):
        if username not in self.users:
            print("[x] Invalid username")
            return
        if self.users[username]["password"] != sha256(password.encode()).hexdigest():
            print("[x] Invalid password")
            return

        token = self.generate_token()
        self.sessions[token] = username
        self.users[username]["token"] = token
        return token

    def set_token(self, token):
        if token not in self.sessions:
            print("[x] Invalid token")
            return
        self.user = self.users[self.sessions[token]]
        print("Welcome, " + self.user["username"])

    def get_flag(self):
        if self.user is None:
            print("You must login first")
            return
        if not self.user["is_admin"] == True: # <-- is_admin=true??
            print("Only admin can access the flag")
            return
        
        print(open("/flag/flag.txt").read())

print("=" * 100)
print(f"p = {p}")
print(f"g = {g}")
print(f"m = {m}")
print(f"a = {a}")
print(f"c = {c}")
print("=" * 100)

server = Server()
server.register("admin", os.getenv("PASSWORD"), True)
server.register("john doe", "password2", False)
server.register("jane doe", "password3", False)


def menu():
    print("=" * 100)
    print("1. Register")
    print("2. Get Token")
    print("3. Set Token")
    print("4. Get flag")
    print("5. Exit")
    return int(input("choose option: "))


print("Welcome to the server!")
while True:
    choice = menu()
    if choice == 1:
        username = input("Username: ")
        password = input("Password: ")
        token = server.register(username, password)
        if token:
            print(f"Your token: {token}")
    elif choice == 2:
        username = input("Username: ")
        password = input("Password: ")
        token = server.get_token(username, password)
        if token:
            print(f"Your token: {token}")
    elif choice == 3:
        token = input("Token: ")
        server.set_token(token)
    elif choice == 4:
        server.get_flag()
    elif choice == 5:
        print("Bye!")
        break

TokenGenerator intinya melakukan generate lcg lalu menghasilkan token dengan cara g^k * x untuk nilai k adalah nilai lcg dan nilai x adalah token sebelumnya atau nilai random (initial). Jadi untuk mendapatkan token dari admin kita bisa lakukan flow sebagai berikut

• Generate ulang nilai token admin karena sudah mengetahui state dan x (token)

• Nilai k bisa didapatkan dengan discrete log karena p smooth

• Lakukan multiplicative inverse untuk dapat nilai g^k % p

• Login 2 kali sebagai john doe untuk dapat tokennya

Berikut solver yang kami gunakan

#!/usr/bin/env sage

from pwn import * 
from Crypto.Util.number import *
import sys
import os

def attack(y, k, s, m, a, c):
    """
    Recovers the states associated with the outputs from a truncated linear congruential generator.
    More information: Frieze, A. et al., "Reconstructing Truncated Integer Variables Satisfying Linear Congruences"
    :param y: the sequential output values obtained from the truncated LCG (the states truncated to s most significant bits)
    :param k: the bit length of the states
    :param s: the bit length of the outputs
    :param m: the modulus of the LCG
    :param a: the multiplier of the LCG
    :param c: the increment of the LCG
    :return: a list containing the states associated with the provided outputs
    """
    diff_bit_length = k - s

    # Preparing for the lattice reduction.
    delta = c % m
    y = vector(ZZ, y)
    for i in range(len(y)):
        # Shift output value to the MSBs and remove the increment.
        y[i] = (y[i] << diff_bit_length) - delta
        delta = (a * delta + c) % m

    # This lattice only works for increment = 0.
    B = matrix(ZZ, len(y), len(y))
    B[0, 0] = m
    for i in range(1, len(y)):
        B[i, 0] = a ** i
        B[i, i] = -1

    B = B.LLL()

    # Finding the target value to solve the equation for the states.
    b = B * y
    for i in range(len(b)):
        b[i] = round(QQ(b[i]) / m) * m - b[i]

    # Recovering the states
    delta = c % m
    x = list(B.solve_right(b))
    for i, state in enumerate(x):
        # Adding the MSBs and the increment back again.
        x[i] = int(y[i] + state + delta)
        delta = (a * delta + c) % m

    return x

def regist(username, password):
	r.recvuntil(b"option: ")
	r.sendline(b"1")
	r.recvuntil(b"Username: ")
	r.sendline(username)
	r.recvuntil(b"Password: ")
	r.sendline(password)
	r.recvuntil(b"Your token: ")
	token = int(r.recvline().strip().decode(),16)
	return token

def login(username, password):
	r.recvuntil(b"option: ")
	r.sendline(b"2")
	r.recvuntil(b"Username: ")
	r.sendline(username)
	r.recvuntil(b"Password: ")
	r.sendline(password)
	r.recvuntil(b"Your token: ")
	token = int(r.recvline().strip().decode(),16)
	return token

ip = sys.argv[1]

r = remote(ip, int(50004))
r.recvuntil(b"p = ")
p = int(r.recvline().decode().strip())
r.recvuntil(b"g = ")
g = int(r.recvline().decode().strip())
r.recvuntil(b"m = ")
m = int(r.recvline().decode().strip())
r.recvuntil(b"a = ")
a = int(r.recvline().decode().strip())
r.recvuntil(b"c = ")
c = int(r.recvline().decode().strip())

if(m != 4267738774321166375026693303590202006447685928119906506624384544530089122661922193 or p != 69278042787891942769502075928585090381290090384778024990006411012262963663859):
    exit()


username = b"john doe"
password = b"password2"
y = []
token1 = login(username, password)
token2 = login(username, password)
token3 = login(username, password)

g1 = Mod(2, p)

gkp = inverse(token1, p) * token2
y.append(discrete_log(gkp,g1))

gkp = inverse(token2, p) * token3
y.append(discrete_log(gkp,g1))

k = 271
s = 255

list_state = attack(y, k, s, m, a, c)

for i in range(3):
	k = (((list_state[0] - c ) * inverse(a, m)) % m)
	list_state.insert(0, k)

list_x = [token1, token2, token3]

for i in range(3):
	new_x = (list_x[0] * inverse(pow(g, list_state[2 - i] >> 16, p), p))%p
	list_x.insert(0, new_x)

r.recvuntil(b"option: ")
r.sendline(b"3")
r.recvuntil(b"Token: ")
r.sendline(hex(list_x[0]).encode())
r.recvuntil(b"option: ")
r.sendline(b"4")
print(r.recvline().strip().decode(), flush=True)
r.close()

Patching

Patching yang dilakukan adalah dengan melakukan perubahan terhadap p dan m dengan strong prime, berikut untuk patch yang diimplementasi.

from hashlib import sha256
import random
import os

p = 28952647841308909269621833267645540813923816053722153826289301924999333975928896957179767092359509824355232814941347849551776965418137320339601906230282605594626237498752828145255589306309199485972897747710200521090486640719956082408562332744778767163030676864747306290834058185412835555997245698931634481293469986945016639304887198130326321012590709317025628821727318888569661590445928105140417820553266128980155518948472369598427185397761897457811418641433812768636207567944001166960240695174113089294317062878260104214348742827688597787318015273359751774467162937353388062956924818911652362606302919071776598499731
g = 2
m = 23322999113566101166114868124251825777365249360854342284449108846057303452231680280816276323545317723530798105085775063547649502566177099584656749522730458778431643207849601139934044213540531482786160671227007312005845732423057563401780925301182577005723978598069967606433875464655042765896069375797207954898058844109743672092024959235213634452809303282814155344147049128759319214396832414040370797209682104576109966781362622017838989976748426416664284714756136603330385027960471417902560636197303489555416069538245512300869624770713471348308348195927404882994404686461451427816100230103666860295624396647517406817593
a = 1872159875735606573086019350365709191427276692069413859597107145760799047673904037
c = 3852523496907343703707599716820831623137858734069135383774172801943851091960152572

class LCG:
    def __init__(self, m,a,c, seed):
        self.m = m
        self.a = atar
        self.c = c
        self.state = seed

    def next(self):
        self.state = (self.a * self.state + self.c) % self.m
        return self.state >> 16

class TokenGenerator:
    def __init__(self, p,g,m,a,c):
        self.p = p
        self.g = g
        self.x = random.randint(1,p)
        self.lcg = LCG(m,a,c, random.randint(1, m))

    def next(self):
        k = self.lcg.next()
        self.x = pow(self.g, k, self.p) * self.x % self.p
        return self.x

class Server:
    def __init__(self):
        self.users = {}
        self.sessions = {}
        self.token_generator = TokenGenerator(p,g,m,a,c)
        self.user = None

    def generate_token(self):
        x = self.token_generator.next()
        return hex(x)

    def register(self, username, password, is_admin=False):
        if username in self.users:
            print("[x] Username already exists")
            return
        token = self.generate_token()
        self.sessions[token] = username
        self.users[username] = {
            "username": username,
            "password": sha256(password.encode()).hexdigest(),
            "token": token,
            "is_admin": is_admin,
        }
        return token

    def get_token(self, username, password):
        if username not in self.users:
            print("[x] Invalid username")
            return
        if self.users[username]["password"] != sha256(password.encode()).hexdigest():
            print("[x] Invalid password")
            return

        token = self.generate_token()
        self.sessions[token] = username
        self.users[username]["token"] = token
        return token

    def set_token(self, token):
        if token not in self.sessions:
            print("[x] Invalid token")
            return
        self.user = self.users[self.sessions[token]]
        print("Welcome, " + self.user["username"])

    def get_flag(self):
        if self.user is None:
            print("You must login first")
            return
        if not self.user["is_admin"] == True: # <-- is_admin=true??
            print("Only admin can access the flag")
            return
        
        print(open("/flag/flag.txt").read())

print("=" * 100)
print(f"p = {p}")
print(f"g = {g}")
print(f"m = {m}")
print(f"a = {a}")
print(f"c = {c}")
print("=" * 100)

server = Server()
server.register("admin", os.getenv("PASSWORD"), True)
server.register("john doe", "password2", False)
server.register("jane doe", "password3", False)


def menu():
    print("=" * 100)
    print("1. Register")
    print("2. Get Token")
    print("3. Set Token")
    print("4. Get flag")
    print("5. Exit")
    return int(input("choose option: "))


print("Welcome to the server!")
while True:
    choice = menu()
    if choice == 1:
        username = input("Username: ")
        password = input("Password: ")
        token = server.register(username, password)
        if token:
            print(f"Your token: {token}")
    elif choice == 2:
        username = input("Username: ")
        password = input("Password: ")
        token = server.get_token(username, password)
        if token:
            print(f"Your token: {token}")
    elif choice == 3:
        token = input("Token: ")
        server.set_token(token)
    elif choice == 4:
        server.get_flag()
    elif choice == 5:
        print("Bye!")
        break