[SECCON CTF 2022] janken vs kurenaif

prob.py

import os
import signal
import random
import secrets

FLAG = os.getenv("FLAG", "fake{cast a special spell}")


def janken(a, b):
    return (a - b + 3) % 3


signal.alarm(1000)
print("kurenaif: Hi, I'm a crypto witch. Let's a spell battle with me.")

witch_spell = secrets.token_hex(16)
witch_rand = random.Random()
witch_rand.seed(int(witch_spell, 16))
print(f"kurenaif: My spell is {witch_spell}. What about your spell?")

your_spell = input("your spell: ")
your_random = random.Random()
your_random.seed(int(your_spell, 16))

for _ in range(666):
    witch_hand = witch_rand.randint(0, 2)
    your_hand = your_random.randint(0, 2)

    if janken(your_hand, witch_hand) != 1:
        print("kurenaif: Could you come here the day before yesterday?")
        quit()

print("kurenaif: Amazing! Your spell is very powerful!!")
print(f"kurenaif: OK. The flag is here. {FLAG}")

It is well-known that python random module is not cryptophically secure. All we need is to find a integer seed which generates 666 target values. When 

 

I first tried to analyze the exact logic for the random module in python but it is too boring. Luckily I find this repository and it contains almost everything I want.

 

Since the whole code is too long, I will introduce a handmade method in Breaker class.

mersenne.py (partial)

class BreakerPy(Breaker):
    # ...
    def state_recovery_rand_partial(self, outputs):
        """
        state recovery for given prob
        """
        MT = [BitVec(f'MT[{i}]',32) for i in range(624)]
        values = []
        start_time = time()
        S = Solver()
        for i in range(len(outputs)):
            if i%624==0:
                self.twist_state(MT)
            S.add(LShR(self.tamper_state(MT[i%624]),30)==outputs[i])
        if S.check()==sat:
            print("time taken :",time()-start_time)
            model = S.model()
            mt = {str(i): model[i].as_long() for i in model.decls()}
            mt = [mt[f'MT[{i}]'] for i in range(len(model))]
            return mt
    # ...

 

I find a candidate mersenne state using state_recovery_rand_partial method then find a corresponding seed.

 

solver.py

from pwn import *
from mersenne import *
import random

def conv(a):
    return (a+1)%3

r = remote("janken-vs-kurenaif.seccon.games", 8080)

r.recvuntil("spell is ")
spell = r.recvuntil(".")[:-1]

print(spell)

witch_rand = random.Random()
witch_rand.seed(int(spell, 16))

outputs = [conv(witch_rand.randint(0, 2)) for _ in range(666)]


b = BreakerPy()
mt = b.state_recovery_rand_partial(outputs)

print("mt recovered")

R = random.Random()
R.setstate((3, tuple(mt) + (624,), None))

for i in range(666):
    assert(R.randint(0,2) == outputs[i])

print("assert passed")

R = random.Random()
#R.seed((1))
R.setstate((3, tuple(mt) + (624,), None))

output32 = [R.getrandbits(32) for _ in range(624)]
seeds = b.get_seeds_python(output32, 624)


if not seeds:
    exit()

print("!!! seeds!!!!", seeds)

seed_int = 0

for i in range(len(seeds)):
    seed_int |= (seeds[i] << (32*i))

r.sendline(hex(seed_int))

r.interactive()