tchen's blog.

The past or the future? (Daily Alpacahack B-SIDE) - writeup

JA

問題へのリンク

問題の概要

コードは以下のようになります。目標は、Pythonのrandomモジュールにおいて任意の32ビット乱数を観測し、

  1. そこからi個後の32ビット乱数を予想する
  2. 最初の観測した乱数からi個前の32ビット乱数を予想する
    のが目的となります。
import os
import random
import secrets

FLAG = os.getenv("FLAG", "fake_flag")
N = 128

rng = random.Random(secrets.randbits(64))

past = [rng.getrandbits(32) for _ in range(N)]

print("=== The Past or the Future? ===")
print("An oracle whispers... it only speaks in 32-bit omens.")
print("Menu: [1] consult the present  [2] name the future  [3] leave quietly")

pos = 0
while True:
    choice = input("> ").strip()
    if choice == "1":
        val = rng.getrandbits(32)
        print(f"[present] {val}")
        pos += 1
    elif choice == "2":
        i = secrets.randbelow(128)
        for _ in range(i):
            rng.getrandbits(32)
        ans = rng.getrandbits(32)
        print(f"The oracle points to the timeline: i = {i}")
        try:
            guess = int(input("Speak the next omen > ").strip(), 0)
        except Exception:
            print("The oracle squints. That was not a number.")
            raise SystemExit(0)
        if guess != ans:
            print("The timeline rejects your prophecy. Try again in another universe.")
            raise SystemExit(0)

        i = secrets.randbelow(N)
        print("The oracle turns its gaze backward.")
        print(f"The oracle asks: what was the omen at index i = {i}?")
        try:
            guess = int(input("Recall the past > ").strip(), 0)
        except Exception:
            print("The oracle frowns. That was not a number.")
            raise SystemExit(0)
        if guess != past[i]:
            print("Your memory fades. The past slips away.")
            raise SystemExit(0)
        break
    elif choice == "3":
        print("You turn away before the future notices you.")
        raise SystemExit(0)
    else:
        print("The oracle does not understand that ritual.")

print("The oracle smiles. You remembered the unrememberable.")
print(FLAG)

解法

Pythonのrandomモジュールはメルセンヌ・ツイスターを利用しており、624個サンプルを集めると内部状態を完全復元することができるとThe Future PathのWriteupで知っておりました。しかしその仕組みはよくわかっていないので、過去を遡る方法もよくわかりません。同Writeupで利用されているrandcrackモジュールに遡れる機能があればいいな、と思いgithubのREADME.mdを読むと、

As well as predicting future values, it can recover the previous states to predict earlier values, ones that came before the numbers you submit. After having submitted enough random numbers to clone the internal state (624), you can use the offset(n) method to offset the state by some number.

まさに欲しい機能があります！しかし、手元で試して見てもoffsetメソッドが存在しないというエラーになってしまいます。よく確認すると、この関数が追加されたのが2024/11/29、最新の0.2.0がリリースされたのが2022/06/25で、このコミットがリリースされていないことがわかります。したがって次のコマンドでインストールすれば使えるようになります。

pip install git+https://github.com/tna0y/Python-random-module-cracker

あとは、ドキュメントにある使い方の通りに使うだけです。またメルセンヌ・ツイスターの理解を放棄してしまった

ソルバー

from randcrack import RandCrack
from pwn import *

io = process(["python", "prob.py"])
# io = remote("34.170.146.252", 48606)

cracker = RandCrack()

for _ in range(624):
	io.sendlineafter(b"> ", b"1")
	cracker.submit(int(io.recvline().split(b" ")[1]))

io.sendlineafter(b"> ", b"2")

i = int(io.recvline().split(b"=")[1])
cracker.offset(i)

io.sendlineafter(b"Speak the next omen > ", str(cracker.predict_getrandbits(32)).encode())
cracker.offset(-i-1)

io.recvline()
i = int(io.recvline().split(b"=")[1][:-2])
cracker.offset(-128+i-624)

io.sendlineafter(b"Recall the past > ", str(cracker.predict_getrandbits(32)).encode())

print(io.recvline_contains(b"Alpaca"))