Challenge

脆弱なカップル！

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_public: 1599718256377804952101531599498863772568230618694466120580310027783856775419774715324430490009702307955575844601185230178048816258775546297605599320433889688149788702236901234905522868569967416567225850806042222083340147485157993071805547560375509693951764934940304995906394917881355417525918023021173242172441340007873982292615475287840119272527822675409016385400712544820436845576792437659620501263257558269716031694407258972273378598219915938064730248662540644
bob_public: 1601509205497326911166665651407955633086809897508704527950455620720477838507803621126588237807460352033730891991811162559292107072226732941342412621198125808491110851607803610326932944231441277178997305795098725764729855265846212191447644979975042348063533857732774890088844866567954281331492269751048224888559719840307800593782696008426362668779570407212587612644451479819243906619852333855883749307751229874778873609891502901892234753096522217233589204630723331
leak: 18745015684416423248238358819116531099692322854758287583875043555248837262023679930415710097187512975438125769318401939978478358430852785607010460104247921522906629910012576819904488213243619895103769135299549586169221570769473234206574921382434244366730718275494665736161014808538417501350114510192342412033471326519013144824828968703748628325803878118375663318670612020895929494354336570752213975226257200515892803889402746161532447603042987169336605
encrypted_flag: fb2f1136cea7c67b1edba34d3741eeac8442e70924b03202352422a28237ee6f3fb6d493

Solution

DH鍵交換でアリスの下位1500bitが漏れている。

pは1536bitなので未知は36bitになる。

離散対数問題なので$2^{18}$程度の計算で解ける。

$a=leak+2^{1500}x$

$A\cdot (g^{leak})^{-1}=(g^{2^{1500}})^x$

Final Script

sageだと内部でbsgsやら色々使ったりして$g^x$に対して$O(\sqrt x)$程度で計算してくれます。

from Crypto.Cipher import AES
import hashlib

p = 0xffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca237327ffffffffffffffff
g = 2

A = 1599718256377804952101531599498863772568230618694466120580310027783856775419774715324430490009702307955575844601185230178048816258775546297605599320433889688149788702236901234905522868569967416567225850806042222083340147485157993071805547560375509693951764934940304995906394917881355417525918023021173242172441340007873982292615475287840119272527822675409016385400712544820436845576792437659620501263257558269716031694407258972273378598219915938064730248662540644
B = 1601509205497326911166665651407955633086809897508704527950455620720477838507803621126588237807460352033730891991811162559292107072226732941342412621198125808491110851607803610326932944231441277178997305795098725764729855265846212191447644979975042348063533857732774890088844866567954281331492269751048224888559719840307800593782696008426362668779570407212587612644451479819243906619852333855883749307751229874778873609891502901892234753096522217233589204630723331
a0 = 18745015684416423248238358819116531099692322854758287583875043555248837262023679930415710097187512975438125769318401939978478358430852785607010460104247921522906629910012576819904488213243619895103769135299549586169221570769473234206574921382434244366730718275494665736161014808538417501350114510192342412033471326519013144824828968703748628325803878118375663318670612020895929494354336570752213975226257200515892803889402746161532447603042987169336605

enc = bytes.fromhex("fb2f1136cea7c67b1edba34d3741eeac8442e70924b03202352422a28237ee6f3fb6d493")
nonce, ciphertext = enc[:8], enc[8:]

Zp = Integers(p)
h = Zp(g)^(2^1500)
t = Zp(A) * (Zp(g)^a0)^(-1)
x = discrete_log(t, h, bounds=(0, 2^36), operation='*')
a = a0 + (2^1500) * Integer(x)
shared = power_mod(B, a, p)
key = hashlib.sha256(int(shared).to_bytes(p.nbits()//8, "big")).digest()
cipher = AES.new(key, AES.MODE_CTR, nonce=nonce)
print(cipher.decrypt(ciphertext))