Baby_Time_Capsule | T4QI-Blog

Vulnerability Analysis

The provided server.py script reveals the following cryptographic setup:

Message: The same FLAG is encrypted every time a user requests a “time capsule.”
Public Exponent ($e$): Fixed at 5.
Modulus ($n$): A new $1024$-bit RSA modulus is generated for every request.
Process: Each time you ask for a capsule, the server provides a new ciphertext $c_i \equiv m^5 \pmod{n_i}$ and the corresponding public key $(n_i, 5)$.

Because the same message $m$ is encrypted with the same small $e=5$ multiple times (to different $n_i$), the system is vulnerable to Håstad’s Broadcast Attack.

The Attack (Håstad’s Broadcast)

If we collect $k$ pairs of ciphertexts and moduli such that $k \ge e$, we can use the Chinese Remainder Theorem (CRT) to find the value of $m^e$.

Collect Data: We need at least $5$ ciphertexts ($c_1, c_2, c_3, c_4, c_5$) and their corresponding moduli ($n_1, n_2, n_3, n_4, n_5$).
Apply CRT: We solve the system of congruences to find a large integer $C$:

$$C \equiv m^5 \pmod{n_1 \cdot n_2 \cdot n_3 \cdot n_4 \cdot n_5}$$
Integer Root: Since $m < n_i$ and we have used $5$ moduli, the product of the moduli is guaranteed to be larger than $m^5$. Therefore, $C$ is exactly equal to $m^5$ in the integers. We can simply take the 5th integer root of $C$ to recover $m$.

Implementation

PYTHON

from pwn import *
import gmpy2

ciphertexts = [
    22059973396265711225547337402676949429780188216104887821818726071218719187258722310941900168763228537122236120013236139314239442617692939733148360709831070066944827051363269362601020608423440794621394353326097798099096170247961991180529016162814076281330849424763580580515247155845116036229118343903368264409,
    75961846872581782324425725432247237743856082349436338037795099649507373384870898030732891030817522525051477063808211925009153885397004981413879506307494064572069366997487816910876938006279028022092501404259818026158497104020000724478030803164251377863165773211041119611422949726210363800766907017840302741583,
    7293186519544616442352693972567692589739327364822572287940727547387220433908132723380215717922083535354401044489094046968109664230708312817852949122104575178658184490895396447432661529519733829696514914967856061126204873882288941206033651443527706146256995282988142845111819636709856781153825267280167060727,
    53860574732388609696496740712426628298161038533488932816814364353880279104972497213339595520479262515054233732152965583588662300959812223491813434997974295368918879131596475913762875967937512934551625997703497070981211707260718568363375865102444862532950182606183783499418400100240657754555209514743969383630,
    68955242536547587768761265444935128404367161719412635235604543414337037290187633030852117695059318001850014698151458572280360185795130719480760249672474796423874806701595354589081820206895105099822144830769387696740508037687105288313662552927284523104275651673566464646547225173745962664244644981171986277083,
]

moduli = [
    125918202549311606835029707872808675995449354711880649633647397124740832862115659225300853218404483974472266981710439448001572731203924582051852191730686629210534041348811735002580131543965679147369916735518087336180677234756470495948183811462492217377734521819776006823851523950964044295451864585705893411037,
    119776996226454675816240363839097927741540759982302972662007784263807381551781298002976820806502568264637400947320988144926912376551225252428392567179604284807527902726089548195500590740406311812567324869154204915489157061583602356966908351073973954373157594145241207693984162704351841489015657363543789779883,
    160678057581887265106339724891721561712476717468618087045411317933346998745536655478761763272555359438772990358091772078453185359064119849419415217209819117154764298986664139961652850968104752855163343091278195143358628947312372039121567040976924072091292060777251484231596183450447933121139931614118333124337,
    90451245486521588904584129528024713938942915303505539209642480756660276562738754373847617601354274403235790614545696503599202391747927643655171734429203520664939331279070584037484623586514196695766841813248944177630619405787843135101507726844179985936108042060848963921326738655377985654647989844385602754833,
    123435331568661004907689495954798046361130943091201114832579463148484906634044173831141435275279027833101109638659950402953102462394838793203301416634703302293952402158124202105717264955008878212412194364725802586523963626068662655334390663166964067103425064811282173127337399126242501850567048097240231335319,
]


def solve_crt(remainders, moduli):
    N = 1
    for n in moduli:
        N *= n

    result = 0
    for c_i, n_i in zip(remainders, moduli):
        M_i = N // n_i
        y_i = gmpy2.invert(M_i, n_i)
        result += c_i * M_i * y_i

    return result % N



C = solve_crt(ciphertexts, moduli)


m, exact = gmpy2.iroot(C, 5)

if exact:
    flag = bytes.fromhex(hex(m)[2:]).decode()
    print(f"Captured the flag: {flag}")