I participated in CODEGATE 2024 held on 6/1-2 with the team WreckTheLine. The result was 11th/220 in the General division.

crypto

Baby Login

10 solves

main.go
package main

import (
	"bufio"
	"crypto/aes"
	"crypto/ecdsa"
	"crypto/elliptic"
	"crypto/hmac"
	"crypto/rand"
	"crypto/sha256"
	"crypto/subtle"
	"encoding/base64"
	"encoding/json"
	"fmt"
	"io/ioutil"
	"math/big"
	"os"
	"os/signal"
	"strings"
	"syscall"
	"time"

	"github.com/google/uuid"
)

type HTTPRequest struct {
	Method   string `json:"method"`
	Uid      string `json:"uid"`
	Password string `json:"password"`
	Session  string `json:"session"`
	Secret   string `json:"secret"`
	Path     string `json:"path"`
}
type User struct {
	userName string
	userRole string
}

var SessionManager map[string]User
var SERVER_SECRET_KEY []byte

func pad(s []byte, length int) []byte {
	for len(s)%length != 0 || len(s) < length {
		s = append(s, byte('\x00'))
	}
	return s
}

func unpad(s []byte) []byte {
	for s[len(s)-1] == byte('\x00') {
		s = s[:len(s)-1]
	}
	return s
}

func KDF(Gx, Gy *big.Int, serverPriv []byte) ([]byte, []byte) {
	_m, _ := elliptic.P256().ScalarMult(Gx, Gy, serverPriv)
	key := pad(_m.Bytes(), 32)
	return key[:16], key[16:32]
}

func passwordGen(uid, role string) []byte {
	curve := elliptic.P256()
	R, _ := ecdsa.GenerateKey(curve, rand.Reader)
	Gx, Gy := R.PublicKey.X, R.PublicKey.Y

	key1, key2 := KDF(Gx, Gy, SERVER_SECRET_KEY)

	cipher, _ := aes.NewCipher(key1)
	ct := make([]byte, 16)

	cipher.Encrypt(ct, pad([]byte(uid+"_GUEST"), 16))

	out := append(Gx.Bytes(), Gy.Bytes()...)
	out = append(out, ct...)
	hmac := hmac.New(sha256.New, key2)
	hmac.Write(out)
	tag := hmac.Sum(nil)

	out = append(out, tag...)
	return out
}

func indexHandler(r HTTPRequest) {
	if r.Method == "GET" {
		u := SessionManager[r.Session]
		if u.userName == "" {
			fmt.Println("Register first and login to access the website!")
			return
		} else {
			fmt.Println("Hi " + u.userName + "! You are logged in as " + u.userRole)
		}
		return
	} else {
		fmt.Println("Method Not Allowed")
		return
	}
}

func registerHandler(r HTTPRequest) {
	if r.Method == "GET" {
		fmt.Println("You can register with your username!")
		return
	} else if r.Method == "POST" {
		uid := r.Uid
		if uid == "" {
			fmt.Println("Bad Request")
			return
		} else if uid == "ADMIN" {
			fmt.Println("Nope! You can't register as ADMIN!")
			return
		}
		password := passwordGen(uid, "GUEST")
		fmt.Println("Here is your password token : " + base64.StdEncoding.EncodeToString(password))
		return
	} else {
		fmt.Println("Method Not Allowed")
		return
	}
}

func loginHandler(r HTTPRequest) {
	if r.Method == "GET" {
		fmt.Println("You can login with your username and password token!")
		return
	} else if r.Method == "POST" {
		uname := SessionManager[r.Session].userName
		if uname != "" {
			fmt.Println("You are already logged in as " + uname)
			return
		}
		uid := r.Uid
		password := r.Password
		if uid == "" || password == "" {
			fmt.Println("Bad Request")
			return
		}

		pw, err := base64.StdEncoding.DecodeString(password)
		if err != nil {
			fmt.Println("Bad Request")
			return
		}

		length := len(pw)
		if length < 112 || length%16 != 0 {
			fmt.Println("Bad Request")
			return
		}

		Gx := new(big.Int).SetBytes(pw[:32])
		Gy := new(big.Int).SetBytes(pw[32:64])
		ct, hmac_in := pw[64:length-32], pw[length-32:]

		key1, key2 := KDF(Gx, Gy, SERVER_SECRET_KEY)
		hmac := hmac.New(sha256.New, key2)
		hmac.Write(pw[:length-32])
		tag := hmac.Sum(nil)

		if subtle.ConstantTimeCompare(tag, hmac_in) != 1 {
			fmt.Println("Unauthorized")
			return
		}

		cipher, _ := aes.NewCipher(key1)
		pt := make([]byte, len(ct))
		cipher.Decrypt(pt, ct)
		tmp := strings.Split(string(unpad(pt)), "_")
		if len(tmp) < 2 {
			fmt.Println("Unauthorized")
			return
		}
		userId, userRole := tmp[0], tmp[1]

		if userId != uid {
			fmt.Println("Unauthorized")
			return
		}
		u, _ := uuid.NewRandom()
		var user User
		user.userName = userId
		user.userRole = userRole
		SessionManager[u.String()] = user
		fmt.Println("Hello " + userId + "! You are logged in as " + userRole + "!!")
		fmt.Println("Here is your session : " + u.String())
		return
	} else {
		fmt.Println("Method Not Allowed")
		return
	}
}

