https://app.hackthebox.com/challenges/419

Description

Quick, there's a new custom Pokemon in the bush called "The Custom Pokemon". Can you find out what its weakness is and capture it?

Source

output.txt

p = 163924920994230253637901818188432016168244271739612329857589126113342762280179217681751572174802922903476854156324228497960403054780444742311082033470378692771947296079573091561798164949003989592245623978327019668789826246878280613414312438425787726549209707561194579292492350868953301012702750092281807657719
g = 97407673851268146184804267386115296213106535602908738837573109808033224187746927894605766365039669844761355888387043653015559933298433068597707383843814893442087063136640943475006105673619942401850890433169719970841218851182254280222787630139143746993351533776324254770080289574521452767936507196421481076841
h = 7771801879117000288817915415260102060832587957130098985489551063161695391373720317596178655146834967333192201720460001561670355858493084613455139466487717364432242890680666229302181326080340061384604634749443972114930849979067572441792867514664636574923631540074373758015873624100768698622048136552173788916
(c1, c2) = (83194887666722435308945316429939841668109985194860518882743309895332330525232854733374220834562004665371728589040849388337869965962272329974327341953512030547150987478914221697662859702721549751949905379177524490596978865458493461926865553151329446008396048857775620413257603550197735539508582063967332954541, 46980139827823872709797876525359718565495105542826335055296195898993549717497706297570900140303523646691120660896057591142474133027314700072754720423416473219145616105901315902667461002549138134613137623172629251106773324834864521095329972962212429468236356687505826351839310216384806147074454773818037349470)

chal.py

from Crypto.Util.number import bytes_to_long, getPrime
import random

FLAG = b'HTB{???????????????????????????????????????????????????}'

def gen_params():
    p = getPrime(1024)
    g = random.randint(2, p - 2)
    x = random.randint(2, p - 2)
    h = pow(g, x, p)
    return (p, g, h), x

def encrypt(pubkey):
    p, g, h = pubkey
    m = bytes_to_long(FLAG)
    y = random.randint(2, p - 2)
    s = pow(h, y, p)
    return (g * y % p, m * s % p)

def main():
    pubkey, _ = gen_params()
    c1, c2 = encrypt(pubkey)
    with open('out.txt', 'w') as f:
        f.write(
            f'p = {pubkey[0]}\ng = {pubkey[1]}\nh = {pubkey[2]}\n(c1, c2) = ({c1}, {c2})\n'
        )

if __name__ == "__main__":
    main()

Exploitation

#!/usr/bin/python3
from Crypto.Util.number import long_to_bytes, inverse

p = 163924920994230253637901818188432016168244271739612329857589126113342762280179217681751572174802922903476854156324228497960403054780444742311082033470378692771947296079573091561798164949003989592245623978327019668789826246878280613414312438425787726549209707561194579292492350868953301012702750092281807657719
g = 97407673851268146184804267386115296213106535602908738837573109808033224187746927894605766365039669844761355888387043653015559933298433068597707383843814893442087063136640943475006105673619942401850890433169719970841218851182254280222787630139143746993351533776324254770080289574521452767936507196421481076841
h = 7771801879117000288817915415260102060832587957130098985489551063161695391373720317596178655146834967333192201720460001561670355858493084613455139466487717364432242890680666229302181326080340061384604634749443972114930849979067572441792867514664636574923631540074373758015873624100768698622048136552173788916
c1 = 83194887666722435308945316429939841668109985194860518882743309895332330525232854733374220834562004665371728589040849388337869965962272329974327341953512030547150987478914221697662859702721549751949905379177524490596978865458493461926865553151329446008396048857775620413257603550197735539508582063967332954541
c2 = 46980139827823872709797876525359718565495105542826335055296195898993549717497706297570900140303523646691120660896057591142474133027314700072754720423416473219145616105901315902667461002549138134613137623172629251106773324834864521095329972962212429468236356687505826351839310216384806147074454773818037349470

g_inv = inverse(g, p)
y = (c1 * g_inv) % p
s = pow(h, y, p)
s_inv = inverse(s, p)
m = (c2 * s_inv) % p
flag = long_to_bytes(m)
print(flag.decode())

Summary

Gonna Lift Em All: reconstruct the PRNG state from the leak, replay it, and recover the flag.