Quintec writeups and other thoughts

corCTF 2022

Another year, another successful CTF :) with a rather impressive 36.96 / 37.380 rating on CTFTime.

Sadly, behind the scenes, this year was less successful for me specifically - besides the two challenges that ended up in the CTF, I had two harder crypto challenges that did not make it - one which I could not fit well into the CTF format, and one that I ended up not solving due to not having time during the summer. Maybe you’ll see them in the future :)

Enough regrets, here are writeups for my challenges in corCTF 2022:

hidE

hidE was a short and simple RSA challenge. The source looks like this:

#!/usr/local/bin/python
import random
import time
import math
import binascii
from Crypto.Util.number import *

p, q = getPrime(512), getPrime(512)
n = p * q
phi = (p - 1) * (q - 1)

flag = open('./flag.txt').read().encode()

random.seed(int(time.time()))

def encrypt(msg):
    e = random.randint(1, n)
    while math.gcd(e, phi) != 1:
        e = random.randint(1, n)
    pt = bytes_to_long(msg)
    ct = pow(pt, e, n)
    return binascii.hexlify(long_to_bytes(ct)).decode()


def main():
    print('Secure Encryption Service')
    print('Your modulus is:', n)
    while True:
        print('Options')
        print('-------')
        print('(1) Encrypt flag')
        print('(2) Encrypt message')
        print('(3) Quit')
        x = input('Choose an option: ')
        if x not in '123':
            print('Unrecognized option.')
            exit()
        elif x == '1':
            print('Here is your encrypted flag:', encrypt(flag))
        elif x == '2':
            msg = input('Enter your message in hex: ')
            print('Here is your encrypted message:', encrypt(binascii.unhexlify(msg)))
        elif x == '3':
            print('Bye')
            exit()

if __name__ == '__main__':
    main()

Taking a quick first glance through, this part should stand out:

random.seed(int(time.time()))

def encrypt(msg):
    e = random.randint(1, n)
    while math.gcd(e, phi) != 1:
        e = random.randint(1, n)
    pt = bytes_to_long(msg)
    ct = pow(pt, e, n)
    return binascii.hexlify(long_to_bytes(ct)).decode()

The random is seeded with the current time (in seconds) when we connect to the server, which means we should be able to easily recover any values that come from it. The random is used to generate \(e\) values for RSA, after checking that they are compatible with the (not seeded) randomly generated \(n\).

Due to server lag and us not knowing the value of phi, we can’t exactly replicate this process every time we connect, but we can solve this by trying multiple values of time.time() and pairs of random.randint().

Seeing that we can encrypt the flag multiple times with different \(e\) values (that we are able to find) points towards a common modulus attack. The idea is as follows: encrypt the same message \(m\) using multiple \(e\) values to get multiple ciphertexts \(c_i\), which gives you these equations:

\[\begin{align*} c_1 &\equiv m^{e_1} \pmod{n} \\ c_2 &\equiv m^{e_2} \pmod{n} \end{align*}\]

Now note that if \(\text{gcd}(e_1, e_2) = 1\) (which happens most of the time due to how \(e\) is selected), then by Bézout’s identity we know that there exists \(a, b\) such that \(ae_1 + be_2 \equiv 1 \pmod{n}\). We can find such a pair of $a, b$ using the Extended Euclidean algorithm. Once we have such a pair, note that

\[c_1^a \cdot c_2^b \equiv m^{ae_1} \cdot m^{be_2} \equiv m^{ae_1+be_2} \equiv m \pmod{n}\]

so we can recover the original message in this way. My solve script is below:

from pwn import *
from Crypto.Util.number import *
import random, binascii
from gmpy2 import gcdext, invert

sh = process(['python3', './main.py'])
random.seed(int(time.time()))

sh.recvuntil(': ')
n = int(sh.recvline())

sh.recvuntil(': ')
sh.sendline('1')
sh.recvuntil(': ')

enc1 = bytes_to_long(binascii.unhexlify(sh.recvline().strip().decode()))
print(enc1)

sh.recvuntil(': ')
sh.sendline('1')
sh.recvuntil(': ')

enc2 = bytes_to_long(binascii.unhexlify(sh.recvline().strip().decode()))
print(enc2)

es = []
for i in range(10):
	es.append(random.randint(1, n))

#ngl i have no idea where this script comes from but it was in my files
def common_modulus_attack(c1, c2, e1, e2, n):
	gcd, s1, s2 = gcdext(e1, e2)
	if s1 < 0:
	    s1 = -s1
	    c1 = invert(c1, n)
	if s2 < 0:
	    s2 = -s2
	    c2 = invert(c2, n)
	v = pow(c1, s1, n)
	w = pow(c2, s2, n)
	m = (v * w) % n
	return m


for i in range(10):
	for j in range(i, 10):
		if i == j:
			continue
		dec = long_to_bytes(common_modulus_attack(enc1, enc2, es[i], es[j], n))
		if b'cor' in dec:
			print(dec.strip().decode())

msfrogofwar

This was a very fun and admittedly slightly silly misc challenge where the goal was to exploit and beat Stockfish in a chess game. To make it more fun, we designed some frog themed chess pieces, which you can find here, and if you are insane, you can try playing with them on lichess by installing this theme. You can see what the challenge looked like here.

Taking a look at the source code, you can see a rather suspicious function in app.py:

@socketio.on('options')
def engine_options(options):
    game.get(request.sid).msfrog.configure(options)

which leads to a function in enemy.py:

def configure(self, options):
        try:
            if "Hash" in options and options["Hash"] > 128:
                return
            if "Threads" in options and options["Threads"] > 1:
                return
            if "Debug Log File" in options:
                return
            self.engine.update_engine_parameters(options)
        except Exception as e:
            print(e)
            self.emit("chat", {"name": "🐸", "msg": "Error configuring engine"})

Hmm, interesting, this is exposed through the socket so we can configure the engine any way we want (except for a few options that would kill the server). Let’s see what sort of options we can configure using the official Stockfish GitHub.

A few should jump out at you:

UCI_LimitStrength

Enable weaker play aiming for an Elo rating as set by UCI_Elo. This option overrides Skill Level.

UCI_Elo

If enabled by UCI_LimitStrength, aim for an engine strength of the given Elo. This Elo rating has been calibrated at a time control of 60s+0.6s and anchored to CCRL 40/4.

Skill Level

Lower the Skill Level in order to make Stockfish play weaker (see also UCI_LimitStrength). Internally, MultiPV is enabled, and with a certain probability depending on the Skill Level a weaker move will be played.

Configuring either the first two or the last option should lower the skill level of Stockfish significantly, enough to beat it by using Stockfish on your own in 30 moves or less, which gives you the flag. (The way I did it was to set Skill Level to 0, which you can do in the JS console with socket.emit("options", {"Skill Level": 0}).)