osu!gaming CTF 2024 Writeup - Learning cyber security by playing and enjoying CTFs

　「出なかったCTFに限って面白い問題が出題される」というマーフィーの法則（死語？）を打破する現実解の一つとして、「可能な限り多くのCTFに参加する」*1というのがあります。

　いろいろと宿題は溜まっていたのですが、3/2 に開催された「osu!gaming CTF 2024」に参加し、「lucky-roll-gaming」1問だけ解きました。

設問

　以下の 2 ファイルが与えられます。

「script.py」

from Crypto.Util.number import getPrime # https://pypi.org/project/pycryptodome/
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from random import randrange
from math import floor

def lcg(s, a, b, p):
    return (a * s + b) % p

p = getPrime(floor(72.7))
a = randrange(0, p)
b = randrange(0, p)
seed = randrange(0, p)
print(f"{p = }")
print(f"{a = }")
print(f"{b = }")

def get_roll():
    global seed
    seed = lcg(seed, a, b, p)
    return seed % 100

out = []
for _ in range(floor(72.7)):
    out.append(get_roll())
print(f"{out = }")

flag = open("flag.txt", "rb").read()
key = bytes([get_roll() for _ in range(16)])
iv = bytes([get_roll() for _ in range(16)])
cipher = AES.new(key, AES.MODE_CBC, iv)
print(cipher.encrypt(pad(flag, 16)).hex())

「out.txt」

p = 4420073644184861649599
a = 1144993629389611207194
b = 3504184699413397958941
out = [39, 47, 95, 1, 77, 89, 77, 70, 99, 23, 44, 38, 87, 34, 99, 42, 10, 67, 24, 3, 2, 80, 26, 87, 91, 86, 1, 71, 59, 97, 69, 31, 17, 91, 73, 78, 43, 18, 15, 46, 22, 68, 98, 60, 98, 17, 53, 13, 6, 13, 19, 50, 73, 44, 7, 44, 3, 5, 80, 26, 10, 55, 27, 47, 72, 80, 53, 2, 40, 64, 55, 6]
34daaa9f7773d7ea4d5f96ef3dab1bbf5584ecec9f0542bbee0c92130721d925f40b175e50587196874e14332460257b

検討

　線形合同法（mod p）による疑似乱数からの mod 100 での出力 72 個から先を予測すれば AES の鍵が手に入ります。

　これは、かの有名な 𝕮𝖗𝖞𝖕𝖙𝖔 𝖂𝖎𝖙𝖈𝖍 「kurenaif」さんの動画*2の内容を少しアレンジすれば解けそうな感じです。

www.youtube.com

方針

　前記動画では、線形合同法 48 ビットからの上位 4 ビットの出力 20 個から先の出力を予測していますが、本質的にはこの手法をそのまま利用すれば OK です。

　アレンジする必要があるのは、得られる出力が「上位 4 ビット」ではなく「mod 100での値」である点と、線形合同法の modulus は「2**48」ではなく「p」となる点です。前者は多少の手間となりますが、後者は逆元計算が楽になるだけなので結果的に難なくやれる感じです。

　また、手に入っている値の数は連続した 72 個があるので十分足りそうな気がします*3 。

ソルバ

from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
import random

class LCG:
  def __init__(self, a, b, m, seed):
    self.a = a
    self.b = b
    self.m = m
    self.state = seed
  def next_state(self):
    self.state = (self.a * self.state + self.b) % self.m
  def get_roll(self):
    self.next_state()
    return self.state %100

ct = bytes.fromhex("34daaa9f7773d7ea4d5f96ef3dab1bbf5584ecec9f0542bbee0c92130721d925f40b175e50587196874e14332460257b")
m = 4420073644184861649599
a = 1144993629389611207194
b = 3504184699413397958941
leaks = [39, 47, 95, 1, 77, 89, 77, 70, 99, 23, 44, 38, 87, 34, 99, 42, 10, 67, 24, 3, 2, 80, 26, 87, 91, 86, 1, 71, 59, 97, 69, 31, 17, 91, 73, 78, 43, 18, 15, 46, 22, 68, 98, 60, 98, 17, 53, 13, 6, 13, 19, 50, 73, 44, 7, 44, 3, 5, 80, 26, 10, 55, 27, 47, 72, 80, 53, 2, 40, 64, 55, 6]

u = len(leaks)
Y = vector(ZZ, [leaks[i+1] - leaks[i] for i in range(u-1)])
inv_100 = pow(100,-1,m)

A = matrix.identity(ZZ, u-1)
for i in range(u-1):
  if i == 0:
    A[i,i] = m
  else:
    A[i,0] = -1 * a^i
L = A.LLL()
K = vector(ZZ,[round(w / m) for w in inv_100 * L * Y])
E = ~L * (m * K - inv_100 * L * Y)
X = E * 100 + Y
seed = pow(a-1,-1,m) * (int(X[0])-b) % m

lcg = LCG(a, b, m, seed)

out = [seed%m]
for _ in range(floor(72.7)-1):
  out.append(lcg.get_roll())
#assert out == leaks

key = bytes([lcg.get_roll() for _ in range(16)])
iv = bytes([lcg.get_roll() for _ in range(16)])
cipher = AES.new(key, AES.MODE_CBC, iv)
pt = unpad(cipher.decrypt(ct),16)
print(pt.decode())