func logoutHandler(r HTTPRequest) {
	if r.Method == "GET" {
		uname := SessionManager[r.Session].userName
		if uname == "" {
			fmt.Println("You are not logged in!")
			return
		}
		delete(SessionManager, r.Session)
		fmt.Println("Logged out successfully!")
		return
	} else {
		fmt.Println("Method Not Allowed")
		return
	}
}

func flagHandler(r HTTPRequest) {
	if r.Method == "POST" {
		uname := SessionManager[r.Session].userName
		userRole := SessionManager[r.Session].userRole
		if uname != "ADMIN" || userRole != "admin" {
			fmt.Println("Unauthorized")
			return
		}
		secret := r.Secret
		sec, err := base64.StdEncoding.DecodeString(secret)
		if err != nil {
			fmt.Println("Bad Request")
			return
		}

		if subtle.ConstantTimeCompare(SERVER_SECRET_KEY, sec) != 1 {
			fmt.Println("Unauthorized")
			return
		}
		FLAG, _ := ioutil.ReadFile("./flag")
		fmt.Println("Here is your flag : " + string(FLAG))
	} else {
		fmt.Println("Method Not Allowed")
		return
	}
}

func getRequest(r *bufio.Reader) (HTTPRequest, error) {
	var err error
	var input string
	var request HTTPRequest

	fmt.Print("> ")

	input, err = r.ReadString('\n')
	if err != nil {
		return HTTPRequest{}, err
	}
	err = json.Unmarshal([]byte(input), &request)
	if err != nil {
		return HTTPRequest{}, err
	}
	return request, nil
}

func generateRandomString(length int) string {
	const charset = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"
	b := make([]byte, length)
	for i := range b {
		num, err := rand.Int(rand.Reader, big.NewInt(int64(len(charset))))
		if err != nil {
			panic(err)
		}
		b[i] = charset[num.Int64()]
	}
	return string(b)
}

func validateHash(hashValue *big.Int) bool {
	shifted := new(big.Int).Rsh(hashValue, 24)
	shifted.Lsh(shifted, 24)
	return shifted.Cmp(hashValue) == 0
}

func PoW() {
	randomString := generateRandomString(16)
	fmt.Println("PoW > " + randomString)

	var answer string
	fmt.Scanln(&answer)

	concatenated := randomString + answer
	hash := sha256.Sum256([]byte(concatenated))
	hashValue := new(big.Int).SetBytes(hash[:])

	if !validateHash(hashValue) {
		fmt.Println("Invalid PoW")
		os.Exit(1)
	}

}

func main() {
	PoW()

	sigChan := make(chan os.Signal, 1)
	signal.Notify(sigChan, syscall.SIGALRM)

	go func() {
		time.Sleep(600 * time.Second)
		fmt.Println("timeout")
		os.Exit(1)
	}()

	SessionManager = make(map[string]User)
	SERVER_SECRET_KEY = make([]byte, 33)

	_, _ = rand.Read(SERVER_SECRET_KEY)

	fmt.Println("webAPI for my \"Baby Login\" system")
	reader := bufio.NewReader(os.Stdin)

	for {
		request, err := getRequest(reader)
		if err != nil {
			fmt.Println("Invalid input")
			return
		}
		switch request.Path {
		case "/", "/index.html":
			indexHandler(request)
		case "/register.html":
			registerHandler(request)
		case "/login.html":
			loginHandler(request)
		case "/logout.html":
			logoutHandler(request)
		case "/flag.html":
			flagHandler(request)
		default:
			fmt.Println("Invalid path")
		}
	}
}

In order to get a flag, we need to login as ADMIN with admin role. In addition we need to know the SERVER_SECRET_KEY.

The first vulnerability is that loginHandler parses userId and userRole as {userId}_{userRole}. If we register the user with uId ADMIN_admin and login with the token, we can login as ADMIN with admin role and get that session.

