UniVsThreats 26 Quals CTF - Celestial Body - Cryptography Writeup

Category: Cryptography
Flag: UVT{0rb1t4l_c0ngru3nc3_m4k35_pr3d1ct4ble_k3y5}

Challenge Description#

We’ve intercepted a highly classified deep-space transmission!

We know the date the transmission began, but not the exact moment. The spacecraft broadcasts a cryptographic fingerprint of the time alongside its non-consecutive telemetry windows and five snapshots of its internal state, sampled at irregular intervals to resist eavesdropping.

Each sector is authenticated by the spacecraft’s onboard Transmission Authentication Protocol. The signatures are included in the transmission log.

Can you decrypt the flag?

Analysis#

The first thing that mattered was the epoch_hash: only the day is known, but the script truncates sha256("HH:MM:SS") to 16 hex chars, so this is a tiny 86,400-search space. I brute-forced all times in the day immediately.

import hashlib
h="8b156702c993b9b5"
for hh in range(24):
    for mm in range(60):
        for ss in range(60):
            t=f"{hh:02d}:{mm:02d}:{ss:02d}"
            if hashlib.sha256(t.encode()).hexdigest()[:16]==h:
                print(t)
                raise SystemExit

04:12:55

With the exact timestamp recovered, I pulled the important constants from both files to make sure the math model matched the implementation: a 512-bit LCG modulus prime, five non-consecutive samples at steps [0,4,10,18,28], and each sample leaking only the upper 192 bits (UNKNOWN_BITS = 320).

rg -n "TRUNCATE_BITS|UNKNOWN_BITS|STEPS|epoch_hash|tap_sign|generate_telemetry" encrypt.py

9:TRUNCATE_BITS = 192
10:UNKNOWN_BITS  = PRIME_BITS - TRUNCATE_BITS
11:STEPS         = [0, 4, 10, 18, 28]
65:def generate_telemetry(a, b, p):
74:        outputs.append(state >> UNKNOWN_BITS)
120:    epoch_hash = hashlib.sha256(time_str.encode()).hexdigest()[:16]

rg -n "epoch_hash|^p =|t_[0-9]+|iv\s*=|ciphertext\s*=|sig_t" output.txt

2:epoch_hash          = 8b156702c993b9b5
3:p = 10035410270612815279389330410121900529620495869479898461384631211745452304638984576440553552006414411373806160282016417372459090604747980402493134112626213
5:  t_0 = 1129223615711367884405014640005288172041367198689786688285
6:  t_4 = 579514026315281536883405991880758556036404753274817543322
7:  t_10 = 1279648546218423539959079224022586160480305721841176089544
8:  t_18 = 1946366015289015629063708515503091199628321083313573104031
9:  t_28 = 3902208990133988884490762855871313599751888895643028675415
10:iv         = ba04a327ffd0c69205ff5dcb5f463d9c
11:ciphertext = 1879e4d0f174c9a6d2be99b6f632cc0f3ea89989e69dbd080761cb616b37d8eba37635de6c6475d741f69450c8259590
19:  sig_t00 = (r=289099664372750378797408625704893428920316669030, s=952632243424303327990876772909325222302098148060)
20:  sig_t04 = (r=289099664372750378797408625704893428920316669030, s=1272131170288215264283670079256435522443165444185)
21:  sig_t10 = (r=289099664372750378797408625704893428920316669030, s=934252686529025066385350090392561039201739148363)
22:  sig_t18 = (r=289099664372750378797408625704893428920316669030, s=727371275836726048686075601698051388854630211444)
23:  sig_t28 = (r=289099664372750378797408625704893428920316669030, s=886522231176385982733156462394271368291922808313)

The repeated DSA r value is a nonce-reuse smell, so I briefly considered recovering the TAP signing key first, but that would not directly yield the AES key because encryption depends on the LCG final state, not the signing secret.

cry

The clean path was recovering the hidden 320-bit suffix of state_0 from truncated outputs. After deriving a,b from the Halley coordinate seed at 04:12:55, I used the affine relation state_s = a^s*state_0 + b*(a^s-1)*(a-1)^(-1) mod p, rewrote each sample constraint as a bounded modular equation, then solved the hidden-number instance with an LLL-reduced CVP lattice (fpylll). That gives low(state_0), reconstructs exact states at steps 4/10/18/28, and then the script computes final_state, derives SHA-256 key material, and decrypts the CBC ciphertext.

import hashlib
from Crypto.Util.number import bytes_to_long,long_to_bytes
from skyfield.api import load
from skyfield.data import mpc
from skyfield.constants import GM_SUN_Pitjeva_2005_km3_s2 as GM_SUN
from fpylll import IntegerMatrix, LLL, CVP
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad

p=10035410270612815279389330410121900529620495869479898461384631211745452304638984576440553552006414411373806160282016417372459090604747980402493134112626213
tele={0:1129223615711367884405014640005288172041367198689786688285,4:579514026315281536883405991880758556036404753274817543322,10:1279648546218423539959079224022586160480305721841176089544,18:1946366015289015629063708515503091199628321083313573104031,28:3902208990133988884490762855871313599751888895643028675415}
M=1<<320
iv=bytes.fromhex("ba04a327ffd0c69205ff5dcb5f463d9c")
ct=bytes.fromhex("1879e4d0f174c9a6d2be99b6f632cc0f3ea89989e69dbd080761cb616b37d8eba37635de6c6475d741f69450c8259590")

h="8b156702c993b9b5"
found=None
for hh in range(24):
    for mm in range(60):
        for ss in range(60):
            t=f"{hh:02d}:{mm:02d}:{ss:02d}"
            if hashlib.sha256(t.encode()).hexdigest()[:16]==h:
                found=(hh,mm,ss); break
        if found: break
    if found: break
