ångstromCTF 2021 - I'm so Random

問題概要

Aplet's quirky and unique so he made my own PRNG! It's not like the other PRNGs, its absolutely unbreakable!

nc crypto.2021.chall.actf.co 21600

chall.py

import time
import random
import os

class Generator():
    DIGITS = 8
    def __init__(self, seed):
        self.seed = seed
        assert(len(str(self.seed)) == self.DIGITS)

    def getNum(self):
        self.seed = int(str(self.seed**2).rjust(self.DIGITS*2, "0")[self.DIGITS//2:self.DIGITS + self.DIGITS//2])
        return self.seed


r1 = Generator(random.randint(10000000, 99999999))
r2 = Generator(random.randint(10000000, 99999999))


query_counter = 0
while True:
    query = input("Would you like to get a random output [r], or guess the next random number [g]? ")
    if query.lower() not in ["r", "g"]:
        print("Invalid input.")
        break
    else:
        if query.lower() == "r" and query_counter < 3:
            print(r1.getNum() * r2.getNum())
            query_counter += 1;
        elif query_counter >= 3 and query.lower() == "r":
            print("You don't get more random numbers!")
        else:
            for i in range(2):
                guess = int(input("What is your guess to the next value generated? "))
                if guess != r1.getNum() * r2.getNum():
                    print("Incorrect!")
                    exit()
            with open("flag", "r") as f:
                fleg = f.read()
            print("Congrats! Here's your flag: ")
            print(fleg)
            exit()

中々複雑な暗号機構をしてますね...暗号機をコピーして証拠に暗号化出来るかテストを通せばOKです。が、コピーのための材料は3つしかありません。

解説

少し試せば分かりますが、実際にコピーの段階で渡される数値は結構大きいです。また、与えられる数値は2つの数の積ですが、2つの数はともに$10^8$未満であることが保証されています。この$10^8$は全探索が可能です。

与えられた数値を「両方の数値が$10^8$未満」という制限で分解します。複数候補が存在することが考えられますが、これに関しては複数回の試行により結構な確率で候補を1つに絞りこむことが可能です。

かなり競プロチックな問題ですが、解くとこんな感じです。

solve.py

from pwn import *

r = remote("crypto.2021.chall.actf.co",  21600)

r.recvuntil(b"Would you like to get a random output [r], or guess the next random number [g]? ")
r.sendline(b"r")
num = int(r.recvline().decode())

def updateVal(x):
    return int(str(x ** 2).rjust(16, "0")[4:12])

sml = num // 10**8
candidates = set()
for i in range(sml, 10**8):
    if num % i == 0:
        j = num // i
        candidates.add((min(i, j), max(i, j)))

for _ in range(2):
    r.recvuntil(b"Would you like to get a random output [r], or guess the next random number [g]? ")
    r.sendline(b"r")
    num = int(r.recvline().decode())

    next_candidates = set()
    for candidate in candidates:
        i, j = candidate
        i = updateVal(i)
        j = updateVal(j)
        if i * j == num:
            next_candidates.add((min(i, j), max(i, j)))
    candidates = next_candidates

print(candidates)
assert(len(candidates) == 1)
i, j = list(candidates)[0]

r.recvuntil(b"Would you like to get a random output [r], or guess the next random number [g]? ")
r.sendline(b"g")
for _ in range(2):
    r.recvuntil(b"What is your guess to the next value generated? ")
    i = updateVal(i)
    j = updateVal(j)
    payload = str(i * j)
    r.sendline(payload.encode())

r.interactive()