The second, and the main vulnerability is that this program uses elliptic.P256().ScalarMult, which is deprecated. I googled ScalarMult and found golang 1.19 release note, which says that ScalarMult doesn't check if the point is on the curve before this version. Since go.mod says the version of golang is 1.18, I can use this vulnerability to get the SERVER_SECRET_KEY.

I remembered a similar challenge, TIRAMISU in Google CTF 2021 (my writeup). I used a same way as that one.

I first collect curve points with small prime orders on $y^2 = x^3 - 3x + b (0 \le b < p)$.

import pickle


# P256
p = 115792089210356248762697446949407573530086143415290314195533631308867097853951
a = -3


data = {}
while True:
    tmp_b = randint(0, p - 1)
    tmp_E = EllipticCurve(GF(p), [a, tmp_b])
    tmp_n = tmp_E.order()
    factors = list(tmp_n.factor(limit=2**20))
    for tmp_p, _ in factors:
        if tmp_p > 2**16:
            continue
        tmp_P = tmp_E.gens()[0] * (tmp_n // tmp_p)
        if tmp_P != tmp_E(0) and tmp_p not in data:
            data[tmp_p] = tmp_P
    with open("./data", "wb") as fp:
        pickle.dump(data, fp)

Then I calculate SERVER_SECRET_KEY with CRT. I don't know why but a curve point with relatively small prime order often gives infinity point even if multiplied by any integer. So I need to skip such points.

We can't distinguish the sign of SERVER_SECRET_KEY mod b_i, so I first recover SERVER_SECRET_KEY^2 and then calculate sqrt of it.

solve.sage
import hmac
import json
import pickle
import random
import string
from base64 import b64decode, b64encode
from dataclasses import dataclass
from hashlib import sha256

from Crypto.Util.number import bytes_to_long, long_to_bytes
from Crypto.Cipher import AES
from tqdm import tqdm
from pwn import remote, context


@dataclass
class HTTPRequest:
    method: str = ""
    uid: str = ""
    password: str = ""
    session: str = ""
    secret: str = ""
    path: str = ""

    def to_json(self):
        return json.dumps(self.__dict__)


# P256
p = 115792089210356248762697446949407573530086143415290314195533631308867097853951
n = 115792089210356248762697446949407573529996955224135760342422259061068512044369
a = -3
b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
Gx = 0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296
Gy = 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5
E = EllipticCurve(GF(p), [a, b])
G = E(Gx, Gy)


def register(uid: str):
    tmp = HTTPRequest(method="POST", uid=uid, path="/register.html").to_json()
    io.sendlineafter(b"> ", tmp.encode())
    io.recvuntil(b"token : ")
    ret = io.recvline().strip().decode()
    return b64decode(ret)


def login(uid: str, password: bytes):
    tmp = HTTPRequest(method="POST", uid=uid, password=b64encode(password).decode(), path="/login.html").to_json()
    io.sendlineafter(b"> ", tmp.encode())
    ret = io.recvline().decode().strip()
    if ret == "Unauthorized":
        return None
    ret = io.recvuntil(b"session : ")
    if b"session : " not in ret:
        return None
    return io.recvline().strip().decode()


def flag(session: str, secret: bytes):
    tmp = HTTPRequest(method="POST", session=session, secret=b64encode(secret).decode(), path="/flag.html").to_json()
    io.sendlineafter(b"> ", tmp.encode())
    return io.recvline().strip().decode()


def pow():
    io.recvuntil(b"PoW > ")
    pow = io.recvline().strip().decode()
    while True:
        tmp = "".join(random.choices(string.ascii_letters + string.digits, k=16))
        if sha256((pow + tmp).encode()).digest()[-3:] == b"\x00\x00\x00":
            io.sendline(tmp.encode())
            return


context.log_level = "DEBUG"
io = remote("43.202.3.171", int(8081))
pow()
token = register("ADMIN_admin")
pub = E(bytes_to_long(token[:32]), bytes_to_long(token[32:64]))
ct = token[64:-32]
tag = token[-32:]
session = login("ADMIN", token)

with open("./data", "rb") as fp:
    data = pickle.load(fp)
a_list = []
b_list = []
context.log_level = "INFO"
for tmp_p in tqdm(sorted(data.keys())):
    if tmp_p in b_list:
        continue
    tmp_P = data[tmp_p]
    for i in tqdm(range(tmp_p)):
        tmp_Q = tmp_P * i
        try:
            tmp_key = long_to_bytes(int(tmp_Q.x()), 32)
        except ZeroDivisionError:
            tmp_key = b"\x00" * 32
        tmp_key1 = tmp_key[:16]
        tmp_key2 = tmp_key[16:]
        tmp_cipher = AES.new(tmp_key1, AES.MODE_ECB)
        tmp_ct = tmp_cipher.encrypt(b"ADMIN_admin_GUES")
        tmp_token = long_to_bytes(int(tmp_P.x()), 32) + long_to_bytes(int(tmp_P.y()), 32) + tmp_ct
        tmp_tag = hmac.new(tmp_key2, tmp_token, sha256).digest()
        tmp_token += tmp_tag
        tmp_session = login("ADMIN", tmp_token)
        if tmp_session is not None:
            break
    if i != 0:  # needed, but don't know why
        a_list.append(i)
        b_list.append(tmp_p)
    print(prod(b_list), len(b_list))
    if prod(b_list) > n**2:
        break

skey_mod_n = int(sqrt(int(crt([a**2 for a in a_list], b_list))))
for i in range(2**8):
    ans = flag(session, long_to_bytes(skey_mod_n + n * i, 33))
    if "flag" in ans:
        print(ans)

The timeout is very strict, so I need to run this script on an EC2 instance in Korea region.

codegate2024{aedcdae5629637cdc74be2aed2cdf5eed9bd2122d1e34f96baa3aab71f0af5b99d2027336052425fa40e73210c0de727e8b7f5}

Cogechan_Dating_Game

15 solves

server.py
#!/usr/bin/python3

import Character
import load_and_save

import base64
import sys
import socket
import os
import random

EAT_COMMAND = 1
PWN_COMMAND = 2
SLEEP_COMMAND = 3
DATE_COMMAND = 4
SAVE_COMMAND = 5

DEBUG = True

def read_flag():
    with open("flag", "r") as f:
        flag = f.read()
    return flag

def load(ID, PW):
    status, character_load = load_and_save.load_game(ID, PW)
    if status == load_and_save.LOAD_SUCCESS:
        character = character_load
        return status, character
    
    new_character = Character.Character()
    new_character.stamina = 100
    return status, new_character

def go(sock):
    sock.settimeout(60) # No response for 60s then connection will be closed.
    # trying to load a save file based on ID, PW first
    ID_len = int.from_bytes(sock.recv(2), 'little')
    ID = sock.recv(ID_len).decode()
    PW_len = int.from_bytes(sock.recv(2), 'little')
    PW = sock.recv(PW_len).decode()

    status, character = load(ID, PW)
    print(len(character.nickname), character.nickname, character.stamina, character.intelligence, character.friendship)
    print(status)

    sock.send(status.to_bytes(1, 'little'))

    if status == load_and_save.LOAD_SUCCESS:
        sock.send(len(character.nickname).to_bytes(2, 'little') + character.nickname.encode())
        sock.send(character.day.to_bytes(4, 'little'))
        sock.send(character.stamina.to_bytes(4, 'little'))
        sock.send(character.intelligence.to_bytes(4, 'little'))
        sock.send(character.friendship.to_bytes(4, 'little'))
        
    if status != load_and_save.LOAD_SUCCESS:
        nickname_len = int.from_bytes(sock.recv(2), 'little')
        character.nickname = sock.recv(nickname_len).decode('utf-8', 'ignore')
        character.stamina = 100

    while True:
        com = int.from_bytes(sock.recv(1), 'little')
        if com == 0: # Meaning that connection is closed
            if DEBUG:
                print("connection closed")
            exit()

        elif com == EAT_COMMAND:
            rnd = random.randint(1, 4)
            sock.send(rnd.to_bytes(1, 'little'))
            character.stamina += rnd
            character.day += 1

        elif com == PWN_COMMAND:
            rnd = random.randint(1, 4)
            sock.send(rnd.to_bytes(1, 'little'))
            if character.stamina >= 10:
                character.stamina -= 10
                character.intelligence += rnd
                character.day += 1

        elif com == SLEEP_COMMAND:
            rnd = random.randint(1, 4)
            sock.send(rnd.to_bytes(1, 'little'))
            character.stamina += rnd
            character.day += 1
            pass

        elif com == DATE_COMMAND:
            rnd = random.randint(1, 4)
            sock.send(rnd.to_bytes(1, 'little'))
            if character.stamina >= 10 and character.intelligence.bit_length() >= character.friendship:
                character.stamina -= 10
                character.friendship += 1
                character.day += 1
                if character.friendship == 34:
                    flag = read_flag()
                    sock.send(len(flag).to_bytes(2, 'little') + flag.encode())
                
        elif com == SAVE_COMMAND:
            file_data_enc_len = int.from_bytes(sock.recv(2), 'little')
            file_data_enc = sock.recv(file_data_enc_len)
            tag = sock.recv(16)
            status = load_and_save.save_game(ID, PW, character, file_data_enc, tag)
            sock.send(status.to_bytes(1, 'little'))
        

def main():
    if len(sys.argv) != 3:
        print(f"usage : {sys.argv[0]} [host] [port]")
        return

    ip = sys.argv[1]
    port = int(sys.argv[2])
    sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)

    sock.bind((ip, port))
    sock.listen(0x10)

    while True:
        client_sock, addr = sock.accept()
        if DEBUG:
            print(f"[+] new connection - {addr[0]}")
        pid = os.fork()
        if pid == 0:
            try:
                go(client_sock)
            except Exception as e:
                if DEBUG:
                    print(e, '-', addr[0])
                client_sock.close()
            exit()
        else:
            client_sock.close()