print("time",found)

with load.open("CometEls.txt") as f:
    comets=mpc.load_comets_dataframe(f)
comets=comets.set_index("designation",drop=False)
row=comets.loc["1P/Halley"]
ts=load.timescale(); t=ts.utc(2026,1,26,*found)
eph=load("de421.bsp"); sun=eph["sun"]
halley=sun+mpc.comet_orbit(row,ts,GM_SUN)
x,y,z=sun.at(t).observe(halley).position.au
coord=f"{x:.10f}_{y:.10f}_{z:.10f}"
a=bytes_to_long(hashlib.sha512((coord+"_A").encode()).digest())
b=bytes_to_long(hashlib.sha512((coord+"_B").encode()).digest())
print("coord",coord)

steps=[4,10,18,28]
A=[]; D=[]
for s in steps:
    As=pow(a,s,p)
    Bs=(b*(As-1)*pow(a-1,-1,p))%p
    Di=(As*tele[0]*M + Bs - tele[s]*M)%p
    A.append(As); D.append(Di)

B=IntegerMatrix(5,5)
B[0,0]=1
for i in range(4):
    B[0,i+1]=A[i]
for i in range(4):
    B[i+1,i+1]=p
LLL.reduction(B)
v=CVP.closest_vector(B,[0]+[-x for x in D])
l0=int(v[0])
print("l0_bits",l0.bit_length())

s0=tele[0]*M+l0
def adv(s,n):
    for _ in range(n):
        s=(a*s+b)%p
    return s
s28=adv(s0,28)
final_state=(a*s28+b)%p
key=hashlib.sha256(long_to_bytes(final_state)).digest()
pt=unpad(AES.new(key,AES.MODE_CBC,iv).decrypt(ct),16)
print(pt.decode())

time (4, 12, 55)
coord -19.4862860815_29.1000971321_1.8433470888
l0_bits 320
UVT{0rb1t4l_c0ngru3nc3_m4k35_pr3d1ct4ble_k3y5}

Once the lattice candidate satisfied all truncated telemetry equations and decrypted clean PKCS#7 output with the expected UVT{...} format, the solve was complete.

dance

Solution#

# solve.py
#!/usr/bin/env python3.12
import hashlib
from Crypto.Util.number import bytes_to_long, long_to_bytes
from skyfield.api import load
from skyfield.data import mpc
from skyfield.constants import GM_SUN_Pitjeva_2005_km3_s2 as GM_SUN
from fpylll import IntegerMatrix, LLL, CVP
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad

p = 10035410270612815279389330410121900529620495869479898461384631211745452304638984576440553552006414411373806160282016417372459090604747980402493134112626213
tele = {
    0: 1129223615711367884405014640005288172041367198689786688285,
    4: 579514026315281536883405991880758556036404753274817543322,
    10: 1279648546218423539959079224022586160480305721841176089544,
    18: 1946366015289015629063708515503091199628321083313573104031,
    28: 3902208990133988884490762855871313599751888895643028675415,
}
M = 1 << 320
iv = bytes.fromhex("ba04a327ffd0c69205ff5dcb5f463d9c")
ct = bytes.fromhex("1879e4d0f174c9a6d2be99b6f632cc0f3ea89989e69dbd080761cb616b37d8eba37635de6c6475d741f69450c8259590")

epoch_hash = "8b156702c993b9b5"

found = None
for hh in range(24):
    for mm in range(60):
        for ss in range(60):
            t = f"{hh:02d}:{mm:02d}:{ss:02d}"
            if hashlib.sha256(t.encode()).hexdigest()[:16] == epoch_hash:
                found = (hh, mm, ss)
                break
        if found:
            break
    if found:
        break

with load.open("CometEls.txt") as f:
    comets = mpc.load_comets_dataframe(f)

comets = comets.set_index("designation", drop=False)
row = comets.loc["1P/Halley"]
ts = load.timescale()
t = ts.utc(2026, 1, 26, *found)
eph = load("de421.bsp")
sun = eph["sun"]
halley = sun + mpc.comet_orbit(row, ts, GM_SUN)
x, y, z = sun.at(t).observe(halley).position.au

coord = f"{x:.10f}_{y:.10f}_{z:.10f}"
a = bytes_to_long(hashlib.sha512((coord + "_A").encode()).digest())
b = bytes_to_long(hashlib.sha512((coord + "_B").encode()).digest())

steps = [4, 10, 18, 28]
A = []
D = []
for s in steps:
    As = pow(a, s, p)
    Bs = (b * (As - 1) * pow(a - 1, -1, p)) % p
    Di = (As * tele[0] * M + Bs - tele[s] * M) % p
    A.append(As)
    D.append(Di)

B = IntegerMatrix(5, 5)
B[0, 0] = 1
for i in range(4):
    B[0, i + 1] = A[i]
for i in range(4):
    B[i + 1, i + 1] = p

LLL.reduction(B)
v = CVP.closest_vector(B, [0] + [-x for x in D])
l0 = int(v[0])

s0 = tele[0] * M + l0
assert 0 <= s0 < p

def advance(state, rounds):
    for _ in range(rounds):
        state = (a * state + b) % p
    return state

s28 = advance(s0, 28)
final_state = (a * s28 + b) % p

key = hashlib.sha256(long_to_bytes(final_state)).digest()
pt = unpad(AES.new(key, AES.MODE_CBC, iv).decrypt(ct), 16)
print(pt.decode())

python3.12 solve.py

UVT{0rb1t4l_c0ngru3nc3_m4k35_pr3d1ct4ble_k3y5}