Daily AlpacaHack - Linear Coffee Generator

2026/01/31

問題ソースコードは以下の通り。

問題ソースコード

import os
import hashlib
from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
 
flag = os.environ.get("FLAG", "Alpaca{dummy}").encode()
 
# You don't need to focus on encrypt_flag/decrypt_flag :)
def encrypt_flag(pt, params):
    key = hashlib.sha256(str(params).encode()).digest()
    cipher = AES.new(key, AES.MODE_CBC)
    return cipher.iv + cipher.encrypt(pad(pt, 16))
 
def decrypt_flag(ct, params):
    key = hashlib.sha256(str(params).encode()).digest()
    cipher = AES.new(key, AES.MODE_CBC, iv=ct[:16])
    return unpad(cipher.decrypt(ct[16:]), 16)
 
class LCG:
    def __init__(self):
        self.p = getPrime(64)
        self.a = getRandomRange(1, self.p)
        self.b = getRandomRange(1, self.p)
        self.s = getRandomRange(1, self.p)
 
    def serve_coffee(self):
        self.s = (self.a * self.s + self.b) % self.p
        return self.s
 
 
lcg = LCG()
enc_flag = encrypt_flag(flag, (lcg.p, lcg.a, lcg.b, lcg.s)).hex()
 
print("#1 order:", lcg.serve_coffee())
print("#2 order:", lcg.serve_coffee())
print("#3 order:", lcg.serve_coffee())
print("#4 order:", lcg.serve_coffee())
# If you can recover p, a, b, and s, you can get the flag using decrypt_flag(bytes.fromhex(enc_flag), (p, a, b, s))!
print("encrypted flag:", enc_flag)

64bitのランダムな素数 $p$ 、および $p$ 未満のランダムな整数 $a, b, s$ を用いて、以下のようにしてserve_coffeeの出力が計算されています。

$s_{n+1} = (a \cdot s_n + b) \mod p$

与えられた4つの出力から $p, a, b, s$ をすべて復元することができたらdecrypt_flagでフラグが得られます。これはLCG(Linear Congruential Generator)という疑似乱数生成器の一種です。

encrypt_flagとdecrypt_flagは(p, a, b, s)を使ってflagを暗号化/復号していますが、特定の値を計算できたらフラグが得られる、という形式の問題ではよくあるパターンで、これらの関数には特に脆弱性はありません。

まずは、与えられた4つの出力から式を立てましょう。出力をそれぞれ $s_1, s_2, s_3, s_4$ とすると、以下の4つの式が成り立ちます。

\begin{align*} s_1 &\equiv a \cdot s + b \pmod p \\ s_2 &\equiv a \cdot s_1 + b \pmod p \\ s_3 &\equiv a \cdot s_2 + b \pmod p \\ s_4 &\equiv a \cdot s_3 + b \pmod p \end{align*}

これらの式を変形して (既知の値からなる式) $\equiv 0 \pmod p$ の形に持っていきます。まず隣接する式同士を引き算して、 $b$ を消去します。

\begin{align*} s_2 - s_1 &\equiv a (s_1 - s) \pmod p \\ s_3 - s_2 &\equiv a (s_2 - s_1) \pmod p \\ s_4 - s_3 &\equiv a (s_3 - s_2) \pmod p \end{align*}

さらにこれらの式を使って、 $a$ も消去します。 2つ目と3つ目の式を使うと、 $(s_4 - s_3)(s_2 - s_1) \equiv (s_3 - s_2)^2 \pmod p$ が成り立ちます。ここから、 $(s_4 - s_3)(s_2 - s_1) - (s_3 - s_2)^2$ が $p$ の倍数であることが分かります。具体的にこの値を計算すると $18015186145068426177274734295463492132$ となります。これは素数ではなく、124bit程度と大きいため、pと別の数の積となっていると考えられます。この値を素因数分解してみると、 $2^2 \times 9197623 \times 37447334611 \times 13076220846716751461$ となります。ちなみに、ある程度高速な素因数分解アルゴリズムを使わないと時間がかかります。例えば、 $O(\sqrt N)$ 時間の試し割りアルゴリズムでは計算しているうちに地球が滅亡してしまいます。Daily AlpacaHackなのでせめて24時間以内には終わってほしいです。 Pythonであればsympy.ntheory.factorintや、SageMathのfactor関数を使うと一瞬で答えが求まります。それすら面倒であれば https://factordb.com などのオンラインサービスもあります。

さて、素因数のうち、64bitの素数は1つしかないので、 $13076220846716751461$ が $p$ であると分かります。次は $a$ を求めましょう。 $s_3 - s_2 \equiv a (s_2 - s_1) \pmod p$ という式から、 $a \equiv (s_3 - s_2) \cdot (s_2 - s_1)^{-1} \pmod p$ と求まります。 $(s_2 - s_1)^{-1} \pmod p$ はPythonであればpow(s2 - s1, -1, p)で計算できます。 $a$ も求まりました。次は $b$ です。 $s_2 \equiv a \cdot s_1 + b \pmod p$ という式を変形して、 $b \equiv (s_2 - s_1 \cdot a) \pmod p$ と求まります。最後に $s$ を求めましょう。 $s_1 \equiv a \cdot s + b \pmod p$ という式を変形して、 $s \equiv (s_1 - b) \cdot a^{-1} \pmod p$ と求まります。これで $p, a, b, s$ がすべて求まりました。あとはdecrypt_flagに与えてフラグを得ましょう。

これを実装したソルバは以下の通りです。

import hashlib
from sympy.ntheory import factorint
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
 
s1 = 4052328936969804578
s2 = 8676271689691567645
s3 = 2647032430467963079
s4 = 6612596210231769351
flag_enc = "0c5355c5bb76b2a86aa7cf53279fb2350883865f2ca7423ff47512278a59a8db1ed85e82e0d84c2fec52e29d0b3aefd97d791f11edf18efdf1febc07ae860b8b"
 
def decrypt_flag(ct, params):
    key = hashlib.sha256(str(params).encode()).digest()
    cipher = AES.new(key, AES.MODE_CBC, iv=ct[:16])
    return unpad(cipher.decrypt(ct[16:]), 16)
 
d1 = s2-s1
d2 = s3-s2
d3 = s4-s3
 
p = max(factorint(d2*d2 - d1*d3).keys())
a = d2*pow(d1,-1,p)%p
b = (s2-s1*a)%p
s = (s1-b)*pow(a,-1,p)%p
print(decrypt_flag(bytes.fromhex(flag_enc), (p,a,b,s)))

ちなみに、SageMathを使うと面倒な式変形を一切せずに、グレブナー基底を計算する関数に与えられた式をそのまま投げるだけで解けます。

PR = PolynomialRing(ZZ, "a, b, s")
a, b, s = PR.gens()
I = PR.ideal([
    s*a+b - s1,
    s1*a+b - s2,
    s2*a+b - s3,
    s3*a+b - s4,
]).groebner_basis()
print(I) # [a + 1466936314606773311942879293366691031, b + 3280619628752045602450999089964835177, s + 2922826573297502520907432861726796897, 4503796536267106544318683573865873033]
mul_p = int(I[3])
p = max(factorint(mul_p).keys())
a = int(I[0].univariate_polynomial().roots()[0][0] % p)
b = int(I[1].univariate_polynomial().roots()[0][0] % p)
s = int(I[2].univariate_polynomial().roots()[0][0] % p)
print(p, a, b, s) # 13076220846716751461 6534081916410610007 12854780772490122855 12938961673315310206
print(decrypt_flag(bytes.fromhex(flag_enc), (p, a, b, s)))

Writeups