if __name__ == "__main__":
    main()

In order to get a flag, we need to increase friendship to 34. We can increase friendship by DATE_COMMAND if stamina >= 10 and intelligence.bit_length() >= friendship. Since the server state is saved in a file, we should make an evil state to increase friendship to 33 and intelligence to 0xFFFFFFFF.

I made file_data_enc, tag, ID, PW1, PW2 with the following conditions:

• DEC1(file_data_enc) = nickname_len1|nickname1|day1|...|friendship1|some_bytes|pad
• DEC2(file_data_enc) = length_before_day2|some_bytes|day2|...|friendship2|some_bytes|pad
• file_data_enc = some_bytes|C (0x10)|some_bytes (0x10)

where DEC1 and DEC2 are decryption functions of AES-GCM with keys from PW1 and PW2, respectively.

After that, I send file_data_enc in SAVE, execute PWN -> DATE and get the flag.

solve.sage
import string
import random
import hashlib

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from Crypto.Util.number import bytes_to_long, long_to_bytes
from pwn import remote
from tqdm import tqdm

import Character


X = GF(2).polynomial_ring().gen()
poly = X ** 128 + X ** 7 + X ** 2 + X ** 1 + 1
F = GF(2 ** 128, name='a', modulus=poly)
R.<x> = PolynomialRing(F)


