プログラム系統備忘録ブログ

記事中のコードは自己責任の下でご自由にどうぞ。

最終更新日

Daily AlpacaHack B-SIDE 2026/02/05～08 HellCouple write-up

CTF

Daily AlpacaHack B-SIDEでの、2026/02/05～08出題のHellCouple問題のwrite-up記事です。

[Crypto, Very Hard, Discrete Logarithm] HellCouple

脆弱なカップル！

配布ファイルとして、問題本体のchal.pyと、その出力のoutput.txtがありました。chal.pyは次の内容でした:

import secrets
import hashlib
from Crypto.Cipher import AES
import os

FLAG = os.getenv("FLAG", "Alpaca{dummy}").encode()

# https://datatracker.ietf.org/doc/html/rfc3526#section-2
p = 0xffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca237327ffffffffffffffff
g = 2

alice_private = secrets.randbelow(p)
bob_private = secrets.randbelow(p)

alice_public = pow(g, alice_private, p)
bob_public = pow(g, bob_private, p)

print("alice_public:", alice_public)
print("bob_public:", bob_public)
print("leak:", alice_private & (2**1500 - 1))

shared_key = pow(alice_public, bob_private, p)
assert shared_key == pow(bob_public, alice_private, p)
session_key = hashlib.sha256(shared_key.to_bytes(p.bit_length() // 8, "big")).digest()

cipher = AES.new(session_key, AES.MODE_CTR)
encrypted_flag = cipher.nonce + cipher.encrypt(FLAG)
print("encrypted_flag:", encrypted_flag.hex())

つまるところ、aliceの公開鍵 \text{alice_public}、bobの公開鍵 \text{bob_public}、それとaliceの秘密鍵 \text{alice_private}の下位1500-bitが分かっている状態で、Diffie-Hellman鍵共有結果 \text{shared_key}を求める問題です。もしも \text{alice_private}の情報がなければ \text{alice_private} = \log_{g} \text{alice_public}の離散対数問題を解く必要があり、難しいです。今回は \text{alice_private}の一部の情報があるので、効率的に解けると考えました。

REPLで pのビット数を調べました:

In [46]: p.bit_length()
Out[46]: 1536

\text{alice_private} \lt pであるため、 \text{alice_private}のうち未知のビット数は36-bitのようです。B-SIDEの問題というわけで、数日以内に解ければ良さそうです。

というわけで全探索するソルバーを書きました。なお、毎回pow(g, exp, p)を計算するのはかなり遅かったので、指数法則を使って乗算だけで済むようにしました。また、素直な実行だと全探索に約300時間かかりそうだったので、とりあえず8並列にしました:

#!/usr/bin/env python3

import hashlib
import multiprocessing

import tqdm
from Crypto.Cipher import AES

p = 0xFFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E088A67CC74020BBEA63B139B22514A08798E3404DDEF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7EDEE386BFB5A899FA5AE9F24117C4B1FE649286651ECE45B3DC2007CB8A163BF0598DA48361C55D39A69163FA8FD24CF5F83655D23DCA3AD961C62F356208552BB9ED529077096966D670C354E4ABC9804F1746C08CA237327FFFFFFFFFFFFFFFF
g = 2
# output.txt内容
alice_public = 1599718256377804952101531599498863772568230618694466120580310027783856775419774715324430490009702307955575844601185230178048816258775546297605599320433889688149788702236901234905522868569967416567225850806042222083340147485157993071805547560375509693951764934940304995906394917881355417525918023021173242172441340007873982292615475287840119272527822675409016385400712544820436845576792437659620501263257558269716031694407258972273378598219915938064730248662540644
bob_public = 1601509205497326911166665651407955633086809897508704527950455620720477838507803621126588237807460352033730891991811162559292107072226732941342412621198125808491110851607803610326932944231441277178997305795098725764729855265846212191447644979975042348063533857732774890088844866567954281331492269751048224888559719840307800593782696008426362668779570407212587612644451479819243906619852333855883749307751229874778873609891502901892234753096522217233589204630723331
leak = 18745015684416423248238358819116531099692322854758287583875043555248837262023679930415710097187512975438125769318401939978478358430852785607010460104247921522906629910012576819904488213243619895103769135299549586169221570769473234206574921382434244366730718275494665736161014808538417501350114510192342412033471326519013144824828968703748628325803878118375663318670612020895929494354336570752213975226257200515892803889402746161532447603042987169336605
encrypted_flag = bytes.fromhex(
    "fb2f1136cea7c67b1edba34d3741eeac8442e70924b03202352422a28237ee6f3fb6d493"
)
nonce = encrypted_flag[:8]
encrypted_flag_core = encrypted_flag[8:]


def try_decrypt(alice_private: int):
    shared_key = pow(bob_public, alice_private, p)
    session_key = hashlib.sha256(
        shared_key.to_bytes(p.bit_length() // 8, "big")
    ).digest()
    cipher = AES.new(session_key, AES.MODE_CTR, nonce=nonce)
    plain_flag = cipher.decrypt(encrypted_flag_core)
    if b"Alpaca" in plain_flag:
        print(plain_flag.decode())


# p.bit_length() => 1536
p_2_1500 = 2**1500
g_p_2_1500 = pow(g, p_2_1500, p)


def worker(begin, end):
    current = pow(g, leak, p)
    current *= pow(g_p_2_1500, begin, p)  # g^(begin*2^1500 + leak)
    current %= p

    # 1個は進捗がほしい
    for i in tqdm.trange(begin, end) if begin == 0 else range(begin, end):
        current *= g_p_2_1500
        current %= p
        if alice_public == current:
            message = f"""Found!!!!
{begin = }
{end = }
{i = }
{begin + i = }"""
            print(message)
            with open(f"result_{begin}.txt", "a") as f:
                f.write(message + "\n")
            alice_private = leak + p_2_1500 * begin + p_2_1500 * (i - begin + 1)
            try_decrypt(alice_private)


manager = multiprocessing.Manager()
WORKER_COUNT = 8
processes = []
for i in range(WORKER_COUNT):
    range_max = 2**37
    begin = (range_max // WORKER_COUNT) * i
    end = (range_max // WORKER_COUNT) * (i + 1)
    process = multiprocessing.Process(target=worker, args=(begin, end))
    process.start()
    processes.append(process)

for process in processes:
    process.join()

手元環境で実行すると、1並列あたり毎秒約9万iterationほどの速度が出て、全探索完了までには50時間～60時間ほどかかる計算でした。この速度なら、B-SIDEの本問題の開催期間の4日間以内に探索が終わると予想しました。

実行を開始して、しばらく放置して、ふと様子を見ると、実行開始から13時間後に \text{alice_private}を見つけていました！

$ ./solve.py
 24%|███████████████▉                                                  | 4151285644/17179869184 [13:46:53<48:56:04, 73956.78it/s]Found!!!!
begin = 51539607552
end = 68719476736
i = 55761561521
begin + i = 107301169073
Alpaca{1_hat3_c0u913s:fire:}
 26%|████████████████▊                                                 | 4384111379/17179869184 [14:34:08<53:15:46, 66732.51it/s]

フラグを入手できました: Alpaca{1_hat3_c0u913s:fire:}

感想

  • 開始40分経過時点で、すでに正解者様が数名おられました。そのため本記事の手法よりも良い効率的な方法は絶対に存在します！
  • それでも36-bit全探索は数日もあれば終わります！
  • 実は探索中に実行していたコードでは、探索完了後に \text{alice_private}を計算する式を間違えていました。途中の状況を出力していて命拾いしました！