def decrypt_and_parse_save_data(key, nonce, save_data, tag):
    cipher = AES.new(key, AES.MODE_GCM, nonce)
    file_data = unpad(cipher.decrypt_and_verify(save_data, tag), 16)
    idx = 0
    nickname_len = int.from_bytes(file_data[idx:idx+2], 'little')
    idx += 2
    nickname = file_data[idx:idx+nickname_len].decode('utf-8', 'ignore')
    idx += nickname_len
    day = int.from_bytes(file_data[idx:idx+4], 'little')
    idx += 4
    stamina = int.from_bytes(file_data[idx:idx+4], 'little')
    idx += 4
    intelligence = int.from_bytes(file_data[idx:idx+4], 'little')
    idx += 4        
    friendship = int.from_bytes(file_data[idx:idx+2], 'little')
    print(nickname_len, nickname, stamina, intelligence, friendship)
    character = Character.Character(nickname, day, stamina, intelligence, friendship)
    return character


def tobin(x, n):
    x = Integer(x)
    nbits = x.nbits()
    assert nbits <= n
    return x.bits() + [0] * (n - nbits)


def frombin(v):
    return int("".join(map(str, v)), 2)


def toF(x):
    x = frombin(tobin(x, 128))
    return F.fetch_int(x)


def fromF(x):
    x = x.integer_representation()
    x = frombin(tobin(x, 128))
    return x


ID = b"abcdhogetaroABCDHOGETARO12345678900"  # random
PW1 = b"zxcvvBIIDFSFJIO78932y7faodfjaou"  # random
id_hash = hashlib.sha256(ID).digest()
pw_hash1 = hashlib.sha256(PW1).digest()
nonce = id_hash[:12]
file_name = id_hash[16:24].hex()
key1 = pw_hash1[:16]
file_data1 = b'\x03\x00You\x00\x00\x00\x00d\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'  # default
cipher1 = AES.new(key1, AES.MODE_GCM, nonce)
file_data_enc = cipher1.encrypt(file_data1)
idx = 0
nickname_len = int.from_bytes(file_data1[idx:idx+2], 'little')

while True:
    PW2 = b"zxcvvBIIDFSFJIO78932y7faodfjaou" + "".join(random.choices(string.ascii_letters, k=8)).encode()
    pw_hash2 = hashlib.sha256(PW2).digest()
    key2 = pw_hash2[:16]
    cipher2 = AES.new(key2, AES.MODE_GCM, nonce)
    file_data2 = cipher2.decrypt(file_data_enc)
    idx = 0
    nickname_len2 = int.from_bytes(file_data2[idx:idx+2], 'little')
    if 100 < nickname_len2 < 300 and (2 + nickname_len2) % 16 == 0:
        break

day = 1337  # random
stamina = 11337  # random
intelligence = 0xffffffff
friendship = 33
payload = file_data1 + (nickname_len2 - len(file_data1) + 2) * b"\x00" + int(day).to_bytes(4, 'little') + int(stamina).to_bytes(4, 'little') + int(intelligence).to_bytes(4, 'little') + int(friendship).to_bytes(4, 'little')
cipher2 = AES.new(key2, AES.MODE_GCM, nonce)
enc_payload2 = file_data_enc[:len(file_data1)] + cipher2.encrypt(payload)[len(file_data1):]

while True:
    cipher1 = AES.new(key1, AES.MODE_GCM, nonce)
    tmp = pad(cipher1.decrypt(enc_payload2) + os.urandom(6 + random.randint(2, 100) * 16), 16)
    cipher1 = AES.new(key1, AES.MODE_GCM, nonce)
    tmp_enc = cipher1.encrypt(tmp)
    try:
        cipher2 = AES.new(key2, AES.MODE_GCM, nonce)
        payload2 = unpad(cipher2.decrypt(tmp_enc), 16)
        enc_payload = tmp_enc
        break
    except ValueError as e:
        continue

cipher1 = AES.new(key1, mode=AES.MODE_ECB)
H1 = toF(bytes_to_long(cipher1.encrypt(b"\x00" * 16)))
S1 = toF(bytes_to_long(cipher1.encrypt(nonce + b"\x00\x00\x00\x01")))
cipher2 = AES.new(key2, mode=AES.MODE_ECB)
H2 = toF(bytes_to_long(cipher2.encrypt(b"\x00" * 16)))
S2 = toF(bytes_to_long(cipher2.encrypt(nonce + b"\x00\x00\x00\x01")))
L = toF(int("%016x%016x" % (0, 8*len(enc_payload)), 16))
Cs = []
for i in tqdm(range(0, len(enc_payload), 16)):
    Cs.append(toF(bytes_to_long(enc_payload[i:i+16])))
Cs_payload = Cs.copy()
Cs_payload[-2] = x
T1 = toF(0)
for i, C in enumerate(Cs_payload[::-1], 2):
    T1 += C * H1**i
T1 += L * H1 + S1
T2 = toF(0)
for i, C in enumerate(Cs_payload[::-1], 2):
    T2 += C * H2**i
T2 += L * H2 + S2
f = T1 - T2
roots = f.roots()
tmp = roots[0][0]
Cs_payload[-2] = tmp
T1 = toF(0)
for i, C in enumerate(Cs_payload[::-1], 2):
    T1 += C * H1**i
T1 += L * H1 + S1
tag = long_to_bytes(fromF(T1))
final_enc_payload = enc_payload[:-32] + long_to_bytes(fromF(tmp)) + enc_payload[-16:]
print(f"{len(final_enc_payload) = }")

# check
character1 = decrypt_and_parse_save_data(key1, nonce, final_enc_payload, tag)
character2 = decrypt_and_parse_save_data(key2, nonce, final_enc_payload, tag)

# save evil state
io = remote("3.35.166.110", int(3434))
io.send(len(ID).to_bytes(2, 'little') + ID)
io.send(len(PW1).to_bytes(2, 'little') + PW1)
status = io.recv(1)
print(status)
if status[0] == 1: # LOAD_SUCCESS
    nickname_len = int.from_bytes(io.recv(2), 'little')
    print(nickname_len)
    character.nickname = io.recv(nickname_len).decode()
    character.day = int.from_bytes(io.recv(4), 'little')
    character.stamina = int.from_bytes(io.recv(4), 'little')
    character.intelligence = int.from_bytes(io.recv(4), 'little')
    character.friendship = int.from_bytes(io.recv(4), 'little')
else:
    print("restart")
SAVE_COMMAND = 5
io.send(SAVE_COMMAND.to_bytes(1, 'little'))
io.send(len(final_enc_payload).to_bytes(2, 'little') + final_enc_payload)
io.send(tag)
status = int.from_bytes(io.recv(1), 'little')
assert status == 11
io.close()

# get flag
io = remote("3.35.166.110", int(3434))
io.send(len(ID).to_bytes(2, 'little') + ID)
io.send(len(PW2).to_bytes(2, 'little') + PW2)
status = io.recv(1)
if status[0] == 1: # LOAD_SUCCESS
    nickname_len = int.from_bytes(io.recv(2), 'little')
    character.nickname = io.recv(nickname_len + 1).decode()  # NOTE: +1 is needed because of something (maybe because decoding of some nickname bytes are ignored)
    character.day = int.from_bytes(io.recv(4), 'little')
    character.stamina = int.from_bytes(io.recv(4), 'little')
    character.intelligence = int.from_bytes(io.recv(4), 'little')
    character.friendship = int.from_bytes(io.recv(4), 'little')
else:
    print("restart")
io.send(int(2).to_bytes(1, 'little'))
_ = io.recv(1)
io.send(int(4).to_bytes(1, 'little'))
_ = io.recv(1)
flag_len = int.from_bytes(io.recv(2), 'little')
flag = io.recv(flag_len).decode()
io.close()

codegate2024{c951863c5f95494a6045e84867625645dd8fb2d062d8c87c3ef89a4b35501e64d912f4698953e7bc19b7d36f24a3aea197dc960d601530}

FactorGame

34 solves

FactorGame.py
import sys
from random import SystemRandom
from Crypto.Util.number import getStrongPrime

def show(data):
    data = "".join(map(str, data))
    sys.stdout.write(data)
    sys.stdout.flush()

def input():
    return sys.stdin.readline().strip()

def main():
    show('Welcome to the FactorGame\n')
    show("The Game is simple factor N given N and bits of p, q\n")
    show("you have 5 lives for each game\n")
    show("win 8 out of 10 games to get the flag\n")
    show("good luck\n\n")
    
    known = 264
    success = 0

    for i in range(10):
        show(f"game{i + 1} start!\n")
        life = 5
        while life > 0:
            p = getStrongPrime(512)
            q = getStrongPrime(512)
            N = p * q

            cryptogen = SystemRandom()
            counter = 0

            while counter < 132 * 2 or counter > 137 * 2:
                counter = 0
                p_mask = 0
                q_mask = 0
                for _ in range(known):
                    if cryptogen.random() < 0.5:
                        p_mask |= 1
                        counter += 1
                    if cryptogen.random() < 0.5:
                        q_mask |= 1
                        counter += 1
                    p_mask <<= 1
                    q_mask <<= 1

            p_redacted = p & p_mask
            q_redacted = q & q_mask

            show(f'p : {hex(p_redacted)}\n')
            show(f'p_mask : {hex(p_mask)}\n')
            show(f'q : {hex(q_redacted)}\n')
            show(f'q_mask : {hex(q_mask)}\n')
            show(f'N : {hex(N)}\n')

            show('input p in hex format : ')
            inp = int(input(), 16)
            show('input q in hex format : ')
            inq = int(input(), 16)

            if inp == p and inq == q:
                success += 1
                show('success!\n')
                break
            else:
                show('wrong p, q\n')
                life -= 1
                show(f'{life} lives left\n')

    if success >= 8:
        show('master of factoring!!\n')
        flag = open('/flag', 'r').read()
        show(f'here is your flag : {flag}\n')
    else:
        show('too bad\n')
        show('mabye next time\n')
    exit()

if __name__ == "__main__":
    main()

In order to get a flag, we need to factorize N with partially known p and q.

From randomly distributed known bits of p and q, we can recover lower bits of p and q. This can be done by a solver I wrote in the past. This solver recovers factors from lower bits by BFS. But this solver doesn't finish before it finds the whole factors, so I need to modify it to stop when it reaches 264 bits and returns the all candidates.

After we get lower bits of them, we should recover higher bits. Since 264 bits out of 512 bits are known, we can do this by coppersmith method. But the server has a strict timeout, so I need to make coppersmith faster.

solve.py
import subprocess

import factor  # my solver
from pwn import remote
from multiprocessing import Pool


def coppersmith(args):
    p_lsb, N = args
    proc = subprocess.run(["sage", "./copper.sage", str(p_lsb), str(N)], stdout=subprocess.PIPE, stderr=subprocess.PIPE)
    try:
        p = int(proc.stdout)
        q = N // p
        assert p * q == N
        return p, q
    except:
        return None, None


while True:
    skip = 0
    end = False
    io = remote("3.38.106.210", 8287)
    for round in range(10):
        print(f"{round = }")
        if end:
            break
        if skip > 2:
            break
        for life in range(5):
            print(f"{life = }")
            io.recvuntil(b"p : ")
            p_redacted = int(io.recvline(), 16)
            io.recvuntil(b"p_mask : ")
            p_mask = int(io.recvline(), 16)
            io.recvuntil(b"q : ")
            q_redacted = int(io.recvline(), 16)
            io.recvuntil(b"q_mask : ")
            q_mask = int(io.recvline(), 16)
            io.recvuntil(b"N : ")
            N = int(io.recvline(), 16)
            p_vec = []
            q_vec = []
            for i in range(264):
                if (p_mask >> i) & 1 == 1:
                    p_vec.append((p_redacted >> i) & 1)
                else:
                    p_vec.append(-1)
                if (q_mask >> i) & 1 == 1:
                    q_vec.append((q_redacted >> i) & 1)
                else:
                    q_vec.append(-1)
            for _ in range(0):
                p_vec.append(-1)
                q_vec.append(-1)
            p_vec = p_vec[::-1]
            q_vec = q_vec[::-1]
            pq_cands = factor.from_vector_all(N, p_vec, q_vec)
            print(f"{len(pq_cands) = }")
            if len(pq_cands) > 20:
                print("skip because of too many candidates")
                io.sendlineafter(b"format : ", hex(0).encode())
                io.sendlineafter(b"format : ", hex(0).encode())
                continue
            with Pool(2) as pool:
                pq_cands = pool.map(coppersmith, [(pq[0], N) for pq in pq_cands])
            p, q = list(filter(lambda x: x[0] is not None, pq_cands))[0]
            assert p * q == N
            io.sendlineafter(b"format : ", hex(p).encode())
            io.sendlineafter(b"format : ", hex(q).encode())
            break
        else:
            skip += 1
    if not end and skip < 3:
        print(io.recvline())
        print(io.recvline())
        print(io.recvline())
        print(io.recvline())
        print(io.recvline())
        print(io.recvline())
        print(io.recvline())
        print(io.recvline())
        print(io.recvline())
        io.close()
        break
    else:
        io.close()

coppersmith.sage
import re
import subprocess
import sys


# from sagemath, but modified in order to speed up
def small_roots(f, X=None, beta=1.0, epsilon=None, **kwds):

    self = f
    from sage.misc.verbose import verbose
    from sage.matrix.constructor import Matrix
    from sage.rings.real_mpfr import RR

    N = self.parent().characteristic()

    if not self.is_monic():
        raise ArithmeticError("Polynomial must be monic.")

    beta = RR(beta)
    if beta <= 0.0 or beta > 1.0:
        raise ValueError("0.0 < beta <= 1.0 not satisfied.")

    f = self.change_ring(ZZ)

    P,(x,) = f.parent().objgens()

    delta = f.degree()

    if epsilon is None:
        epsilon = beta/8
    verbose("epsilon = %f"%epsilon, level=2)

    m = max(beta**2/(delta * epsilon), 7*beta/delta).ceil()
    verbose("m = %d"%m, level=2)

    t = int( ( delta*m*(1/beta -1) ).floor() )
    verbose("t = %d"%t, level=2)

    if X is None:
        X = (0.5 * N**(beta**2/delta - epsilon)).ceil()
    verbose("X = %s"%X, level=2)

    # we could do this much faster, but this is a cheap step
    # compared to LLL
    g  = [x**j * N**(m-i) * f**i for i in range(m) for j in range(delta) ]
    g.extend([x**i * f**m for i in range(t)]) # h

    B = Matrix(ZZ, len(g), delta*m + max(delta,t) )
    for i in range(B.nrows()):
        for j in range( g[i].degree()+1 ):
            B[i,j] = g[i][j]*X**j

    # B =  B.LLL(**kwds)
    B = flatter(B)  # use flatter

    f = sum([ZZ(B[0,i]//X**i)*x**i for i in range(B.ncols())])
    R = f.roots()

    ZmodN = self.base_ring()
    # roots = set([ZmodN(r) for r,m in R if abs(r) <= X])
    roots = set([ZmodN(r) for r,m in R])  # NOTE: remove strict range condition
    Nbeta = N**beta
    # return [root for root in roots if N.gcd(ZZ(self(root))) >= Nbeta]
    return list(roots)  # NOTE: remove gcd >= N**beta condition


def flatter(mat):
    s = "[\n"
    for i in range(mat.nrows()):
        s += "[" + " ".join(map(str, mat[i])) + "]\n"
    s += "]"
    ret = subprocess.check_output(["flatter"], input=s.encode())
    return matrix(mat.base_ring(), mat.nrows(), mat.ncols(), map(mat.base_ring(), re.findall(r"-?\d+", ret.decode())))


assert len(sys.argv) == 3
p_lsb = int(sys.argv[1])
N = int(sys.argv[2])

set_verbose(0)

PR.<p_msb> = PolynomialRing(Zmod(N))
f = 2**511 + p_msb * 2**264 + p_lsb
f = f.monic()
roots = small_roots(f, beta=0.5, epsilon=0.011)
assert len(roots) <= 1
if len(roots) > 0:
    p = gcd(int(f(roots[0])), N)
    print(p)
else:
    print(None)

codegate2024{d6fc5dcb451243a74a39f407d760ed7ded590d70ed4b0024b1de5513c830e668e744a470eab7329302c1145e5f041ba5f2cbda8364db9c}